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