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