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