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