1 files changed, 193 insertions, 0 deletions
diff --git a/src/base/mem/pool.c b/src/base/mem/pool.c
new file mode 100644
index 0000000..bf6f2b5
--- /dev/null
+++ b/src/base/mem/pool.c
@@ -0,0 +1,193 @@
+#include <u.h>
+#include <base.h>
+
+#include "pool.h"
+
+// -----------------------------------------------------------------------
+// globals/macros
+
+#define NOMAGIC        0xDEADFA11u
+#define DEADMAGIC      0xDEADDEADu
+#define TAILMAGIC0     0xBEu
+#define TAILMAGIC1     0xEFu
+#define FREEMAGIC      0xBA5EBA11u
+#define USEDMAGIC      0x0A110C09u
+#define UNUSEDMAGIC   (0xCAB00D1Eu+1)
+#define COREMAGIC     (0xC0A1E5CEu+1)
+#define CORETAILMAGIC (0xEC5E1A0Cu+1)
+#define ALIGNMAGIC     0xA1F1D1C1u
+
+#define POISON        ((void*)0xCAFEBABEu)
+
+// -----------------------------------------------------------------------
+// hunk maintenance
+
+#define HUNKTAIL(h)  ((Tail*)((uchar*)(h)+(h)->size-sizeof(Tail)))
+
+static uintptr
+gethunksize(mem·Pool *pool, uintptr size)
+{
+    size += sizeof(Head) + sizeof(Tail);
+    if(size < pool->minhunk)
+        size = pool->minhunk;
+    size = (size+pool->quantum) & ~(pool->quantum-1); // aligns to quantum
+    return size;
+}
+
+static Head *
+sethunksize(Head *h, uintptr size)
+{
+    Tail *t;
+
+    assert(h->magic != FREEMAGIC);
+
+    h->size = size;
+
+    t = HUNKTAIL(h);
+    t->size = size;
+    t->magic0 = TAILMAGIC0;
+    t->magic1 = TAILMAGIC1;
+
+    return h;
+}
+
+static void
+checkhunk(mem·Pool *p, Head *h)
+{
+    switch(h->magic){
+        default:
+            abort();
+        case FREEMAGIC:
+        case UNUSEDMAGIC:
+        case DEADMAGIC:
+        case COREMAGIC:
+        case CORETAILMAGIC:
+        case USEDMAGIC:
+            ;
+    }
+}
+
+// -----------------------------------------------------------------------
+// core maintenance
+
+#define COREHEAD(c)  ((Head*)((uchar*)(c)+(c)->len -sizeof(Head)))
+
+static uintptr
+getcoresize(mem·Pool *pool, uintptr size)
+{
+    size += sizeof(Core) + sizeof(Tail);
+    if(size < pool->mincore)
+        size = pool->mincore;
+    size = (size+pool->quantum) & ~(pool->quantum-1);
+    return size;
+}
+
+static Core *
+setcoresize(Core *c, uintptr size)
+{
+    Head *h;
+
+    c->len = size;
+
+    h = COREHEAD(c);
+    h->size  = 0;
+    h->magic = CORETAILMAGIC;
+
+    return c;
+}
+
+static void
+newcore(mem·Pool *pool, uintptr size)
+{
+    Core *c;
+
+    // XXX: check for size overflow
+ 
+    if(!(c = pool->mem.alloc(pool->heap, 1, size)))
+        return;
+
+    pool->cursize += size;
+
+    /* core header */
+    c->magic = COREMAGIC;
+    sethunksize((Head*)c, sizeof(Core));
+    setcoresize(c, size);
+    checkhunk(pool, (Head*)c);
+}
+
+// -----------------------------------------------------------------------
+// free list maintenance
+
+static Free *
+findgreater(Free *root, uintptr size)
+{
+    Free *last;
+
+    last = nil;
+    for(;;){
+        if(!root)
+            return last;
+        if(size == root->size)
+            return root;
+        if(size < root->size){
+            last = root;
+            root = root->left;
+        }else
+            root = root->right;
+    }
+}
+
+// -----------------------------------------------------------------------
+// exported functions
+
+/* constructors / destructors */
+mem·Pool*
+mem·makepool(mem·Allocator mem, void *heap, char *name, int flags, intptr maxsize, intptr mincore)
+{
+    mem·Pool *pool = mem.alloc(heap, 1, sizeof(*pool));
+    mem·set(pool, sizeof(*pool), 0);
+
+    pool->mem     = mem;
+    pool->heap    = heap;
+    pool->name    = name;
+    pool->flags   = flags;
+    pool->mincore = mincore;
+    pool->maxsize = maxsize;
+ 
+    return pool;
+}
+
+void
+mem·freepool(mem·Pool *pool)
+{
+    void *heap = pool->heap;
+    mem·Allocator mem = pool->mem;
+
+    mem.free(heap, pool);
+}
+
+/* base functions */
+
+void *
+mem·poolalloc(mem·Pool *pool, long n, uintptr eltsize)
+{
+    Free *node;
+    uintptr size, bksz;
+
+    if((size = n*eltsize) >= 0x80000000UL){
+        errorf("allocation overflow");
+        return nil;
+    }
+
+    bksz = gethunksize(pool, size);
+    node = findgreater(pool->free, bksz);
+    if(!node){
+        newcore(pool, getcoresize(pool, bksz));
+        if(!(node = findgreater(pool->free, bksz)))
+            return nil;
+    }
+
+
+
+    return nil;
+}