src/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
  50
  51 typedef struct
  52 {
  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
  59   /* The following fields are set for fixed-size, preallocated pools */
  60
  61   /** Maximum size of the pool, in elements */
  62   u32 max_elts;
  63
  64 } pool_header_t;
  65
  66 /** Align pool header so that pointers are naturally aligned. */
  67 #define pool_aligned_header_bytes                                             \
  68   round_pow2 (sizeof (pool_header_t), sizeof (void *))
  69
  70 /** Get pool header from user pool pointer */
  71 always_inline pool_header_t *
  72 pool_header (void *v)
  73 {
  74   return vec_header (v);
  75 }
  76
  77 extern void _pool_init_fixed (void **, u32, u32);
  78 extern void fpool_free (void *);
  79
  80 /** initialize a fixed-size, preallocated pool */
  81 #define pool_init_fixed(pool,max_elts)                  \
  82 {                                                       \
  83   _pool_init_fixed((void **)&(pool),sizeof(pool[0]),max_elts);  \
  84 }
  85
  86 /** Validate a pool */
  87 always_inline void
  88 pool_validate (void *v)
  89 {
  90   pool_header_t *p = pool_header (v);
  91   uword i, n_free_bitmap;
  92
  93   if (!v)
  94     return;
  95
  96   n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
  97   ASSERT (n_free_bitmap == vec_len (p->free_indices));
  98   for (i = 0; i < vec_len (p->free_indices); i++)
  99     ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
 100 }
 101
 102 always_inline void
 103 pool_header_validate_index (void *v, uword index)
 104 {
 105   pool_header_t *p = pool_header (v);
 106
 107   if (v)
 108     vec_validate (p->free_bitmap, index / BITS (uword));
 109 }
 110
 111 #define pool_validate_index(v,i)                                \
 112 do {                                                            \
 113   uword __pool_validate_index = (i);                            \
 114   vec_validate_ha ((v), __pool_validate_index,                  \
 115                    pool_aligned_header_bytes, /* align */ 0);   \
 116   pool_header_validate_index ((v), __pool_validate_index);      \
 117 } while (0)
 118
 119 /** Number of active elements in a pool.
 120  * @return Number of active elements in a pool
 121  */
 122 always_inline uword
 123 pool_elts (void *v)
 124 {
 125   uword ret = vec_len (v);
 126   if (v)
 127     ret -= vec_len (pool_header (v)->free_indices);
 128   return ret;
 129 }
 130
 131 /** Number of elements in pool vector.
 132
 133     @note You probably want to call pool_elts() instead.
 134 */
 135 #define pool_len(p)     vec_len(p)
 136
 137 /** Number of elements in pool vector (usable as an lvalue)
 138
 139     @note You probably don't want to use this macro.
 140 */
 141 #define _pool_len(p)    _vec_len(p)
 142
 143 /** Memory usage of pool header. */
 144 always_inline uword
 145 pool_header_bytes (void *v)
 146 {
 147   pool_header_t *p = pool_header (v);
 148
 149   if (!v)
 150     return 0;
 151
 152   return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
 153 }
 154
 155 /** Memory usage of pool. */
 156 #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
 157
 158 /** Local variable naming macro. */
 159 #define _pool_var(v) _pool_##v
 160
 161 /** Number of elements that can fit into pool with current allocation */
 162 #define pool_max_len(P) vec_max_len (P)
 163
 164 /** Number of free elements in pool */
 165 #define pool_free_elts(P)                                                     \
 166   ({                                                                          \
 167     pool_header_t *_pool_var (p) = pool_header (P);                           \
 168     uword n_free = 0;                                                         \
 169     if (P)                                                                    \
 170       {                                                                       \
 171         n_free += vec_len (_pool_var (p)->free_indices);                      \
 172         /* Fixed-size pools have max_elts set non-zero */                     \
 173         if (_pool_var (p)->max_elts == 0)                                     \
 174           n_free += pool_max_len (P) - vec_len (P);                           \
 175       }                                                                       \
 176     n_free;                                                                   \
 177   })
 178
 179 /** Allocate an object E from a pool P (general version).
 180
 181    First search free list.  If nothing is free extend vector of objects.
 182 */
 183 #define _pool_get_aligned_internal(P, E, A, Z)                                \
 184   do                                                                          \
 185     {                                                                         \
 186       pool_header_t *_pool_var (p) = pool_header (P);                         \
 187       uword _pool_var (l);                                                    \
 188                                                                               \
 189       STATIC_ASSERT (A == 0 || ((A % sizeof (P[0])) == 0) ||                  \
 190                        ((sizeof (P[0]) % A) == 0),                            \
 191                      "Pool aligned alloc of incorrectly sized object");       \
 192       _pool_var (l) = 0;                                                      \
 193       if (P)                                                                  \
 194         _pool_var (l) = vec_len (_pool_var (p)->free_indices);                \
 195                                                                               \
 196       if (_pool_var (l) > 0)                                                  \
 197         {                                                                     \
 198           /* Return free element from free list. */                           \
 199           uword _pool_var (i) =                                               \
 200             _pool_var (p)->free_indices[_pool_var (l) - 1];                   \
 201           (E) = (P) + _pool_var (i);                                          \
 202           _pool_var (p)->free_bitmap = clib_bitmap_andnoti_notrim (           \
 203             _pool_var (p)->free_bitmap, _pool_var (i));                       \
 204           _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1;         \
 205           CLIB_MEM_UNPOISON ((E), sizeof ((E)[0]));                           \
 206         }                                                                     \
 207       else                                                                    \
 208         {                                                                     \
 209           /* fixed-size, preallocated pools cannot expand */                  \
 210           if ((P) && _pool_var (p)->max_elts)                                 \
 211             {                                                                 \
 212               clib_warning ("can't expand fixed-size pool");                  \
 213               os_out_of_memory ();                                            \
 214             }                                                                 \
 215           /* Nothing on free list, make a new element and return it. */       \
 216           P = _vec_resize (P, /* length_increment */ 1,                       \
 217                            /* new size */ (vec_len (P) + 1) * sizeof (P[0]),  \
 218                            pool_aligned_header_bytes, /* align */ (A));       \
 219           E = vec_end (P) - 1;                                                \
 220         }                                                                     \
 221       if (Z)                                                                  \
 222         memset (E, 0, sizeof (*E));                                           \
 223     }                                                                         \
 224   while (0)
 225
 226 /** Allocate an object E from a pool P with alignment A */
 227 #define pool_get_aligned(P,E,A) _pool_get_aligned_internal(P,E,A,0)
 228
 229 /** Allocate an object E from a pool P with alignment A and zero it */
 230 #define pool_get_aligned_zero(P,E,A) _pool_get_aligned_internal(P,E,A,1)
 231
 232 /** Allocate an object E from a pool P (unspecified alignment). */
 233 #define pool_get(P,E) pool_get_aligned(P,E,0)
 234
 235 /** Allocate an object E from a pool P and zero it */
 236 #define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0)
 237
 238 always_inline int
 239 _pool_get_will_expand (void *p, uword elt_size)
 240 {
 241   pool_header_t *ph;
 242   uword len;
 243
 244   if (p == 0)
 245     return 1;
 246
 247   ph = pool_header (p);
 248
 249   if (ph->max_elts)
 250     len = ph->max_elts;
 251   else
 252     len = vec_len (ph->free_indices);
 253
 254   /* Free elements, certainly won't expand */
 255   if (len > 0)
 256     return 0;
 257
 258   return _vec_resize_will_expand (p, 1, elt_size);
 259 }
 260
 261 #define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0]))
 262
 263 always_inline int
 264 _pool_put_will_expand (void *p, uword index, uword elt_size)
 265 {
 266   pool_header_t *ph = pool_header (p);
 267
 268   if (clib_bitmap_will_expand (ph->free_bitmap, index))
 269     return 1;
 270
 271   if (vec_resize_will_expand (ph->free_indices, 1))
 272     return 1;
 273
 274   return 0;
 275 }
 276
 277 #define pool_put_will_expand(P, E) _pool_put_will_expand (P, (E) - (P), sizeof ((P)[0])
 278
 279 /** Use free bitmap to query whether given element is free. */
 280 #define pool_is_free(P,E)                                               \
 281 ({                                                                      \
 282   pool_header_t * _pool_var (p) = pool_header (P);                      \
 283   uword _pool_var (i) = (E) - (P);                                      \
 284   (_pool_var (i) < vec_len (P)) ? clib_bitmap_get (_pool_var (p)->free_bitmap, _pool_i) : 1; \
 285 })
 286
 287 /** Use free bitmap to query whether given index is free */
 288 #define pool_is_free_index(P,I) pool_is_free((P),(P)+(I))
 289
 290 /** Free an object E in pool P. */
 291 #define pool_put(P, E)                                                        \
 292   do                                                                          \
 293     {                                                                         \
 294       typeof (P) _pool_var (p__) = (P);                                       \
 295       typeof (E) _pool_var (e__) = (E);                                       \
 296       pool_header_t *_pool_var (p) = pool_header (_pool_var (p__));           \
 297       uword _pool_var (l) = _pool_var (e__) - _pool_var (p__);                \
 298       if (_pool_var (p)->max_elts == 0)                                       \
 299         ASSERT (vec_is_member (_pool_var (p__), _pool_var (e__)));            \
 300       ASSERT (!pool_is_free (_pool_var (p__), _pool_var (e__)));              \
 301                                                                               \
 302       /* Add element to free bitmap and to free list. */                      \
 303       _pool_var (p)->free_bitmap =                                            \
 304         clib_bitmap_ori_notrim (_pool_var (p)->free_bitmap, _pool_var (l));   \
 305                                                                               \
 306       /* Preallocated pool? */                                                \
 307       if (_pool_var (p)->max_elts)                                            \
 308         {                                                                     \
 309           ASSERT (_pool_var (l) < _pool_var (p)->max_elts);                   \
 310           _pool_var (p)                                                       \
 311             ->free_indices[_vec_len (_pool_var (p)->free_indices)] =          \
 312             _pool_var (l);                                                    \
 313           _vec_len (_pool_var (p)->free_indices) += 1;                        \
 314         }                                                                     \
 315       else                                                                    \
 316         vec_add1 (_pool_var (p)->free_indices, _pool_var (l));                \
 317                                                                               \
 318       CLIB_MEM_POISON (_pool_var (e__), sizeof (_pool_var (e__)[0]));         \
 319     }                                                                         \
 320   while (0)
 321
 322 /** Free pool element with given index. */
 323 #define pool_put_index(p,i)                     \
 324 do {                                            \
 325   typeof (p) _e = (p) + (i);                    \
 326   pool_put (p, _e);                             \
 327 } while (0)
 328
 329 /** Allocate N more free elements to pool (general version). */
 330 #define pool_alloc_aligned(P,N,A)                                       \
 331 do {                                                                    \
 332   pool_header_t * _p;                                                   \
 333                                                                         \
 334   if ((P))                                                              \
 335     {                                                                   \
 336       _p = pool_header (P);                                             \
 337       if (_p->max_elts)                                                 \
 338         {                                                               \
 339            clib_warning ("Can't expand fixed-size pool");               \
 340            os_out_of_memory();                                          \
 341         }                                                               \
 342     }                                                                   \
 343                                                                         \
 344   (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]),       \
 345                      pool_aligned_header_bytes,                         \
 346                      (A));                                              \
 347   _p = pool_header (P);                                                 \
 348   vec_resize (_p->free_indices, (N));                                   \
 349   _vec_len (_p->free_indices) -= (N);                                   \
 350 } while (0)
 351
 352 /** Allocate N more free elements to pool (unspecified alignment). */
 353 #define pool_alloc(P,N) pool_alloc_aligned(P,N,0)
 354
 355 /**
 356  * Return copy of pool with alignment
 357  *
 358  * @param P pool to copy
 359  * @param A alignment (may be zero)
 360  * @return copy of pool
 361  */
 362 #define pool_dup_aligned(P, A)                                                \
 363   ({                                                                          \
 364     typeof (P) _pool_var (new) = 0;                                           \
 365     pool_header_t *_pool_var (ph), *_pool_var (new_ph);                       \
 366     u32 _pool_var (n) = pool_len (P);                                         \
 367     if ((P))                                                                  \
 368       {                                                                       \
 369         _pool_var (new) = _vec_resize (_pool_var (new), _pool_var (n),        \
 370                                        _pool_var (n) * sizeof ((P)[0]),       \
 371                                        pool_aligned_header_bytes, (A));       \
 372         CLIB_MEM_OVERFLOW_PUSH ((P), _pool_var (n) * sizeof ((P)[0]));        \
 373         clib_memcpy_fast (_pool_var (new), (P),                               \
 374                           _pool_var (n) * sizeof ((P)[0]));                   \
 375         CLIB_MEM_OVERFLOW_POP ();                                             \
 376         _pool_var (ph) = pool_header (P);                                     \
 377         _pool_var (new_ph) = pool_header (_pool_var (new));                   \
 378         _pool_var (new_ph)->free_bitmap =                                     \
 379           clib_bitmap_dup (_pool_var (ph)->free_bitmap);                      \
 380         _pool_var (new_ph)->free_indices =                                    \
 381           vec_dup (_pool_var (ph)->free_indices);                             \
 382         _pool_var (new_ph)->max_elts = _pool_var (ph)->max_elts;              \
 383       }                                                                       \
 384     _pool_var (new);                                                          \
 385   })
 386
 387 /**
 388  * Return copy of pool without alignment
 389  *
 390  * @param P pool to copy
 391  * @return copy of pool
 392  */
 393 #define pool_dup(P) pool_dup_aligned(P,0)
 394
 395 /** Low-level free pool operator (do not call directly). */
 396 always_inline void *
 397 _pool_free (void *v)
 398 {
 399   pool_header_t *p = pool_header (v);
 400   if (!v)
 401     return v;
 402   clib_bitmap_free (p->free_bitmap);
 403
 404   vec_free (p->free_indices);
 405   vec_free (v);
 406   return 0;
 407 }
 408
 409 static_always_inline uword
 410 pool_get_first_index (void *pool)
 411 {
 412   pool_header_t *h = pool_header (pool);
 413   return clib_bitmap_first_clear (h->free_bitmap);
 414 }
 415
 416 static_always_inline uword
 417 pool_get_next_index (void *pool, uword last)
 418 {
 419   pool_header_t *h = pool_header (pool);
 420   return clib_bitmap_next_clear (h->free_bitmap, last + 1);
 421 }
 422
 423 /** Free a pool. */
 424 #define pool_free(p) (p) = _pool_free(p)
 425
 426 /** Optimized iteration through pool.
 427
 428     @param LO pointer to first element in chunk
 429     @param HI pointer to last element in chunk
 430     @param POOL pool to iterate across
 431     @param BODY operation to perform
 432
 433     Optimized version which assumes that BODY is smart enough to
 434     process multiple (LOW,HI) chunks. See also pool_foreach().
 435  */
 436 #define pool_foreach_region(LO,HI,POOL,BODY)                            \
 437 do {                                                                    \
 438   uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \
 439   uword _pool_var (bl), * _pool_var (b);                                \
 440   pool_header_t * _pool_var (p);                                        \
 441                                                                         \
 442   _pool_var (p) = pool_header (POOL);                                   \
 443   _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0;              \
 444   _pool_var (bl) = vec_len (_pool_var (b));                             \
 445   _pool_var (len) = vec_len (POOL);                                     \
 446   _pool_var (lo) = 0;                                                   \
 447                                                                         \
 448   for (_pool_var (i) = 0;                                               \
 449        _pool_var (i) <= _pool_var (bl);                                 \
 450        _pool_var (i)++)                                                 \
 451     {                                                                   \
 452       uword _pool_var (m), _pool_var (f);                               \
 453       _pool_var (m) = (_pool_var (i) < _pool_var (bl)                   \
 454                        ? _pool_var (b) [_pool_var (i)]                  \
 455                        : 1);                                            \
 456       while (_pool_var (m) != 0)                                        \
 457         {                                                               \
 458           _pool_var (f) = first_set (_pool_var (m));                    \
 459           _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0])     \
 460                             + min_log2 (_pool_var (f)));                \
 461           _pool_var (hi) = (_pool_var (i) < _pool_var (bl)              \
 462                             ? _pool_var (hi) : _pool_var (len));        \
 463           _pool_var (m) ^= _pool_var (f);                               \
 464           if (_pool_var (hi) > _pool_var (lo))                          \
 465             {                                                           \
 466               (LO) = _pool_var (lo);                                    \
 467               (HI) = _pool_var (hi);                                    \
 468               do { BODY; } while (0);                                   \
 469             }                                                           \
 470           _pool_var (lo) = _pool_var (hi) + 1;                          \
 471         }                                                               \
 472     }                                                                   \
 473 } while (0)
 474
 475 /** Iterate through pool.
 476
 477     @param VAR A variable of same type as pool vector to be used as an
 478                iterator.
 479     @param POOL The pool to iterate across.
 480     @param BODY The operation to perform, typically a code block. See
 481                 the example below.
 482
 483     This macro will call @c BODY with each active pool element.
 484
 485     It is a bad idea to allocate or free pool element from within
 486     @c pool_foreach. Build a vector of indices and dispose of them later.
 487     Or call pool_flush.
 488
 489
 490     @par Example
 491     @code{.c}
 492     proc_t *procs;   // a pool of processes.
 493     proc_t *proc;    // pointer to one process; used as the iterator.
 494
 495     pool_foreach (proc, procs, ({
 496         if (proc->state != PROC_STATE_RUNNING)
 497             continue;
 498
 499         // check a running proc in some way
 500         ...
 501     }));
 502     @endcode
 503
 504     @warning Because @c pool_foreach is a macro, syntax errors can be
 505     difficult to find inside @c BODY, let alone actual code bugs. One
 506     can temporarily split a complex @c pool_foreach into a trivial
 507     @c pool_foreach which builds a vector of active indices, and a
 508     vec_foreach() (or plain for-loop) to walk the active index vector.
 509  */
 510
 511 #define pool_foreach(VAR,POOL)                                          \
 512   if (POOL)                                                             \
 513     for (VAR = POOL + pool_get_first_index (POOL);                      \
 514          VAR < vec_end (POOL);                                          \
 515          VAR = POOL + pool_get_next_index (POOL, VAR - POOL))
 516
 517 /** Returns pointer to element at given index.
 518
 519     ASSERTs that the supplied index is valid.
 520     Even though one can write correct code of the form
 521     @code
 522         p = pool_base + index;
 523     @endcode
 524     use of @c pool_elt_at_index is strongly suggested.
 525  */
 526 #define pool_elt_at_index(p,i)                  \
 527 ({                                              \
 528   typeof (p) _e = (p) + (i);                    \
 529   ASSERT (! pool_is_free (p, _e));              \
 530   _e;                                           \
 531 })
 532
 533 /** Return next occupied pool index after @c i, useful for safe iteration. */
 534 #define pool_next_index(P,I)                                            \
 535 ({                                                                      \
 536   pool_header_t * _pool_var (p) = pool_header (P);                      \
 537   uword _pool_var (rv) = (I) + 1;                                       \
 538                                                                         \
 539   _pool_var(rv) =                                                       \
 540     (_pool_var (rv) < vec_len (P) ?                                     \
 541      clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
 542      : ~0);                                                             \
 543   _pool_var(rv) =                                                       \
 544     (_pool_var (rv) < vec_len (P) ?                                     \
 545      _pool_var (rv) : ~0);                                              \
 546   _pool_var(rv);                                                        \
 547 })
 548
 549 #define pool_foreach_index(i,v)         \
 550   if (v)                                        \
 551     for (i = pool_get_first_index (v);          \
 552          i < vec_len (v);                       \
 553          i = pool_get_next_index (v, i))        \
 554
 555 /**
 556  * @brief Remove all elements from a pool in a safe way
 557  *
 558  * @param VAR each element in the pool
 559  * @param POOL The pool to flush
 560  * @param BODY The actions to perform on each element before it is returned to
 561  *        the pool. i.e. before it is 'freed'
 562  */
 563 #define pool_flush(VAR, POOL, BODY)                     \
 564 {                                                       \
 565   uword *_pool_var(ii), *_pool_var(dv) = NULL;          \
 566                                                         \
 567   pool_foreach((VAR), (POOL))                          \
 568   {                                                     \
 569     vec_add1(_pool_var(dv), (VAR) - (POOL));            \
 570   }                                                     \
 571   vec_foreach(_pool_var(ii), _pool_var(dv))             \
 572   {                                                     \
 573     (VAR) = pool_elt_at_index((POOL), *_pool_var(ii));  \
 574     do { BODY; } while (0);                             \
 575     pool_put((POOL), (VAR));                            \
 576   }                                                     \
 577   vec_free(_pool_var(dv));                              \
 578 }
 579
 580 #endif /* included_pool_h */
 581
 582 /*
 583  * fd.io coding-style-patch-verification: ON
 584  *
 585  * Local Variables:
 586  * eval: (c-set-style "gnu")
 587  * End:
 588  */