FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
pool.h File Reference

Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedly allocating and freeing fixed-size data. Pools are fast, and avoid memory fragmentation. More...

+ Include dependency graph for pool.h:

Go to the source code of this file.

Data Structures

struct  pool_header_t
 

Macros

#define pool_aligned_header_bytes   vec_aligned_header_bytes (sizeof (pool_header_t), sizeof (void *))
 Align pool header so that pointers are naturally aligned. More...
 
#define pool_init_fixed(pool, max_elts)
 initialize a fixed-size, preallocated pool More...
 
#define pool_validate_index(v, i)
 
#define pool_len(p)   vec_len(p)
 Number of elements in pool vector. More...
 
#define pool_bytes(P)   (vec_bytes (P) + pool_header_bytes (P))
 Memory usage of pool. More...
 
#define pool_get_aligned_zero_numa(P, E, A, Z, S)   _pool_get_aligned_internal_numa(P,E,A,Z,S)
 
#define pool_get_aligned_numa(P, E, A, S)   _pool_get_aligned_internal_numa(P,E,A,0/*zero*/,S)
 
#define pool_get_numa(P, E, S)   _pool_get_aligned_internal_numa(P,E,0/*align*/,0/*zero*/,S)
 
#define pool_get_aligned(P, E, A)   _pool_get_aligned_internal(P,E,A,0)
 Allocate an object E from a pool P with alignment A. More...
 
#define pool_get_aligned_zero(P, E, A)   _pool_get_aligned_internal(P,E,A,1)
 Allocate an object E from a pool P with alignment A and zero it. More...
 
#define pool_get(P, E)   pool_get_aligned(P,E,0)
 Allocate an object E from a pool P (unspecified alignment). More...
 
#define pool_get_zero(P, E)   pool_get_aligned_zero(P,E,0)
 Allocate an object E from a pool P and zero it. More...
 
#define pool_get_aligned_will_expand(P, YESNO, A)
 See if pool_get will expand the pool or not. More...
 
#define pool_get_will_expand(P, YESNO)   pool_get_aligned_will_expand(P,YESNO,0)
 Tell the caller if pool get will expand the pool. More...
 
#define pool_is_free(P, E)
 Use free bitmap to query whether given element is free. More...
 
#define pool_is_free_index(P, I)   pool_is_free((P),(P)+(I))
 Use free bitmap to query whether given index is free. More...
 
#define pool_put(P, E)
 Free an object E in pool P. More...
 
#define pool_put_index(p, i)
 Free pool element with given index. More...
 
#define pool_alloc_aligned(P, N, A)
 Allocate N more free elements to pool (general version). More...
 
#define pool_alloc(P, N)   pool_alloc_aligned(P,N,0)
 Allocate N more free elements to pool (unspecified alignment). More...
 
#define pool_dup_aligned(P, A)
 Return copy of pool with alignment. More...
 
#define pool_dup(P)   pool_dup_aligned(P,0)
 Return copy of pool without alignment. More...
 
#define pool_free(p)   (p) = _pool_free(p)
 Free a pool. More...
 
#define pool_foreach_region(LO, HI, POOL, BODY)
 Optimized iteration through pool. More...
 
#define pool_foreach(VAR, POOL)
 Iterate through pool. More...
 
#define pool_foreach_old(VAR, POOL, BODY)
 
#define pool_elt_at_index(p, i)
 Returns pointer to element at given index. More...
 
#define pool_next_index(P, I)
 Return next occupied pool index after i, useful for safe iteration. More...
 
#define pool_foreach_index(i, v)
 
#define pool_foreach_index_old(i, v, body)
 Iterate pool by index. More...
 
#define pool_flush(VAR, POOL, BODY)
 Remove all elements from a pool in a safe way. More...
 

Functions

static pool_header_tpool_header (void *v)
 Get pool header from user pool pointer. More...
 
void fpool_free (void *)
 
static void pool_validate (void *v)
 Validate a pool. More...
 
static void pool_header_validate_index (void *v, uword index)
 
static uword pool_elts (void *v)
 Number of active elements in a pool. More...
 
static uword pool_header_bytes (void *v)
 Memory usage of pool header. More...
 
static uword pool_free_elts (void *v)
 Queries whether pool has at least N_FREE free elements. More...
 
static_always_inline uword pool_get_first_index (void *pool)
 
static_always_inline uword pool_get_next_index (void *pool, uword last)
 

Detailed Description

Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedly allocating and freeing fixed-size data. Pools are fast, and avoid memory fragmentation.

Definition in file pool.h.

Macro Definition Documentation

