[PATCH] bucket alloc: a simpler approach

[Brian Pane]

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);
+    }
 }