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