◆ pool_aligned_header_bytes

#define pool_aligned_header_bytes   vec_aligned_header_bytes (sizeof (pool_header_t), sizeof (void *))

Align pool header so that pointers are naturally aligned.

Definition at line 71 of file pool.h.

◆ pool_alloc

#define pool_alloc (   P,
  N 
)    pool_alloc_aligned(P,N,0)

Allocate N more free elements to pool (unspecified alignment).

Definition at line 367 of file pool.h.

◆ pool_alloc_aligned

#define pool_alloc_aligned (   P,
  N,
  A 
)
Value:
do { \
pool_header_t * _p; \
if ((P)) \
{ \
_p = pool_header (P); \
if (_p->max_elts) \
{ \
clib_warning ("Can't expand fixed-size pool"); \
os_out_of_memory(); \
} \
} \
\
(P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]), \
(A)); \
_p = pool_header (P); \
vec_resize (_p->free_indices, (N)); \
_vec_len (_p->free_indices) -= (N); \
} while (0)

Allocate N more free elements to pool (general version).

Definition at line 344 of file pool.h.

◆ pool_bytes

#define pool_bytes (   P)    (vec_bytes (P) + pool_header_bytes (P))

Memory usage of pool.

Definition at line 160 of file pool.h.

◆ pool_dup

#define pool_dup (   P)    pool_dup_aligned(P,0)

Return copy of pool without alignment.

Parameters
Ppool to copy
Returns
copy of pool

Definition at line 405 of file pool.h.

◆ pool_dup_aligned

#define pool_dup_aligned (   P,
  A 
)
Value:
({ \
typeof (P) _pool_var (new) = 0; \
pool_header_t * _pool_var (ph), * _pool_var (new_ph); \
u32 _pool_var (n) = pool_len (P); \
if ((P)) \
{ \
_pool_var (new) = _vec_resize (_pool_var (new), _pool_var (n), \
_pool_var (n) * sizeof ((P)[0]), \
clib_memcpy_fast (_pool_var (new), (P), \
_pool_var (n) * sizeof ((P)[0])); \
_pool_var (ph) = pool_header (P); \
_pool_var (new_ph) = pool_header (_pool_var (new)); \
_pool_var (new_ph)->free_bitmap = \
clib_bitmap_dup (_pool_var (ph)->free_bitmap); \
_pool_var (new_ph)->free_indices = \
vec_dup (_pool_var (ph)->free_indices); \
_pool_var (new_ph)->max_elts = _pool_var (ph)->max_elts; \
} \
_pool_var (new); \
})

Return copy of pool with alignment.

Parameters
Ppool to copy
Aalignment (may be zero)
Returns
copy of pool

Definition at line 376 of file pool.h.

◆ pool_elt_at_index

#define pool_elt_at_index (   p,
  i 
)
Value:
({ \
typeof (p) _e = (p) + (i); \
ASSERT (! pool_is_free (p, _e)); \
_e; \
})

Returns pointer to element at given index.

ASSERTs that the supplied index is valid. Even though one can write correct code of the form

p = pool_base + index;

use of pool_elt_at_index is strongly suggested.

Definition at line 553 of file pool.h.

◆ pool_flush

#define pool_flush (   VAR,
  POOL,
  BODY 
)
Value:
{ \
uword *_pool_var(ii), *_pool_var(dv) = NULL; \
pool_foreach((VAR), (POOL)) \
{ \
vec_add1(_pool_var(dv), (VAR) - (POOL)); \
} \
vec_foreach(_pool_var(ii), _pool_var(dv)) \
{ \
(VAR) = pool_elt_at_index((POOL), *_pool_var(ii)); \
do { BODY; } while (0); \
pool_put((POOL), (VAR)); \
} \
vec_free(_pool_var(dv)); \
}

Remove all elements from a pool in a safe way.

Parameters
VAReach element in the pool
POOLThe pool to flush
BODYThe actions to perform on each element before it is returned to the pool. i.e. before it is 'freed'

Definition at line 595 of file pool.h.

◆ pool_foreach

#define pool_foreach (   VAR,
  POOL 
)
Value:
if (POOL) \
for (VAR = POOL + pool_get_first_index (POOL); \
VAR < vec_end (POOL); \
VAR = POOL + pool_get_next_index (POOL, VAR - POOL))

Iterate through pool.

Parameters
VARA variable of same type as pool vector to be used as an iterator.
POOLThe pool to iterate across.
BODYThe operation to perform, typically a code block. See the example below.

This macro will call BODY with each active pool element.

It is a bad idea to allocate or free pool element from within pool_foreach. Build a vector of indices and dispose of them later. Or call pool_flush.

