git.ozlabs.org Git - ccan/blob - alloc/alloc.c

   1 #include <unistd.h>
   2 #include <stdint.h>
   3 #include <string.h>
   4 #include <limits.h>
   5 #include <assert.h>
   6 #include "alloc.h"
   7 #include "build_assert/build_assert.h"
   8 #include "config.h"
   9
  10 #if HAVE_ALIGNOF
  11 #define ALIGNOF(t) __alignof__(t)
  12 #else
  13 /* Alignment by measuring structure padding. */
  14 #define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
  15 #endif
  16
  17 /* FIXME: Doesn't handle non-page-aligned poolsize. */
  18
  19 /* FIXME: Reduce. */
  20 #define MIN_SIZE (getpagesize() * 2)
  21
  22 /* What's the granularity of sub-page allocs? */
  23 #define BITMAP_GRANULARITY 4
  24
  25 /* File layout:
  26  *
  27  *  file := pagestates pad metadata
  28  *  pagestates := pages * 2-bits-per-page
  29  *  pad := pad to next ALIGNOF(metadata)
  30  *
  31  *  metadata := metalen next-ptr metabits
  32  *  metabits := freeblock | bitblock
  33  *  freeblock := 0+
  34  *  bitblock := 2-bits-per-bit-in-page 1
  35  */
  36 struct metaheader
  37 {
  38         /* Length (after this header).  (FIXME: implied by page bits!). */
  39         unsigned long metalen;
  40         /* Next meta header, or 0 */
  41         unsigned long next;
  42         /* Bits start here. */
  43 };
  44
  45 /* Assumes a is a power of two. */
  46 static unsigned long align_up(unsigned long x, unsigned long a)
  47 {
  48         return (x + a - 1) & ~(a - 1);
  49 }
  50
  51 static unsigned long div_up(unsigned long x, unsigned long a)
  52 {
  53         return (x + a - 1) / a;
  54 }
  55
  56 /* It turns out that we spend a lot of time dealing with bit pairs.
  57  * These routines manipulate them.
  58  */
  59 static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
  60 {
  61         return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
  62 }
  63
  64 static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
  65 {
  66         bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
  67         bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
  68 }
  69
  70 /* This is used for page states and subpage allocations */
  71 enum alloc_state
  72 {
  73         FREE,
  74         TAKEN,
  75         TAKEN_START,
  76         SPECIAL,        /* Sub-page allocation for page states. */
  77 };
  78
  79 /* The types for subpage metadata. */
  80 enum sub_metadata_type
  81 {
  82         /* FREE is same as alloc state */
  83         BITMAP = 1,
  84 };
  85
  86 /* Page states are represented by bitpairs, at the start of the pool. */
  87 #define BITS_PER_PAGE 2
  88
  89 static enum alloc_state get_page_state(const void *pool, unsigned long page)
  90 {
  91         return get_bit_pair(pool, page);
  92 }
  93
  94 static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
  95 {
  96         set_bit_pair(pool, page, s);
  97 }
  98
  99 /* The offset of metadata for a subpage allocation is found at the end
 100  * of the subpage */
 101 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
 102
 103 /* This is the length of metadata in bits.  It consists of two bits
 104  * for every BITMAP_GRANULARITY of usable bytes in the page, then two
 105  * bits for the tailer.. */
 106 #define BITMAP_METABITLEN                                               \
 107     ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
 108
 109 /* This is the length in bytes. */
 110 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
 111
 112 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
 113 {
 114         unsigned int pagestatelen;
 115
 116         pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
 117                                        CHAR_BIT),
 118                                 ALIGNOF(struct metaheader));
 119         return (struct metaheader *)((char *)pool + pagestatelen);
 120 }
 121
 122 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
 123 {
 124         if (!mh->next)
 125                 return NULL;
 126
 127         return (struct metaheader *)((char *)pool + mh->next);
 128 }
 129
 130 static unsigned long pool_offset(void *pool, void *p)
 131 {
 132         return (char *)p - (char *)pool;
 133 }
 134
 135 void alloc_init(void *pool, unsigned long poolsize)
 136 {
 137         /* FIXME: Alignment assumptions about pool. */
 138         unsigned long len, i;
 139         struct metaheader *mh;
 140
 141         if (poolsize < MIN_SIZE)
 142                 return;
 143
 144         mh = first_mheader(pool, poolsize);
 145
 146         /* Mark all page states FREE, and all of metaheader bitmap which takes
 147          * rest of first page. */
 148         len = align_up(pool_offset(pool, mh + 1), getpagesize());
 149         BUILD_ASSERT(FREE == 0);
 150         memset(pool, 0, len);
 151
 152         /* Set up metalen */
 153         mh->metalen = len - pool_offset(pool, mh + 1);
 154
 155         /* Mark the pagestate and metadata page(s) allocated. */
 156         set_page_state(pool, 0, TAKEN_START);
 157         for (i = 1; i < div_up(len, getpagesize()); i++)
 158                 set_page_state(pool, i, TAKEN);
 159 }
 160
 161 /* Two bits per element, representing page states.  Returns 0 on fail.
 162  * off is used to allocate from subpage bitmaps, which use the first 2
 163  * bits as the type, so the real bitmap is offset by 1. */
 164 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
 165                                        unsigned long elems,
 166                                        unsigned long want, unsigned long align)
 167 {
 168         long i;
 169         unsigned long free;
 170
 171         free = 0;
 172         /* We allocate from far end, to increase ability to expand metadata. */
 173         for (i = elems - 1; i >= 0; i--) {
 174                 switch (get_bit_pair(bits, off+i)) {
 175                 case FREE:
 176                         if (++free >= want) {
 177                                 unsigned long j;
 178
 179                                 /* They might ask for large alignment. */
 180                                 if (align && i % align)
 181                                         continue;
 182
 183                                 set_bit_pair(bits, off+i, TAKEN_START);
 184                                 for (j = i+1; j < i + want; j++)
 185                                         set_bit_pair(bits, off+j, TAKEN);
 186                                 return off+i;
 187                         }
 188                         break;
 189                 case SPECIAL:
 190                 case TAKEN_START:
 191                 case TAKEN:
 192                         free = 0;
 193                         break;
 194                 }
 195         }
 196
 197         return 0;
 198 }
 199
 200 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
 201                                      unsigned long pages, unsigned long align)
 202 {
 203         return alloc_from_bitmap(pool, 0, poolsize / getpagesize(), pages,
 204                                  align / getpagesize());
 205 }
 206
 207 /* Offset to metadata is at end of page. */
 208 static unsigned long *metadata_off(void *pool, unsigned long page)
 209 {
 210         return (unsigned long *)
 211                 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
 212 }
 213
 214 static uint8_t *get_page_metadata(void *pool, unsigned long page)
 215 {
 216         return (uint8_t *)pool + *metadata_off(pool, page);
 217 }
 218
 219 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
 220 {
 221         *metadata_off(pool, page) = meta - (uint8_t *)pool;
 222 }
 223
 224 static unsigned long sub_page_alloc(void *pool, unsigned long page,
 225                                     unsigned long size, unsigned long align)
 226 {
 227         uint8_t *bits = get_page_metadata(pool, page);
 228         unsigned long i;
 229
 230         /* TAKEN at start means a bitwise alloc. */
 231         assert(get_bit_pair(bits, 0) == BITMAP);
 232
 233         /* We use a standart bitmap, but offset because of that BITMAP
 234          * header. */
 235         i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
 236                               div_up(size, BITMAP_GRANULARITY),
 237                               align / BITMAP_GRANULARITY);
 238
 239         /* Can't allocate? */
 240         if (i == 0)
 241                 return 0;
 242
 243         /* i-1 because of the header. */
 244         return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
 245 }
 246
 247 static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes,
 248                                 enum sub_metadata_type type)
 249 {
 250         uint8_t *meta = (uint8_t *)(mh + 1);
 251         unsigned long free = 0, len;
 252         unsigned long i;
 253
 254         /* TAKEN tags end a subpage alloc. */
 255         for (i = 0; i < mh->metalen * CHAR_BIT / BITS_PER_PAGE; i += len) {
 256                 switch (get_bit_pair(meta, i)) {
 257                 case FREE:
 258                         len = 1;
 259                         free++;
 260                         if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
 261                                 /* Mark this as a bitmap. */
 262                                 set_bit_pair(meta, i - free + 1, type);
 263                                 return meta + (i - free + 1)
 264                                         / (CHAR_BIT / BITS_PER_PAGE);
 265                         }
 266                         break;
 267                 case BITMAP:
 268                         /* Skip over this allocated part. */
 269                         len = BITMAP_METALEN * CHAR_BIT / BITS_PER_PAGE;
 270                         free = 0;
 271                         break;
 272                 default:
 273                         assert(0);
 274                         return NULL;
 275                 }
 276         }
 277         return NULL;
 278 }
 279
 280 /* We need this many bytes of metadata. */
 281 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
 282                              unsigned long bytes, enum sub_metadata_type type)
 283 {
 284         struct metaheader *mh, *newmh;
 285         unsigned long page;
 286
 287         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 288                 uint8_t *meta = alloc_metaspace(mh, bytes, type);
 289
 290                 if (meta)
 291                         return meta;
 292         }
 293
 294         /* No room for metadata?  Can we expand an existing one? */
 295         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 296                 /* It should end on a page boundary. */
 297                 unsigned long nextpage;
 298
 299                 nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
 300                 assert(nextpage % getpagesize() == 0);
 301
 302                 /* Now, can we grab that page? */
 303                 if (get_page_state(pool, nextpage / getpagesize()) != FREE)
 304                         continue;
 305
 306                 /* OK, expand metadata, do it again. */
 307                 set_page_state(pool, nextpage / getpagesize(), TAKEN);
 308                 BUILD_ASSERT(FREE == 0);
 309                 memset((char *)pool + nextpage, 0, getpagesize());
 310                 mh->metalen += getpagesize();
 311                 return alloc_metaspace(mh, bytes, type);
 312         }
 313
 314         /* No metadata left at all? */
 315         page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
 316         if (!page)
 317                 return NULL;
 318
 319         newmh = (struct metaheader *)((char *)pool + page * getpagesize());
 320         newmh->metalen = getpagesize() - sizeof(*mh);
 321         BUILD_ASSERT(FREE == 0);
 322         memset(newmh + 1, 0, newmh->metalen);
 323
 324         /* Sew it into linked list */
 325         mh = first_mheader(pool,poolsize);
 326         newmh->next = mh->next;
 327         mh->next = pool_offset(pool, newmh);
 328
 329         return alloc_metaspace(newmh, bytes, type);
 330 }
 331
 332 static void alloc_free_pages(void *pool, unsigned long pagenum)
 333 {
 334         assert(get_page_state(pool, pagenum) == TAKEN_START);
 335         set_page_state(pool, pagenum, FREE);
 336         while (get_page_state(pool, ++pagenum) == TAKEN)
 337                 set_page_state(pool, pagenum, FREE);
 338 }
 339
 340 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
 341                                     unsigned long size, unsigned long align)
 342 {
 343         unsigned long i;
 344         uint8_t *metadata;
 345
 346         /* Look for partial page. */
 347         for (i = 0; i < poolsize / getpagesize(); i++) {
 348                 unsigned long ret;
 349                 if (get_page_state(pool, i) != SPECIAL)
 350                         continue;
 351
 352                 ret = sub_page_alloc(pool, i, size, align);
 353                 if (ret)
 354                         return ret;
 355         }
 356
 357         /* Create new SUBPAGE page. */
 358         i = alloc_get_pages(pool, poolsize, 1, 1);
 359         if (i == 0)
 360                 return 0;
 361
 362         /* Get metadata for page. */
 363         metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
 364         if (!metadata) {
 365                 alloc_free_pages(pool, i);
 366                 return 0;
 367         }
 368
 369         /* Actually, this is a subpage page now. */
 370         set_page_state(pool, i, SPECIAL);
 371
 372         /* Set metadata pointer for page. */
 373         set_page_metadata(pool, i, metadata);
 374
 375         /* Do allocation like normal */
 376         return sub_page_alloc(pool, i, size, align);
 377 }
 378
 379 /* Returns true if we cleaned any pages. */
 380 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
 381 {
 382         unsigned long i;
 383         bool progress = false;
 384
 385         for (i = 0; i < poolsize/getpagesize(); i++) {
 386                 uint8_t *meta;
 387                 unsigned int j;
 388                 if (get_page_state(pool, i) != SPECIAL)
 389                         continue;
 390
 391                 meta = get_page_metadata(pool, i);
 392                 /* Skip the header (first bit of metadata). */
 393                 for (j = 1; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; j++)
 394                         if (get_bit_pair(meta, j) != FREE)
 395                                 break;
 396
 397                 /* So, is this page totally empty? */
 398                 if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY+1) {
 399                         set_page_state(pool, i, FREE);
 400                         progress = true;
 401                 }
 402         }
 403         return progress;
 404 }
 405
 406 /* Returns true if we cleaned any pages. */
 407 static bool clean_metadata(void *pool, unsigned long poolsize)
 408 {
 409         struct metaheader *mh, *prev_mh = NULL;
 410         bool progress = false;
 411
 412         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 413                 uint8_t *meta;
 414                 long i;
 415
 416                 meta = (uint8_t *)(mh + 1);
 417                 BUILD_ASSERT(FREE == 0);
 418                 for (i = mh->metalen - 1; i > 0; i--)
 419                         if (meta[i] != 0)
 420                                 break;
 421
 422                 /* Completely empty? */
 423                 if (prev_mh && i == mh->metalen) {
 424                         alloc_free_pages(pool,
 425                                          pool_offset(pool, mh)/getpagesize());
 426                         prev_mh->next = mh->next;
 427                         mh = prev_mh;
 428                         progress = true;
 429                 } else {
 430                         uint8_t *p;
 431
 432                         /* Some pages at end are free? */
 433                         for (p = (uint8_t *)(mh+1)+mh->metalen - getpagesize();
 434                              p > meta + i;
 435                              p -= getpagesize()) {
 436                                 set_page_state(pool,
 437                                                pool_offset(pool, p)
 438                                                / getpagesize(),
 439                                                FREE);
 440                                 progress = true;
 441                         }
 442                 }
 443         }
 444
 445         return progress;
 446 }
 447
 448 void *alloc_get(void *pool, unsigned long poolsize,
 449                 unsigned long size, unsigned long align)
 450 {
 451         bool subpage_clean = false, metadata_clean = false;
 452         unsigned long ret;
 453
 454         if (poolsize < MIN_SIZE)
 455                 return NULL;
 456
 457 again:
 458         /* Sub-page allocations have an overhead of ~12%. */
 459         if (size + size/8 >= getpagesize() || align >= getpagesize()) {
 460                 unsigned long pages = div_up(size, getpagesize());
 461
 462                 ret = alloc_get_pages(pool, poolsize, pages, align)
 463                         * getpagesize();
 464         } else
 465                 ret = alloc_sub_page(pool, poolsize, size, align);
 466
 467         if (ret != 0)
 468                 return (char *)pool + ret;
 469
 470         /* Allocation failed: garbage collection. */
 471         if (!subpage_clean) {
 472                 subpage_clean = true;
 473                 if (clean_empty_subpages(pool, poolsize))
 474                         goto again;
 475         }
 476
 477         if (!metadata_clean) {
 478                 metadata_clean = true;
 479                 if (clean_metadata(pool, poolsize))
 480                         goto again;
 481         }
 482
 483         /* FIXME: Compact metadata? */
 484         return NULL;
 485 }
 486
 487 static void subpage_free(void *pool, unsigned long pagenum, void *free)
 488 {
 489         unsigned long off = (unsigned long)free % getpagesize();
 490         uint8_t *metadata;
 491
 492         assert(off < SUBPAGE_METAOFF);
 493         assert(off % BITMAP_GRANULARITY == 0);
 494
 495         metadata = get_page_metadata(pool, pagenum);
 496
 497         off /= BITMAP_GRANULARITY;
 498
 499         /* Offset by one because first bit is used for header. */
 500         off++;
 501
 502         set_bit_pair(metadata, off++, FREE);
 503         while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
 504                && get_bit_pair(metadata, off) == TAKEN)
 505                 set_bit_pair(metadata, off++, FREE);
 506 }
 507
 508 void alloc_free(void *pool, unsigned long poolsize, void *free)
 509 {
 510         unsigned long pagenum;
 511         struct metaheader *mh;
 512
 513         if (!free)
 514                 return;
 515
 516         assert(poolsize >= MIN_SIZE);
 517
 518         mh = first_mheader(pool, poolsize);
 519         assert((char *)free >= (char *)(mh + 1) + mh->metalen);
 520         assert((char *)pool + poolsize > (char *)free);
 521
 522         pagenum = pool_offset(pool, free) / getpagesize();
 523
 524         if (get_page_state(pool, pagenum) == SPECIAL)
 525                 subpage_free(pool, pagenum, free);
 526         else {
 527                 assert((unsigned long)free % getpagesize() == 0);
 528                 alloc_free_pages(pool, pagenum);
 529         }
 530 }
 531
 532 static bool is_metadata_page(void *pool, unsigned long poolsize,
 533                              unsigned long page)
 534 {
 535         struct metaheader *mh;
 536
 537         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 538                 unsigned long start, end;
 539
 540                 start = pool_offset(pool, mh);
 541                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
 542                 if (page >= start/getpagesize() && page < end/getpagesize())
 543                         return true;
 544         }
 545         return false;
 546 }
 547
 548 static bool check_subpage(void *pool, unsigned long poolsize,
 549                           unsigned long page)
 550 {
 551         unsigned long *mhoff = metadata_off(pool, page);
 552         unsigned int i;
 553         enum alloc_state last_state = FREE;
 554
 555         if (*mhoff + sizeof(struct metaheader) > poolsize)
 556                 return false;
 557
 558         if (*mhoff % ALIGNOF(struct metaheader) != 0)
 559                 return false;
 560
 561         /* It must point to a metadata page. */
 562         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
 563                 return false;
 564
 565         /* Header at start of subpage allocation */
 566         if (get_bit_pair((uint8_t *)pool + *mhoff, 0) != BITMAP)
 567                 return false;
 568
 569         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
 570                 enum alloc_state state;
 571
 572                 /* +1 because header is the first byte. */
 573                 state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
 574                 switch (state) {
 575                 case SPECIAL:
 576                         return false;
 577                 case TAKEN:
 578                         if (last_state == FREE)
 579                                 return false;
 580                         break;
 581                 default:
 582                         break;
 583                 }
 584                 last_state = state;
 585         }
 586         return true;
 587 }
 588
 589 bool alloc_check(void *pool, unsigned long poolsize)
 590 {
 591         unsigned long i;
 592         struct metaheader *mh;
 593         enum alloc_state last_state = FREE;
 594         bool was_metadata = false;
 595
 596         if (poolsize < MIN_SIZE)
 597                 return true;
 598
 599         if (get_page_state(pool, 0) != TAKEN_START)
 600                 return false;
 601
 602         /* First check metadata pages. */
 603         /* Metadata pages will be marked TAKEN. */
 604         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 605                 unsigned long start, end;
 606
 607                 start = pool_offset(pool, mh);
 608                 if (start + sizeof(*mh) > poolsize)
 609                         return false;
 610
 611                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
 612                 if (end > poolsize)
 613                         return false;
 614
 615                 /* Non-first pages should start on a page boundary. */
 616                 if (mh != first_mheader(pool, poolsize)
 617                     && start % getpagesize() != 0)
 618                         return false;
 619
 620                 /* It should end on a page boundary. */
 621                 if (end % getpagesize() != 0)
 622                         return false;
 623         }
 624
 625         for (i = 0; i < poolsize / getpagesize(); i++) {
 626                 enum alloc_state state = get_page_state(pool, i);
 627                 bool is_metadata = is_metadata_page(pool, poolsize,i);
 628
 629                 switch (state) {
 630                 case FREE:
 631                         /* metadata pages are never free. */
 632                         if (is_metadata)
 633                                 return false;
 634                 case TAKEN_START:
 635                         break;
 636                 case TAKEN:
 637                         /* This should continue a previous block. */
 638                         if (last_state == FREE)
 639                                 return false;
 640                         if (is_metadata != was_metadata)
 641                                 return false;
 642                         break;
 643                 case SPECIAL:
 644                         /* Check metadata pointer etc. */
 645                         if (!check_subpage(pool, poolsize, i))
 646                                 return false;
 647                 }
 648                 last_state = state;
 649                 was_metadata = is_metadata;
 650         }
 651         return true;
 652 }
 653
 654 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
 655 {
 656         struct metaheader *mh;
 657         unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
 658         long i;
 659
 660         if (poolsize < MIN_SIZE) {
 661                 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
 662                 return;
 663         }
 664
 665         memset(count, 0, sizeof(count));
 666         for (i = 0; i < poolsize / getpagesize(); i++)
 667                 count[get_page_state(pool, i)]++;
 668
 669         mh = first_mheader(pool, poolsize);
 670         pagebitlen = (char *)mh - (char *)pool;
 671         fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
 672                 pagebitlen, count[0], count[1], count[2], count[3]);
 673
 674         /* One metadata page for every page of page bits. */
 675         metadata_pages = div_up(pagebitlen, getpagesize());
 676
 677         /* Now do each metadata page. */
 678         for (; mh; mh = next_mheader(pool,mh)) {
 679                 unsigned long free = 0, subpageblocks = 0, len = 0;
 680                 uint8_t *meta = (uint8_t *)(mh + 1);
 681
 682                 metadata_pages += (sizeof(*mh) + mh->metalen) / getpagesize();
 683
 684                 for (i = 0;
 685                      i < mh->metalen * CHAR_BIT / BITS_PER_PAGE;
 686                      i += len) {
 687                         switch (get_page_state(meta, i)) {
 688                         case FREE:
 689                                 len = 1;
 690                                 free++;
 691                                 break;
 692                         case BITMAP:
 693                                 /* Skip over this allocated part. */
 694                                 len = BITMAP_METALEN * CHAR_BIT;
 695                                 subpageblocks++;
 696                                 break;
 697                         default:
 698                                 assert(0);
 699                         }
 700                 }
 701
 702                 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
 703                         pool_offset(pool, mh),
 704                         pool_offset(pool, (char *)(mh+1) + mh->metalen),
 705                         free, subpageblocks,
 706                         subpageblocks * BITMAP_METALEN * 100
 707                         / (free + subpageblocks * BITMAP_METALEN));
 708         }
 709
 710         /* Account for total pages allocated. */
 711         tot = (count[1] + count[2] - metadata_pages) * getpagesize();
 712
 713         fprintf(out, "Total metadata bytes = %lu\n",
 714                 metadata_pages * getpagesize());
 715
 716         /* Now do every subpage. */
 717         for (i = 0; i < poolsize / getpagesize(); i++) {
 718                 uint8_t *meta;
 719                 unsigned int j;
 720                 if (get_page_state(pool, i) != SPECIAL)
 721                         continue;
 722
 723                 memset(count, 0, sizeof(count));
 724                 meta = get_page_metadata(pool, i);
 725                 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
 726                         count[get_page_state(meta, j)]++;
 727
 728                 fprintf(out, "Subpage %lu: "
 729                         "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
 730                         i, count[0], count[1], count[2],
 731                         ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
 732                         / getpagesize());
 733                 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
 734         }
 735
 736         /* This is optimistic, since we overalloc in several cases. */
 737         fprintf(out, "Best possible allocation density = %lu%%\n",
 738                 tot * 100 / poolsize);
 739 }