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 (u8x16_is_equal (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   /* Round requested size. */
 667   n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
 668   n_user_data_bytes =
 669     round_pow2 (n_user_data_bytes,
 670                 STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
 671
 672   if (!v)
 673     v = mheap_alloc (0, 64 << 20);
 674
 675   mheap_maybe_lock (v);
 676
 677   h = mheap_header (v);
 678
 679   if (h->flags & MHEAP_FLAG_VALIDATE)
 680     mheap_validate (v);
 681
 682   /* First search free lists for object. */
 683   offset =
 684     mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);
 685
 686   h = mheap_header (v);
 687
 688   /* If that fails allocate object at end of heap by extending vector. */
 689   if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
 690     {
 691       v =
 692         mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
 693                                  &offset);
 694       h = mheap_header (v);
 695       h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
 696     }
 697
 698   *offset_return = offset;
 699   if (offset != MHEAP_GROUNDED)
 700     {
 701       h->n_elts += 1;
 702
 703       if (h->flags & MHEAP_FLAG_TRACE)
 704         {
 705           /* Recursion block for case when we are traceing main clib heap. */
 706           h->flags &= ~MHEAP_FLAG_TRACE;
 707
 708           mheap_get_trace (v, offset, n_user_data_bytes);
 709
 710           h->flags |= MHEAP_FLAG_TRACE;
 711         }
 712     }
 713
 714   if (h->flags & MHEAP_FLAG_VALIDATE)
 715     mheap_validate (v);
 716
 717   mheap_maybe_unlock (v);
 718
 719   cpu_times[1] = clib_cpu_time_now ();
 720   h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
 721   h->stats.n_gets += 1;
 722
 723   return v;
 724 }
 725
 726 static void
 727 free_last_elt (void *v, mheap_elt_t * e)
 728 {
 729   mheap_t *h = mheap_header (v);
 730
 731   /* Possibly delete preceeding free element also. */
 732   if (e->prev_is_free)
 733     {
 734       e = mheap_prev_elt (e);
 735       remove_free_elt2 (v, e);
 736     }
 737
 738   if (e->prev_n_user_data == MHEAP_N_USER_DATA_INVALID)
 739     {
 740       if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 741         mheap_vm_elt (v, MHEAP_VM_UNMAP, mheap_elt_uoffset (v, e));
 742       _vec_len (v) = 0;
 743     }
 744   else
 745     {
 746       uword uo = mheap_elt_uoffset (v, e);
 747       if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 748         mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
 749       e->n_user_data = MHEAP_N_USER_DATA_INVALID;
 750       _vec_len (v) = uo;
 751     }
 752 }
 753
 754 void
 755 mheap_put (void *v, uword uoffset)
 756 {
 757   mheap_t *h;
 758   uword n_user_data_bytes, bin;
 759   mheap_elt_t *e, *n;
 760   uword trace_uoffset, trace_n_user_data_bytes;
 761   u64 cpu_times[2];
 762
 763   cpu_times[0] = clib_cpu_time_now ();
 764
 765   h = mheap_header (v);
 766
 767   mheap_maybe_lock (v);
 768
 769   if (h->flags & MHEAP_FLAG_VALIDATE)
 770     mheap_validate (v);
 771
 772   ASSERT (h->n_elts > 0);
 773   h->n_elts--;
 774   h->stats.n_puts += 1;
 775
 776   e = mheap_elt_at_uoffset (v, uoffset);
 777   n = mheap_next_elt (e);
 778   n_user_data_bytes = mheap_elt_data_bytes (e);
 779
 780   trace_uoffset = uoffset;
 781   trace_n_user_data_bytes = n_user_data_bytes;
 782
 783   bin = user_data_size_to_bin_index (n_user_data_bytes);
 784   if (MHEAP_HAVE_SMALL_OBJECT_CACHE
 785       && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
 786     {
 787       uoffset = mheap_put_small_object (h, bin, uoffset);
 788       if (uoffset == 0)
 789         goto done;
 790
 791       e = mheap_elt_at_uoffset (v, uoffset);
 792       n = mheap_next_elt (e);
 793       n_user_data_bytes = mheap_elt_data_bytes (e);
 794     }
 795
 796   /* Assert that forward and back pointers are equal. */
 797   if (e->n_user_data != n->prev_n_user_data)
 798     os_panic ();
 799
 800   /* Forward and backwards is_free must agree. */
 801   if (e->is_free != n->prev_is_free)
 802     os_panic ();
 803
 804   /* Object was already freed. */
 805   if (e->is_free)
 806     os_panic ();
 807
 808   /* Special case: delete last element in heap. */
 809   if (n->n_user_data == MHEAP_N_USER_DATA_INVALID)
 810     free_last_elt (v, e);
 811
 812   else
 813     {
 814       uword f0, f1, n_combine;
 815
 816       f0 = uoffset;
 817       f1 = f0 + n_user_data_bytes;
 818       n_combine = 0;
 819
 820       if (e->prev_is_free)
 821         {
 822           mheap_elt_t *p = mheap_prev_elt (e);
 823           f0 = mheap_elt_uoffset (v, p);
 824           remove_free_elt2 (v, p);
 825           n_combine++;
 826         }
 827
 828       if (n->is_free)
 829         {
 830           mheap_elt_t *m = mheap_next_elt (n);
 831           f1 = (void *) m - v;
 832           remove_free_elt2 (v, n);
 833           n_combine++;
 834         }
 835
 836       if (n_combine)
 837         mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
 838       else
 839         e->is_free = n->prev_is_free = 1;
 840       set_free_elt (v, f0, f1 - f0);
 841
 842       if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 843         mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
 844     }
 845
 846 done:
 847   h = mheap_header (v);
 848
 849   if (h->flags & MHEAP_FLAG_TRACE)
 850     {
 851       /* Recursion block for case when we are traceing main clib heap. */
 852       h->flags &= ~MHEAP_FLAG_TRACE;
 853
 854       mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);
 855
 856       h->flags |= MHEAP_FLAG_TRACE;
 857     }
 858
 859   if (h->flags & MHEAP_FLAG_VALIDATE)
 860     mheap_validate (v);
 861
 862   mheap_maybe_unlock (v);
 863
 864   cpu_times[1] = clib_cpu_time_now ();
 865   h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
 866 }
 867
 868 void *
 869 mheap_alloc_with_flags (void *memory, uword memory_size, uword flags)
 870 {
 871   mheap_t *h;
 872   void *v;
 873   uword size;
 874
 875   if (!mheap_page_size)
 876     mheap_page_size = clib_mem_get_page_size ();
 877
 878   if (!memory)
 879     {
 880       /* No memory given, try to VM allocate some. */
 881       memory = clib_mem_vm_alloc (memory_size);
 882       if (!memory)
 883         return 0;
 884
 885       /* No memory region implies we have virtual memory. */
 886       flags &= ~MHEAP_FLAG_DISABLE_VM;
 887     }
 888
 889   /* Make sure that given memory is page aligned. */
 890   {
 891     uword am, av, ah;
 892
 893     am = pointer_to_uword (memory);
 894     av = mheap_page_round (am);
 895     v = uword_to_pointer (av, void *);
 896     h = mheap_header (v);
 897     ah = pointer_to_uword (h);
 898     while (ah < am)
 899       ah += mheap_page_size;
 900
 901     h = uword_to_pointer (ah, void *);
 902     v = mheap_vector (h);
 903
 904     if (PREDICT_FALSE (memory + memory_size < v))
 905       {
 906         /*
 907          * This will happen when the requested memory_size is too
 908          * small to cope with the heap header and/or memory alignment.
 909          */
 910         clib_mem_vm_free (memory, memory_size);
 911         return 0;
 912       }
 913
 914     size = memory + memory_size - v;
 915   }
 916
 917   /* VM map header so we can use memory. */
 918   if (!(flags & MHEAP_FLAG_DISABLE_VM))
 919     clib_mem_vm_map (h, sizeof (h[0]));
 920
 921   /* Zero vector header: both heap header and vector length. */
 922   memset (h, 0, sizeof (h[0]));
 923   _vec_len (v) = 0;
 924
 925   h->vm_alloc_offset_from_header = (void *) h - memory;
 926   h->vm_alloc_size = memory_size;
 927
 928   h->max_size = size;
 929   h->owner_cpu = ~0;
 930
 931   /* Set flags based on those given less builtin-flags. */
 932   h->flags |= (flags & ~MHEAP_FLAG_TRACE);
 933
 934   /* Unmap remainder of heap until we will be ready to use it. */
 935   if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
 936     mheap_vm (v, MHEAP_VM_UNMAP | MHEAP_VM_ROUND_UP,
 937               (clib_address_t) v, h->max_size);
 938
 939   /* Initialize free list heads to empty. */
 940   memset (h->first_free_elt_uoffset_by_bin, 0xFF,
 941           sizeof (h->first_free_elt_uoffset_by_bin));
 942
 943   return v;
 944 }
 945
 946 void *
 947 mheap_alloc (void *memory, uword size)
 948 {
 949   uword flags = 0;
 950
 951   if (memory != 0)
 952     flags |= MHEAP_FLAG_DISABLE_VM;
 953
 954 #ifdef CLIB_HAVE_VEC128
 955   flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
 956 #endif
 957
 958   return mheap_alloc_with_flags (memory, size, flags);
 959 }
 960
 961 void *
 962 _mheap_free (void *v)
 963 {
 964   mheap_t *h = mheap_header (v);
 965
 966   if (v)
 967     clib_mem_vm_free ((void *) h - h->vm_alloc_offset_from_header,
 968                       h->vm_alloc_size);
 969
 970   return 0;
 971 }
 972
 973 /* Call user's function with each object in heap. */
 974 void
 975 mheap_foreach (void *v,
 976                uword (*func) (void *arg, void *v, void *elt_data,
 977                               uword elt_size), void *arg)
 978 {
 979   mheap_elt_t *e;
 980   u8 *stack_heap, *clib_mem_mheap_save;
 981   u8 tmp_heap_memory[16 * 1024];
 982
 983   mheap_maybe_lock (v);
 984
 985   if (vec_len (v) == 0)
 986     goto done;
 987
 988   clib_mem_mheap_save = 0;
 989   stack_heap = 0;
 990
 991   /* Allocate a new temporary heap on the stack.
 992      This is so that our hash table & user's callback function can
 993      themselves allocate memory somewhere without getting in the way
 994      of the heap we are looking at. */
 995   if (v == clib_mem_get_heap ())
 996     {
 997       stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
 998       clib_mem_mheap_save = v;
 999       clib_mem_set_heap (stack_heap);
1000     }
1001
1002   for (e = v;
1003        e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = mheap_next_elt (e))
1004     {
1005       void *p = mheap_elt_data (v, e);
1006       if (e->is_free)
1007         continue;
1008       if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
1009         break;
1010     }
1011
1012   /* Restore main CLIB heap. */
1013   if (clib_mem_mheap_save)
1014     clib_mem_set_heap (clib_mem_mheap_save);
1015
1016 done:
1017   mheap_maybe_unlock (v);
1018 }
1019
1020 /* Bytes in mheap header overhead not including data bytes. */
1021 always_inline uword
1022 mheap_bytes_overhead (void *v)
1023 {
1024   mheap_t *h = mheap_header (v);
1025   return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
1026 }
1027
1028 /* Total number of bytes including both data and overhead. */
1029 uword
1030 mheap_bytes (void *v)
1031 {
1032   return mheap_bytes_overhead (v) + vec_bytes (v);
1033 }
1034
1035 static void
1036 mheap_usage_no_lock (void *v, clib_mem_usage_t * usage)
1037 {
1038   mheap_t *h = mheap_header (v);
1039   uword used = 0, free = 0, free_vm_unmapped = 0;
1040
1041   if (vec_len (v) > 0)
1042     {
1043       mheap_elt_t *e;
1044
1045       for (e = v;
1046            e->n_user_data != MHEAP_N_USER_DATA_INVALID;
1047            e = mheap_next_elt (e))
1048         {
1049           uword size = mheap_elt_data_bytes (e);
1050           if (e->is_free)
1051             {
1052               free += size;
1053               if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
1054                 free_vm_unmapped +=
1055                   mheap_vm_elt (v, MHEAP_VM_NOMAP, mheap_elt_uoffset (v, e));
1056             }
1057           else
1058             used += size;
1059         }
1060     }
1061
1062   usage->object_count = mheap_elts (v);
1063   usage->bytes_total = mheap_bytes (v);
1064   usage->bytes_overhead = mheap_bytes_overhead (v);
1065   usage->bytes_max = mheap_max_size (v);
1066   usage->bytes_used = used;
1067   usage->bytes_free = free;
1068   usage->bytes_free_reclaimed = free_vm_unmapped;
1069 }
1070
1071 void
1072 mheap_usage (void *v, clib_mem_usage_t * usage)
1073 {
1074   mheap_maybe_lock (v);
1075   mheap_usage_no_lock (v, usage);
1076   mheap_maybe_unlock (v);
1077 }
1078
1079 static u8 *
1080 format_mheap_byte_count (u8 * s, va_list * va)
1081 {
1082   uword n_bytes = va_arg (*va, uword);
1083   if (n_bytes < 1024)
1084     return format (s, "%wd", n_bytes);
1085   else
1086     return format (s, "%wdk", n_bytes / 1024);
1087 }
1088
1089 /* Returns first corrupt heap element. */
1090 static mheap_elt_t *
1091 mheap_first_corrupt (void *v)
1092 {
1093   mheap_elt_t *e, *n;
1094
1095   if (vec_len (v) == 0)
1096     return 0;
1097
1098   e = v;
1099   while (1)
1100     {
1101       if (e->n_user_data == MHEAP_N_USER_DATA_INVALID)
1102         break;
1103
1104       n = mheap_next_elt (e);
1105
1106       if (e->n_user_data != n->prev_n_user_data)
1107         return e;
1108
1109       if (e->is_free != n->prev_is_free)
1110         return e;
1111
1112       e = n;
1113     }
1114
1115   return 0;
1116 }
1117
1118 static u8 *
1119 format_mheap_stats (u8 * s, va_list * va)
1120 {
1121   mheap_t *h = va_arg (*va, mheap_t *);
1122   mheap_stats_t *st = &h->stats;
1123   u32 indent = format_get_indent (s);
1124
1125   s =
1126     format (s,
1127             "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
1128             st->n_small_object_cache_hits, st->n_small_object_cache_attempts,
1129             (st->n_small_object_cache_attempts !=
1130              0 ? 100. * (f64) st->n_small_object_cache_hits /
1131              (f64) st->n_small_object_cache_attempts : 0.),
1132             h->small_object_cache.replacement_index);
1133
1134   s =
1135     format (s,
1136             "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
1137             format_white_space, indent, st->free_list.n_search_attempts,
1138             st->free_list.n_objects_found,
1139             (st->free_list.n_search_attempts !=
1140              0 ? 100. * (f64) st->free_list.n_objects_found /
1141              (f64) st->free_list.n_search_attempts : 0.),
1142             st->free_list.n_objects_searched,
1143             (st->free_list.n_search_attempts !=
1144              0 ? (f64) st->free_list.n_objects_searched /
1145              (f64) st->free_list.n_search_attempts : 0.));
1146
1147   s = format (s, "\n%Ualloc. from vector-expand: %Ld",
1148               format_white_space, indent, st->n_vector_expands);
1149
1150   s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
1151               format_white_space, indent,
1152               st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);
1153
1154   s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
1155               format_white_space, indent,
1156               st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);
1157
1158   return s;
1159 }
1160
1161 u8 *
1162 format_mheap (u8 * s, va_list * va)
1163 {
1164   void *v = va_arg (*va, u8 *);
1165   int verbose = va_arg (*va, int);
1166
1167   mheap_t *h;
1168   uword i, size, indent;
1169   clib_mem_usage_t usage;
1170   mheap_elt_t *first_corrupt;
1171
1172   mheap_maybe_lock (v);
1173
1174   h = mheap_header (v);
1175
1176   mheap_usage_no_lock (v, &usage);
1177
1178   indent = format_get_indent (s);
1179
1180   s =
1181     format (s,
1182             "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
1183             usage.object_count, format_mheap_byte_count, usage.bytes_used,
1184             format_mheap_byte_count, usage.bytes_total,
1185             format_mheap_byte_count, usage.bytes_free,
1186             format_mheap_byte_count, usage.bytes_free_reclaimed,
1187             format_mheap_byte_count, usage.bytes_overhead);
1188
1189   if (usage.bytes_max != ~0)
1190     s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);
1191
1192   /* Show histogram of sizes. */
1193   if (verbose > 1)
1194     {
1195       uword hist[MHEAP_N_BINS];
1196       mheap_elt_t *e;
1197       uword i, n_hist;
1198
1199       memset (hist, 0, sizeof (hist));
1200
1201       n_hist = 0;
1202       for (e = v;
1203            e->n_user_data != MHEAP_N_USER_DATA_INVALID;
1204            e = mheap_next_elt (e))
1205         {
1206           uword n_user_data_bytes = mheap_elt_data_bytes (e);
1207           uword bin = user_data_size_to_bin_index (n_user_data_bytes);
1208           if (!e->is_free)
1209             {
1210               hist[bin] += 1;
1211               n_hist += 1;
1212             }
1213         }
1214
1215       s = format (s, "\n%U%=12s%=12s%=16s",
1216                   format_white_space, indent + 2,
1217                   "Size", "Count", "Fraction");
1218
1219       for (i = 0; i < ARRAY_LEN (hist); i++)
1220         {
1221           if (hist[i] == 0)
1222             continue;
1223           s = format (s, "\n%U%12d%12wd%16.4f",
1224                       format_white_space, indent + 2,
1225                       MHEAP_MIN_USER_DATA_BYTES +
1226                       i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
1227                       (f64) hist[i] / (f64) n_hist);
1228         }
1229     }
1230
1231   if (verbose)
1232     s = format (s, "\n%U%U",
1233                 format_white_space, indent + 2, format_mheap_stats, h);
1234
1235   if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
1236     {
1237       /* Make a copy of traces since we'll be sorting them. */
1238       mheap_trace_t *t, *traces_copy;
1239       u32 indent, total_objects_traced;
1240
1241       traces_copy = vec_dup (h->trace_main.traces);
1242       qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
1243              mheap_trace_sort);
1244
1245       total_objects_traced = 0;
1246       s = format (s, "\n");
1247       vec_foreach (t, traces_copy)
1248       {
1249         /* Skip over free elements. */
1250         if (t->n_allocations == 0)
1251           continue;
1252
1253         total_objects_traced += t->n_allocations;
1254
1255         /* When not verbose only report allocations of more than 1k. */
1256         if (!verbose && t->n_bytes < 1024)
1257           continue;
1258
1259         if (t == traces_copy)
1260           s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
1261                       "Sample");
1262         s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
1263                     t->offset + v);
1264         indent = format_get_indent (s);
1265         for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
1266           {
1267             if (i > 0)
1268               s = format (s, "%U", format_white_space, indent);
1269 #ifdef CLIB_UNIX
1270             s =
1271               format (s, " %U\n", format_clib_elf_symbol_with_address,
1272                       t->callers[i]);
1273 #else
1274             s = format (s, " %p\n", t->callers[i]);
1275 #endif
1276           }
1277       }
1278
1279       s = format (s, "%d total traced objects\n", total_objects_traced);
1280
1281       vec_free (traces_copy);
1282     }
1283
1284   first_corrupt = mheap_first_corrupt (v);
1285   if (first_corrupt)
1286     {
1287       size = mheap_elt_data_bytes (first_corrupt);
1288       s = format (s, "\n  first corrupt object: %p, size %wd\n  %U",
1289                   first_corrupt, size, format_hex_bytes, first_corrupt, size);
1290     }
1291
1292   /* FIXME.  This output could be wrong in the unlikely case that format
1293      uses the same mheap as we are currently inspecting. */
1294   if (verbose > 1)
1295     {
1296       mheap_elt_t *e;
1297       uword i, o;
1298
1299       s = format (s, "\n");
1300
1301       e = mheap_elt_at_uoffset (v, 0);
1302       i = 0;
1303       while (1)
1304         {
1305           if ((i % 8) == 0)
1306             s = format (s, "%8d: ", i);
1307
1308           o = mheap_elt_uoffset (v, e);
1309
1310           if (e->is_free)
1311             s = format (s, "(%8d) ", o);
1312           else
1313             s = format (s, " %8d  ", o);
1314
1315           if ((i % 8) == 7 || (i + 1) >= h->n_elts)
1316             s = format (s, "\n");
1317         }
1318     }
1319
1320   mheap_maybe_unlock (v);
1321
1322   return s;
1323 }
1324
1325 void
1326 dmh (void *v)
1327 {
1328   fformat (stderr, "%U", format_mheap, v, 1);
1329 }
1330
1331 static void
1332 mheap_validate_breakpoint ()
1333 {
1334   os_panic ();
1335 }
1336
1337 void
1338 mheap_validate (void *v)
1339 {
1340   mheap_t *h = mheap_header (v);
1341   uword i, s;
1342
1343   uword elt_count, elt_size;
1344   uword free_count_from_free_lists, free_size_from_free_lists;
1345   uword small_elt_free_count, small_elt_free_size;
1346
1347 #define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }
1348
1349   if (vec_len (v) == 0)
1350     return;
1351
1352   mheap_maybe_lock (v);
1353
1354   /* Validate number of elements and size. */
1355   free_size_from_free_lists = free_count_from_free_lists = 0;
1356   for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
1357     {
1358       mheap_elt_t *e, *n;
1359       uword is_first;
1360
1361       CHECK ((h->first_free_elt_uoffset_by_bin[i] != MHEAP_GROUNDED)
1362              ==
1363              ((h->non_empty_free_elt_heads[i /
1364                                            BITS (uword)] & ((uword) 1 <<
1365                                                             (uword) (i %
1366                                                                      BITS
1367                                                                      (uword))))
1368               != 0));
1369
1370       if (h->first_free_elt_uoffset_by_bin[i] == MHEAP_GROUNDED)
1371         continue;
1372
1373       e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[i]);
1374       is_first = 1;
1375       while (1)
1376         {
1377           uword s;
1378
1379           n = mheap_next_elt (e);
1380
1381           /* Object must be marked free. */
1382           CHECK (e->is_free);
1383
1384           /* Next object's previous free bit must also be set. */
1385           CHECK (n->prev_is_free);
1386
1387           if (is_first)
1388             CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
1389           is_first = 0;
1390
1391           s = mheap_elt_data_bytes (e);
1392           CHECK (user_data_size_to_bin_index (s) == i);
1393
1394           free_count_from_free_lists += 1;
1395           free_size_from_free_lists += s;
1396
1397           if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
1398             break;
1399
1400           n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
1401
1402           /* Check free element linkages. */
1403           CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));
1404
1405           e = n;
1406         }
1407     }
1408
1409   /* Go through small object cache. */
1410   small_elt_free_count = small_elt_free_size = 0;
1411   for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
1412     {
1413       if (h->small_object_cache.bins.as_u8[i] != 0)
1414         {
1415           mheap_elt_t *e;
1416           uword b = h->small_object_cache.bins.as_u8[i] - 1;
1417           uword o = h->small_object_cache.offsets[i];
1418           uword s;
1419
1420           e = mheap_elt_at_uoffset (v, o);
1421
1422           /* Object must be allocated. */
1423           CHECK (!e->is_free);
1424
1425           s = mheap_elt_data_bytes (e);
1426           CHECK (user_data_size_to_bin_index (s) == b);
1427
1428           small_elt_free_count += 1;
1429           small_elt_free_size += s;
1430         }
1431     }
1432
1433   {
1434     mheap_elt_t *e, *n;
1435     uword elt_free_size, elt_free_count;
1436
1437     elt_count = elt_size = elt_free_size = elt_free_count = 0;
1438     for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
1439       {
1440         if (e->prev_n_user_data != MHEAP_N_USER_DATA_INVALID)
1441           CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
1442                  MHEAP_MIN_USER_DATA_BYTES);
1443
1444         CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
1445                MHEAP_MIN_USER_DATA_BYTES);
1446
1447         n = mheap_next_elt (e);
1448
1449         CHECK (e->is_free == n->prev_is_free);
1450
1451         elt_count++;
1452         s = mheap_elt_data_bytes (e);
1453         elt_size += s;
1454
1455         if (e->is_free)
1456           {
1457             elt_free_count++;
1458             elt_free_size += s;
1459           }
1460
1461         /* Consecutive free objects should have been combined. */
1462         CHECK (!(e->prev_is_free && n->prev_is_free));
1463       }
1464
1465     CHECK (free_count_from_free_lists == elt_free_count);
1466     CHECK (free_size_from_free_lists == elt_free_size);
1467     CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
1468     CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
1469            vec_len (v));
1470   }
1471
1472   {
1473     mheap_elt_t *e, *n;
1474
1475     for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
1476       {
1477         n = mheap_next_elt (e);
1478         CHECK (e->n_user_data == n->prev_n_user_data);
1479       }
1480   }
1481
1482 #undef CHECK
1483
1484   mheap_maybe_unlock (v);
1485
1486   h->validate_serial += 1;
1487 }
1488
1489 static void
1490 mheap_get_trace (void *v, uword offset, uword size)
1491 {
1492   mheap_t *h;
1493   mheap_trace_main_t *tm;
1494   mheap_trace_t *t;
1495   uword i, n_callers, trace_index, *p;
1496   mheap_trace_t trace;
1497
1498   /* Spurious Coverity warnings be gone. */
1499   memset (&trace, 0, sizeof (trace));
1500
1501   n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
1502                               /* Skip mheap_get_aligned's frame */ 1);
1503   if (n_callers == 0)
1504     return;
1505
1506   for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
1507     trace.callers[i] = 0;
1508
1509   h = mheap_header (v);
1510   tm = &h->trace_main;
1511
1512   if (!tm->trace_by_callers)
1513     tm->trace_by_callers =
1514       hash_create_mem (0, sizeof (trace.callers), sizeof (uword));
1515
1516   p = hash_get_mem (tm->trace_by_callers, &trace.callers);
1517   if (p)
1518     {
1519       trace_index = p[0];
1520       t = tm->traces + trace_index;
1521     }
1522   else
1523     {
1524       i = vec_len (tm->trace_free_list);
1525       if (i > 0)
1526         {
1527           trace_index = tm->trace_free_list[i - 1];
1528           _vec_len (tm->trace_free_list) = i - 1;
1529         }
1530       else
1531         {
1532           mheap_trace_t *old_start = tm->traces;
1533           mheap_trace_t *old_end = vec_end (tm->traces);
1534
1535           vec_add2 (tm->traces, t, 1);
1536
1537           if (tm->traces != old_start)
1538             {
1539               hash_pair_t *p;
1540               mheap_trace_t *q;
1541             /* *INDENT-OFF* */
1542             hash_foreach_pair (p, tm->trace_by_callers,
1543             ({
1544               q = uword_to_pointer (p->key, mheap_trace_t *);
1545               ASSERT (q >= old_start && q < old_end);
1546               p->key = pointer_to_uword (tm->traces + (q - old_start));
1547             }));
1548             /* *INDENT-ON* */
1549             }
1550           trace_index = t - tm->traces;
1551         }
1552
1553       t = tm->traces + trace_index;
1554       t[0] = trace;
1555       t->n_allocations = 0;
1556       t->n_bytes = 0;
1557       hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
1558     }
1559
1560   t->n_allocations += 1;
1561   t->n_bytes += size;
1562   t->offset = offset;           /* keep a sample to autopsy */
1563   hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
1564 }
1565
1566 static void
1567 mheap_put_trace (void *v, uword offset, uword size)
1568 {
1569   mheap_t *h;
1570   mheap_trace_main_t *tm;
1571   mheap_trace_t *t;
1572   uword trace_index, *p;
1573
1574   h = mheap_header (v);
1575   tm = &h->trace_main;
1576   p = hash_get (tm->trace_index_by_offset, offset);
1577   if (!p)
1578     return;
1579
1580   trace_index = p[0];
1581   hash_unset (tm->trace_index_by_offset, offset);
1582   ASSERT (trace_index < vec_len (tm->traces));
1583
1584   t = tm->traces + trace_index;
1585   ASSERT (t->n_allocations > 0);
1586   ASSERT (t->n_bytes >= size);
1587   t->n_allocations -= 1;
1588   t->n_bytes -= size;
1589   if (t->n_allocations == 0)
1590     {
1591       hash_unset_mem (tm->trace_by_callers, t->callers);
1592       vec_add1 (tm->trace_free_list, trace_index);
1593       memset (t, 0, sizeof (t[0]));
1594     }
1595 }
1596
1597 static int
1598 mheap_trace_sort (const void *_t1, const void *_t2)
1599 {
1600   const mheap_trace_t *t1 = _t1;
1601   const mheap_trace_t *t2 = _t2;
1602   word cmp;
1603
1604   cmp = (word) t2->n_bytes - (word) t1->n_bytes;
1605   if (!cmp)
1606     cmp = (word) t2->n_allocations - (word) t1->n_allocations;
1607   return cmp;
1608 }
1609
1610 always_inline void
1611 mheap_trace_main_free (mheap_trace_main_t * tm)
1612 {
1613   vec_free (tm->traces);
1614   vec_free (tm->trace_free_list);
1615   hash_free (tm->trace_by_callers);
1616   hash_free (tm->trace_index_by_offset);
1617 }
1618
1619 void
1620 mheap_trace (void *v, int enable)
1621 {
1622   mheap_t *h;
1623
1624   h = mheap_header (v);
1625
1626   if (enable)
1627     {
1628       h->flags |= MHEAP_FLAG_TRACE;
1629     }
1630   else
1631     {
1632       mheap_trace_main_free (&h->trace_main);
1633       h->flags &= ~MHEAP_FLAG_TRACE;
1634     }
1635 }
1636
1637 /*
1638  * fd.io coding-style-patch-verification: ON
1639  *
1640  * Local Variables:
1641  * eval: (c-set-style "gnu")
1642  * End:
1643  */