From: Rusty Russell Date: Mon, 12 Jul 2010 13:52:30 +0000 (+0930) Subject: alloc: first cut of tiny allocator (down to 2 bytes!) X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=7f9d956574d30f70d2260f4b7694f481e3765173;ds=sidebyside alloc: first cut of tiny allocator (down to 2 bytes!) --- diff --git a/ccan/alloc/alloc.c b/ccan/alloc/alloc.c index 535e7b47..bc3760ab 100644 --- a/ccan/alloc/alloc.c +++ b/ccan/alloc/alloc.c @@ -5,6 +5,8 @@ #include #include #include "alloc.h" +#include "bitops.h" +#include "tiny.h" #include #include #include @@ -91,146 +93,6 @@ struct page_header { unsigned long used[1]; /* One bit per element. */ }; -/* 2 bit for every byte to allocate. */ -static void tiny_alloc_init(void *pool, unsigned long poolsize) -{ -/* FIXME */ -} - -static void *tiny_alloc_get(void *pool, unsigned long poolsize, - unsigned long size, unsigned long align) -{ -/* FIXME */ - return NULL; -} - -static void tiny_alloc_free(void *pool, unsigned long poolsize, void *free) -{ -/* FIXME */ -} - -static unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, - void *p) -{ -/* FIXME */ - return 0; -} - -static bool tiny_alloc_check(void *pool, unsigned long poolsize) -{ -/* FIXME */ - return true; -} - -static unsigned int fls(unsigned long val) -{ -#if HAVE_BUILTIN_CLZL - /* This is significantly faster! */ - return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0; -#else - unsigned int r = 32; - - if (!val) - return 0; - if (!(val & 0xffff0000u)) { - val <<= 16; - r -= 16; - } - if (!(val & 0xff000000u)) { - val <<= 8; - r -= 8; - } - if (!(val & 0xf0000000u)) { - val <<= 4; - r -= 4; - } - if (!(val & 0xc0000000u)) { - val <<= 2; - r -= 2; - } - if (!(val & 0x80000000u)) { - val <<= 1; - r -= 1; - } - return r; -#endif -} - -/* FIXME: Move to bitops. */ -static unsigned int ffsl(unsigned long val) -{ -#if HAVE_BUILTIN_FFSL - /* This is significantly faster! */ - return __builtin_ffsl(val); -#else - unsigned int r = 1; - - if (!val) - return 0; - if (sizeof(long) == sizeof(u64)) { - if (!(val & 0xffffffff)) { - /* Workaround gcc warning on 32-bit: - error: right shift count >= width of type */ - u64 tmp = val; - tmp >>= 32; - val = tmp; - r += 32; - } - } - if (!(val & 0xffff)) { - val >>= 16; - r += 16; - } - if (!(val & 0xff)) { - val >>= 8; - r += 8; - } - if (!(val & 0xf)) { - val >>= 4; - r += 4; - } - if (!(val & 3)) { - val >>= 2; - r += 2; - } - if (!(val & 1)) { - val >>= 1; - r += 1; - } - return r; -#endif -} - -static unsigned int popcount(unsigned long val) -{ -#if HAVE_BUILTIN_POPCOUNTL - return __builtin_popcountl(val); -#else - if (sizeof(long) == sizeof(u64)) { - u64 v = val; - v = (v & 0x5555555555555555ULL) - + ((v >> 1) & 0x5555555555555555ULL); - v = (v & 0x3333333333333333ULL) - + ((v >> 1) & 0x3333333333333333ULL); - v = (v & 0x0F0F0F0F0F0F0F0FULL) - + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL); - v = (v & 0x00FF00FF00FF00FFULL) - + ((v >> 1) & 0x00FF00FF00FF00FFULL); - v = (v & 0x0000FFFF0000FFFFULL) - + ((v >> 1) & 0x0000FFFF0000FFFFULL); - v = (v & 0x00000000FFFFFFFFULL) - + ((v >> 1) & 0x00000000FFFFFFFFULL); - return v; - } - val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL); - val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL); - val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL); - val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL); - val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL); - return val; -#endif -} - /* * Every 4 buckets, the size doubles. * Between buckets, sizes increase linearly. @@ -274,11 +136,6 @@ static unsigned int small_page_bits(unsigned long poolsize) return fls(poolsize / MAX_SMALL_PAGES / 2); } -static unsigned long align_up(unsigned long x, unsigned long align) -{ - return (x + align - 1) & ~(align - 1); -} - static struct page_header *from_pgnum(struct header *head, unsigned long pgnum, unsigned sp_bits) @@ -1051,10 +908,6 @@ static unsigned long visualize_bucket(FILE *out, struct header *head, return overhead; } -static void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize) -{ -} - void alloc_visualize(FILE *out, void *pool, unsigned long poolsize) { struct header *head = pool; diff --git a/ccan/alloc/bitops.c b/ccan/alloc/bitops.c new file mode 100644 index 00000000..ad4465f9 --- /dev/null +++ b/ccan/alloc/bitops.c @@ -0,0 +1,118 @@ +#include "bitops.h" +#include "config.h" +#include +#include + +unsigned int fls(unsigned long val) +{ +#if HAVE_BUILTIN_CLZL + /* This is significantly faster! */ + return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0; +#else + unsigned int r = 32; + + if (!val) + return 0; + if (!(val & 0xffff0000u)) { + val <<= 16; + r -= 16; + } + if (!(val & 0xff000000u)) { + val <<= 8; + r -= 8; + } + if (!(val & 0xf0000000u)) { + val <<= 4; + r -= 4; + } + if (!(val & 0xc0000000u)) { + val <<= 2; + r -= 2; + } + if (!(val & 0x80000000u)) { + val <<= 1; + r -= 1; + } + return r; +#endif +} + +/* FIXME: Move to bitops. */ +unsigned int ffsl(unsigned long val) +{ +#if HAVE_BUILTIN_FFSL + /* This is significantly faster! */ + return __builtin_ffsl(val); +#else + unsigned int r = 1; + + if (!val) + return 0; + if (sizeof(long) == sizeof(u64)) { + if (!(val & 0xffffffff)) { + /* Workaround gcc warning on 32-bit: + error: right shift count >= width of type */ + u64 tmp = val; + tmp >>= 32; + val = tmp; + r += 32; + } + } + if (!(val & 0xffff)) { + val >>= 16; + r += 16; + } + if (!(val & 0xff)) { + val >>= 8; + r += 8; + } + if (!(val & 0xf)) { + val >>= 4; + r += 4; + } + if (!(val & 3)) { + val >>= 2; + r += 2; + } + if (!(val & 1)) { + val >>= 1; + r += 1; + } + return r; +#endif +} + +unsigned int popcount(unsigned long val) +{ +#if HAVE_BUILTIN_POPCOUNTL + return __builtin_popcountl(val); +#else + if (sizeof(long) == sizeof(u64)) { + u64 v = val; + v = (v & 0x5555555555555555ULL) + + ((v >> 1) & 0x5555555555555555ULL); + v = (v & 0x3333333333333333ULL) + + ((v >> 1) & 0x3333333333333333ULL); + v = (v & 0x0F0F0F0F0F0F0F0FULL) + + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL); + v = (v & 0x00FF00FF00FF00FFULL) + + ((v >> 1) & 0x00FF00FF00FF00FFULL); + v = (v & 0x0000FFFF0000FFFFULL) + + ((v >> 1) & 0x0000FFFF0000FFFFULL); + v = (v & 0x00000000FFFFFFFFULL) + + ((v >> 1) & 0x00000000FFFFFFFFULL); + return v; + } + val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL); + val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL); + val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL); + val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL); + val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL); + return val; +#endif +} + +unsigned long align_up(unsigned long x, unsigned long align) +{ + return (x + align - 1) & ~(align - 1); +} diff --git a/ccan/alloc/bitops.h b/ccan/alloc/bitops.h new file mode 100644 index 00000000..11ec950e --- /dev/null +++ b/ccan/alloc/bitops.h @@ -0,0 +1,7 @@ +#ifndef CCAN_ALLOC_BITOPS_H +#define CCAN_ALLOC_BITOPS_H +unsigned int fls(unsigned long val); +unsigned int ffsl(unsigned long val); +unsigned int popcount(unsigned long val); +unsigned long align_up(unsigned long x, unsigned long align); +#endif /* CCAN_ALLOC_BITOPS_H */ diff --git a/ccan/alloc/test/run-testsize.c b/ccan/alloc/test/run-testsize.c index 2f0b772a..5ad8d231 100644 --- a/ccan/alloc/test/run-testsize.c +++ b/ccan/alloc/test/run-testsize.c @@ -1,13 +1,12 @@ #include #include #include +#include +#include #include #include #include -#define POOL_ORD 16 -#define POOL_SIZE (1 << POOL_ORD) - static void invert_bytes(unsigned char *p, unsigned long size) { unsigned int i; @@ -21,49 +20,62 @@ static bool sizes_ok(void *mem, unsigned long poolsize, void *p[], unsigned num) unsigned int i; for (i = 0; i < num; i++) - if (alloc_size(mem, poolsize, p[i]) < i) + if (p[i] && alloc_size(mem, poolsize, p[i]) < i) return false; return true; } -int main(int argc, char *argv[]) +static void test_pool(unsigned long pool_size) { + unsigned int i, j, num; void *mem; - unsigned int i, num; - void *p[POOL_SIZE]; - - plan_tests(5); + void **p; + bool flip = false; - /* FIXME: Needs to be page aligned for now. */ - if (posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE) != 0) - errx(1, "Failed allocating aligned memory"); + p = calloc(pool_size, sizeof(void *)); + mem = malloc(pool_size); - alloc_init(mem, POOL_SIZE); + alloc_init(mem, pool_size); /* Check that alloc_size() gives reasonable answers. */ - for (i = 0; i < POOL_SIZE; i++) { - p[i] = alloc_get(mem, POOL_SIZE, i, 1); + for (i = 0; i < pool_size; i = i * 3 / 2 + 1) { + p[i] = alloc_get(mem, pool_size, i, 1); if (!p[i]) break; - invert_bytes(p[i], alloc_size(mem, POOL_SIZE, p[i])); + invert_bytes(p[i], alloc_size(mem, pool_size, p[i])); } - ok1(i < POOL_SIZE); + ok1(i < pool_size); num = i; - ok1(alloc_check(mem, POOL_SIZE)); - ok1(sizes_ok(mem, POOL_SIZE, p, num)); + ok1(alloc_check(mem, pool_size)); + ok1(sizes_ok(mem, pool_size, p, num)); /* Free every second one. */ - for (i = 0; i < num; i+=2) { - alloc_free(mem, POOL_SIZE, p[i]); - /* Compact. */ - if (i + 1 < num) { - p[i/2] = p[i + 1]; - invert_bytes(p[i/2], alloc_size(mem,POOL_SIZE,p[i/2])); + for (i = j = 0; i < num; i = i * 3 / 2 + 1) { + flip = !flip; + if (flip) { + /* Compact. */ + p[j++] = p[i]; + invert_bytes(p[i], alloc_size(mem,pool_size,p[i])); + continue; } + alloc_free(mem, pool_size, p[i]); } num /= 2; - ok1(alloc_check(mem, POOL_SIZE)); - ok1(sizes_ok(mem, POOL_SIZE, p, num)); + ok1(alloc_check(mem, pool_size)); + ok1(sizes_ok(mem, pool_size, p, num)); + free(p); + free(mem); +} + +int main(int argc, char *argv[]) +{ + plan_tests(10); + + /* Large test. */ + test_pool(MIN_USEFUL_SIZE * 2); + + /* Small test. */ + test_pool(MIN_USEFUL_SIZE / 2); return exit_status(); } diff --git a/ccan/alloc/test/run-tiny-encode.c b/ccan/alloc/test/run-tiny-encode.c new file mode 100644 index 00000000..fac83f00 --- /dev/null +++ b/ccan/alloc/test/run-tiny-encode.c @@ -0,0 +1,88 @@ +#include +#include "config.h" +#include +#include +#include +#include + +/* Test encoding and decoding. */ +#define ARR_SIZE 10 + +int main(void) +{ + unsigned char array[ARR_SIZE]; + unsigned int i, prev; + + plan_tests(567); + + prev = 0; + /* Test encode_length */ + for (i = 1; i < 0x8000000; i *= 2) { + ok1(encode_length(i-1) >= prev); + ok1(encode_length(i) >= encode_length(i-1)); + ok1(encode_length(i+1) >= encode_length(i)); + prev = encode_length(i); + } + + /* Test it against actual encoding return val. */ + for (i = 1; i < 0x8000000; i *= 2) { + ok1(encode_length(i-1) == encode(i - 1 + MIN_BLOCK_SIZE, + false, array, ARR_SIZE)); + ok1(encode_length(i) == encode(i + MIN_BLOCK_SIZE, + false, array, ARR_SIZE)); + ok1(encode_length(i+1) == encode(i + 1 + MIN_BLOCK_SIZE, + false, array, ARR_SIZE)); + } + + /* Test encoder vs. decoder. */ + for (i = 1; i < 0x8000000; i *= 2) { + unsigned long hdrlen, len; + bool free; + + hdrlen = encode(i - 1 + MIN_BLOCK_SIZE, false, array, ARR_SIZE); + ok1(decode(&len, &free, array) == hdrlen); + ok1(len == i - 1 + MIN_BLOCK_SIZE); + ok1(free == false); + + hdrlen = encode(i + MIN_BLOCK_SIZE, true, array, ARR_SIZE); + ok1(decode(&len, &free, array) == hdrlen); + ok1(len == i + MIN_BLOCK_SIZE); + ok1(free == true); + + hdrlen = encode(i + 1 + MIN_BLOCK_SIZE, true, array, ARR_SIZE); + ok1(decode(&len, &free, array) == hdrlen); + ok1(len == i + 1 + MIN_BLOCK_SIZE); + ok1(free == true); + } + + /* Test encoder limit enforcement. */ + for (i = 1; i < 0x8000000; i *= 2) { + unsigned char *arr; + unsigned int len; + + /* These should fit. */ + ok1(encode(i-1 + MIN_BLOCK_SIZE, false, array, + encode_length(i-1)) == encode_length(i-1)); + ok1(encode(i + MIN_BLOCK_SIZE, false, array, + encode_length(i)) == encode_length(i)); + ok1(encode(i+1 + MIN_BLOCK_SIZE, false, array, + encode_length(i+1)) == encode_length(i+1)); + + /* These should not: malloc so valgrind finds overruns. */ + len = encode_length(i-1) - 1; + arr = malloc(len); + ok1(encode(i-1 + MIN_BLOCK_SIZE, true, arr, len) == 0); + free(arr); + + len = encode_length(i-1) - 1; + arr = malloc(len); + ok1(encode(i + MIN_BLOCK_SIZE, false, arr, len) == 0); + free(arr); + + len = encode_length(i+1) - 1; + arr = malloc(len); + ok1(encode(i+1 + MIN_BLOCK_SIZE, false, arr, len) == 0); + free(arr); + } + return exit_status(); +} diff --git a/ccan/alloc/test/run.c b/ccan/alloc/test/run.c index c3f09626..f98eb7c5 100644 --- a/ccan/alloc/test/run.c +++ b/ccan/alloc/test/run.c @@ -1,12 +1,11 @@ #include #include #include +#include +#include #include #include -#define POOL_ORD 20 -#define POOL_SIZE (1 << POOL_ORD) - #define sort(p, num, cmp) \ qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp) @@ -25,35 +24,35 @@ static bool unique(void *p[], unsigned int num) return true; } -static bool free_every_second_one(void *mem, unsigned int num, void *p[]) +static bool free_every_second_one(void *mem, unsigned int num, + unsigned long pool_size, void *p[]) { unsigned int i; /* Free every second one. */ for (i = 0; i < num; i += 2) { - alloc_free(mem, POOL_SIZE, p[i]); + alloc_free(mem, pool_size, p[i]); } - if (!alloc_check(mem, POOL_SIZE)) + if (!alloc_check(mem, pool_size)) return false; for (i = 1; i < num; i += 2) { - alloc_free(mem, POOL_SIZE, p[i]); + alloc_free(mem, pool_size, p[i]); } - if (!alloc_check(mem, POOL_SIZE)) + if (!alloc_check(mem, pool_size)) return false; return true; } - -int main(int argc, char *argv[]) +static void test(unsigned int pool_size) { void *mem; unsigned int i, num, max_size; - void **p = calloc(POOL_SIZE, sizeof(*p)); - - plan_tests(120); + void **p = calloc(pool_size, sizeof(*p)); + /* FIXME: Should be pool_size! */ + unsigned alloc_limit = (pool_size / MAX_LARGE_PAGES) >> MAX_PAGE_OBJECT_ORDER; /* FIXME: Needs to be page aligned for now. */ - if (posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE) != 0) + if (posix_memalign(&mem, pool_size, pool_size) != 0) errx(1, "Failed allocating aligned memory"); /* Small pool, all allocs fail, even 0-length. */ @@ -66,33 +65,33 @@ int main(int argc, char *argv[]) /* Free of NULL should work. */ alloc_free(mem, 0, NULL); - alloc_init(mem, POOL_SIZE); - ok1(alloc_check(mem, POOL_SIZE)); + 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); + for (max_size = pool_size + 1; 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 < pool_size); ok1(max_size > 0); - ok1(alloc_check(mem, POOL_SIZE)); - ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size); + ok1(alloc_check(mem, pool_size)); + ok1(alloc_size(mem, pool_size, p[0]) >= max_size); /* Free it, should be able to reallocate it. */ - alloc_free(mem, POOL_SIZE, p[0]); - ok1(alloc_check(mem, POOL_SIZE)); + alloc_free(mem, pool_size, p[0]); + ok1(alloc_check(mem, pool_size)); - p[0] = alloc_get(mem, POOL_SIZE, max_size, 1); + p[0] = alloc_get(mem, pool_size, max_size, 1); ok1(p[0]); - ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size); - ok1(alloc_check(mem, POOL_SIZE)); - alloc_free(mem, POOL_SIZE, p[0]); - ok1(alloc_check(mem, POOL_SIZE)); + ok1(alloc_size(mem, pool_size, p[0]) >= max_size); + 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); + for (i = 0; i < pool_size; i++) { + p[i] = alloc_get(mem, pool_size, 1, 1); if (!p[i]) break; } @@ -100,13 +99,13 @@ int main(int argc, char *argv[]) /* Uncomment this for a more intuitive view of what the * allocator looks like after all these 1 byte allocs. */ #if 0 - alloc_visualize(stderr, mem, POOL_SIZE); + alloc_visualize(stderr, mem, pool_size); #endif num = i; /* Can't allocate this many. */ - ok1(num != POOL_SIZE); - ok1(alloc_check(mem, POOL_SIZE)); + ok1(num != pool_size); + ok1(alloc_check(mem, pool_size)); /* Sort them. */ sort(p, num, addr_cmp); @@ -114,55 +113,66 @@ int main(int argc, char *argv[]) /* Uniqueness check */ ok1(unique(p, num)); - ok1(free_every_second_one(mem, num, p)); - ok1(alloc_check(mem, POOL_SIZE)); + ok1(free_every_second_one(mem, num, pool_size, p)); + ok1(alloc_check(mem, pool_size)); /* Should be able to reallocate max size. */ - p[0] = alloc_get(mem, POOL_SIZE, max_size, 1); + p[0] = alloc_get(mem, pool_size, max_size, 1); ok1(p[0]); - ok1(alloc_check(mem, POOL_SIZE)); - ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size); + ok1(alloc_check(mem, pool_size)); + ok1(alloc_size(mem, pool_size, p[0]) >= max_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); + 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_size(mem, POOL_SIZE, p[0]) >= max_size); - ok1(alloc_check(mem, POOL_SIZE)); - alloc_free(mem, POOL_SIZE, p[0]); - ok1(alloc_check(mem, POOL_SIZE)); + ok1(alloc_size(mem, pool_size, p[0]) >= max_size); + 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 < /*FIXME: POOL_ORD-1*/ 10; i++) { - p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i); + for (i = 0; (1 << i) < alloc_limit; 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)); - ok1(alloc_size(mem, POOL_SIZE, p[i]) >= i); + ok1(alloc_check(mem, pool_size)); + ok1(alloc_size(mem, pool_size, p[i]) >= i); } - for (i = 0; i < /*FIXME: POOL_ORD-1*/ 10; i++) { - alloc_free(mem, POOL_SIZE, p[i]); - ok1(alloc_check(mem, POOL_SIZE)); + for (i = 0; (1 << i) < alloc_limit; 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 < /*FIXME: POOL_ORD*/ 10; i++) { - p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i); + for (i = 0; (1 << i) < alloc_limit; i++) { + p[0] = alloc_get(mem, pool_size, 1, 1 << i); ok1(p[0]); - ok1(alloc_check(mem, POOL_SIZE)); - ok1(alloc_size(mem, POOL_SIZE, p[i]) >= 1); - alloc_free(mem, POOL_SIZE, p[0]); - ok1(alloc_check(mem, POOL_SIZE)); + ok1(alloc_check(mem, pool_size)); + ok1(alloc_size(mem, pool_size, p[i]) >= 1); + alloc_free(mem, pool_size, p[0]); + ok1(alloc_check(mem, pool_size)); } /* Alignment check for a 0-byte allocation. Corner case. */ - p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (/*FIXME: POOL_ORD - 1*/ 10)); - ok1(alloc_check(mem, POOL_SIZE)); - ok1(alloc_size(mem, POOL_SIZE, p[0]) < POOL_SIZE); - alloc_free(mem, POOL_SIZE, p[0]); - ok1(alloc_check(mem, POOL_SIZE)); + p[0] = alloc_get(mem, pool_size, 0, alloc_limit); + ok1(alloc_check(mem, pool_size)); + ok1(alloc_size(mem, pool_size, p[0]) < pool_size); + alloc_free(mem, pool_size, p[0]); + ok1(alloc_check(mem, pool_size)); +} + +int main(int argc, char *argv[]) +{ + plan_tests(112 + 92); + + /* Large test. */ + test(MIN_USEFUL_SIZE * 2); + + /* Small test. */ + test(MIN_USEFUL_SIZE / 2); return exit_status(); } diff --git a/ccan/alloc/tiny.c b/ccan/alloc/tiny.c new file mode 100755 index 00000000..678ca52d --- /dev/null +++ b/ccan/alloc/tiny.c @@ -0,0 +1,296 @@ +#include "tiny.h" +#include "bitops.h" +#include +#include +#include + +/* One byte header, one byte data. */ +#define MIN_BLOCK_SIZE 2 + +/* Bit 7 (in any byte) == start or end. */ +#define TERM_BIT 0x80 +/* Bit 6 (first and last byte) == one byte long. */ +#define SINGLE_BYTE 0x40 +/* Bit 5 (of first byte) == "is this block free?" */ +#define FREE_BIT 0x20 + +/* Val is usually offset by MIN_BLOCK_SIZE here. */ +static unsigned encode_length(unsigned long val) +{ + unsigned int bits = fls(val); + /* 5 bits in first byte. */ + if (bits <= 5) + return 1; + /* 6 bits in last byte, 7 bits in middle ones. */ + return 2 + (bits - 5) / 7; +} + +/* Header is included in length, so we might need an extra byte. */ +static unsigned encode_len_with_header(unsigned long len) +{ + unsigned int hdrlen = 1; + + assert(len); + while (encode_length(len + hdrlen - MIN_BLOCK_SIZE) != hdrlen) + hdrlen = encode_length(len + hdrlen - MIN_BLOCK_SIZE); + + return hdrlen; +} + +/* Encoding can be read from front or back; 0 is invalid at either + * start or end. Returns bytes used for header, or 0 if won't fit. */ +static unsigned encode(unsigned long len, bool free, unsigned char arr[], + size_t limit) +{ + unsigned int hdrlen = 1; + + /* We can never have a length < MIN_BLOCK_SIZE. */ + assert(len >= MIN_BLOCK_SIZE); + len -= MIN_BLOCK_SIZE; + + if (encode_length(len) > limit) + return 0; + + /* First byte always contains free bit. */ + arr[0] = TERM_BIT | (free ? FREE_BIT : 0); + /* Also holds 5 bits of data (0 - 31) */ + arr[0] |= (len & 0x1F); + len >>= 5; + + /* One byte only? */ + if (!len) { + arr[0] |= SINGLE_BYTE; + return hdrlen; + } + + /* Middle bytes. */ + while (len >= (1 << 6)) { + /* Next 7 data bits */ + arr[hdrlen++] = (len & 0x7F); + len >>= 7; + } + arr[hdrlen++] = (len | TERM_BIT); + return hdrlen; +} + +/* Returns bytes used for header. */ +static unsigned decode(unsigned long *len, bool *free, const unsigned char *arr) +{ + unsigned int hdrlen = 0, bits = 5; + + /* Free flag is in bit 5 */ + *free = (arr[hdrlen] & FREE_BIT); + /* Bottom five bits are data. */ + *len = (arr[hdrlen] & 0x1f); + if (!(arr[hdrlen++] & SINGLE_BYTE)) { + /* Multi-byte encoding? */ + while (!(arr[hdrlen] & TERM_BIT)) { + /* 7 more data bits. */ + *len |= (arr[hdrlen] & 0x7fUL) << bits; + hdrlen++; + bits += 7; + } + /* Final byte has 6 bits. */ + *len |= (arr[hdrlen] & 0x3fUL) << bits; + hdrlen++; + } + + *len += MIN_BLOCK_SIZE; + return hdrlen; +} + +/* We keep a recently-freed array, one byte per k. */ +static unsigned long free_array_size(unsigned long poolsize) +{ + return poolsize / 1024; +} + +void tiny_alloc_init(void *pool, unsigned long poolsize) +{ + /* We start with free array, and then the rest is free. */ + unsigned long arrsize = free_array_size(poolsize); + + /* Do nothing with 1 byte or less! */ + if (poolsize < MIN_BLOCK_SIZE) + return; + + memset(pool, 0, arrsize); + encode(poolsize - arrsize, true, + (unsigned char *)pool + arrsize, poolsize - arrsize); +} + +/* Walk through and try to coalesce */ +static bool try_coalesce(unsigned char *pool, unsigned long poolsize) +{ + unsigned long len, hdrlen, prev_off = 0, prev_len = 0, off; + bool free, prev_free = false, coalesced = false; + + off = free_array_size(poolsize); + do { + hdrlen = decode(&len, &free, pool + off); + if (free && prev_free) { + encode(prev_len + len, true, pool + prev_off, + poolsize - prev_off); + coalesced = true; + } + prev_free = free; + prev_off = off; + prev_len = len; + off += len; + } while (off < poolsize); + + return coalesced; +} + +static bool long_enough(unsigned long offset, unsigned long len, + unsigned long size, unsigned long align) +{ + unsigned long end = offset + len; + + offset += encode_len_with_header(len); + offset = align_up(offset, align); + return offset + size <= end; +} + +void *tiny_alloc_get(void *pool, unsigned long poolsize, + unsigned long size, unsigned long align) +{ + unsigned long arrsize = free_array_size(poolsize); + unsigned long len, off, actual, hdr, hdrlen; + bool free; + + /* We can't do anything with tiny pools. */ + if (poolsize < MIN_BLOCK_SIZE) + return NULL; + + /* We don't do zero-allocs; allows 1 more offset in encoding. */ + if (!size) + size = 1; + + /* FIXME: Look through free array. */ + +again: + off = arrsize; + + hdrlen = decode(&len, &free, (unsigned char *)pool + off); + while (!free || !long_enough(off, len, size, align)) { + /* FIXME: Refill free array if this block is free. */ + + /* Hit end? */ + off += len; + if (off == poolsize) { + if (try_coalesce(pool, poolsize)) + goto again; + return NULL; + } + hdrlen = decode(&len, &free, (unsigned char *)pool + off); + } + + /* We have a free block. Since we walk from front, take far end. */ + actual = ((off + len - size) & ~(align - 1)); + hdr = actual - encode_len_with_header(off + len - actual); + + /* Do we have enough room to split? */ + if (hdr - off >= MIN_BLOCK_SIZE) { + encode(hdr - off, true, (unsigned char *)pool + off, poolsize); + } else { + hdr = off; + } + + /* Make sure that we are all-zero up to actual, so we can walk back + * and find header. */ + memset((unsigned char *)pool + hdr, 0, actual - hdr); + + /* Create header for allocated block. */ + encode(off + len - hdr, false, (unsigned char *)pool + hdr, poolsize); + + return (unsigned char *)pool + actual; +} + +static unsigned char *to_hdr(void *p) +{ + unsigned char *hdr = p; + + /* Walk back to find end of header. */ + while (!*(--hdr)); + assert(*hdr & TERM_BIT); + + /* Now walk back to find start of header. */ + if (!(*hdr & SINGLE_BYTE)) { + while (!(*(--hdr) & TERM_BIT)); + } + return hdr; +} + +void tiny_alloc_free(void *pool, unsigned long poolsize, void *freep) +{ + unsigned char *hdr; + + /* Too small to do anything. */ + if (poolsize < MIN_BLOCK_SIZE) + return; + + hdr = to_hdr(freep); + + /* FIXME: Put in free array. */ + hdr[0] |= FREE_BIT; +} + +unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p) +{ + unsigned char *hdr = to_hdr(p); + unsigned long len, hdrlen; + bool free; + + hdrlen = decode(&len, &free, hdr); + return len - hdrlen; +} + +/* Useful for gdb breakpoints. */ +static bool tiny_check_fail(void) +{ + return false; +} + +bool tiny_alloc_check(void *pool, unsigned long poolsize) +{ + unsigned long arrsize = free_array_size(poolsize); + unsigned char *arr = pool; + unsigned long len, off, hdrlen; + bool free; + + if (poolsize < MIN_BLOCK_SIZE) + return true; + + /* For the moment, free array is all zeroes. */ + for (off = 0; off < arrsize; off++) { + if (arr[off] != 0) + return tiny_check_fail(); + } + + for (off = arrsize; off < poolsize; off += len) { + /* We should have a valid header. */ + if (!(arr[off] & TERM_BIT)) + return tiny_check_fail(); + if (!(arr[off] & SINGLE_BYTE)) { + unsigned long off2; + for (off2 = off+1; off2 < poolsize; off2++) { + if (arr[off2] & TERM_BIT) + break; + } + if (off2 == poolsize) + return tiny_check_fail(); + } + hdrlen = decode(&len, &free, arr + off); + if (off + len > poolsize) + return tiny_check_fail(); + if (hdrlen != encode_length(len - MIN_BLOCK_SIZE)) + return tiny_check_fail(); + } + return true; +} + +/* FIXME: Implement. */ +void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize) +{ +} diff --git a/ccan/alloc/tiny.h b/ccan/alloc/tiny.h new file mode 100644 index 00000000..37922d9c --- /dev/null +++ b/ccan/alloc/tiny.h @@ -0,0 +1,14 @@ +#ifndef CCAN_TINY_H +#define CCAN_TINY_H +#include +#include + +void tiny_alloc_init(void *pool, unsigned long poolsize); +void *tiny_alloc_get(void *pool, unsigned long poolsize, + unsigned long size, unsigned long align); +void tiny_alloc_free(void *pool, unsigned long poolsize, void *free); +unsigned long tiny_alloc_size(void *pool, unsigned long poolsize, void *p); +bool tiny_alloc_check(void *pool, unsigned long poolsize); +void tiny_alloc_visualize(FILE *out, void *pool, unsigned long poolsize); + +#endif /* CCAN_TINY_H */