alloc: first cut of tiny allocator (down to 2 bytes!)
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 12 Jul 2010 13:52:30 +0000 (23:22 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 12 Jul 2010 13:52:30 +0000 (23:22 +0930)
ccan/alloc/alloc.c
ccan/alloc/bitops.c [new file with mode: 0644]
ccan/alloc/bitops.h [new file with mode: 0644]
ccan/alloc/test/run-testsize.c
ccan/alloc/test/run-tiny-encode.c [new file with mode: 0644]
ccan/alloc/test/run.c
ccan/alloc/tiny.c [new file with mode: 0755]
ccan/alloc/tiny.h [new file with mode: 0644]

index 535e7b477316b206f0139d3a668a6151a9939989..bc3760abc0797d43e10ab1dbed920d28bd501c24 100644 (file)
@@ -5,6 +5,8 @@
 #include <assert.h>
 #include <stdlib.h>
 #include "alloc.h"
+#include "bitops.h"
+#include "tiny.h"
 #include <ccan/build_assert/build_assert.h>
 #include <ccan/likely/likely.h>
 #include <ccan/short_types/short_types.h>
@@ -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 (file)
index 0000000..ad4465f
--- /dev/null
@@ -0,0 +1,118 @@
+#include "bitops.h"
+#include "config.h"
+#include <ccan/short_types/short_types.h>
+#include <limits.h>
+
+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 (file)
index 0000000..11ec950
--- /dev/null
@@ -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 */
index 2f0b772a4a3ba2a6c3f379b7b55581a51c810f63..5ad8d2311983fc32250762a5ac162748dc8ff507 100644 (file)
@@ -1,13 +1,12 @@
 #include <ccan/alloc/alloc.h>
 #include <ccan/tap/tap.h>
 #include <ccan/alloc/alloc.c>
+#include <ccan/alloc/bitops.c>
+#include <ccan/alloc/tiny.c>
 #include <stdlib.h>
 #include <stdbool.h>
 #include <err.h>
 
-#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 (file)
index 0000000..fac83f0
--- /dev/null
@@ -0,0 +1,88 @@
+#include <ccan/tap/tap.h>
+#include "config.h"
+#include <ccan/alloc/tiny.c>
+#include <ccan/alloc/bitops.c>
+#include <stdlib.h>
+#include <err.h>
+
+/* 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();
+}
index c3f09626446497512993443722609315485571df..f98eb7c5e9e90a620a06a370592314d913cae427 100644 (file)
@@ -1,12 +1,11 @@
 #include <ccan/alloc/alloc.h>
 #include <ccan/tap/tap.h>
 #include <ccan/alloc/alloc.c>
+#include <ccan/alloc/bitops.c>
+#include <ccan/alloc/tiny.c>
 #include <stdlib.h>
 #include <err.h>
 
-#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 (executable)
index 0000000..678ca52
--- /dev/null
@@ -0,0 +1,296 @@
+#include "tiny.h"
+#include "bitops.h"
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* 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 (file)
index 0000000..37922d9
--- /dev/null
@@ -0,0 +1,14 @@
+#ifndef CCAN_TINY_H
+#define CCAN_TINY_H
+#include <stdbool.h>
+#include <stdio.h>
+
+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 */