vppinfra/vppinfra/mheap_bootstrap.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 #ifndef included_mem_mheap_h
  39 #define included_mem_mheap_h
  40
  41 /* Bootstrap include so that #include <vppinfra/mem.h> can include e.g.
  42    <vppinfra/mheap.h> which depends on <vppinfra/vec.h>. */
  43
  44 #include <vppinfra/vec_bootstrap.h>
  45 #include <vppinfra/error_bootstrap.h>
  46 #include <vppinfra/os.h>
  47 #include <vppinfra/vector.h>
  48
  49 /* Each element in heap is immediately followed by this struct. */
  50 typedef struct {
  51   /* Number of mheap_size_t words of user data in previous object.
  52      Used to find mheap_elt_t for previous object. */
  53 #if CLIB_VEC64 > 0
  54   u64 prev_n_user_data : 63;
  55
  56   /* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
  57 #define MHEAP_N_USER_DATA_INVALID (0x7fffffffffffffffULL)
  58 #define MHEAP_GROUNDED (~0ULL)
  59
  60   /* Set if previous object is free. */
  61   u64 prev_is_free : 1;
  62
  63   /* Number of mheap_size_t words of user data that follow this object. */
  64   u64 n_user_data : 63;
  65
  66   /* Set if this object is on free list (and therefore following free_elt
  67      is valid). */
  68   u64 is_free : 1;
  69
  70 #else
  71   u32 prev_n_user_data : 31;
  72
  73   /* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
  74 #define MHEAP_N_USER_DATA_INVALID (0x7fffffff)
  75 #define MHEAP_GROUNDED (~0)
  76
  77   /* Set if previous object is free. */
  78   u32 prev_is_free : 1;
  79
  80   /* Number of mheap_size_t words of user data that follow this object. */
  81   u32 n_user_data : 31;
  82
  83   /* Set if this object is on free list (and therefore following free_elt
  84      is valid). */
  85   u32 is_free : 1;
  86 #endif
  87
  88   union {
  89 #if CLIB_VEC64 > 0
  90     /* For allocated objects: user data follows.
  91        User data is allocated in units of typeof (user_data[0]). */
  92     u64 user_data[0];
  93
  94     /* For free objects, offsets of next and previous free objects of this size;
  95        ~0 means end of doubly-linked list.
  96        This is stored in user data (guaranteed to be at least 8 bytes)
  97        but only for *free* objects. */
  98     struct {
  99       u64 next_uoffset, prev_uoffset;
 100     } free_elt;
 101 #else
 102     /* For allocated objects: user data follows.
 103        User data is allocated in units of typeof (user_data[0]). */
 104     u32 user_data[0];
 105
 106     /* For free objects, offsets of next and previous free objects of this size;
 107        ~0 means end of doubly-linked list.
 108        This is stored in user data (guaranteed to be at least 8 bytes)
 109        but only for *free* objects. */
 110     struct {
 111       u32 next_uoffset, prev_uoffset;
 112     } free_elt;
 113 #endif
 114   };
 115 } mheap_elt_t;
 116
 117 /* Number of bytes of "overhead": e.g. not user data. */
 118 #define MHEAP_ELT_OVERHEAD_BYTES (sizeof (mheap_elt_t) - STRUCT_OFFSET_OF (mheap_elt_t, user_data))
 119
 120 /* User objects must be large enough to hold 2 x u32 free offsets in free elt. */
 121 #define MHEAP_MIN_USER_DATA_BYTES MHEAP_ELT_OVERHEAD_BYTES
 122
 123 /* Number of byte in user data "words". */
 124 #define MHEAP_USER_DATA_WORD_BYTES STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
 125
 126 typedef struct {
 127   /* Address of callers: outer first, inner last. */
 128   uword callers[12];
 129
 130   /* Count of allocations with this traceback. */
 131 #if CLIB_VEC64 > 0
 132   u64 n_allocations;
 133 #else
 134   u32 n_allocations;
 135 #endif
 136
 137   /* Count of bytes allocated with this traceback. */
 138   u32 n_bytes;
 139
 140   /* Offset of this item */
 141   uword offset;
 142 } mheap_trace_t;
 143
 144 typedef struct {
 145   mheap_trace_t * traces;
 146
 147   /* Indices of free traces. */
 148   u32 * trace_free_list;
 149
 150   /* Hash table mapping callers to trace index. */
 151   uword * trace_by_callers;
 152
 153   /* Hash table mapping mheap offset to trace index. */
 154   uword * trace_index_by_offset;
 155 } mheap_trace_main_t;
 156
 157   /* Small object bin i is for objects with
 158        user_size >  sizeof (mheap_elt_t) + sizeof (mheap_elt_t) * (i - 1)
 159        user_size <= sizeof (mheap_elt_t) + sizeof (mheap_size_t) * i. */
 160 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 8
 161 #define MHEAP_N_SMALL_OBJECT_BINS (1 << MHEAP_LOG2_N_SMALL_OBJECT_BINS)
 162
 163 #define MHEAP_N_BINS                                                    \
 164   (MHEAP_N_SMALL_OBJECT_BINS                                            \
 165    + (STRUCT_BITS_OF (mheap_elt_t, user_data[0]) - MHEAP_LOG2_N_SMALL_OBJECT_BINS))
 166
 167 typedef struct {
 168   struct {
 169     u64 n_search_attempts;
 170     u64 n_objects_searched;
 171     u64 n_objects_found;
 172   } free_list;
 173
 174   u64 n_vector_expands;
 175
 176   u64 n_small_object_cache_hits;
 177   u64 n_small_object_cache_attempts;
 178
 179   u64 n_gets, n_puts;
 180   u64 n_clocks_get, n_clocks_put;
 181 } mheap_stats_t;
 182
 183 /* Without vector instructions don't bother with small object cache. */
 184 #ifdef CLIB_HAVE_VEC128
 185 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
 186 #else
 187 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
 188 #endif
 189
 190 #if CLIB_VEC64 > 0
 191 #undef MHEAP_HAVE_SMALL_OBJECT_CACHE
 192 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
 193 #endif
 194
 195 /* For objects with align == 4 and align_offset == 0 (e.g. vector strings). */
 196 typedef struct {
 197   union {
 198 #ifdef CLIB_HAVE_VEC128
 199     u8x16 as_u8x16[BITS (uword) / 16];
 200 #endif
 201
 202     /* Store bin + 1; zero means unused. */
 203     u8 as_u8[BITS (uword)];
 204   } bins;
 205
 206   uword offsets[BITS (uword)];
 207
 208   u32 replacement_index;
 209 } mheap_small_object_cache_t;
 210
 211 /* Vec header for heaps. */
 212 typedef struct {
 213   /* User offsets for head of doubly-linked list of free objects of this size. */
 214 #if CLIB_VEC64 > 0
 215   u64 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
 216 #else
 217   u32 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
 218 #endif
 219
 220   /* Bitmap of non-empty free list bins. */
 221   uword non_empty_free_elt_heads[(MHEAP_N_BINS + BITS (uword) - 1) / BITS (uword)];
 222
 223   mheap_small_object_cache_t small_object_cache;
 224
 225   u32 flags;
 226 #define MHEAP_FLAG_TRACE                        (1 << 0)
 227 #define MHEAP_FLAG_DISABLE_VM                   (1 << 1)
 228 #define MHEAP_FLAG_THREAD_SAFE                  (1 << 2)
 229 #define MHEAP_FLAG_SMALL_OBJECT_CACHE           (1 << 3)
 230 #define MHEAP_FLAG_VALIDATE                     (1 << 4)
 231
 232   /* Lock use when MHEAP_FLAG_THREAD_SAFE is set. */
 233   volatile u32 lock;
 234   volatile u32 owner_cpu;
 235   int recursion_count;
 236
 237   /* Number of allocated objects. */
 238   u64 n_elts;
 239
 240   /* Maximum size (in bytes) this heap is allowed to grow to.
 241      Set to ~0 to grow heap (via vec_resize) arbitrarily. */
 242   u64 max_size;
 243
 244   uword vm_alloc_offset_from_header;
 245   uword vm_alloc_size;
 246
 247   /* Each successful mheap_validate call increments this serial number.
 248      Used to debug heap corruption problems.  GDB breakpoints can be
 249      made conditional on validate_serial. */
 250   u64 validate_serial;
 251
 252   mheap_trace_main_t trace_main;
 253
 254   mheap_stats_t stats;
 255 } mheap_t;
 256
 257 always_inline mheap_t * mheap_header (u8 * v)
 258 { return vec_aligned_header (v, sizeof (mheap_t), 16); }
 259
 260 always_inline u8 * mheap_vector (mheap_t * h)
 261 { return vec_aligned_header_end (h, sizeof (mheap_t), 16); }
 262
 263 always_inline uword mheap_elt_uoffset (void * v, mheap_elt_t * e)
 264 { return (uword)e->user_data - (uword)v; }
 265
 266 always_inline mheap_elt_t * mheap_user_pointer_to_elt (void *v)
 267 { return v - STRUCT_OFFSET_OF (mheap_elt_t, user_data); }
 268
 269 /* For debugging we keep track of offsets for valid objects.
 270    We make sure user is not trying to free object with invalid offset. */
 271 always_inline uword mheap_offset_is_valid (void * v, uword uo)
 272 { return uo >= MHEAP_ELT_OVERHEAD_BYTES && uo <= vec_len (v); }
 273
 274 always_inline mheap_elt_t * mheap_elt_at_uoffset (void * v, uword uo)
 275 {
 276   ASSERT (mheap_offset_is_valid (v, uo));
 277   return (mheap_elt_t *) (v + uo - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
 278 }
 279
 280 always_inline void * mheap_elt_data (void * v, mheap_elt_t * e)
 281 { return v + mheap_elt_uoffset (v, e); }
 282
 283 always_inline uword mheap_elt_data_bytes (mheap_elt_t * e)
 284 { return e->n_user_data * sizeof (e->user_data[0]); }
 285
 286 always_inline uword mheap_data_bytes (void * v, uword uo)
 287 {
 288   mheap_elt_t * e = mheap_elt_at_uoffset (v, uo);
 289   return mheap_elt_data_bytes (e);
 290 }
 291
 292 #define mheap_len(v,d) (mheap_data_bytes((v),(void *) (d) - (void *) (v)) / sizeof ((d)[0]))
 293
 294 always_inline mheap_elt_t * mheap_next_elt (mheap_elt_t * e)
 295 {
 296   ASSERT (e->n_user_data < MHEAP_N_USER_DATA_INVALID);
 297   return (mheap_elt_t *) (e->user_data + e->n_user_data);
 298 }
 299
 300 always_inline mheap_elt_t * mheap_prev_elt (mheap_elt_t * e)
 301 {
 302   ASSERT (e->prev_n_user_data < MHEAP_N_USER_DATA_INVALID);
 303   return ((void *) e
 304           - e->prev_n_user_data * sizeof (e->user_data[0])
 305           - MHEAP_ELT_OVERHEAD_BYTES);
 306 }
 307
 308 /* Exported operations. */
 309
 310 always_inline uword mheap_elts (void * v)
 311 { return v ? mheap_header (v)->n_elts : 0; }
 312
 313 always_inline uword mheap_max_size (void * v)
 314 { return v ? mheap_header (v)->max_size : ~0; }
 315
 316 /* Free previously allocated offset. */
 317 void mheap_put (void * v, uword offset);
 318
 319 /* Allocate object from mheap. */
 320 void * mheap_get_aligned (void * v, uword size, uword align, uword align_offset,
 321                           uword * offset_return);
 322
 323 #endif /* included_mem_mheap_h */