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 /** Get pool header from user pool pointer */
  67 always_inline pool_header_t *
  68 pool_header (void *v)
  69 {
  70   return vec_header (v);
  71 }
  72
  73 void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts,
  74                        uword align);
  75
  76 /** initialize a fixed-size, preallocated pool */
  77 #define pool_init_fixed(P, E)                                                 \
  78   _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0));
  79
  80 /** Validate a pool */
  81 always_inline void
  82 pool_validate (void *v)
  83 {
  84   pool_header_t *p = pool_header (v);
  85   uword i, n_free_bitmap;
  86
  87   if (!v)
  88     return;
  89
  90   n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
  91   ASSERT (n_free_bitmap == vec_len (p->free_indices));
  92   for (i = 0; i < vec_len (p->free_indices); i++)
  93     ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
  94 }
  95
  96 /** Number of active elements in a pool.
  97  * @return Number of active elements in a pool
  98  */
  99 always_inline uword
 100 pool_elts (void *v)
 101 {
 102   uword ret = vec_len (v);
 103   if (v)
 104     ret -= vec_len (pool_header (v)->free_indices);
 105   return ret;
 106 }
 107
 108 /** Number of elements in pool vector.
 109
 110     @note You probably want to call pool_elts() instead.
 111 */
 112 #define pool_len(p)     vec_len(p)
 113
 114 /** Number of elements in pool vector (usable as an lvalue)
 115
 116     @note You probably don't want to use this macro.
 117 */
 118 #define _pool_len(p)    _vec_len(p)
 119
 120 /** Memory usage of pool header. */
 121 always_inline uword
 122 pool_header_bytes (void *v)
 123 {
 124   pool_header_t *p = pool_header (v);
 125
 126   if (!v)
 127     return 0;
 128
 129   return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
 130 }
 131
 132 /** Memory usage of pool. */
 133 #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
 134
 135 /** Local variable naming macro. */
 136 #define _pool_var(v) _pool_##v
 137
 138 /** Number of elements that can fit into pool with current allocation */
 139 #define pool_max_len(P) vec_max_len (P)
 140
 141 /** Number of free elements in pool */
 142 static_always_inline uword
 143 _pool_free_elts (void *p, uword elt_sz)
 144 {
 145   pool_header_t *ph;
 146   uword n_free;
 147
 148   if (p == 0)
 149     return 0;
 150
 151   ph = pool_header (p);
 152
 153   n_free = vec_len (ph->free_indices);
 154
 155   /* Fixed-size pools have max_elts set non-zero */
 156   if (ph->max_elts == 0)
 157     n_free += _vec_max_len (p, elt_sz) - vec_len (p);
 158
 159   return n_free;
 160 }
 161
 162 #define pool_free_elts(P) _pool_free_elts ((void *) (P), _vec_elt_sz (P))
 163
 164 /** Allocate an object E from a pool P (general version).
 165
 166    First search free list.  If nothing is free extend vector of objects.
 167 */
 168
 169 static_always_inline void
 170 _pool_get (void **pp, void **ep, uword align, int zero, uword elt_sz)
 171 {
 172   uword len = 0;
 173   void *p = pp[0];
 174   void *e;
 175
 176   if (p)
 177     {
 178       pool_header_t *ph = pool_header (p);
 179       uword n_free = vec_len (ph->free_indices);
 180
 181       if (n_free)
 182         {
 183           uword index = ph->free_indices[n_free - 1];
 184           e = p + index * elt_sz;
 185           ph->free_bitmap =
 186             clib_bitmap_andnoti_notrim (ph->free_bitmap, index);
 187           _vec_len (ph->free_indices) = n_free - 1;
 188           CLIB_MEM_UNPOISON (e, elt_sz);
 189           goto done;
 190         }
 191
 192       if (ph->max_elts)
 193         {
 194           clib_warning ("can't expand fixed-size pool");
 195           os_out_of_memory ();
 196         }
 197     }
 198
 199   len = vec_len (p);
 200
 201   /* Nothing on free list, make a new element and return it. */
 202   p =
 203     _vec_realloc_inline (p, len + 1, elt_sz, sizeof (pool_header_t), align, 0);
 204   e = p + len * elt_sz;
 205
 206   _vec_update_pointer (pp, p);
 207
 208 done:
 209   ep[0] = e;
 210   if (zero)
 211     clib_memset_u8 (e, 0, elt_sz);
 212 }
 213
 214 #define _pool_get_aligned_internal(P, E, A, Z)                                \
 215   _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z,            \
 216              _vec_elt_sz (P))
 217
 218 /** Allocate an object E from a pool P with alignment A */
 219 #define pool_get_aligned(P,E,A) _pool_get_aligned_internal(P,E,A,0)
 220
 221 /** Allocate an object E from a pool P with alignment A and zero it */
 222 #define pool_get_aligned_zero(P,E,A) _pool_get_aligned_internal(P,E,A,1)
 223
 224 /** Allocate an object E from a pool P (unspecified alignment). */
 225 #define pool_get(P,E) pool_get_aligned(P,E,0)
 226
 227 /** Allocate an object E from a pool P and zero it */
 228 #define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0)
 229
 230 always_inline int
 231 _pool_get_will_expand (void *p, uword elt_sz)
 232 {
 233   pool_header_t *ph;
 234   uword len;
 235
 236   if (p == 0)
 237     return 1;
 238
 239   ph = pool_header (p);
 240
 241   if (ph->max_elts)
 242     len = ph->max_elts;
 243   else
 244     len = vec_len (ph->free_indices);
 245
 246   /* Free elements, certainly won't expand */
 247   if (len > 0)
 248     return 0;
 249
 250   return _vec_resize_will_expand (p, 1, elt_sz);
 251 }
 252
 253 #define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0]))
 254
 255 always_inline int
 256 _pool_put_will_expand (void *p, uword index, uword elt_sz)
 257 {
 258   pool_header_t *ph = pool_header (p);
 259
 260   if (clib_bitmap_will_expand (ph->free_bitmap, index))
 261     return 1;
 262
 263   if (vec_resize_will_expand (ph->free_indices, 1))
 264     return 1;
 265
 266   return 0;
 267 }
 268
 269 #define pool_put_will_expand(P, E) _pool_put_will_expand (P, (E) - (P), sizeof ((P)[0])
 270
 271 /** Use free bitmap to query whether given element is free. */
 272 static_always_inline int
 273 pool_is_free_index (void *p, uword index)
 274 {
 275   pool_header_t *ph = pool_header (p);
 276   return index < vec_len (p) ? clib_bitmap_get (ph->free_bitmap, index) : 1;
 277 }
 278
 279 #define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P))
 280
 281 /** Free an object E in pool P. */
 282 static_always_inline void
 283 _pool_put_index (void *p, uword index, uword elt_sz)
 284 {
 285   pool_header_t *ph = pool_header (p);
 286
 287   ASSERT (index < ph->max_elts ? ph->max_elts : vec_len (p));
 288   ASSERT (!pool_is_free_index (p, index));
 289
 290   /* Add element to free bitmap and to free list. */
 291   ph->free_bitmap = clib_bitmap_ori_notrim (ph->free_bitmap, index);
 292
 293   /* Preallocated pool? */
 294   if (ph->max_elts)
 295     {
 296       ph->free_indices[_vec_len (ph->free_indices)] = index;
 297       _vec_len (ph->free_indices) += 1;
 298     }
 299   else
 300     vec_add1 (ph->free_indices, index);
 301
 302   CLIB_MEM_POISON (p + index * elt_sz, elt_sz);
 303 }
 304
 305 #define pool_put_index(P, I) _pool_put_index ((void *) (P), I, _vec_elt_sz (P))
 306 #define pool_put(P, E)       pool_put_index (P, (E) - (P))
 307
 308 /** Allocate N more free elements to pool (general version). */
 309
 310 static_always_inline void
 311 _pool_alloc (void **pp, uword n_elts, uword align, uword elt_sz)
 312 {
 313   pool_header_t *ph = pool_header (pp[0]);
 314   uword len = vec_len (pp[0]);
 315
 316   if (ph && ph->max_elts)
 317     {
 318       clib_warning ("Can't expand fixed-size pool");
 319       os_out_of_memory ();
 320     }
 321
 322   pp[0] = _vec_realloc_inline (pp[0], len + n_elts, elt_sz,
 323                                sizeof (pool_header_t), align, 0);
 324   _vec_len (pp[0]) = len;
 325   CLIB_MEM_POISON (pp[0] + len * elt_sz, n_elts * elt_sz);
 326
 327   ph = pool_header (pp[0]);
 328   vec_resize (ph->free_indices, n_elts);
 329   _vec_len (ph->free_indices) -= n_elts;
 330   clib_bitmap_vec_validate (ph->free_bitmap, len + n_elts - 1);
 331 }
 332
 333 #define pool_alloc_aligned(P, N, A)                                           \
 334   _pool_alloc ((void **) &(P), N, _vec_align (P, A), _vec_elt_sz (P))
 335
 336 /** Allocate N more free elements to pool (unspecified alignment). */
 337 #define pool_alloc(P,N) pool_alloc_aligned(P,N,0)
 338
 339 static_always_inline void *
 340 _pool_dup (void *p, uword align, uword elt_sz)
 341 {
 342   pool_header_t *nph, *ph = pool_header (p);
 343   uword len = vec_len (p);
 344   void *n;
 345
 346   if (ph && ph->max_elts)
 347     {
 348       clib_warning ("Can't expand fixed-size pool");
 349       os_out_of_memory ();
 350     }
 351
 352   n = _vec_realloc_inline (0, len, elt_sz, sizeof (pool_header_t), align, 0);
 353   nph = pool_header (n);
 354   clib_memset_u8 (nph, 0, sizeof (vec_header_t));
 355
 356   if (len)
 357     {
 358       u32 *fi;
 359       vec_foreach (fi, ph->free_indices)
 360         CLIB_MEM_UNPOISON (p + elt_sz * fi[0], elt_sz);
 361
 362       clib_memcpy_fast (n, p, len * elt_sz);
 363
 364       nph->free_bitmap = clib_bitmap_dup (ph->free_bitmap);
 365       nph->free_indices = vec_dup (ph->free_indices);
 366
 367       vec_foreach (fi, ph->free_indices)
 368         {
 369           uword offset = elt_sz * fi[0];
 370           CLIB_MEM_POISON (p + offset, elt_sz);
 371           CLIB_MEM_POISON (n + offset, elt_sz);
 372         }
 373     }
 374
 375   return n;
 376 }
 377
 378 /**
 379  * Return copy of pool with alignment
 380  *
 381  * @param P pool to copy
 382  * @param A alignment (may be zero)
 383  * @return copy of pool
 384  */
 385
 386 #define pool_dup_aligned(P, A)                                                \
 387   _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P))
 388
 389 /**
 390  * Return copy of pool without alignment
 391  *
 392  * @param P pool to copy
 393  * @return copy of pool
 394  */
 395 #define pool_dup(P) pool_dup_aligned(P,0)
 396
 397 /** Low-level free pool operator (do not call directly). */
 398 always_inline void
 399 _pool_free (void **v)
 400 {
 401   pool_header_t *p = pool_header (v[0]);
 402   if (!p)
 403     return;
 404
 405   clib_bitmap_free (p->free_bitmap);
 406
 407   vec_free (p->free_indices);
 408   _vec_free (v);
 409 }
 410 #define pool_free(p) _pool_free ((void **) &(p))
 411
 412 static_always_inline uword
 413 pool_get_first_index (void *pool)
 414 {
 415   pool_header_t *h = pool_header (pool);
 416   return clib_bitmap_first_clear (h->free_bitmap);
 417 }
 418
 419 static_always_inline uword
 420 pool_get_next_index (void *pool, uword last)
 421 {
 422   pool_header_t *h = pool_header (pool);
 423   return clib_bitmap_next_clear (h->free_bitmap, last + 1);
 424 }
 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  */