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