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