src/vppinfra/heap.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 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 /* Heaps of objects of type T (e.g. int, struct foo, ...).
  39
  40    Usage.  To declare a null heap:
  41
  42      T * heap = 0;
  43
  44    To allocate:
  45
  46      offset = heap_alloc (heap, size, handle);
  47
  48    New object is heap[offset] ... heap[offset + size]
  49    Handle is used to free/query object.
  50
  51    To free object:
  52
  53      heap_dealloc (heap, handle);
  54
  55    To query the size of an object:
  56
  57      heap_size (heap, handle)
  58
  59 */
  60
  61 #ifndef included_heap_h
  62 #define included_heap_h
  63
  64 #include <vppinfra/clib.h>
  65 #include <vppinfra/cache.h>
  66 #include <vppinfra/hash.h>
  67 #include <vppinfra/format.h>
  68 #include <vppinfra/bitmap.h>
  69
  70 /* Doubly linked list of elements. */
  71 typedef struct
  72 {
  73   /* Offset of this element (plus free bit).
  74      If element is free, data at offset contains pointer to free list. */
  75   u32 offset;
  76
  77   /* Index of next and previous elements relative to current element. */
  78   i32 next, prev;
  79 } heap_elt_t;
  80
  81 /* Use high bit of offset as free bit. */
  82 #define HEAP_ELT_FREE_BIT       (1 << 31)
  83
  84 always_inline uword
  85 heap_is_free (heap_elt_t * e)
  86 {
  87   return (e->offset & HEAP_ELT_FREE_BIT) != 0;
  88 }
  89
  90 always_inline uword
  91 heap_offset (heap_elt_t * e)
  92 {
  93   return e->offset & ~HEAP_ELT_FREE_BIT;
  94 }
  95
  96 always_inline heap_elt_t *
  97 heap_next (heap_elt_t * e)
  98 {
  99   return e + e->next;
 100 }
 101
 102 always_inline heap_elt_t *
 103 heap_prev (heap_elt_t * e)
 104 {
 105   return e + e->prev;
 106 }
 107
 108 always_inline uword
 109 heap_elt_size (void *v, heap_elt_t * e)
 110 {
 111   heap_elt_t *n = heap_next (e);
 112   uword next_offset = n != e ? heap_offset (n) : vec_len (v);
 113   return next_offset - heap_offset (e);
 114 }
 115
 116 /* Sizes are binned.  Sizes 1 to 2^log2_small_bins have their
 117    own free lists.  Larger sizes are grouped in powers of two. */
 118 #define HEAP_LOG2_SMALL_BINS    (5)
 119 #define HEAP_SMALL_BINS         (1 << HEAP_LOG2_SMALL_BINS)
 120 #define HEAP_N_BINS             (2 * HEAP_SMALL_BINS)
 121
 122 /* Header for heaps. */
 123 typedef struct
 124 {
 125   /* Vector of used and free elements. */
 126   heap_elt_t *elts;
 127
 128   /* For elt_bytes < sizeof (u32) we need some extra space
 129      per elt to store free list index. */
 130   u32 *small_free_elt_free_index;
 131
 132   /* Vector of free indices of elts array. */
 133   u32 *free_elts;
 134
 135   /* Indices of free elts indexed by size bin. */
 136   u32 **free_lists;
 137
 138   format_function_t *format_elt;
 139
 140   /* Used for validation/debugging. */
 141   uword *used_elt_bitmap;
 142
 143   /* First and last element of doubly linked chain of elements. */
 144   u32 head, tail;
 145
 146   u32 used_count, max_len;
 147
 148   /* Number of bytes in a help element. */
 149   u32 elt_bytes;
 150
 151   u32 flags;
 152   /* Static heaps are made from external memory given to
 153      us by user and are not re-sizable vectors. */
 154 #define HEAP_IS_STATIC (1)
 155 } heap_header_t;
 156
 157 /* Start of heap elements is always cache aligned. */
 158 #define HEAP_DATA_ALIGN (CLIB_CACHE_LINE_BYTES)
 159
 160 always_inline heap_header_t *
 161 heap_header (void *v)
 162 {
 163   return vec_header (v, sizeof (heap_header_t));
 164 }
 165
 166 always_inline uword
 167 heap_header_bytes ()
 168 {
 169   return vec_header_bytes (sizeof (heap_header_t));
 170 }
 171
 172 always_inline void
 173 heap_dup_header (heap_header_t * old, heap_header_t * new)
 174 {
 175   uword i;
 176
 177   new[0] = old[0];
 178   new->elts = vec_dup (new->elts);
 179   new->free_elts = vec_dup (new->free_elts);
 180   new->free_lists = vec_dup (new->free_lists);
 181   for (i = 0; i < vec_len (new->free_lists); i++)
 182     new->free_lists[i] = vec_dup (new->free_lists[i]);
 183   new->used_elt_bitmap = clib_bitmap_dup (new->used_elt_bitmap);
 184   new->small_free_elt_free_index = vec_dup (new->small_free_elt_free_index);
 185 }
 186
 187 /* Make a duplicate copy of a heap. */
 188 #define heap_dup(v) _heap_dup(v, vec_len (v) * sizeof (v[0]))
 189
 190 always_inline void *
 191 _heap_dup (void *v_old, uword v_bytes)
 192 {
 193   heap_header_t *h_old, *h_new;
 194   void *v_new;
 195
 196   h_old = heap_header (v_old);
 197
 198   if (!v_old)
 199     return v_old;
 200
 201   v_new = 0;
 202   v_new =
 203     _vec_resize (v_new, _vec_len (v_old), v_bytes, sizeof (heap_header_t),
 204                  HEAP_DATA_ALIGN);
 205   h_new = heap_header (v_new);
 206   heap_dup_header (h_old, h_new);
 207   clib_memcpy (v_new, v_old, v_bytes);
 208   return v_new;
 209 }
 210
 211 always_inline uword
 212 heap_elts (void *v)
 213 {
 214   heap_header_t *h = heap_header (v);
 215   return h->used_count;
 216 }
 217
 218 uword heap_bytes (void *v);
 219
 220 always_inline void *
 221 _heap_new (u32 len, u32 n_elt_bytes)
 222 {
 223   void *v = _vec_resize ((void *) 0, len, (uword) len * n_elt_bytes,
 224                          sizeof (heap_header_t),
 225                          HEAP_DATA_ALIGN);
 226   heap_header (v)->elt_bytes = n_elt_bytes;
 227   return v;
 228 }
 229
 230 #define heap_new(v) (v) = _heap_new (0, sizeof ((v)[0]))
 231
 232 always_inline void
 233 heap_set_format (void *v, format_function_t * format_elt)
 234 {
 235   ASSERT (v);
 236   heap_header (v)->format_elt = format_elt;
 237 }
 238
 239 always_inline void
 240 heap_set_max_len (void *v, uword max_len)
 241 {
 242   ASSERT (v);
 243   heap_header (v)->max_len = max_len;
 244 }
 245
 246 always_inline uword
 247 heap_get_max_len (void *v)
 248 {
 249   return v ? heap_header (v)->max_len : 0;
 250 }
 251
 252 /* Create fixed size heap with given block of memory. */
 253 always_inline void *
 254 heap_create_from_memory (void *memory, uword max_len, uword elt_bytes)
 255 {
 256   heap_header_t *h;
 257   void *v;
 258
 259   if (max_len * elt_bytes < sizeof (h[0]))
 260     return 0;
 261
 262   h = memory;
 263   memset (h, 0, sizeof (h[0]));
 264   h->max_len = max_len;
 265   h->elt_bytes = elt_bytes;
 266   h->flags = HEAP_IS_STATIC;
 267
 268   v = (void *) (memory + heap_header_bytes ());
 269   _vec_len (v) = 0;
 270   return v;
 271 }
 272
 273 /* Execute BODY for each allocated heap element. */
 274 #define heap_foreach(var,len,heap,body)                 \
 275 do {                                                    \
 276   if (vec_len (heap) > 0)                               \
 277     {                                                   \
 278       heap_header_t * _h = heap_header (heap);          \
 279       heap_elt_t * _e   = _h->elts + _h->head;          \
 280       heap_elt_t * _end = _h->elts + _h->tail;          \
 281       while (1)                                         \
 282         {                                               \
 283           if (! heap_is_free (_e))                      \
 284             {                                           \
 285               (var) = (heap) + heap_offset (_e);        \
 286               (len) = heap_elt_size ((heap), _e);       \
 287               do { body; } while (0);                   \
 288             }                                           \
 289           if (_e == _end)                               \
 290             break;                                      \
 291           _e = heap_next (_e);                          \
 292         }                                               \
 293     }                                                   \
 294 } while (0)
 295
 296 #define heap_elt_at_index(v,index) vec_elt_at_index(v,index)
 297
 298 always_inline heap_elt_t *
 299 heap_get_elt (void *v, uword handle)
 300 {
 301   heap_header_t *h = heap_header (v);
 302   heap_elt_t *e = vec_elt_at_index (h->elts, handle);
 303   ASSERT (!heap_is_free (e));
 304   return e;
 305 }
 306
 307 #define heap_elt_with_handle(v,handle)                  \
 308 ({                                                      \
 309   heap_elt_t * _e = heap_get_elt ((v), (handle));       \
 310   (v) + heap_offset (_e);                               \
 311 })
 312
 313 always_inline uword
 314 heap_is_free_handle (void *v, uword heap_handle)
 315 {
 316   heap_header_t *h = heap_header (v);
 317   heap_elt_t *e = vec_elt_at_index (h->elts, heap_handle);
 318   return heap_is_free (e);
 319 }
 320
 321 extern uword heap_len (void *v, word handle);
 322
 323 /* Low level allocation call. */
 324 extern void *_heap_alloc (void *v, uword size, uword alignment,
 325                           uword elt_bytes, uword * offset, uword * handle);
 326
 327 #define heap_alloc_aligned(v,size,align,handle)                 \
 328 ({                                                              \
 329   uword _o, _h;                                                 \
 330   uword _a = (align);                                           \
 331   uword _s = (size);                                            \
 332   (v) = _heap_alloc ((v), _s, _a, sizeof ((v)[0]), &_o, &_h);   \
 333   (handle) = _h;                                                \
 334   _o;                                                           \
 335 })
 336
 337 #define heap_alloc(v,size,handle) heap_alloc_aligned((v),(size),0,(handle))
 338
 339 extern void heap_dealloc (void *v, uword handle);
 340 extern void heap_validate (void *v);
 341
 342 /* Format heap internal data structures as string. */
 343 extern u8 *format_heap (u8 * s, va_list * va);
 344
 345 void *_heap_free (void *v);
 346
 347 #define heap_free(v) (v)=_heap_free(v)
 348
 349 #endif /* included_heap_h */
 350
 351 /*
 352  * fd.io coding-style-patch-verification: ON
 353  *
 354  * Local Variables:
 355  * eval: (c-set-style "gnu")
 356  * End:
 357  */