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);
 164 }
 165
 166 always_inline void
 167 heap_dup_header (heap_header_t * old, heap_header_t * new)
 168 {
 169   uword i;
 170
 171   new[0] = old[0];
 172   new->elts = vec_dup (new->elts);
 173   new->free_elts = vec_dup (new->free_elts);
 174   new->free_lists = vec_dup (new->free_lists);
 175   for (i = 0; i < vec_len (new->free_lists); i++)
 176     new->free_lists[i] = vec_dup (new->free_lists[i]);
 177   new->used_elt_bitmap = clib_bitmap_dup (new->used_elt_bitmap);
 178   new->small_free_elt_free_index = vec_dup (new->small_free_elt_free_index);
 179 }
 180
 181 /* Make a duplicate copy of a heap. */
 182 #define heap_dup(v) _heap_dup(v, vec_len (v) * sizeof (v[0]))
 183
 184 always_inline void *
 185 _heap_dup (void *v_old, uword v_bytes)
 186 {
 187   heap_header_t *h_old, *h_new;
 188   vec_attr_t va = { .align = HEAP_DATA_ALIGN,
 189                     .hdr_sz = sizeof (heap_header_t),
 190                     .elt_sz = 1 };
 191   void *v_new;
 192
 193   h_old = heap_header (v_old);
 194
 195   if (!v_old)
 196     return v_old;
 197
 198   v_new = _vec_alloc_internal (_vec_len (v_old), &va);
 199   h_new = heap_header (v_new);
 200   heap_dup_header (h_old, h_new);
 201   clib_memcpy_fast (v_new, v_old, v_bytes);
 202   return v_new;
 203 }
 204
 205 always_inline uword
 206 heap_elts (void *v)
 207 {
 208   heap_header_t *h = heap_header (v);
 209   return h->used_count;
 210 }
 211
 212 uword heap_bytes (void *v);
 213
 214 always_inline void *
 215 _heap_new (u32 len, u32 n_elt_bytes)
 216 {
 217   vec_attr_t va = { .align = HEAP_DATA_ALIGN,
 218                     .hdr_sz = sizeof (heap_header_t),
 219                     .elt_sz = n_elt_bytes };
 220   void *v = _vec_alloc_internal (len, &va);
 221   heap_header (v)->elt_bytes = n_elt_bytes;
 222   return v;
 223 }
 224
 225 #define heap_new(v) (v) = _heap_new (0, sizeof ((v)[0]))
 226
 227 always_inline void
 228 heap_set_format (void *v, format_function_t * format_elt)
 229 {
 230   ASSERT (v);
 231   heap_header (v)->format_elt = format_elt;
 232 }
 233
 234 always_inline void
 235 heap_set_max_len (void *v, uword max_len)
 236 {
 237   ASSERT (v);
 238   heap_header (v)->max_len = max_len;
 239 }
 240
 241 always_inline uword
 242 heap_get_max_len (void *v)
 243 {
 244   return v ? heap_header (v)->max_len : 0;
 245 }
 246
 247 /* Execute BODY for each allocated heap element. */
 248 #define heap_foreach(var,len,heap,body)                 \
 249 do {                                                    \
 250   if (vec_len (heap) > 0)                               \
 251     {                                                   \
 252       heap_header_t * _h = heap_header (heap);          \
 253       heap_elt_t * _e   = _h->elts + _h->head;          \
 254       heap_elt_t * _end = _h->elts + _h->tail;          \
 255       while (1)                                         \
 256         {                                               \
 257           if (! heap_is_free (_e))                      \
 258             {                                           \
 259               (var) = (heap) + heap_offset (_e);        \
 260               (len) = heap_elt_size ((heap), _e);       \
 261               do { body; } while (0);                   \
 262             }                                           \
 263           if (_e == _end)                               \
 264             break;                                      \
 265           _e = heap_next (_e);                          \
 266         }                                               \
 267     }                                                   \
 268 } while (0)
 269
 270 #define heap_elt_at_index(v,index) vec_elt_at_index(v,index)
 271
 272 always_inline heap_elt_t *
 273 heap_get_elt (void *v, uword handle)
 274 {
 275   heap_header_t *h = heap_header (v);
 276   heap_elt_t *e = vec_elt_at_index (h->elts, handle);
 277   ASSERT (!heap_is_free (e));
 278   return e;
 279 }
 280
 281 #define heap_elt_with_handle(v,handle)                  \
 282 ({                                                      \
 283   heap_elt_t * _e = heap_get_elt ((v), (handle));       \
 284   (v) + heap_offset (_e);                               \
 285 })
 286
 287 always_inline uword
 288 heap_is_free_handle (void *v, uword heap_handle)
 289 {
 290   heap_header_t *h = heap_header (v);
 291   heap_elt_t *e = vec_elt_at_index (h->elts, heap_handle);
 292   return heap_is_free (e);
 293 }
 294
 295 extern uword heap_len (void *v, word handle);
 296
 297 /* Low level allocation call. */
 298 extern void *_heap_alloc (void *v, uword size, uword alignment,
 299                           uword elt_bytes, uword * offset, uword * handle);
 300
 301 #define heap_alloc_aligned(v,size,align,handle)                 \
 302 ({                                                              \
 303   uword _o, _h;                                                 \
 304   uword _a = (align);                                           \
 305   uword _s = (size);                                            \
 306   (v) = _heap_alloc ((v), _s, _a, sizeof ((v)[0]), &_o, &_h);   \
 307   (handle) = _h;                                                \
 308   _o;                                                           \
 309 })
 310
 311 #define heap_alloc(v,size,handle) heap_alloc_aligned((v),(size),0,(handle))
 312
 313 extern void heap_dealloc (void *v, uword handle);
 314 extern void heap_validate (void *v);
 315
 316 /* Format heap internal data structures as string. */
 317 extern u8 *format_heap (u8 * s, va_list * va);
 318
 319 void *_heap_free (void *v);
 320
 321 #define heap_free(v) (v)=_heap_free(v)
 322
 323 #endif /* included_heap_h */
 324
 325 /*
 326  * fd.io coding-style-patch-verification: ON
 327  *
 328  * Local Variables:
 329  * eval: (c-set-style "gnu")
 330  * End:
 331  */