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 __clib_export 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_realloc (v, offset + align_size, elt_bytes, sizeof (h[0]),
 426                           HEAP_DATA_ALIGN, 0);
 427       else
 428         _vec_len (v) += align_size;
 429
 430       if (offset == 0)
 431         {
 432           h = heap_header (v);
 433           h->elt_bytes = elt_bytes;
 434         }
 435     }
 436
 437   h = heap_header (v);
 438
 439   /* Add new element to doubly linked chain of elements. */
 440   if (!e)
 441     {
 442       e = elt_new (h);
 443       e->offset = offset;
 444       elt_insert_after (h, last (h), e);
 445     }
 446
 447   if (align > 0)
 448     {
 449       uword e_index;
 450       uword new_offset, old_offset;
 451
 452       old_offset = e->offset;
 453       new_offset = (old_offset + align - 1) & ~(align - 1);
 454       e->offset = new_offset;
 455       e_index = e - h->elts;
 456
 457       /* Free fragments before and after aligned object. */
 458       if (new_offset > old_offset)
 459         {
 460           heap_elt_t *before_e = elt_new (h);
 461           before_e->offset = old_offset;
 462           elt_insert_before (h, h->elts + e_index, before_e);
 463           dealloc_elt (v, before_e);
 464         }
 465
 466       if (new_offset + size < old_offset + align_size)
 467         {
 468           heap_elt_t *after_e = elt_new (h);
 469           after_e->offset = new_offset + size;
 470           elt_insert_after (h, h->elts + e_index, after_e);
 471           dealloc_elt (v, after_e);
 472         }
 473
 474       e = h->elts + e_index;
 475     }
 476
 477   h->used_count++;
 478
 479   /* Keep track of used elements when debugging.
 480      This allows deallocation to check that passed objects are valid. */
 481   if (CLIB_DEBUG > 0)
 482     {
 483       uword handle = e - h->elts;
 484       ASSERT (!clib_bitmap_get (h->used_elt_bitmap, handle));
 485       h->used_elt_bitmap = clib_bitmap_ori (h->used_elt_bitmap, handle);
 486     }
 487
 488   *offset_return = e->offset;
 489   *handle_return = e - h->elts;
 490   return v;
 491
 492 error:
 493   *offset_return = *handle_return = ~0;
 494   return v;
 495 }
 496
 497 __clib_export void
 498 heap_dealloc (void *v, uword handle)
 499 {
 500   heap_header_t *h = heap_header (v);
 501   heap_elt_t *e;
 502
 503   ASSERT (handle < vec_len (h->elts));
 504
 505   /* For debugging we keep track of indices for valid objects.
 506      We make sure user is not trying to free object with an invalid index. */
 507   if (CLIB_DEBUG > 0)
 508     {
 509       ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
 510       h->used_elt_bitmap = clib_bitmap_andnoti (h->used_elt_bitmap, handle);
 511     }
 512
 513   h->used_count--;
 514
 515   e = h->elts + handle;
 516   ASSERT (!heap_is_free (e));
 517
 518   dealloc_elt (v, e);
 519 }
 520
 521 /* While freeing objects at INDEX we noticed free blocks i0 <= index and
 522    i1 >= index.  We combine these two or three blocks into one big free block. */
 523 static void
 524 combine_free_blocks (void *v, heap_elt_t * e0, heap_elt_t * e1)
 525 {
 526   heap_header_t *h = heap_header (v);
 527   uword total_size, i, b, tb, ti, i_last, g_offset;
 528   heap_elt_t *e;
 529
 530   struct
 531   {
 532     u32 index;
 533     u32 bin;
 534     u32 bin_index;
 535   } f[3], g;
 536
 537   /* Compute total size of free objects i0 through i1. */
 538   total_size = 0;
 539   for (i = 0, e = e0; 1; e = heap_next (e), i++)
 540     {
 541       ASSERT (i < ARRAY_LEN (f));
 542
 543       ti = get_free_elt (v, e, &tb);
 544
 545       ASSERT (tb < vec_len (h->free_lists));
 546       ASSERT (ti < vec_len (h->free_lists[tb]));
 547
 548       f[i].index = h->free_lists[tb][ti];
 549       f[i].bin = tb;
 550       f[i].bin_index = ti;
 551
 552       total_size += heap_elt_size (v, elt_at (h, f[i].index));
 553
 554       if (e == e1)
 555         {
 556           i_last = i;
 557           break;
 558         }
 559     }
 560
 561   /* Compute combined bin.  See if all objects can be
 562      combined into existing bin. */
 563   b = size_to_bin (total_size);
 564   g.index = g.bin_index = 0;
 565   for (i = 0; i <= i_last; i++)
 566     if (b == f[i].bin)
 567       {
 568         g = f[i];
 569         break;
 570       }
 571
 572   /* Make sure we found a bin. */
 573   if (i > i_last)
 574     {
 575       g.index = elt_new (h) - h->elts;
 576       vec_validate (h->free_lists, b);
 577       g.bin_index = vec_len (h->free_lists[b]);
 578       vec_add1 (h->free_lists[b], g.index);
 579       elt_insert_before (h, elt_at (h, f[0].index), elt_at (h, g.index));
 580     }
 581
 582   g_offset = elt_at (h, f[0].index)->offset;
 583
 584   /* Delete unused bins. */
 585   for (i = 0; i <= i_last; i++)
 586     if (g.index != f[i].index)
 587       {
 588         ti = get_free_elt (v, elt_at (h, f[i].index), &tb);
 589         remove_free_block (v, tb, ti);
 590         elt_delete (h, elt_at (h, f[i].index));
 591       }
 592
 593   /* Initialize new element. */
 594   elt_at (h, g.index)->offset = g_offset;
 595   set_free_elt (v, elt_at (h, g.index), g.bin_index);
 596 }
 597
 598 __clib_export uword
 599 heap_len (void *v, word handle)
 600 {
 601   heap_header_t *h = heap_header (v);
 602
 603   if (CLIB_DEBUG > 0)
 604     ASSERT (clib_bitmap_get (h->used_elt_bitmap, handle));
 605   return heap_elt_size (v, elt_at (h, handle));
 606 }
 607
 608 __clib_export void *
 609 _heap_free (void *v)
 610 {
 611   heap_header_t *h = heap_header (v);
 612   uword b;
 613
 614   if (!v)
 615     return v;
 616
 617   clib_bitmap_free (h->used_elt_bitmap);
 618   for (b = 0; b < vec_len (h->free_lists); b++)
 619     vec_free (h->free_lists[b]);
 620   vec_free (h->free_lists);
 621   vec_free (h->elts);
 622   vec_free (h->free_elts);
 623   vec_free (h->small_free_elt_free_index);
 624   if (!(h->flags & HEAP_IS_STATIC))
 625     vec_free (v);
 626   return v;
 627 }
 628
 629 uword
 630 heap_bytes (void *v)
 631 {
 632   heap_header_t *h = heap_header (v);
 633   uword bytes, b;
 634
 635   if (!v)
 636     return 0;
 637
 638   bytes = sizeof (h[0]);
 639   bytes += vec_len (v) * sizeof (h->elt_bytes);
 640   for (b = 0; b < vec_len (h->free_lists); b++)
 641     bytes += vec_mem_size (h->free_lists[b]);
 642   bytes += vec_bytes (h->free_lists);
 643   bytes += vec_mem_size (h->elts);
 644   bytes += vec_mem_size (h->free_elts);
 645   bytes += vec_bytes (h->used_elt_bitmap);
 646
 647   return bytes;
 648 }
 649
 650 static u8 *
 651 debug_elt (u8 * s, void *v, word i, word n)
 652 {
 653   heap_elt_t *e, *e0, *e1;
 654   heap_header_t *h = heap_header (v);
 655   word j;
 656
 657   if (vec_len (h->elts) == 0)
 658     return s;
 659
 660   if (i < 0)
 661     e0 = first (h);
 662   else
 663     {
 664       e0 = h->elts + i;
 665       for (j = 0; j < n / 2; j++)
 666         e0 = heap_prev (e0);
 667     }
 668
 669   if (n < 0)
 670     e1 = h->elts + h->tail;
 671   else
 672     {
 673       e1 = h->elts + i;
 674       for (j = 0; j < n / 2; j++)
 675         e1 = heap_next (e1);
 676     }
 677
 678   i = -n / 2;
 679   for (e = e0; 1; e = heap_next (e))
 680     {
 681       if (heap_is_free (e))
 682         s = format (s, "index %4d, free\n", e - h->elts);
 683       else if (h->format_elt)
 684         s = format (s, "%U", h->format_elt, v, elt_data (v, e));
 685       else
 686         s = format (s, "index %4d, used\n", e - h->elts);
 687       i++;
 688       if (e == e1)
 689         break;
 690     }
 691
 692   return s;
 693 }
 694
 695 __clib_export u8 *
 696 format_heap (u8 *s, va_list *va)
 697 {
 698   void *v = va_arg (*va, void *);
 699   uword verbose = va_arg (*va, uword);
 700   heap_header_t *h = heap_header (v);
 701   heap_header_t zero;
 702
 703   clib_memset (&zero, 0, sizeof (zero));
 704
 705   if (!v)
 706     h = &zero;
 707
 708   {
 709     f64 elt_bytes = vec_len (v) * h->elt_bytes;
 710     f64 overhead_bytes = heap_bytes (v);
 711
 712     s = format (s, "heap %p, %6d objects, size %.1fk + overhead %.1fk\n",
 713                 v, h->used_count, elt_bytes / 1024,
 714                 (overhead_bytes - elt_bytes) / 1024);
 715   }
 716
 717   if (v && verbose)
 718     s = debug_elt (s, v, -1, -1);
 719
 720   return s;
 721 }
 722
 723 __clib_export void
 724 heap_validate (void *v)
 725 {
 726   heap_header_t *h = heap_header (v);
 727   uword i, o, s;
 728   u8 *free_map;
 729   heap_elt_t *e, *n;
 730
 731   uword used_count, total_size;
 732   uword free_count, free_size;
 733
 734   ASSERT (h->used_count == clib_bitmap_count_set_bits (h->used_elt_bitmap));
 735
 736   ASSERT (first (h)->prev == 0);
 737   ASSERT (last (h)->next == 0);
 738
 739   /* Validate number of elements and size. */
 740   free_size = free_count = 0;
 741   for (i = 0; i < vec_len (h->free_lists); i++)
 742     {
 743       free_count += vec_len (h->free_lists[i]);
 744       for (o = 0; o < vec_len (h->free_lists[i]); o++)
 745         {
 746           e = h->elts + h->free_lists[i][o];
 747           s = heap_elt_size (v, e);
 748           ASSERT (size_to_bin (s) == i);
 749           ASSERT (heap_is_free (e));
 750           free_size += s;
 751         }
 752     }
 753
 754   {
 755     uword elt_free_size, elt_free_count;
 756
 757     used_count = total_size = elt_free_size = elt_free_count = 0;
 758     for (e = first (h); 1; e = n)
 759       {
 760         int is_free = heap_is_free (e);
 761         used_count++;
 762         s = heap_elt_size (v, e);
 763         total_size += s;
 764         ASSERT (is_free ==
 765                 !clib_bitmap_get (h->used_elt_bitmap, e - h->elts));
 766         if (is_free)
 767           {
 768             elt_free_count++;
 769             elt_free_size += s;
 770           }
 771         n = heap_next (e);
 772         if (e == n)
 773           {
 774             ASSERT (last (h) == n);
 775             break;
 776           }
 777
 778         /* We should never have two free adjacent elements. */
 779         ASSERT (!(heap_is_free (e) && heap_is_free (n)));
 780       }
 781
 782     ASSERT (free_count == elt_free_count);
 783     ASSERT (free_size == elt_free_size);
 784     ASSERT (used_count == h->used_count + free_count);
 785     ASSERT (total_size == vec_len (v));
 786   }
 787
 788   free_map = vec_new (u8, used_count);
 789
 790   e = first (h);
 791   for (i = o = 0; 1; i++)
 792     {
 793       ASSERT (heap_offset (e) == o);
 794       s = heap_elt_size (v, e);
 795
 796       if (heap_is_free (e))
 797         {
 798           uword fb, fi;
 799
 800           fi = get_free_elt (v, e, &fb);
 801
 802           ASSERT (fb < vec_len (h->free_lists));
 803           ASSERT (fi < vec_len (h->free_lists[fb]));
 804           ASSERT (h->free_lists[fb][fi] == e - h->elts);
 805
 806           ASSERT (!free_map[i]);
 807           free_map[i] = 1;
 808         }
 809
 810       n = heap_next (e);
 811
 812       if (e == n)
 813         break;
 814
 815       ASSERT (heap_prev (n) == e);
 816
 817       o += s;
 818       e = n;
 819     }
 820
 821   vec_free (free_map);
 822 }
 823
 824 /*
 825  * fd.io coding-style-patch-verification: ON
 826  *
 827  * Local Variables:
 828  * eval: (c-set-style "gnu")
 829  * End:
 830  */