FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
pool.h
Go to the documentation of this file.
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 #include <vppinfra/mheap.h>
50 
51 
52 typedef struct
53 {
54  /** Bitmap of indices of free objects. */
56 
57  /** Vector of free indices. One element for each set bit in bitmap. */
59 
60  /* The following fields are set for fixed-size, preallocated pools */
61 
62  /** Maximum size of the pool, in elements */
64 
65  /** mmap segment info: base + length */
68 
70 
71 /** Align pool header so that pointers are naturally aligned. */
72 #define pool_aligned_header_bytes \
73  vec_aligned_header_bytes (sizeof (pool_header_t), sizeof (void *))
74 
75 /** Get pool header from user pool pointer */
77 pool_header (void *v)
78 {
79  return vec_aligned_header (v, sizeof (pool_header_t), sizeof (void *));
80 }
81 
82 extern void _pool_init_fixed (void **, u32, u32);
83 extern void fpool_free (void *);
84 
85 /** initialize a fixed-size, preallocated pool */
86 #define pool_init_fixed(pool,max_elts) \
87 { \
88  _pool_init_fixed((void **)&(pool),sizeof(pool[0]),max_elts); \
89 }
90 
91 /** Validate a pool */
92 always_inline void
93 pool_validate (void *v)
94 {
95  pool_header_t *p = pool_header (v);
96  uword i, n_free_bitmap;
97 
98  if (!v)
99  return;
100 
101  n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
102  ASSERT (n_free_bitmap == vec_len (p->free_indices));
103  for (i = 0; i < vec_len (p->free_indices); i++)
104  ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
105 }
106 
107 always_inline void
109 {
110  pool_header_t *p = pool_header (v);
111 
112  if (v)
113  vec_validate (p->free_bitmap, index / BITS (uword));
114 }
115 
116 #define pool_validate_index(v,i) \
117 do { \
118  uword __pool_validate_index = (i); \
119  vec_validate_ha ((v), __pool_validate_index, \
120  pool_aligned_header_bytes, /* align */ 0); \
121  pool_header_validate_index ((v), __pool_validate_index); \
122 } while (0)
123 
124 /** Number of active elements in a pool.
125  * @return Number of active elements in a pool
126  */
128 pool_elts (void *v)
129 {
130  uword ret = vec_len (v);
131  if (v)
132  ret -= vec_len (pool_header (v)->free_indices);
133  return ret;
134 }
135 
136 /** Number of elements in pool vector.
137 
138  @note You probably want to call pool_elts() instead.
139 */
140 #define pool_len(p) vec_len(p)
141 
142 /** Number of elements in pool vector (usable as an lvalue)
143 
144  @note You probably don't want to use this macro.
145 */
146 #define _pool_len(p) _vec_len(p)
147 
148 /** Memory usage of pool header. */
151 {
152  pool_header_t *p = pool_header (v);
153 
154  if (!v)
155  return 0;
156 
157  return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
158 }
159 
160 /** Memory usage of pool. */
161 #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
162 
163 /** Local variable naming macro. */
164 #define _pool_var(v) _pool_##v
165 
166 /** Queries whether pool has at least N_FREE free elements. */
168 pool_free_elts (void *v)
169 {
170  pool_header_t *p = pool_header (v);
171  uword n_free = 0;
172 
173  if (v)
174  {
175  n_free += vec_len (p->free_indices);
176 
177  /* Space left at end of vector? */
178  n_free += vec_capacity (v, sizeof (p[0])) - vec_len (v);
179  }
180 
181  return n_free;
182 }
183 
184 /** Allocate an object E from a pool P (general version).
185 
186  First search free list. If nothing is free extend vector of objects.
187 */
188 #define _pool_get_aligned_internal_numa(P,E,A,Z,N) \
189 do { \
190  pool_header_t * _pool_var (p) = pool_header (P); \
191  uword _pool_var (l); \
192  \
193  STATIC_ASSERT(A==0 || ((A % sizeof(P[0]))==0) \
194  || ((sizeof(P[0]) % A) == 0), \
195  "Pool aligned alloc of incorrectly sized object"); \
196  _pool_var (l) = 0; \
197  if (P) \
198  _pool_var (l) = vec_len (_pool_var (p)->free_indices); \
199  \
200  if (_pool_var (l) > 0) \
201  { \
202  /* Return free element from free list. */ \
203  uword _pool_var (i) = \
204  _pool_var (p)->free_indices[_pool_var (l) - 1]; \
205  (E) = (P) + _pool_var (i); \
206  _pool_var (p)->free_bitmap = \
207  clib_bitmap_andnoti_notrim (_pool_var (p)->free_bitmap, \
208  _pool_var (i)); \
209  _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1; \
210  CLIB_MEM_UNPOISON((E), sizeof((E)[0])); \
211  } \
212  else \
213  { \
214  /* fixed-size, preallocated pools cannot expand */ \
215  if ((P) && _pool_var(p)->max_elts) \
216  { \
217  clib_warning ("can't expand fixed-size pool"); \
218  os_out_of_memory(); \
219  } \
220  /* Nothing on free list, make a new element and return it. */ \
221  P = _vec_resize_numa (P, \
222  /* length_increment */ 1, \
223  /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
224  pool_aligned_header_bytes, \
225  /* align */ (A), \
226  /* numa */ (N)); \
227  E = vec_end (P) - 1; \
228  } \
229  if (Z) \
230  memset(E, 0, sizeof(*E)); \
231 } while (0)
232 
233 #define pool_get_aligned_zero_numa(P,E,A,Z,S) \
234  _pool_get_aligned_internal_numa(P,E,A,Z,S)
235 
236 #define pool_get_aligned_numa(P,E,A,S) \
237  _pool_get_aligned_internal_numa(P,E,A,0/*zero*/,S)
238 
239 #define pool_get_numa(P,E,S) \
240  _pool_get_aligned_internal_numa(P,E,0/*align*/,0/*zero*/,S)
241 
242 #define _pool_get_aligned_internal(P,E,A,Z) \
243  _pool_get_aligned_internal_numa(P,E,A,Z,VEC_NUMA_UNSPECIFIED)
244 
245 /** Allocate an object E from a pool P with alignment A */
246 #define pool_get_aligned(P,E,A) _pool_get_aligned_internal(P,E,A,0)
247 
248 /** Allocate an object E from a pool P with alignment A and zero it */
249 #define pool_get_aligned_zero(P,E,A) _pool_get_aligned_internal(P,E,A,1)
250 
251 /** Allocate an object E from a pool P (unspecified alignment). */
252 #define pool_get(P,E) pool_get_aligned(P,E,0)
253 
254 /** Allocate an object E from a pool P and zero it */
255 #define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0)
256 
257 /** See if pool_get will expand the pool or not */
258 #define pool_get_aligned_will_expand(P,YESNO,A) \
259 do { \
260  pool_header_t * _pool_var (p) = pool_header (P); \
261  uword _pool_var (l); \
262  \
263  _pool_var (l) = 0; \
264  if (P) \
265  { \
266  if (_pool_var (p)->max_elts) \
267  _pool_var (l) = _pool_var (p)->max_elts; \
268  else \
269  _pool_var (l) = vec_len (_pool_var (p)->free_indices); \
270  } \
271  \
272  /* Free elements, certainly won't expand */ \
273  if (_pool_var (l) > 0) \
274  YESNO=0; \
275  else \
276  { \
277  /* Nothing on free list, make a new element and return it. */ \
278  YESNO = _vec_resize_will_expand \
279  (P, \
280  /* length_increment */ 1, \
281  /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
282  pool_aligned_header_bytes, \
283  /* align */ (A)); \
284  } \
285 } while (0)
286 
287 /** Tell the caller if pool get will expand the pool */
288 #define pool_get_will_expand(P,YESNO) pool_get_aligned_will_expand(P,YESNO,0)
289 
290 /** Use free bitmap to query whether given element is free. */
291 #define pool_is_free(P,E) \
292 ({ \
293  pool_header_t * _pool_var (p) = pool_header (P); \
294  uword _pool_var (i) = (E) - (P); \
295  (_pool_var (i) < vec_len (P)) ? clib_bitmap_get (_pool_var (p)->free_bitmap, _pool_i) : 1; \
296 })
297 
298 /** Use free bitmap to query whether given index is free */
299 #define pool_is_free_index(P,I) pool_is_free((P),(P)+(I))
300 
301 /** Free an object E in pool P. */
302 #define pool_put(P,E) \
303 do { \
304  typeof (P) _pool_var(p__) = (P); \
305  typeof (E) _pool_var(e__) = (E); \
306  pool_header_t * _pool_var (p) = pool_header (_pool_var(p__)); \
307  uword _pool_var (l) = _pool_var(e__) - _pool_var(p__); \
308  ASSERT (vec_is_member (_pool_var(p__), _pool_var(e__))); \
309  ASSERT (! pool_is_free (_pool_var(p__), _pool_var(e__))); \
310  \
311  /* Add element to free bitmap and to free list. */ \
312  _pool_var (p)->free_bitmap = \
313  clib_bitmap_ori_notrim (_pool_var (p)->free_bitmap, \
314  _pool_var (l)); \
315  \
316  /* Preallocated pool? */ \
317  if (_pool_var (p)->max_elts) \
318  { \
319  ASSERT(_pool_var(l) < _pool_var (p)->max_elts); \
320  _pool_var(p)->free_indices[_vec_len(_pool_var(p)->free_indices)] = \
321  _pool_var(l); \
322  _vec_len(_pool_var(p)->free_indices) += 1; \
323  } \
324  else \
325  vec_add1 (_pool_var (p)->free_indices, _pool_var (l)); \
326  \
327  CLIB_MEM_POISON(_pool_var(e__), sizeof(_pool_var(e__)[0])); \
328 } while (0)
329 
330 /** Free pool element with given index. */
331 #define pool_put_index(p,i) \
332 do { \
333  typeof (p) _e = (p) + (i); \
334  pool_put (p, _e); \
335 } while (0)
336 
337 /** Allocate N more free elements to pool (general version). */
338 #define pool_alloc_aligned(P,N,A) \
339 do { \
340  pool_header_t * _p; \
341  \
342  if ((P)) \
343  { \
344  _p = pool_header (P); \
345  if (_p->max_elts) \
346  { \
347  clib_warning ("Can't expand fixed-size pool"); \
348  os_out_of_memory(); \
349  } \
350  } \
351  \
352  (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]), \
353  pool_aligned_header_bytes, \
354  (A)); \
355  _p = pool_header (P); \
356  vec_resize (_p->free_indices, (N)); \
357  _vec_len (_p->free_indices) -= (N); \
358 } while (0)
359 
360 /** Allocate N more free elements to pool (unspecified alignment). */
361 #define pool_alloc(P,N) pool_alloc_aligned(P,N,0)
362 
363 /**
364  * Return copy of pool with alignment
365  *
366  * @param P pool to copy
367  * @param A alignment (may be zero)
368  * @return copy of pool
369  */
370 #define pool_dup_aligned(P,A) \
371 ({ \
372  typeof (P) _pool_var (new) = 0; \
373  pool_header_t * _pool_var (ph), * _pool_var (new_ph); \
374  u32 _pool_var (n) = pool_len (P); \
375  if ((P)) \
376  { \
377  _pool_var (new) = _vec_resize (_pool_var (new), _pool_var (n), \
378  _pool_var (n) * sizeof ((P)[0]), \
379  pool_aligned_header_bytes, (A)); \
380  clib_memcpy_fast (_pool_var (new), (P), \
381  _pool_var (n) * sizeof ((P)[0])); \
382  _pool_var (ph) = pool_header (P); \
383  _pool_var (new_ph) = pool_header (_pool_var (new)); \
384  _pool_var (new_ph)->free_bitmap = \
385  clib_bitmap_dup (_pool_var (ph)->free_bitmap); \
386  _pool_var (new_ph)->free_indices = \
387  vec_dup (_pool_var (ph)->free_indices); \
388  _pool_var (new_ph)->max_elts = _pool_var (ph)->max_elts; \
389  } \
390  _pool_var (new); \
391 })
392 
393 /**
394  * Return copy of pool without alignment
395  *
396  * @param P pool to copy
397  * @return copy of pool
398  */
399 #define pool_dup(P) pool_dup_aligned(P,0)
400 
401 /** Low-level free pool operator (do not call directly). */
402 always_inline void *
403 _pool_free (void *v)
404 {
405  pool_header_t *p = pool_header (v);
406  if (!v)
407  return v;
409 
410  if (p->max_elts)
411  {
412  int rv;
413 
414  rv = munmap (p->mmap_base, p->mmap_size);
415  if (rv)
416  clib_unix_warning ("munmap");
417  }
418  else
419  {
420  vec_free (p->free_indices);
422  }
423  return 0;
424 }
425 
426 /** Free a pool. */
427 #define pool_free(p) (p) = _pool_free(p)
428 
429 /** Optimized iteration through pool.
430 
431  @param LO pointer to first element in chunk
432  @param HI pointer to last element in chunk
433  @param POOL pool to iterate across
434  @param BODY operation to perform
435 
436  Optimized version which assumes that BODY is smart enough to
437  process multiple (LOW,HI) chunks. See also pool_foreach().
438  */
439 #define pool_foreach_region(LO,HI,POOL,BODY) \
440 do { \
441  uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \
442  uword _pool_var (bl), * _pool_var (b); \
443  pool_header_t * _pool_var (p); \
444  \
445  _pool_var (p) = pool_header (POOL); \
446  _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0; \
447  _pool_var (bl) = vec_len (_pool_var (b)); \
448  _pool_var (len) = vec_len (POOL); \
449  _pool_var (lo) = 0; \
450  \
451  for (_pool_var (i) = 0; \
452  _pool_var (i) <= _pool_var (bl); \
453  _pool_var (i)++) \
454  { \
455  uword _pool_var (m), _pool_var (f); \
456  _pool_var (m) = (_pool_var (i) < _pool_var (bl) \
457  ? _pool_var (b) [_pool_var (i)] \
458  : 1); \
459  while (_pool_var (m) != 0) \
460  { \
461  _pool_var (f) = first_set (_pool_var (m)); \
462  _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0]) \
463  + min_log2 (_pool_var (f))); \
464  _pool_var (hi) = (_pool_var (i) < _pool_var (bl) \
465  ? _pool_var (hi) : _pool_var (len)); \
466  _pool_var (m) ^= _pool_var (f); \
467  if (_pool_var (hi) > _pool_var (lo)) \
468  { \
469  (LO) = _pool_var (lo); \
470  (HI) = _pool_var (hi); \
471  do { BODY; } while (0); \
472  } \
473  _pool_var (lo) = _pool_var (hi) + 1; \
474  } \
475  } \
476 } while (0)
477 
478 /** Iterate through pool.
479 
480  @param VAR A variable of same type as pool vector to be used as an
481  iterator.
482  @param POOL The pool to iterate across.
483  @param BODY The operation to perform, typically a code block. See
484  the example below.
485 
486  This macro will call @c BODY with each active pool element.
487 
488  It is a bad idea to allocate or free pool element from within
489  @c pool_foreach. Build a vector of indices and dispose of them later.
490  Or call pool_flush.
491 
492 
493  @par Example
494  @code{.c}
495  proc_t *procs; // a pool of processes.
496  proc_t *proc; // pointer to one process; used as the iterator.
497 
498  pool_foreach (proc, procs, ({
499  if (proc->state != PROC_STATE_RUNNING)
500  continue;
501 
502  // check a running proc in some way
503  ...
504  }));
505  @endcode
506 
507  @warning Because @c pool_foreach is a macro, syntax errors can be
508  difficult to find inside @c BODY, let alone actual code bugs. One
509  can temporarily split a complex @c pool_foreach into a trivial
510  @c pool_foreach which builds a vector of active indices, and a
511  vec_foreach() (or plain for-loop) to walk the active index vector.
512  */
513 #define pool_foreach(VAR,POOL,BODY) \
514 do { \
515  uword _pool_foreach_lo, _pool_foreach_hi; \
516  pool_foreach_region (_pool_foreach_lo, _pool_foreach_hi, (POOL), \
517  ({ \
518  for ((VAR) = (POOL) + _pool_foreach_lo; \
519  (VAR) < (POOL) + _pool_foreach_hi; \
520  (VAR)++) \
521  do { BODY; } while (0); \
522  })); \
523 } while (0)
524 
525 /** Returns pointer to element at given index.
526 
527  ASSERTs that the supplied index is valid.
528  Even though one can write correct code of the form
529  @code
530  p = pool_base + index;
531  @endcode
532  use of @c pool_elt_at_index is strongly suggested.
533  */
534 #define pool_elt_at_index(p,i) \
535 ({ \
536  typeof (p) _e = (p) + (i); \
537  ASSERT (! pool_is_free (p, _e)); \
538  _e; \
539 })
540 
541 /** Return next occupied pool index after @c i, useful for safe iteration. */
542 #define pool_next_index(P,I) \
543 ({ \
544  pool_header_t * _pool_var (p) = pool_header (P); \
545  uword _pool_var (rv) = (I) + 1; \
546  \
547  _pool_var(rv) = \
548  (_pool_var (rv) < vec_len (P) ? \
549  clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
550  : ~0); \
551  _pool_var(rv) = \
552  (_pool_var (rv) < vec_len (P) ? \
553  _pool_var (rv) : ~0); \
554  _pool_var(rv); \
555 })
556 
557 /** Iterate pool by index. */
558 #define pool_foreach_index(i,v,body) \
559  for ((i) = 0; (i) < vec_len (v); (i)++) \
560  { \
561  if (! pool_is_free_index ((v), (i))) \
562  do { body; } while (0); \
563  }
564 
565 /**
566  * @brief Remove all elements from a pool in a safe way
567  *
568  * @param VAR each element in the pool
569  * @param POOL The pool to flush
570  * @param BODY The actions to perform on each element before it is returned to
571  * the pool. i.e. before it is 'freed'
572  */
573 #define pool_flush(VAR, POOL, BODY) \
574 { \
575  uword *_pool_var(ii), *_pool_var(dv) = NULL; \
576  \
577  pool_foreach((VAR), (POOL), \
578  ({ \
579  vec_add1(_pool_var(dv), (VAR) - (POOL)); \
580  })); \
581  vec_foreach(_pool_var(ii), _pool_var(dv)) \
582  { \
583  (VAR) = pool_elt_at_index((POOL), *_pool_var(ii)); \
584  do { BODY; } while (0); \
585  pool_put((POOL), (VAR)); \
586  } \
587  vec_free(_pool_var(dv)); \
588 }
589 
590 #endif /* included_pool_h */
591 
592 /*
593  * fd.io coding-style-patch-verification: ON
594  *
595  * Local Variables:
596  * eval: (c-set-style "gnu")
597  * End:
598  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:509
u64 mmap_size
Definition: pool.h:67
unsigned long u64
Definition: types.h:89
static void pool_header_validate_index(void *v, uword index)
Definition: pool.h:108
u32 * free_indices
Vector of free indices.
Definition: pool.h:58
#define vec_bytes(v)
Number of data bytes in vector.
unsigned char u8
Definition: types.h:56
unsigned int u32
Definition: types.h:88
void fpool_free(void *)
static pool_header_t * pool_header(void *v)
Get pool header from user pool pointer.
Definition: pool.h:77
#define always_inline
Definition: ipsec.h:28
#define pool_aligned_header_bytes
Align pool header so that pointers are naturally aligned.
Definition: pool.h:72
static uword pool_header_bytes(void *v)
Memory usage of pool header.
Definition: pool.h:150
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:317
static void pool_validate(void *v)
Validate a pool.
Definition: pool.h:93
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:380
static void * vec_aligned_header(void *v, uword header_bytes, uword align)
#define vec_capacity(v, b)
Total number of bytes that can fit in vector with current allocation.
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
Definition: bitmap.h:197
#define ASSERT(truth)
Bitmaps built as vectors of machine words.
#define clib_bitmap_free(v)
Free a bitmap.
Definition: bitmap.h:92
uword * free_bitmap
Bitmap of indices of free objects.
Definition: pool.h:55
static uword clib_bitmap_count_set_bits(uword *ai)
Return the number of set bits in a bitmap.
Definition: bitmap.h:462
#define vec_free_h(V, H)
Free vector&#39;s memory (general version)
Definition: vec.h:367
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u64 uword
Definition: types.h:112
#define clib_unix_warning(format, args...)
Definition: error.h:68
u32 index
Definition: flow_types.api:221
u32 max_elts
Maximum size of the pool, in elements.
Definition: pool.h:63
#define BITS(x)
Definition: clib.h:66
static uword pool_free_elts(void *v)
Queries whether pool has at least N_FREE free elements.
Definition: pool.h:168
u8 * mmap_base
mmap segment info: base + length
Definition: pool.h:66
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128