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