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: Could be in pages). */
  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 0 on fail. */
 140 static unsigned 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 0;
 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 void *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         unsigned 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 NULL;
 247
 248         return (char *)pool + 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 = (char *)newmh - (char *)pool;
 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 void *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                 void *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 NULL;
 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 NULL;
 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 void *alloc_get(void *pool, unsigned long poolsize,
 382                 unsigned long size, unsigned long align)
 383 {
 384         if (poolsize < MIN_SIZE)
 385                 return NULL;
 386
 387         /* Sub-page allocations have an overhead of 25%. */
 388         if (size + size/4 >= getpagesize() || align >= getpagesize()) {
 389                 unsigned long ret, pages = div_up(size, getpagesize());
 390
 391                 ret = alloc_get_pages(pool, poolsize, pages, align);
 392                 if (ret == 0)
 393                         return NULL;
 394                 return (char *)pool + ret * getpagesize();
 395         }
 396
 397         return alloc_sub_page(pool, poolsize, size, align);
 398 }
 399
 400 static void subpage_free(void *pool, unsigned long pagenum, void *free)
 401 {
 402         unsigned long off = (unsigned long)free % getpagesize();
 403         uint8_t *metadata;
 404
 405         assert(off < SUBPAGE_METAOFF);
 406         assert(off % BITMAP_GRANULARITY == 0);
 407
 408         metadata = get_page_metadata(pool, pagenum);
 409
 410         off /= BITMAP_GRANULARITY;
 411
 412         set_page_state(metadata, off++, FREE);
 413         while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
 414                && get_page_state(metadata, off) == TAKEN)
 415                 set_page_state(metadata, off++, FREE);
 416
 417         /* FIXME: If whole page free, free page and metadata. */
 418 }
 419
 420 void alloc_free(void *pool, unsigned long poolsize, void *free)
 421 {
 422         unsigned long pagenum;
 423         struct metaheader *mh;
 424
 425         if (!free)
 426                 return;
 427
 428         assert(poolsize >= MIN_SIZE);
 429
 430         mh = first_mheader(pool, poolsize);
 431         assert((char *)free >= (char *)(mh + 1) + mh->metalen);
 432         assert((char *)pool + poolsize > (char *)free);
 433
 434         pagenum = pool_offset(pool, free) / getpagesize();
 435
 436         if (get_page_state(pool, pagenum) == SUBPAGE)
 437                 subpage_free(pool, pagenum, free);
 438         else {
 439                 assert((unsigned long)free % getpagesize() == 0);
 440                 alloc_free_pages(pool, pagenum);
 441         }
 442 }
 443
 444 static bool is_metadata_page(void *pool, unsigned long poolsize,
 445                              unsigned long page)
 446 {
 447         struct metaheader *mh;
 448
 449         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 450                 unsigned long start, end;
 451
 452                 start = pool_offset(pool, mh);
 453                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
 454                 if (page >= start/getpagesize() && page < end/getpagesize())
 455                         return true;
 456         }
 457         return false;
 458 }
 459
 460 static bool check_subpage(void *pool, unsigned long poolsize,
 461                           unsigned long page)
 462 {
 463         unsigned long *mhoff = metadata_off(pool, page);
 464         unsigned int i;
 465         enum page_state last_state = FREE;
 466
 467         if (*mhoff + sizeof(struct metaheader) > poolsize)
 468                 return false;
 469
 470         if (*mhoff % ALIGNOF(struct metaheader) != 0)
 471                 return false;
 472
 473         /* It must point to a metadata page. */
 474         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
 475                 return false;
 476
 477         /* Marker at end of subpage allocation is "taken" */
 478         if (get_page_state((uint8_t *)pool + *mhoff,
 479                            getpagesize()/BITMAP_GRANULARITY - 1) != TAKEN)
 480                 return false;
 481
 482         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
 483                 enum page_state state;
 484
 485                 state = get_page_state((uint8_t *)pool + *mhoff, i);
 486                 switch (state) {
 487                 case SUBPAGE:
 488                         return false;
 489                 case TAKEN:
 490                         if (last_state == FREE)
 491                                 return false;
 492                         break;
 493                 default:
 494                         break;
 495                 }
 496                 last_state = state;
 497         }
 498         return true;
 499 }
 500
 501 bool alloc_check(void *pool, unsigned long poolsize)
 502 {
 503         unsigned long i;
 504         struct metaheader *mh;
 505         enum page_state last_state = FREE;
 506         bool was_metadata = false;
 507
 508         if (poolsize < MIN_SIZE)
 509                 return true;
 510
 511         if (get_page_state(pool, 0) != TAKEN_START)
 512                 return false;
 513
 514         /* First check metadata pages. */
 515         /* Metadata pages will be marked TAKEN. */
 516         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 517                 unsigned long start, end;
 518
 519                 start = pool_offset(pool, mh);
 520                 if (start + sizeof(*mh) > poolsize)
 521                         return false;
 522
 523                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
 524                 if (end > poolsize)
 525                         return false;
 526
 527                 /* Non-first pages should start on a page boundary. */
 528                 if (mh != first_mheader(pool, poolsize)
 529                     && start % getpagesize() != 0)
 530                         return false;
 531
 532                 /* It should end on a page boundary. */
 533                 if (end % getpagesize() != 0)
 534                         return false;
 535         }
 536
 537         for (i = 0; i < poolsize / getpagesize(); i++) {
 538                 enum page_state state = get_page_state(pool, i);
 539                 bool is_metadata = is_metadata_page(pool, poolsize,i);
 540
 541                 switch (state) {
 542                 case FREE:
 543                         /* metadata pages are never free. */
 544                         if (is_metadata)
 545                                 return false;
 546                 case TAKEN_START:
 547                         break;
 548                 case TAKEN:
 549                         /* This should continue a previous block. */
 550                         if (last_state == FREE)
 551                                 return false;
 552                         if (is_metadata != was_metadata)
 553                                 return false;
 554                         break;
 555                 case SUBPAGE:
 556                         /* Check metadata pointer etc. */
 557                         if (!check_subpage(pool, poolsize, i))
 558                                 return false;
 559                 }
 560                 last_state = state;
 561                 was_metadata = is_metadata;
 562         }
 563         return true;
 564 }
 565
 566 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
 567 {
 568         struct metaheader *mh;
 569         unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
 570         long i;
 571
 572         if (poolsize < MIN_SIZE) {
 573                 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
 574                 return;
 575         }
 576
 577         memset(count, 0, sizeof(count));
 578         for (i = 0; i < poolsize / getpagesize(); i++)
 579                 count[get_page_state(pool, i)]++;
 580
 581         mh = first_mheader(pool, poolsize);
 582         pagebitlen = (char *)mh - (char *)pool;
 583         fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
 584                 pagebitlen, count[0], count[1], count[2], count[3]);
 585
 586         /* One metadata page for every page of page bits. */
 587         metadata_pages = div_up(pagebitlen, getpagesize());
 588
 589         /* Now do each metadata page. */
 590         for (; mh; mh = next_mheader(pool,mh)) {
 591                 unsigned long free = 0, subpageblocks = 0, len = 0;
 592                 uint8_t *meta = (uint8_t *)(mh + 1);
 593
 594                 metadata_pages += (sizeof(*mh) + mh->metalen) / getpagesize();
 595
 596                 /* TAKEN tags end a subpage alloc. */
 597                 for (i = mh->metalen * CHAR_BIT/BITS_PER_PAGE - 1;
 598                      i >= 0;
 599                      i -= len) {
 600                         switch (get_page_state(meta, i)) {
 601                         case FREE:
 602                                 len = 1;
 603                                 free++;
 604                                 break;
 605                         case TAKEN:
 606                                 /* Skip over this allocated part. */
 607                                 len = BITMAP_METALEN * CHAR_BIT;
 608                                 subpageblocks++;
 609                                 break;
 610                         default:
 611                                 assert(0);
 612                         }
 613                 }
 614
 615                 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
 616                         pool_offset(pool, mh),
 617                         pool_offset(pool, (char *)(mh+1) + mh->metalen),
 618                         free, subpageblocks,
 619                         subpageblocks * BITMAP_METALEN * 100
 620                         / (free + subpageblocks * BITMAP_METALEN));
 621         }
 622
 623         /* Account for total pages allocated. */
 624         tot = (count[1] + count[2] - metadata_pages) * getpagesize();
 625
 626         fprintf(out, "Total metadata bytes = %lu\n",
 627                 metadata_pages * getpagesize());
 628
 629         /* Now do every subpage. */
 630         for (i = 0; i < poolsize / getpagesize(); i++) {
 631                 uint8_t *meta;
 632                 unsigned int j;
 633                 if (get_page_state(pool, i) != SUBPAGE)
 634                         continue;
 635
 636                 memset(count, 0, sizeof(count));
 637                 meta = get_page_metadata(pool, i);
 638                 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
 639                         count[get_page_state(meta, j)]++;
 640
 641                 fprintf(out, "Subpage %lu: "
 642                         "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
 643                         i, count[0], count[1], count[2],
 644                         ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
 645                         / getpagesize());
 646                 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
 647         }
 648
 649         /* This is optimistic, since we overalloc in several cases. */
 650         fprintf(out, "Best possible allocation density = %lu%%\n",
 651                 tot * 100 / poolsize);
 652 }