src/vppinfra/mheap.c

   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 #include <vppinfra/bitops.h>
  39 #include <vppinfra/hash.h>
  40 #include <vppinfra/format.h>
  41 #include <vppinfra/mheap.h>
  42 #include <vppinfra/os.h>
  43 #include <vppinfra/time.h>
  44
  45 #ifdef CLIB_UNIX
  46 #include <vppinfra/elf_clib.h>
  47 #endif
  48
  49 static void mheap_get_trace (void *v, uword offset, uword size);
  50 static void mheap_put_trace (void *v, uword offset, uword size);
  51 static int mheap_trace_sort (const void *t1, const void *t2);
  52
  53 always_inline void
  54 mheap_maybe_lock (void *v)
  55 {
  56   mheap_t *h = mheap_header (v);
  57   if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE))
  58     {
  59       u32 my_cpu = os_get_thread_index ();
  60       if (h->owner_cpu == my_cpu)
  61         {
  62           h->recursion_count++;
  63           return;
  64         }
  65
  66       while (__sync_lock_test_and_set (&h->lock, 1))
  67         ;
  68
  69       h->owner_cpu = my_cpu;
  70       h->recursion_count = 1;
  71     }
  72 }
  73
  74 always_inline void
  75 mheap_maybe_unlock (void *v)
  76 {
  77   mheap_t *h = mheap_header (v);
  78   if (v && h->flags & MHEAP_FLAG_THREAD_SAFE)
  79     {
  80       ASSERT (os_get_thread_index () == h->owner_cpu);
  81       if (--h->recursion_count == 0)
  82         {
  83           h->owner_cpu = ~0;
  84           CLIB_MEMORY_BARRIER ();
  85           h->lock = 0;
  86         }
  87     }
  88 }
  89
  90 /* Find bin for objects with size at least n_user_data_bytes. */
  91 always_inline uword
  92 user_data_size_to_bin_index (uword n_user_data_bytes)
  93 {
  94   uword n_user_data_words;
  95   word small_bin, large_bin;
  96
  97   /* User size must be at least big enough to hold free elt. */
  98   n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
  99
 100   /* Round to words. */
 101   n_user_data_words =
 102     (round_pow2 (n_user_data_bytes, MHEAP_USER_DATA_WORD_BYTES) /
 103      MHEAP_USER_DATA_WORD_BYTES);
 104
 105   ASSERT (n_user_data_words > 0);
 106   small_bin =
 107     n_user_data_words -
 108     (MHEAP_MIN_USER_DATA_BYTES / MHEAP_USER_DATA_WORD_BYTES);
 109   ASSERT (small_bin >= 0);
 110
 111   large_bin =
 112     MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) -
 113     MHEAP_LOG2_N_SMALL_OBJECT_BINS;
 114
 115   return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
 116 }
 117
 118 always_inline uword
 119 mheap_elt_size_to_user_n_bytes (uword n_bytes)
 120 {
 121   ASSERT (n_bytes >= sizeof (mheap_elt_t));
 122   return (n_bytes - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
 123 }
 124
 125 always_inline uword __attribute__ ((unused))
 126 mheap_elt_size_to_user_n_words (uword n_bytes)
 127 {
 128   ASSERT (n_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
 129   return mheap_elt_size_to_user_n_bytes (n_bytes) /
 130     MHEAP_USER_DATA_WORD_BYTES;
 131 }
 132
 133 always_inline void
 134 mheap_elt_set_size (void *v,
 135                     uword uoffset, uword n_user_data_bytes, uword is_free)
 136 {
 137   mheap_elt_t *e, *n;
 138
 139   e = mheap_elt_at_uoffset (v, uoffset);
 140
 141   ASSERT (n_user_data_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
 142
 143   e->n_user_data = n_user_data_bytes / MHEAP_USER_DATA_WORD_BYTES;
 144   e->is_free = is_free;
 145   ASSERT (e->prev_n_user_data * sizeof (e->user_data[0]) >=
 146           MHEAP_MIN_USER_DATA_BYTES);
 147
 148   n = mheap_next_elt (e);
 149   n->prev_n_user_data = e->n_user_data;
 150   n->prev_is_free = is_free;
 151 }
 152
 153 always_inline void
 154 set_first_free_elt_offset (mheap_t * h, uword bin, uword uoffset)
 155 {
 156   uword i0, i1;
 157
 158   h->first_free_elt_uoffset_by_bin[bin] = uoffset;
 159
 160   i0 = bin / BITS (h->non_empty_free_elt_heads[0]);
 161   i1 = (uword) 1 << (uword) (bin % BITS (h->non_empty_free_elt_heads[0]));
 162
 163   ASSERT (i0 < ARRAY_LEN (h->non_empty_free_elt_heads));
 164   if (h->first_free_elt_uoffset_by_bin[bin] == MHEAP_GROUNDED)
 165     h->non_empty_free_elt_heads[i0] &= ~i1;
 166   else
 167     h->non_empty_free_elt_heads[i0] |= i1;
 168 }
 169
 170 always_inline void
 171 set_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
 172 {
 173   mheap_t *h = mheap_header (v);
 174   mheap_elt_t *e = mheap_elt_at_uoffset (v, uoffset);
 175   mheap_elt_t *n = mheap_next_elt (e);
 176   uword bin = user_data_size_to_bin_index (n_user_data_bytes);
 177
 178   ASSERT (n->prev_is_free);
 179   ASSERT (e->is_free);
 180
 181   e->free_elt.prev_uoffset = MHEAP_GROUNDED;
 182   e->free_elt.next_uoffset = h->first_free_elt_uoffset_by_bin[bin];
 183
 184   /* Fill in next free elt's previous pointer. */
 185   if (e->free_elt.next_uoffset != MHEAP_GROUNDED)
 186     {
 187       mheap_elt_t *nf = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
 188       ASSERT (nf->is_free);
 189       nf->free_elt.prev_uoffset = uoffset;
 190     }
 191
 192   set_first_free_elt_offset (h, bin, uoffset);
 193 }
 194
 195 always_inline void
 196 new_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
 197 {
 198   mheap_elt_set_size (v, uoffset, n_user_data_bytes, /* is_free */ 1);
 199   set_free_elt (v, uoffset, n_user_data_bytes);
 200 }
 201
 202 always_inline void
 203 remove_free_elt (void *v, mheap_elt_t * e, uword bin)
 204 {
 205   mheap_t *h = mheap_header (v);
 206   mheap_elt_t *p, *n;
 207 #if CLIB_VEC64 > 0
 208   u64 no, po;
 209 #else
 210   u32 no, po;
 211 #endif
 212
 213   no = e->free_elt.next_uoffset;
 214
 215   n = no != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, no) : 0;
 216   po = e->free_elt.prev_uoffset;
 217   p = po != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, po) : 0;
 218
 219   if (!p)
 220     set_first_free_elt_offset (h, bin, no);
 221   else
 222     p->free_elt.next_uoffset = no;
 223
 224   if (n)
 225     n->free_elt.prev_uoffset = po;
 226 }
 227
 228 always_inline void
 229 remove_free_elt2 (void *v, mheap_elt_t * e)
 230 {
 231   uword bin;
 232   bin = user_data_size_to_bin_index (mheap_elt_data_bytes (e));
 233   remove_free_elt (v, e, bin);
 234 }
 235
 236 #define MHEAP_VM_MAP            (1 << 0)
 237 #define MHEAP_VM_UNMAP          (1 << 1)
 238 #define MHEAP_VM_NOMAP          (0 << 1)
 239 #define MHEAP_VM_ROUND          (1 << 2)
 240 #define MHEAP_VM_ROUND_UP       MHEAP_VM_ROUND
 241 #define MHEAP_VM_ROUND_DOWN     (0 << 2)
 242
 243 static uword mheap_page_size;
 244
 245 static_always_inline uword
 246 mheap_page_round (uword addr)
 247 {
 248   return (addr + mheap_page_size - 1) & ~(mheap_page_size - 1);
 249 }
 250
 251 static_always_inline uword
 252 mheap_page_truncate (uword addr)
 253 {
 254   return addr & ~(mheap_page_size - 1);
 255 }
 256
 257 static_always_inline uword
 258 mheap_vm (void *v, uword flags, clib_address_t start_addr, uword size)
 259 {
 260   mheap_t *h = mheap_header (v);
 261   clib_address_t start_page, end_page, end_addr;
 262   uword mapped_bytes;
 263
 264   ASSERT (!(h->flags & MHEAP_FLAG_DISABLE_VM));
 265
 266   end_addr = start_addr + size;
 267
 268   /* Round start/end address up to page boundary. */
 269   start_page = mheap_page_round (start_addr);
 270
 271   if ((flags & MHEAP_VM_ROUND) == MHEAP_VM_ROUND_UP)
 272     end_page = mheap_page_round (end_addr);
 273   else
 274     end_page = mheap_page_truncate (end_addr);
 275
 276   mapped_bytes = 0;
 277   if (end_page > start_page)
 278     {
 279       mapped_bytes = end_page - start_page;
 280       if (flags & MHEAP_VM_MAP)
 281         clib_mem_vm_map ((void *) start_page, end_page - start_page);
 282       else if (flags & MHEAP_VM_UNMAP)
 283         clib_mem_vm_unmap ((void *) start_page, end_page - start_page);
 284     }
 285
 286   return mapped_bytes;
 287 }
 288
 289 static_always_inline uword
 290 mheap_vm_elt (void *v, uword flags, uword offset)
 291 {
 292   mheap_elt_t *e;
 293   clib_address_t start_addr, end_addr;
 294
 295   e = mheap_elt_at_uoffset (v, offset);
 296   start_addr = (clib_address_t) ((void *) e->user_data);
 297   end_addr = (clib_address_t) mheap_next_elt (e);
 298   return mheap_vm (v, flags, start_addr, end_addr - start_addr);
 299 }
 300
 301 always_inline uword
 302 mheap_small_object_cache_mask (mheap_small_object_cache_t * c, uword bin)
 303 {
 304   uword mask;
 305
 306 /* $$$$ ELIOT FIXME: add Altivec version of this routine */
 307 #if !defined (CLIB_HAVE_VEC128) || defined (__ALTIVEC__) || defined (__i386__)
 308   mask = 0;
 309 #else
 310   u8x16 b = u8x16_splat (bin);
 311
 312   ASSERT (bin < 256);
 313
 314 #define _(i) ((uword) u8x16_compare_byte_mask ((b == c->bins.as_u8x16[i])) << (uword) ((i)*16))
 315   mask = _(0) | _(1);
 316   if (BITS (uword) > 32)
 317     mask |= _(2) | _(3);
 318 #undef _
 319
 320 #endif
 321   return mask;
 322 }
 323
 324 always_inline uword
 325 mheap_get_small_object (mheap_t * h, uword bin)
 326 {
 327   mheap_small_object_cache_t *c = &h->small_object_cache;
 328   uword mask = mheap_small_object_cache_mask (c, bin + 1);
 329   uword offset = MHEAP_GROUNDED;
 330
 331   if (mask)
 332     {
 333       uword i = min_log2 (mask);
 334       uword o = c->offsets[i];
 335       ASSERT (o != MHEAP_GROUNDED);
 336       c->bins.as_u8[i] = 0;
 337       offset = o;
 338     }
 339
 340   return offset;
 341 }
 342
 343 always_inline uword
 344 mheap_put_small_object (mheap_t * h, uword bin, uword offset)
 345 {
 346   mheap_small_object_cache_t *c = &h->small_object_cache;
 347   uword free_mask = mheap_small_object_cache_mask (c, 0);
 348   uword b = bin + 1;
 349   uword i;
 350
 351   if (free_mask != 0)
 352     {
 353       i = min_log2 (free_mask);
 354       c->bins.as_u8[i] = b;
 355       c->offsets[i] = offset;
 356       return 0;
 357     }
 358   else
 359     /* Nothing free with right size: cyclic replacement. */
 360     {
 361       uword old_offset;
 362
 363       i = c->replacement_index++;
 364       i %= BITS (uword);
 365       c->bins.as_u8[i] = b;
 366       old_offset = c->offsets[i];
 367       c->offsets[i] = offset;
 368
 369       /* Return old offset so it can be freed. */
 370       return old_offset;
 371     }
 372 }
 373
 374 static uword
 375 mheap_get_search_free_bin (void *v,
 376                            uword bin,
 377                            uword * n_user_data_bytes_arg,
 378                            uword align, uword align_offset)
 379 {
 380   mheap_t *h = mheap_header (v);
 381   mheap_elt_t *e;
 382
 383   /* Free object is at offset f0 ... f1;
 384      Allocatted object is at offset o0 ... o1. */
 385   word o0, o1, f0, f1, search_n_user_data_bytes;
 386   word lo_free_usize, hi_free_usize;
 387
 388   ASSERT (h->first_free_elt_uoffset_by_bin[bin] != MHEAP_GROUNDED);
 389   e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[bin]);
 390
 391   search_n_user_data_bytes = *n_user_data_bytes_arg;
 392
 393   /* Silence compiler warning. */
 394   o0 = o1 = f0 = f1 = 0;
 395
 396   h->stats.free_list.n_search_attempts += 1;
 397
 398   /* Find an object that is large enough with correct alignment at given alignment offset. */
 399   while (1)
 400     {
 401       uword this_object_n_user_data_bytes = mheap_elt_data_bytes (e);
 402
 403       ASSERT (e->is_free);
 404       if (bin < MHEAP_N_SMALL_OBJECT_BINS)
 405         ASSERT (this_object_n_user_data_bytes >= search_n_user_data_bytes);
 406
 407       h->stats.free_list.n_objects_searched += 1;
 408
 409       if (this_object_n_user_data_bytes < search_n_user_data_bytes)
 410         goto next;
 411
 412       /* Bounds of free object: from f0 to f1. */
 413       f0 = ((void *) e->user_data - v);
 414       f1 = f0 + this_object_n_user_data_bytes;
 415
 416       /* Place candidate object at end of free block and align as requested. */
 417       o0 = ((f1 - search_n_user_data_bytes) & ~(align - 1)) - align_offset;
 418       while (o0 < f0)
 419         o0 += align;
 420
 421       /* Make sure that first free fragment is either empty or
 422          large enough to be valid. */
 423       while (1)
 424         {
 425           lo_free_usize = o0 != f0 ? o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES : 0;
 426           if (o0 <= f0 || lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES)
 427             break;
 428           o0 -= align;
 429         }
 430
 431       o1 = o0 + search_n_user_data_bytes;
 432
 433       /* Does it fit? */
 434       if (o0 >= f0 && o1 <= f1)
 435         goto found;
 436
 437     next:
 438       /* Reached end of free list without finding large enough object. */
 439       if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
 440         return MHEAP_GROUNDED;
 441
 442       /* Otherwise keep searching for large enough object. */
 443       e = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
 444     }
 445
 446 found:
 447   /* Free fragment at end. */
 448   hi_free_usize = f1 != o1 ? f1 - o1 - MHEAP_ELT_OVERHEAD_BYTES : 0;
 449
 450   /* If fragment at end is too small to be a new object,
 451      give user's object a bit more space than requested. */
 452   if (hi_free_usize < (word) MHEAP_MIN_USER_DATA_BYTES)
 453     {
 454       search_n_user_data_bytes += f1 - o1;
 455       o1 = f1;
 456       hi_free_usize = 0;
 457     }
 458
 459   /* Need to make sure that relevant memory areas are mapped. */
 460   if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 461     {
 462       mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
 463       mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
 464       mheap_elt_t *o0_elt = mheap_elt_at_uoffset (v, o0);
 465       mheap_elt_t *o1_elt = mheap_elt_at_uoffset (v, o1);
 466
 467       uword f0_page_start, f0_page_end;
 468       uword o0_page_start, o0_page_end;
 469
 470       /* Free elt is mapped.  Addresses after that may not be mapped. */
 471       f0_page_start = mheap_page_round (pointer_to_uword (f0_elt->user_data));
 472       f0_page_end = mheap_page_truncate (pointer_to_uword (f1_elt));
 473
 474       o0_page_start = mheap_page_truncate (pointer_to_uword (o0_elt));
 475       o0_page_end = mheap_page_round (pointer_to_uword (o1_elt->user_data));
 476
 477       if (o0_page_start < f0_page_start)
 478         o0_page_start = f0_page_start;
 479       if (o0_page_end > f0_page_end)
 480         o0_page_end = f0_page_end;
 481
 482       if (o0_page_end > o0_page_start)
 483         clib_mem_vm_map (uword_to_pointer (o0_page_start, void *),
 484                          o0_page_end - o0_page_start);
 485     }
 486
 487   /* Remove free object from free list. */
 488   remove_free_elt (v, e, bin);
 489
 490   /* Free fragment at begining. */
 491   if (lo_free_usize > 0)
 492     {
 493       ASSERT (lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES);
 494       mheap_elt_set_size (v, f0, lo_free_usize, /* is_free */ 1);
 495       new_free_elt (v, f0, lo_free_usize);
 496     }
 497
 498   mheap_elt_set_size (v, o0, search_n_user_data_bytes, /* is_free */ 0);
 499
 500   if (hi_free_usize > 0)
 501     {
 502       uword uo = o1 + MHEAP_ELT_OVERHEAD_BYTES;
 503       mheap_elt_set_size (v, uo, hi_free_usize, /* is_free */ 1);
 504       new_free_elt (v, uo, hi_free_usize);
 505     }
 506
 507   /* Return actual size of block. */
 508   *n_user_data_bytes_arg = search_n_user_data_bytes;
 509
 510   h->stats.free_list.n_objects_found += 1;
 511
 512   return o0;
 513 }
 514
 515 /* Search free lists for object with given size and alignment. */
 516 static uword
 517 mheap_get_search_free_list (void *v,
 518                             uword * n_user_bytes_arg,
 519                             uword align, uword align_offset)
 520 {
 521   mheap_t *h = mheap_header (v);
 522   uword bin, n_user_bytes, i, bi;
 523
 524   n_user_bytes = *n_user_bytes_arg;
 525   bin = user_data_size_to_bin_index (n_user_bytes);
 526
 527   if (MHEAP_HAVE_SMALL_OBJECT_CACHE
 528       && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE)
 529       && bin < 255
 530       && align == STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
 531       && align_offset == 0)
 532     {
 533       uword r = mheap_get_small_object (h, bin);
 534       h->stats.n_small_object_cache_attempts += 1;
 535       if (r != MHEAP_GROUNDED)
 536         {
 537           h->stats.n_small_object_cache_hits += 1;
 538           return r;
 539         }
 540     }
 541
 542   for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads);
 543        i++)
 544     {
 545       uword non_empty_bin_mask = h->non_empty_free_elt_heads[i];
 546
 547       /* No need to search smaller bins. */
 548       if (i == bin / BITS (uword))
 549         non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));
 550
 551       /* Search each occupied free bin which is large enough. */
 552       /* *INDENT-OFF* */
 553       foreach_set_bit (bi, non_empty_bin_mask,
 554       ({
 555         uword r =
 556           mheap_get_search_free_bin (v, bi + i * BITS (uword),
 557                                      n_user_bytes_arg,
 558                                      align,
 559                                      align_offset);
 560         if (r != MHEAP_GROUNDED) return r;
 561       }));
 562       /* *INDENT-ON* */
 563     }
 564
 565   return MHEAP_GROUNDED;
 566 }
 567
 568 static never_inline void *
 569 mheap_get_extend_vector (void *v,
 570                          uword n_user_data_bytes,
 571                          uword align,
 572                          uword align_offset, uword * offset_return)
 573 {
 574   /* Bounds of free and allocated objects (as above). */
 575   uword f0, f1, o0, o1;
 576   word free_size;
 577   mheap_t *h = mheap_header (v);
 578   mheap_elt_t *e;
 579
 580   if (_vec_len (v) == 0)
 581     {
 582       _vec_len (v) = MHEAP_ELT_OVERHEAD_BYTES;
 583
 584       /* Create first element of heap. */
 585       e = mheap_elt_at_uoffset (v, _vec_len (v));
 586       e->prev_n_user_data = MHEAP_N_USER_DATA_INVALID;
 587     }
 588
 589   f0 = _vec_len (v);
 590
 591   o0 = round_pow2 (f0, align) - align_offset;
 592   while (1)
 593     {
 594       free_size = o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES;
 595       if (o0 == f0 || free_size >= (word) sizeof (mheap_elt_t))
 596         break;
 597
 598       o0 += align;
 599     }
 600
 601   o1 = o0 + n_user_data_bytes;
 602   f1 = o1 + MHEAP_ELT_OVERHEAD_BYTES;
 603
 604   ASSERT (v != 0);
 605   h = mheap_header (v);
 606
 607   /* Make sure we have space for object plus overhead. */
 608   if (f1 > h->max_size)
 609     {
 610       *offset_return = MHEAP_GROUNDED;
 611       return v;
 612     }
 613
 614   _vec_len (v) = f1;
 615
 616   if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 617     {
 618       mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
 619       mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
 620
 621       uword f0_page = mheap_page_round (pointer_to_uword (f0_elt->user_data));
 622       uword f1_page = mheap_page_round (pointer_to_uword (f1_elt->user_data));
 623
 624       if (f1_page > f0_page)
 625         mheap_vm (v, MHEAP_VM_MAP, f0_page, f1_page - f0_page);
 626     }
 627
 628   if (free_size > 0)
 629     new_free_elt (v, f0, free_size);
 630
 631   mheap_elt_set_size (v, o0, n_user_data_bytes, /* is_free */ 0);
 632
 633   /* Mark last element. */
 634   e = mheap_elt_at_uoffset (v, f1);
 635   e->n_user_data = MHEAP_N_USER_DATA_INVALID;
 636
 637   *offset_return = o0;
 638
 639   return v;
 640 }
 641
 642 void *
 643 mheap_get_aligned (void *v,
 644                    uword n_user_data_bytes,
 645                    uword align, uword align_offset, uword * offset_return)
 646 {
 647   mheap_t *h;
 648   uword offset;
 649   u64 cpu_times[2];
 650
 651   cpu_times[0] = clib_cpu_time_now ();
 652
 653   align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
 654   align = max_pow2 (align);
 655
 656   /* Correct align offset to be smaller than alignment. */
 657   align_offset &= (align - 1);
 658
 659   /* Align offset must be multiple of minimum object size. */
 660   if (align_offset % STRUCT_SIZE_OF (mheap_elt_t, user_data[0]) != 0)
 661     {
 662       *offset_return = MHEAP_GROUNDED;
 663       return v;
 664     }
 665
 666   /*
 667    * Round requested size.
 668    *
 669    * Step 1: round up to the minimum object size.
 670    * Step 2: round up to a multiple of the user data size (e.g. 4)
 671    * Step 3: if non-trivial alignment requested, round up
 672    *         so that the object precisely fills a chunk
 673    *         as big as the alignment request.
 674    *
 675    * Step 3 prevents the code from going into "bin search hyperspace":
 676    * looking at a huge number of fractional remainder chunks, none of which
 677    * will satisfy the alignment constraint. This fixes an allocator
 678    * performance issue when one requests a large number of 16 byte objects
 679    * aligned to 64 bytes, to name one variation on the theme.
 680    */
 681   n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
 682   n_user_data_bytes =
 683     round_pow2 (n_user_data_bytes,
 684                 STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
 685   if (align > MHEAP_ELT_OVERHEAD_BYTES)
 686     n_user_data_bytes = clib_max (n_user_data_bytes,
 687                                   align - MHEAP_ELT_OVERHEAD_BYTES);
 688   if (!v)
 689     v = mheap_alloc (0, 64 << 20);
 690
 691   mheap_maybe_lock (v);
 692
 693   h = mheap_header (v);
 694
 695   if (h->flags & MHEAP_FLAG_VALIDATE)
 696     mheap_validate (v);
 697
 698   /* First search free lists for object. */
 699   offset =
 700     mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
 701
 702   h = mheap_header (v);
 703
 704   /* If that fails allocate object at end of heap by extending vector. */
 705   if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
 706     {
 707       v =
 708         mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
 709                                  &offset);
 710       h = mheap_header (v);
 711       h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
 712     }
 713
 714   *offset_return = offset;
 715   if (offset != MHEAP_GROUNDED)
 716     {
 717       h->n_elts += 1;
 718
 719       if (h->flags & MHEAP_FLAG_TRACE)
 720         {
 721           /* Recursion block for case when we are traceing main clib heap. */
 722           h->flags &= ~MHEAP_FLAG_TRACE;
 723
 724           mheap_get_trace (v, offset, n_user_data_bytes);
 725
 726           h->flags |= MHEAP_FLAG_TRACE;
 727         }
 728     }
 729
 730   if (h->flags & MHEAP_FLAG_VALIDATE)
 731     mheap_validate (v);
 732
 733   mheap_maybe_unlock (v);
 734
 735   cpu_times[1] = clib_cpu_time_now ();
 736   h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
 737   h->stats.n_gets += 1;
 738
 739   return v;
 740 }
 741
 742 static void
 743 free_last_elt (void *v, mheap_elt_t * e)
 744 {
 745   mheap_t *h = mheap_header (v);
 746
 747   /* Possibly delete preceeding free element also. */
 748   if (e->prev_is_free)
 749     {
 750       e = mheap_prev_elt (e);
 751       remove_free_elt2 (v, e);
 752     }
 753
 754   if (e->prev_n_user_data == MHEAP_N_USER_DATA_INVALID)
 755     {
 756       if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 757         mheap_vm_elt (v, MHEAP_VM_UNMAP, mheap_elt_uoffset (v, e));
 758       _vec_len (v) = 0;
 759     }
 760   else
 761     {
 762       uword uo = mheap_elt_uoffset (v, e);
 763       if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 764         mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
 765       e->n_user_data = MHEAP_N_USER_DATA_INVALID;
 766       _vec_len (v) = uo;
 767     }
 768 }
 769
 770 void
 771 mheap_put (void *v, uword uoffset)
 772 {
 773   mheap_t *h;
 774   uword n_user_data_bytes, bin;
 775   mheap_elt_t *e, *n;
 776   uword trace_uoffset, trace_n_user_data_bytes;
 777   u64 cpu_times[2];
 778
 779   cpu_times[0] = clib_cpu_time_now ();
 780
 781   h = mheap_header (v);
 782
 783   mheap_maybe_lock (v);
 784
 785   if (h->flags & MHEAP_FLAG_VALIDATE)
 786     mheap_validate (v);
 787
 788   ASSERT (h->n_elts > 0);
 789   h->n_elts--;
 790   h->stats.n_puts += 1;
 791
 792   e = mheap_elt_at_uoffset (v, uoffset);
 793   n = mheap_next_elt (e);
 794   n_user_data_bytes = mheap_elt_data_bytes (e);
 795
 796   trace_uoffset = uoffset;
 797   trace_n_user_data_bytes = n_user_data_bytes;
 798
 799   bin = user_data_size_to_bin_index (n_user_data_bytes);
 800   if (MHEAP_HAVE_SMALL_OBJECT_CACHE
 801       && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
 802     {
 803       uoffset = mheap_put_small_object (h, bin, uoffset);
 804       if (uoffset == 0)
 805         goto done;
 806
 807       e = mheap_elt_at_uoffset (v, uoffset);
 808       n = mheap_next_elt (e);
 809       n_user_data_bytes = mheap_elt_data_bytes (e);
 810     }
 811
 812   /* Assert that forward and back pointers are equal. */
 813   if (e->n_user_data != n->prev_n_user_data)
 814     os_panic ();
 815
 816   /* Forward and backwards is_free must agree. */
 817   if (e->is_free != n->prev_is_free)
 818     os_panic ();
 819
 820   /* Object was already freed. */
 821   if (e->is_free)
 822     os_panic ();
 823
 824   /* Special case: delete last element in heap. */
 825   if (n->n_user_data == MHEAP_N_USER_DATA_INVALID)
 826     free_last_elt (v, e);
 827
 828   else
 829     {
 830       uword f0, f1, n_combine;
 831
 832       f0 = uoffset;
 833       f1 = f0 + n_user_data_bytes;
 834       n_combine = 0;
 835
 836       if (e->prev_is_free)
 837         {
 838           mheap_elt_t *p = mheap_prev_elt (e);
 839           f0 = mheap_elt_uoffset (v, p);
 840           remove_free_elt2 (v, p);
 841           n_combine++;
 842         }
 843
 844       if (n->is_free)
 845         {
 846           mheap_elt_t *m = mheap_next_elt (n);
 847           f1 = (void *) m - v;
 848           remove_free_elt2 (v, n);
 849           n_combine++;
 850         }
 851
 852       if (n_combine)
 853         mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
 854       else
 855         e->is_free = n->prev_is_free = 1;
 856       set_free_elt (v, f0, f1 - f0);
 857
 858       if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 859         mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
 860     }
 861
 862 done:
 863   h = mheap_header (v);
 864
 865   if (h->flags & MHEAP_FLAG_TRACE)
 866     {
 867       /* Recursion block for case when we are traceing main clib heap. */
 868       h->flags &= ~MHEAP_FLAG_TRACE;
 869
 870       mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
 871
 872       h->flags |= MHEAP_FLAG_TRACE;
 873     }
 874
 875   if (h->flags & MHEAP_FLAG_VALIDATE)
 876     mheap_validate (v);
 877
 878   mheap_maybe_unlock (v);
 879
 880   cpu_times[1] = clib_cpu_time_now ();
 881   h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
 882 }
 883
 884 void *
 885 mheap_alloc_with_flags (void *memory, uword memory_size, uword flags)
 886 {
 887   mheap_t *h;
 888   void *v;
 889   uword size;
 890
 891   if (!mheap_page_size)
 892     mheap_page_size = clib_mem_get_page_size ();
 893
 894   if (!memory)
 895     {
 896       /* No memory given, try to VM allocate some. */
 897       memory = clib_mem_vm_alloc (memory_size);
 898       if (!memory)
 899         return 0;
 900
 901       /* No memory region implies we have virtual memory. */
 902       flags &= ~MHEAP_FLAG_DISABLE_VM;
 903     }
 904
 905   /* Make sure that given memory is page aligned. */
 906   {
 907     uword am, av, ah;
 908
 909     am = pointer_to_uword (memory);
 910     av = mheap_page_round (am);
 911     v = uword_to_pointer (av, void *);
 912     h = mheap_header (v);
 913     ah = pointer_to_uword (h);
 914     while (ah < am)
 915       ah += mheap_page_size;
 916
 917     h = uword_to_pointer (ah, void *);
 918     v = mheap_vector (h);
 919
 920     if (PREDICT_FALSE (memory + memory_size < v))
 921       {
 922         /*
 923          * This will happen when the requested memory_size is too
 924          * small to cope with the heap header and/or memory alignment.
 925          */
 926         clib_mem_vm_free (memory, memory_size);
 927         return 0;
 928       }
 929
 930     size = memory + memory_size - v;
 931   }
 932
 933   /* VM map header so we can use memory. */
 934   if (!(flags & MHEAP_FLAG_DISABLE_VM))
 935     clib_mem_vm_map (h, sizeof (h[0]));
 936
 937   /* Zero vector header: both heap header and vector length. */
 938   memset (h, 0, sizeof (h[0]));
 939   _vec_len (v) = 0;
 940
 941   h->vm_alloc_offset_from_header = (void *) h - memory;
 942   h->vm_alloc_size = memory_size;
 943
 944   h->max_size = size;
 945   h->owner_cpu = ~0;
 946
 947   /* Set flags based on those given less builtin-flags. */
 948   h->flags |= (flags & ~MHEAP_FLAG_TRACE);
 949
 950   /* Unmap remainder of heap until we will be ready to use it. */
 951   if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 952     mheap_vm (v, MHEAP_VM_UNMAP | MHEAP_VM_ROUND_UP,
 953               (clib_address_t) v, h->max_size);
 954
 955   /* Initialize free list heads to empty. */
 956   memset (h->first_free_elt_uoffset_by_bin, 0xFF,
 957           sizeof (h->first_free_elt_uoffset_by_bin));
 958
 959   return v;
 960 }
 961
 962 void *
 963 mheap_alloc (void *memory, uword size)
 964 {
 965   uword flags = 0;
 966
 967   if (memory != 0)
 968     flags |= MHEAP_FLAG_DISABLE_VM;
 969
 970 #ifdef CLIB_HAVE_VEC128
 971   flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
 972 #endif
 973
 974   return mheap_alloc_with_flags (memory, size, flags);
 975 }
 976
 977 void *
 978 _mheap_free (void *v)
 979 {
 980   mheap_t *h = mheap_header (v);
 981
 982   if (v)
 983     clib_mem_vm_free ((void *) h - h->vm_alloc_offset_from_header,
 984                       h->vm_alloc_size);
 985
 986   return 0;
 987 }
 988
 989 /* Call user's function with each object in heap. */
 990 void
 991 mheap_foreach (void *v,
 992                uword (*func) (void *arg, void *v, void *elt_data,
 993                               uword elt_size), void *arg)
 994 {
 995   mheap_elt_t *e;
 996   u8 *stack_heap, *clib_mem_mheap_save;
 997   u8 tmp_heap_memory[16 * 1024];
 998
 999   mheap_maybe_lock (v);
1000
1001   if (vec_len (v) == 0)
1002     goto done;
1003
1004   clib_mem_mheap_save = 0;
1005   stack_heap = 0;
1006
1007   /* Allocate a new temporary heap on the stack.
1008      This is so that our hash table & user's callback function can
1009      themselves allocate memory somewhere without getting in the way
1010      of the heap we are looking at. */
1011   if (v == clib_mem_get_heap ())
1012     {
1013       stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
1014       clib_mem_mheap_save = v;
1015       clib_mem_set_heap (stack_heap);
1016     }
1017
1018   for (e = v;
1019        e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = mheap_next_elt (e))
1020     {
1021       void *p = mheap_elt_data (v, e);
1022       if (e->is_free)
1023         continue;
1024       if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
1025         break;
1026     }
1027
1028   /* Restore main CLIB heap. */
1029   if (clib_mem_mheap_save)
1030     clib_mem_set_heap (clib_mem_mheap_save);
1031
1032 done:
1033   mheap_maybe_unlock (v);
1034 }
1035
1036 /* Bytes in mheap header overhead not including data bytes. */
1037 always_inline uword
1038 mheap_bytes_overhead (void *v)
1039 {
1040   mheap_t *h = mheap_header (v);
1041   return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
1042 }
1043
1044 /* Total number of bytes including both data and overhead. */
1045 uword
1046 mheap_bytes (void *v)
1047 {
1048   return mheap_bytes_overhead (v) + vec_bytes (v);
1049 }
1050
1051 static void
1052 mheap_usage_no_lock (void *v, clib_mem_usage_t * usage)
1053 {
1054   mheap_t *h = mheap_header (v);
1055   uword used = 0, free = 0, free_vm_unmapped = 0;
1056
1057   if (vec_len (v) > 0)
1058     {
1059       mheap_elt_t *e;
1060
1061       for (e = v;
1062            e->n_user_data != MHEAP_N_USER_DATA_INVALID;
1063            e = mheap_next_elt (e))
1064         {
1065           uword size = mheap_elt_data_bytes (e);
1066           if (e->is_free)
1067             {
1068               free += size;
1069               if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
1070                 free_vm_unmapped +=
1071                   mheap_vm_elt (v, MHEAP_VM_NOMAP, mheap_elt_uoffset (v, e));
1072             }
1073           else
1074             used += size;
1075         }
1076     }
1077
1078   usage->object_count = mheap_elts (v);
1079   usage->bytes_total = mheap_bytes (v);
1080   usage->bytes_overhead = mheap_bytes_overhead (v);
1081   usage->bytes_max = mheap_max_size (v);
1082   usage->bytes_used = used;
1083   usage->bytes_free = free;
1084   usage->bytes_free_reclaimed = free_vm_unmapped;
1085 }
1086
1087 void
1088 mheap_usage (void *v, clib_mem_usage_t * usage)
1089 {
1090   mheap_maybe_lock (v);
1091   mheap_usage_no_lock (v, usage);
1092   mheap_maybe_unlock (v);
1093 }
1094
1095 static u8 *
1096 format_mheap_byte_count (u8 * s, va_list * va)
1097 {
1098   uword n_bytes = va_arg (*va, uword);
1099   if (n_bytes < 1024)
1100     return format (s, "%wd", n_bytes);
1101   else
1102     return format (s, "%wdk", n_bytes / 1024);
1103 }
1104
1105 /* Returns first corrupt heap element. */
1106 static mheap_elt_t *
1107 mheap_first_corrupt (void *v)
1108 {
1109   mheap_elt_t *e, *n;
1110
1111   if (vec_len (v) == 0)
1112     return 0;
1113
1114   e = v;
1115   while (1)
1116     {
1117       if (e->n_user_data == MHEAP_N_USER_DATA_INVALID)
1118         break;
1119
1120       n = mheap_next_elt (e);
1121
1122       if (e->n_user_data != n->prev_n_user_data)
1123         return e;
1124
1125       if (e->is_free != n->prev_is_free)
1126         return e;
1127
1128       e = n;
1129     }
1130
1131   return 0;
1132 }
1133
1134 static u8 *
1135 format_mheap_stats (u8 * s, va_list * va)
1136 {
1137   mheap_t *h = va_arg (*va, mheap_t *);
1138   mheap_stats_t *st = &h->stats;
1139   u32 indent = format_get_indent (s);
1140
1141   s =
1142     format (s,
1143             "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1144             st->n_small_object_cache_hits, st->n_small_object_cache_attempts,
1145             (st->n_small_object_cache_attempts !=
1146              0 ? 100. * (f64) st->n_small_object_cache_hits /
1147              (f64) st->n_small_object_cache_attempts : 0.),
1148             h->small_object_cache.replacement_index);
1149
1150   s =
1151     format (s,
1152             "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1153             format_white_space, indent, st->free_list.n_search_attempts,
1154             st->free_list.n_objects_found,
1155             (st->free_list.n_search_attempts !=
1156              0 ? 100. * (f64) st->free_list.n_objects_found /
1157              (f64) st->free_list.n_search_attempts : 0.),
1158             st->free_list.n_objects_searched,
1159             (st->free_list.n_search_attempts !=
1160              0 ? (f64) st->free_list.n_objects_searched /
1161              (f64) st->free_list.n_search_attempts : 0.));
1162
1163   s = format (s, "\n%Ualloc. from vector-expand: %Ld",
1164               format_white_space, indent, st->n_vector_expands);
1165
1166   s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1167               format_white_space, indent,
1168               st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
1169
1170   s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1171               format_white_space, indent,
1172               st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
1173
1174   return s;
1175 }
1176
1177 u8 *
1178 format_mheap (u8 * s, va_list * va)
1179 {
1180   void *v = va_arg (*va, u8 *);
1181   int verbose = va_arg (*va, int);
1182
1183   mheap_t *h;
1184   uword i, size;
1185   u32 indent;
1186   clib_mem_usage_t usage;
1187   mheap_elt_t *first_corrupt;
1188
1189   mheap_maybe_lock (v);
1190
1191   h = mheap_header (v);
1192
1193   mheap_usage_no_lock (v, &usage);
1194
1195   indent = format_get_indent (s);
1196
1197   s =
1198     format (s,
1199             "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1200             usage.object_count, format_mheap_byte_count, usage.bytes_used,
1201             format_mheap_byte_count, usage.bytes_total,
1202             format_mheap_byte_count, usage.bytes_free,
1203             format_mheap_byte_count, usage.bytes_free_reclaimed,
1204             format_mheap_byte_count, usage.bytes_overhead);
1205
1206   if (usage.bytes_max != ~0)
1207     s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
1208
1209   /* Show histogram of sizes. */
1210   if (verbose > 1)
1211     {
1212       uword hist[MHEAP_N_BINS];
1213       mheap_elt_t *e;
1214       uword i, n_hist;
1215
1216       memset (hist, 0, sizeof (hist));
1217
1218       n_hist = 0;
1219       for (e = v;
1220            e->n_user_data != MHEAP_N_USER_DATA_INVALID;
1221            e = mheap_next_elt (e))
1222         {
1223           uword n_user_data_bytes = mheap_elt_data_bytes (e);
1224           uword bin = user_data_size_to_bin_index (n_user_data_bytes);
1225           if (!e->is_free)
1226             {
1227               hist[bin] += 1;
1228               n_hist += 1;
1229             }
1230         }
1231
1232       s = format (s, "\n%U%=12s%=12s%=16s",
1233                   format_white_space, indent + 2,
1234                   "Size", "Count", "Fraction");
1235
1236       for (i = 0; i < ARRAY_LEN (hist); i++)
1237         {
1238           if (hist[i] == 0)
1239             continue;
1240           s = format (s, "\n%U%12d%12wd%16.4f",
1241                       format_white_space, indent + 2,
1242                       MHEAP_MIN_USER_DATA_BYTES +
1243                       i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
1244                       (f64) hist[i] / (f64) n_hist);
1245         }
1246     }
1247
1248   if (verbose)
1249     s = format (s, "\n%U%U",
1250                 format_white_space, indent + 2, format_mheap_stats, h);
1251
1252   if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
1253     {
1254       /* Make a copy of traces since we'll be sorting them. */
1255       mheap_trace_t *t, *traces_copy;
1256       u32 indent, total_objects_traced;
1257
1258       traces_copy = vec_dup (h->trace_main.traces);
1259       qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
1260              mheap_trace_sort);
1261
1262       total_objects_traced = 0;
1263       s = format (s, "\n");
1264       vec_foreach (t, traces_copy)
1265       {
1266         /* Skip over free elements. */
1267         if (t->n_allocations == 0)
1268           continue;
1269
1270         total_objects_traced += t->n_allocations;
1271
1272         /* When not verbose only report allocations of more than 1k. */
1273         if (!verbose && t->n_bytes < 1024)
1274           continue;
1275
1276         if (t == traces_copy)
1277           s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
1278                       "Sample");
1279         s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
1280                     t->offset + v);
1281         indent = format_get_indent (s);
1282         for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
1283           {
1284             if (i > 0)
1285               s = format (s, "%U", format_white_space, indent);
1286 #ifdef CLIB_UNIX
1287             s =
1288               format (s, " %U\n", format_clib_elf_symbol_with_address,
1289                       t->callers[i]);
1290 #else
1291             s = format (s, " %p\n", t->callers[i]);
1292 #endif
1293           }
1294       }
1295
1296       s = format (s, "%d total traced objects\n", total_objects_traced);
1297
1298       vec_free (traces_copy);
1299     }
1300
1301   first_corrupt = mheap_first_corrupt (v);
1302   if (first_corrupt)
1303     {
1304       size = mheap_elt_data_bytes (first_corrupt);
1305       s = format (s, "\n  first corrupt object: %p, size %wd\n  %U",
1306                   first_corrupt, size, format_hex_bytes, first_corrupt, size);
1307     }
1308
1309   /* FIXME.  This output could be wrong in the unlikely case that format
1310      uses the same mheap as we are currently inspecting. */
1311   if (verbose > 1)
1312     {
1313       mheap_elt_t *e;
1314       uword i, o;
1315
1316       s = format (s, "\n");
1317
1318       e = mheap_elt_at_uoffset (v, 0);
1319       i = 0;
1320       while (1)
1321         {
1322           if ((i % 8) == 0)
1323             s = format (s, "%8d: ", i);
1324
1325           o = mheap_elt_uoffset (v, e);
1326
1327           if (e->is_free)
1328             s = format (s, "(%8d) ", o);
1329           else
1330             s = format (s, " %8d  ", o);
1331
1332           if ((i % 8) == 7 || (i + 1) >= h->n_elts)
1333             s = format (s, "\n");
1334         }
1335     }
1336
1337   mheap_maybe_unlock (v);
1338
1339   return s;
1340 }
1341
1342 void
1343 dmh (void *v)
1344 {
1345   fformat (stderr, "%U", format_mheap, v, 1);
1346 }
1347
1348 static void
1349 mheap_validate_breakpoint ()
1350 {
1351   os_panic ();
1352 }
1353
1354 void
1355 mheap_validate (void *v)
1356 {
1357   mheap_t *h = mheap_header (v);
1358   uword i, s;
1359
1360   uword elt_count, elt_size;
1361   uword free_count_from_free_lists, free_size_from_free_lists;
1362   uword small_elt_free_count, small_elt_free_size;
1363
1364 #define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
1365
1366   if (vec_len (v) == 0)
1367     return;
1368
1369   mheap_maybe_lock (v);
1370
1371   /* Validate number of elements and size. */
1372   free_size_from_free_lists = free_count_from_free_lists = 0;
1373   for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
1374     {
1375       mheap_elt_t *e, *n;
1376       uword is_first;
1377
1378       CHECK ((h->first_free_elt_uoffset_by_bin[i] != MHEAP_GROUNDED)
1379              ==
1380              ((h->non_empty_free_elt_heads[i /
1381                                            BITS (uword)] & ((uword) 1 <<
1382                                                             (uword) (i %
1383                                                                      BITS
1384                                                                      (uword))))
1385               != 0));
1386
1387       if (h->first_free_elt_uoffset_by_bin[i] == MHEAP_GROUNDED)
1388         continue;
1389
1390       e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[i]);
1391       is_first = 1;
1392       while (1)
1393         {
1394           uword s;
1395
1396           n = mheap_next_elt (e);
1397
1398           /* Object must be marked free. */
1399           CHECK (e->is_free);
1400
1401           /* Next object's previous free bit must also be set. */
1402           CHECK (n->prev_is_free);
1403
1404           if (is_first)
1405             CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
1406           is_first = 0;
1407
1408           s = mheap_elt_data_bytes (e);
1409           CHECK (user_data_size_to_bin_index (s) == i);
1410
1411           free_count_from_free_lists += 1;
1412           free_size_from_free_lists += s;
1413
1414           if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
1415             break;
1416
1417           n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
1418
1419           /* Check free element linkages. */
1420           CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
1421
1422           e = n;
1423         }
1424     }
1425
1426   /* Go through small object cache. */
1427   small_elt_free_count = small_elt_free_size = 0;
1428   for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
1429     {
1430       if (h->small_object_cache.bins.as_u8[i] != 0)
1431         {
1432           mheap_elt_t *e;
1433           uword b = h->small_object_cache.bins.as_u8[i] - 1;
1434           uword o = h->small_object_cache.offsets[i];
1435           uword s;
1436
1437           e = mheap_elt_at_uoffset (v, o);
1438
1439           /* Object must be allocated. */
1440           CHECK (!e->is_free);
1441
1442           s = mheap_elt_data_bytes (e);
1443           CHECK (user_data_size_to_bin_index (s) == b);
1444
1445           small_elt_free_count += 1;
1446           small_elt_free_size += s;
1447         }
1448     }
1449
1450   {
1451     mheap_elt_t *e, *n;
1452     uword elt_free_size, elt_free_count;
1453
1454     elt_count = elt_size = elt_free_size = elt_free_count = 0;
1455     for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
1456       {
1457         if (e->prev_n_user_data != MHEAP_N_USER_DATA_INVALID)
1458           CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
1459                  MHEAP_MIN_USER_DATA_BYTES);
1460
1461         CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
1462                MHEAP_MIN_USER_DATA_BYTES);
1463
1464         n = mheap_next_elt (e);
1465
1466         CHECK (e->is_free == n->prev_is_free);
1467
1468         elt_count++;
1469         s = mheap_elt_data_bytes (e);
1470         elt_size += s;
1471
1472         if (e->is_free)
1473           {
1474             elt_free_count++;
1475             elt_free_size += s;
1476           }
1477
1478         /* Consecutive free objects should have been combined. */
1479         CHECK (!(e->prev_is_free && n->prev_is_free));
1480       }
1481
1482     CHECK (free_count_from_free_lists == elt_free_count);
1483     CHECK (free_size_from_free_lists == elt_free_size);
1484     CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
1485     CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
1486            vec_len (v));
1487   }
1488
1489   {
1490     mheap_elt_t *e, *n;
1491
1492     for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
1493       {
1494         n = mheap_next_elt (e);
1495         CHECK (e->n_user_data == n->prev_n_user_data);
1496       }
1497   }
1498
1499 #undef CHECK
1500
1501   mheap_maybe_unlock (v);
1502
1503   h->validate_serial += 1;
1504 }
1505
1506 static void
1507 mheap_get_trace (void *v, uword offset, uword size)
1508 {
1509   mheap_t *h;
1510   mheap_trace_main_t *tm;
1511   mheap_trace_t *t;
1512   uword i, n_callers, trace_index, *p;
1513   mheap_trace_t trace;
1514
1515   /* Spurious Coverity warnings be gone. */
1516   memset (&trace, 0, sizeof (trace));
1517
1518   n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1519                               /* Skip mheap_get_aligned's frame */ 1);
1520   if (n_callers == 0)
1521     return;
1522
1523   for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
1524     trace.callers[i] = 0;
1525
1526   h = mheap_header (v);
1527   tm = &h->trace_main;
1528
1529   if (!tm->trace_by_callers)
1530     tm->trace_by_callers =
1531       hash_create_shmem (0, sizeof (trace.callers), sizeof (uword));
1532
1533   p = hash_get_mem (tm->trace_by_callers, &trace.callers);
1534   if (p)
1535     {
1536       trace_index = p[0];
1537       t = tm->traces + trace_index;
1538     }
1539   else
1540     {
1541       i = vec_len (tm->trace_free_list);
1542       if (i > 0)
1543         {
1544           trace_index = tm->trace_free_list[i - 1];
1545           _vec_len (tm->trace_free_list) = i - 1;
1546         }
1547       else
1548         {
1549           mheap_trace_t *old_start = tm->traces;
1550           mheap_trace_t *old_end = vec_end (tm->traces);
1551
1552           vec_add2 (tm->traces, t, 1);
1553
1554           if (tm->traces != old_start)
1555             {
1556               hash_pair_t *p;
1557               mheap_trace_t *q;
1558             /* *INDENT-OFF* */
1559             hash_foreach_pair (p, tm->trace_by_callers,
1560             ({
1561               q = uword_to_pointer (p->key, mheap_trace_t *);
1562               ASSERT (q >= old_start && q < old_end);
1563               p->key = pointer_to_uword (tm->traces + (q - old_start));
1564             }));
1565             /* *INDENT-ON* */
1566             }
1567           trace_index = t - tm->traces;
1568         }
1569
1570       t = tm->traces + trace_index;
1571       t[0] = trace;
1572       t->n_allocations = 0;
1573       t->n_bytes = 0;
1574       hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
1575     }
1576
1577   t->n_allocations += 1;
1578   t->n_bytes += size;
1579   t->offset = offset;           /* keep a sample to autopsy */
1580   hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1581 }
1582
1583 static void
1584 mheap_put_trace (void *v, uword offset, uword size)
1585 {
1586   mheap_t *h;
1587   mheap_trace_main_t *tm;
1588   mheap_trace_t *t;
1589   uword trace_index, *p;
1590
1591   h = mheap_header (v);
1592   tm = &h->trace_main;
1593   p = hash_get (tm->trace_index_by_offset, offset);
1594   if (!p)
1595     return;
1596
1597   trace_index = p[0];
1598   hash_unset (tm->trace_index_by_offset, offset);
1599   ASSERT (trace_index < vec_len (tm->traces));
1600
1601   t = tm->traces + trace_index;
1602   ASSERT (t->n_allocations > 0);
1603   ASSERT (t->n_bytes >= size);
1604   t->n_allocations -= 1;
1605   t->n_bytes -= size;
1606   if (t->n_allocations == 0)
1607     {
1608       hash_unset_mem (tm->trace_by_callers, t->callers);
1609       vec_add1 (tm->trace_free_list, trace_index);
1610       memset (t, 0, sizeof (t[0]));
1611     }
1612 }
1613
1614 static int
1615 mheap_trace_sort (const void *_t1, const void *_t2)
1616 {
1617   const mheap_trace_t *t1 = _t1;
1618   const mheap_trace_t *t2 = _t2;
1619   word cmp;
1620
1621   cmp = (word) t2->n_bytes - (word) t1->n_bytes;
1622   if (!cmp)
1623     cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1624   return cmp;
1625 }
1626
1627 always_inline void
1628 mheap_trace_main_free (mheap_trace_main_t * tm)
1629 {
1630   vec_free (tm->traces);
1631   vec_free (tm->trace_free_list);
1632   hash_free (tm->trace_by_callers);
1633   hash_free (tm->trace_index_by_offset);
1634 }
1635
1636 void
1637 mheap_trace (void *v, int enable)
1638 {
1639   mheap_t *h;
1640
1641   h = mheap_header (v);
1642
1643   if (enable)
1644     {
1645       h->flags |= MHEAP_FLAG_TRACE;
1646     }
1647   else
1648     {
1649       mheap_trace_main_free (&h->trace_main);
1650       h->flags &= ~MHEAP_FLAG_TRACE;
1651     }
1652 }
1653
1654 /*
1655  * fd.io coding-style-patch-verification: ON
1656  *
1657  * Local Variables:
1658  * eval: (c-set-style "gnu")
1659  * End:
1660  */