Line data Source code
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 : */
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 : */
43 :
44 : #ifndef included_pool_h
45 : #define included_pool_h
46 :
47 : #include <vppinfra/bitmap.h>
48 : #include <vppinfra/error.h>
49 :
50 :
51 : typedef struct
52 : {
53 : /** Bitmap of indices of free objects. */
54 : uword *free_bitmap;
55 :
56 : /** Vector of free indices. One element for each set bit in bitmap. */
57 : u32 *free_indices;
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 :
64 : } pool_header_t;
65 :
66 : /** Get pool header from user pool pointer */
67 : always_inline pool_header_t *
68 2683406093 : pool_header (void *v)
69 : {
70 2683406093 : return vec_header (v);
71 : }
72 :
73 : void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts,
74 : uword align);
75 :
76 : /** initialize a fixed-size, preallocated pool */
77 : #define pool_init_fixed(P, E) \
78 : _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0));
79 :
80 : /** Validate a pool */
81 : always_inline void
82 : pool_validate (void *v)
83 : {
84 : pool_header_t *p = pool_header (v);
85 : uword i, n_free_bitmap;
86 :
87 : if (!v)
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 :
96 : /** Number of active elements in a pool.
97 : * @return Number of active elements in a pool
98 : */
99 : always_inline uword
100 1691473 : pool_elts (void *v)
101 : {
102 1691473 : uword ret = vec_len (v);
103 1691470 : if (v)
104 831389 : ret -= vec_len (pool_header (v)->free_indices);
105 1691472 : return ret;
106 : }
107 :
108 : /** Number of elements in pool vector.
109 :
110 : @note You probably want to call pool_elts() instead.
111 : */
112 : #define pool_len(p) vec_len(p)
113 :
114 : /** Number of elements in pool vector (usable as an lvalue)
115 :
116 : @note You probably don't want to use this macro.
117 : */
118 : #define _pool_len(p) _vec_len(p)
119 :
120 : /** Memory usage of pool header. */
121 : always_inline uword
122 : pool_header_bytes (void *v)
123 : {
124 : pool_header_t *p = pool_header (v);
125 :
126 : if (!v)
127 : return 0;
128 :
129 : return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
130 : }
131 :
132 : /** Memory usage of pool. */
133 : #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
134 :
135 : /** Local variable naming macro. */
136 : #define _pool_var(v) _pool_##v
137 :
138 : /** Number of elements that can fit into pool with current allocation */
139 : #define pool_max_len(P) vec_max_len (P)
140 :
141 : /** Number of free elements in pool */
142 : static_always_inline uword
143 8359 : _pool_free_elts (void *p, uword elt_sz)
144 : {
145 : pool_header_t *ph;
146 : uword n_free;
147 :
148 8359 : if (p == 0)
149 0 : return 0;
150 :
151 8359 : ph = pool_header (p);
152 :
153 8359 : n_free = vec_len (ph->free_indices);
154 :
155 : /* Fixed-size pools have max_elts set non-zero */
156 8359 : if (ph->max_elts == 0)
157 1435 : n_free += _vec_max_len (p, elt_sz) - vec_len (p);
158 :
159 8359 : return n_free;
160 : }
161 :
162 : #define pool_free_elts(P) _pool_free_elts ((void *) (P), _vec_elt_sz (P))
163 :
164 : /** Allocate an object E from a pool P (general version).
165 :
166 : First search free list. If nothing is free extend vector of objects.
167 : */
168 :
169 : static_always_inline void
170 11244824 : _pool_get (void **pp, void **ep, uword align, int zero, uword elt_sz)
171 : {
172 11244824 : uword len = 0;
173 11244824 : void *p = pp[0];
174 : void *e;
175 11244824 : vec_attr_t va = { .hdr_sz = sizeof (pool_header_t),
176 : .elt_sz = elt_sz,
177 : .align = align };
178 :
179 11244824 : if (p)
180 : {
181 11179550 : pool_header_t *ph = pool_header (p);
182 11179519 : uword n_free = vec_len (ph->free_indices);
183 :
184 11179521 : if (n_free)
185 : {
186 3820278 : uword index = ph->free_indices[n_free - 1];
187 3820278 : e = p + index * elt_sz;
188 3820278 : ph->free_bitmap =
189 3820278 : clib_bitmap_andnoti_notrim (ph->free_bitmap, index);
190 3820278 : vec_set_len (ph->free_indices, n_free - 1);
191 3820278 : clib_mem_unpoison (e, elt_sz);
192 3820278 : goto done;
193 : }
194 :
195 7359243 : if (ph->max_elts)
196 : {
197 0 : clib_warning ("can't expand fixed-size pool");
198 0 : os_out_of_memory ();
199 : }
200 : }
201 :
202 7424511 : len = vec_len (p);
203 :
204 : /* Nothing on free list, make a new element and return it. */
205 7424484 : p = _vec_realloc_internal (p, len + 1, &va);
206 7424253 : e = p + len * elt_sz;
207 :
208 7424253 : _vec_update_pointer (pp, p);
209 :
210 11244519 : done:
211 11244519 : ep[0] = e;
212 11244519 : if (zero)
213 95014 : clib_memset_u8 (e, 0, elt_sz);
214 11244519 : }
215 :
216 : #define _pool_get_aligned_internal(P, E, A, Z) \
217 : _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z, \
218 : _vec_elt_sz (P))
219 :
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 :
226 : /** Allocate an object E from a pool P (unspecified alignment). */
227 : #define pool_get(P,E) pool_get_aligned(P,E,0)
228 :
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 :
232 : always_inline int
233 246770 : _pool_get_will_expand (void *p, uword elt_sz)
234 : {
235 : pool_header_t *ph;
236 : uword len;
237 :
238 246770 : if (p == 0)
239 3134 : return 1;
240 :
241 243636 : ph = pool_header (p);
242 :
243 243636 : if (ph->max_elts)
244 0 : len = ph->max_elts;
245 : else
246 243636 : len = vec_len (ph->free_indices);
247 :
248 : /* Free elements, certainly won't expand */
249 243636 : if (len > 0)
250 136823 : return 0;
251 :
252 106813 : return _vec_resize_will_expand (p, 1, elt_sz);
253 : }
254 :
255 : #define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0]))
256 :
257 : always_inline int
258 : _pool_put_will_expand (void *p, uword index, uword elt_sz)
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])
272 :
273 : /** Use free bitmap to query whether given element is free. */
274 : static_always_inline int
275 2227331209 : pool_is_free_index (void *p, uword index)
276 : {
277 2227331209 : pool_header_t *ph = pool_header (p);
278 2227289542 : return index < vec_len (p) ? clib_bitmap_get (ph->free_bitmap, index) : 1;
279 : }
280 :
281 : #define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P))
282 :
283 : /** Free an object E in pool P. */
284 : static_always_inline void
285 4151189 : _pool_put_index (void *p, uword index, uword elt_sz)
286 : {
287 4151189 : pool_header_t *ph = pool_header (p);
288 :
289 4151189 : ASSERT (index < ph->max_elts ? ph->max_elts : vec_len (p));
290 4151189 : ASSERT (!pool_is_free_index (p, index));
291 :
292 : /* Add element to free bitmap and to free list. */
293 4151189 : ph->free_bitmap = clib_bitmap_ori_notrim (ph->free_bitmap, index);
294 :
295 : /* Preallocated pool? */
296 4151189 : if (ph->max_elts)
297 : {
298 7134 : u32 len = _vec_len (ph->free_indices);
299 7134 : vec_set_len (ph->free_indices, len + 1);
300 7134 : ph->free_indices[len] = index;
301 : }
302 : else
303 4144055 : vec_add1 (ph->free_indices, index);
304 :
305 4151189 : clib_mem_poison (p + index * elt_sz, elt_sz);
306 4151189 : }
307 :
308 : #define pool_put_index(P, I) _pool_put_index ((void *) (P), I, _vec_elt_sz (P))
309 : #define pool_put(P, E) pool_put_index (P, (E) - (P))
310 :
311 : /** Allocate N more free elements to pool (general version). */
312 :
313 : static_always_inline void
314 5715 : _pool_alloc (void **pp, uword n_elts, uword align, void *heap, uword elt_sz)
315 : {
316 5715 : pool_header_t *ph = pool_header (pp[0]);
317 5715 : uword len = vec_len (pp[0]);
318 5715 : const vec_attr_t va = { .hdr_sz = sizeof (pool_header_t),
319 : .elt_sz = elt_sz,
320 : .align = align,
321 : .heap = heap };
322 :
323 5715 : if (ph && ph->max_elts)
324 : {
325 0 : clib_warning ("Can't expand fixed-size pool");
326 0 : os_out_of_memory ();
327 : }
328 :
329 5715 : pp[0] = _vec_resize_internal (pp[0], len + n_elts, &va);
330 5715 : _vec_set_len (pp[0], len, elt_sz);
331 5715 : clib_mem_poison (pp[0] + len * elt_sz, n_elts * elt_sz);
332 :
333 5715 : ph = pool_header (pp[0]);
334 5715 : vec_resize (ph->free_indices, n_elts);
335 5715 : vec_dec_len (ph->free_indices, n_elts);
336 5715 : clib_bitmap_validate (ph->free_bitmap, (len + n_elts) ?: 1);
337 5715 : }
338 :
339 : #define pool_alloc_aligned_heap(P, N, A, H) \
340 : _pool_alloc ((void **) &(P), N, _vec_align (P, A), H, _vec_elt_sz (P))
341 :
342 : #define pool_alloc_heap(P, N, H) pool_alloc_aligned_heap (P, N, 0, H)
343 : #define pool_alloc_aligned(P, N, A) pool_alloc_aligned_heap (P, N, A, 0)
344 : #define pool_alloc(P, N) pool_alloc_aligned_heap (P, N, 0, 0)
345 :
346 : static_always_inline void *
347 437 : _pool_dup (void *p, uword align, uword elt_sz)
348 : {
349 437 : pool_header_t *nph, *ph = pool_header (p);
350 437 : uword len = vec_len (p);
351 437 : const vec_attr_t va = { .hdr_sz = sizeof (pool_header_t),
352 : .elt_sz = elt_sz,
353 : .align = align };
354 : void *n;
355 :
356 437 : if (ph && ph->max_elts)
357 : {
358 0 : clib_warning ("Can't expand fixed-size pool");
359 0 : os_out_of_memory ();
360 : }
361 :
362 437 : n = _vec_alloc_internal (len, &va);
363 437 : nph = pool_header (n);
364 437 : clib_memset_u8 (nph, 0, sizeof (vec_header_t));
365 :
366 437 : if (len)
367 : {
368 : u32 *fi;
369 240 : vec_foreach (fi, ph->free_indices)
370 18 : clib_mem_unpoison (p + elt_sz * fi[0], elt_sz);
371 :
372 222 : clib_memcpy_fast (n, p, len * elt_sz);
373 :
374 222 : nph->free_bitmap = clib_bitmap_dup (ph->free_bitmap);
375 222 : nph->free_indices = vec_dup (ph->free_indices);
376 :
377 240 : vec_foreach (fi, ph->free_indices)
378 : {
379 18 : uword offset = elt_sz * fi[0];
380 18 : clib_mem_poison (p + offset, elt_sz);
381 18 : clib_mem_poison (n + offset, elt_sz);
382 : }
383 : }
384 :
385 437 : return n;
386 : }
387 :
388 : /**
389 : * Return copy of pool with alignment
390 : *
391 : * @param P pool to copy
392 : * @param A alignment (may be zero)
393 : * @return copy of pool
394 : */
395 :
396 : #define pool_dup_aligned(P, A) \
397 : _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P))
398 :
399 : /**
400 : * Return copy of pool without alignment
401 : *
402 : * @param P pool to copy
403 : * @return copy of pool
404 : */
405 : #define pool_dup(P) pool_dup_aligned(P,0)
406 :
407 : /** Low-level free pool operator (do not call directly). */
408 : always_inline void
409 28835 : _pool_free (void **v)
410 : {
411 28835 : pool_header_t *p = pool_header (v[0]);
412 28835 : if (!p)
413 9274 : return;
414 :
415 19561 : clib_bitmap_free (p->free_bitmap);
416 :
417 19561 : vec_free (p->free_indices);
418 19561 : _vec_free (v);
419 : }
420 : #define pool_free(p) _pool_free ((void **) &(p))
421 :
422 : static_always_inline uword
423 158447934 : pool_get_first_index (void *pool)
424 : {
425 158447934 : pool_header_t *h = pool_header (pool);
426 158447935 : return clib_bitmap_first_clear (h->free_bitmap);
427 : }
428 :
429 : static_always_inline uword
430 280371232 : pool_get_next_index (void *pool, uword last)
431 : {
432 280371232 : pool_header_t *h = pool_header (pool);
433 280371232 : return clib_bitmap_next_clear (h->free_bitmap, last + 1);
434 : }
435 :
436 : /** Optimized iteration through pool.
437 :
438 : @param LO pointer to first element in chunk
439 : @param HI pointer to last element in chunk
440 : @param POOL pool to iterate across
441 : @param BODY operation to perform
442 :
443 : Optimized version which assumes that BODY is smart enough to
444 : process multiple (LOW,HI) chunks. See also pool_foreach().
445 : */
446 : #define pool_foreach_region(LO,HI,POOL,BODY) \
447 : do { \
448 : uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \
449 : uword _pool_var (bl), * _pool_var (b); \
450 : pool_header_t * _pool_var (p); \
451 : \
452 : _pool_var (p) = pool_header (POOL); \
453 : _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0; \
454 : _pool_var (bl) = vec_len (_pool_var (b)); \
455 : _pool_var (len) = vec_len (POOL); \
456 : _pool_var (lo) = 0; \
457 : \
458 : for (_pool_var (i) = 0; \
459 : _pool_var (i) <= _pool_var (bl); \
460 : _pool_var (i)++) \
461 : { \
462 : uword _pool_var (m), _pool_var (f); \
463 : _pool_var (m) = (_pool_var (i) < _pool_var (bl) \
464 : ? _pool_var (b) [_pool_var (i)] \
465 : : 1); \
466 : while (_pool_var (m) != 0) \
467 : { \
468 : _pool_var (f) = first_set (_pool_var (m)); \
469 : _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0]) \
470 : + min_log2 (_pool_var (f))); \
471 : _pool_var (hi) = (_pool_var (i) < _pool_var (bl) \
472 : ? _pool_var (hi) : _pool_var (len)); \
473 : _pool_var (m) ^= _pool_var (f); \
474 : if (_pool_var (hi) > _pool_var (lo)) \
475 : { \
476 : (LO) = _pool_var (lo); \
477 : (HI) = _pool_var (hi); \
478 : do { BODY; } while (0); \
479 : } \
480 : _pool_var (lo) = _pool_var (hi) + 1; \
481 : } \
482 : } \
483 : } while (0)
484 :
485 : /** Iterate through pool.
486 :
487 : @param VAR A variable of same type as pool vector to be used as an
488 : iterator.
489 : @param POOL The pool to iterate across.
490 : @param BODY The operation to perform, typically a code block. See
491 : the example below.
492 :
493 : This macro will call @c BODY with each active pool element.
494 :
495 : It is a bad idea to allocate or free pool element from within
496 : @c pool_foreach. Build a vector of indices and dispose of them later.
497 : Or call pool_flush.
498 :
499 :
500 : @par Example
501 : @code{.c}
502 : proc_t *procs; // a pool of processes.
503 : proc_t *proc; // pointer to one process; used as the iterator.
504 :
505 : pool_foreach (proc, procs, ({
506 : if (proc->state != PROC_STATE_RUNNING)
507 : continue;
508 :
509 : // check a running proc in some way
510 : ...
511 : }));
512 : @endcode
513 :
514 : @warning Because @c pool_foreach is a macro, syntax errors can be
515 : difficult to find inside @c BODY, let alone actual code bugs. One
516 : can temporarily split a complex @c pool_foreach into a trivial
517 : @c pool_foreach which builds a vector of active indices, and a
518 : vec_foreach() (or plain for-loop) to walk the active index vector.
519 : */
520 :
521 : #define pool_foreach(VAR,POOL) \
522 : if (POOL) \
523 : for (VAR = POOL + pool_get_first_index (POOL); \
524 : VAR < vec_end (POOL); \
525 : VAR = POOL + pool_get_next_index (POOL, VAR - POOL))
526 :
527 : /** Returns pointer to element at given index.
528 :
529 : ASSERTs that the supplied index is valid.
530 : Even though one can write correct code of the form
531 : @code
532 : p = pool_base + index;
533 : @endcode
534 : use of @c pool_elt_at_index is strongly suggested.
535 : */
536 : #define pool_elt_at_index(p,i) \
537 : ({ \
538 : typeof (p) _e = (p) + (i); \
539 : ASSERT (! pool_is_free (p, _e)); \
540 : _e; \
541 : })
542 :
543 : /** Return next occupied pool index after @c i, useful for safe iteration. */
544 : #define pool_next_index(P,I) \
545 : ({ \
546 : pool_header_t * _pool_var (p) = pool_header (P); \
547 : uword _pool_var (rv) = (I) + 1; \
548 : \
549 : _pool_var(rv) = \
550 : (_pool_var (rv) < vec_len (P) ? \
551 : clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
552 : : ~0); \
553 : _pool_var(rv) = \
554 : (_pool_var (rv) < vec_len (P) ? \
555 : _pool_var (rv) : ~0); \
556 : _pool_var(rv); \
557 : })
558 :
559 : #define pool_foreach_index(i, v) \
560 : if (v) \
561 : for (i = pool_get_first_index (v); i < vec_len (v); \
562 : i = pool_get_next_index (v, i))
563 :
564 : /* Iterate pool by index from s to e */
565 : #define pool_foreach_stepping_index(i, s, e, v) \
566 : for ((i) = \
567 : (pool_is_free_index ((v), (s)) ? pool_get_next_index ((v), (s)) : \
568 : (s)); \
569 : (i) < (e); (i) = pool_get_next_index ((v), (i)))
570 :
571 : /* works only for pool of pointers, e is declared inside macro */
572 : #define pool_foreach_pointer(e, p) \
573 : if (p) \
574 : for (typeof ((p)[0]) *_t = (p) + pool_get_first_index (p), (e) = *_t; \
575 : _t < vec_end (p); \
576 : _t = (p) + pool_get_next_index (p, _t - (p)), (e) = *_t)
577 :
578 : /**
579 : * @brief Remove all elements from a pool in a safe way
580 : *
581 : * @param VAR each element in the pool
582 : * @param POOL The pool to flush
583 : * @param BODY The actions to perform on each element before it is returned to
584 : * the pool. i.e. before it is 'freed'
585 : */
586 : #define pool_flush(VAR, POOL, BODY) \
587 : { \
588 : uword *_pool_var(ii), *_pool_var(dv) = NULL; \
589 : \
590 : pool_foreach((VAR), (POOL)) \
591 : { \
592 : vec_add1(_pool_var(dv), (VAR) - (POOL)); \
593 : } \
594 : vec_foreach(_pool_var(ii), _pool_var(dv)) \
595 : { \
596 : (VAR) = pool_elt_at_index((POOL), *_pool_var(ii)); \
597 : do { BODY; } while (0); \
598 : pool_put((POOL), (VAR)); \
599 : } \
600 : vec_free(_pool_var(dv)); \
601 : }
602 :
603 : #endif /* included_pool_h */
604 :
605 : /*
606 : * fd.io coding-style-patch-verification: ON
607 : *
608 : * Local Variables:
609 : * eval: (c-set-style "gnu")
610 : * End:
611 : */
|
