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 #define BITS_PER_PAGE 2
46 /* FIXME: Don't use page states for bitblock. It's tacky and confusing. */
55 /* Assumes a is a power of two. */
56 static unsigned long align_up(unsigned long x, unsigned long a)
58 return (x + a - 1) & ~(a - 1);
61 static unsigned long div_up(unsigned long x, unsigned long a)
63 return (x + a - 1) / a;
66 /* The offset of metadata for a subpage allocation is found at the end
68 #define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
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)
76 /* This is the length in bytes. */
77 #define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
79 static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
81 return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
84 static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
86 bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
87 bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
90 static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
92 unsigned int pagestatelen;
94 pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
96 ALIGNOF(struct metaheader));
97 return (struct metaheader *)((char *)pool + pagestatelen);
100 static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
105 return (struct metaheader *)((char *)pool + mh->next);
108 static unsigned long pool_offset(void *pool, void *p)
110 return (char *)p - (char *)pool;
113 void alloc_init(void *pool, unsigned long poolsize)
115 /* FIXME: Alignment assumptions about pool. */
116 unsigned long len, i;
117 struct metaheader *mh;
119 if (poolsize < MIN_SIZE)
122 mh = first_mheader(pool, poolsize);
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);
130 /* metaheader len takes us up to next page boundary. */
131 mh->metalen = align_up(len, getpagesize()) - len;
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);
139 /* Two bits per element, representing page states. Returns -1 on fail. */
140 static long alloc_from_bitmap(uint8_t *bits, unsigned long elems,
141 unsigned long want, unsigned long align)
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)) {
151 if (++free >= want) {
154 /* They might ask for large alignment. */
155 if (align && i % align)
158 for (j = i+1; j < i + want; j++)
159 set_page_state(bits, j, TAKEN);
160 set_page_state(bits, i, TAKEN_START);
175 static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
176 unsigned long pages, unsigned long align)
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)) {
186 if (++free >= pages) {
187 unsigned long j, addr;
189 addr = (unsigned long)pool + i * getpagesize();
191 /* They might ask for multi-page alignment. */
195 for (j = i+1; j < i + pages; j++)
196 set_page_state(pool, j, TAKEN);
197 set_page_state(pool, i, TAKEN_START);
212 /* Offset to metadata is at end of page. */
213 static unsigned long *metadata_off(void *pool, unsigned long page)
215 return (unsigned long *)
216 ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
219 static uint8_t *get_page_metadata(void *pool, unsigned long page)
221 return (uint8_t *)pool + *metadata_off(pool, page);
224 static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
226 *metadata_off(pool, page) = meta - (uint8_t *)pool;
229 static unsigned long sub_page_alloc(void *pool, unsigned long page,
230 unsigned long size, unsigned long align)
232 uint8_t *bits = get_page_metadata(pool, page);
235 /* TAKEN at end means a bitwise alloc. */
236 assert(get_page_state(bits, getpagesize()/BITMAP_GRANULARITY - 1)
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);
244 /* Can't allocate? */
248 return page*getpagesize() + i*BITMAP_GRANULARITY;
251 static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes)
253 uint8_t *meta = (uint8_t *)(mh + 1);
254 unsigned long free = 0, len;
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)) {
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);
270 /* Skip over this allocated part. */
271 len = BITMAP_METALEN * CHAR_BIT / BITS_PER_PAGE;
282 /* We need this many bytes of metadata. */
283 static uint8_t *new_metadata(void *pool, unsigned long poolsize,
286 struct metaheader *mh, *newmh;
289 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
290 uint8_t *meta = alloc_metaspace(mh, bytes);
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;
301 nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
302 assert(nextpage % getpagesize() == 0);
304 /* Now, can we grab that page? */
305 if (get_page_state(pool, nextpage / getpagesize()) != FREE)
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);
316 /* No metadata left at all? */
317 page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
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);
326 /* Sew it into linked list */
327 mh = first_mheader(pool,poolsize);
328 newmh->next = mh->next;
329 mh->next = pool_offset(pool, newmh);
331 return alloc_metaspace(newmh, bytes);
334 static void alloc_free_pages(void *pool, unsigned long pagenum)
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);
342 static unsigned long alloc_sub_page(void *pool, unsigned long poolsize,
343 unsigned long size, unsigned long align)
348 /* Look for partial page. */
349 for (i = 0; i < poolsize / getpagesize(); i++) {
351 if (get_page_state(pool, i) != SUBPAGE)
354 ret = sub_page_alloc(pool, i, size, align);
359 /* Create new SUBPAGE page. */
360 i = alloc_get_pages(pool, poolsize, 1, 1);
364 /* Get metadata for page. */
365 metadata = new_metadata(pool, poolsize, BITMAP_METALEN);
367 alloc_free_pages(pool, i);
371 /* Actually, this is a SUBPAGE page now. */
372 set_page_state(pool, i, SUBPAGE);
374 /* Set metadata pointer for page. */
375 set_page_metadata(pool, i, metadata);
377 /* Do allocation like normal */
378 return sub_page_alloc(pool, i, size, align);
381 /* Returns true if we cleaned any pages. */
382 static bool clean_empty_subpages(void *pool, unsigned long poolsize)
385 bool progress = false;
387 for (i = 0; i < poolsize/getpagesize(); i++) {
390 if (get_page_state(pool, i) != SUBPAGE)
393 meta = get_page_metadata(pool, i);
394 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
395 if (get_page_state(meta, j) != FREE)
398 /* So, is this page totally empty? */
399 if (j == SUBPAGE_METAOFF/BITMAP_GRANULARITY) {
400 set_page_state(pool, i, FREE);
407 /* Returns true if we cleaned any pages. */
408 static bool clean_metadata(void *pool, unsigned long poolsize)
410 struct metaheader *mh, *prev_mh = NULL;
411 bool progress = false;
413 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
417 meta = (uint8_t *)(mh + 1);
418 BUILD_ASSERT(FREE == 0);
419 for (i = mh->metalen - 1; i > 0; i--)
423 /* Completely empty? */
424 if (prev_mh && i == mh->metalen) {
425 alloc_free_pages(pool,
426 pool_offset(pool, mh)/getpagesize());
427 prev_mh->next = mh->next;
433 /* Some pages at end are free? */
434 for (p = (uint8_t *)(mh+1)+mh->metalen - getpagesize();
436 p -= getpagesize()) {
449 void *alloc_get(void *pool, unsigned long poolsize,
450 unsigned long size, unsigned long align)
452 bool subpage_clean = false, metadata_clean = false;
455 if (poolsize < MIN_SIZE)
459 /* Sub-page allocations have an overhead of ~12%. */
460 if (size + size/8 >= getpagesize() || align >= getpagesize()) {
461 unsigned long pages = div_up(size, getpagesize());
463 ret = alloc_get_pages(pool, poolsize, pages, align)
466 ret = alloc_sub_page(pool, poolsize, size, align);
469 return (char *)pool + ret;
471 /* Allocation failed: garbage collection. */
472 if (!subpage_clean) {
473 subpage_clean = true;
474 if (clean_empty_subpages(pool, poolsize))
478 if (!metadata_clean) {
479 metadata_clean = true;
480 if (clean_metadata(pool, poolsize))
484 /* FIXME: Compact metadata? */
488 static void subpage_free(void *pool, unsigned long pagenum, void *free)
490 unsigned long off = (unsigned long)free % getpagesize();
493 assert(off < SUBPAGE_METAOFF);
494 assert(off % BITMAP_GRANULARITY == 0);
496 metadata = get_page_metadata(pool, pagenum);
498 off /= BITMAP_GRANULARITY;
500 set_page_state(metadata, off++, FREE);
501 while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
502 && get_page_state(metadata, off) == TAKEN)
503 set_page_state(metadata, off++, FREE);
506 void alloc_free(void *pool, unsigned long poolsize, void *free)
508 unsigned long pagenum;
509 struct metaheader *mh;
514 assert(poolsize >= MIN_SIZE);
516 mh = first_mheader(pool, poolsize);
517 assert((char *)free >= (char *)(mh + 1) + mh->metalen);
518 assert((char *)pool + poolsize > (char *)free);
520 pagenum = pool_offset(pool, free) / getpagesize();
522 if (get_page_state(pool, pagenum) == SUBPAGE)
523 subpage_free(pool, pagenum, free);
525 assert((unsigned long)free % getpagesize() == 0);
526 alloc_free_pages(pool, pagenum);
530 static bool is_metadata_page(void *pool, unsigned long poolsize,
533 struct metaheader *mh;
535 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
536 unsigned long start, end;
538 start = pool_offset(pool, mh);
539 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
540 if (page >= start/getpagesize() && page < end/getpagesize())
546 static bool check_subpage(void *pool, unsigned long poolsize,
549 unsigned long *mhoff = metadata_off(pool, page);
551 enum page_state last_state = FREE;
553 if (*mhoff + sizeof(struct metaheader) > poolsize)
556 if (*mhoff % ALIGNOF(struct metaheader) != 0)
559 /* It must point to a metadata page. */
560 if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
563 /* Marker at end of subpage allocation is "taken" */
564 if (get_page_state((uint8_t *)pool + *mhoff,
565 getpagesize()/BITMAP_GRANULARITY - 1) != TAKEN)
568 for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
569 enum page_state state;
571 state = get_page_state((uint8_t *)pool + *mhoff, i);
576 if (last_state == FREE)
587 bool alloc_check(void *pool, unsigned long poolsize)
590 struct metaheader *mh;
591 enum page_state last_state = FREE;
592 bool was_metadata = false;
594 if (poolsize < MIN_SIZE)
597 if (get_page_state(pool, 0) != TAKEN_START)
600 /* First check metadata pages. */
601 /* Metadata pages will be marked TAKEN. */
602 for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
603 unsigned long start, end;
605 start = pool_offset(pool, mh);
606 if (start + sizeof(*mh) > poolsize)
609 end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
613 /* Non-first pages should start on a page boundary. */
614 if (mh != first_mheader(pool, poolsize)
615 && start % getpagesize() != 0)
618 /* It should end on a page boundary. */
619 if (end % getpagesize() != 0)
623 for (i = 0; i < poolsize / getpagesize(); i++) {
624 enum page_state state = get_page_state(pool, i);
625 bool is_metadata = is_metadata_page(pool, poolsize,i);
629 /* metadata pages are never free. */
635 /* This should continue a previous block. */
636 if (last_state == FREE)
638 if (is_metadata != was_metadata)
642 /* Check metadata pointer etc. */
643 if (!check_subpage(pool, poolsize, i))
647 was_metadata = is_metadata;
652 void alloc_visualize(FILE *out, void *pool, unsigned long poolsize)
654 struct metaheader *mh;
655 unsigned long pagebitlen, metadata_pages, count[1<<BITS_PER_PAGE], tot;
658 if (poolsize < MIN_SIZE) {
659 fprintf(out, "Pool smaller than %u: no content\n", MIN_SIZE);
663 memset(count, 0, sizeof(count));
664 for (i = 0; i < poolsize / getpagesize(); i++)
665 count[get_page_state(pool, i)]++;
667 mh = first_mheader(pool, poolsize);
668 pagebitlen = (char *)mh - (char *)pool;
669 fprintf(out, "%lu bytes of page bits: FREE/TAKEN/TAKEN_START/SUBPAGE = %lu/%lu/%lu/%lu\n",
670 pagebitlen, count[0], count[1], count[2], count[3]);
672 /* One metadata page for every page of page bits. */
673 metadata_pages = div_up(pagebitlen, getpagesize());
675 /* Now do each metadata page. */
676 for (; mh; mh = next_mheader(pool,mh)) {
677 unsigned long free = 0, subpageblocks = 0, len = 0;
678 uint8_t *meta = (uint8_t *)(mh + 1);
680 metadata_pages += (sizeof(*mh) + mh->metalen) / getpagesize();
682 /* TAKEN tags end a subpage alloc. */
683 for (i = mh->metalen * CHAR_BIT/BITS_PER_PAGE - 1;
686 switch (get_page_state(meta, i)) {
692 /* Skip over this allocated part. */
693 len = BITMAP_METALEN * CHAR_BIT;
701 fprintf(out, "Metadata %lu-%lu: %lu free, %lu subpageblocks, %lu%% density\n",
702 pool_offset(pool, mh),
703 pool_offset(pool, (char *)(mh+1) + mh->metalen),
705 subpageblocks * BITMAP_METALEN * 100
706 / (free + subpageblocks * BITMAP_METALEN));
709 /* Account for total pages allocated. */
710 tot = (count[1] + count[2] - metadata_pages) * getpagesize();
712 fprintf(out, "Total metadata bytes = %lu\n",
713 metadata_pages * getpagesize());
715 /* Now do every subpage. */
716 for (i = 0; i < poolsize / getpagesize(); i++) {
719 if (get_page_state(pool, i) != SUBPAGE)
722 memset(count, 0, sizeof(count));
723 meta = get_page_metadata(pool, i);
724 for (j = 0; j < SUBPAGE_METAOFF/BITMAP_GRANULARITY; j++)
725 count[get_page_state(meta, j)]++;
727 fprintf(out, "Subpage %lu: "
728 "FREE/TAKEN/TAKEN_START = %lu/%lu/%lu %lu%% density\n",
729 i, count[0], count[1], count[2],
730 ((count[1] + count[2]) * BITMAP_GRANULARITY) * 100
732 tot += (count[1] + count[2]) * BITMAP_GRANULARITY;
735 /* This is optimistic, since we overalloc in several cases. */
736 fprintf(out, "Best possible allocation density = %lu%%\n",
737 tot * 100 / poolsize);