7 #include "build_assert/build_assert.h"
11 #define ALIGNOF(t) __alignof__(t)
13 /* Alignment by measuring structure padding. */
14 #define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
17 /* FIXME: Doesn't handle non-page-aligned poolsize. */
20 #define MIN_SIZE (getpagesize() * 2)
22 /* What's the granularity of sub-page allocs? */
23 #define BITMAP_GRANULARITY 4
27 * file := pagestates pad metadata
28 * pagestates := pages * 2-bits-per-page
29 * pad := pad to next ALIGNOF(metadata)
31 * metadata := metalen next-ptr metabits
32 * metabits := freeblock | bitblock
34 * bitblock := 2-bits-per-bit-in-page 1
38 /* Next meta header, or 0 */
40 /* Bits start here. */
43 /* Assumes a is a power of two. */
44 static unsigned long align_up(unsigned long x, unsigned long a)
46 return (x + a - 1) & ~(a - 1);
49 static unsigned long div_up(unsigned long x, unsigned long a)
51 return (x + a - 1) / a;
54 /* It turns out that we spend a lot of time dealing with bit pairs.
55 * These routines manipulate them.
57 static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
59 return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
62 static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
64 bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
65 bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
68 /* This is used for page states and subpage allocations */
74 SPECIAL, /* Sub-page allocation for page states. */
77 /* The types for subpage metadata. */
78 enum sub_metadata_type
80 /* FREE is same as alloc state */
84 /* Page states are represented by bitpairs, at the start of the pool. */
85 #define BITS_PER_PAGE 2
87 static enum alloc_state get_page_state(const void *pool, unsigned long page)
89 return get_bit_pair(pool, page);
92 static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
94 set_bit_pair(pool, page, s);
97 /* The offset of metadata for a subpage allocation is found at the end
99 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
101 /* This is the length of metadata in bits. It consists of two bits
102 * for every BITMAP_GRANULARITY of usable bytes in the page, then two
103 * bits for the tailer.. */
104 #define BITMAP_METABITLEN \
105 ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
107 /* This is the length in bytes. */
108 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
110 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
112 unsigned int pagestatelen;
114 pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
116 ALIGNOF(struct metaheader));
117 return (struct metaheader *)((char *)pool + pagestatelen);
120 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
125 return (struct metaheader *)((char *)pool + mh->next);
128 static unsigned long pool_offset(void *pool, void *p)
130 return (char *)p - (char *)pool;
133 void alloc_init(void *pool, unsigned long poolsize)
135 /* FIXME: Alignment assumptions about pool. */
136 unsigned long len, i;
137 struct metaheader *mh;
139 if (poolsize < MIN_SIZE)
142 mh = first_mheader(pool, poolsize);
144 /* Mark all page states FREE, and all of metaheader bitmap which takes
145 * rest of first page. */
146 len = align_up(pool_offset(pool, mh + 1), getpagesize());
147 BUILD_ASSERT(FREE == 0);
148 memset(pool, 0, len);
150 /* Mark the pagestate and metadata page(s) allocated. */
151 set_page_state(pool, 0, TAKEN_START);
152 for (i = 1; i < div_up(len, getpagesize()); i++)
153 set_page_state(pool, i, TAKEN);
156 /* Two bits per element, representing page states. Returns 0 on fail.
157 * off is used to allocate from subpage bitmaps, which use the first 2
158 * bits as the type, so the real bitmap is offset by 1. */
159 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
161 unsigned long want, unsigned long align)
167 /* We allocate from far end, to increase ability to expand metadata. */
168 for (i = elems - 1; i >= 0; i--) {
169 switch (get_bit_pair(bits, off+i)) {
171 if (++free >= want) {
174 /* They might ask for large alignment. */
175 if (align && i % align)
178 set_bit_pair(bits, off+i, TAKEN_START);
179 for (j = i+1; j < i + want; j++)
180 set_bit_pair(bits, off+j, TAKEN);
195 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
196 unsigned long pages, unsigned long align)
198 return alloc_from_bitmap(pool, 0, poolsize / getpagesize(), pages,
199 align / getpagesize());
202 /* Offset to metadata is at end of page. */
203 static unsigned long *metadata_off(void *pool, unsigned long page)
205 return (unsigned long *)
206 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
209 static uint8_t *get_page_metadata(void *pool, unsigned long page)
211 return (uint8_t *)pool + *metadata_off(pool, page);
214 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
216 *metadata_off(pool, page) = meta - (uint8_t *)pool;
219 static unsigned long sub_page_alloc(void *pool, unsigned long page,
220 unsigned long size, unsigned long align)
222 uint8_t *bits = get_page_metadata(pool, page);
225 /* TAKEN at start means a bitwise alloc. */
226 assert(get_bit_pair(bits, 0) == BITMAP);
228 /* We use a standart bitmap, but offset because of that BITMAP
230 i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
231 div_up(size, BITMAP_GRANULARITY),
232 align / BITMAP_GRANULARITY);
234 /* Can't allocate? */
238 /* i-1 because of the header. */
239 return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
242 /* We look at the page states to figure out where the allocation for this
244 static unsigned long get_metalen(void *pool, unsigned long poolsize,
245 struct metaheader *mh)
247 unsigned long i, first, pages = poolsize / getpagesize();
249 first = pool_offset(pool, mh + 1)/getpagesize();
251 for (i = first + 1; i < pages && get_page_state(pool,i) == TAKEN; i++);
253 return i * getpagesize() - pool_offset(pool, mh + 1);
256 static uint8_t *alloc_metaspace(void *pool, unsigned long poolsize,
257 struct metaheader *mh, unsigned long bytes,
258 enum sub_metadata_type type)
260 uint8_t *meta = (uint8_t *)(mh + 1);
261 unsigned long free = 0, len, i, metalen;
263 metalen = get_metalen(pool, poolsize, mh);
265 /* TAKEN tags end a subpage alloc. */
266 for (i = 0; i < metalen * CHAR_BIT / BITS_PER_PAGE; i += len) {
267 switch (get_bit_pair(meta, i)) {
271 if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
272 /* Mark this as a bitmap. */
273 set_bit_pair(meta, i - free + 1, type);
274 return meta + (i - free + 1)
275 / (CHAR_BIT / BITS_PER_PAGE);
279 /* Skip over this allocated part. */
280 len = BITMAP_METALEN * CHAR_BIT / BITS_PER_PAGE;
291 /* We need this many bytes of metadata. */
292 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
293 unsigned long bytes, enum sub_metadata_type type)
295 struct metaheader *mh, *newmh;
298 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
299 uint8_t *meta = alloc_metaspace(pool, poolsize, mh, bytes,type);
305 /* No room for metadata? Can we expand an existing one? */
306 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
307 unsigned long nextpage;
309 /* We start on this page. */
310 nextpage = pool_offset(pool, (char *)(mh+1))/getpagesize();
311 /* Iterate through any other pages we own. */
312 while (get_page_state(pool, ++nextpage) == TAKEN)
314 /* Now, can we grab that page? */
315 if (get_page_state(pool, nextpage) != FREE)
318 /* OK, expand metadata, do it again. */
319 set_page_state(pool, nextpage, TAKEN);
320 BUILD_ASSERT(FREE == 0);
321 memset((char *)pool + nextpage*getpagesize(), 0, getpagesize());
322 return alloc_metaspace(pool, poolsize, mh, bytes, type);
325 /* No metadata left at all? */
326 page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
330 newmh = (struct metaheader *)((char *)pool + page * getpagesize());
331 BUILD_ASSERT(FREE == 0);
332 memset(newmh + 1, 0, getpagesize() - sizeof(*mh));
334 /* Sew it into linked list */
335 mh = first_mheader(pool,poolsize);
336 newmh->next = mh->next;
337 mh->next = pool_offset(pool, newmh);
339 return alloc_metaspace(pool, poolsize, newmh, bytes, type);
342 static void alloc_free_pages(void *pool, unsigned long pagenum)
344 assert(get_page_state(pool, pagenum) == TAKEN_START);
345 set_page_state(pool, pagenum, FREE);
346 while (get_page_state(pool, ++pagenum) == TAKEN)
347 set_page_state(pool, pagenum, FREE);
350 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
351 unsigned long size, unsigned long align)
356 /* Look for partial page. */
357 for (i = 0; i < poolsize / getpagesize(); i++) {
359 if (get_page_state(pool, i) != SPECIAL)
362 ret = sub_page_alloc(pool, i, size, align);
367 /* Create new SUBPAGE page. */
368 i = alloc_get_pages(pool, poolsize, 1, 1);
372 /* Get metadata for page. */
373 metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
375 alloc_free_pages(pool, i);
379 /* Actually, this is a subpage page now. */
380 set_page_state(pool, i, SPECIAL);
382 /* Set metadata pointer for page. */
383 set_page_metadata(pool, i, metadata);
385 /* Do allocation like normal */
386 return sub_page_alloc(pool, i, size, align);
389 /* Returns true if we cleaned any pages. */
390 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
393 bool progress = false;
395 for (i = 0; i < poolsize/getpagesize(); i++) {
398 if (get_page_state(pool, i) != SPECIAL)
401 meta = get_page_metadata(pool, i);
402 /* Skip the header (first bit of metadata). */
403 for (j = 1; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; j++)
404 if (get_bit_pair(meta, j) != FREE)
407 /* So, is this page totally empty? */
408 if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY+1) {
409 set_page_state(pool, i, FREE);
416 /* Returns true if we cleaned any pages. */
417 static bool clean_metadata(void *pool, unsigned long poolsize)
419 struct metaheader *mh, *prev_mh = NULL;
420 bool progress = false;
422 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
425 unsigned long metalen = get_metalen(pool, poolsize, mh);
427 meta = (uint8_t *)(mh + 1);
428 BUILD_ASSERT(FREE == 0);
429 for (i = metalen - 1; i > 0; i--)
433 /* Completely empty? */
434 if (prev_mh && i == metalen) {
435 alloc_free_pages(pool,
436 pool_offset(pool, mh)/getpagesize());
437 prev_mh->next = mh->next;
443 /* Some pages at end are free? */
444 for (p = (uint8_t *)(mh+1) + metalen - getpagesize();
446 p -= getpagesize()) {
459 void *alloc_get(void *pool, unsigned long poolsize,
460 unsigned long size, unsigned long align)
462 bool subpage_clean = false, metadata_clean = false;
465 if (poolsize < MIN_SIZE)
469 /* Sub-page allocations have an overhead of ~12%. */
470 if (size + size/8 >= getpagesize() || align >= getpagesize()) {
471 unsigned long pages = div_up(size, getpagesize());
473 ret = alloc_get_pages(pool, poolsize, pages, align)
476 ret = alloc_sub_page(pool, poolsize, size, align);
479 return (char *)pool + ret;
481 /* Allocation failed: garbage collection. */
482 if (!subpage_clean) {
483 subpage_clean = true;
484 if (clean_empty_subpages(pool, poolsize))
488 if (!metadata_clean) {
489 metadata_clean = true;
490 if (clean_metadata(pool, poolsize))
494 /* FIXME: Compact metadata? */
498 static void subpage_free(void *pool, unsigned long pagenum, void *free)
500 unsigned long off = (unsigned long)free % getpagesize();
503 assert(off < SUBPAGE_METAOFF);
504 assert(off % BITMAP_GRANULARITY == 0);
506 metadata = get_page_metadata(pool, pagenum);
508 off /= BITMAP_GRANULARITY;
510 /* Offset by one because first bit is used for header. */
513 set_bit_pair(metadata, off++, FREE);
514 while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
515 && get_bit_pair(metadata, off) == TAKEN)
516 set_bit_pair(metadata, off++, FREE);
519 void alloc_free(void *pool, unsigned long poolsize, void *free)
521 unsigned long pagenum;
522 struct metaheader *mh;
527 assert(poolsize >= MIN_SIZE);
529 mh = first_mheader(pool, poolsize);
530 assert((char *)free >= (char *)(mh + 1));
531 assert((char *)pool + poolsize > (char *)free);
533 pagenum = pool_offset(pool, free) / getpagesize();
535 if (get_page_state(pool, pagenum) == SPECIAL)
536 subpage_free(pool, pagenum, free);
538 assert((unsigned long)free % getpagesize() == 0);
539 alloc_free_pages(pool, pagenum);
543 static bool is_metadata_page(void *pool, unsigned long poolsize,
546 struct metaheader *mh;
548 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
549 unsigned long start, end;
551 start = pool_offset(pool, mh);
552 end = pool_offset(pool, (char *)(mh+1)
553 + get_metalen(pool, poolsize, mh));
554 if (page >= start/getpagesize() && page < end/getpagesize())
560 static bool check_subpage(void *pool, unsigned long poolsize,
563 unsigned long *mhoff = metadata_off(pool, page);
565 enum alloc_state last_state = FREE;
567 if (*mhoff + sizeof(struct metaheader) > poolsize)
570 if (*mhoff % ALIGNOF(struct metaheader) != 0)
573 /* It must point to a metadata page. */
574 if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
577 /* Header at start of subpage allocation */
578 if (get_bit_pair((uint8_t *)pool + *mhoff, 0) != BITMAP)
581 for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
582 enum alloc_state state;
584 /* +1 because header is the first byte. */
585 state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
590 if (last_state == FREE)
601 bool alloc_check(void *pool, unsigned long poolsize)
604 struct metaheader *mh;
605 enum alloc_state last_state = FREE;
606 bool was_metadata = false;
608 if (poolsize < MIN_SIZE)
611 if (get_page_state(pool, 0) != TAKEN_START)
614 /* First check metadata pages. */
615 /* Metadata pages will be marked TAKEN. */
616 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
617 unsigned long start, end;
619 start = pool_offset(pool, mh);
620 if (start + sizeof(*mh) > poolsize)
623 end = pool_offset(pool, (char *)(mh+1)
624 + get_metalen(pool, poolsize, mh));
628 /* Non-first pages should start on a page boundary. */
629 if (mh != first_mheader(pool, poolsize)
630 && start % getpagesize() != 0)
633 /* It should end on a page boundary. */
634 if (end % getpagesize() != 0)
638 for (i = 0; i < poolsize / getpagesize(); i++) {
639 enum alloc_state state = get_page_state(pool, i);
640 bool is_metadata = is_metadata_page(pool, poolsize,i);
644 /* metadata pages are never free. */
650 /* This should continue a previous block. */
651 if (last_state == FREE)
653 if (is_metadata != was_metadata)
657 /* Check metadata pointer etc. */
658 if (!check_subpage(pool, poolsize, i))
662 was_metadata = is_metadata;
667 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
669 struct metaheader *mh;
670 unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
673 if (poolsize < MIN_SIZE) {
674 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
678 memset(count, 0, sizeof(count));
679 for (i = 0; i < poolsize / getpagesize(); i++)
680 count[get_page_state(pool, i)]++;
682 mh = first_mheader(pool, poolsize);
683 pagebitlen = (char *)mh - (char *)pool;
684 fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
685 pagebitlen, count[0], count[1], count[2], count[3]);
687 /* One metadata page for every page of page bits. */
688 metadata_pages = div_up(pagebitlen, getpagesize());
690 /* Now do each metadata page. */
691 for (; mh; mh = next_mheader(pool,mh)) {
692 unsigned long free = 0, subpageblocks = 0, len = 0, metalen;
693 uint8_t *meta = (uint8_t *)(mh + 1);
695 metalen = get_metalen(pool, poolsize, mh);
696 metadata_pages += (sizeof(*mh) + metalen) / getpagesize();
698 for (i = 0; i < metalen * CHAR_BIT / BITS_PER_PAGE; i += len) {
699 switch (get_page_state(meta, i)) {
705 /* Skip over this allocated part. */
706 len = BITMAP_METALEN * CHAR_BIT;
714 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
715 pool_offset(pool, mh),
716 pool_offset(pool, (char *)(mh+1) + metalen),
718 subpageblocks * BITMAP_METALEN * 100
719 / (free + subpageblocks * BITMAP_METALEN));
722 /* Account for total pages allocated. */
723 tot = (count[1] + count[2] - metadata_pages) * getpagesize();
725 fprintf(out, "Total metadata bytes = %lu\n",
726 metadata_pages * getpagesize());
728 /* Now do every subpage. */
729 for (i = 0; i < poolsize / getpagesize(); i++) {
732 if (get_page_state(pool, i) != SPECIAL)
735 memset(count, 0, sizeof(count));
736 meta = get_page_metadata(pool, i);
737 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
738 count[get_page_state(meta, j)]++;
740 fprintf(out, "Subpage %lu: "
741 "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
742 i, count[0], count[1], count[2],
743 ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
745 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
748 /* This is optimistic, since we overalloc in several cases. */
749 fprintf(out, "Best possible allocation density = %lu%%\n",
750 tot * 100 / poolsize);