Example
proc_t *procs; // a pool of processes.
proc_t *proc; // pointer to one process; used as the iterator.
pool_foreach (proc, procs, ({
if (proc->state != PROC_STATE_RUNNING)
continue;
// check a running proc in some way
...
}));
Warning
Because pool_foreach is a macro, syntax errors can be difficult to find inside BODY, let alone actual code bugs. One can temporarily split a complex pool_foreach into a trivial pool_foreach which builds a vector of active indices, and a vec_foreach() (or plain for-loop) to walk the active index vector.

Definition at line 534 of file pool.h.

◆ pool_foreach_index

#define pool_foreach_index (   i,
 
)
Value:
if (v) \
for (i = pool_get_first_index (v); \
i < vec_len (v); \
i = pool_get_next_index (v, i)) \

Definition at line 576 of file pool.h.

◆ pool_foreach_index_old

#define pool_foreach_index_old (   i,
  v,
  body 
)
Value:
{ body; }

Iterate pool by index.

Definition at line 583 of file pool.h.

◆ pool_foreach_old

#define pool_foreach_old (   VAR,
  POOL,
  BODY 
)
Value:
pool_foreach(VAR,POOL) \
{ BODY; }

Definition at line 540 of file pool.h.

◆ pool_foreach_region

#define pool_foreach_region (   LO,
  HI,
  POOL,
  BODY 
)
Value:
do { \
uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \
uword _pool_var (bl), * _pool_var (b); \
pool_header_t * _pool_var (p); \
\
_pool_var (p) = pool_header (POOL); \
_pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0; \
_pool_var (bl) = vec_len (_pool_var (b)); \
_pool_var (len) = vec_len (POOL); \
_pool_var (lo) = 0; \
for (_pool_var (i) = 0; \
_pool_var (i) <= _pool_var (bl); \
_pool_var (i)++) \
{ \
uword _pool_var (m), _pool_var (f); \
_pool_var (m) = (_pool_var (i) < _pool_var (bl) \
? _pool_var (b) [_pool_var (i)] \
: 1); \
while (_pool_var (m) != 0) \
{ \
_pool_var (f) = first_set (_pool_var (m)); \
_pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0]) \
+ min_log2 (_pool_var (f))); \
_pool_var (hi) = (_pool_var (i) < _pool_var (bl) \
? _pool_var (hi) : _pool_var (len)); \
_pool_var (m) ^= _pool_var (f); \
if (_pool_var (hi) > _pool_var (lo)) \
{ \
(LO) = _pool_var (lo); \
(HI) = _pool_var (hi); \
do { BODY; } while (0); \
} \
_pool_var (lo) = _pool_var (hi) + 1; \
} \
} \
} while (0)

Optimized iteration through pool.

Parameters
LOpointer to first element in chunk
HIpointer to last element in chunk
POOLpool to iterate across
BODYoperation to perform

Optimized version which assumes that BODY is smart enough to process multiple (LOW,HI) chunks. See also pool_foreach().

Definition at line 459 of file pool.h.

◆ pool_free

#define pool_free (   p)    (p) = _pool_free(p)

Free a pool.

Definition at line 447 of file pool.h.

◆ pool_get

#define pool_get (   P,
 
)    pool_get_aligned(P,E,0)

Allocate an object E from a pool P (unspecified alignment).

Definition at line 255 of file pool.h.

◆ pool_get_aligned

#define pool_get_aligned (   P,
  E,
  A 
)    _pool_get_aligned_internal(P,E,A,0)

Allocate an object E from a pool P with alignment A.

Definition at line 249 of file pool.h.

◆ pool_get_aligned_numa

#define pool_get_aligned_numa (   P,
  E,
  A,
  S 
)    _pool_get_aligned_internal_numa(P,E,A,0/*zero*/,S)

Definition at line 239 of file pool.h.

◆ pool_get_aligned_will_expand

#define pool_get_aligned_will_expand (   P,
  YESNO,
  A 
)
Value:
do { \
pool_header_t * _pool_var (p) = pool_header (P); \
uword _pool_var (l); \
\
_pool_var (l) = 0; \
if (P) \
{ \
if (_pool_var (p)->max_elts) \
_pool_var (l) = _pool_var (p)->max_elts; \
else \
_pool_var (l) = vec_len (_pool_var (p)->free_indices); \
} \
\
/* Free elements, certainly won't expand */ \
if (_pool_var (l) > 0) \
YESNO=0; \
else \
{ \
/* Nothing on free list, make a new element and return it. */ \
YESNO = _vec_resize_will_expand \
(P, \
/* length_increment */ 1, \
/* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
pool_aligned_header_bytes, \
/* align */ (A)); \
} \
} while (0)

