#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>
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.
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)
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;
--- /dev/null
+#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);
+}
--- /dev/null
+#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 */
#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;
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();
}
--- /dev/null
+#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();
+}
#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)
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. */
/* 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;
}
/* 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);
/* 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();
}
--- /dev/null
+#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)
+{
+}
--- /dev/null
+#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 */