From 1d7e593d2221690abd8010d4d572984ef2be4d21 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sun, 29 Jun 2008 19:03:53 +1000 Subject: [PATCH] Add alloc_size(): every allocator has to be able to answer this, since free() doesn't have a size arg. --- ccan/alloc/alloc.c | 47 ++++++++++++++++++++++++ ccan/alloc/alloc.h | 1 + ccan/alloc/test/run-testsize.c | 67 ++++++++++++++++++++++++++++++++++ ccan/alloc/test/run.c | 12 +++++- 4 files changed, 126 insertions(+), 1 deletion(-) create mode 100644 ccan/alloc/test/run-testsize.c diff --git a/ccan/alloc/alloc.c b/ccan/alloc/alloc.c index f7a05e2d..c70b7fa7 100644 --- a/ccan/alloc/alloc.c +++ b/ccan/alloc/alloc.c @@ -822,6 +822,53 @@ void alloc_free(void *pool, unsigned long poolsize, void *free) } } +unsigned long alloc_size(void *pool, unsigned long poolsize, void *p) +{ + unsigned long len, pagenum; + struct metaheader *mh; + + assert(poolsize >= MIN_SIZE); + + mh = first_mheader(pool, poolsize); + assert((char *)p >= (char *)(mh + 1)); + assert((char *)pool + poolsize > (char *)p); + + pagenum = pool_offset(pool, p) / getpagesize(); + + if (get_page_state(pool, pagenum) == SPECIAL) { + unsigned long off = (unsigned long)p % getpagesize(); + uint8_t *metadata = get_page_metadata(pool, pagenum); + enum sub_metadata_type type = get_bit_pair(metadata, 0); + + assert(off < SUBPAGE_METAOFF); + + switch (type) { + case BITMAP: + assert(off % BITMAP_GRANULARITY == 0); + off /= BITMAP_GRANULARITY; + + /* Offset by one because first bit used for header. */ + off++; + len = BITMAP_GRANULARITY; + while (++off < SUBPAGE_METAOFF / BITMAP_GRANULARITY + && get_bit_pair(metadata, off) == TAKEN) + len += BITMAP_GRANULARITY; + break; + case UNIFORM: + len = decode_usize(metadata); + break; + default: + assert(0); + } + } else { + len = getpagesize(); + while (get_page_state(pool, ++pagenum) == TAKEN) + len += getpagesize(); + } + + return len; +} + static bool is_metadata_page(void *pool, unsigned long poolsize, unsigned long page) { diff --git a/ccan/alloc/alloc.h b/ccan/alloc/alloc.h index 29c29d07..d4927141 100644 --- a/ccan/alloc/alloc.h +++ b/ccan/alloc/alloc.h @@ -7,6 +7,7 @@ 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); +unsigned long alloc_size(void *pool, unsigned long poolsize, void *p); bool alloc_check(void *pool, unsigned long poolsize); void alloc_visualize(FILE *out, void *pool, unsigned long poolsize); diff --git a/ccan/alloc/test/run-testsize.c b/ccan/alloc/test/run-testsize.c new file mode 100644 index 00000000..bb063c24 --- /dev/null +++ b/ccan/alloc/test/run-testsize.c @@ -0,0 +1,67 @@ +#include "alloc/alloc.h" +#include "tap/tap.h" +#include "alloc/alloc.c" +#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; + + for (i = 0; i < size; i++) + p[i] ^= 0xFF; +} + +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) + return false; + return true; +} + +int main(int argc, char *argv[]) +{ + void *mem; + unsigned int i, num; + void *p[POOL_SIZE]; + + plan_tests(5); + + /* FIXME: Needs to be page aligned for now. */ + posix_memalign(&mem, 1 << POOL_ORD, 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); + if (!p[i]) + break; + invert_bytes(p[i], alloc_size(mem, POOL_SIZE, p[i])); + } + ok1(i < POOL_SIZE); + num = i; + 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])); + } + } + num /= 2; + ok1(alloc_check(mem, POOL_SIZE)); + ok1(sizes_ok(mem, POOL_SIZE, p, num)); + + return exit_status(); +} diff --git a/ccan/alloc/test/run.c b/ccan/alloc/test/run.c index 8cfe8b42..bf8ab479 100644 --- a/ccan/alloc/test/run.c +++ b/ccan/alloc/test/run.c @@ -49,7 +49,7 @@ int main(int argc, char *argv[]) unsigned int i, num, max_size; void *p[POOL_SIZE]; - plan_tests(139); + plan_tests(178); /* FIXME: Needs to be page aligned for now. */ posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE); @@ -75,6 +75,7 @@ int main(int argc, char *argv[]) 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); /* Free it, should be able to reallocate it. */ alloc_free(mem, POOL_SIZE, p[0]); @@ -82,6 +83,7 @@ int main(int argc, char *argv[]) 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)); @@ -117,12 +119,14 @@ int main(int argc, char *argv[]) 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); /* 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_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)); @@ -133,6 +137,7 @@ int main(int argc, char *argv[]) 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); } for (i = 0; i < POOL_ORD-1; i++) { @@ -145,6 +150,7 @@ int main(int argc, char *argv[]) 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)); } @@ -152,6 +158,7 @@ int main(int argc, char *argv[]) /* Alignment check for a 0-byte allocation. Corner case. */ p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (POOL_ORD - 1)); 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)); @@ -163,6 +170,7 @@ int main(int argc, char *argv[]) break; } ok1(alloc_check(mem, POOL_SIZE)); + ok1(alloc_size(mem, POOL_SIZE, p[i-1]) >= getpagesize()); /* Sort them. */ sort(p, i-1, addr_cmp); @@ -171,6 +179,7 @@ int main(int argc, char *argv[]) for (i = 1; p[i]; i++) alloc_free(mem, POOL_SIZE, p[i]); ok1(alloc_check(mem, POOL_SIZE)); + ok1(alloc_size(mem, POOL_SIZE, p[0]) >= getpagesize()); /* Now do a whole heap of subpage allocs. */ for (i = 1; i < POOL_SIZE; i++) { @@ -185,6 +194,7 @@ int main(int argc, char *argv[]) ok1(alloc_check(mem, POOL_SIZE)); p[0] = alloc_get(mem, POOL_SIZE, 1, 1); ok1(p[0]); + ok1(alloc_size(mem, POOL_SIZE, p[0]) >= 1); /* Clean up. */ for (i = 0; p[i]; i++) -- 2.39.2