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