src/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         u8 found = 0;
 301         do
 302           {
 303             l--;
 304             f_index = h->free_lists[b][l];
 305             f = elt_at (h, f_index);
 306             f_size = heap_elt_size (v, f);
 307             if ((s = f_size - size) >= 0)
 308               {
 309                 found = 1;
 310                 break;
 311               }
 312           }
 313         while (l > 0);
 314
 315         /* If we fail to find a large enough object, try the next larger size. */
 316         if (found == 0)
 317           continue;
 318
 319         ASSERT (heap_is_free (f));
 320
 321         /* Link in used object (u) after free object (f). */
 322         if (s == 0)
 323           {
 324             u = f;
 325             fb = HEAP_N_BINS;
 326           }
 327         else
 328           {
 329             u = elt_new (h);
 330             f = elt_at (h, f_index);
 331             elt_insert_after (h, f, u);
 332             fb = size_to_bin (s);
 333           }
 334
 335         u->offset = heap_offset (f) + s;
 336
 337         if (fb != b)
 338           {
 339             if (fb < HEAP_N_BINS)
 340               {
 341                 uword i;
 342                 vec_validate (h->free_lists, fb);
 343                 i = vec_len (h->free_lists[fb]);
 344                 vec_add1 (h->free_lists[fb], f - h->elts);
 345                 set_free_elt (v, f, i);
 346               }
 347
 348             remove_free_block (v, b, l);
 349           }
 350
 351         return u;
 352       }
 353
 354   return 0;
 355 }
 356
 357 static void combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1);
 358
 359 static inline void
 360 dealloc_elt (void *v, heap_elt_t * e)
 361 {
 362   heap_header_t *h = heap_header (v);
 363   uword b, l;
 364   heap_elt_t *n, *p;
 365
 366   b = size_to_bin (heap_elt_size (v, e));
 367   vec_validate (h->free_lists, b);
 368   l = vec_len (h->free_lists[b]);
 369   vec_add1 (h->free_lists[b], e - h->elts);
 370   set_free_elt (v, e, l);
 371
 372   /* See if we can combine the block we just freed with neighboring free blocks. */
 373   p = heap_prev (e);
 374   if (!heap_is_free (p))
 375     p = e;
 376
 377   n = heap_next (e);
 378   if (!heap_is_free (n))
 379     n = e;
 380
 381   if (p != n)
 382     combine_free_blocks (v, p, n);
 383 }
 384
 385 void *
 386 _heap_alloc (void *v,
 387              uword size,
 388              uword align,
 389              uword elt_bytes, uword * offset_return, uword * handle_return)
 390 {
 391   uword offset = 0, align_size;
 392   heap_header_t *h;
 393   heap_elt_t *e;
 394
 395   if (size == 0)
 396     goto error;
 397
 398   /* Round up alignment to power of 2. */
 399   if (align <= 1)
 400     {
 401       align = 0;
 402       align_size = size;
 403     }
 404   else
 405     {
 406       align = max_pow2 (align);
 407       align_size = size + align - 1;
 408     }
 409
 410   e = search_free_list (v, align_size);
 411
 412   /* If nothing found on free list, allocate object from end of vector. */
 413   if (!e)
 414     {
 415       uword max_len;
 416
 417       offset = vec_len (v);
 418       max_len = heap_get_max_len (v);
 419
 420       if (max_len && offset + align_size > max_len)
 421         goto error;
 422
 423       h = heap_header (v);
 424       if (!v || !(h->flags & HEAP_IS_STATIC))
 425         v = _vec_resize (v,
 426                          align_size,
 427                          (offset + align_size) * elt_bytes,
 428                          sizeof (h[0]), HEAP_DATA_ALIGN);
 429       else
 430         _vec_len (v) += align_size;
 431
 432       if (offset == 0)
 433         {
 434           h = heap_header (v);
 435           h->elt_bytes = elt_bytes;
 436         }
 437     }
 438
 439   h = heap_header (v);
 440
 441   /* Add new element to doubly linked chain of elements. */
 442   if (!e)
 443     {
 444       e = elt_new (h);
 445       e->offset = offset;
 446       elt_insert_after (h, last (h), e);
 447     }
 448
 449   if (align > 0)
 450     {
 451       uword e_index;
 452       uword new_offset, old_offset;
 453
 454       old_offset = e->offset;
 455       new_offset = (old_offset + align - 1) & ~(align - 1);
 456       e->offset = new_offset;
 457       e_index = e - h->elts;
 458
 459       /* Free fragments before and after aligned object. */
 460       if (new_offset > old_offset)
 461         {
 462           heap_elt_t *before_e = elt_new (h);
 463           before_e->offset = old_offset;
 464           elt_insert_before (h, h->elts + e_index, before_e);
 465           dealloc_elt (v, before_e);
 466         }
 467
 468       if (new_offset + size < old_offset + align_size)
 469         {
 470           heap_elt_t *after_e = elt_new (h);
 471           after_e->offset = new_offset + size;
 472           elt_insert_after (h, h->elts + e_index, after_e);
 473           dealloc_elt (v, after_e);
 474         }
 475
 476       e = h->elts + e_index;
 477     }
 478
 479   h->used_count++;
 480
 481   /* Keep track of used elements when debugging.
 482      This allows deallocation to check that passed objects are valid. */
 483   if (CLIB_DEBUG > 0)
 484     {
 485       uword handle = e - h->elts;
 486       ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle));
 487       h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
 488     }
 489
 490   *offset_return = e->offset;
 491   *handle_return = e - h->elts;
 492   return v;
 493
 494 error:
 495   *offset_return = *handle_return = ~0;
 496   return v;
 497 }
 498
 499 void
 500 heap_dealloc (void *v, uword handle)
 501 {
 502   heap_header_t *h = heap_header (v);
 503   heap_elt_t *e;
 504
 505   ASSERT (handle < vec_len (h->elts));
 506
 507   /* For debugging we keep track of indices for valid objects.
 508      We make sure user is not trying to free object with an invalid index. */
 509   if (CLIB_DEBUG > 0)
 510     {
 511       ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
 512       h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
 513     }
 514
 515   h->used_count--;
 516
 517   e = h->elts + handle;
 518   ASSERT (!heap_is_free (e));
 519
 520   dealloc_elt (v, e);
 521 }
 522
 523 /* While freeing objects at INDEX we noticed free blocks i0 <= index and
 524    i1 >= index.  We combine these two or three blocks into one big free block. */
 525 static void
 526 combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1)
 527 {
 528   heap_header_t *h = heap_header (v);
 529   uword total_size, i, b, tb, ti, i_last, g_offset;
 530   heap_elt_t *e;
 531
 532   struct
 533   {
 534     u32 index;
 535     u32 bin;
 536     u32 bin_index;
 537   } f[3], g;
 538
 539   /* Compute total size of free objects i0 through i1. */
 540   total_size = 0;
 541   for (i = 0, e = e0; 1; e = heap_next (e), i++)
 542     {
 543       ASSERT (i < ARRAY_LEN (f));
 544
 545       ti = get_free_elt (v, e, &tb);
 546
 547       ASSERT (tb < vec_len (h->free_lists));
 548       ASSERT (ti < vec_len (h->free_lists[tb]));
 549
 550       f[i].index = h->free_lists[tb][ti];
 551       f[i].bin = tb;
 552       f[i].bin_index = ti;
 553
 554       total_size += heap_elt_size (v, elt_at (h, f[i].index));
 555
 556       if (e == e1)
 557         {
 558           i_last = i;
 559           break;
 560         }
 561     }
 562
 563   /* Compute combined bin.  See if all objects can be
 564      combined into existing bin. */
 565   b = size_to_bin (total_size);
 566   g.index = g.bin_index = 0;
 567   for (i = 0; i <= i_last; i++)
 568     if (b == f[i].bin)
 569       {
 570         g = f[i];
 571         break;
 572       }
 573
 574   /* Make sure we found a bin. */
 575   if (i > i_last)
 576     {
 577       g.index = elt_new (h) - h->elts;
 578       vec_validate (h->free_lists, b);
 579       g.bin_index = vec_len (h->free_lists[b]);
 580       vec_add1 (h->free_lists[b], g.index);
 581       elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
 582     }
 583
 584   g_offset = elt_at (h, f[0].index)->offset;
 585
 586   /* Delete unused bins. */
 587   for (i = 0; i <= i_last; i++)
 588     if (g.index != f[i].index)
 589       {
 590         ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
 591         remove_free_block (v, tb, ti);
 592         elt_delete (h, elt_at (h, f[i].index));
 593       }
 594
 595   /* Initialize new element. */
 596   elt_at (h, g.index)->offset = g_offset;
 597   set_free_elt (v, elt_at (h, g.index), g.bin_index);
 598 }
 599
 600 uword
 601 heap_len (void *v, word handle)
 602 {
 603   heap_header_t *h = heap_header (v);
 604
 605   if (CLIB_DEBUG > 0)
 606     ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
 607   return heap_elt_size (v, elt_at (h, handle));
 608 }
 609
 610 void *
 611 _heap_free (void *v)
 612 {
 613   heap_header_t *h = heap_header (v);
 614   uword b;
 615
 616   if (!v)
 617     return v;
 618
 619   clib_bitmap_free (h->used_elt_bitmap);
 620   for (b = 0; b < vec_len (h->free_lists); b++)
 621     vec_free (h->free_lists[b]);
 622   vec_free (h->free_lists);
 623   vec_free (h->elts);
 624   vec_free (h->free_elts);
 625   vec_free (h->small_free_elt_free_index);
 626   if (!(h->flags & HEAP_IS_STATIC))
 627     vec_free_h (v, sizeof (h[0]));
 628   return v;
 629 }
 630
 631 uword
 632 heap_bytes (void *v)
 633 {
 634   heap_header_t *h = heap_header (v);
 635   uword bytes, b;
 636
 637   if (!v)
 638     return 0;
 639
 640   bytes = sizeof (h[0]);
 641   bytes += vec_len (v) * sizeof (h->elt_bytes);
 642   for (b = 0; b < vec_len (h->free_lists); b++)
 643     bytes += vec_capacity (h->free_lists[b], 0);
 644   bytes += vec_bytes (h->free_lists);
 645   bytes += vec_capacity (h->elts, 0);
 646   bytes += vec_capacity (h->free_elts, 0);
 647   bytes += vec_bytes (h->used_elt_bitmap);
 648
 649   return bytes;
 650 }
 651
 652 static u8 *
 653 debug_elt (u8 * s, void *v, word i, word n)
 654 {
 655   heap_elt_t *e, *e0, *e1;
 656   heap_header_t *h = heap_header (v);
 657   word j;
 658
 659   if (vec_len (h->elts) == 0)
 660     return s;
 661
 662   if (i < 0)
 663     e0 = first (h);
 664   else
 665     {
 666       e0 = h->elts + i;
 667       for (j = 0; j < n / 2; j++)
 668         e0 = heap_prev (e0);
 669     }
 670
 671   if (n < 0)
 672     e1 = h->elts + h->tail;
 673   else
 674     {
 675       e1 = h->elts + i;
 676       for (j = 0; j < n / 2; j++)
 677         e1 = heap_next (e1);
 678     }
 679
 680   i = -n / 2;
 681   for (e = e0; 1; e = heap_next (e))
 682     {
 683       if (heap_is_free (e))
 684         s = format (s, "index %4d, free\n", e - h->elts);
 685       else if (h->format_elt)
 686         s = format (s, "%U", h->format_elt, v, elt_data (v, e));
 687       else
 688         s = format (s, "index %4d, used\n", e - h->elts);
 689       i++;
 690       if (e == e1)
 691         break;
 692     }
 693
 694   return s;
 695 }
 696
 697 u8 *
 698 format_heap (u8 * s, va_list * va)
 699 {
 700   void *v = va_arg (*va, void *);
 701   uword verbose = va_arg (*va, uword);
 702   heap_header_t *h = heap_header (v);
 703   heap_header_t zero;
 704
 705   clib_memset (&zero, 0, sizeof (zero));
 706
 707   if (!v)
 708     h = &zero;
 709
 710   {
 711     f64 elt_bytes = vec_len (v) * h->elt_bytes;
 712     f64 overhead_bytes = heap_bytes (v);
 713
 714     s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
 715                 v, h->used_count, elt_bytes / 1024,
 716                 (overhead_bytes - elt_bytes) / 1024);
 717   }
 718
 719   if (v && verbose)
 720     s = debug_elt (s, v, -1, -1);
 721
 722   return s;
 723 }
 724
 725 void
 726 heap_validate (void *v)
 727 {
 728   heap_header_t *h = heap_header (v);
 729   uword i, o, s;
 730   u8 *free_map;
 731   heap_elt_t *e, *n;
 732
 733   uword used_count, total_size;
 734   uword free_count, free_size;
 735
 736   ASSERT (h->used_count == clib_bitmap_count_set_bits (h->used_elt_bitmap));
 737
 738   ASSERT (first (h)->prev == 0);
 739   ASSERT (last (h)->next == 0);
 740
 741   /* Validate number of elements and size. */
 742   free_size = free_count = 0;
 743   for (i = 0; i < vec_len (h->free_lists); i++)
 744     {
 745       free_count += vec_len (h->free_lists[i]);
 746       for (o = 0; o < vec_len (h->free_lists[i]); o++)
 747         {
 748           e = h->elts + h->free_lists[i][o];
 749           s = heap_elt_size (v, e);
 750           ASSERT (size_to_bin (s) == i);
 751           ASSERT (heap_is_free (e));
 752           free_size += s;
 753         }
 754     }
 755
 756   {
 757     uword elt_free_size, elt_free_count;
 758
 759     used_count = total_size = elt_free_size = elt_free_count = 0;
 760     for (e = first (h); 1; e = n)
 761       {
 762         int is_free = heap_is_free (e);
 763         used_count++;
 764         s = heap_elt_size (v, e);
 765         total_size += s;
 766         ASSERT (is_free ==
 767                 !clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
 768         if (is_free)
 769           {
 770             elt_free_count++;
 771             elt_free_size += s;
 772           }
 773         n = heap_next (e);
 774         if (e == n)
 775           {
 776             ASSERT (last (h) == n);
 777             break;
 778           }
 779
 780         /* We should never have two free adjacent elements. */
 781         ASSERT (!(heap_is_free (e) && heap_is_free (n)));
 782       }
 783
 784     ASSERT (free_count == elt_free_count);
 785     ASSERT (free_size == elt_free_size);
 786     ASSERT (used_count == h->used_count + free_count);
 787     ASSERT (total_size == vec_len (v));
 788   }
 789
 790   free_map = vec_new (u8, used_count);
 791
 792   e = first (h);
 793   for (i = o = 0; 1; i++)
 794     {
 795       ASSERT (heap_offset (e) == o);
 796       s = heap_elt_size (v, e);
 797
 798       if (heap_is_free (e))
 799         {
 800           uword fb, fi;
 801
 802           fi = get_free_elt (v, e, &fb);
 803
 804           ASSERT (fb < vec_len (h->free_lists));
 805           ASSERT (fi < vec_len (h->free_lists[fb]));
 806           ASSERT (h->free_lists[fb][fi] == e - h->elts);
 807
 808           ASSERT (!free_map[i]);
 809           free_map[i] = 1;
 810         }
 811
 812       n = heap_next (e);
 813
 814       if (e == n)
 815         break;
 816
 817       ASSERT (heap_prev (n) == e);
 818
 819       o += s;
 820       e = n;
 821     }
 822
 823   vec_free (free_map);
 824 }
 825
 826 /*
 827  * fd.io coding-style-patch-verification: ON
 828  *
 829  * Local Variables:
 830  * eval: (c-set-style "gnu")
 831  * End:
 832  */