From 2622d34405aa838770d9c72c523db4ed8defadaa Mon Sep 17 00:00:00 2001 From: Joey Adams Date: Tue, 14 Jul 2009 21:36:37 -0400 Subject: [PATCH] Added module block_pool --- ccan/block_pool/_info | 51 +++++++++ ccan/block_pool/block_pool.c | 196 +++++++++++++++++++++++++++++++++++ ccan/block_pool/block_pool.h | 68 ++++++++++++ ccan/block_pool/test/run.c | 151 +++++++++++++++++++++++++++ 4 files changed, 466 insertions(+) create mode 100644 ccan/block_pool/_info create mode 100644 ccan/block_pool/block_pool.c create mode 100644 ccan/block_pool/block_pool.h create mode 100644 ccan/block_pool/test/run.c diff --git a/ccan/block_pool/_info b/ccan/block_pool/_info new file mode 100644 index 00000000..53afc7bd --- /dev/null +++ b/ccan/block_pool/_info @@ -0,0 +1,51 @@ +#include +#include +#include "config.h" + +/** + * block_pool - An efficient allocator for blocks that don't need to be + * resized or freed. + * + * block_pool allocates blocks by packing them into buffers, making the + * overhead per block virtually zero. Because of this, you cannot resize or + * free individual blocks, but you can free the entire block_pool. + * + * The rationale behind block_pool is that talloc uses a lot of bytes per + * block (48 on 32-bit, 80 on 64-bit). Nevertheless, talloc is an excellent + * tool for C programmers of all ages. Because a block_pool is a talloc + * context, it can be useful in talloc-based applications where many small + * blocks need to be allocated. + * + * Example: + * + * #include + * + * int main(void) { + * struct block_pool *bp = block_pool_new(NULL); + * + * void *buffer = block_pool_alloc(bp, 4096); + * char *string = block_pool_strdup(bp, "A string"); + * + * int array[] = {0,1,1,2,3,5,8,13,21,34}; + * int *array_copy = block_pool_memdup(bp, array, sizeof(array)); + * + * block_pool_free(bp); + * return 0; + * } + * + * Author: Joey Adams + * License: BSD + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/talloc\n"); + return 0; + } + + return 1; +} diff --git a/ccan/block_pool/block_pool.c b/ccan/block_pool/block_pool.c new file mode 100644 index 00000000..0959e733 --- /dev/null +++ b/ccan/block_pool/block_pool.c @@ -0,0 +1,196 @@ +/* + Copyright (c) 2009 Joseph A. Adams + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + 3. The name of the author may not be used to endorse or promote products + derived from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#include "block_pool.h" +#include +#include +#include + +//must be a power of 2 +#define BLOCK_SIZE 4096 + +struct block { + size_t remaining; + size_t size; + char *data; +}; + +struct block_pool { + size_t count; + size_t alloc; //2^n - 1, where n is an integer > 1 + struct block *block; + + //blocks are arranged in a max-heap by the .remaining field + // (except the root block does not percolate down until it is filled) +}; + +static int destructor(struct block_pool *bp) { + struct block *block = bp->block; + size_t d = bp->count; + + for (;d--;block++) + free(block->data); + free(bp->block); + + return 0; +} + +struct block_pool *block_pool_new(void *ctx) { + struct block_pool *bp = talloc(ctx, struct block_pool); + talloc_set_destructor(bp, destructor); + + bp->count = 0; + bp->alloc = 7; + bp->block = malloc(bp->alloc * sizeof(struct block)); + + return bp; +} + +static void *new_block(struct block *b, size_t needed) { + b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1); + b->remaining = b->size - needed; + b->data = malloc(b->size); + return b->data; +} + +//for the first block, keep the memory usage low in case it's the only block. +static void *new_block_tiny(struct block *b, size_t needed) { + if (needed < 256) + b->size = 256; + else + b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1); + b->remaining = b->size - needed; + b->data = malloc(b->size); + return b->data; +} + +static void *try_block(struct block *b, size_t size, size_t align) { + size_t offset = b->size - b->remaining; + offset = (offset+align) & ~align; + + if (b->size-offset >= size) { + //good, we can use this block + void *ret = b->data + offset; + b->remaining = b->size-offset-size; + + return ret; + } + + return NULL; +} + +#define L(node) (node+node+1) +#define R(node) (node+node+2) +#define P(node) ((node-1)>>1) + +#define V(node) (bp->block[node].remaining) + +static void percolate_down(struct block_pool *bp, size_t node) { + size_t child = L(node); + struct block tmp; + + //get the maximum child + if (child >= bp->count) + return; + if (child+1 < bp->count && V(child+1) > V(child)) + child++; + + if (V(child) <= V(node)) + return; + + tmp = bp->block[node]; + bp->block[node] = bp->block[child]; + bp->block[child] = tmp; + + percolate_down(bp, child); +} + +//note: percolates up to either 1 or 2 as a root +static void percolate_up(struct block_pool *bp, size_t node) { + size_t parent = P(node); + struct block tmp; + + if (node<3 || V(parent) >= V(node)) + return; + + tmp = bp->block[node]; + bp->block[node] = bp->block[parent]; + bp->block[parent] = tmp; + + percolate_up(bp, parent); +} + +void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align) { + void *ret; + + if (align) + align--; + + //if there aren't any blocks, make a new one + if (!bp->count) { + bp->count = 1; + return new_block_tiny(bp->block, size); + } + + //try the root block + ret = try_block(bp->block, size, align); + if (ret) + return ret; + + //root block is filled, percolate down and try the biggest one + percolate_down(bp, 0); + ret = try_block(bp->block, size, align); + if (ret) + return ret; + + //the biggest wasn't big enough; we need a new block + if (bp->count >= bp->alloc) { + //make room for another block + bp->alloc += bp->alloc; + bp->alloc++; + bp->block = realloc(bp->block, bp->alloc * sizeof(struct block)); + } + ret = new_block(bp->block+(bp->count++), size); + + //fix the heap after adding the new block + percolate_up(bp, bp->count-1); + + return ret; +} + +#undef L +#undef R +#undef P +#undef V + +char *block_pool_strdup(struct block_pool *bp, const char *str) { + size_t size = strlen(str)+1; + char *ret = block_pool_alloc_align(bp, size, 1); + + memcpy(ret, str, size); + return ret; +} diff --git a/ccan/block_pool/block_pool.h b/ccan/block_pool/block_pool.h new file mode 100644 index 00000000..4db25a8d --- /dev/null +++ b/ccan/block_pool/block_pool.h @@ -0,0 +1,68 @@ +/* + Copyright (c) 2009 Joseph A. Adams + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + 3. The name of the author may not be used to endorse or promote products + derived from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CCAN_BLOCK_POOL +#define CCAN_BLOCK_POOL + +#include +#include + +struct block_pool; + +/* Construct a new block pool. + ctx is a talloc context (or NULL if you don't know what talloc is ;) ) */ +struct block_pool *block_pool_new(void *ctx); + +/* Same as block_pool_alloc, but allows you to manually specify alignment. + For instance, strings need not be aligned, so set align=1 for them. + align must be a power of two. */ +void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align); + +/* Allocate a block of a given size. The returned pointer will remain valid + for the life of the block_pool. The block cannot be resized or + freed individually. */ +static inline void *block_pool_alloc(struct block_pool *bp, size_t size) { + size_t align = size & -size; //greatest power of two by which size is divisible + if (align > 16) + align = 16; + return block_pool_alloc_align(bp, size, align); +} + +static inline void block_pool_free(struct block_pool *bp) { + talloc_free(bp); +} + + +char *block_pool_strdup(struct block_pool *bp, const char *str); + +static inline void *block_pool_memdup(struct block_pool *bp, const void *src, size_t size) { + void *ret = block_pool_alloc(bp, size); + memcpy(ret, src, size); + return ret; +} + +#endif diff --git a/ccan/block_pool/test/run.c b/ccan/block_pool/test/run.c new file mode 100644 index 00000000..3fa7effd --- /dev/null +++ b/ccan/block_pool/test/run.c @@ -0,0 +1,151 @@ +#include "block_pool/block_pool.h" +#include "block_pool/block_pool.c" +#include "tap/tap.h" + +struct alloc_record { + size_t size; + char *ptr; +}; + +static int compar_alloc_record_by_ptr(const void *ap, const void *bp) { + const struct alloc_record *a=ap, *b=bp; + + if (a->ptr < b->ptr) + return -1; + else if (a->ptr > b->ptr) + return 1; + else + return 0; +} + +static size_t random_block_size(void) { + int scale = random() % 11; + switch (scale) { + case 0: + case 1: + case 2: + case 3: + case 4: return random() % 25; + case 5: + case 6: + case 7: return random() % 100; + case 8: + case 9: return random() % 1000; + case 10: return random() % 10000; + default: + fprintf(stderr, "random() %% 3 returned %d somehow!\n", scale); + exit(EXIT_FAILURE); + } +} + +#define L(node) (node+node+1) +#define R(node) (node+node+2) +#define P(node) ((node-1)>>1) + +#define V(node) (bp->block[node].remaining) + +//used by test_block_pool to make sure the pool's block array is a max heap +//set node=0 to scan the whole heap (starting at the root) +//returns nonzero on success +static int check_heap(struct block_pool *bp, size_t node) { + if (node < bp->count) { + if (node) { //the root node need not be the max, but its subtrees must be valid + if (L(node) < bp->count && V(L(node)) > V(node)) + return 0; + if (R(node) < bp->count && V(R(node)) > V(node)) + return 0; + } + return check_heap(bp, L(node)) && check_heap(bp, R(node)); + } else + return 1; +} + +#undef L +#undef R +#undef P +#undef V + +/* Performs a self-test of block_pool. + Returns 1 on success, 0 on failure. + If verify_heap is nonzero, the test will check the heap structure every + single allocation, making test_block_pool take n^2 time. */ +static int test_block_pool(size_t blocks_to_try, FILE *out, int verify_heap) { + struct block_pool *bp = block_pool_new(NULL); + struct alloc_record *record = malloc(sizeof(*record) * blocks_to_try); + size_t i; + size_t bytes_allocated = 0; + #define print(...) do { \ + if (out) \ + printf(__VA_ARGS__); \ + } while(0) + + print("Allocating %zu blocks...\n", blocks_to_try); + + for (i=0; icount); + + qsort(record, blocks_to_try, + sizeof(*record), compar_alloc_record_by_ptr); + + print("Making sure block ranges are unique...\n"); + //print("0: %p ... %p\n", record[0].ptr, record[0].ptr+record[0].size); + for (i=1; iptr, b->ptr+b->size); + + if (a->ptr > b->ptr) { + struct alloc_record *tmp = a; + a = b; + b = tmp; + } + + if (a->ptr <= b->ptr && a->ptr+a->size <= b->ptr) + continue; + + print("Allocations %zu and %zu overlap\n", i-1, i); + return 0; + } + + print("Checking heap structure...\n"); + if (!check_heap(bp, 0)) { + print("Block pool's max-heap is wrong\n"); + return 0; + } + + block_pool_free(bp); + free(record); + + return 1; + + #undef print +} + + +int main(void) +{ + plan_tests(1); + + //test a few blocks with heap verification + ok1(test_block_pool(10000, NULL, 1)); + + return exit_status(); +} -- 2.39.2