From: Rusty Russell Date: Sat, 15 Mar 2008 10:57:57 +0000 (+1100) Subject: Initial cut at file/mem allocator (pages only) X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=c9f42c0a9387dc14b17c9c75c58d34bbcf52755b;hp=bd9f392599277acd2404688d034aa98b652ee1b7 Initial cut at file/mem allocator (pages only) --- diff --git a/alloc/_info.c b/alloc/_info.c new file mode 100644 index 00000000..588dd868 --- /dev/null +++ b/alloc/_info.c @@ -0,0 +1,102 @@ +#include +#include +#include "config.h" + +/** + * alloc - memory allocator routines + * + * The alloc module implements a simple allocator which you can use to + * dynamically allocate space within a region of memory. This can be useful + * for suballocations within a given region, or a memory-mapped file. + * + * All metadata is kept within the memory handed to the allocator: you only + * need hand the pointer and the size of the memory to each call. + * + * The region contents is always in offsets, so it can be mapped in different + * places, but is not endian-safe. + * + * Example: + * #include + * #include + * #include + * #include + * #include "alloc/alloc.h" + * + * static void usage(const char *name) + * { + * errx(1, "Usage: %s --create \n" + * " %s --check \n" + * " %s --alloc \n" + * " %s --free= \n", name, name, name); + * } + * + * // Create a memory mapped file, and allocate from within it + * int main(int argc, char *argv[]) + * { + * void *a, *p; + * int fd; + * enum { CREATE, CHECK, ALLOC, FREE } cmd; + * + * if (argc != 3) + * usage(argv[0]); + * + * if (strcmp(argv[1], "--create") == 0) + * cmd = CREATE; + * else if (strcmp(argv[1], "--check") == 0) + * cmd = CHECK; + * else if (strcmp(argv[1], "--alloc") == 0) + * cmd = ALLOC; + * else if (strncmp(argv[1], "--free=", strlen("--free=")) == 0) + * cmd = FREE; + * else + * usage(argv[0]); + * + * if (cmd == CREATE) { + * fd = open(argv[2], O_RDWR|O_CREAT|O_EXCL, 0600); + * if (fd < 0) + * err(1, "Could not create %s", argv[2]); + * if (ftruncate(fd, 1048576) != 0) + * err(1, "Could not set length on %s", argv[2]); + * } else { + * fd = open(argv[2], O_RDWR); + * if (fd < 0) + * err(1, "Could not open %s", argv[2]); + * } + * + * a = mmap(NULL, 1048576, PROT_READ|PROT_WRITE, MAP_SHARED, fd,0); + * if (a == MAP_FAILED) + * err(1, "Could not map %s", argv[2]); + * + * switch (cmd) { + * case CREATE: + * alloc_init(a, 1048576); + * break; + * case CHECK: + * if (!alloc_check(a, 1048576)) + * err(1, "Region is corrupt"); + * break; + * case ALLOC: + * p = alloc_get(a, 1048576, 1024, 16); + * if (!p) + * errx(1, "Could not allocate"); + * printf("%zu\n", (char *)p - (char *)a); + * break; + * case FREE: + * p = (char *)a + atol(argv[1] + strlen("--free=")); + * alloc_free(a, 1048576, p); + * break; + * } + * return 0; + * } + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + return 0; + } + + return 1; +} diff --git a/alloc/alloc.c b/alloc/alloc.c new file mode 100644 index 00000000..f3638340 --- /dev/null +++ b/alloc/alloc.c @@ -0,0 +1,139 @@ +#include +#include +#include +#include +#include +#include "alloc.h" + +/* FIXME: Doesn't handle non-page-aligned poolsize. */ +/* FIXME: Doesn't handle sub-page allocations. */ + +#define MIN_SIZE (getpagesize() * 2) + +enum page_state +{ + FREE, + TAKEN, + 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) +{ + 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[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT)); + bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT)); +} + +static unsigned long metadata_length(void *pool, unsigned long poolsize) +{ + return ((poolsize / getpagesize() * 2 / CHAR_BIT) + getpagesize() - 1) + & ~(getpagesize() - 1); +} + +void *alloc_get(void *pool, unsigned long poolsize, + unsigned long size, unsigned long align) +{ + unsigned long i, free, want, metalen; + + if (poolsize < MIN_SIZE) + return NULL; + + /* FIXME: Necessary for this. */ + if (size == 0) + size = 1; + + want = (size + getpagesize() - 1) / getpagesize(); + metalen = metadata_length(pool, poolsize); + + free = 0; + for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) { + switch (get_page_state(pool, i)) { + case FREE: + if (++free >= want) { + unsigned int j; + char *ret = (char *)pool + metalen + + (i - want + 1) * getpagesize(); + + if ((unsigned long)ret % align) + continue; + + for (j = i; j > i - want + 1; j--) + set_page_state(pool, j, TAKEN); + set_page_state(pool, i - want + 1, TAKEN_START); + return ret; + } + break; + case TAKEN_START: + case TAKEN: + free = 0; + break; + } + } + + return NULL; +} + +void alloc_free(void *pool, unsigned long poolsize, void *free) +{ + unsigned long pagenum, metalen; + + if (poolsize < MIN_SIZE) + return; + + if (!free) + return; + + metalen = metadata_length(pool, poolsize); + + assert(free > pool && (char *)pool + poolsize > (char *)free); + assert((unsigned long)free % getpagesize() == 0); + + pagenum = ((char *)free - (char *)pool - metalen) / 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); +} + +bool alloc_check(void *pool, unsigned long poolsize) +{ + unsigned int i, metalen; + 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++) { + enum page_state state = get_page_state(pool, i); + switch (state) { + case FREE: + case TAKEN_START: + break; + case TAKEN: + if (last_state == FREE) + return false; + break; + default: + return false; + } + last_state = state; + } + return true; +} diff --git a/alloc/alloc.h b/alloc/alloc.h new file mode 100644 index 00000000..7d0aa146 --- /dev/null +++ b/alloc/alloc.h @@ -0,0 +1,11 @@ +#ifndef ALLOC_H +#define ALLOC_H +#include + +void alloc_init(void *pool, unsigned long poolsize); +void *alloc_get(void *pool, unsigned long poolsize, + unsigned long size, unsigned long align); +void alloc_free(void *pool, unsigned long poolsize, void *free); +bool alloc_check(void *pool, unsigned long poolsize); + +#endif /* ALLOC_H */ diff --git a/alloc/test/run.c b/alloc/test/run.c new file mode 100644 index 00000000..b0fbe81c --- /dev/null +++ b/alloc/test/run.c @@ -0,0 +1,136 @@ +#include "alloc/alloc.h" +#include "tap.h" +#include "alloc/alloc.c" +#include + +#define POOL_ORD 16 +#define POOL_SIZE (1 << POOL_ORD) + +#define sort(p, num, cmp) \ + qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp) + +static int addr_cmp(void **a, void **b) +{ + return (*a) - (*b); +} + +static bool unique(void *p[], unsigned int num) +{ + unsigned int i; + + for (i = 1; i < num; i++) + if (p[i] == p[i-1]) + return false; + return true; +} + +int main(int argc, char *argv[]) +{ + void *mem; + unsigned int i, num, max_size; + void *p[POOL_SIZE]; + + plan_tests(141); + + /* FIXME: Needs to be page aligned for now. */ + posix_memalign(&mem, getpagesize(), POOL_SIZE); + + /* Small pool, all allocs fail, even 0-length. */ + alloc_init(mem, 0); + ok1(alloc_check(mem, 0)); + ok1(alloc_get(mem, 0, 1, 1) == NULL); + ok1(alloc_get(mem, 0, 128, 1) == NULL); + ok1(alloc_get(mem, 0, 0, 1) == NULL); + + /* Free of NULL should work. */ + alloc_free(mem, 0, NULL); + + alloc_init(mem, POOL_SIZE); + ok1(alloc_check(mem, POOL_SIZE)); + /* Find largest allocation which works. */ + for (max_size = POOL_SIZE * 2; max_size; max_size--) { + p[0] = alloc_get(mem, POOL_SIZE, max_size, 1); + if (p[0]) + break; + } + ok1(max_size < POOL_SIZE); + ok1(max_size > 0); + ok1(alloc_check(mem, POOL_SIZE)); + + /* Free it, should be able to reallocate it. */ + alloc_free(mem, POOL_SIZE, p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + + p[0] = alloc_get(mem, POOL_SIZE, max_size, 1); + ok1(p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + alloc_free(mem, POOL_SIZE, p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + + /* Allocate a whole heap. */ + for (i = 0; i < POOL_SIZE; i++) { + p[i] = alloc_get(mem, POOL_SIZE, 1, 1); + if (!p[i]) + break; + } + + num = i; + /* Can't allocate this many. */ + ok1(num != POOL_SIZE); + ok1(alloc_check(mem, POOL_SIZE)); + + /* Sort them. */ + sort(p, num, addr_cmp); + + /* Uniqueness check */ + ok1(unique(p, num)); + + /* Free every second one. */ + for (i = 0; i < num; i += 2) { + alloc_free(mem, POOL_SIZE, p[i]); + ok1(alloc_check(mem, POOL_SIZE)); + } + for (i = 1; i < num; i += 2) { + alloc_free(mem, POOL_SIZE, p[i]); + ok1(alloc_check(mem, POOL_SIZE)); + } + ok1(alloc_check(mem, POOL_SIZE)); + + /* Should be able to reallocate max size. */ + p[0] = alloc_get(mem, POOL_SIZE, max_size, 1); + ok1(p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + + /* Re-initializing should be the same as freeing everything */ + alloc_init(mem, POOL_SIZE); + ok1(alloc_check(mem, POOL_SIZE)); + p[0] = alloc_get(mem, POOL_SIZE, max_size, 1); + ok1(p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + alloc_free(mem, POOL_SIZE, p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + + /* Alignment constraints should be met, as long as powers of two */ + for (i = 0; i < POOL_ORD-2 /* FIXME: Should be -1 */; i++) { + p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i); + ok1(p[i]); + ok1(((unsigned long)p[i] % (1 << i)) == 0); + ok1(alloc_check(mem, POOL_SIZE)); + } + + for (i = 0; i < POOL_ORD-2 /* FIXME: Should be -1 */; i++) { + alloc_free(mem, POOL_SIZE, p[i]); + ok1(alloc_check(mem, POOL_SIZE)); + } + + /* Alignment constraints for a single-byte allocation. */ + for (i = 0; i < POOL_ORD; i++) { + p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i); + ok1(p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + alloc_free(mem, POOL_SIZE, p[0]); + ok1(alloc_check(mem, POOL_SIZE)); + } + + return exit_status(); +}