Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2015 Cisco and/or its affiliates. |
| 3 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | * you may not use this file except in compliance with the License. |
| 5 | * You may obtain a copy of the License at: |
| 6 | * |
| 7 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | * |
| 9 | * Unless required by applicable law or agreed to in writing, software |
| 10 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | * See the License for the specific language governing permissions and |
| 13 | * limitations under the License. |
| 14 | */ |
| 15 | /* |
| 16 | Copyright (c) 2001, 2002, 2003, 2004 Eliot Dresselhaus |
| 17 | |
| 18 | Permission is hereby granted, free of charge, to any person obtaining |
| 19 | a copy of this software and associated documentation files (the |
| 20 | "Software"), to deal in the Software without restriction, including |
| 21 | without limitation the rights to use, copy, modify, merge, publish, |
| 22 | distribute, sublicense, and/or sell copies of the Software, and to |
| 23 | permit persons to whom the Software is furnished to do so, subject to |
| 24 | the following conditions: |
| 25 | |
| 26 | The above copyright notice and this permission notice shall be |
| 27 | included in all copies or substantial portions of the Software. |
| 28 | |
| 29 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 30 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 31 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 32 | NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
| 33 | LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
| 34 | OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
| 35 | WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 36 | */ |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 37 | /** @file |
| 38 | * @brief Fixed length block allocator. |
| 39 | Pools are built from clib vectors and bitmaps. Use pools when |
| 40 | repeatedly allocating and freeing fixed-size data. Pools are |
| 41 | fast, and avoid memory fragmentation. |
| 42 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 43 | |
| 44 | #ifndef included_pool_h |
| 45 | #define included_pool_h |
| 46 | |
| 47 | #include <vppinfra/bitmap.h> |
| 48 | #include <vppinfra/error.h> |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 49 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 50 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 51 | typedef struct |
| 52 | { |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 53 | /** Bitmap of indices of free objects. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 54 | uword *free_bitmap; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 55 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 56 | /** Vector of free indices. One element for each set bit in bitmap. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 57 | u32 *free_indices; |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 58 | |
| 59 | /* The following fields are set for fixed-size, preallocated pools */ |
| 60 | |
| 61 | /** Maximum size of the pool, in elements */ |
| 62 | u32 max_elts; |
| 63 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 64 | } pool_header_t; |
| 65 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 66 | /** Get pool header from user pool pointer */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 67 | always_inline pool_header_t * |
| 68 | pool_header (void *v) |
| 69 | { |
Damjan Marion | a4a28f0 | 2022-03-17 15:46:25 +0100 | [diff] [blame] | 70 | return vec_header (v); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 71 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 72 | |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 73 | void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts, |
| 74 | uword align); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 75 | |
| 76 | /** initialize a fixed-size, preallocated pool */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 77 | #define pool_init_fixed(P, E) \ |
| 78 | _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0)); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 79 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 80 | /** Validate a pool */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 81 | always_inline void |
| 82 | pool_validate (void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 83 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 84 | pool_header_t *p = pool_header (v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 85 | uword i, n_free_bitmap; |
| 86 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 87 | if (!v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 88 | return; |
| 89 | |
| 90 | n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap); |
| 91 | ASSERT (n_free_bitmap == vec_len (p->free_indices)); |
| 92 | for (i = 0; i < vec_len (p->free_indices); i++) |
| 93 | ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1); |
| 94 | } |
| 95 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 96 | /** Number of active elements in a pool. |
| 97 | * @return Number of active elements in a pool |
| 98 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 99 | always_inline uword |
| 100 | pool_elts (void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 101 | { |
| 102 | uword ret = vec_len (v); |
| 103 | if (v) |
| 104 | ret -= vec_len (pool_header (v)->free_indices); |
| 105 | return ret; |
| 106 | } |
| 107 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 108 | /** Number of elements in pool vector. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 109 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 110 | @note You probably want to call pool_elts() instead. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 111 | */ |
| 112 | #define pool_len(p) vec_len(p) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 113 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 114 | /** Number of elements in pool vector (usable as an lvalue) |
| 115 | |
| 116 | @note You probably don't want to use this macro. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 117 | */ |
| 118 | #define _pool_len(p) _vec_len(p) |
| 119 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 120 | /** Memory usage of pool header. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 121 | always_inline uword |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 122 | pool_header_bytes (void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 123 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 124 | pool_header_t *p = pool_header (v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 125 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 126 | if (!v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 127 | return 0; |
| 128 | |
| 129 | return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices); |
| 130 | } |
| 131 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 132 | /** Memory usage of pool. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 133 | #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P)) |
| 134 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 135 | /** Local variable naming macro. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 136 | #define _pool_var(v) _pool_##v |
| 137 | |
Florin Coras | 400d459 | 2022-03-09 13:34:12 -0800 | [diff] [blame] | 138 | /** Number of elements that can fit into pool with current allocation */ |
Damjan Marion | 5c45d1c | 2022-03-17 15:32:56 +0100 | [diff] [blame] | 139 | #define pool_max_len(P) vec_max_len (P) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 140 | |
Florin Coras | 400d459 | 2022-03-09 13:34:12 -0800 | [diff] [blame] | 141 | /** Number of free elements in pool */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 142 | static_always_inline uword |
| 143 | _pool_free_elts (void *p, uword elt_sz) |
| 144 | { |
| 145 | pool_header_t *ph; |
| 146 | uword n_free; |
| 147 | |
| 148 | if (p == 0) |
| 149 | return 0; |
| 150 | |
| 151 | ph = pool_header (p); |
| 152 | |
| 153 | n_free = vec_len (ph->free_indices); |
| 154 | |
| 155 | /* Fixed-size pools have max_elts set non-zero */ |
| 156 | if (ph->max_elts == 0) |
| 157 | n_free += _vec_max_len (p, elt_sz) - vec_len (p); |
| 158 | |
| 159 | return n_free; |
| 160 | } |
| 161 | |
| 162 | #define pool_free_elts(P) _pool_free_elts ((void *) (P), _vec_elt_sz (P)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 163 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 164 | /** Allocate an object E from a pool P (general version). |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 165 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 166 | First search free list. If nothing is free extend vector of objects. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 167 | */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 168 | |
| 169 | static_always_inline void |
| 170 | _pool_get (void **pp, void **ep, uword align, int zero, uword elt_sz) |
| 171 | { |
| 172 | uword len = 0; |
| 173 | void *p = pp[0]; |
| 174 | void *e; |
Damjan Marion | e4fa1d2 | 2022-04-11 18:41:49 +0200 | [diff] [blame^] | 175 | vec_attr_t va = { .hdr_sz = sizeof (pool_header_t), |
| 176 | .elt_sz = elt_sz, |
| 177 | .align = align }; |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 178 | |
| 179 | if (p) |
| 180 | { |
| 181 | pool_header_t *ph = pool_header (p); |
| 182 | uword n_free = vec_len (ph->free_indices); |
| 183 | |
| 184 | if (n_free) |
| 185 | { |
| 186 | uword index = ph->free_indices[n_free - 1]; |
| 187 | e = p + index * elt_sz; |
| 188 | ph->free_bitmap = |
| 189 | clib_bitmap_andnoti_notrim (ph->free_bitmap, index); |
Damjan Marion | 8bea589 | 2022-04-04 22:40:45 +0200 | [diff] [blame] | 190 | vec_set_len (ph->free_indices, n_free - 1); |
Damjan Marion | 79934e8 | 2022-04-05 12:40:31 +0200 | [diff] [blame] | 191 | clib_mem_unpoison (e, elt_sz); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 192 | goto done; |
| 193 | } |
| 194 | |
| 195 | if (ph->max_elts) |
| 196 | { |
| 197 | clib_warning ("can't expand fixed-size pool"); |
| 198 | os_out_of_memory (); |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | len = vec_len (p); |
| 203 | |
| 204 | /* Nothing on free list, make a new element and return it. */ |
Damjan Marion | e4fa1d2 | 2022-04-11 18:41:49 +0200 | [diff] [blame^] | 205 | p = _vec_realloc_internal (p, len + 1, &va); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 206 | e = p + len * elt_sz; |
| 207 | |
| 208 | _vec_update_pointer (pp, p); |
| 209 | |
| 210 | done: |
| 211 | ep[0] = e; |
| 212 | if (zero) |
| 213 | clib_memset_u8 (e, 0, elt_sz); |
| 214 | } |
| 215 | |
Damjan Marion | 3cfd529 | 2022-03-18 15:48:12 +0100 | [diff] [blame] | 216 | #define _pool_get_aligned_internal(P, E, A, Z) \ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 217 | _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z, \ |
| 218 | _vec_elt_sz (P)) |
Dave Barach | a690fdb | 2020-01-21 12:34:55 -0500 | [diff] [blame] | 219 | |
Dave Barach | bf3443b | 2018-10-18 15:37:49 -0400 | [diff] [blame] | 220 | /** Allocate an object E from a pool P with alignment A */ |
| 221 | #define pool_get_aligned(P,E,A) _pool_get_aligned_internal(P,E,A,0) |
| 222 | |
| 223 | /** Allocate an object E from a pool P with alignment A and zero it */ |
| 224 | #define pool_get_aligned_zero(P,E,A) _pool_get_aligned_internal(P,E,A,1) |
| 225 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 226 | /** Allocate an object E from a pool P (unspecified alignment). */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 227 | #define pool_get(P,E) pool_get_aligned(P,E,0) |
| 228 | |
Dave Barach | bf3443b | 2018-10-18 15:37:49 -0400 | [diff] [blame] | 229 | /** Allocate an object E from a pool P and zero it */ |
| 230 | #define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0) |
| 231 | |
Damjan Marion | 66d4cb5 | 2022-03-17 18:59:46 +0100 | [diff] [blame] | 232 | always_inline int |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 233 | _pool_get_will_expand (void *p, uword elt_sz) |
Damjan Marion | 66d4cb5 | 2022-03-17 18:59:46 +0100 | [diff] [blame] | 234 | { |
| 235 | pool_header_t *ph; |
| 236 | uword len; |
Dave Barach | 614ac5d | 2017-02-06 09:28:03 -0500 | [diff] [blame] | 237 | |
Damjan Marion | 66d4cb5 | 2022-03-17 18:59:46 +0100 | [diff] [blame] | 238 | if (p == 0) |
| 239 | return 1; |
Stanislav Zaikin | 09abed6 | 2021-11-04 09:32:32 +0100 | [diff] [blame] | 240 | |
Damjan Marion | 66d4cb5 | 2022-03-17 18:59:46 +0100 | [diff] [blame] | 241 | ph = pool_header (p); |
| 242 | |
| 243 | if (ph->max_elts) |
| 244 | len = ph->max_elts; |
| 245 | else |
| 246 | len = vec_len (ph->free_indices); |
| 247 | |
| 248 | /* Free elements, certainly won't expand */ |
| 249 | if (len > 0) |
| 250 | return 0; |
| 251 | |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 252 | return _vec_resize_will_expand (p, 1, elt_sz); |
Damjan Marion | 66d4cb5 | 2022-03-17 18:59:46 +0100 | [diff] [blame] | 253 | } |
| 254 | |
| 255 | #define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0])) |
| 256 | |
| 257 | always_inline int |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 258 | _pool_put_will_expand (void *p, uword index, uword elt_sz) |
Damjan Marion | 66d4cb5 | 2022-03-17 18:59:46 +0100 | [diff] [blame] | 259 | { |
| 260 | pool_header_t *ph = pool_header (p); |
| 261 | |
| 262 | if (clib_bitmap_will_expand (ph->free_bitmap, index)) |
| 263 | return 1; |
| 264 | |
| 265 | if (vec_resize_will_expand (ph->free_indices, 1)) |
| 266 | return 1; |
| 267 | |
| 268 | return 0; |
| 269 | } |
| 270 | |
| 271 | #define pool_put_will_expand(P, E) _pool_put_will_expand (P, (E) - (P), sizeof ((P)[0]) |
Dave Barach | 614ac5d | 2017-02-06 09:28:03 -0500 | [diff] [blame] | 272 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 273 | /** Use free bitmap to query whether given element is free. */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 274 | static_always_inline int |
| 275 | pool_is_free_index (void *p, uword index) |
| 276 | { |
| 277 | pool_header_t *ph = pool_header (p); |
| 278 | return index < vec_len (p) ? clib_bitmap_get (ph->free_bitmap, index) : 1; |
| 279 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 280 | |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 281 | #define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 282 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 283 | /** Free an object E in pool P. */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 284 | static_always_inline void |
| 285 | _pool_put_index (void *p, uword index, uword elt_sz) |
| 286 | { |
| 287 | pool_header_t *ph = pool_header (p); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 288 | |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 289 | ASSERT (index < ph->max_elts ? ph->max_elts : vec_len (p)); |
| 290 | ASSERT (!pool_is_free_index (p, index)); |
| 291 | |
| 292 | /* Add element to free bitmap and to free list. */ |
| 293 | ph->free_bitmap = clib_bitmap_ori_notrim (ph->free_bitmap, index); |
| 294 | |
| 295 | /* Preallocated pool? */ |
| 296 | if (ph->max_elts) |
| 297 | { |
| 298 | ph->free_indices[_vec_len (ph->free_indices)] = index; |
Damjan Marion | 8bea589 | 2022-04-04 22:40:45 +0200 | [diff] [blame] | 299 | vec_inc_len (ph->free_indices, 1); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 300 | } |
| 301 | else |
| 302 | vec_add1 (ph->free_indices, index); |
| 303 | |
Damjan Marion | 79934e8 | 2022-04-05 12:40:31 +0200 | [diff] [blame] | 304 | clib_mem_poison (p + index * elt_sz, elt_sz); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 305 | } |
| 306 | |
| 307 | #define pool_put_index(P, I) _pool_put_index ((void *) (P), I, _vec_elt_sz (P)) |
| 308 | #define pool_put(P, E) pool_put_index (P, (E) - (P)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 309 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 310 | /** Allocate N more free elements to pool (general version). */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 311 | |
| 312 | static_always_inline void |
Damjan Marion | 2473858 | 2022-03-31 15:12:20 +0200 | [diff] [blame] | 313 | _pool_alloc (void **pp, uword n_elts, uword align, void *heap, uword elt_sz) |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 314 | { |
| 315 | pool_header_t *ph = pool_header (pp[0]); |
| 316 | uword len = vec_len (pp[0]); |
Damjan Marion | e4fa1d2 | 2022-04-11 18:41:49 +0200 | [diff] [blame^] | 317 | const vec_attr_t va = { .hdr_sz = sizeof (pool_header_t), |
| 318 | .elt_sz = elt_sz, |
| 319 | .align = align, |
| 320 | .heap = heap }; |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 321 | |
| 322 | if (ph && ph->max_elts) |
| 323 | { |
| 324 | clib_warning ("Can't expand fixed-size pool"); |
| 325 | os_out_of_memory (); |
| 326 | } |
| 327 | |
Damjan Marion | e4fa1d2 | 2022-04-11 18:41:49 +0200 | [diff] [blame^] | 328 | pp[0] = _vec_resize_internal (pp[0], len + n_elts, &va); |
Damjan Marion | 8bea589 | 2022-04-04 22:40:45 +0200 | [diff] [blame] | 329 | _vec_set_len (pp[0], len, elt_sz); |
Damjan Marion | 79934e8 | 2022-04-05 12:40:31 +0200 | [diff] [blame] | 330 | clib_mem_poison (pp[0] + len * elt_sz, n_elts * elt_sz); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 331 | |
| 332 | ph = pool_header (pp[0]); |
| 333 | vec_resize (ph->free_indices, n_elts); |
Damjan Marion | 8bea589 | 2022-04-04 22:40:45 +0200 | [diff] [blame] | 334 | vec_dec_len (ph->free_indices, n_elts); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 335 | clib_bitmap_vec_validate (ph->free_bitmap, len + n_elts - 1); |
| 336 | } |
| 337 | |
Damjan Marion | 2473858 | 2022-03-31 15:12:20 +0200 | [diff] [blame] | 338 | #define pool_alloc_aligned_heap(P, N, A, H) \ |
| 339 | _pool_alloc ((void **) &(P), N, _vec_align (P, A), H, _vec_elt_sz (P)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 340 | |
Damjan Marion | 2473858 | 2022-03-31 15:12:20 +0200 | [diff] [blame] | 341 | #define pool_alloc_heap(P, N, H) pool_alloc_aligned_heap (P, N, 0, H) |
| 342 | #define pool_alloc_aligned(P, N, A) pool_alloc_aligned_heap (P, N, A, 0) |
| 343 | #define pool_alloc(P, N) pool_alloc_aligned_heap (P, N, 0, 0) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 344 | |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 345 | static_always_inline void * |
| 346 | _pool_dup (void *p, uword align, uword elt_sz) |
| 347 | { |
| 348 | pool_header_t *nph, *ph = pool_header (p); |
| 349 | uword len = vec_len (p); |
Damjan Marion | e4fa1d2 | 2022-04-11 18:41:49 +0200 | [diff] [blame^] | 350 | const vec_attr_t va = { .hdr_sz = sizeof (pool_header_t), |
| 351 | .elt_sz = elt_sz, |
| 352 | .align = align }; |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 353 | void *n; |
| 354 | |
| 355 | if (ph && ph->max_elts) |
| 356 | { |
| 357 | clib_warning ("Can't expand fixed-size pool"); |
| 358 | os_out_of_memory (); |
| 359 | } |
| 360 | |
Damjan Marion | e4fa1d2 | 2022-04-11 18:41:49 +0200 | [diff] [blame^] | 361 | n = _vec_alloc_internal (len, &va); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 362 | nph = pool_header (n); |
| 363 | clib_memset_u8 (nph, 0, sizeof (vec_header_t)); |
| 364 | |
| 365 | if (len) |
| 366 | { |
| 367 | u32 *fi; |
| 368 | vec_foreach (fi, ph->free_indices) |
Damjan Marion | 79934e8 | 2022-04-05 12:40:31 +0200 | [diff] [blame] | 369 | clib_mem_unpoison (p + elt_sz * fi[0], elt_sz); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 370 | |
| 371 | clib_memcpy_fast (n, p, len * elt_sz); |
| 372 | |
| 373 | nph->free_bitmap = clib_bitmap_dup (ph->free_bitmap); |
| 374 | nph->free_indices = vec_dup (ph->free_indices); |
| 375 | |
| 376 | vec_foreach (fi, ph->free_indices) |
| 377 | { |
| 378 | uword offset = elt_sz * fi[0]; |
Damjan Marion | 79934e8 | 2022-04-05 12:40:31 +0200 | [diff] [blame] | 379 | clib_mem_poison (p + offset, elt_sz); |
| 380 | clib_mem_poison (n + offset, elt_sz); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 381 | } |
| 382 | } |
| 383 | |
| 384 | return n; |
| 385 | } |
| 386 | |
Florin Coras | 8be6c40 | 2018-11-27 17:11:37 -0800 | [diff] [blame] | 387 | /** |
| 388 | * Return copy of pool with alignment |
| 389 | * |
| 390 | * @param P pool to copy |
| 391 | * @param A alignment (may be zero) |
| 392 | * @return copy of pool |
| 393 | */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 394 | |
Benoît Ganne | 563ec99 | 2021-11-19 13:39:10 +0100 | [diff] [blame] | 395 | #define pool_dup_aligned(P, A) \ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 396 | _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P)) |
Florin Coras | 8be6c40 | 2018-11-27 17:11:37 -0800 | [diff] [blame] | 397 | |
| 398 | /** |
| 399 | * Return copy of pool without alignment |
| 400 | * |
| 401 | * @param P pool to copy |
| 402 | * @return copy of pool |
| 403 | */ |
Florin Coras | 47c40e2 | 2018-11-26 17:01:36 -0800 | [diff] [blame] | 404 | #define pool_dup(P) pool_dup_aligned(P,0) |
Florin Coras | 8be6c40 | 2018-11-27 17:11:37 -0800 | [diff] [blame] | 405 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 406 | /** Low-level free pool operator (do not call directly). */ |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 407 | always_inline void |
| 408 | _pool_free (void **v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 409 | { |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 410 | pool_header_t *p = pool_header (v[0]); |
| 411 | if (!p) |
| 412 | return; |
| 413 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 414 | clib_bitmap_free (p->free_bitmap); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 415 | |
Damjan Marion | 86bbdf9 | 2022-03-18 12:28:35 +0100 | [diff] [blame] | 416 | vec_free (p->free_indices); |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 417 | _vec_free (v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 418 | } |
Damjan Marion | 299571a | 2022-03-19 00:07:52 +0100 | [diff] [blame] | 419 | #define pool_free(p) _pool_free ((void **) &(p)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 420 | |
Damjan Marion | 62c25ab | 2020-12-12 23:32:12 +0100 | [diff] [blame] | 421 | static_always_inline uword |
| 422 | pool_get_first_index (void *pool) |
| 423 | { |
| 424 | pool_header_t *h = pool_header (pool); |
| 425 | return clib_bitmap_first_clear (h->free_bitmap); |
| 426 | } |
| 427 | |
| 428 | static_always_inline uword |
| 429 | pool_get_next_index (void *pool, uword last) |
| 430 | { |
| 431 | pool_header_t *h = pool_header (pool); |
| 432 | return clib_bitmap_next_clear (h->free_bitmap, last + 1); |
| 433 | } |
| 434 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 435 | /** Optimized iteration through pool. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 436 | |
| 437 | @param LO pointer to first element in chunk |
| 438 | @param HI pointer to last element in chunk |
| 439 | @param POOL pool to iterate across |
| 440 | @param BODY operation to perform |
| 441 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 442 | Optimized version which assumes that BODY is smart enough to |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 443 | process multiple (LOW,HI) chunks. See also pool_foreach(). |
| 444 | */ |
| 445 | #define pool_foreach_region(LO,HI,POOL,BODY) \ |
| 446 | do { \ |
| 447 | uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \ |
| 448 | uword _pool_var (bl), * _pool_var (b); \ |
| 449 | pool_header_t * _pool_var (p); \ |
| 450 | \ |
| 451 | _pool_var (p) = pool_header (POOL); \ |
| 452 | _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0; \ |
| 453 | _pool_var (bl) = vec_len (_pool_var (b)); \ |
| 454 | _pool_var (len) = vec_len (POOL); \ |
| 455 | _pool_var (lo) = 0; \ |
| 456 | \ |
| 457 | for (_pool_var (i) = 0; \ |
| 458 | _pool_var (i) <= _pool_var (bl); \ |
| 459 | _pool_var (i)++) \ |
| 460 | { \ |
| 461 | uword _pool_var (m), _pool_var (f); \ |
| 462 | _pool_var (m) = (_pool_var (i) < _pool_var (bl) \ |
| 463 | ? _pool_var (b) [_pool_var (i)] \ |
| 464 | : 1); \ |
| 465 | while (_pool_var (m) != 0) \ |
| 466 | { \ |
| 467 | _pool_var (f) = first_set (_pool_var (m)); \ |
| 468 | _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0]) \ |
| 469 | + min_log2 (_pool_var (f))); \ |
| 470 | _pool_var (hi) = (_pool_var (i) < _pool_var (bl) \ |
| 471 | ? _pool_var (hi) : _pool_var (len)); \ |
| 472 | _pool_var (m) ^= _pool_var (f); \ |
| 473 | if (_pool_var (hi) > _pool_var (lo)) \ |
| 474 | { \ |
| 475 | (LO) = _pool_var (lo); \ |
| 476 | (HI) = _pool_var (hi); \ |
| 477 | do { BODY; } while (0); \ |
| 478 | } \ |
| 479 | _pool_var (lo) = _pool_var (hi) + 1; \ |
| 480 | } \ |
| 481 | } \ |
| 482 | } while (0) |
| 483 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 484 | /** Iterate through pool. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 485 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 486 | @param VAR A variable of same type as pool vector to be used as an |
| 487 | iterator. |
| 488 | @param POOL The pool to iterate across. |
| 489 | @param BODY The operation to perform, typically a code block. See |
| 490 | the example below. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 491 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 492 | This macro will call @c BODY with each active pool element. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 493 | |
| 494 | It is a bad idea to allocate or free pool element from within |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 495 | @c pool_foreach. Build a vector of indices and dispose of them later. |
Neale Ranns | 87df12d | 2017-02-18 08:16:41 -0800 | [diff] [blame] | 496 | Or call pool_flush. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 497 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 498 | |
| 499 | @par Example |
| 500 | @code{.c} |
| 501 | proc_t *procs; // a pool of processes. |
| 502 | proc_t *proc; // pointer to one process; used as the iterator. |
| 503 | |
| 504 | pool_foreach (proc, procs, ({ |
| 505 | if (proc->state != PROC_STATE_RUNNING) |
| 506 | continue; |
| 507 | |
| 508 | // check a running proc in some way |
| 509 | ... |
| 510 | })); |
| 511 | @endcode |
| 512 | |
| 513 | @warning Because @c pool_foreach is a macro, syntax errors can be |
| 514 | difficult to find inside @c BODY, let alone actual code bugs. One |
| 515 | can temporarily split a complex @c pool_foreach into a trivial |
| 516 | @c pool_foreach which builds a vector of active indices, and a |
| 517 | vec_foreach() (or plain for-loop) to walk the active index vector. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 518 | */ |
Damjan Marion | 62c25ab | 2020-12-12 23:32:12 +0100 | [diff] [blame] | 519 | |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame] | 520 | #define pool_foreach(VAR,POOL) \ |
Damjan Marion | 62c25ab | 2020-12-12 23:32:12 +0100 | [diff] [blame] | 521 | if (POOL) \ |
| 522 | for (VAR = POOL + pool_get_first_index (POOL); \ |
| 523 | VAR < vec_end (POOL); \ |
| 524 | VAR = POOL + pool_get_next_index (POOL, VAR - POOL)) |
| 525 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 526 | /** Returns pointer to element at given index. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 527 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 528 | ASSERTs that the supplied index is valid. |
| 529 | Even though one can write correct code of the form |
| 530 | @code |
| 531 | p = pool_base + index; |
| 532 | @endcode |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 533 | use of @c pool_elt_at_index is strongly suggested. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 534 | */ |
| 535 | #define pool_elt_at_index(p,i) \ |
| 536 | ({ \ |
| 537 | typeof (p) _e = (p) + (i); \ |
| 538 | ASSERT (! pool_is_free (p, _e)); \ |
| 539 | _e; \ |
| 540 | }) |
| 541 | |
Chris Luke | 8e5b041 | 2016-07-26 13:06:10 -0400 | [diff] [blame] | 542 | /** Return next occupied pool index after @c i, useful for safe iteration. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 543 | #define pool_next_index(P,I) \ |
| 544 | ({ \ |
| 545 | pool_header_t * _pool_var (p) = pool_header (P); \ |
| 546 | uword _pool_var (rv) = (I) + 1; \ |
| 547 | \ |
| 548 | _pool_var(rv) = \ |
| 549 | (_pool_var (rv) < vec_len (P) ? \ |
| 550 | clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \ |
| 551 | : ~0); \ |
John Lo | 7f358b3 | 2018-04-28 01:19:24 -0400 | [diff] [blame] | 552 | _pool_var(rv) = \ |
| 553 | (_pool_var (rv) < vec_len (P) ? \ |
| 554 | _pool_var (rv) : ~0); \ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 555 | _pool_var(rv); \ |
| 556 | }) |
| 557 | |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame] | 558 | #define pool_foreach_index(i,v) \ |
Damjan Marion | 62c25ab | 2020-12-12 23:32:12 +0100 | [diff] [blame] | 559 | if (v) \ |
| 560 | for (i = pool_get_first_index (v); \ |
| 561 | i < vec_len (v); \ |
| 562 | i = pool_get_next_index (v, i)) \ |
| 563 | |
Neale Ranns | 87df12d | 2017-02-18 08:16:41 -0800 | [diff] [blame] | 564 | /** |
Paul Vinciguerra | ec11b13 | 2018-09-24 05:25:00 -0700 | [diff] [blame] | 565 | * @brief Remove all elements from a pool in a safe way |
Neale Ranns | 87df12d | 2017-02-18 08:16:41 -0800 | [diff] [blame] | 566 | * |
| 567 | * @param VAR each element in the pool |
| 568 | * @param POOL The pool to flush |
| 569 | * @param BODY The actions to perform on each element before it is returned to |
| 570 | * the pool. i.e. before it is 'freed' |
| 571 | */ |
| 572 | #define pool_flush(VAR, POOL, BODY) \ |
| 573 | { \ |
| 574 | uword *_pool_var(ii), *_pool_var(dv) = NULL; \ |
| 575 | \ |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame] | 576 | pool_foreach((VAR), (POOL)) \ |
| 577 | { \ |
Neale Ranns | 87df12d | 2017-02-18 08:16:41 -0800 | [diff] [blame] | 578 | vec_add1(_pool_var(dv), (VAR) - (POOL)); \ |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame] | 579 | } \ |
Neale Ranns | 87df12d | 2017-02-18 08:16:41 -0800 | [diff] [blame] | 580 | vec_foreach(_pool_var(ii), _pool_var(dv)) \ |
| 581 | { \ |
| 582 | (VAR) = pool_elt_at_index((POOL), *_pool_var(ii)); \ |
| 583 | do { BODY; } while (0); \ |
| 584 | pool_put((POOL), (VAR)); \ |
| 585 | } \ |
| 586 | vec_free(_pool_var(dv)); \ |
| 587 | } |
| 588 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 589 | #endif /* included_pool_h */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 590 | |
| 591 | /* |
| 592 | * fd.io coding-style-patch-verification: ON |
| 593 | * |
| 594 | * Local Variables: |
| 595 | * eval: (c-set-style "gnu") |
| 596 | * End: |
| 597 | */ |