See if pool_get will expand the pool or not.

Definition at line 261 of file pool.h.

◆ pool_get_aligned_zero

#define pool_get_aligned_zero (   P,
  E,
  A 
)    _pool_get_aligned_internal(P,E,A,1)

Allocate an object E from a pool P with alignment A and zero it.

Definition at line 252 of file pool.h.

◆ pool_get_aligned_zero_numa

#define pool_get_aligned_zero_numa (   P,
  E,
  A,
  Z,
  S 
)    _pool_get_aligned_internal_numa(P,E,A,Z,S)

Definition at line 236 of file pool.h.

◆ pool_get_numa

#define pool_get_numa (   P,
  E,
  S 
)    _pool_get_aligned_internal_numa(P,E,0/*align*/,0/*zero*/,S)

Definition at line 242 of file pool.h.

◆ pool_get_will_expand

#define pool_get_will_expand (   P,
  YESNO 
)    pool_get_aligned_will_expand(P,YESNO,0)

Tell the caller if pool get will expand the pool.

Definition at line 291 of file pool.h.

◆ pool_get_zero

#define pool_get_zero (   P,
 
)    pool_get_aligned_zero(P,E,0)

Allocate an object E from a pool P and zero it.

Definition at line 258 of file pool.h.

◆ pool_init_fixed

#define pool_init_fixed (   pool,
  max_elts 
)
Value:
{ \
_pool_init_fixed((void **)&(pool),sizeof(pool[0]),max_elts); \
}

initialize a fixed-size, preallocated pool

Definition at line 85 of file pool.h.

◆ pool_is_free

#define pool_is_free (   P,
 
)
Value:
({ \
pool_header_t * _pool_var (p) = pool_header (P); \
uword _pool_var (i) = (E) - (P); \
(_pool_var (i) < vec_len (P)) ? clib_bitmap_get (_pool_var (p)->free_bitmap, _pool_i) : 1; \
})

Use free bitmap to query whether given element is free.

Definition at line 294 of file pool.h.

◆ pool_is_free_index

#define pool_is_free_index (   P,
 
)    pool_is_free((P),(P)+(I))

Use free bitmap to query whether given index is free.

Definition at line 302 of file pool.h.

◆ pool_len

#define pool_len (   p)    vec_len(p)

Number of elements in pool vector.

Note
You probably want to call pool_elts() instead.

Definition at line 139 of file pool.h.

◆ pool_next_index

#define pool_next_index (   P,
 
)
Value:
({ \
pool_header_t * _pool_var (p) = pool_header (P); \
uword _pool_var (rv) = (I) + 1; \
\
_pool_var(rv) = \
(_pool_var (rv) < vec_len (P) ? \
clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
: ~0); \
_pool_var(rv) = \
(_pool_var (rv) < vec_len (P) ? \
_pool_var (rv) : ~0); \
_pool_var(rv); \
})

Return next occupied pool index after i, useful for safe iteration.

Definition at line 561 of file pool.h.

◆ pool_put

#define pool_put (   P,
 
)
Value:
do \
{ \
typeof (P) _pool_var (p__) = (P); \
typeof (E) _pool_var (e__) = (E); \
pool_header_t *_pool_var (p) = pool_header (_pool_var (p__)); \
uword _pool_var (l) = _pool_var (e__) - _pool_var (p__); \
if (_pool_var (p)->max_elts == 0) \
ASSERT (vec_is_member (_pool_var (p__), _pool_var (e__))); \
ASSERT (!pool_is_free (_pool_var (p__), _pool_var (e__))); \
\
/* Add element to free bitmap and to free list. */ \
_pool_var (p)->free_bitmap = \
clib_bitmap_ori_notrim (_pool_var (p)->free_bitmap, _pool_var (l)); \
\
/* Preallocated pool? */ \
if (_pool_var (p)->max_elts) \
{ \
ASSERT (_pool_var (l) < _pool_var (p)->max_elts); \
_pool_var (p) \
->free_indices[_vec_len (_pool_var (p)->free_indices)] = \
_pool_var (l); \
_vec_len (_pool_var (p)->free_indices) += 1; \
} \
vec_add1 (_pool_var (p)->free_indices, _pool_var (l)); \
CLIB_MEM_POISON (_pool_var (e__), sizeof (_pool_var (e__)[0])); \
} \
while (0)

Free an object E in pool P.

Definition at line 305 of file pool.h.

◆ pool_put_index

