aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra/pool.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/pool.h')
-rw-r--r--src/vppinfra/pool.h405
1 files changed, 405 insertions, 0 deletions
diff --git a/src/vppinfra/pool.h b/src/vppinfra/pool.h
new file mode 100644
index 00000000000..e1c89e0a5fa
--- /dev/null
+++ b/src/vppinfra/pool.h
@@ -0,0 +1,405 @@
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/*
+ Copyright (c) 2001, 2002, 2003, 2004 Eliot Dresselhaus
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be
+ included in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+/** @file
+ * @brief 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.
+ */
+
+#ifndef included_pool_h
+#define included_pool_h
+
+#include <vppinfra/bitmap.h>
+#include <vppinfra/error.h>
+#include <vppinfra/mheap.h>
+
+
+typedef struct
+{
+ /** Bitmap of indices of free objects. */
+ uword *free_bitmap;
+
+ /** 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 *))
+
+/** 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 *));
+}
+
+/** Validate a pool */
+always_inline void
+pool_validate (void *v)
+{
+ pool_header_t *p = pool_header (v);
+ uword i, n_free_bitmap;
+
+ if (!v)
+ return;
+
+ n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
+ ASSERT (n_free_bitmap == vec_len (p->free_indices));
+ for (i = 0; i < vec_len (p->free_indices); i++)
+ 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
+ */
+always_inline uword
+pool_elts (void *v)
+{
+ uword ret = vec_len (v);
+ if (v)
+ ret -= vec_len (pool_header (v)->free_indices);
+ return ret;
+}
+
+/** Number of elements in pool vector.
+
+ @note You probably want to call pool_elts() instead.
+*/
+#define pool_len(p) vec_len(p)
+
+/** Number of elements in pool vector (usable as an lvalue)
+
+ @note You probably don't want to use this macro.
+*/
+#define _pool_len(p) _vec_len(p)
+
+/** Memory usage of pool header. */
+always_inline uword
+pool_header_bytes (void *v)
+{
+ pool_header_t *p = pool_header (v);
+
+ if (!v)
+ return 0;
+
+ return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
+}
+
+/** Memory usage of pool. */
+#define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
+
+/** 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)
+{
+ pool_header_t *p = pool_header (v);
+ uword n_free = 0;
+
+ if (v)
+ {
+ n_free += vec_len (p->free_indices);
+
+ /* Space left at end of vector? */
+ n_free += vec_capacity (v, sizeof (p[0])) - vec_len (v);
+ }
+
+ return n_free;
+}
+
+/** 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)
+
+/** Allocate an object E from a pool P (unspecified alignment). */
+#define pool_get(P,E) pool_get_aligned(P,E,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; \
+})
+
+/** Use free bitmap to query whether given index is free */
+#define pool_is_free_index(P,I) pool_is_free((P),(P)+(I))
+
+/** 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)
+
+/** Free pool element with given index. */
+#define pool_put_index(p,i) \
+do { \
+ typeof (p) _e = (p) + (i); \
+ pool_put (p, _e); \
+} while (0)
+
+/** 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)
+
+/** Low-level free pool operator (do not call directly). */
+always_inline void *
+_pool_free (void *v)
+{
+ pool_header_t *p = pool_header (v);
+ if (!v)
+ return v;
+ clib_bitmap_free (p->free_bitmap);
+ vec_free (p->free_indices);
+ vec_free_h (v, pool_aligned_header_bytes);
+ return 0;
+}
+
+/** Free a pool. */
+#define pool_free(p) (p) = _pool_free(p)
+
+/** Optimized iteration through pool.
+
+ @param LO pointer to first element in chunk
+ @param HI pointer to last element in chunk
+ @param POOL pool to iterate across
+ @param BODY operation to perform
+
+ Optimized version which assumes that BODY is smart enough to
+ process multiple (LOW,HI) chunks. See also pool_foreach().
+ */
+#define pool_foreach_region(LO,HI,POOL,BODY) \
+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)
+
+/** Iterate through pool.
+
+ @param VAR A variable of same type as pool vector to be used as an
+ iterator.
+ @param POOL The pool to iterate across.
+ @param BODY The operation to perform, typically a code block. See
+ the example below.
+
+ This macro will call @c BODY with each active pool element.
+
+ 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.
+
+
+ @par Example
+ @code{.c}
+ 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
+ ...
+ }));
+ @endcode
+
+ @warning Because @c pool_foreach is a macro, syntax errors can be
+ difficult to find inside @c BODY, let alone actual code bugs. One
+ can temporarily split a complex @c pool_foreach into a trivial
+ @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)
+
+/** Returns pointer to element at given index.
+
+ ASSERTs that the supplied index is valid.
+ Even though one can write correct code of the form
+ @code
+ p = pool_base + index;
+ @endcode
+ use of @c pool_elt_at_index is strongly suggested.
+ */
+#define pool_elt_at_index(p,i) \
+({ \
+ typeof (p) _e = (p) + (i); \
+ ASSERT (! pool_is_free (p, _e)); \
+ _e; \
+})
+
+/** Return next occupied pool index after @c i, useful for safe iteration. */
+#define pool_next_index(P,I) \
+({ \
+ 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); \
+})
+
+/** 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); \
+ }
+
+#endif /* included_pool_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */