Add heap manager for allocations up to 2040 bytes

4 files changed, 125 insertions, 2 deletions

diff --git a/src/include/kernel/heapmgr.H b/src/include/kernel/heapmgr.H
new file mode 100644
index 000000000..41a3e2cf5
--- /dev/null
+++ b/src/include/kernel/heapmgr.H
@@ -0,0 +1,39 @@
+#ifndef __KERNEL_HEAPMGR_H
+#define __KERNEL_HEAPMGR_H
+
+#include <stdint.h>
+#include <util/lockfree/stack.H>
+
+class HeapManager
+{
+    public:
+	static void* allocate(size_t n);
+	static void  free(void *);
+
+	enum
+	{
+	    BUCKETS = 8,
+	};
+
+    protected:
+	HeapManager() {};
+	~HeapManager() {};
+
+    private:
+	void* _allocate(size_t);
+	void _free(void*);
+
+	struct chunk_t
+	{
+	    size_t len;
+	    chunk_t* next;
+	};
+	Util::Lockfree::Stack<chunk_t> first_chunk[BUCKETS];
+
+	chunk_t* pop_bucket(size_t);
+	void push_bucket(chunk_t*, size_t);
+
+	void newPage();
+};
+
+#endif
diff --git a/src/kernel/heapmgr.C b/src/kernel/heapmgr.C
new file mode 100644
index 000000000..43a9cd23c
--- /dev/null
+++ b/src/kernel/heapmgr.C
@@ -0,0 +1,83 @@
+#include <kernel/heapmgr.H>
+#include <util/singleton.H>
+#include <kernel/console.H>
+#include <kernel/pagemgr.H>
+
+void* HeapManager::allocate(size_t n)
+{
+    HeapManager& hmgr = Singleton<HeapManager>::instance();
+    return hmgr._allocate(n);
+}
+
+void HeapManager::free(void* p)
+{
+    HeapManager& hmgr = Singleton<HeapManager>::instance();
+    return hmgr._free(p);
+}
+
+void* HeapManager::_allocate(size_t n)
+{
+    int which_bucket = 0;
+    while (n > ((1 << (which_bucket + 4)) - 8)) which_bucket++;
+
+    chunk_t* chunk = (chunk_t*)NULL;
+    chunk = pop_bucket(which_bucket);
+    if (NULL == chunk)
+    {
+	newPage();
+	return _allocate(n);
+    }
+    else
+    {
+	return &chunk->next;
+    }
+}
+
+void HeapManager::_free(void* p)
+{
+    if (NULL == p) return;
+
+    chunk_t* chunk = (chunk_t*)((size_t*)p)-1;
+    push_bucket(chunk, chunk->len);
+}
+
+HeapManager::chunk_t* HeapManager::pop_bucket(size_t n)
+{
+    if (n >= BUCKETS) return NULL;
+
+    chunk_t* c = first_chunk[n].pop();
+
+    if (NULL == c)
+    {
+	// Couldn't allocate from the correct size bucket, so split up an
+	// item from the next sized bucket.
+	c = pop_bucket(n+1);
+	if (NULL != c)
+	{
+	    chunk_t* c1 = (chunk_t*)(((uint8_t*)c) + (1 << (n + 4)));
+	    c->len = n;
+	    c1->len = n;
+	    push_bucket(c1, n);
+	}
+    }
+
+    return c;
+}
+
+void HeapManager::push_bucket(chunk_t* c, size_t n)
+{
+    if (n >= BUCKETS) return;
+    first_chunk[n].push(c);
+}
+
+void HeapManager::newPage()
+{
+    void* page = PageManager::allocatePage();
+    chunk_t * c = (chunk_t*)page;
+    for (int i = 0; i < (PageManager::PAGESIZE / (1 << (BUCKETS + 3))); i++)
+    {
+	c->len = BUCKETS-1;
+	push_bucket(c, BUCKETS-1);
+	c = (chunk_t*)(((uint8_t*)c) + (1 << (BUCKETS + 3)));
+    }
+}
diff --git a/src/kernel/kernel.C b/src/kernel/kernel.C
index 2ce5f3e43..2872c398f 100644
--- a/src/kernel/kernel.C
+++ b/src/kernel/kernel.C
@@ -1,6 +1,7 @@
 #include <stdint.h>
 #include <kernel/console.H>
 #include <kernel/pagemgr.H>
+#include <kernel/heapmgr.H>
 #include <util/singleton.H>
 
 class Kernel
@@ -20,7 +21,7 @@ int main()
     Kernel& kernel = Singleton<Kernel>::instance();
     kernel.cppBootstrap();
     kernel.memBootstrap(); 
-
+    
     while(1);
     return 0;
 }
diff --git a/src/kernel/makefile b/src/kernel/makefile
index c4cf3c421..41d9f706c 100644
--- a/src/kernel/makefile
+++ b/src/kernel/makefile
@@ -1,7 +1,7 @@
 OBJDIR = ../../obj
 include ../../config.mk
 
-OBJS = start.o kernel.o console.o pagemgr.o
+OBJS = start.o kernel.o console.o pagemgr.o heapmgr.o
 OBJECTS = $(addprefix ${OBJDIR}/, ${OBJS})
 
 all: ${OBJECTS}