X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=alloc%2Falloc.c;h=1bf9ade7f2e5c13fe06f81dfe7fd171b6287309f;hp=3ec6952c82c8b6d20187ea722d56a907d518548f;hb=3d34b48fce2c63217969232d1924f66a91fb404f;hpb=294f8d35427a7f5a0afe872fee7d4a47494d6add diff --git a/alloc/alloc.c b/alloc/alloc.c index 3ec6952c..1bf9ade7 100644 --- a/alloc/alloc.c +++ b/alloc/alloc.c @@ -4,12 +4,26 @@ #include #include #include "alloc.h" +#include "build_assert/build_assert.h" +#include "config.h" + +#if HAVE_ALIGNOF +#define ALIGNOF(t) __alignof__(t) +#else +/* Alignment by measuring structure padding. */ +#define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t)) +#endif /* FIXME: Doesn't handle non-page-aligned poolsize. */ -/* FIXME: Doesn't handle sub-page allocations. */ +/* FIXME: Reduce. */ #define MIN_SIZE (getpagesize() * 2) +/* Metadata looks like this: + * [<1-byte-len> bits...]* [unsigned long next]. + */ + +#define BITS_PER_PAGE 2 enum page_state { FREE, @@ -17,65 +31,82 @@ enum page_state TAKEN_START, }; -void alloc_init(void *pool, unsigned long poolsize) -{ - uint8_t *bits = pool; - unsigned int pages = poolsize / getpagesize(); - - if (poolsize < MIN_SIZE) - return; - - memset(bits, 0, (pages * 2 + CHAR_BIT - 1)/ 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) +{ + return (x + a - 1) & ~(a - 1); +} + +static unsigned long div_up(unsigned long x, unsigned long a) +{ + return (x + a - 1) / a; +} + static unsigned long metadata_length(void *pool, unsigned long poolsize) { - return ((poolsize / getpagesize() * 2 / CHAR_BIT) + getpagesize() - 1) - & ~(getpagesize() - 1); + return *(unsigned long *)pool; } -void *alloc_get(void *pool, unsigned long poolsize, - unsigned long size, unsigned long align) +void alloc_init(void *pool, unsigned long poolsize) { - long i; - unsigned long free, want, metalen; + /* FIXME: Alignment assumptions about pool. */ + unsigned long *metalen = pool, pages, pagestatebytes, i; if (poolsize < MIN_SIZE) - return NULL; + return; - /* FIXME: Necessary for this. */ - if (size == 0) - size = 1; + pages = poolsize / getpagesize(); - want = (size + getpagesize() - 1) / getpagesize(); - metalen = metadata_length(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. */ + BUILD_ASSERT(FREE == 0); + memset(metalen + 1, 0, *metalen - sizeof(*metalen)); + + /* Mark the metadata page(s) allocated. */ + set_page_state(pool, 0, TAKEN_START); + for (i = 1; i < div_up(*metalen, getpagesize()); i++) + set_page_state(pool, i, TAKEN); +} + +static void *alloc_get_pages(void *pool, unsigned long poolsize, + unsigned long pages, unsigned long align) +{ + long i; + unsigned long free; free = 0; /* We allocate from far end, to increase ability to expand metadata. */ - for (i = (poolsize - metalen) / getpagesize() - 1; i >= 0; i--) { + for (i = poolsize / getpagesize() - 1; i >= 0; i--) { switch (get_page_state(pool, i)) { case FREE: - if (++free >= want) { + if (++free >= pages) { unsigned long j; - char *ret = (char *)pool + metalen - + i * getpagesize(); + char *ret = (char *)pool + i * getpagesize(); /* They might ask for multi-page alignment. */ if ((unsigned long)ret % align) continue; - for (j = i+1; j < i + want; j++) + for (j = i+1; j < i + pages; j++) set_page_state(pool, j, TAKEN); set_page_state(pool, i, TAKEN_START); return ret; @@ -91,22 +122,37 @@ void *alloc_get(void *pool, unsigned long poolsize, return NULL; } +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); + } + + /* FIXME: Sub-page allocations. */ + return alloc_get_pages(pool, poolsize, 1, align); +} + void alloc_free(void *pool, unsigned long poolsize, void *free) { unsigned long pagenum, metalen; - if (poolsize < MIN_SIZE) - return; - if (!free) return; + assert(poolsize >= MIN_SIZE); + metalen = metadata_length(pool, poolsize); - assert(free > pool && (char *)pool + poolsize > (char *)free); + assert((char *)free >= (char *)pool + metalen); + assert((char *)pool + poolsize > (char *)free); assert((unsigned long)free % getpagesize() == 0); - pagenum = ((char *)free - (char *)pool - metalen) / getpagesize(); + pagenum = ((char *)free - (char *)pool) / getpagesize(); assert(get_page_state(pool, pagenum) == TAKEN_START); set_page_state(pool, pagenum, FREE); @@ -116,15 +162,33 @@ void alloc_free(void *pool, unsigned long poolsize, void *free) bool alloc_check(void *pool, unsigned long poolsize) { - unsigned int i, metalen; + unsigned long i, metalen, pagestatebytes; enum page_state last_state = FREE; if (poolsize < MIN_SIZE) return true; metalen = metadata_length(pool, poolsize); - for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) { + 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; + + for (i = 1; i < poolsize / getpagesize(); i++) { enum page_state state = get_page_state(pool, i); + + /* Metadata pages will be marked TAKEN. */ + if (i < div_up(metalen, getpagesize())) { + if (get_page_state(pool, 0) != TAKEN) + return false; + continue; + } + switch (state) { case FREE: case TAKEN_START: