vppinfra/vppinfra/pool.h

   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   /** Bitmap of indices of free objects. */
  54   uword * free_bitmap;
  55
  56   /** Vector of free indices.  One element for each set bit in bitmap. */
  57   u32 * free_indices;
  58 } pool_header_t;
  59
  60 /** Align pool header so that pointers are naturally aligned. */
  61 #define pool_aligned_header_bytes \
  62   vec_aligned_header_bytes (sizeof (pool_header_t), sizeof (void *))
  63
  64 /** Get pool header from user pool pointer */
  65 always_inline pool_header_t * pool_header (void * v)
  66 { return vec_aligned_header (v, sizeof (pool_header_t), sizeof (void *)); }
  67
  68 /** Validate a pool */
  69 always_inline void pool_validate (void * v)
  70 {
  71   pool_header_t * p = pool_header (v);
  72   uword i, n_free_bitmap;
  73
  74   if (! v)
  75     return;
  76
  77   n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
  78   ASSERT (n_free_bitmap == vec_len (p->free_indices));
  79   for (i = 0; i < vec_len (p->free_indices); i++)
  80     ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
  81 }
  82
  83 always_inline void pool_header_validate_index (void * v, uword index)
  84 {
  85   pool_header_t * p = pool_header (v);
  86
  87   if (v)
  88     vec_validate (p->free_bitmap, index / BITS (uword));
  89 }
  90
  91 #define pool_validate_index(v,i)                                \
  92 do {                                                            \
  93   uword __pool_validate_index = (i);                            \
  94   vec_validate_ha ((v), __pool_validate_index,                  \
  95                    pool_aligned_header_bytes, /* align */ 0);           \
  96   pool_header_validate_index ((v), __pool_validate_index);      \
  97 } while (0)
  98
  99 /** Number of active elements in a pool.
 100  * @return Number of active elements in a pool
 101  */
 102 always_inline uword pool_elts (void * v)
 103 {
 104   uword ret = vec_len (v);
 105   if (v)
 106     ret -= vec_len (pool_header (v)->free_indices);
 107   return ret;
 108 }
 109
 110 /** Number of elements in pool vector.
 111
 112     @note You probably want to call pool_elts() instead.
 113 */
 114 #define pool_len(p)     vec_len(p)
 115
 116 /** Number of elements in pool vector (usable as an lvalue)
 117
 118     @note You probably don't want to use this macro.
 119 */
 120 #define _pool_len(p)    _vec_len(p)
 121
 122 /** Memory usage of pool header. */
 123 always_inline uword
 124 pool_header_bytes (void * v)
 125 {
 126   pool_header_t * p = pool_header (v);
 127
 128   if (! v)
 129     return 0;
 130
 131   return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
 132 }
 133
 134 /** Memory usage of pool. */
 135 #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
 136
 137 /** Local variable naming macro. */
 138 #define _pool_var(v) _pool_##v
 139
 140 /** Queries whether pool has at least N_FREE free elements. */
 141 always_inline uword
 142 pool_free_elts (void * v)
 143 {
 144   pool_header_t * p = pool_header (v);
 145   uword n_free = 0;
 146
 147   if (v) {
 148     n_free += vec_len (p->free_indices);
 149
 150     /* Space left at end of vector? */
 151     n_free += vec_capacity (v, sizeof (p[0])) - vec_len (v);
 152   }
 153
 154   return n_free;
 155 }
 156
 157 /** Allocate an object E from a pool P (general version).
 158
 159    First search free list.  If nothing is free extend vector of objects.
 160 */
 161 #define pool_get_aligned(P,E,A)                                         \
 162 do {                                                                    \
 163   pool_header_t * _pool_var (p) = pool_header (P);                      \
 164   uword _pool_var (l);                                                  \
 165                                                                         \
 166   _pool_var (l) = 0;                                                    \
 167   if (P)                                                                \
 168     _pool_var (l) = vec_len (_pool_var (p)->free_indices);              \
 169                                                                         \
 170   if (_pool_var (l) > 0)                                                \
 171     {                                                                   \
 172       /* Return free element from free list. */                         \
 173       uword _pool_var (i) = _pool_var (p)->free_indices[_pool_var (l) - 1]; \
 174       (E) = (P) + _pool_var (i);                                        \
 175       _pool_var (p)->free_bitmap =                                      \
 176         clib_bitmap_andnoti (_pool_var (p)->free_bitmap, _pool_var (i)); \
 177       _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1;       \
 178     }                                                                   \
 179   else                                                                  \
 180     {                                                                   \
 181       /* Nothing on free list, make a new element and return it. */     \
 182       P = _vec_resize (P,                                               \
 183                        /* length_increment */ 1,                        \
 184                        /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
 185                        pool_aligned_header_bytes,                               \
 186                        /* align */ (A));                                \
 187       E = vec_end (P) - 1;                                              \
 188     }                                                                   \
 189 } while (0)
 190
 191 /** Allocate an object E from a pool P (unspecified alignment). */
 192 #define pool_get(P,E) pool_get_aligned(P,E,0)
 193
 194 /** Use free bitmap to query whether given element is free. */
 195 #define pool_is_free(P,E)                                               \
 196 ({                                                                      \
 197   pool_header_t * _pool_var (p) = pool_header (P);                      \
 198   uword _pool_var (i) = (E) - (P);                                      \
 199   (_pool_var (i) < vec_len (P)) ? clib_bitmap_get (_pool_var (p)->free_bitmap, _pool_i) : 1; \
 200 })
 201
 202 /** Use free bitmap to query whether given index is free */
 203 #define pool_is_free_index(P,I) pool_is_free((P),(P)+(I))
 204
 205 /** Free an object E in pool P. */
 206 #define pool_put(P,E)                                                   \
 207 do {                                                                    \
 208   pool_header_t * _pool_var (p) = pool_header (P);                      \
 209   uword _pool_var (l) = (E) - (P);                                      \
 210   ASSERT (vec_is_member (P, E));                                        \
 211   ASSERT (! pool_is_free (P, E));                                       \
 212                                                                         \
 213   /* Add element to free bitmap and to free list. */                    \
 214   _pool_var (p)->free_bitmap =                                          \
 215     clib_bitmap_ori (_pool_var (p)->free_bitmap, _pool_var (l));        \
 216   vec_add1 (_pool_var (p)->free_indices, _pool_var (l));                \
 217 } while (0)
 218
 219 /** Free pool element with given index. */
 220 #define pool_put_index(p,i)                     \
 221 do {                                            \
 222   typeof (p) _e = (p) + (i);                    \
 223   pool_put (p, _e);                             \
 224 } while (0)
 225
 226 /** Allocate N more free elements to pool (general version). */
 227 #define pool_alloc_aligned(P,N,A)                                       \
 228 do {                                                                    \
 229   pool_header_t * _p;                                                   \
 230   (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]),       \
 231                      pool_aligned_header_bytes,                         \
 232                      (A));                                              \
 233   _p = pool_header (P);                                                 \
 234   vec_resize (_p->free_indices, (N));                                   \
 235   _vec_len (_p->free_indices) -= (N);                                   \
 236 } while (0)
 237
 238 /** Allocate N more free elements to pool (unspecified alignment). */
 239 #define pool_alloc(P,N) pool_alloc_aligned(P,N,0)
 240
 241 /** Low-level free pool operator (do not call directly). */
 242 always_inline void * _pool_free (void * v)
 243 {
 244   pool_header_t * p = pool_header (v);
 245   if (! v)
 246     return v;
 247   clib_bitmap_free (p->free_bitmap);
 248   vec_free (p->free_indices);
 249   vec_free_h (v, pool_aligned_header_bytes);
 250   return 0;
 251 }
 252
 253 /** Free a pool. */
 254 #define pool_free(p) (p) = _pool_free(p)
 255
 256 /** Optimized iteration through pool.
 257
 258     @param LO pointer to first element in chunk
 259     @param HI pointer to last element in chunk
 260     @param POOL pool to iterate across
 261     @param BODY operation to perform
 262
 263     Optimized version which assumes that BODY is smart enough to
 264     process multiple (LOW,HI) chunks. See also pool_foreach().
 265  */
 266 #define pool_foreach_region(LO,HI,POOL,BODY)                            \
 267 do {                                                                    \
 268   uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \
 269   uword _pool_var (bl), * _pool_var (b);                                \
 270   pool_header_t * _pool_var (p);                                        \
 271                                                                         \
 272   _pool_var (p) = pool_header (POOL);                                   \
 273   _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0;              \
 274   _pool_var (bl) = vec_len (_pool_var (b));                             \
 275   _pool_var (len) = vec_len (POOL);                                     \
 276   _pool_var (lo) = 0;                                                   \
 277                                                                         \
 278   for (_pool_var (i) = 0;                                               \
 279        _pool_var (i) <= _pool_var (bl);                                 \
 280        _pool_var (i)++)                                                 \
 281     {                                                                   \
 282       uword _pool_var (m), _pool_var (f);                               \
 283       _pool_var (m) = (_pool_var (i) < _pool_var (bl)                   \
 284                        ? _pool_var (b) [_pool_var (i)]                  \
 285                        : 1);                                            \
 286       while (_pool_var (m) != 0)                                        \
 287         {                                                               \
 288           _pool_var (f) = first_set (_pool_var (m));                    \
 289           _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0])     \
 290                             + min_log2 (_pool_var (f)));                \
 291           _pool_var (hi) = (_pool_var (i) < _pool_var (bl)              \
 292                             ? _pool_var (hi) : _pool_var (len));        \
 293           _pool_var (m) ^= _pool_var (f);                               \
 294           if (_pool_var (hi) > _pool_var (lo))                          \
 295             {                                                           \
 296               (LO) = _pool_var (lo);                                    \
 297               (HI) = _pool_var (hi);                                    \
 298               do { BODY; } while (0);                                   \
 299             }                                                           \
 300           _pool_var (lo) = _pool_var (hi) + 1;                          \
 301         }                                                               \
 302     }                                                                   \
 303 } while (0)
 304
 305 /** Iterate through pool.
 306
 307     @param VAR A variable of same type as pool vector to be used as an
 308                iterator.
 309     @param POOL The pool to iterate across.
 310     @param BODY The operation to perform, typically a code block. See
 311                 the example below.
 312
 313     This macro will call @c BODY with each active pool element.
 314
 315     It is a bad idea to allocate or free pool element from within
 316     @c pool_foreach. Build a vector of indices and dispose of them later.
 317
 318
 319     @par Example
 320     @code{.c}
 321     proc_t *procs;   // a pool of processes.
 322     proc_t *proc;    // pointer to one process; used as the iterator.
 323
 324     pool_foreach (proc, procs, ({
 325         if (proc->state != PROC_STATE_RUNNING)
 326             continue;
 327
 328         // check a running proc in some way
 329         ...
 330     }));
 331     @endcode
 332
 333     @warning Because @c pool_foreach is a macro, syntax errors can be
 334     difficult to find inside @c BODY, let alone actual code bugs. One
 335     can temporarily split a complex @c pool_foreach into a trivial
 336     @c pool_foreach which builds a vector of active indices, and a
 337     vec_foreach() (or plain for-loop) to walk the active index vector.
 338  */
 339 #define pool_foreach(VAR,POOL,BODY)                                     \
 340 do {                                                                    \
 341   uword _pool_foreach_lo, _pool_foreach_hi;                             \
 342   pool_foreach_region (_pool_foreach_lo, _pool_foreach_hi, (POOL),      \
 343     ({                                                                  \
 344       for ((VAR) = (POOL) + _pool_foreach_lo;                           \
 345            (VAR) < (POOL) + _pool_foreach_hi;                           \
 346            (VAR)++)                                                     \
 347         do { BODY; } while (0);                                         \
 348     }));                                                                \
 349 } while (0)
 350
 351 /** Returns pointer to element at given index.
 352
 353     ASSERTs that the supplied index is valid.
 354     Even though one can write correct code of the form
 355     @code
 356         p = pool_base + index;
 357     @endcode
 358     use of @c pool_elt_at_index is strongly suggested.
 359  */
 360 #define pool_elt_at_index(p,i)                  \
 361 ({                                              \
 362   typeof (p) _e = (p) + (i);                    \
 363   ASSERT (! pool_is_free (p, _e));              \
 364   _e;                                           \
 365 })
 366
 367 /** Return next occupied pool index after @c i, useful for safe iteration. */
 368 #define pool_next_index(P,I)                                            \
 369 ({                                                                      \
 370   pool_header_t * _pool_var (p) = pool_header (P);                      \
 371   uword _pool_var (rv) = (I) + 1;                                       \
 372                                                                         \
 373   _pool_var(rv) =                                                       \
 374     (_pool_var (rv) < vec_len (P) ?                                     \
 375      clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
 376      : ~0);                                                             \
 377   _pool_var(rv);                                                        \
 378 })
 379
 380 /** Iterate pool by index. */
 381 #define pool_foreach_index(i,v,body)            \
 382   for ((i) = 0; (i) < vec_len (v); (i)++)       \
 383     {                                           \
 384       if (! pool_is_free_index ((v), (i)))      \
 385         do { body; } while (0);                 \
 386     }
 387
 388 #endif /* included_pool_h */