#define pool_put_index (   p,
  i 
)
Value:
do { \
typeof (p) _e = (p) + (i); \
pool_put (p, _e); \
} while (0)

Free pool element with given index.

Definition at line 337 of file pool.h.

◆ pool_validate_index

#define pool_validate_index (   v,
  i 
)
Value:
do { \
uword __pool_validate_index = (i); \
vec_validate_ha ((v), __pool_validate_index, \
pool_aligned_header_bytes, /* align */ 0); \
pool_header_validate_index ((v), __pool_validate_index); \
} while (0)

Definition at line 115 of file pool.h.

Function Documentation

◆ fpool_free()

void fpool_free ( void *  )

◆ pool_elts()

static uword pool_elts ( void *  v)
inlinestatic

Number of active elements in a pool.

Returns
Number of active elements in a pool

Definition at line 127 of file pool.h.

+ Here is the call graph for this function:

◆ pool_free_elts()

static uword pool_free_elts ( void *  v)
inlinestatic

Queries whether pool has at least N_FREE free elements.

Definition at line 167 of file pool.h.

+ Here is the call graph for this function:

◆ pool_get_first_index()

static_always_inline uword pool_get_first_index ( void *  pool)

Definition at line 433 of file pool.h.

+ Here is the call graph for this function:

◆ pool_get_next_index()

static_always_inline uword pool_get_next_index ( void *  pool,
uword  last 
)

Definition at line 440 of file pool.h.

+ Here is the call graph for this function:

◆ pool_header()

static pool_header_t* pool_header ( void *  v)
inlinestatic

Get pool header from user pool pointer.

Definition at line 76 of file pool.h.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ pool_header_bytes()

static uword pool_header_bytes ( void *  v)
inlinestatic

Memory usage of pool header.

Definition at line 149 of file pool.h.

+ Here is the call graph for this function:

◆ pool_header_validate_index()

static void pool_header_validate_index ( void *  v,
uword  index 
)
inlinestatic

Definition at line 107 of file pool.h.

+ Here is the call graph for this function:

◆ pool_validate()

static void pool_validate ( void *  v)
inlinestatic

Validate a pool.

Definition at line 92 of file pool.h.

+ Here is the call graph for this function:
vec_is_member
#define vec_is_member(v, e)
True if given pointer is within given vector.
Definition: vec_bootstrap.h:200
CLIB_MEM_POISON
#define CLIB_MEM_POISON(a, s)
Definition: sanitizer.h:46
f
vlib_frame_t * f
Definition: interface_output.c:1080
pool_elt_at_index
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:553
vec_end
#define vec_end(v)
End (last data address) of vector.
Definition: vec_bootstrap.h:197
hi
vl_api_ip4_address_t hi
Definition: arp.api:37
P
#define P(fmt,...)
ph
pool_header_t * ph(void *p)
GDB callable function: ph - call pool_header - get pool header.
Definition: gdb_funcs.c:78
pool_foreach
#define pool_foreach(VAR, POOL)
Iterate through pool.
Definition: pool.h:534
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
clib_bitmap_get
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
Definition: bitmap.h:197
len
u8 len
Definition: ip_types.api:103
vec_add1
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:606
BITS
#define BITS(x)
Definition: clib.h:69
pool_is_free
#define pool_is_free(P, E)
Use free bitmap to query whether given element is free.
Definition: pool.h:294
if
if(node->flags &VLIB_NODE_FLAG_TRACE) vnet_interface_output_trace(vm
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:261
pool_len
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:139
index
u32 index
Definition: flow_types.api:221
A
#define A(x)
Definition: main.c:57
pool_get_first_index
static_always_inline uword pool_get_first_index(void *pool)
Definition: pool.h:433
pool_foreach_index
#define pool_foreach_index(i, v)
Definition: pool.h:576
pool_aligned_header_bytes
#define pool_aligned_header_bytes
Align pool header so that pointers are naturally aligned.
Definition: pool.h:71
for
for(i=1;i<=collision_buckets;i++)
Definition: flowhash_template.h:378
pool_header
static pool_header_t * pool_header(void *v)
Get pool header from user pool pointer.
Definition: pool.h:76
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
pool_get_next_index
static_always_inline uword pool_get_next_index(void *pool, uword last)
Definition: pool.h:440
rv
int __clib_unused rv
Definition: application.c:491
min_log2
static uword min_log2(uword x)
Definition: clib.h:176
first_set
static uword first_set(uword x)
Definition: clib.h:291
lo
lo
Definition: vector_altivec.h:95
N
#define N
Definition: aes_cbc.c:225