pool.h File Reference

Fixed length block allocator. More...

Include dependency graph for pool.h:

This graph shows which files directly or indirectly include this file:

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_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(P, E, A)
	Allocate an object E from a pool P (general version). 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_aligned_will_expand
	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)
#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_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, BODY)
	Iterate through pool. More...
#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, body)
	Iterate pool by index. More...
#define	pool_flush(VAR, POOL, BODY)
	Remove all elemenets from a pool in a safe way. More...

Functions
static pool_header_t *	pool_header (void *v)
	Get pool header from user pool pointer. More...
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...

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

#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 62 of file pool.h.

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

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

Definition at line 274 of file pool.h.

#define pool_alloc_aligned	(		P,
			N,
			A
	)

Value:

do {                                                                    \
  pool_header_t * _p;                                                   \
  (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]),       \
                     pool_aligned_header_bytes,                         \
                     (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 262 of file pool.h.

#define pool_bytes

(

P

)

(vec_bytes (P) + pool_header_bytes (P))

Memory usage of pool.

Definition at line 142 of file pool.h.

#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 397 of file pool.h.

#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 elemenets from a pool in a safe way.

Parameters

VAR	each element in the pool
POOL	The pool to flush
BODY	The actions to perform on each element before it is returned to the pool. i.e. before it is 'freed'

Definition at line 433 of file pool.h.

#define pool_foreach	(		VAR,
			POOL,
			BODY
	)

Value:

do {                                                                    \
  uword _pool_foreach_lo, _pool_foreach_hi;                             \
  pool_foreach_region (_pool_foreach_lo, _pool_foreach_hi, (POOL),      \
    ({                                                                  \
      for ((VAR) = (POOL) + _pool_foreach_lo;                           \
           (VAR) < (POOL) + _pool_foreach_hi;                           \
           (VAR)++)                                                     \
        do { BODY; } while (0);                                         \
    }));                                                                \
} while (0)

Iterate through pool.

Parameters

VAR	A variable of same type as pool vector to be used as an iterator.
POOL	The pool to iterate across.
BODY	The 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 376 of file pool.h.

#define pool_foreach_index	(		i,
			v,
			body
	)

Value:

for ((i) = 0; (i) < vec_len (v); (i)++) \
    {                                           \
      if (! pool_is_free_index ((v), (i)))      \
        do { body; } while (0);                 \
    }

Iterate pool by index.

Definition at line 418 of file pool.h.

#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

LO	pointer to first element in chunk
HI	pointer to last element in chunk
POOL	pool to iterate across
BODY	operation to perform

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

Definition at line 302 of file pool.h.

#define pool_free

(

p

)

(p) = _pool_free(p)

Free a pool.

Definition at line 290 of file pool.h.

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

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

Definition at line 200 of file pool.h.

#define pool_get_aligned	(		P,
			E,
			A
	)

Value:

do {                                                                    \
  pool_header_t * _pool_var (p) = pool_header (P);                      \
  uword _pool_var (l);                                                  \
                                                                        \
  _pool_var (l) = 0;                                                    \
  if (P)                                                                \
    _pool_var (l) = vec_len (_pool_var (p)->free_indices);              \
                                                                        \
  if (_pool_var (l) > 0)                                                \
    {                                                                   \
      /* Return free element from free list. */                         \
      uword _pool_var (i) = _pool_var (p)->free_indices[_pool_var (l) - 1]; \
      (E) = (P) + _pool_var (i);                                        \
      _pool_var (p)->free_bitmap =                                      \
        clib_bitmap_andnoti (_pool_var (p)->free_bitmap, _pool_var (i)); \
      _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1;       \
    }                                                                   \
  else                                                                  \
    {                                                                   \
      /* Nothing on free list, make a new element and return it. */     \
      P = _vec_resize (P,                                               \
                       /* length_increment */ 1,                        \
                       /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
                       pool_aligned_header_bytes,                               \
                       /* align */ (A));                                \
      E = vec_end (P) - 1;                                              \
    }                                                                   \
} while (0)

Allocate an object E from a pool P (general version).

First search free list. If nothing is free extend vector of objects.

Definition at line 169 of file pool.h.

#define pool_get_aligned_will_expand

Value:

(P,YESNO,A)                        \
do {                                                                    \
  pool_header_t * _pool_var (p) = pool_header (P);                      \
  uword _pool_var (l);                                                  \
                                                                        \
  _pool_var (l) = 0;                                                    \
  if (P)                                                                \
    _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 203 of file pool.h.

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

Definition at line 227 of file pool.h.

#define pool_is_free	(		P,
			E
	)

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 230 of file pool.h.

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

Use free bitmap to query whether given index is free.

Definition at line 238 of file pool.h.

#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 121 of file pool.h.

#define pool_next_index	(		P,
			I
	)

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);                                                        \
})

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

Definition at line 405 of file pool.h.

#define pool_put	(		P,
			E
	)

Value:

do {                                                                    \
  pool_header_t * _pool_var (p) = pool_header (P);                      \
  uword _pool_var (l) = (E) - (P);                                      \
  ASSERT (vec_is_member (P, E));                                        \
  ASSERT (! pool_is_free (P, E));                                       \
                                                                        \
  /* Add element to free bitmap and to free list. */                    \
  _pool_var (p)->free_bitmap =                                          \
    clib_bitmap_ori (_pool_var (p)->free_bitmap, _pool_var (l));        \
  vec_add1 (_pool_var (p)->free_indices, _pool_var (l));                \
} while (0)

Free an object E in pool P.

Definition at line 241 of file pool.h.

#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 255 of file pool.h.

#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 97 of file pool.h.

Function Documentation

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 109 of file pool.h.

Here is the call graph for this function:

static uword pool_free_elts ( void *  v )

inlinestatic

Queries whether pool has at least N_FREE free elements.

Definition at line 149 of file pool.h.

Here is the call graph for this function:

static pool_header_t* pool_header ( void *  v )

inlinestatic

Get pool header from user pool pointer.

Definition at line 67 of file pool.h.

Here is the call graph for this function:

Here is the caller graph for this function:

static uword pool_header_bytes ( void *  v )

inlinestatic

Memory usage of pool header.

Definition at line 131 of file pool.h.

Here is the call graph for this function:

static void pool_header_validate_index ( void *  v, uword  index  )

inlinestatic

Definition at line 89 of file pool.h.

Here is the call graph for this function:

static void pool_validate ( void *  v )

inlinestatic

Validate a pool.

Definition at line 74 of file pool.h.

Here is the call graph for this function: