/* FIXME: Reduce. */
#define MIN_SIZE (getpagesize() * 2)
-/* Metadata looks like this:
- * <unsigned long metalen> <page states> <align-pad> [<1-byte-len> <free|bit|uniform> bits...]* [unsigned long next].
+/* What's the granularity of sub-page allocs? */
+#define BITMAP_GRANULARITY 4
+
+/* File layout:
+ *
+ * file := pagestates pad metadata
+ * pagestates := pages * 2-bits-per-page
+ * pad := pad to next ALIGNOF(metadata)
+ *
+ * metadata := metalen next-ptr metabits
+ * metabits := freeblock | bitblock
+ * freeblock := 0+
+ * bitblock := 2-bits-per-bit-in-page 1
*/
+struct metaheader
+{
+ /* Length (after this header). (FIXME: Could be in pages). */
+ unsigned long metalen;
+ /* Next meta header, or 0 */
+ unsigned long next;
+ /* Bits start here. */
+};
#define BITS_PER_PAGE 2
+/* FIXME: Don't use page states for bitblock. It's tacky and confusing. */
enum page_state
{
FREE,
TAKEN,
TAKEN_START,
+ SUBPAGE,
};
+/* Assumes a is a power of two. */
+static unsigned long align_up(unsigned long x, unsigned long a)
+{
+ return (x + a - 1) & ~(a - 1);
+}
+
+static unsigned long div_up(unsigned long x, unsigned long a)
+{
+ return (x + a - 1) / a;
+}
+
+/* The offset of metadata for a subpage allocation is found at the end
+ * of the subpage */
+#define SUBPAGE_METAOFF (getpagesize() - sizeof(unsigned long))
+
+/* This is the length of metadata in bits. It consists of a TAKEN header,
+ * then two bits for every BITMAP_GRANULARITY of usable bytes in the. */
+#define BITMAP_METABITLEN \
+ ((1 + div_up(SUBPAGE_METAOFF, BITMAP_GRANULARITY)) * BITS_PER_PAGE)
+
+/* This is the length in bytes. */
+#define BITMAP_METALEN (div_up(BITMAP_METABITLEN, CHAR_BIT))
+
static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
{
- bits += sizeof(unsigned long);
return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
}
static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
{
- bits += sizeof(unsigned long);
bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
}
-/* Assumes a is a power of two. */
-static unsigned long align_up(unsigned long x, unsigned long a)
+static struct metaheader *first_mheader(void *pool, unsigned long poolsize)
{
- return (x + a - 1) & ~(a - 1);
+ unsigned int pagestatelen;
+
+ pagestatelen = align_up(div_up(poolsize/getpagesize() * BITS_PER_PAGE,
+ CHAR_BIT),
+ ALIGNOF(struct metaheader));
+ return (struct metaheader *)((char *)pool + pagestatelen);
}
-static unsigned long div_up(unsigned long x, unsigned long a)
+static struct metaheader *next_mheader(void *pool, struct metaheader *mh)
{
- return (x + a - 1) / a;
+ if (!mh->next)
+ return NULL;
+
+ return (struct metaheader *)((char *)pool + mh->next);
}
-static unsigned long metadata_length(void *pool, unsigned long poolsize)
+static unsigned long pool_offset(void *pool, void *p)
{
- return *(unsigned long *)pool;
+ return (char *)p - (char *)pool;
}
void alloc_init(void *pool, unsigned long poolsize)
{
/* FIXME: Alignment assumptions about pool. */
- unsigned long *metalen = pool, pages, pagestatebytes, i;
+ unsigned long len, i;
+ struct metaheader *mh;
if (poolsize < MIN_SIZE)
return;
- pages = poolsize / getpagesize();
+ mh = first_mheader(pool, poolsize);
- /* First comes the metadata length, then 2 bits per page, then
- * the next pointer. */
- pagestatebytes = div_up(pages * BITS_PER_PAGE, CHAR_BIT);
- *metalen = sizeof(*metalen)
- + align_up(pagestatebytes, ALIGNOF(unsigned long))
- + sizeof(unsigned long);
-
- /* Mark all the bits FREE to start, and zero the next pointer. */
+ /* len covers all page states, plus the metaheader. */
+ len = (char *)(mh + 1) - (char *)pool;
+ /* Mark all page states FREE */
BUILD_ASSERT(FREE == 0);
- memset(metalen + 1, 0, *metalen - sizeof(*metalen));
+ memset(pool, 0, len);
+
+ /* metaheader len takes us up to next page boundary. */
+ mh->metalen = align_up(len, getpagesize()) - len;
- /* Mark the metadata page(s) allocated. */
+ /* Mark the pagestate and metadata page(s) allocated. */
set_page_state(pool, 0, TAKEN_START);
- for (i = 1; i < div_up(*metalen, getpagesize()); i++)
+ for (i = 1; i < div_up(len, getpagesize()); i++)
set_page_state(pool, i, TAKEN);
}
-static void *alloc_get_pages(void *pool, unsigned long poolsize,
- unsigned long pages, unsigned long align)
+/* Two bits per element, representing page states. Returns 0 on fail. */
+static unsigned long alloc_from_bitmap(uint8_t *bits, unsigned long elems,
+ unsigned long want, unsigned long align)
+{
+ long i;
+ unsigned long free;
+
+ free = 0;
+ /* We allocate from far end, to increase ability to expand metadata. */
+ for (i = elems - 1; i >= 0; i--) {
+ switch (get_page_state(bits, i)) {
+ case FREE:
+ if (++free >= want) {
+ unsigned long j;
+
+ /* They might ask for large alignment. */
+ if (align && i % align)
+ continue;
+
+ for (j = i+1; j < i + want; j++)
+ set_page_state(bits, j, TAKEN);
+ set_page_state(bits, i, TAKEN_START);
+ return i;
+ }
+ break;
+ case SUBPAGE:
+ case TAKEN_START:
+ case TAKEN:
+ free = 0;
+ break;
+ }
+ }
+
+ return 0;
+}
+
+static unsigned long alloc_get_pages(void *pool, unsigned long poolsize,
+ unsigned long pages, unsigned long align)
{
long i;
unsigned long free;
switch (get_page_state(pool, i)) {
case FREE:
if (++free >= pages) {
- unsigned long j;
- char *ret = (char *)pool + i * getpagesize();
+ unsigned long j, addr;
+
+ addr = (unsigned long)pool + i * getpagesize();
/* They might ask for multi-page alignment. */
- if ((unsigned long)ret % align)
+ if (addr % align)
continue;
for (j = i+1; j < i + pages; j++)
set_page_state(pool, j, TAKEN);
set_page_state(pool, i, TAKEN_START);
- return ret;
+ return i;
}
break;
+ case SUBPAGE:
case TAKEN_START:
case TAKEN:
free = 0;
}
}
+ return 0;
+}
+
+/* Offset to metadata is at end of page. */
+static unsigned long *metadata_off(void *pool, unsigned long page)
+{
+ return (unsigned long *)
+ ((char *)pool + (page+1)*getpagesize() - sizeof(unsigned long));
+}
+
+static uint8_t *get_page_metadata(void *pool, unsigned long page)
+{
+ return (uint8_t *)pool + *metadata_off(pool, page);
+}
+
+static void set_page_metadata(void *pool, unsigned long page, uint8_t *meta)
+{
+ *metadata_off(pool, page) = meta - (uint8_t *)pool;
+}
+
+static void *sub_page_alloc(void *pool, unsigned long page,
+ unsigned long size, unsigned long align)
+{
+ uint8_t *bits = get_page_metadata(pool, page);
+ unsigned long i;
+
+ /* TAKEN at end means a bitwise alloc. */
+ assert(get_page_state(bits, getpagesize()/BITMAP_GRANULARITY - 1)
+ == TAKEN);
+
+ /* Our bits are the same as the page bits. */
+ i = alloc_from_bitmap(bits, getpagesize()/BITMAP_GRANULARITY,
+ div_up(size, BITMAP_GRANULARITY),
+ align / BITMAP_GRANULARITY);
+
+ /* Can't allocate? */
+ if (i == 0)
+ return NULL;
+
+ return (char *)pool + page*getpagesize() + i*BITMAP_GRANULARITY;
+}
+
+static uint8_t *alloc_metaspace(struct metaheader *mh, unsigned long bytes)
+{
+ uint8_t *meta = (uint8_t *)(mh + 1);
+ unsigned long free = 0, len;
+ long i;
+
+ /* TAKEN tags end a subpage alloc. */
+ for (i = mh->metalen * CHAR_BIT / BITS_PER_PAGE - 1; i >= 0; i -= len) {
+ switch (get_page_state(meta, i)) {
+ case FREE:
+ len = 1;
+ free++;
+ if (free == bytes * CHAR_BIT / BITS_PER_PAGE) {
+ /* TAKEN marks end of metablock. */
+ set_page_state(meta, i + free - 1, TAKEN);
+ return meta + i / (CHAR_BIT / BITS_PER_PAGE);
+ }
+ break;
+ case TAKEN:
+ /* Skip over this allocated part. */
+ len = BITMAP_METALEN * CHAR_BIT;
+ free = 0;
+ break;
+ default:
+ assert(0);
+ return NULL;
+ }
+ }
return NULL;
}
+/* We need this many bytes of metadata. */
+static uint8_t *new_metadata(void *pool, unsigned long poolsize,
+ unsigned long bytes)
+{
+ struct metaheader *mh, *newmh;
+ unsigned long page;
+
+ for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+ uint8_t *meta = alloc_metaspace(mh, bytes);
+
+ if (meta)
+ return meta;
+ }
+
+ /* No room for metadata? Can we expand an existing one? */
+ for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+ /* It should end on a page boundary. */
+ unsigned long nextpage;
+
+ nextpage = pool_offset(pool, (char *)(mh + 1) + mh->metalen);
+ assert(nextpage % getpagesize() == 0);
+
+ /* Now, can we grab that page? */
+ if (get_page_state(pool, nextpage / getpagesize()) != FREE)
+ continue;
+
+ /* OK, expand metadata, do it again. */
+ set_page_state(pool, nextpage / getpagesize(), TAKEN);
+ memset((char *)pool + nextpage, 0, getpagesize());
+ mh->metalen += getpagesize();
+ return alloc_metaspace(mh, bytes);
+ }
+
+ /* No metadata left at all? */
+ page = alloc_get_pages(pool, poolsize, div_up(bytes, getpagesize()), 1);
+ if (!page)
+ return NULL;
+
+ newmh = (struct metaheader *)((char *)pool + page * getpagesize());
+ newmh->metalen = getpagesize() - sizeof(*mh);
+ memset(newmh + 1, 0, newmh->metalen);
+
+ /* Sew it into linked list */
+ mh = first_mheader(pool,poolsize);
+ newmh->next = mh->next;
+ mh->next = (char *)newmh - (char *)pool;
+
+ return alloc_metaspace(newmh, bytes);
+}
+
+static void alloc_free_pages(void *pool, unsigned long pagenum)
+{
+ assert(get_page_state(pool, pagenum) == TAKEN_START);
+ set_page_state(pool, pagenum, FREE);
+ while (get_page_state(pool, ++pagenum) == TAKEN)
+ set_page_state(pool, pagenum, FREE);
+}
+
+static void *alloc_sub_page(void *pool, unsigned long poolsize,
+ unsigned long size, unsigned long align)
+{
+ unsigned long i;
+ uint8_t *metadata;
+
+ /* Look for partial page. */
+ for (i = 0; i < poolsize / getpagesize(); i++) {
+ void *ret;
+ if (get_page_state(pool, i) != SUBPAGE)
+ continue;
+
+ ret = sub_page_alloc(pool, i, size, align);
+ if (ret)
+ return ret;
+ }
+
+ /* Create new SUBPAGE page. */
+ i = alloc_get_pages(pool, poolsize, 1, 1);
+ if (i == 0)
+ return NULL;
+
+ /* Get metadata for page. */
+ metadata = new_metadata(pool, poolsize, BITMAP_METALEN);
+ if (!metadata) {
+ alloc_free_pages(pool, i);
+ return NULL;
+ }
+
+ /* Actually, this is a SUBPAGE page now. */
+ set_page_state(pool, i, SUBPAGE);
+
+ /* Set metadata pointer for page. */
+ set_page_metadata(pool, i, metadata);
+
+ /* Do allocation like normal */
+ return sub_page_alloc(pool, i, size, align);
+}
+
void *alloc_get(void *pool, unsigned long poolsize,
unsigned long size, unsigned long align)
{
if (poolsize < MIN_SIZE)
return NULL;
- if (size >= getpagesize() || align > getpagesize()) {
- unsigned long pages = (size + getpagesize()-1) / getpagesize();
- return alloc_get_pages(pool, poolsize, pages, align);
+ /* Sub-page allocations have an overhead of 25%. */
+ if (size + size/4 >= getpagesize() || align >= getpagesize()) {
+ unsigned long ret, pages = div_up(size, getpagesize());
+
+ ret = alloc_get_pages(pool, poolsize, pages, align);
+ if (ret == 0)
+ return NULL;
+ return (char *)pool + ret * getpagesize();
}
- /* FIXME: Sub-page allocations. */
- return alloc_get_pages(pool, poolsize, 1, align);
+ return alloc_sub_page(pool, poolsize, size, align);
+}
+
+static void subpage_free(void *pool, unsigned long pagenum, void *free)
+{
+ unsigned long off = (unsigned long)free % getpagesize();
+ uint8_t *metadata;
+
+ assert(off < SUBPAGE_METAOFF);
+ assert(off % BITMAP_GRANULARITY == 0);
+
+ metadata = get_page_metadata(pool, pagenum);
+
+ off /= BITMAP_GRANULARITY;
+
+ set_page_state(metadata, off++, FREE);
+ while (off < SUBPAGE_METAOFF / BITMAP_GRANULARITY
+ && get_page_state(metadata, off) == TAKEN)
+ set_page_state(metadata, off++, FREE);
+
+ /* FIXME: If whole page free, free page and metadata. */
}
void alloc_free(void *pool, unsigned long poolsize, void *free)
{
- unsigned long pagenum, metalen;
+ unsigned long pagenum;
+ struct metaheader *mh;
if (!free)
return;
assert(poolsize >= MIN_SIZE);
- metalen = metadata_length(pool, poolsize);
-
- assert((char *)free >= (char *)pool + metalen);
+ mh = first_mheader(pool, poolsize);
+ assert((char *)free >= (char *)(mh + 1) + mh->metalen);
assert((char *)pool + poolsize > (char *)free);
- assert((unsigned long)free % getpagesize() == 0);
- pagenum = ((char *)free - (char *)pool) / getpagesize();
+ pagenum = pool_offset(pool, free) / getpagesize();
- assert(get_page_state(pool, pagenum) == TAKEN_START);
- set_page_state(pool, pagenum, FREE);
- while (get_page_state(pool, ++pagenum) == TAKEN)
- set_page_state(pool, pagenum, FREE);
+ if (get_page_state(pool, pagenum) == SUBPAGE)
+ subpage_free(pool, pagenum, free);
+ else {
+ assert((unsigned long)free % getpagesize() == 0);
+ alloc_free_pages(pool, pagenum);
+ }
+}
+
+static bool is_metadata_page(void *pool, unsigned long poolsize,
+ unsigned long page)
+{
+ struct metaheader *mh;
+
+ for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+ unsigned long start, end;
+
+ start = pool_offset(pool, mh);
+ end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
+ if (page >= start/getpagesize() && page < end/getpagesize())
+ return true;
+ }
+ return false;
+}
+
+static bool check_subpage(void *pool, unsigned long poolsize,
+ unsigned long page)
+{
+ unsigned long *mhoff = metadata_off(pool, page);
+ unsigned int i;
+ enum page_state last_state = FREE;
+
+ if (*mhoff + sizeof(struct metaheader) > poolsize)
+ return false;
+
+ if (*mhoff % ALIGNOF(struct metaheader) != 0)
+ return false;
+
+ /* It must point to a metadata page. */
+ if (!is_metadata_page(pool, poolsize, *mhoff / getpagesize()))
+ return false;
+
+ /* Marker at end of subpage allocation is "taken" */
+ if (get_page_state((uint8_t *)pool + *mhoff,
+ getpagesize()/BITMAP_GRANULARITY - 1) != TAKEN)
+ return false;
+
+ for (i = 0; i < SUBPAGE_METAOFF / BITMAP_GRANULARITY; i++) {
+ enum page_state state;
+
+ state = get_page_state((uint8_t *)pool + *mhoff, i);
+ switch (state) {
+ case SUBPAGE:
+ return false;
+ case TAKEN:
+ if (last_state == FREE)
+ return false;
+ break;
+ default:
+ break;
+ }
+ last_state = state;
+ }
+ return true;
}
bool alloc_check(void *pool, unsigned long poolsize)
{
- unsigned long i, metalen, pagestatebytes;
+ unsigned long i;
+ struct metaheader *mh;
enum page_state last_state = FREE;
+ bool was_metadata = false;
if (poolsize < MIN_SIZE)
return true;
- metalen = metadata_length(pool, poolsize);
if (get_page_state(pool, 0) != TAKEN_START)
return false;
- pagestatebytes = div_up(poolsize / getpagesize() * BITS_PER_PAGE,
- CHAR_BIT);
- if (metalen < (sizeof(unsigned long)
- + align_up(pagestatebytes, ALIGNOF(unsigned long))
- + sizeof(unsigned long)))
- return false;
+ /* First check metadata pages. */
+ /* Metadata pages will be marked TAKEN. */
+ for (mh = first_mheader(pool,poolsize); mh; mh = next_mheader(pool,mh)){
+ unsigned long start, end;
- for (i = 1; i < poolsize / getpagesize(); i++) {
- enum page_state state = get_page_state(pool, i);
+ start = pool_offset(pool, mh);
+ if (start + sizeof(*mh) > poolsize)
+ return false;
- /* Metadata pages will be marked TAKEN. */
- if (i < div_up(metalen, getpagesize())) {
- if (get_page_state(pool, 0) != TAKEN)
- return false;
- continue;
- }
+ end = pool_offset(pool, (char *)(mh+1) + mh->metalen);
+ if (end > poolsize)
+ return false;
+
+ /* Non-first pages should start on a page boundary. */
+ if (mh != first_mheader(pool, poolsize)
+ && start % getpagesize() != 0)
+ return false;
+
+ /* It should end on a page boundary. */
+ if (end % getpagesize() != 0)
+ return false;
+ }
+
+ for (i = 0; i < poolsize / getpagesize(); i++) {
+ enum page_state state = get_page_state(pool, i);
+ bool is_metadata = is_metadata_page(pool, poolsize,i);
switch (state) {
case FREE:
+ /* metadata pages are never free. */
+ if (is_metadata)
+ return false;
case TAKEN_START:
break;
case TAKEN:
+ /* This should continue a previous block. */
if (last_state == FREE)
return false;
+ if (is_metadata != was_metadata)
+ return false;
break;
- default:
- return false;
+ case SUBPAGE:
+ /* Check metadata pointer etc. */
+ if (!check_subpage(pool, poolsize, i))
+ return false;
}
last_state = state;
+ was_metadata = is_metadata;
}
return true;
}