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