blob: 2a356291051154cb1a657c2c70ac4502eec65a60 [file] [log] [blame]
Ed Warnickecb9cada2015-12-08 15:45:58 -07001/*
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 Luke8e5b0412016-07-26 13:06:10 -040037/** @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 Warnickecb9cada2015-12-08 15:45:58 -070043
44#ifndef included_pool_h
45#define included_pool_h
46
47#include <vppinfra/bitmap.h>
48#include <vppinfra/error.h>
Ed Warnickecb9cada2015-12-08 15:45:58 -070049
Ed Warnickecb9cada2015-12-08 15:45:58 -070050
Dave Barachc3799992016-08-15 11:12:27 -040051typedef struct
52{
Chris Luke8e5b0412016-07-26 13:06:10 -040053 /** Bitmap of indices of free objects. */
Dave Barachc3799992016-08-15 11:12:27 -040054 uword *free_bitmap;
Ed Warnickecb9cada2015-12-08 15:45:58 -070055
Chris Luke8e5b0412016-07-26 13:06:10 -040056 /** Vector of free indices. One element for each set bit in bitmap. */
Dave Barachc3799992016-08-15 11:12:27 -040057 u32 *free_indices;
Dave Barachb7f1faa2017-08-29 11:43:37 -040058
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 Warnickecb9cada2015-12-08 15:45:58 -070064} pool_header_t;
65
Chris Luke8e5b0412016-07-26 13:06:10 -040066/** Get pool header from user pool pointer */
Dave Barachc3799992016-08-15 11:12:27 -040067always_inline pool_header_t *
68pool_header (void *v)
69{
Damjan Mariona4a28f02022-03-17 15:46:25 +010070 return vec_header (v);
Dave Barachc3799992016-08-15 11:12:27 -040071}
Ed Warnickecb9cada2015-12-08 15:45:58 -070072
Damjan Marion299571a2022-03-19 00:07:52 +010073void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts,
74 uword align);
Dave Barachb7f1faa2017-08-29 11:43:37 -040075
76/** initialize a fixed-size, preallocated pool */
Damjan Marion299571a2022-03-19 00:07:52 +010077#define pool_init_fixed(P, E) \
78 _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0));
Dave Barachb7f1faa2017-08-29 11:43:37 -040079
Chris Luke8e5b0412016-07-26 13:06:10 -040080/** Validate a pool */
Dave Barachc3799992016-08-15 11:12:27 -040081always_inline void
82pool_validate (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -070083{
Dave Barachc3799992016-08-15 11:12:27 -040084 pool_header_t *p = pool_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -070085 uword i, n_free_bitmap;
86
Dave Barachc3799992016-08-15 11:12:27 -040087 if (!v)
Ed Warnickecb9cada2015-12-08 15:45:58 -070088 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 Luke8e5b0412016-07-26 13:06:10 -040096/** Number of active elements in a pool.
97 * @return Number of active elements in a pool
98 */
Dave Barachc3799992016-08-15 11:12:27 -040099always_inline uword
100pool_elts (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700101{
102 uword ret = vec_len (v);
103 if (v)
104 ret -= vec_len (pool_header (v)->free_indices);
105 return ret;
106}
107
Chris Luke8e5b0412016-07-26 13:06:10 -0400108/** Number of elements in pool vector.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700109
Chris Luke8e5b0412016-07-26 13:06:10 -0400110 @note You probably want to call pool_elts() instead.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700111*/
112#define pool_len(p) vec_len(p)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700113
Chris Luke8e5b0412016-07-26 13:06:10 -0400114/** Number of elements in pool vector (usable as an lvalue)
115
116 @note You probably don't want to use this macro.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700117*/
118#define _pool_len(p) _vec_len(p)
119
Chris Luke8e5b0412016-07-26 13:06:10 -0400120/** Memory usage of pool header. */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700121always_inline uword
Dave Barachc3799992016-08-15 11:12:27 -0400122pool_header_bytes (void *v)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700123{
Dave Barachc3799992016-08-15 11:12:27 -0400124 pool_header_t *p = pool_header (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700125
Dave Barachc3799992016-08-15 11:12:27 -0400126 if (!v)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700127 return 0;
128
129 return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
130}
131
Chris Luke8e5b0412016-07-26 13:06:10 -0400132/** Memory usage of pool. */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700133#define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
134
Chris Luke8e5b0412016-07-26 13:06:10 -0400135/** Local variable naming macro. */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700136#define _pool_var(v) _pool_##v
137
Florin Coras400d4592022-03-09 13:34:12 -0800138/** Number of elements that can fit into pool with current allocation */
Damjan Marion5c45d1c2022-03-17 15:32:56 +0100139#define pool_max_len(P) vec_max_len (P)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700140
Florin Coras400d4592022-03-09 13:34:12 -0800141/** Number of free elements in pool */
Damjan Marion299571a2022-03-19 00:07:52 +0100142static_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 Warnickecb9cada2015-12-08 15:45:58 -0700163
Chris Luke8e5b0412016-07-26 13:06:10 -0400164/** Allocate an object E from a pool P (general version).
Ed Warnickecb9cada2015-12-08 15:45:58 -0700165
Chris Luke8e5b0412016-07-26 13:06:10 -0400166 First search free list. If nothing is free extend vector of objects.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700167*/
Damjan Marion299571a2022-03-19 00:07:52 +0100168
169static_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 Marione4fa1d22022-04-11 18:41:49 +0200175 vec_attr_t va = { .hdr_sz = sizeof (pool_header_t),
176 .elt_sz = elt_sz,
177 .align = align };
Damjan Marion299571a2022-03-19 00:07:52 +0100178
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 Marion8bea5892022-04-04 22:40:45 +0200190 vec_set_len (ph->free_indices, n_free - 1);
Damjan Marion79934e82022-04-05 12:40:31 +0200191 clib_mem_unpoison (e, elt_sz);
Damjan Marion299571a2022-03-19 00:07:52 +0100192 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 Marione4fa1d22022-04-11 18:41:49 +0200205 p = _vec_realloc_internal (p, len + 1, &va);
Damjan Marion299571a2022-03-19 00:07:52 +0100206 e = p + len * elt_sz;
207
208 _vec_update_pointer (pp, p);
209
210done:
211 ep[0] = e;
212 if (zero)
213 clib_memset_u8 (e, 0, elt_sz);
214}
215
Damjan Marion3cfd5292022-03-18 15:48:12 +0100216#define _pool_get_aligned_internal(P, E, A, Z) \
Damjan Marion299571a2022-03-19 00:07:52 +0100217 _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z, \
218 _vec_elt_sz (P))
Dave Baracha690fdb2020-01-21 12:34:55 -0500219
Dave Barachbf3443b2018-10-18 15:37:49 -0400220/** 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 Luke8e5b0412016-07-26 13:06:10 -0400226/** Allocate an object E from a pool P (unspecified alignment). */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700227#define pool_get(P,E) pool_get_aligned(P,E,0)
228
Dave Barachbf3443b2018-10-18 15:37:49 -0400229/** 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 Marion66d4cb52022-03-17 18:59:46 +0100232always_inline int
Damjan Marion299571a2022-03-19 00:07:52 +0100233_pool_get_will_expand (void *p, uword elt_sz)
Damjan Marion66d4cb52022-03-17 18:59:46 +0100234{
235 pool_header_t *ph;
236 uword len;
Dave Barach614ac5d2017-02-06 09:28:03 -0500237
Damjan Marion66d4cb52022-03-17 18:59:46 +0100238 if (p == 0)
239 return 1;
Stanislav Zaikin09abed62021-11-04 09:32:32 +0100240
Damjan Marion66d4cb52022-03-17 18:59:46 +0100241 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 Marion299571a2022-03-19 00:07:52 +0100252 return _vec_resize_will_expand (p, 1, elt_sz);
Damjan Marion66d4cb52022-03-17 18:59:46 +0100253}
254
255#define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0]))
256
257always_inline int
Damjan Marion299571a2022-03-19 00:07:52 +0100258_pool_put_will_expand (void *p, uword index, uword elt_sz)
Damjan Marion66d4cb52022-03-17 18:59:46 +0100259{
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 Barach614ac5d2017-02-06 09:28:03 -0500272
Chris Luke8e5b0412016-07-26 13:06:10 -0400273/** Use free bitmap to query whether given element is free. */
Damjan Marion299571a2022-03-19 00:07:52 +0100274static_always_inline int
275pool_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 Barachc3799992016-08-15 11:12:27 -0400280
Damjan Marion299571a2022-03-19 00:07:52 +0100281#define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700282
Chris Luke8e5b0412016-07-26 13:06:10 -0400283/** Free an object E in pool P. */
Damjan Marion299571a2022-03-19 00:07:52 +0100284static_always_inline void
285_pool_put_index (void *p, uword index, uword elt_sz)
286{
287 pool_header_t *ph = pool_header (p);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700288
Damjan Marion299571a2022-03-19 00:07:52 +0100289 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 Marion8bea5892022-04-04 22:40:45 +0200299 vec_inc_len (ph->free_indices, 1);
Damjan Marion299571a2022-03-19 00:07:52 +0100300 }
301 else
302 vec_add1 (ph->free_indices, index);
303
Damjan Marion79934e82022-04-05 12:40:31 +0200304 clib_mem_poison (p + index * elt_sz, elt_sz);
Damjan Marion299571a2022-03-19 00:07:52 +0100305}
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 Warnickecb9cada2015-12-08 15:45:58 -0700309
Chris Luke8e5b0412016-07-26 13:06:10 -0400310/** Allocate N more free elements to pool (general version). */
Damjan Marion299571a2022-03-19 00:07:52 +0100311
312static_always_inline void
Damjan Marion24738582022-03-31 15:12:20 +0200313_pool_alloc (void **pp, uword n_elts, uword align, void *heap, uword elt_sz)
Damjan Marion299571a2022-03-19 00:07:52 +0100314{
315 pool_header_t *ph = pool_header (pp[0]);
316 uword len = vec_len (pp[0]);
Damjan Marione4fa1d22022-04-11 18:41:49 +0200317 const vec_attr_t va = { .hdr_sz = sizeof (pool_header_t),
318 .elt_sz = elt_sz,
319 .align = align,
320 .heap = heap };
Damjan Marion299571a2022-03-19 00:07:52 +0100321
322 if (ph && ph->max_elts)
323 {
324 clib_warning ("Can't expand fixed-size pool");
325 os_out_of_memory ();
326 }
327
Damjan Marione4fa1d22022-04-11 18:41:49 +0200328 pp[0] = _vec_resize_internal (pp[0], len + n_elts, &va);
Damjan Marion8bea5892022-04-04 22:40:45 +0200329 _vec_set_len (pp[0], len, elt_sz);
Damjan Marion79934e82022-04-05 12:40:31 +0200330 clib_mem_poison (pp[0] + len * elt_sz, n_elts * elt_sz);
Damjan Marion299571a2022-03-19 00:07:52 +0100331
332 ph = pool_header (pp[0]);
333 vec_resize (ph->free_indices, n_elts);
Damjan Marion8bea5892022-04-04 22:40:45 +0200334 vec_dec_len (ph->free_indices, n_elts);
Damjan Marion299571a2022-03-19 00:07:52 +0100335 clib_bitmap_vec_validate (ph->free_bitmap, len + n_elts - 1);
336}
337
Damjan Marion24738582022-03-31 15:12:20 +0200338#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 Warnickecb9cada2015-12-08 15:45:58 -0700340
Damjan Marion24738582022-03-31 15:12:20 +0200341#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 Warnickecb9cada2015-12-08 15:45:58 -0700344
Damjan Marion299571a2022-03-19 00:07:52 +0100345static_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 Marione4fa1d22022-04-11 18:41:49 +0200350 const vec_attr_t va = { .hdr_sz = sizeof (pool_header_t),
351 .elt_sz = elt_sz,
352 .align = align };
Damjan Marion299571a2022-03-19 00:07:52 +0100353 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 Marione4fa1d22022-04-11 18:41:49 +0200361 n = _vec_alloc_internal (len, &va);
Damjan Marion299571a2022-03-19 00:07:52 +0100362 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 Marion79934e82022-04-05 12:40:31 +0200369 clib_mem_unpoison (p + elt_sz * fi[0], elt_sz);
Damjan Marion299571a2022-03-19 00:07:52 +0100370
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 Marion79934e82022-04-05 12:40:31 +0200379 clib_mem_poison (p + offset, elt_sz);
380 clib_mem_poison (n + offset, elt_sz);
Damjan Marion299571a2022-03-19 00:07:52 +0100381 }
382 }
383
384 return n;
385}
386
Florin Coras8be6c402018-11-27 17:11:37 -0800387/**
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 Marion299571a2022-03-19 00:07:52 +0100394
Benoît Ganne563ec992021-11-19 13:39:10 +0100395#define pool_dup_aligned(P, A) \
Damjan Marion299571a2022-03-19 00:07:52 +0100396 _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P))
Florin Coras8be6c402018-11-27 17:11:37 -0800397
398/**
399 * Return copy of pool without alignment
400 *
401 * @param P pool to copy
402 * @return copy of pool
403 */
Florin Coras47c40e22018-11-26 17:01:36 -0800404#define pool_dup(P) pool_dup_aligned(P,0)
Florin Coras8be6c402018-11-27 17:11:37 -0800405
Chris Luke8e5b0412016-07-26 13:06:10 -0400406/** Low-level free pool operator (do not call directly). */
Damjan Marion299571a2022-03-19 00:07:52 +0100407always_inline void
408_pool_free (void **v)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700409{
Damjan Marion299571a2022-03-19 00:07:52 +0100410 pool_header_t *p = pool_header (v[0]);
411 if (!p)
412 return;
413
Ed Warnickecb9cada2015-12-08 15:45:58 -0700414 clib_bitmap_free (p->free_bitmap);
Dave Barachb7f1faa2017-08-29 11:43:37 -0400415
Damjan Marion86bbdf92022-03-18 12:28:35 +0100416 vec_free (p->free_indices);
Damjan Marion299571a2022-03-19 00:07:52 +0100417 _vec_free (v);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700418}
Damjan Marion299571a2022-03-19 00:07:52 +0100419#define pool_free(p) _pool_free ((void **) &(p))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700420
Damjan Marion62c25ab2020-12-12 23:32:12 +0100421static_always_inline uword
422pool_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
428static_always_inline uword
429pool_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 Luke8e5b0412016-07-26 13:06:10 -0400435/** Optimized iteration through pool.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700436
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 Barachc3799992016-08-15 11:12:27 -0400442 Optimized version which assumes that BODY is smart enough to
Ed Warnickecb9cada2015-12-08 15:45:58 -0700443 process multiple (LOW,HI) chunks. See also pool_foreach().
444 */
445#define pool_foreach_region(LO,HI,POOL,BODY) \
446do { \
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 Luke8e5b0412016-07-26 13:06:10 -0400484/** Iterate through pool.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700485
Chris Luke8e5b0412016-07-26 13:06:10 -0400486 @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 Warnickecb9cada2015-12-08 15:45:58 -0700491
Chris Luke8e5b0412016-07-26 13:06:10 -0400492 This macro will call @c BODY with each active pool element.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700493
494 It is a bad idea to allocate or free pool element from within
Chris Luke8e5b0412016-07-26 13:06:10 -0400495 @c pool_foreach. Build a vector of indices and dispose of them later.
Neale Ranns87df12d2017-02-18 08:16:41 -0800496 Or call pool_flush.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700497
Chris Luke8e5b0412016-07-26 13:06:10 -0400498
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 Warnickecb9cada2015-12-08 15:45:58 -0700518 */
Damjan Marion62c25ab2020-12-12 23:32:12 +0100519
Damjan Marionb2c31b62020-12-13 21:47:40 +0100520#define pool_foreach(VAR,POOL) \
Damjan Marion62c25ab2020-12-12 23:32:12 +0100521 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 Luke8e5b0412016-07-26 13:06:10 -0400526/** Returns pointer to element at given index.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700527
Chris Luke8e5b0412016-07-26 13:06:10 -0400528 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 Barachc3799992016-08-15 11:12:27 -0400533 use of @c pool_elt_at_index is strongly suggested.
Ed Warnickecb9cada2015-12-08 15:45:58 -0700534 */
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 Luke8e5b0412016-07-26 13:06:10 -0400542/** Return next occupied pool index after @c i, useful for safe iteration. */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700543#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 Lo7f358b32018-04-28 01:19:24 -0400552 _pool_var(rv) = \
553 (_pool_var (rv) < vec_len (P) ? \
554 _pool_var (rv) : ~0); \
Ed Warnickecb9cada2015-12-08 15:45:58 -0700555 _pool_var(rv); \
556})
557
Damjan Marionb2c31b62020-12-13 21:47:40 +0100558#define pool_foreach_index(i,v) \
Damjan Marion62c25ab2020-12-12 23:32:12 +0100559 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 Ranns87df12d2017-02-18 08:16:41 -0800564/**
Paul Vinciguerraec11b132018-09-24 05:25:00 -0700565 * @brief Remove all elements from a pool in a safe way
Neale Ranns87df12d2017-02-18 08:16:41 -0800566 *
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 Marionb2c31b62020-12-13 21:47:40 +0100576 pool_foreach((VAR), (POOL)) \
577 { \
Neale Ranns87df12d2017-02-18 08:16:41 -0800578 vec_add1(_pool_var(dv), (VAR) - (POOL)); \
Damjan Marionb2c31b62020-12-13 21:47:40 +0100579 } \
Neale Ranns87df12d2017-02-18 08:16:41 -0800580 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 Warnickecb9cada2015-12-08 15:45:58 -0700589#endif /* included_pool_h */
Dave Barachc3799992016-08-15 11:12:27 -0400590
591/*
592 * fd.io coding-style-patch-verification: ON
593 *
594 * Local Variables:
595 * eval: (c-set-style "gnu")
596 * End:
597 */