Added module block_pool
authorJoey Adams <joeyadams3.14159@gmail.com>
Wed, 15 Jul 2009 01:36:37 +0000 (21:36 -0400)
committerJoey Adams <joeyadams3.14159@gmail.com>
Wed, 15 Jul 2009 01:36:37 +0000 (21:36 -0400)
ccan/block_pool/_info [new file with mode: 0644]
ccan/block_pool/block_pool.c [new file with mode: 0644]
ccan/block_pool/block_pool.h [new file with mode: 0644]
ccan/block_pool/test/run.c [new file with mode: 0644]

diff --git a/ccan/block_pool/_info b/ccan/block_pool/_info
new file mode 100644 (file)
index 0000000..53afc7b
--- /dev/null
@@ -0,0 +1,51 @@
+#include <stdio.h>
+#include <string.h>
+#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 <ccan/block_pool/block_pool.h>
+ *
+ * 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 (file)
index 0000000..0959e73
--- /dev/null
@@ -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 <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+//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 (file)
index 0000000..4db25a8
--- /dev/null
@@ -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 <ccan/talloc/talloc.h>
+#include <string.h>
+
+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 (file)
index 0000000..3fa7eff
--- /dev/null
@@ -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; i<blocks_to_try; i++) {
+               record[i].size = random_block_size();
+               record[i].ptr = block_pool_alloc(bp, record[i].size);
+               
+               bytes_allocated += record[i].size;
+               
+               memset(record[i].ptr, 0x55, record[i].size);
+               
+               if (verify_heap && !check_heap(bp, 0)) {
+                       print("Block pool's max-heap is wrong (allocation %zu)\n", i);
+                       return 0;
+               }
+       }
+       
+       print("Finished allocating\n"
+              "    %zu blocks\n"
+              "    %zu bytes\n"
+              "    %zu pages\n",
+               blocks_to_try, bytes_allocated, bp->count);
+       
+       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; i<blocks_to_try; i++) {
+               struct alloc_record *a = &record[i-1];
+               struct alloc_record *b = &record[i];
+               
+               //print("%zu: %p ... %p\n", i, b->ptr, 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();
+}