#include <vppinfra/bitmap.h>
#include <vppinfra/error.h>
-#include <vppinfra/mheap.h>
typedef struct
/** Vector of free indices. One element for each set bit in bitmap. */
u32 *free_indices;
-} pool_header_t;
-/** Align pool header so that pointers are naturally aligned. */
-#define pool_aligned_header_bytes \
- vec_aligned_header_bytes (sizeof (pool_header_t), sizeof (void *))
+ /* The following fields are set for fixed-size, preallocated pools */
+
+ /** Maximum size of the pool, in elements */
+ u32 max_elts;
+
+} pool_header_t;
/** Get pool header from user pool pointer */
always_inline pool_header_t *
pool_header (void *v)
{
- return vec_aligned_header (v, sizeof (pool_header_t), sizeof (void *));
+ return vec_header (v);
}
+void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts,
+ uword align);
+
+/** initialize a fixed-size, preallocated pool */
+#define pool_init_fixed(P, E) \
+ _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0));
+
/** Validate a pool */
always_inline void
pool_validate (void *v)
ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
}
-always_inline void
-pool_header_validate_index (void *v, uword index)
-{
- pool_header_t *p = pool_header (v);
-
- if (v)
- vec_validate (p->free_bitmap, index / BITS (uword));
-}
-
-#define pool_validate_index(v,i) \
-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)
-
/** Number of active elements in a pool.
* @return Number of active elements in a pool
*/
/** Local variable naming macro. */
#define _pool_var(v) _pool_##v
-/** Queries whether pool has at least N_FREE free elements. */
-always_inline uword
-pool_free_elts (void *v)
+/** Number of elements that can fit into pool with current allocation */
+#define pool_max_len(P) vec_max_len (P)
+
+/** Number of free elements in pool */
+static_always_inline uword
+_pool_free_elts (void *p, uword elt_sz)
{
- pool_header_t *p = pool_header (v);
- uword n_free = 0;
+ pool_header_t *ph;
+ uword n_free;
- if (v)
- {
- n_free += vec_len (p->free_indices);
+ if (p == 0)
+ return 0;
- /* Space left at end of vector? */
- n_free += vec_capacity (v, sizeof (p[0])) - vec_len (v);
- }
+ ph = pool_header (p);
+
+ n_free = vec_len (ph->free_indices);
+
+ /* Fixed-size pools have max_elts set non-zero */
+ if (ph->max_elts == 0)
+ n_free += _vec_max_len (p, elt_sz) - vec_len (p);
return n_free;
}
+#define pool_free_elts(P) _pool_free_elts ((void *) (P), _vec_elt_sz (P))
+
/** Allocate an object E from a pool P (general version).
First search free list. If nothing is free extend vector of objects.
*/
-#define pool_get_aligned(P,E,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); \
- \
- 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)
+
+static_always_inline void
+_pool_get (void **pp, void **ep, uword align, int zero, uword elt_sz)
+{
+ uword len = 0;
+ void *p = pp[0];
+ void *e;
+
+ if (p)
+ {
+ pool_header_t *ph = pool_header (p);
+ uword n_free = vec_len (ph->free_indices);
+
+ if (n_free)
+ {
+ uword index = ph->free_indices[n_free - 1];
+ e = p + index * elt_sz;
+ ph->free_bitmap =
+ clib_bitmap_andnoti_notrim (ph->free_bitmap, index);
+ vec_set_len (ph->free_indices, n_free - 1);
+ CLIB_MEM_UNPOISON (e, elt_sz);
+ goto done;
+ }
+
+ if (ph->max_elts)
+ {
+ clib_warning ("can't expand fixed-size pool");
+ os_out_of_memory ();
+ }
+ }
+
+ len = vec_len (p);
+
+ /* Nothing on free list, make a new element and return it. */
+ p =
+ _vec_realloc_inline (p, len + 1, elt_sz, sizeof (pool_header_t), align, 0);
+ e = p + len * elt_sz;
+
+ _vec_update_pointer (pp, p);
+
+done:
+ ep[0] = e;
+ if (zero)
+ clib_memset_u8 (e, 0, elt_sz);
+}
+
+#define _pool_get_aligned_internal(P, E, A, Z) \
+ _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z, \
+ _vec_elt_sz (P))
+
+/** Allocate an object E from a pool P with alignment A */
+#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 and zero it */
+#define pool_get_aligned_zero(P,E,A) _pool_get_aligned_internal(P,E,A,1)
/** Allocate an object E from a pool P (unspecified alignment). */
#define pool_get(P,E) pool_get_aligned(P,E,0)
+/** Allocate an object E from a pool P and zero it */
+#define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0)
+
+always_inline int
+_pool_get_will_expand (void *p, uword elt_sz)
+{
+ pool_header_t *ph;
+ uword len;
+
+ if (p == 0)
+ return 1;
+
+ ph = pool_header (p);
+
+ if (ph->max_elts)
+ len = ph->max_elts;
+ else
+ len = vec_len (ph->free_indices);
+
+ /* Free elements, certainly won't expand */
+ if (len > 0)
+ return 0;
+
+ return _vec_resize_will_expand (p, 1, elt_sz);
+}
+
+#define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0]))
+
+always_inline int
+_pool_put_will_expand (void *p, uword index, uword elt_sz)
+{
+ pool_header_t *ph = pool_header (p);
+
+ if (clib_bitmap_will_expand (ph->free_bitmap, index))
+ return 1;
+
+ if (vec_resize_will_expand (ph->free_indices, 1))
+ return 1;
+
+ return 0;
+}
+
+#define pool_put_will_expand(P, E) _pool_put_will_expand (P, (E) - (P), sizeof ((P)[0])
+
/** Use free bitmap to query whether given element is free. */
-#define pool_is_free(P,E) \
-({ \
- 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; \
-})
+static_always_inline int
+pool_is_free_index (void *p, uword index)
+{
+ pool_header_t *ph = pool_header (p);
+ return index < vec_len (p) ? clib_bitmap_get (ph->free_bitmap, index) : 1;
+}
-/** Use free bitmap to query whether given index is free */
-#define pool_is_free_index(P,I) pool_is_free((P),(P)+(I))
+#define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P))
/** Free an object E in pool P. */
-#define pool_put(P,E) \
-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)
+static_always_inline void
+_pool_put_index (void *p, uword index, uword elt_sz)
+{
+ pool_header_t *ph = pool_header (p);
-/** Free pool element with given index. */
-#define pool_put_index(p,i) \
-do { \
- typeof (p) _e = (p) + (i); \
- pool_put (p, _e); \
-} while (0)
+ ASSERT (index < ph->max_elts ? ph->max_elts : vec_len (p));
+ ASSERT (!pool_is_free_index (p, index));
+
+ /* Add element to free bitmap and to free list. */
+ ph->free_bitmap = clib_bitmap_ori_notrim (ph->free_bitmap, index);
+
+ /* Preallocated pool? */
+ if (ph->max_elts)
+ {
+ ph->free_indices[_vec_len (ph->free_indices)] = index;
+ vec_inc_len (ph->free_indices, 1);
+ }
+ else
+ vec_add1 (ph->free_indices, index);
+
+ CLIB_MEM_POISON (p + index * elt_sz, elt_sz);
+}
+
+#define pool_put_index(P, I) _pool_put_index ((void *) (P), I, _vec_elt_sz (P))
+#define pool_put(P, E) pool_put_index (P, (E) - (P))
/** Allocate N more free elements to pool (general version). */
-#define pool_alloc_aligned(P,N,A) \
-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 (unspecified alignment). */
-#define pool_alloc(P,N) pool_alloc_aligned(P,N,0)
+static_always_inline void
+_pool_alloc (void **pp, uword n_elts, uword align, void *heap, uword elt_sz)
+{
+ pool_header_t *ph = pool_header (pp[0]);
+ uword len = vec_len (pp[0]);
+
+ if (ph && ph->max_elts)
+ {
+ clib_warning ("Can't expand fixed-size pool");
+ os_out_of_memory ();
+ }
+
+ pp[0] = _vec_realloc_inline (pp[0], len + n_elts, elt_sz,
+ sizeof (pool_header_t), align, heap);
+ _vec_set_len (pp[0], len, elt_sz);
+ CLIB_MEM_POISON (pp[0] + len * elt_sz, n_elts * elt_sz);
+
+ ph = pool_header (pp[0]);
+ vec_resize (ph->free_indices, n_elts);
+ vec_dec_len (ph->free_indices, n_elts);
+ clib_bitmap_vec_validate (ph->free_bitmap, len + n_elts - 1);
+}
+
+#define pool_alloc_aligned_heap(P, N, A, H) \
+ _pool_alloc ((void **) &(P), N, _vec_align (P, A), H, _vec_elt_sz (P))
+
+#define pool_alloc_heap(P, N, H) pool_alloc_aligned_heap (P, N, 0, H)
+#define pool_alloc_aligned(P, N, A) pool_alloc_aligned_heap (P, N, A, 0)
+#define pool_alloc(P, N) pool_alloc_aligned_heap (P, N, 0, 0)
+
+static_always_inline void *
+_pool_dup (void *p, uword align, uword elt_sz)
+{
+ pool_header_t *nph, *ph = pool_header (p);
+ uword len = vec_len (p);
+ void *n;
+
+ if (ph && ph->max_elts)
+ {
+ clib_warning ("Can't expand fixed-size pool");
+ os_out_of_memory ();
+ }
+
+ n = _vec_realloc_inline (0, len, elt_sz, sizeof (pool_header_t), align, 0);
+ nph = pool_header (n);
+ clib_memset_u8 (nph, 0, sizeof (vec_header_t));
+
+ if (len)
+ {
+ u32 *fi;
+ vec_foreach (fi, ph->free_indices)
+ CLIB_MEM_UNPOISON (p + elt_sz * fi[0], elt_sz);
+
+ clib_memcpy_fast (n, p, len * elt_sz);
+
+ nph->free_bitmap = clib_bitmap_dup (ph->free_bitmap);
+ nph->free_indices = vec_dup (ph->free_indices);
+
+ vec_foreach (fi, ph->free_indices)
+ {
+ uword offset = elt_sz * fi[0];
+ CLIB_MEM_POISON (p + offset, elt_sz);
+ CLIB_MEM_POISON (n + offset, elt_sz);
+ }
+ }
+
+ return n;
+}
+
+/**
+ * Return copy of pool with alignment
+ *
+ * @param P pool to copy
+ * @param A alignment (may be zero)
+ * @return copy of pool
+ */
+
+#define pool_dup_aligned(P, A) \
+ _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P))
+
+/**
+ * Return copy of pool without alignment
+ *
+ * @param P pool to copy
+ * @return copy of pool
+ */
+#define pool_dup(P) pool_dup_aligned(P,0)
/** Low-level free pool operator (do not call directly). */
-always_inline void *
-_pool_free (void *v)
+always_inline void
+_pool_free (void **v)
{
- pool_header_t *p = pool_header (v);
- if (!v)
- return v;
+ pool_header_t *p = pool_header (v[0]);
+ if (!p)
+ return;
+
clib_bitmap_free (p->free_bitmap);
+
vec_free (p->free_indices);
- vec_free_h (v, pool_aligned_header_bytes);
- return 0;
+ _vec_free (v);
+}
+#define pool_free(p) _pool_free ((void **) &(p))
+
+static_always_inline uword
+pool_get_first_index (void *pool)
+{
+ pool_header_t *h = pool_header (pool);
+ return clib_bitmap_first_clear (h->free_bitmap);
}
-/** Free a pool. */
-#define pool_free(p) (p) = _pool_free(p)
+static_always_inline uword
+pool_get_next_index (void *pool, uword last)
+{
+ pool_header_t *h = pool_header (pool);
+ return clib_bitmap_next_clear (h->free_bitmap, last + 1);
+}
/** Optimized iteration through pool.
It is a bad idea to allocate or free pool element from within
@c pool_foreach. Build a vector of indices and dispose of them later.
+ Or call pool_flush.
@par Example
@c pool_foreach which builds a vector of active indices, and a
vec_foreach() (or plain for-loop) to walk the active index vector.
*/
-#define pool_foreach(VAR,POOL,BODY) \
-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)
+
+#define pool_foreach(VAR,POOL) \
+ if (POOL) \
+ for (VAR = POOL + pool_get_first_index (POOL); \
+ VAR < vec_end (POOL); \
+ VAR = POOL + pool_get_next_index (POOL, VAR - POOL))
/** Returns pointer to element at given index.
(_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); \
})
-/** Iterate pool by index. */
-#define pool_foreach_index(i,v,body) \
- for ((i) = 0; (i) < vec_len (v); (i)++) \
- { \
- if (! pool_is_free_index ((v), (i))) \
- do { body; } while (0); \
- }
+#define pool_foreach_index(i,v) \
+ if (v) \
+ for (i = pool_get_first_index (v); \
+ i < vec_len (v); \
+ i = pool_get_next_index (v, i)) \
+
+/**
+ * @brief Remove all elements from a pool in a safe way
+ *
+ * @param VAR each element in the pool
+ * @param POOL The pool to flush
+ * @param BODY The actions to perform on each element before it is returned to
+ * the pool. i.e. before it is 'freed'
+ */
+#define pool_flush(VAR, POOL, BODY) \
+{ \
+ 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)); \
+}
#endif /* included_pool_h */
Code Review / vpp.git / blobdiff