vppinfra/vppinfra/heap.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/cache.h>     /* for CLIB_CACHE_LINE_BYTES */
  39 #include <vppinfra/mem.h>
  40 #include <vppinfra/hash.h>
  41 #include <vppinfra/vec.h>
  42 #include <vppinfra/heap.h>
  43 #include <vppinfra/error.h>
  44
  45 always_inline heap_elt_t *
  46 elt_at (heap_header_t * h, uword i)
  47 {
  48   ASSERT (i < vec_len (h->elts));
  49   return h->elts + i;
  50 }
  51
  52 always_inline heap_elt_t *
  53 last (heap_header_t * h)
  54 {
  55   return elt_at (h, h->tail);
  56 }
  57
  58 always_inline heap_elt_t *
  59 first (heap_header_t * h)
  60 {
  61   return elt_at (h, h->head);
  62 }
  63
  64 /* Objects sizes are binned into N_BINS bins.
  65    Objects with size <= SMALL_BINS have their own bins.
  66    Larger objects are grouped together in power or 2 sized
  67    bins.
  68
  69    Sizes are in units of elt_bytes bytes. */
  70
  71 /* Convert size to bin. */
  72 always_inline uword
  73 size_to_bin (uword size)
  74 {
  75   uword bin;
  76
  77   ASSERT (size > 0);
  78
  79   if (size <= HEAP_SMALL_BINS)
  80     {
  81       bin = size - 1;
  82       if (size == 0)
  83         bin = 0;
  84     }
  85   else
  86     {
  87       bin = HEAP_SMALL_BINS + max_log2 (size) - (HEAP_LOG2_SMALL_BINS + 1);
  88       if (bin >= HEAP_N_BINS)
  89         bin = HEAP_N_BINS - 1;
  90     }
  91
  92   return bin;
  93 }
  94
  95 /* Convert bin to size. */
  96 always_inline __attribute__ ((unused))
  97      uword bin_to_size (uword bin)
  98 {
  99   uword size;
 100
 101   if (bin <= HEAP_SMALL_BINS - 1)
 102     size = bin + 1;
 103   else
 104     size = (uword) 1 << ((bin - HEAP_SMALL_BINS) + HEAP_LOG2_SMALL_BINS + 1);
 105
 106   return size;
 107 }
 108
 109 static void
 110 elt_delete (heap_header_t * h, heap_elt_t * e)
 111 {
 112   heap_elt_t *l = vec_end (h->elts) - 1;
 113
 114   ASSERT (e >= h->elts && e <= l);
 115
 116   /* Update doubly linked pointers. */
 117   {
 118     heap_elt_t *p = heap_prev (e);
 119     heap_elt_t *n = heap_next (e);
 120
 121     if (p == e)
 122       {
 123         n->prev = 0;
 124         h->head = n - h->elts;
 125       }
 126     else if (n == e)
 127       {
 128         p->next = 0;
 129         h->tail = p - h->elts;
 130       }
 131     else
 132       {
 133         p->next = n - p;
 134         n->prev = p - n;
 135       }
 136   }
 137
 138   /* Add to index free list or delete from end. */
 139   if (e < l)
 140     vec_add1 (h->free_elts, e - h->elts);
 141   else
 142     _vec_len (h->elts)--;
 143 }
 144
 145 /*
 146   Before: P ... E
 147   After : P ... NEW ... E
 148 */
 149 always_inline void
 150 elt_insert_before (heap_header_t * h, heap_elt_t * e, heap_elt_t * new)
 151 {
 152   heap_elt_t *p = heap_prev (e);
 153
 154   if (p == e)
 155     {
 156       new->prev = 0;
 157       new->next = e - new;
 158       p->prev = new - p;
 159       h->head = new - h->elts;
 160     }
 161   else
 162     {
 163       new->prev = p - new;
 164       new->next = e - new;
 165       e->prev = new - e;
 166       p->next = new - p;
 167     }
 168 }
 169
 170 /*
 171   Before: E ... N
 172   After : E ... NEW ... N
 173 */
 174 always_inline void
 175 elt_insert_after (heap_header_t * h, heap_elt_t * e, heap_elt_t * new)
 176 {
 177   heap_elt_t *n = heap_next (e);
 178
 179   if (n == e)
 180     {
 181       new->next = 0;
 182       new->prev = e - new;
 183       e->next = new - e;
 184       h->tail = new - h->elts;
 185     }
 186   else
 187     {
 188       new->prev = e - new;
 189       new->next = n - new;
 190       e->next = new - e;
 191       n->prev = new - n;
 192     }
 193 }
 194
 195 always_inline heap_elt_t *
 196 elt_new (heap_header_t * h)
 197 {
 198   heap_elt_t *e;
 199   uword l;
 200   if ((l = vec_len (h->free_elts)) > 0)
 201     {
 202       e = elt_at (h, h->free_elts[l - 1]);
 203       _vec_len (h->free_elts) -= 1;
 204     }
 205   else
 206     vec_add2 (h->elts, e, 1);
 207   return e;
 208 }
 209
 210 /* Return pointer to object at given offset.
 211    Used to write free list index of free objects. */
 212 always_inline u32 *
 213 elt_data (void *v, heap_elt_t * e)
 214 {
 215   heap_header_t *h = heap_header (v);
 216   return v + heap_offset (e) * h->elt_bytes;
 217 }
 218
 219 always_inline void
 220 set_free_elt (void *v, heap_elt_t * e, uword fi)
 221 {
 222   heap_header_t *h = heap_header (v);
 223
 224   e->offset |= HEAP_ELT_FREE_BIT;
 225   if (h->elt_bytes >= sizeof (u32))
 226     {
 227       *elt_data (v, e) = fi;
 228     }
 229   else
 230     {
 231       /* For elt_bytes < 4 we must store free index in separate
 232          vector. */
 233       uword elt_index = e - h->elts;
 234       vec_validate (h->small_free_elt_free_index, elt_index);
 235       h->small_free_elt_free_index[elt_index] = fi;
 236     }
 237 }
 238
 239 always_inline uword
 240 get_free_elt (void *v, heap_elt_t * e, uword * bin_result)
 241 {
 242   heap_header_t *h = heap_header (v);
 243   uword fb, fi;
 244
 245   ASSERT (heap_is_free (e));
 246   fb = size_to_bin (heap_elt_size (v, e));
 247
 248   if (h->elt_bytes >= sizeof (u32))
 249     {
 250       fi = *elt_data (v, e);
 251     }
 252   else
 253     {
 254       uword elt_index = e - h->elts;
 255       fi = vec_elt (h->small_free_elt_free_index, elt_index);
 256     }
 257
 258   *bin_result = fb;
 259   return fi;
 260 }
 261
 262 always_inline void
 263 remove_free_block (void *v, uword b, uword i)
 264 {
 265   heap_header_t *h = heap_header (v);
 266   uword l;
 267
 268   ASSERT (b < vec_len (h->free_lists));
 269   ASSERT (i < vec_len (h->free_lists[b]));
 270
 271   l = vec_len (h->free_lists[b]);
 272
 273   if (i < l - 1)
 274     {
 275       uword t = h->free_lists[b][l - 1];
 276       h->free_lists[b][i] = t;
 277       set_free_elt (v, elt_at (h, t), i);
 278     }
 279   _vec_len (h->free_lists[b]) = l - 1;
 280 }
 281
 282 static heap_elt_t *
 283 search_free_list (void *v, uword size)
 284 {
 285   heap_header_t *h = heap_header (v);
 286   heap_elt_t *f, *u;
 287   uword b, fb, f_size, f_index;
 288   word s, l;
 289
 290   if (!v)
 291     return 0;
 292
 293   /* Search free lists for bins >= given size. */
 294   for (b = size_to_bin (size); b < vec_len (h->free_lists); b++)
 295     if ((l = vec_len (h->free_lists[b])) > 0)
 296       {
 297         /* Find an object that is large enough.
 298            Search list in reverse so that more recently freed objects will be
 299            allocated again sooner. */
 300         do
 301           {
 302             l--;
 303             f_index = h->free_lists[b][l];
 304             f = elt_at (h, f_index);
 305             f_size = heap_elt_size (v, f);
 306             if ((s = f_size - size) >= 0)
 307               break;
 308           }
 309         while (l >= 0);
 310
 311         /* If we fail to find a large enough object, try the next larger size. */
 312         if (l < 0)
 313           continue;
 314
 315         ASSERT (heap_is_free (f));
 316
 317         /* Link in used object (u) after free object (f). */
 318         if (s == 0)
 319           {
 320             u = f;
 321             fb = HEAP_N_BINS;
 322           }
 323         else
 324           {
 325             u = elt_new (h);
 326             f = elt_at (h, f_index);
 327             elt_insert_after (h, f, u);
 328             fb = size_to_bin (s);
 329           }
 330
 331         u->offset = heap_offset (f) + s;
 332
 333         if (fb != b)
 334           {
 335             if (fb < HEAP_N_BINS)
 336               {
 337                 uword i;
 338                 vec_validate (h->free_lists, fb);
 339                 i = vec_len (h->free_lists[fb]);
 340                 vec_add1 (h->free_lists[fb], f - h->elts);
 341                 set_free_elt (v, f, i);
 342               }
 343
 344             remove_free_block (v, b, l);
 345           }
 346
 347         return u;
 348       }
 349
 350   return 0;
 351 }
 352
 353 static void combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1);
 354
 355 static inline void
 356 dealloc_elt (void *v, heap_elt_t * e)
 357 {
 358   heap_header_t *h = heap_header (v);
 359   uword b, l;
 360   heap_elt_t *n, *p;
 361
 362   b = size_to_bin (heap_elt_size (v, e));
 363   vec_validate (h->free_lists, b);
 364   l = vec_len (h->free_lists[b]);
 365   vec_add1 (h->free_lists[b], e - h->elts);
 366   set_free_elt (v, e, l);
 367
 368   /* See if we can combine the block we just freed with neighboring free blocks. */
 369   p = heap_prev (e);
 370   if (!heap_is_free (p))
 371     p = e;
 372
 373   n = heap_next (e);
 374   if (!heap_is_free (n))
 375     n = e;
 376
 377   if (p != n)
 378     combine_free_blocks (v, p, n);
 379 }
 380
 381 void *
 382 _heap_alloc (void *v,
 383              uword size,
 384              uword align,
 385              uword elt_bytes, uword * offset_return, uword * handle_return)
 386 {
 387   uword offset = 0, align_size;
 388   heap_header_t *h;
 389   heap_elt_t *e;
 390
 391   if (size == 0)
 392     goto error;
 393
 394   /* Round up alignment to power of 2. */
 395   if (align <= 1)
 396     {
 397       align = 0;
 398       align_size = size;
 399     }
 400   else
 401     {
 402       align = max_pow2 (align);
 403       align_size = size + align - 1;
 404     }
 405
 406   e = search_free_list (v, align_size);
 407
 408   /* If nothing found on free list, allocate object from end of vector. */
 409   if (!e)
 410     {
 411       uword max_len;
 412
 413       offset = vec_len (v);
 414       max_len = heap_get_max_len (v);
 415
 416       if (max_len && offset + align_size > max_len)
 417         goto error;
 418
 419       h = heap_header (v);
 420       if (!v || !(h->flags & HEAP_IS_STATIC))
 421         v = _vec_resize (v,
 422                          align_size,
 423                          (offset + align_size) * elt_bytes,
 424                          sizeof (h[0]), HEAP_DATA_ALIGN);
 425       else
 426         _vec_len (v) += align_size;
 427
 428       if (offset == 0)
 429         {
 430           h = heap_header (v);
 431           h->elt_bytes = elt_bytes;
 432         }
 433     }
 434
 435   h = heap_header (v);
 436
 437   /* Add new element to doubly linked chain of elements. */
 438   if (!e)
 439     {
 440       e = elt_new (h);
 441       e->offset = offset;
 442       elt_insert_after (h, last (h), e);
 443     }
 444
 445   if (align > 0)
 446     {
 447       uword e_index;
 448       uword new_offset, old_offset;
 449
 450       old_offset = e->offset;
 451       new_offset = (old_offset + align - 1) & ~(align - 1);
 452       e->offset = new_offset;
 453       e_index = e - h->elts;
 454
 455       /* Free fragments before and after aligned object. */
 456       if (new_offset > old_offset)
 457         {
 458           heap_elt_t *before_e = elt_new (h);
 459           before_e->offset = old_offset;
 460           elt_insert_before (h, h->elts + e_index, before_e);
 461           dealloc_elt (v, before_e);
 462         }
 463
 464       if (new_offset + size < old_offset + align_size)
 465         {
 466           heap_elt_t *after_e = elt_new (h);
 467           after_e->offset = new_offset + size;
 468           elt_insert_after (h, h->elts + e_index, after_e);
 469           dealloc_elt (v, after_e);
 470         }
 471
 472       e = h->elts + e_index;
 473     }
 474
 475   h->used_count++;
 476
 477   /* Keep track of used elements when debugging.
 478      This allows deallocation to check that passed objects are valid. */
 479   if (CLIB_DEBUG > 0)
 480     {
 481       uword handle = e - h->elts;
 482       ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle));
 483       h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
 484     }
 485
 486   *offset_return = e->offset;
 487   *handle_return = e - h->elts;
 488   return v;
 489
 490 error:
 491   *offset_return = *handle_return = ~0;
 492   return v;
 493 }
 494
 495 void
 496 heap_dealloc (void *v, uword handle)
 497 {
 498   heap_header_t *h = heap_header (v);
 499   heap_elt_t *e;
 500
 501   ASSERT (handle < vec_len (h->elts));
 502
 503   /* For debugging we keep track of indices for valid objects.
 504      We make sure user is not trying to free object with an invalid index. */
 505   if (CLIB_DEBUG > 0)
 506     {
 507       ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
 508       h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
 509     }
 510
 511   h->used_count--;
 512
 513   e = h->elts + handle;
 514   ASSERT (!heap_is_free (e));
 515
 516   dealloc_elt (v, e);
 517 }
 518
 519 /* While freeing objects at INDEX we noticed free blocks i0 <= index and
 520    i1 >= index.  We combine these two or three blocks into one big free block. */
 521 static void
 522 combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1)
 523 {
 524   heap_header_t *h = heap_header (v);
 525   uword total_size, i, b, tb, ti, i_last, g_offset;
 526   heap_elt_t *e;
 527
 528   struct
 529   {
 530     u32 index;
 531     u32 bin;
 532     u32 bin_index;
 533   } f[3], g;
 534
 535   /* Compute total size of free objects i0 through i1. */
 536   total_size = 0;
 537   for (i = 0, e = e0; 1; e = heap_next (e), i++)
 538     {
 539       ASSERT (i < ARRAY_LEN (f));
 540
 541       ti = get_free_elt (v, e, &tb);
 542
 543       ASSERT (tb < vec_len (h->free_lists));
 544       ASSERT (ti < vec_len (h->free_lists[tb]));
 545
 546       f[i].index = h->free_lists[tb][ti];
 547       f[i].bin = tb;
 548       f[i].bin_index = ti;
 549
 550       total_size += heap_elt_size (v, elt_at (h, f[i].index));
 551
 552       if (e == e1)
 553         {
 554           i_last = i;
 555           break;
 556         }
 557     }
 558
 559   /* Compute combined bin.  See if all objects can be
 560      combined into existing bin. */
 561   b = size_to_bin (total_size);
 562   g.index = g.bin_index = 0;
 563   for (i = 0; i <= i_last; i++)
 564     if (b == f[i].bin)
 565       {
 566         g = f[i];
 567         break;
 568       }
 569
 570   /* Make sure we found a bin. */
 571   if (i > i_last)
 572     {
 573       g.index = elt_new (h) - h->elts;
 574       vec_validate (h->free_lists, b);
 575       g.bin_index = vec_len (h->free_lists[b]);
 576       vec_add1 (h->free_lists[b], g.index);
 577       elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
 578     }
 579
 580   g_offset = elt_at (h, f[0].index)->offset;
 581
 582   /* Delete unused bins. */
 583   for (i = 0; i <= i_last; i++)
 584     if (g.index != f[i].index)
 585       {
 586         ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
 587         remove_free_block (v, tb, ti);
 588         elt_delete (h, elt_at (h, f[i].index));
 589       }
 590
 591   /* Initialize new element. */
 592   elt_at (h, g.index)->offset = g_offset;
 593   set_free_elt (v, elt_at (h, g.index), g.bin_index);
 594 }
 595
 596 uword
 597 heap_len (void *v, word handle)
 598 {
 599   heap_header_t *h = heap_header (v);
 600
 601   if (CLIB_DEBUG > 0)
 602     ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
 603   return heap_elt_size (v, elt_at (h, handle));
 604 }
 605
 606 void *
 607 _heap_free (void *v)
 608 {
 609   heap_header_t *h = heap_header (v);
 610   uword b;
 611
 612   if (!v)
 613     return v;
 614
 615   clib_bitmap_free (h->used_elt_bitmap);
 616   for (b = 0; b < vec_len (h->free_lists); b++)
 617     vec_free (h->free_lists[b]);
 618   vec_free (h->free_lists);
 619   vec_free (h->elts);
 620   vec_free (h->free_elts);
 621   vec_free (h->small_free_elt_free_index);
 622   if (!(h->flags & HEAP_IS_STATIC))
 623     vec_free_h (v, sizeof (h[0]));
 624   return v;
 625 }
 626
 627 uword
 628 heap_bytes (void *v)
 629 {
 630   heap_header_t *h = heap_header (v);
 631   uword bytes, b;
 632
 633   if (!v)
 634     return 0;
 635
 636   bytes = sizeof (h[0]);
 637   bytes += vec_len (v) * sizeof (h->elt_bytes);
 638   for (b = 0; b < vec_len (h->free_lists); b++)
 639     bytes += vec_capacity (h->free_lists[b], 0);
 640   bytes += vec_bytes (h->free_lists);
 641   bytes += vec_capacity (h->elts, 0);
 642   bytes += vec_capacity (h->free_elts, 0);
 643   bytes += vec_bytes (h->used_elt_bitmap);
 644
 645   return bytes;
 646 }
 647
 648 static u8 *
 649 debug_elt (u8 * s, void *v, word i, word n)
 650 {
 651   heap_elt_t *e, *e0, *e1;
 652   heap_header_t *h = heap_header (v);
 653   word j;
 654
 655   if (vec_len (h->elts) == 0)
 656     return s;
 657
 658   if (i < 0)
 659     e0 = first (h);
 660   else
 661     {
 662       e0 = h->elts + i;
 663       for (j = 0; j < n / 2; j++)
 664         e0 = heap_prev (e0);
 665     }
 666
 667   if (n < 0)
 668     e1 = h->elts + h->tail;
 669   else
 670     {
 671       e1 = h->elts + i;
 672       for (j = 0; j < n / 2; j++)
 673         e1 = heap_next (e1);
 674     }
 675
 676   i = -n / 2;
 677   for (e = e0; 1; e = heap_next (e))
 678     {
 679       if (heap_is_free (e))
 680         s = format (s, "index %4d, free\n", e - h->elts);
 681       else if (h->format_elt)
 682         s = format (s, "%U", h->format_elt, v, elt_data (v, e));
 683       else
 684         s = format (s, "index %4d, used\n", e - h->elts);
 685       i++;
 686       if (e == e1)
 687         break;
 688     }
 689
 690   return s;
 691 }
 692
 693 u8 *
 694 format_heap (u8 * s, va_list * va)
 695 {
 696   void *v = va_arg (*va, void *);
 697   uword verbose = va_arg (*va, uword);
 698   heap_header_t *h = heap_header (v);
 699   heap_header_t zero;
 700
 701   memset (&zero, 0, sizeof (zero));
 702
 703   if (!v)
 704     h = &zero;
 705
 706   {
 707     f64 elt_bytes = vec_len (v) * h->elt_bytes;
 708     f64 overhead_bytes = heap_bytes (v);
 709
 710     s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
 711                 v, h->used_count, elt_bytes / 1024,
 712                 (overhead_bytes - elt_bytes) / 1024);
 713   }
 714
 715   if (v && verbose)
 716     s = debug_elt (s, v, -1, -1);
 717
 718   return s;
 719 }
 720
 721 void
 722 heap_validate (void *v)
 723 {
 724   heap_header_t *h = heap_header (v);
 725   uword i, o, s;
 726   u8 *free_map;
 727   heap_elt_t *e, *n;
 728
 729   uword used_count, total_size;
 730   uword free_count, free_size;
 731
 732   ASSERT (h->used_count == clib_bitmap_count_set_bits (h->used_elt_bitmap));
 733
 734   ASSERT (first (h)->prev == 0);
 735   ASSERT (last (h)->next == 0);
 736
 737   /* Validate number of elements and size. */
 738   free_size = free_count = 0;
 739   for (i = 0; i < vec_len (h->free_lists); i++)
 740     {
 741       free_count += vec_len (h->free_lists[i]);
 742       for (o = 0; o < vec_len (h->free_lists[i]); o++)
 743         {
 744           e = h->elts + h->free_lists[i][o];
 745           s = heap_elt_size (v, e);
 746           ASSERT (size_to_bin (s) == i);
 747           ASSERT (heap_is_free (e));
 748           free_size += s;
 749         }
 750     }
 751
 752   {
 753     uword elt_free_size, elt_free_count;
 754
 755     used_count = total_size = elt_free_size = elt_free_count = 0;
 756     for (e = first (h); 1; e = n)
 757       {
 758         int is_free = heap_is_free (e);
 759         used_count++;
 760         s = heap_elt_size (v, e);
 761         total_size += s;
 762         ASSERT (is_free ==
 763                 !clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
 764         if (is_free)
 765           {
 766             elt_free_count++;
 767             elt_free_size += s;
 768           }
 769         n = heap_next (e);
 770         if (e == n)
 771           {
 772             ASSERT (last (h) == n);
 773             break;
 774           }
 775
 776         /* We should never have two free adjacent elements. */
 777         ASSERT (!(heap_is_free (e) && heap_is_free (n)));
 778       }
 779
 780     ASSERT (free_count == elt_free_count);
 781     ASSERT (free_size == elt_free_size);
 782     ASSERT (used_count == h->used_count + free_count);
 783     ASSERT (total_size == vec_len (v));
 784   }
 785
 786   free_map = vec_new (u8, used_count);
 787
 788   e = first (h);
 789   for (i = o = 0; 1; i++)
 790     {
 791       ASSERT (heap_offset (e) == o);
 792       s = heap_elt_size (v, e);
 793
 794       if (heap_is_free (e))
 795         {
 796           uword fb, fi;
 797
 798           fi = get_free_elt (v, e, &fb);
 799
 800           ASSERT (fb < vec_len (h->free_lists));
 801           ASSERT (fi < vec_len (h->free_lists[fb]));
 802           ASSERT (h->free_lists[fb][fi] == e - h->elts);
 803
 804           ASSERT (!free_map[i]);
 805           free_map[i] = 1;
 806         }
 807
 808       n = heap_next (e);
 809
 810       if (e == n)
 811         break;
 812
 813       ASSERT (heap_prev (n) == e);
 814
 815       o += s;
 816       e = n;
 817     }
 818
 819   vec_free (free_map);
 820 }
 821
 822 /*
 823  * fd.io coding-style-patch-verification: ON
 824  *
 825  * Local Variables:
 826  * eval: (c-set-style "gnu")
 827  * End:
 828  */