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 a TAKEN header,
  71  * then two bits for every BITMAP_GRANULARITY of usable bytes in the. */
  72 #define BITMAP_METABITLEN                                               \
  73     ((1 + div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY)) * BITS_PER_PAGE)
  74
  75 /* This is the length in bytes. */
  76 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
  77
  78 static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
  79 {
  80         return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
  81 }
  82
  83 static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
  84 {
  85         bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
  86         bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
  87 }
  88
  89 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
  90 {
  91         unsigned int pagestatelen;
  92
  93         pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
  94                                        CHAR_BIT),
  95                                 ALIGNOF(struct metaheader));
  96         return (struct metaheader *)((char *)pool + pagestatelen);
  97 }
  98
  99 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
 100 {
 101         if (!mh->next)
 102                 return NULL;
 103
 104         return (struct metaheader *)((char *)pool + mh->next);
 105 }
 106
 107 static unsigned long pool_offset(void *pool, void *p)
 108 {
 109         return (char *)p - (char *)pool;
 110 }
 111
 112 void alloc_init(void *pool, unsigned long poolsize)
 113 {
 114         /* FIXME: Alignment assumptions about pool. */
 115         unsigned long len, i;
 116         struct metaheader *mh;
 117
 118         if (poolsize < MIN_SIZE)
 119                 return;
 120
 121         mh = first_mheader(pool, poolsize);
 122
 123         /* len covers all page states, plus the metaheader. */
 124         len = (char *)(mh + 1) - (char *)pool;
 125         /* Mark all page states FREE */
 126         BUILD_ASSERT(FREE == 0);
 127         memset(pool, 0, len);
 128
 129         /* metaheader len takes us up to next page boundary. */
 130         mh->metalen = align_up(len, getpagesize()) - len;
 131
 132         /* Mark the pagestate and metadata page(s) allocated. */
 133         set_page_state(pool, 0, TAKEN_START);
 134         for (i = 1; i < div_up(len, getpagesize()); i++)
 135                 set_page_state(pool, i, TAKEN);
 136 }
 137
 138 /* Two bits per element, representing page states.  Returns 0 on fail. */
 139 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long elems,
 140                                        unsigned long want, unsigned long align)
 141 {
 142         long i;
 143         unsigned long free;
 144
 145         free = 0;
 146         /* We allocate from far end, to increase ability to expand metadata. */
 147         for (i = elems - 1; i >= 0; i--) {
 148                 switch (get_page_state(bits, i)) {
 149                 case FREE:
 150                         if (++free >= want) {
 151                                 unsigned long j;
 152
 153                                 /* They might ask for large alignment. */
 154                                 if (align && i % align)
 155                                         continue;
 156
 157                                 for (j = i+1; j < i + want; j++)
 158                                         set_page_state(bits, j, TAKEN);
 159                                 set_page_state(bits, i, TAKEN_START);
 160                                 return i;
 161                         }
 162                         break;
 163                 case SUBPAGE:
 164                 case TAKEN_START:
 165                 case TAKEN:
 166                         free = 0;
 167                         break;
 168                 }
 169         }
 170
 171         return 0;
 172 }
 173
 174 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
 175                                      unsigned long pages, unsigned long align)
 176 {
 177         long i;
 178         unsigned long free;
 179
 180         free = 0;
 181         /* We allocate from far end, to increase ability to expand metadata. */
 182         for (i = poolsize / getpagesize() - 1; i >= 0; i--) {
 183                 switch (get_page_state(pool, i)) {
 184                 case FREE:
 185                         if (++free >= pages) {
 186                                 unsigned long j, addr;
 187
 188                                 addr = (unsigned long)pool + i * getpagesize();
 189
 190                                 /* They might ask for multi-page alignment. */
 191                                 if (addr % align)
 192                                         continue;
 193
 194                                 for (j = i+1; j < i + pages; j++)
 195                                         set_page_state(pool, j, TAKEN);
 196                                 set_page_state(pool, i, TAKEN_START);
 197                                 return i;
 198                         }
 199                         break;
 200                 case SUBPAGE:
 201                 case TAKEN_START:
 202                 case TAKEN:
 203                         free = 0;
 204                         break;
 205                 }
 206         }
 207
 208         return 0;
 209 }
 210
 211 /* Offset to metadata is at end of page. */
 212 static unsigned long *metadata_off(void *pool, unsigned long page)
 213 {
 214         return (unsigned long *)
 215                 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
 216 }
 217
 218 static uint8_t *get_page_metadata(void *pool, unsigned long page)
 219 {
 220         return (uint8_t *)pool + *metadata_off(pool, page);
 221 }
 222
 223 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
 224 {
 225         *metadata_off(pool, page) = meta - (uint8_t *)pool;
 226 }
 227
 228 static void *sub_page_alloc(void *pool, unsigned long page,
 229                             unsigned long size, unsigned long align)
 230 {
 231         uint8_t *bits = get_page_metadata(pool, page);
 232         unsigned long i;
 233
 234         /* TAKEN at end means a bitwise alloc. */
 235         assert(get_page_state(bits, getpagesize()/BITMAP_GRANULARITY - 1)
 236                == TAKEN);
 237
 238         /* Our bits are the same as the page bits. */
 239         i = alloc_from_bitmap(bits, getpagesize()/BITMAP_GRANULARITY,
 240                               div_up(size, BITMAP_GRANULARITY),
 241                               align / BITMAP_GRANULARITY);
 242
 243         /* Can't allocate? */
 244         if (i == 0)
 245                 return NULL;
 246
 247         return (char *)pool + page*getpagesize() + i*BITMAP_GRANULARITY;
 248 }
 249
 250 static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes)
 251 {
 252         uint8_t *meta = (uint8_t *)(mh + 1);
 253         unsigned long free = 0, len;
 254         long i;
 255
 256         /* TAKEN tags end a subpage alloc. */
 257         for (i = mh->metalen * CHAR_BIT / BITS_PER_PAGE - 1; i >= 0; i -= len) {
 258                 switch (get_page_state(meta, i)) {
 259                 case FREE:
 260                         len = 1;
 261                         free++;
 262                         if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
 263                                 /* TAKEN marks end of metablock. */
 264                                 set_page_state(meta, i + free - 1, TAKEN);
 265                                 return meta + i / (CHAR_BIT / BITS_PER_PAGE);
 266                         }
 267                         break;
 268                 case TAKEN:
 269                         /* Skip over this allocated part. */
 270                         len = BITMAP_METALEN * CHAR_BIT;
 271                         free = 0;
 272                         break;
 273                 default:
 274                         assert(0);
 275                         return NULL;
 276                 }
 277         }
 278         return NULL;
 279 }
 280
 281 /* We need this many bytes of metadata. */
 282 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
 283                              unsigned long bytes)
 284 {
 285         struct metaheader *mh, *newmh;
 286         unsigned long page;
 287
 288         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 289                 uint8_t *meta = alloc_metaspace(mh, bytes);
 290
 291                 if (meta)
 292                         return meta;
 293         }
 294
 295         /* No room for metadata?  Can we expand an existing one? */
 296         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 297                 /* It should end on a page boundary. */
 298                 unsigned long nextpage;
 299
 300                 nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
 301                 assert(nextpage % getpagesize() == 0);
 302
 303                 /* Now, can we grab that page? */
 304                 if (get_page_state(pool, nextpage / getpagesize()) != FREE)
 305                         continue;
 306
 307                 /* OK, expand metadata, do it again. */
 308                 set_page_state(pool, nextpage / getpagesize(), TAKEN);
 309                 memset((char *)pool + nextpage, 0, getpagesize());
 310                 mh->metalen += getpagesize();
 311                 return alloc_metaspace(mh, bytes);
 312         }
 313
 314         /* No metadata left at all? */
 315         page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
 316         if (!page)
 317                 return NULL;
 318
 319         newmh = (struct metaheader *)((char *)pool + page * getpagesize());
 320         newmh->metalen = getpagesize() - sizeof(*mh);
 321         memset(newmh + 1, 0, newmh->metalen);
 322
 323         /* Sew it into linked list */
 324         mh = first_mheader(pool,poolsize);
 325         newmh->next = mh->next;
 326         mh->next = (char *)newmh - (char *)pool;
 327
 328         return alloc_metaspace(newmh, bytes);
 329 }
 330
 331 static void alloc_free_pages(void *pool, unsigned long pagenum)
 332 {
 333         assert(get_page_state(pool, pagenum) == TAKEN_START);
 334         set_page_state(pool, pagenum, FREE);
 335         while (get_page_state(pool, ++pagenum) == TAKEN)
 336                 set_page_state(pool, pagenum, FREE);
 337 }
 338
 339 static void *alloc_sub_page(void *pool, unsigned long poolsize,
 340                             unsigned long size, unsigned long align)
 341 {
 342         unsigned long i;
 343         uint8_t *metadata;
 344
 345         /* Look for partial page. */
 346         for (i = 0; i < poolsize / getpagesize(); i++) {
 347                 void *ret;
 348                 if (get_page_state(pool, i) != SUBPAGE)
 349                         continue;
 350
 351                 ret = sub_page_alloc(pool, i, size, align);
 352                 if (ret)
 353                         return ret;
 354         }
 355
 356         /* Create new SUBPAGE page. */
 357         i = alloc_get_pages(pool, poolsize, 1, 1);
 358         if (i == 0)
 359                 return NULL;
 360
 361         /* Get metadata for page. */
 362         metadata = new_metadata(pool, poolsize, BITMAP_METALEN);
 363         if (!metadata) {
 364                 alloc_free_pages(pool, i);
 365                 return NULL;
 366         }
 367
 368         /* Actually, this is a SUBPAGE page now. */
 369         set_page_state(pool, i, SUBPAGE);
 370
 371         /* Set metadata pointer for page. */
 372         set_page_metadata(pool, i, metadata);
 373
 374         /* Do allocation like normal */
 375         return sub_page_alloc(pool, i, size, align);
 376 }
 377
 378 void *alloc_get(void *pool, unsigned long poolsize,
 379                 unsigned long size, unsigned long align)
 380 {
 381         if (poolsize < MIN_SIZE)
 382                 return NULL;
 383
 384         /* Sub-page allocations have an overhead of 25%. */
 385         if (size + size/4 >= getpagesize() || align >= getpagesize()) {
 386                 unsigned long ret, pages = div_up(size, getpagesize());
 387
 388                 ret = alloc_get_pages(pool, poolsize, pages, align);
 389                 if (ret == 0)
 390                         return NULL;
 391                 return (char *)pool + ret * getpagesize();
 392         }
 393
 394         return alloc_sub_page(pool, poolsize, size, align);
 395 }
 396
 397 static void subpage_free(void *pool, unsigned long pagenum, void *free)
 398 {
 399         unsigned long off = (unsigned long)free % getpagesize();
 400         uint8_t *metadata;
 401
 402         assert(off < SUBPAGE_METAOFF);
 403         assert(off % BITMAP_GRANULARITY == 0);
 404
 405         metadata = get_page_metadata(pool, pagenum);
 406
 407         off /= BITMAP_GRANULARITY;
 408
 409         set_page_state(metadata, off++, FREE);
 410         while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
 411                && get_page_state(metadata, off) == TAKEN)
 412                 set_page_state(metadata, off++, FREE);
 413
 414         /* FIXME: If whole page free, free page and metadata. */
 415 }
 416
 417 void alloc_free(void *pool, unsigned long poolsize, void *free)
 418 {
 419         unsigned long pagenum;
 420         struct metaheader *mh;
 421
 422         if (!free)
 423                 return;
 424
 425         assert(poolsize >= MIN_SIZE);
 426
 427         mh = first_mheader(pool, poolsize);
 428         assert((char *)free >= (char *)(mh + 1) + mh->metalen);
 429         assert((char *)pool + poolsize > (char *)free);
 430
 431         pagenum = pool_offset(pool, free) / getpagesize();
 432
 433         if (get_page_state(pool, pagenum) == SUBPAGE)
 434                 subpage_free(pool, pagenum, free);
 435         else {
 436                 assert((unsigned long)free % getpagesize() == 0);
 437                 alloc_free_pages(pool, pagenum);
 438         }
 439 }
 440
 441 static bool is_metadata_page(void *pool, unsigned long poolsize,
 442                              unsigned long page)
 443 {
 444         struct metaheader *mh;
 445
 446         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 447                 unsigned long start, end;
 448
 449                 start = pool_offset(pool, mh);
 450                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
 451                 if (page >= start/getpagesize() && page < end/getpagesize())
 452                         return true;
 453         }
 454         return false;
 455 }
 456
 457 static bool check_subpage(void *pool, unsigned long poolsize,
 458                           unsigned long page)
 459 {
 460         unsigned long *mhoff = metadata_off(pool, page);
 461         unsigned int i;
 462         enum page_state last_state = FREE;
 463
 464         if (*mhoff + sizeof(struct metaheader) > poolsize)
 465                 return false;
 466
 467         if (*mhoff % ALIGNOF(struct metaheader) != 0)
 468                 return false;
 469
 470         /* It must point to a metadata page. */
 471         if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
 472                 return false;
 473
 474         /* Marker at end of subpage allocation is "taken" */
 475         if (get_page_state((uint8_t *)pool + *mhoff,
 476                            getpagesize()/BITMAP_GRANULARITY - 1) != TAKEN)
 477                 return false;
 478
 479         for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
 480                 enum page_state state;
 481
 482                 state = get_page_state((uint8_t *)pool + *mhoff, i);
 483                 switch (state) {
 484                 case SUBPAGE:
 485                         return false;
 486                 case TAKEN:
 487                         if (last_state == FREE)
 488                                 return false;
 489                         break;
 490                 default:
 491                         break;
 492                 }
 493                 last_state = state;
 494         }
 495         return true;
 496 }
 497
 498 bool alloc_check(void *pool, unsigned long poolsize)
 499 {
 500         unsigned long i;
 501         struct metaheader *mh;
 502         enum page_state last_state = FREE;
 503         bool was_metadata = false;
 504
 505         if (poolsize < MIN_SIZE)
 506                 return true;
 507
 508         if (get_page_state(pool, 0) != TAKEN_START)
 509                 return false;
 510
 511         /* First check metadata pages. */
 512         /* Metadata pages will be marked TAKEN. */
 513         for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
 514                 unsigned long start, end;
 515
 516                 start = pool_offset(pool, mh);
 517                 if (start + sizeof(*mh) > poolsize)
 518                         return false;
 519
 520                 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
 521                 if (end > poolsize)
 522                         return false;
 523
 524                 /* Non-first pages should start on a page boundary. */
 525                 if (mh != first_mheader(pool, poolsize)
 526                     && start % getpagesize() != 0)
 527                         return false;
 528
 529                 /* It should end on a page boundary. */
 530                 if (end % getpagesize() != 0)
 531                         return false;
 532         }
 533
 534         for (i = 0; i < poolsize / getpagesize(); i++) {
 535                 enum page_state state = get_page_state(pool, i);
 536                 bool is_metadata = is_metadata_page(pool, poolsize,i);
 537
 538                 switch (state) {
 539                 case FREE:
 540                         /* metadata pages are never free. */
 541                         if (is_metadata)
 542                                 return false;
 543                 case TAKEN_START:
 544                         break;
 545                 case TAKEN:
 546                         /* This should continue a previous block. */
 547                         if (last_state == FREE)
 548                                 return false;
 549                         if (is_metadata != was_metadata)
 550                                 return false;
 551                         break;
 552                 case SUBPAGE:
 553                         /* Check metadata pointer etc. */
 554                         if (!check_subpage(pool, poolsize, i))
 555                                 return false;
 556                 }
 557                 last_state = state;
 558                 was_metadata = is_metadata;
 559         }
 560         return true;
 561 }