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 /* Length (after this header). (FIXME: implied by page bits!). */
39 unsigned long metalen;
40 /* Next meta header, or 0 */
42 /* Bits start here. */
45 /* Assumes a is a power of two. */
46 static unsigned long align_up(unsigned long x, unsigned long a)
48 return (x + a - 1) & ~(a - 1);
51 static unsigned long div_up(unsigned long x, unsigned long a)
53 return (x + a - 1) / a;
56 /* It turns out that we spend a lot of time dealing with bit pairs.
57 * These routines manipulate them.
59 static uint8_t get_bit_pair(const uint8_t *bits, unsigned long index)
61 return bits[index * 2 / CHAR_BIT] >> (index * 2 % CHAR_BIT) & 3;
64 static void set_bit_pair(uint8_t *bits, unsigned long index, uint8_t val)
66 bits[index * 2 / CHAR_BIT] &= ~(3 << (index * 2 % CHAR_BIT));
67 bits[index * 2 / CHAR_BIT] |= (val << (index * 2 % CHAR_BIT));
70 /* This is used for page states and subpage allocations */
76 SPECIAL, /* Sub-page allocation for page states. */
79 /* The types for subpage metadata. */
80 enum sub_metadata_type
82 /* FREE is same as alloc state */
86 /* Page states are represented by bitpairs, at the start of the pool. */
87 #define BITS_PER_PAGE 2
89 static enum alloc_state get_page_state(const void *pool, unsigned long page)
91 return get_bit_pair(pool, page);
94 static void set_page_state(void *pool, unsigned long page, enum alloc_state s)
96 set_bit_pair(pool, page, s);
99 /* The offset of metadata for a subpage allocation is found at the end
101 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
103 /* This is the length of metadata in bits. It consists of two bits
104 * for every BITMAP_GRANULARITY of usable bytes in the page, then two
105 * bits for the tailer.. */
106 #define BITMAP_METABITLEN \
107 ((div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY) + 1) * BITS_PER_PAGE)
109 /* This is the length in bytes. */
110 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
112 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
114 unsigned int pagestatelen;
116 pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
118 ALIGNOF(struct metaheader));
119 return (struct metaheader *)((char *)pool + pagestatelen);
122 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
127 return (struct metaheader *)((char *)pool + mh->next);
130 static unsigned long pool_offset(void *pool, void *p)
132 return (char *)p - (char *)pool;
135 void alloc_init(void *pool, unsigned long poolsize)
137 /* FIXME: Alignment assumptions about pool. */
138 unsigned long len, i;
139 struct metaheader *mh;
141 if (poolsize < MIN_SIZE)
144 mh = first_mheader(pool, poolsize);
146 /* Mark all page states FREE, and all of metaheader bitmap which takes
147 * rest of first page. */
148 len = align_up(pool_offset(pool, mh + 1), getpagesize());
149 BUILD_ASSERT(FREE == 0);
150 memset(pool, 0, len);
153 mh->metalen = len - pool_offset(pool, mh + 1);
155 /* Mark the pagestate and metadata page(s) allocated. */
156 set_page_state(pool, 0, TAKEN_START);
157 for (i = 1; i < div_up(len, getpagesize()); i++)
158 set_page_state(pool, i, TAKEN);
161 /* Two bits per element, representing page states. Returns 0 on fail.
162 * off is used to allocate from subpage bitmaps, which use the first 2
163 * bits as the type, so the real bitmap is offset by 1. */
164 static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long off,
166 unsigned long want, unsigned long align)
172 /* We allocate from far end, to increase ability to expand metadata. */
173 for (i = elems - 1; i >= 0; i--) {
174 switch (get_bit_pair(bits, off+i)) {
176 if (++free >= want) {
179 /* They might ask for large alignment. */
180 if (align && i % align)
183 set_bit_pair(bits, off+i, TAKEN_START);
184 for (j = i+1; j < i + want; j++)
185 set_bit_pair(bits, off+j, TAKEN);
200 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
201 unsigned long pages, unsigned long align)
203 return alloc_from_bitmap(pool, 0, poolsize / getpagesize(), pages,
204 align / getpagesize());
207 /* Offset to metadata is at end of page. */
208 static unsigned long *metadata_off(void *pool, unsigned long page)
210 return (unsigned long *)
211 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
214 static uint8_t *get_page_metadata(void *pool, unsigned long page)
216 return (uint8_t *)pool + *metadata_off(pool, page);
219 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
221 *metadata_off(pool, page) = meta - (uint8_t *)pool;
224 static unsigned long sub_page_alloc(void *pool, unsigned long page,
225 unsigned long size, unsigned long align)
227 uint8_t *bits = get_page_metadata(pool, page);
230 /* TAKEN at start means a bitwise alloc. */
231 assert(get_bit_pair(bits, 0) == BITMAP);
233 /* We use a standart bitmap, but offset because of that BITMAP
235 i = alloc_from_bitmap(bits, 1, SUBPAGE_METAOFF/BITMAP_GRANULARITY,
236 div_up(size, BITMAP_GRANULARITY),
237 align / BITMAP_GRANULARITY);
239 /* Can't allocate? */
243 /* i-1 because of the header. */
244 return page*getpagesize() + (i-1)*BITMAP_GRANULARITY;
247 static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes,
248 enum sub_metadata_type type)
250 uint8_t *meta = (uint8_t *)(mh + 1);
251 unsigned long free = 0, len;
254 /* TAKEN tags end a subpage alloc. */
255 for (i = 0; i < mh->metalen * CHAR_BIT / BITS_PER_PAGE; i += len) {
256 switch (get_bit_pair(meta, i)) {
260 if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
261 /* Mark this as a bitmap. */
262 set_bit_pair(meta, i - free + 1, type);
263 return meta + (i - free + 1)
264 / (CHAR_BIT / BITS_PER_PAGE);
268 /* Skip over this allocated part. */
269 len = BITMAP_METALEN * CHAR_BIT / BITS_PER_PAGE;
280 /* We need this many bytes of metadata. */
281 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
282 unsigned long bytes, enum sub_metadata_type type)
284 struct metaheader *mh, *newmh;
287 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
288 uint8_t *meta = alloc_metaspace(mh, bytes, type);
294 /* No room for metadata? Can we expand an existing one? */
295 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
296 /* It should end on a page boundary. */
297 unsigned long nextpage;
299 nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
300 assert(nextpage % getpagesize() == 0);
302 /* Now, can we grab that page? */
303 if (get_page_state(pool, nextpage / getpagesize()) != FREE)
306 /* OK, expand metadata, do it again. */
307 set_page_state(pool, nextpage / getpagesize(), TAKEN);
308 BUILD_ASSERT(FREE == 0);
309 memset((char *)pool + nextpage, 0, getpagesize());
310 mh->metalen += getpagesize();
311 return alloc_metaspace(mh, bytes, type);
314 /* No metadata left at all? */
315 page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
319 newmh = (struct metaheader *)((char *)pool + page * getpagesize());
320 newmh->metalen = getpagesize() - sizeof(*mh);
321 BUILD_ASSERT(FREE == 0);
322 memset(newmh + 1, 0, newmh->metalen);
324 /* Sew it into linked list */
325 mh = first_mheader(pool,poolsize);
326 newmh->next = mh->next;
327 mh->next = pool_offset(pool, newmh);
329 return alloc_metaspace(newmh, bytes, type);
332 static void alloc_free_pages(void *pool, unsigned long pagenum)
334 assert(get_page_state(pool, pagenum) == TAKEN_START);
335 set_page_state(pool, pagenum, FREE);
336 while (get_page_state(pool, ++pagenum) == TAKEN)
337 set_page_state(pool, pagenum, FREE);
340 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
341 unsigned long size, unsigned long align)
346 /* Look for partial page. */
347 for (i = 0; i < poolsize / getpagesize(); i++) {
349 if (get_page_state(pool, i) != SPECIAL)
352 ret = sub_page_alloc(pool, i, size, align);
357 /* Create new SUBPAGE page. */
358 i = alloc_get_pages(pool, poolsize, 1, 1);
362 /* Get metadata for page. */
363 metadata = new_metadata(pool, poolsize, BITMAP_METALEN, BITMAP);
365 alloc_free_pages(pool, i);
369 /* Actually, this is a subpage page now. */
370 set_page_state(pool, i, SPECIAL);
372 /* Set metadata pointer for page. */
373 set_page_metadata(pool, i, metadata);
375 /* Do allocation like normal */
376 return sub_page_alloc(pool, i, size, align);
379 /* Returns true if we cleaned any pages. */
380 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
383 bool progress = false;
385 for (i = 0; i < poolsize/getpagesize(); i++) {
388 if (get_page_state(pool, i) != SPECIAL)
391 meta = get_page_metadata(pool, i);
392 /* Skip the header (first bit of metadata). */
393 for (j = 1; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY+1; j++)
394 if (get_bit_pair(meta, j) != FREE)
397 /* So, is this page totally empty? */
398 if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY+1) {
399 set_page_state(pool, i, FREE);
406 /* Returns true if we cleaned any pages. */
407 static bool clean_metadata(void *pool, unsigned long poolsize)
409 struct metaheader *mh, *prev_mh = NULL;
410 bool progress = false;
412 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
416 meta = (uint8_t *)(mh + 1);
417 BUILD_ASSERT(FREE == 0);
418 for (i = mh->metalen - 1; i > 0; i--)
422 /* Completely empty? */
423 if (prev_mh && i == mh->metalen) {
424 alloc_free_pages(pool,
425 pool_offset(pool, mh)/getpagesize());
426 prev_mh->next = mh->next;
432 /* Some pages at end are free? */
433 for (p = (uint8_t *)(mh+1)+mh->metalen - getpagesize();
435 p -= getpagesize()) {
448 void *alloc_get(void *pool, unsigned long poolsize,
449 unsigned long size, unsigned long align)
451 bool subpage_clean = false, metadata_clean = false;
454 if (poolsize < MIN_SIZE)
458 /* Sub-page allocations have an overhead of ~12%. */
459 if (size + size/8 >= getpagesize() || align >= getpagesize()) {
460 unsigned long pages = div_up(size, getpagesize());
462 ret = alloc_get_pages(pool, poolsize, pages, align)
465 ret = alloc_sub_page(pool, poolsize, size, align);
468 return (char *)pool + ret;
470 /* Allocation failed: garbage collection. */
471 if (!subpage_clean) {
472 subpage_clean = true;
473 if (clean_empty_subpages(pool, poolsize))
477 if (!metadata_clean) {
478 metadata_clean = true;
479 if (clean_metadata(pool, poolsize))
483 /* FIXME: Compact metadata? */
487 static void subpage_free(void *pool, unsigned long pagenum, void *free)
489 unsigned long off = (unsigned long)free % getpagesize();
492 assert(off < SUBPAGE_METAOFF);
493 assert(off % BITMAP_GRANULARITY == 0);
495 metadata = get_page_metadata(pool, pagenum);
497 off /= BITMAP_GRANULARITY;
499 /* Offset by one because first bit is used for header. */
502 set_bit_pair(metadata, off++, FREE);
503 while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
504 && get_bit_pair(metadata, off) == TAKEN)
505 set_bit_pair(metadata, off++, FREE);
508 void alloc_free(void *pool, unsigned long poolsize, void *free)
510 unsigned long pagenum;
511 struct metaheader *mh;
516 assert(poolsize >= MIN_SIZE);
518 mh = first_mheader(pool, poolsize);
519 assert((char *)free >= (char *)(mh + 1) + mh->metalen);
520 assert((char *)pool + poolsize > (char *)free);
522 pagenum = pool_offset(pool, free) / getpagesize();
524 if (get_page_state(pool, pagenum) == SPECIAL)
525 subpage_free(pool, pagenum, free);
527 assert((unsigned long)free % getpagesize() == 0);
528 alloc_free_pages(pool, pagenum);
532 static bool is_metadata_page(void *pool, unsigned long poolsize,
535 struct metaheader *mh;
537 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
538 unsigned long start, end;
540 start = pool_offset(pool, mh);
541 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
542 if (page >= start/getpagesize() && page < end/getpagesize())
548 static bool check_subpage(void *pool, unsigned long poolsize,
551 unsigned long *mhoff = metadata_off(pool, page);
553 enum alloc_state last_state = FREE;
555 if (*mhoff + sizeof(struct metaheader) > poolsize)
558 if (*mhoff % ALIGNOF(struct metaheader) != 0)
561 /* It must point to a metadata page. */
562 if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
565 /* Header at start of subpage allocation */
566 if (get_bit_pair((uint8_t *)pool + *mhoff, 0) != BITMAP)
569 for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
570 enum alloc_state state;
572 /* +1 because header is the first byte. */
573 state = get_bit_pair((uint8_t *)pool + *mhoff, i+1);
578 if (last_state == FREE)
589 bool alloc_check(void *pool, unsigned long poolsize)
592 struct metaheader *mh;
593 enum alloc_state last_state = FREE;
594 bool was_metadata = false;
596 if (poolsize < MIN_SIZE)
599 if (get_page_state(pool, 0) != TAKEN_START)
602 /* First check metadata pages. */
603 /* Metadata pages will be marked TAKEN. */
604 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
605 unsigned long start, end;
607 start = pool_offset(pool, mh);
608 if (start + sizeof(*mh) > poolsize)
611 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
615 /* Non-first pages should start on a page boundary. */
616 if (mh != first_mheader(pool, poolsize)
617 && start % getpagesize() != 0)
620 /* It should end on a page boundary. */
621 if (end % getpagesize() != 0)
625 for (i = 0; i < poolsize / getpagesize(); i++) {
626 enum alloc_state state = get_page_state(pool, i);
627 bool is_metadata = is_metadata_page(pool, poolsize,i);
631 /* metadata pages are never free. */
637 /* This should continue a previous block. */
638 if (last_state == FREE)
640 if (is_metadata != was_metadata)
644 /* Check metadata pointer etc. */
645 if (!check_subpage(pool, poolsize, i))
649 was_metadata = is_metadata;
654 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
656 struct metaheader *mh;
657 unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
660 if (poolsize < MIN_SIZE) {
661 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
665 memset(count, 0, sizeof(count));
666 for (i = 0; i < poolsize / getpagesize(); i++)
667 count[get_page_state(pool, i)]++;
669 mh = first_mheader(pool, poolsize);
670 pagebitlen = (char *)mh - (char *)pool;
671 fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
672 pagebitlen, count[0], count[1], count[2], count[3]);
674 /* One metadata page for every page of page bits. */
675 metadata_pages = div_up(pagebitlen, getpagesize());
677 /* Now do each metadata page. */
678 for (; mh; mh = next_mheader(pool,mh)) {
679 unsigned long free = 0, subpageblocks = 0, len = 0;
680 uint8_t *meta = (uint8_t *)(mh + 1);
682 metadata_pages += (sizeof(*mh) + mh->metalen) / getpagesize();
685 i < mh->metalen * CHAR_BIT / BITS_PER_PAGE;
687 switch (get_page_state(meta, i)) {
693 /* Skip over this allocated part. */
694 len = BITMAP_METALEN * CHAR_BIT;
702 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
703 pool_offset(pool, mh),
704 pool_offset(pool, (char *)(mh+1) + mh->metalen),
706 subpageblocks * BITMAP_METALEN * 100
707 / (free + subpageblocks * BITMAP_METALEN));
710 /* Account for total pages allocated. */
711 tot = (count[1] + count[2] - metadata_pages) * getpagesize();
713 fprintf(out, "Total metadata bytes = %lu\n",
714 metadata_pages * getpagesize());
716 /* Now do every subpage. */
717 for (i = 0; i < poolsize / getpagesize(); i++) {
720 if (get_page_state(pool, i) != SPECIAL)
723 memset(count, 0, sizeof(count));
724 meta = get_page_metadata(pool, i);
725 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
726 count[get_page_state(meta, j)]++;
728 fprintf(out, "Subpage %lu: "
729 "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
730 i, count[0], count[1], count[2],
731 ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
733 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
736 /* This is optimistic, since we overalloc in several cases. */
737 fprintf(out, "Best possible allocation density = %lu%%\n",
738 tot * 100 / poolsize);