git.ozlabs.org Git - ccan/blob - ccan/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 <stdlib.h>
   7 #include "alloc.h"
   8 #include <ccan/build_assert/build_assert.h>
   9 #include <ccan/alignof/alignof.h>
  10 #include "config.h"
  11
  12 /* FIXME: We assume getpagesize() doesnt change.  Remapping file with
  13  * different pagesize should still work. */
  14
  15 /* FIXME: Doesn't handle non-page-aligned poolsize. */
  16
  17 /* FIXME: Reduce. */
  18 #define MIN_SIZE (getpagesize() * 2)
  19
  20 /* What's the granularity of sub-page allocs? */
  21 #define BITMAP_GRANULARITY 4
  22
  23 /* File layout:
  24  *
  25  *  file := pagestates pad uniform-cache metadata
  26  *  pagestates := pages * 2-bits-per-page
  27  *  pad := pad to next ALIGNOF(metaheader)
  28  *
  29  *  metadata := metalen next-ptr metabits
  30  *  metabits := freeblock | bitblock | uniformblock
  31  *  freeblock := FREE +
  32  *  bitblock := BITMAP + 2-bits-per-bit-in-page + pad-to-byte
  33  *  uniformblock := UNIFORM + 14-bit-byte-len + bits + pad-to-byte
  34  */
  35 #define UNIFORM_CACHE_NUM 16
  36 struct uniform_cache
  37 {
  38         uint16_t size[UNIFORM_CACHE_NUM];
  39         /* These could be u32 if we're prepared to limit size. */
  40         unsigned long page[UNIFORM_CACHE_NUM];
  41 };
  42
  43 struct metaheader
  44 {
  45         /* Next meta header, or 0 */
  46         unsigned long next;
  47         /* Bits start here. */
  48 };
  49
  50 /* Assumes a is a power of two. */
  51 static unsigned long align_up(unsigned long x, unsigned long a)
  52 {
  53         return (x + a - 1) & ~(a - 1);
  54 }
  55
  56 static unsigned long align_down(unsigned long x, unsigned long a)
  57 {
  58         return x & ~(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 /* It turns out that we spend a lot of time dealing with bit pairs.
  67  * These routines manipulate them.
  68  */
  69 static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
  70 {
  71         return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
  72 }
  73
  74 static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
  75 {
  76         bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
  77         bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
  78 }
  79
  80 /* This is used for page states and subpage allocations */
  81 enum alloc_state
  82 {
  83         FREE,
  84         TAKEN,
  85         TAKEN_START,
  86         SPECIAL,        /* Sub-page allocation for page states. */
  87 };
  88
  89 /* The types for subpage metadata. */
  90 enum sub_metadata_type
  91 {
  92         /* FREE is same as alloc state */
  93         BITMAP = 1, /* bitmap allocated page */
  94         UNIFORM, /* uniform size allocated page */
  95 };
  96
  97 /* Page states are represented by bitpairs, at the start of the pool. */
  98 #define BITS_PER_PAGE 2
  99
 100 /* How much metadata info per byte? */
 101 #define METADATA_PER_BYTE (CHAR_BIT / 2)
 102
 103 static uint8_t *get_page_statebits(const void *pool)
 104 {
 105         return (uint8_t *)pool + sizeof(struct uniform_cache);
 106 }
 107
 108 static enum alloc_state get_page_state(const void *pool, unsigned long page)
 109 {
 110         return get_bit_pair(get_page_statebits(pool), page);
 111 }
 112
 113 static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
 114 {
 115         set_bit_pair(get_page_statebits(pool), page, s);
 116 }
 117
 118 /* The offset of metadata for a subpage allocation is found at the end
 119  * of the subpage */
 120 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
 121
 122 /* This is the length of metadata in bits.  It consists of two bits
 123  * for every BITMAP_GRANULARITY of usable bytes in the page, then two
 124  * bits for the tailer.. */
 125 #define BITMAP_METABITLEN                                               \
 126     ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
 127
 128 /* This is the length in bytes. */
 129 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
 130
 131 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
 132 {
 133         unsigned int pagestatelen;
 134
 135         pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
 136                                        CHAR_BIT),
 137                                 ALIGNOF(struct metaheader));
 138         return (struct metaheader *)(get_page_statebits(pool) + pagestatelen);
 139 }
 140
 141 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
 142 {
 143         if (!mh->next)
 144                 return NULL;
 145
 146         return (struct metaheader *)((char *)pool + mh->next);
 147 }
 148
 149 static unsigned long pool_offset(void *pool, void *p)
 150 {
 151         return (char *)p - (char *)pool;
 152 }
 153
 154 void alloc_init(void *pool, unsigned long poolsize)
 155 {
 156         /* FIXME: Alignment assumptions about pool. */
 157         unsigned long len, i;
 158         struct metaheader *mh;
 159
 160         if (poolsize < MIN_SIZE)
 161                 return;
 162
 163         mh = first_mheader(pool, poolsize);
 164
 165         /* Mark all page states FREE, all uniform caches zero, and all of
 166          * metaheader bitmap which takes rest of first page. */
 167         len = align_up(pool_offset(pool, mh + 1), getpagesize());
 168         BUILD_ASSERT(FREE == 0);
 169         memset(pool, 0, len);
 170
 171         /* Mark the pagestate and metadata page(s) allocated. */
 172         set_page_state(pool, 0, TAKEN_START);
 173         for (i = 1; i < div_up(len, getpagesize()); i++)
 174                 set_page_state(pool, i, TAKEN);
 175 }
 176
 177 /* Two bits per element, representing page states.  Returns 0 on fail.
 178  * off is used to allocate from subpage bitmaps, which use the first 2
 179  * bits as the type, so the real bitmap is offset by 1. */
 180 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
 181                                        unsigned long elems,
 182                                        unsigned long want, unsigned long align)
 183 {
 184         long i;
 185         unsigned long free;
 186
 187         free = 0;
 188         /* We allocate from far end, to increase ability to expand metadata. */
 189         for (i = elems - 1; i >= 0; i--) {
 190                 switch (get_bit_pair(bits, off+i)) {
 191                 case FREE:
 192                         if (++free >= want) {
 193                                 unsigned long j;
 194
 195                                 /* They might ask for large alignment. */
 196                                 if (align && i % align)
 197                                         continue;
 198
 199                                 set_bit_pair(bits, off+i, TAKEN_START);
 200                                 for (j = i+1; j < i + want; j++)
 201                                         set_bit_pair(bits, off+j, TAKEN);
 202                                 return off+i;
 203                         }
 204                         break;
 205                 case SPECIAL:
 206                 case TAKEN_START:
 207                 case TAKEN:
 208                         free = 0;
 209                         break;
 210                 }
 211         }
 212
 213         return 0;
 214 }
 215
 216 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
 217                                      unsigned long pages, unsigned long align)
 218 {
 219         return alloc_from_bitmap(get_page_statebits(pool),
 220                                  0, poolsize / getpagesize(), pages,
 221                                  align / getpagesize());
 222 }
 223
 224 /* Offset to metadata is at end of page. */
 225 static unsigned long *metadata_off(void *pool, unsigned long page)
 226 {
 227         return (unsigned long *)
 228                 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
 229 }
 230
 231 static uint8_t *get_page_metadata(void *pool, unsigned long page)
 232 {
 233         return (uint8_t *)pool + *metadata_off(pool, page);
 234 }
 235
 236 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
 237 {
 238         *metadata_off(pool, page) = meta - (uint8_t *)pool;
 239 }
 240
 241 static unsigned long sub_page_alloc(void *pool, unsigned long page,
 242                                     unsigned long size, unsigned long align)
 243 {
 244         uint8_t *bits = get_page_metadata(pool, page);
 245         unsigned long i;
 246         enum sub_metadata_type type;
 247
 248         type = get_bit_pair(bits, 0);
 249
 250         /* If this is a uniform page, we can't allocate from it. */
 251         if (type == UNIFORM)
 252                 return 0;
 253
 254         assert(type == BITMAP);
 255
 256         /* We use a standart bitmap, but offset because of that BITMAP
 257          * header. */
 258         i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
 259                               div_up(size, BITMAP_GRANULARITY),
 260                               align / BITMAP_GRANULARITY);
 261
 262         /* Can't allocate? */
 263         if (i == 0)
 264                 return 0;
 265
 266         /* i-1 because of the header. */
 267         return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
 268 }
 269
 270 /* We look at the page states to figure out where the allocation for this
 271  * metadata ends. */
 272 static unsigned long get_metalen(void *pool, unsigned long poolsize,
 273                                  struct metaheader *mh)
 274 {
 275         unsigned long i, first, pages = poolsize / getpagesize();
 276
 277         first = pool_offset(pool, mh + 1)/getpagesize();
 278
 279         for (i = first + 1; i < pages && get_page_state(pool,i) == TAKEN; i++);
 280
 281         return i * getpagesize() - pool_offset(pool, mh + 1);
 282 }
 283
 284 static unsigned int uniform_metalen(unsigned int usize)
 285 {
 286         unsigned int metalen;
 287
 288         assert(usize < (1 << 14));
 289
 290         /* Two bits for the header, 14 bits for size, then one bit for each
 291          * element the page can hold.  Round up to number of bytes. */
 292         metalen = div_up(2 + 14 + SUBPAGE_METAOFF / usize, CHAR_BIT);
 293
 294         /* To ensure metaheader is always aligned, round bytes up. */
 295         metalen = align_up(metalen, ALIGNOF(struct metaheader));
 296
 297         return metalen;
 298 }
 299
 300 static unsigned int decode_usize(uint8_t *meta)
 301 {
 302         return ((unsigned)meta[1] << (CHAR_BIT-2)) | (meta[0] >> 2);
 303 }
 304
 305 static void encode_usize(uint8_t *meta, unsigned int usize)
 306 {
 307         meta[0] = (UNIFORM | (usize << 2));
 308         meta[1] = (usize >> (CHAR_BIT - 2));
 309 }
 310
 311 static uint8_t *alloc_metaspace(void *pool, unsigned long poolsize,
 312                                 struct metaheader *mh, unsigned long bytes,
 313                                 enum sub_metadata_type type)
 314 {
 315         uint8_t *meta = (uint8_t *)(mh + 1);
 316         unsigned long free = 0, len, i, metalen;
 317
 318         metalen = get_metalen(pool, poolsize, mh);
 319
 320         /* Walk through metadata looking for free. */
 321         for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
 322                 switch (get_bit_pair(meta, i)) {
 323                 case FREE:
 324                         len = 1;
 325                         free++;
 326                         if (free == bytes * METADATA_PER_BYTE) {
 327                                 /* Mark this as a bitmap. */
 328                                 set_bit_pair(meta, i - free + 1, type);
 329                                 return meta + (i - free + 1)/METADATA_PER_BYTE;
 330                         }
 331                         break;
 332                 case BITMAP:
 333                         /* Skip over this allocated part. */
 334                         len = BITMAP_METALEN * METADATA_PER_BYTE;
 335                         free = 0;
 336                         break;
 337                 case UNIFORM:
 338                         /* Figure metalen given usize. */
 339                         len = decode_usize(meta + i / METADATA_PER_BYTE);
 340                         len = uniform_metalen(len) * METADATA_PER_BYTE;
 341                         free = 0;
 342                         break;
 343                 default:
 344                         assert(0);
 345                         return NULL;
 346                 }
 347         }
 348         return NULL;
 349 }
 350
 351 /* We need this many bytes of metadata. */
 352 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
 353                              unsigned long bytes, enum sub_metadata_type type)
 354 {
 355         struct metaheader *mh, *newmh;
 356         unsigned long page;
 357         uint8_t *meta;
 358
 359         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh))
 360                 if ((meta = alloc_metaspace(pool, poolsize, mh, bytes, type)))
 361                         return meta;
 362
 363         /* No room for metadata?  Can we expand an existing one? */
 364         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 365                 unsigned long nextpage;
 366
 367                 /* We start on this page. */
 368                 nextpage = pool_offset(pool, (char *)(mh+1))/getpagesize();
 369                 /* Iterate through any other pages we own. */
 370                 while (get_page_state(pool, ++nextpage) == TAKEN);
 371
 372                 /* Now, can we grab that page? */
 373                 if (get_page_state(pool, nextpage) != FREE)
 374                         continue;
 375
 376                 /* OK, expand metadata, do it again. */
 377                 set_page_state(pool, nextpage, TAKEN);
 378                 BUILD_ASSERT(FREE == 0);
 379                 memset((char *)pool + nextpage*getpagesize(), 0, getpagesize());
 380                 return alloc_metaspace(pool, poolsize, mh, bytes, type);
 381         }
 382
 383         /* No metadata left at all? */
 384         page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
 385         if (!page)
 386                 return NULL;
 387
 388         newmh = (struct metaheader *)((char *)pool + page * getpagesize());
 389         BUILD_ASSERT(FREE == 0);
 390         memset(newmh + 1, 0, getpagesize() - sizeof(*mh));
 391
 392         /* Sew it into linked list */
 393         mh = first_mheader(pool,poolsize);
 394         newmh->next = mh->next;
 395         mh->next = pool_offset(pool, newmh);
 396
 397         return alloc_metaspace(pool, poolsize, newmh, bytes, type);
 398 }
 399
 400 static void alloc_free_pages(void *pool, unsigned long pagenum)
 401 {
 402         assert(get_page_state(pool, pagenum) == TAKEN_START);
 403         set_page_state(pool, pagenum, FREE);
 404         while (get_page_state(pool, ++pagenum) == TAKEN)
 405                 set_page_state(pool, pagenum, FREE);
 406 }
 407
 408 static void maybe_transform_uniform_page(void *pool, unsigned long offset)
 409 {
 410         /* FIXME: If possible and page isn't full, change to a bitmap */
 411 }
 412
 413 /* Returns 0 or the size of the uniform alloc to use */
 414 static unsigned long suitable_for_uc(unsigned long size, unsigned long align)
 415 {
 416         unsigned long num_elems, wastage, usize;
 417         unsigned long bitmap_cost;
 418
 419         if (size == 0)
 420                 size = 1;
 421
 422         /* Fix up silly alignments. */
 423         usize = align_up(size, align);
 424
 425         /* How many can fit in this page? */
 426         num_elems = SUBPAGE_METAOFF / usize;
 427
 428         /* Can happen with bigger alignments. */
 429         if (!num_elems)
 430                 return 0;
 431
 432         /* Usize maxes out at 14 bits. */
 433         if (usize >= (1 << 14))
 434                 return 0;
 435
 436         /* How many bytes would be left at the end? */
 437         wastage = SUBPAGE_METAOFF % usize;
 438
 439         /* If we can get a larger allocation within alignment constraints, we
 440          * should do it, otherwise might as well leave wastage at the end. */
 441         usize += align_down(wastage / num_elems, align);
 442
 443         /* Bitmap allocation costs 2 bits per BITMAP_GRANULARITY bytes, plus
 444          * however much we waste in rounding up to BITMAP_GRANULARITY. */
 445         bitmap_cost = 2 * div_up(size, BITMAP_GRANULARITY)
 446                 + CHAR_BIT * (align_up(size, BITMAP_GRANULARITY) - size);
 447
 448         /* Our cost is 1 bit, plus usize overhead */
 449         if (bitmap_cost < 1 + (usize - size) * CHAR_BIT)
 450                 return 0;
 451
 452         return usize;
 453 }
 454
 455 static unsigned long uniform_alloc(void *pool, unsigned long poolsize,
 456                                    struct uniform_cache *uc,
 457                                    unsigned long ucnum)
 458 {
 459         uint8_t *metadata = get_page_metadata(pool, uc->page[ucnum]) + 2;
 460         unsigned long i, max;
 461
 462         /* Simple one-bit-per-object bitmap. */
 463         max = SUBPAGE_METAOFF / uc->size[ucnum];
 464         for (i = 0; i < max; i++) {
 465                 if (!(metadata[i / CHAR_BIT] & (1 << (i % CHAR_BIT)))) {
 466                         metadata[i / CHAR_BIT] |= (1 << (i % CHAR_BIT));
 467                         return uc->page[ucnum] * getpagesize()
 468                                 + i * uc->size[ucnum];
 469                 }
 470         }
 471
 472         return 0;
 473 }
 474
 475 static unsigned long new_uniform_page(void *pool, unsigned long poolsize,
 476                                       unsigned long usize)
 477 {
 478         unsigned long page, metalen;
 479         uint8_t *metadata;
 480
 481         /* FIXME: Walk metadata looking for an existing uniform page. */
 482         page = alloc_get_pages(pool, poolsize, 1, 1);
 483         if (page == 0)
 484                 return 0;
 485
 486         metalen = uniform_metalen(usize);
 487
 488         /* Get metadata for page. */
 489         metadata = new_metadata(pool, poolsize, metalen, UNIFORM);
 490         if (!metadata) {
 491                 alloc_free_pages(pool, page);
 492                 return 0;
 493         }
 494
 495         encode_usize(metadata, usize);
 496
 497         BUILD_ASSERT(FREE == 0);
 498         memset(metadata + 2, 0, metalen - 2);
 499
 500         /* Actually, this is a subpage page now. */
 501         set_page_state(pool, page, SPECIAL);
 502
 503         /* Set metadata pointer for page. */
 504         set_page_metadata(pool, page, metadata);
 505
 506         return page;
 507 }
 508
 509 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
 510                                     unsigned long size, unsigned long align)
 511 {
 512         unsigned long i, usize;
 513         uint8_t *metadata;
 514         struct uniform_cache *uc = pool;
 515
 516         usize = suitable_for_uc(size, align);
 517         if (usize) {
 518                 static int random_entry;
 519                 /* Look for a uniform page. */
 520                 for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
 521                         if (uc->size[i] == usize) {
 522                                 unsigned long ret;
 523                                 ret = uniform_alloc(pool, poolsize, uc, i);
 524                                 if (ret != 0)
 525                                         return ret;
 526                                 /* OK, that one is full, remove from cache. */
 527                                 uc->size[i] = 0;
 528                                 break;
 529                         }
 530                 }
 531
 532                 /* OK, try a new uniform page.  Use random discard for now. */
 533                 i = (++random_entry % UNIFORM_CACHE_NUM);
 534                 maybe_transform_uniform_page(pool, uc->page[i]);
 535
 536                 uc->page[i] = new_uniform_page(pool, poolsize, usize);
 537                 if (uc->page[i]) {
 538                         uc->size[i] = usize;
 539                         return uniform_alloc(pool, poolsize, uc, i);
 540                 }
 541                 uc->size[i] = 0;
 542         }
 543
 544         /* Look for partial page. */
 545         for (i = 0; i < poolsize / getpagesize(); i++) {
 546                 unsigned long ret;
 547                 if (get_page_state(pool, i) != SPECIAL)
 548                         continue;
 549
 550                 ret = sub_page_alloc(pool, i, size, align);
 551                 if (ret)
 552                         return ret;
 553         }
 554
 555         /* Create new SUBPAGE page. */
 556         i = alloc_get_pages(pool, poolsize, 1, 1);
 557         if (i == 0)
 558                 return 0;
 559
 560         /* Get metadata for page. */
 561         metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
 562         if (!metadata) {
 563                 alloc_free_pages(pool, i);
 564                 return 0;
 565         }
 566
 567         /* Actually, this is a subpage page now. */
 568         set_page_state(pool, i, SPECIAL);
 569
 570         /* Set metadata pointer for page. */
 571         set_page_metadata(pool, i, metadata);
 572
 573         /* Do allocation like normal */
 574         return sub_page_alloc(pool, i, size, align);
 575 }
 576
 577 static bool bitmap_page_is_empty(uint8_t *meta)
 578 {
 579         unsigned int i;
 580
 581         /* Skip the header (first bit of metadata). */
 582         for (i = 1; i < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; i++)
 583                 if (get_bit_pair(meta, i) != FREE)
 584                         return false;
 585
 586         return true;
 587 }
 588
 589 static bool uniform_page_is_empty(uint8_t *meta)
 590 {
 591         unsigned int i, metalen;
 592
 593         metalen = uniform_metalen(decode_usize(meta));
 594
 595         /* Skip the header (first two bytes of metadata). */
 596         for (i = 2; i < metalen; i++) {
 597                 BUILD_ASSERT(FREE == 0);
 598                 if (meta[i])
 599                         return false;
 600         }
 601         return true;
 602 }
 603
 604 static bool special_page_is_empty(void *pool, unsigned long page)
 605 {
 606         uint8_t *meta;
 607         enum sub_metadata_type type;
 608
 609         meta = get_page_metadata(pool, page);
 610         type = get_bit_pair(meta, 0);
 611
 612         switch (type) {
 613         case UNIFORM:
 614                 return uniform_page_is_empty(meta);
 615         case BITMAP:
 616                 return bitmap_page_is_empty(meta);
 617         default:
 618                 assert(0);
 619         }
 620 }
 621
 622 static void clear_special_metadata(void *pool, unsigned long page)
 623 {
 624         uint8_t *meta;
 625         enum sub_metadata_type type;
 626
 627         meta = get_page_metadata(pool, page);
 628         type = get_bit_pair(meta, 0);
 629
 630         switch (type) {
 631         case UNIFORM:
 632                 /* First two bytes are the header, rest is already FREE */
 633                 BUILD_ASSERT(FREE == 0);
 634                 memset(meta, 0, 2);
 635                 break;
 636         case BITMAP:
 637                 /* First two bits is the header. */
 638                 BUILD_ASSERT(BITMAP_METALEN > 1);
 639                 meta[0] = 0;
 640                 break;
 641         default:
 642                 assert(0);
 643         }
 644 }
 645
 646 /* Returns true if we cleaned any pages. */
 647 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
 648 {
 649         unsigned long i;
 650         bool progress = false;
 651
 652         for (i = 0; i < poolsize/getpagesize(); i++) {
 653                 if (get_page_state(pool, i) != SPECIAL)
 654                         continue;
 655
 656                 if (special_page_is_empty(pool, i)) {
 657                         clear_special_metadata(pool, i);
 658                         set_page_state(pool, i, FREE);
 659                         progress = true;
 660                 }
 661         }
 662         return progress;
 663 }
 664
 665 /* Returns true if we cleaned any pages. */
 666 static bool clean_metadata(void *pool, unsigned long poolsize)
 667 {
 668         struct metaheader *mh, *prev_mh = NULL;
 669         bool progress = false;
 670
 671         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 672                 uint8_t *meta;
 673                 long i;
 674                 unsigned long metalen = get_metalen(pool, poolsize, mh);
 675
 676                 meta = (uint8_t *)(mh + 1);
 677                 BUILD_ASSERT(FREE == 0);
 678                 for (i = metalen - 1; i > 0; i--)
 679                         if (meta[i] != 0)
 680                                 break;
 681
 682                 /* Completely empty? */
 683                 if (prev_mh && i == metalen) {
 684                         alloc_free_pages(pool,
 685                                          pool_offset(pool, mh)/getpagesize());
 686                         prev_mh->next = mh->next;
 687                         mh = prev_mh;
 688                         progress = true;
 689                 } else {
 690                         uint8_t *p;
 691
 692                         /* Some pages at end are free? */
 693                         for (p = (uint8_t *)(mh+1) + metalen - getpagesize();
 694                              p > meta + i;
 695                              p -= getpagesize()) {
 696                                 set_page_state(pool,
 697                                                pool_offset(pool, p)
 698                                                / getpagesize(),
 699                                                FREE);
 700                                 progress = true;
 701                         }
 702                 }
 703         }
 704
 705         return progress;
 706 }
 707
 708 void *alloc_get(void *pool, unsigned long poolsize,
 709                 unsigned long size, unsigned long align)
 710 {
 711         bool subpage_clean = false, metadata_clean = false;
 712         unsigned long ret;
 713
 714         if (poolsize < MIN_SIZE)
 715                 return NULL;
 716
 717 again:
 718         /* Sub-page allocations have an overhead of ~12%. */
 719         if (size + size/8 >= getpagesize() || align >= getpagesize()) {
 720                 unsigned long pages = div_up(size, getpagesize());
 721
 722                 ret = alloc_get_pages(pool, poolsize, pages, align)
 723                         * getpagesize();
 724         } else
 725                 ret = alloc_sub_page(pool, poolsize, size, align);
 726
 727         if (ret != 0)
 728                 return (char *)pool + ret;
 729
 730         /* Allocation failed: garbage collection. */
 731         if (!subpage_clean) {
 732                 subpage_clean = true;
 733                 if (clean_empty_subpages(pool, poolsize))
 734                         goto again;
 735         }
 736
 737         if (!metadata_clean) {
 738                 metadata_clean = true;
 739                 if (clean_metadata(pool, poolsize))
 740                         goto again;
 741         }
 742
 743         /* FIXME: Compact metadata? */
 744         return NULL;
 745 }
 746
 747 static void bitmap_free(void *pool, unsigned long pagenum, unsigned long off,
 748                         uint8_t *metadata)
 749 {
 750         assert(off % BITMAP_GRANULARITY == 0);
 751
 752         off /= BITMAP_GRANULARITY;
 753
 754         /* Offset by one because first bit is used for header. */
 755         off++;
 756
 757         set_bit_pair(metadata, off++, FREE);
 758         while (off <= SUBPAGE_METAOFF / BITMAP_GRANULARITY
 759                && get_bit_pair(metadata, off) == TAKEN)
 760                 set_bit_pair(metadata, off++, FREE);
 761 }
 762
 763 static void uniform_free(void *pool, unsigned long pagenum, unsigned long off,
 764                          uint8_t *metadata)
 765 {
 766         unsigned int usize, bit;
 767
 768         usize = decode_usize(metadata);
 769         /* Must have been this size. */
 770         assert(off % usize == 0);
 771         bit = off / usize;
 772
 773         /* Skip header. */
 774         metadata += 2;
 775
 776         /* Must have been allocated. */
 777         assert(metadata[bit / CHAR_BIT] & (1 << (bit % CHAR_BIT)));
 778         metadata[bit / CHAR_BIT] &= ~(1 << (bit % CHAR_BIT));
 779 }
 780
 781 static void subpage_free(void *pool, unsigned long pagenum, void *free)
 782 {
 783         unsigned long off = (unsigned long)free % getpagesize();
 784         uint8_t *metadata = get_page_metadata(pool, pagenum);
 785         enum sub_metadata_type type;
 786
 787         type = get_bit_pair(metadata, 0);
 788
 789         assert(off < SUBPAGE_METAOFF);
 790
 791         switch (type) {
 792         case BITMAP:
 793                 bitmap_free(pool, pagenum, off, metadata);
 794                 break;
 795         case UNIFORM:
 796                 uniform_free(pool, pagenum, off, metadata);
 797                 break;
 798         default:
 799                 assert(0);
 800         }
 801 }
 802
 803 void alloc_free(void *pool, unsigned long poolsize, void *free)
 804 {
 805         unsigned long pagenum;
 806         struct metaheader *mh;
 807
 808         if (!free)
 809                 return;
 810
 811         assert(poolsize >= MIN_SIZE);
 812
 813         mh = first_mheader(pool, poolsize);
 814         assert((char *)free >= (char *)(mh + 1));
 815         assert((char *)pool + poolsize > (char *)free);
 816
 817         pagenum = pool_offset(pool, free) / getpagesize();
 818
 819         if (get_page_state(pool, pagenum) == SPECIAL)
 820                 subpage_free(pool, pagenum, free);
 821         else {
 822                 assert((unsigned long)free % getpagesize() == 0);
 823                 alloc_free_pages(pool, pagenum);
 824         }
 825 }
 826
 827 unsigned long alloc_size(void *pool, unsigned long poolsize, void *p)
 828 {
 829         unsigned long len, pagenum;
 830         struct metaheader *mh;
 831
 832         assert(poolsize >= MIN_SIZE);
 833
 834         mh = first_mheader(pool, poolsize);
 835         assert((char *)p >= (char *)(mh + 1));
 836         assert((char *)pool + poolsize > (char *)p);
 837
 838         pagenum = pool_offset(pool, p) / getpagesize();
 839
 840         if (get_page_state(pool, pagenum) == SPECIAL) {
 841                 unsigned long off = (unsigned long)p % getpagesize();
 842                 uint8_t *metadata = get_page_metadata(pool, pagenum);
 843                 enum sub_metadata_type type = get_bit_pair(metadata, 0);
 844
 845                 assert(off < SUBPAGE_METAOFF);
 846
 847                 switch (type) {
 848                 case BITMAP:
 849                         assert(off % BITMAP_GRANULARITY == 0);
 850                         off /= BITMAP_GRANULARITY;
 851
 852                         /* Offset by one because first bit used for header. */
 853                         off++;
 854                         len = BITMAP_GRANULARITY;
 855                         while (++off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
 856                                && get_bit_pair(metadata, off) == TAKEN)
 857                                 len += BITMAP_GRANULARITY;
 858                         break;
 859                 case UNIFORM:
 860                         len = decode_usize(metadata);
 861                         break;
 862                 default:
 863                         assert(0);
 864                 }
 865         } else {
 866                 len = getpagesize();
 867                 while (get_page_state(pool, ++pagenum) == TAKEN)
 868                         len += getpagesize();
 869         }
 870
 871         return len;
 872 }
 873
 874 static bool is_metadata_page(void *pool, unsigned long poolsize,
 875                              unsigned long page)
 876 {
 877         struct metaheader *mh;
 878
 879         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 880                 unsigned long start, end;
 881
 882                 start = pool_offset(pool, mh);
 883                 end = pool_offset(pool, (char *)(mh+1)
 884                                   + get_metalen(pool, poolsize, mh));
 885                 if (page >= start/getpagesize() && page < end/getpagesize())
 886                         return true;
 887         }
 888         return false;
 889 }
 890
 891 /* Useful for gdb breakpoints. */
 892 static bool check_fail(void)
 893 {
 894         return false;
 895 }
 896
 897 static bool check_bitmap_metadata(void *pool, unsigned long *mhoff)
 898 {
 899         enum alloc_state last_state = FREE;
 900         unsigned int i;
 901
 902         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
 903                 enum alloc_state state;
 904
 905                 /* +1 because header is the first byte. */
 906                 state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
 907                 switch (state) {
 908                 case SPECIAL:
 909                         return check_fail();
 910                 case TAKEN:
 911                         if (last_state == FREE)
 912                                 return check_fail();
 913                         break;
 914                 default:
 915                         break;
 916                 }
 917                 last_state = state;
 918         }
 919         return true;
 920 }
 921
 922 /* We don't know what alignment they asked for, but we can infer worst
 923  * case from the size. */
 924 static unsigned int max_align(unsigned int size)
 925 {
 926         unsigned int align = 1;
 927
 928         while (size % (align * 2) == 0)
 929                 align *= 2;
 930         return align;
 931 }
 932
 933 static bool check_uniform_metadata(void *pool, unsigned long *mhoff)
 934 {
 935         uint8_t *meta = (uint8_t *)pool + *mhoff;
 936         unsigned int i, usize;
 937         struct uniform_cache *uc = pool;
 938
 939         usize = decode_usize(meta);
 940         if (usize == 0 || suitable_for_uc(usize, max_align(usize)) != usize)
 941                 return check_fail();
 942
 943         /* If it's in uniform cache, make sure that agrees on size. */
 944         for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
 945                 uint8_t *ucm;
 946
 947                 if (!uc->size[i])
 948                         continue;
 949
 950                 ucm = get_page_metadata(pool, uc->page[i]);
 951                 if (ucm != meta)
 952                         continue;
 953
 954                 if (usize != uc->size[i])
 955                         return check_fail();
 956         }
 957         return true;
 958 }
 959
 960 static bool check_subpage(void *pool, unsigned long poolsize,
 961                           unsigned long page)
 962 {
 963         unsigned long *mhoff = metadata_off(pool, page);
 964
 965         if (*mhoff + sizeof(struct metaheader) > poolsize)
 966                 return check_fail();
 967
 968         if (*mhoff % ALIGNOF(struct metaheader) != 0)
 969                 return check_fail();
 970
 971         /* It must point to a metadata page. */
 972         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
 973                 return check_fail();
 974
 975         /* Header at start of subpage allocation */
 976         switch (get_bit_pair((uint8_t *)pool + *mhoff, 0)) {
 977         case BITMAP:
 978                 return check_bitmap_metadata(pool, mhoff);
 979         case UNIFORM:
 980                 return check_uniform_metadata(pool, mhoff);
 981         default:
 982                 return check_fail();
 983         }
 984
 985 }
 986
 987 bool alloc_check(void *pool, unsigned long poolsize)
 988 {
 989         unsigned long i;
 990         struct metaheader *mh;
 991         enum alloc_state last_state = FREE;
 992         bool was_metadata = false;
 993
 994         if (poolsize < MIN_SIZE)
 995                 return true;
 996
 997         if (get_page_state(pool, 0) != TAKEN_START)
 998                 return check_fail();
 999
1000         /* First check metadata pages. */
1001         /* Metadata pages will be marked TAKEN. */
1002         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
1003                 unsigned long start, end;
1004
1005                 start = pool_offset(pool, mh);
1006                 if (start + sizeof(*mh) > poolsize)
1007                         return check_fail();
1008
1009                 end = pool_offset(pool, (char *)(mh+1)
1010                                   + get_metalen(pool, poolsize, mh));
1011                 if (end > poolsize)
1012                         return check_fail();
1013
1014                 /* Non-first pages should start on a page boundary. */
1015                 if (mh != first_mheader(pool, poolsize)
1016                     && start % getpagesize() != 0)
1017                         return check_fail();
1018
1019                 /* It should end on a page boundary. */
1020                 if (end % getpagesize() != 0)
1021                         return check_fail();
1022         }
1023
1024         for (i = 0; i < poolsize / getpagesize(); i++) {
1025                 enum alloc_state state = get_page_state(pool, i);
1026                 bool is_metadata = is_metadata_page(pool, poolsize,i);
1027
1028                 switch (state) {
1029                 case FREE:
1030                         /* metadata pages are never free. */
1031                         if (is_metadata)
1032                                 return check_fail();
1033                 case TAKEN_START:
1034                         break;
1035                 case TAKEN:
1036                         /* This should continue a previous block. */
1037                         if (last_state == FREE)
1038                                 return check_fail();
1039                         if (is_metadata != was_metadata)
1040                                 return check_fail();
1041                         break;
1042                 case SPECIAL:
1043                         /* Check metadata pointer etc. */
1044                         if (!check_subpage(pool, poolsize, i))
1045                                 return check_fail();
1046                 }
1047                 last_state = state;
1048                 was_metadata = is_metadata;
1049         }
1050         return true;
1051 }
1052
1053 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
1054 {
1055         struct metaheader *mh;
1056         struct uniform_cache *uc = pool;
1057         unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
1058         long i;
1059
1060         if (poolsize < MIN_SIZE) {
1061                 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
1062                 return;
1063         }
1064
1065         tot = 0;
1066         for (i = 0; i < UNIFORM_CACHE_NUM; i++)
1067                 tot += (uc->size[i] != 0);
1068         fprintf(out, "Uniform cache (%lu entries):\n", tot);
1069         for (i = 0; i < UNIFORM_CACHE_NUM; i++) {
1070                 unsigned int j, total = 0;
1071                 uint8_t *meta;
1072
1073                 if (!uc->size[i])
1074                         continue;
1075
1076                 /* First two bytes are header. */
1077                 meta = get_page_metadata(pool, uc->page[i]) + 2;
1078
1079                 for (j = 0; j < SUBPAGE_METAOFF / uc->size[i]; j++)
1080                         if (meta[j / 8] & (1 << (j % 8)))
1081                                 total++;
1082
1083                 printf("  %u: %lu: %u/%zu (%zu%% density)\n",
1084                        uc->size[i], uc->page[i], total,
1085                        SUBPAGE_METAOFF / uc->size[i],
1086                        (total * 100) / (SUBPAGE_METAOFF / uc->size[i]));
1087         }
1088
1089         memset(count, 0, sizeof(count));
1090         for (i = 0; i < poolsize / getpagesize(); i++)
1091                 count[get_page_state(pool, i)]++;
1092
1093         mh = first_mheader(pool, poolsize);
1094         pagebitlen = (uint8_t *)mh - get_page_statebits(pool);
1095         fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
1096                 pagebitlen, count[0], count[1], count[2], count[3]);
1097
1098         /* One metadata page for every page of page bits. */
1099         metadata_pages = div_up(pagebitlen, getpagesize());
1100
1101         /* Now do each metadata page. */
1102         for (; mh; mh = next_mheader(pool,mh)) {
1103                 unsigned long free = 0, bitmapblocks = 0, uniformblocks = 0,
1104                         len = 0, uniformlen = 0, bitmaplen = 0, metalen;
1105                 uint8_t *meta = (uint8_t *)(mh + 1);
1106
1107                 metalen = get_metalen(pool, poolsize, mh);
1108                 metadata_pages += (sizeof(*mh) + metalen) / getpagesize();
1109
1110                 for (i = 0; i < metalen * METADATA_PER_BYTE; i += len) {
1111                         switch (get_bit_pair(meta, i)) {
1112                         case FREE:
1113                                 len = 1;
1114                                 free++;
1115                                 break;
1116                         case BITMAP:
1117                                 /* Skip over this allocated part. */
1118                                 len = BITMAP_METALEN * METADATA_PER_BYTE;
1119                                 bitmapblocks++;
1120                                 bitmaplen += len;
1121                                 break;
1122                         case UNIFORM:
1123                                 /* Skip over this part. */
1124                                 len = decode_usize(meta + i/METADATA_PER_BYTE);
1125                                 len = uniform_metalen(len) * METADATA_PER_BYTE;
1126                                 uniformblocks++;
1127                                 uniformlen += len;
1128                                 break;
1129                         default:
1130                                 assert(0);
1131                         }
1132                 }
1133
1134                 fprintf(out, "Metadata %lu-%lu: %lu free, %lu bitmapblocks, %lu uniformblocks, %lu%% density\n",
1135                         pool_offset(pool, mh),
1136                         pool_offset(pool, (char *)(mh+1) + metalen),
1137                         free, bitmapblocks, uniformblocks,
1138                         (bitmaplen + uniformlen) * 100
1139                         / (free + bitmaplen + uniformlen));
1140         }
1141
1142         /* Account for total pages allocated. */
1143         tot = (count[1] + count[2] - metadata_pages) * getpagesize();
1144
1145         fprintf(out, "Total metadata bytes = %lu\n",
1146                 metadata_pages * getpagesize());
1147
1148         /* Now do every subpage. */
1149         for (i = 0; i < poolsize / getpagesize(); i++) {
1150                 uint8_t *meta;
1151                 unsigned int j, allocated;
1152                 enum sub_metadata_type type;
1153
1154                 if (get_page_state(pool, i) != SPECIAL)
1155                         continue;
1156
1157                 memset(count, 0, sizeof(count));
1158
1159                 meta = get_page_metadata(pool, i);
1160                 type = get_bit_pair(meta, 0);
1161
1162                 if (type == BITMAP) {
1163                         for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
1164                                 count[get_page_state(meta, j)]++;
1165                         allocated = (count[1] + count[2]) * BITMAP_GRANULARITY;
1166                         fprintf(out, "Subpage bitmap ");
1167                 } else {
1168                         unsigned int usize = decode_usize(meta);
1169
1170                         assert(type == UNIFORM);
1171                         fprintf(out, "Subpage uniform (%u) ", usize);
1172                         meta += 2;
1173                         for (j = 0; j < SUBPAGE_METAOFF / usize; j++)
1174                                 count[!!(meta[j / 8] & (1 << (j % 8)))]++;
1175                         allocated = count[1] * usize;
1176                 }
1177                 fprintf(out, "%lu: FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %u%% density\n",
1178                         i, count[0], count[1], count[2],
1179                         allocated * 100 / getpagesize());
1180                 tot += allocated;
1181         }
1182
1183         /* This is optimistic, since we overalloc in several cases. */
1184         fprintf(out, "Best possible allocation density = %lu%%\n",
1185                 tot * 100 / poolsize);
1186 }