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