refactoring

1 files changed, 310 insertions, 0 deletions

diff --git a/kernel/src/memory.c b/kernel/src/memory.c
new file mode 100644
index 0000000..e8d864b
--- /dev/null
+++ b/kernel/src/memory.c
@@ -0,0 +1,310 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <memory.h>
+
+struct boundary_tag {
+	unsigned int magic;	   
+	unsigned int size; 	   
+	unsigned int real_size;
+	int index;
+
+	struct boundary_tag *split_left;
+	struct boundary_tag *split_right;
+	
+	struct boundary_tag *next;
+	struct boundary_tag *prev;
+};
+
+#define ALLOC_MAGIC     0xc001c0de
+#define MAXCOMPLETE     5
+#define MAXEXP          32
+#define MINEXP          8    
+
+#define MODE_BEST       0
+#define MODE_INSTANT    1
+
+#define MODE    MODE_BEST
+
+struct boundary_tag* l_freePages[MAXEXP];
+int                  l_completePages[MAXEXP];
+
+static int l_initialized = 0;
+static int l_pageSize  = 4096;
+static int l_pageCount = 16;
+
+static inline int getexp(unsigned int size) {
+    if (size < (1<<MINEXP)) {
+        return -1;
+    }
+        
+    int shift = MINEXP;
+
+    while (shift < MAXEXP) {
+        if ((unsigned)(1<<shift) > size) break;
+        shift += 1;
+    }
+
+    return shift - 1;    
+}
+
+static inline void insert_tag(struct boundary_tag *tag, int index) {
+    int realIndex;
+    
+    if (index < 0)  {
+        realIndex = getexp(tag->real_size - sizeof(struct boundary_tag));
+        if (realIndex < MINEXP) realIndex = MINEXP;
+    } else {
+        realIndex = index;
+    }
+    
+    tag->index = realIndex;
+    
+    if (l_freePages[ realIndex ] != NULL) {
+        l_freePages[ realIndex ]->prev = tag;
+        tag->next = l_freePages[ realIndex ];
+    }
+
+    l_freePages[ realIndex ] = tag;
+}
+
+static inline void remove_tag(struct boundary_tag *tag) {
+    if (l_freePages[ tag->index ] == tag) l_freePages[ tag->index ] = tag->next;
+
+    if (tag->prev != NULL) tag->prev->next = tag->next;
+    if (tag->next != NULL) tag->next->prev = tag->prev;
+
+    tag->next = NULL;
+    tag->prev = NULL;
+    tag->index = -1;
+}
+
+static inline struct boundary_tag* melt_left(struct boundary_tag *tag) {
+    struct boundary_tag *left = tag->split_left;
+                            
+    left->real_size   += tag->real_size;
+    left->split_right  = tag->split_right;
+    
+    if (tag->split_right != NULL) tag->split_right->split_left = left;
+
+    return left;
+}
+
+
+static inline struct boundary_tag* absorb_right(struct boundary_tag *tag) {
+    struct boundary_tag *right = tag->split_right;
+
+    remove_tag(right);
+    
+    tag->real_size += right->real_size;
+    
+    tag->split_right  = right->split_right;
+    if (right->split_right != NULL)
+                right->split_right->split_left = tag;
+
+    return tag;
+}
+
+static inline struct boundary_tag* split_tag(struct boundary_tag* tag) {
+    unsigned int remainder = tag->real_size - sizeof(struct boundary_tag) - tag->size;
+
+    struct boundary_tag *new_tag = 
+        (struct boundary_tag*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag) + tag->size);    
+    
+    new_tag->magic = ALLOC_MAGIC;
+    new_tag->real_size = remainder;    
+
+    new_tag->next = NULL;
+    new_tag->prev = NULL;
+    
+    new_tag->split_left = tag;
+    new_tag->split_right = tag->split_right;
+    
+    if (new_tag->split_right != NULL) new_tag->split_right->split_left = new_tag;
+    tag->split_right = new_tag;
+    
+    tag->real_size -= new_tag->real_size;
+    
+    insert_tag(new_tag, -1);
+    
+    return new_tag;
+}
+
+static struct boundary_tag* allocate_new_tag(unsigned int size) {
+    unsigned int pages;
+    unsigned int usage;
+    struct boundary_tag *tag;
+
+    usage  = size + sizeof(struct boundary_tag);
+
+    pages = usage / l_pageSize;
+    if ((usage % l_pageSize) != 0) pages += 1;
+
+    if (pages < (unsigned) l_pageCount) pages = l_pageCount;
+
+    tag = (struct boundary_tag*)memory_alloc_page(pages);
+
+    if (tag == NULL) return NULL;
+    
+    tag->magic         = ALLOC_MAGIC;
+    tag->size         = size;
+    tag->real_size     = pages * l_pageSize;
+    tag->index         = -1;
+
+    tag->next        = NULL;
+    tag->prev        = NULL;
+    tag->split_left     = NULL;
+    tag->split_right     = NULL;
+
+    return tag;
+}
+
+
+
+void *malloc(size_t size) {
+    int index;
+    void *ptr;
+    struct boundary_tag *tag = NULL;
+
+    memory_lock();
+
+    if (l_initialized == 0) {
+        for (index = 0; index < MAXEXP; index++) {
+            l_freePages[index] = NULL;
+            l_completePages[index] = 0;
+        }
+        l_initialized = 1;
+    }
+
+    index = getexp(size) + MODE;
+    if (index < MINEXP) index = MINEXP;
+    
+    tag = l_freePages[index];
+    while (tag != NULL) {
+        if (
+            (tag->real_size - sizeof(struct boundary_tag)) 
+            >= (size + sizeof(struct boundary_tag))
+       ) {
+            break;
+        }
+        tag = tag->next;
+    }
+    
+    if (tag == NULL) {    
+        if ((tag = allocate_new_tag(size)) == NULL) {
+            memory_unlock();
+            return NULL;
+        }
+        index = getexp(tag->real_size - sizeof(struct boundary_tag));
+    } else {
+        remove_tag(tag);
+
+        if ((tag->split_left == NULL) && (tag->split_right == NULL))
+            l_completePages[ index ] -= 1;
+    }
+    
+    tag->size = size;
+
+    unsigned int remainder = tag->real_size - size - sizeof(struct boundary_tag) * 2;
+
+    if (((int)(remainder) > 0)) {
+        int childIndex = getexp(remainder);
+
+        if (childIndex >= 0) {
+            struct boundary_tag *new_tag = split_tag(tag); 
+            tag = new_tag;
+        }
+    }
+
+    ptr = (void*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag));
+    memory_unlock();
+    return ptr;
+}
+
+void free(void *ptr) {
+    int index;
+    struct boundary_tag *tag;
+
+    if (ptr == NULL) return;
+
+    memory_lock();
+    
+    tag = (struct boundary_tag*)((uintptr_t)(void *)ptr - sizeof(struct boundary_tag));
+    
+    if (tag->magic != ALLOC_MAGIC) {
+        memory_unlock();
+        return;
+    }
+
+    while ((tag->split_left != NULL) && (tag->split_left->index >= 0)) {
+        tag = melt_left(tag);
+        remove_tag(tag);
+    }
+
+    while ((tag->split_right != NULL) && (tag->split_right->index >= 0)) {
+        tag = absorb_right(tag);
+    }
+
+    index = getexp(tag->real_size - sizeof(struct boundary_tag));
+    if (index < MINEXP) index = MINEXP;
+    
+    if ((tag->split_left == NULL) && (tag->split_right == NULL)) {
+        if (l_completePages[index] == MAXCOMPLETE) {
+            unsigned int pages = tag->real_size / l_pageSize;
+
+            if ((tag->real_size % l_pageSize) != 0) pages += 1;
+            if (pages < (unsigned) l_pageCount) pages = l_pageCount;
+
+            memory_free_page(tag, pages);
+            memory_unlock();
+            return;
+        }
+
+        l_completePages[ index ] += 1;
+    }
+
+    insert_tag(tag, index);
+
+    memory_unlock();
+}
+
+void* calloc(size_t nobj, size_t size) {
+    int real_size;
+    void *p;
+
+    real_size = nobj * size;
+       
+    p = malloc(real_size);
+
+    memset(p, 0, real_size);
+
+    return p;
+}
+
+void* realloc(void *p, size_t size) {
+    void *ptr;
+    struct boundary_tag *tag;
+    size_t real_size;
+    
+    if (size == 0) {
+        free(p);
+        return NULL;
+    }
+
+    if (p == NULL) {
+        return malloc(size);
+    }
+
+    memory_lock();
+    tag = (struct boundary_tag*)((uintptr_t)(void *)p - sizeof(struct boundary_tag));
+    real_size = tag->size;
+    memory_unlock();
+
+    if (real_size > size) real_size = size;
+
+    ptr = malloc(size);
+    memcpy(ptr, p, real_size);
+    free(p);
+
+    return ptr;
+}