While prototyping an apr_allocator_t based implementation for the bucket allocator, I suddenly realized that there may be a much simpler way to solve the problem.
The attached implementation handles allocation requests differently based on their size: * Anything <= 128 bytes is allocated from a free list of 128-byte blocks contained within the bucket allocator. When the free list runs out of blocks, the bucket allocator gets additional memory from its pool. (We can do this because the allocator's lifetime is the same as that of the pool from which it was created.) * Anything > 128 bytes is handled using malloc/free. The only common case larger than 128 is 8192. It would be easy to add a second free list within the allocator for 8192-byte blocks. For this free list, we should probably impose a max size, so that we never store more than two or three 8KB blocks in an allocator. Comments...? --Brian
Index: srclib/apr-util/buckets/apr_buckets_alloc.c =================================================================== RCS file: /home/cvs/apr-util/buckets/apr_buckets_alloc.c,v retrieving revision 1.3 diff -u -r1.3 apr_buckets_alloc.c --- srclib/apr-util/buckets/apr_buckets_alloc.c 29 Mar 2002 22:45:45 -0000 1.3 +++ srclib/apr-util/buckets/apr_buckets_alloc.c 30 Mar 2002 06:41:20 -0000 @@ -55,24 +55,31 @@ #include <stdlib.h> #include "apr_buckets.h" -/* - * XXX: this file will be filled in later - */ +typedef struct bucket_alloc_node_header { + apr_size_t size; + apr_bucket_alloc_t *alloc; + struct bucket_alloc_node_header *next; +} bucket_alloc_node_header; + +#define SMALL_NODE_THRESHOLD 128 +#define NODE_HEADER_SIZE APR_ALIGN_DEFAULT(sizeof(bucket_alloc_node_header)) + -/* XXX: Remove the ifdef when the struct is filled in. - * An empty struct causes a compiler error on NetWare - */ -#ifndef NETWARE /** A list of free memory from which new buckets or private bucket * structures can be allocated. */ struct apr_bucket_alloc_t { + apr_pool_t *pool; + bucket_alloc_node_header *small_nodes; }; -#endif APU_DECLARE(apr_bucket_alloc_t *) apr_bucket_alloc_create(apr_pool_t *p) { - return (apr_bucket_alloc_t *)0xFECCFECC; + apr_bucket_alloc_t *list = + (apr_bucket_alloc_t *)apr_palloc(p, sizeof(*list)); + list->pool = p; + list->small_nodes = NULL; + return list; } APU_DECLARE(void) apr_bucket_alloc_destroy(apr_bucket_alloc_t *list) @@ -81,10 +88,37 @@ APU_DECLARE(void *) apr_bucket_alloc(apr_size_t size, apr_bucket_alloc_t *list) { - return malloc(size); + bucket_alloc_node_header *node; + if (size <= SMALL_NODE_THRESHOLD) { + node = list->small_nodes; + if (node) { + list->small_nodes = node->next; + } + else { + node = (bucket_alloc_node_header *)apr_palloc(list->pool, + NODE_HEADER_SIZE + + SMALL_NODE_THRESHOLD); + node->alloc = list; + node->size = SMALL_NODE_THRESHOLD; + } + } + else { + node = (bucket_alloc_node_header *)malloc(size + NODE_HEADER_SIZE); + node->alloc = NULL; + node->size = size; + } + return ((char *)node) + NODE_HEADER_SIZE; } APU_DECLARE(void) apr_bucket_free(void *block) { - free(block); + bucket_alloc_node_header *node = (bucket_alloc_node_header *) + (((char *)block) - NODE_HEADER_SIZE); + if (node->size <= SMALL_NODE_THRESHOLD) { + node->next = node->alloc->small_nodes; + node->alloc->small_nodes = node; + } + else { + free(node); + } }