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