Implimented a simple allocation system that does not waste memory.

Added realloc. The allocation system was needed to support realloc.

1 files changed, 132 insertions, 7 deletions

diff --git a/libc/stdlib/malloc/alloc.c b/libc/stdlib/malloc/alloc.c
index 5282c140a..5e508f9c1 100644
--- a/libc/stdlib/malloc/alloc.c
+++ b/libc/stdlib/malloc/alloc.c
@@ -3,6 +3,28 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+struct chunkControl {
+	size_t nodeCount;
+	size_t chunkSize;
+};
+
+struct nodeControl {
+	struct chunkControl *chunk;
+	size_t nodeSize;
+};
+
+#define ROUND_UP_LENGTH(len) ((len+7) & ~0x07)
+
+extern struct nodeControl *mallocNextNode;
+
+#ifdef L_malloc
+/* This variable is a pointer to the next place to allocate from.
+ * Note: This variable makes the code NOT thread save. */
+struct nodeControl *mallocNextNode = 0;
+static size_t PageSize = 0;
+
+#endif
+
 #ifdef L_calloc_dbg
 
 void *
@@ -61,12 +83,64 @@ calloc(size_t num, size_t size)
 void *
 malloc(size_t len)
 {
-  void * result = mmap((void *)0, len, PROT_READ | PROT_WRITE,
-                 MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
-  if (result == (void*)-1)
-    return 0;
-    
-  return result;
+	void *result;
+	struct chunkControl *chunk;
+	struct nodeControl  *next;
+	size_t size;
+
+	/* round len up to keep things on even boundaries */
+	len = ROUND_UP_LENGTH(len);
+
+	if (len == 0)
+		return 0;
+
+TryAgain:
+	if (mallocNextNode != 0) {
+		/* first see if this request will fit on this chunk */
+		next  = mallocNextNode;
+		chunk = next->chunk;
+		if (((char *)next + sizeof(struct nodeControl)*2 + len) < 
+		    ((char *)chunk + chunk->chunkSize))
+		{
+			/* this request will fit, so simply move the next
+			 * pointer ahead and update chunk node count */
+			next->nodeSize = len;
+			result = (char *)next + sizeof(struct nodeControl);
+			chunk->nodeCount++;
+			next = (struct nodeControl *)
+			          ((char *)next + (sizeof(struct nodeControl) + len));
+			next->chunk = chunk;
+			next->nodeSize = 0;
+			mallocNextNode = next;
+
+			return result; /* normal return path */
+		}
+		
+	}
+	
+	/* the request will not fit on this chunk, so get another chunk */
+	if (PageSize == 0) {
+		PageSize = getpagesize();
+	}
+	size = len + (sizeof(struct chunkControl) + (sizeof(struct nodeControl) * 2));
+	if (size < PageSize * 2) {
+		size = PageSize * 2;
+	}
+	size = (size + (PageSize-1)) & ~(PageSize-1);
+
+	chunk = mmap((void *)0, size, PROT_READ | PROT_WRITE,
+	              MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
+	if (chunk == (void*)-1)
+		return 0;
+
+	chunk->chunkSize = size;
+	chunk->nodeCount = 0;
+	next             = (struct nodeControl *)
+		                 ((char *)chunk + sizeof(struct chunkControl));
+	next->chunk      = chunk;
+	mallocNextNode   = next;
+
+	goto TryAgain;
 }
 
 #endif
@@ -76,7 +150,58 @@ malloc(size_t len)
 void
 free(void * ptr)
 {
-  munmap(ptr, 0);
+	struct chunkControl *chunk;
+	struct nodeControl  *node;
+	
+	if (ptr == 0) {
+		return;
+	}
+	/* get a pointer to the control information for this memory node
+	 * and the chunk it belongs to */
+	node  = (struct nodeControl *)ptr - 1;
+	chunk = node->chunk;
+	/* decrement the node count and if it is zero free the chunk */
+	chunk->nodeCount--;
+	if (chunk->nodeCount == 0) {
+		if ((void *)mallocNextNode >= (void *)chunk && 
+		     ((void *)mallocNextNode < (void *)((char *)chunk + chunk->chunkSize)))
+		{
+			mallocNextNode = 0;
+		}
+		munmap(chunk, chunk->chunkSize);
+	}
 }
 
 #endif
+
+#ifdef L_realloc
+
+void *
+realloc(void *ptr, size_t len)
+{
+	struct nodeControl *node;
+	size_t oldSize;
+	void *new;
+	
+	
+	if (ptr == 0) {
+		return malloc(len);
+	}
+	if (len == 0) {
+		free(ptr);
+		return 0;
+	}
+	node    = (struct nodeControl *)ptr - 1;
+	oldSize = node->nodeSize;
+	if (oldSize >= len) {
+		return ptr;
+	}
+	
+	new = malloc(len);
+	memcpy(new, ptr, len);
+	free(ptr);
+	return new;
+}
+
+#endif
+