idk

2 files changed, 376 insertions, 73 deletions

diff --git a/src/kernel/lib/stdlib/liballoc.c b/src/kernel/lib/stdlib/liballoc.c
index 04dc450..0b7e182 100644
--- a/src/kernel/lib/stdlib/liballoc.c
+++ b/src/kernel/lib/stdlib/liballoc.c
@@ -1,7 +1,10 @@
+/**
+ * TODO: This file suffers from major ugliness and needs a cleanup!
+ */
+
 #include <stddef.h>
 #include <stdint.h>
 #include <kernel/paging/paging.h>
-#include <kernel/lib/stdlib/liballoc.h>
 
 int liballoc_lock()
 {
@@ -30,11 +33,6 @@ int liballoc_free(void *ptr, size_t p)
 #define ALIGNMENT 16ul
 #define ALIGN_TYPE char
 #define ALIGN_INFO sizeof(ALIGN_TYPE) * 16
-#define USE_CASE1
-#define USE_CASE2
-#define USE_CASE3
-#define USE_CASE4
-#define USE_CASE5
 
 #define ALIGN(ptr) \
         if ( ALIGNMENT > 1 ) { \
@@ -77,17 +75,17 @@ struct liballoc_minor {
     unsigned int req_size;
 };
 
-static struct liballoc_major *l_memRoot = NULL;
-static struct liballoc_major *l_bestBet = NULL;
+static struct liballoc_major *l_mem_root = NULL;
+static struct liballoc_major *l_best_bet = NULL;
 
 static unsigned int l_pageSize = 4096;
 static unsigned int l_pageCount = 16;
 static unsigned long long l_allocated = 0;
 static unsigned long long l_inuse = 0;
 
-static long long l_warningCount = 0;
-static long long l_errorCount = 0;
-static long long l_possibleOverruns = 0;
+static long long l_warning_count = 0;
+static long long l_error_count = 0;
+static long long l_possible_overruns = 0;
 
 static void *liballoc_memset(void *s, int c, size_t n)
 {
@@ -120,7 +118,7 @@ static void *liballoc_memcpy(void *s1, const void *s2, size_t n)
     return s1;
 }
 
-static struct liballoc_major *allocate_new_page(unsigned int size)
+static struct liballoc_major *allocate_new_page(unsigned int size, unsigned int shared)
 {
     unsigned int st;
     struct liballoc_major *maj;
@@ -136,9 +134,10 @@ static struct liballoc_major *allocate_new_page(unsigned int size)
     if (st < l_pageCount) st = l_pageCount;
 
     maj = (struct liballoc_major *) liballoc_alloc(st);
+    if (shared == 1) paging_set_user((uint32_t) maj, st);
 
     if (maj == NULL) {
-        l_warningCount += 1;
+        l_warning_count += 1;
         return NULL;
     }
 
@@ -154,10 +153,14 @@ static struct liballoc_major *allocate_new_page(unsigned int size)
     return maj;
 }
 
-void *PREFIX(malloc)(size_t req_size)
+/**
+ * KERNEL SECTION
+*/
+
+void *kmalloc(size_t req_size)
 {
-    int startedBet = 0;
-    unsigned long long bestSize = 0;
+    int started_bet = 0;
+    unsigned long long best_size = 0;
     void *p = NULL;
     uintptr_t diff;
     struct liballoc_major *maj;
@@ -172,59 +175,58 @@ void *PREFIX(malloc)(size_t req_size)
     liballoc_lock();
 
     if (size == 0) {
-        l_warningCount += 1;
+        l_warning_count += 1;
         liballoc_unlock();
-        return PREFIX(malloc)(1);
+        return kmalloc(1);
     }
 
-    if (l_memRoot == NULL) {
-        l_memRoot = allocate_new_page(size);
-        if (l_memRoot == NULL) {
+    if (l_mem_root == NULL) {
+        l_mem_root = allocate_new_page(size, 0);
+        if (l_mem_root == NULL) {
             liballoc_unlock();
             return NULL;
         }
     }
 
-    maj = l_memRoot;
-    startedBet = 0;
+    maj = l_mem_root;
+    started_bet = 0;
 
-    if (l_bestBet != NULL) {
-        bestSize = l_bestBet->size - l_bestBet->usage;
+    if (l_best_bet != NULL) {
+        best_size = l_best_bet->size - l_best_bet->usage;
 
-        if (bestSize > (size + sizeof(struct liballoc_minor))) {
-            maj = l_bestBet;
-            startedBet = 1;
+        if (best_size > (size + sizeof(struct liballoc_minor))) {
+            maj = l_best_bet;
+            started_bet = 1;
         }
     }
 
     while (maj != NULL) {
         diff = maj->size - maj->usage;
-        if (bestSize < diff) {
-            l_bestBet = maj;
-            bestSize = diff;
+        if (best_size < diff) {
+            l_best_bet = maj;
+            best_size = diff;
         }
 
-#ifdef USE_CASE1
+        // Use-case 1
         if (diff < (size + sizeof(struct liballoc_minor))) {
             if (maj->next != NULL) {
                 maj = maj->next;
                 continue;
             }
 
-            if (startedBet == 1) {
-                maj = l_memRoot;
-                startedBet = 0;
+            if (started_bet == 1) {
+                maj = l_mem_root;
+                started_bet = 0;
                 continue;
             }
 
-            maj->next = allocate_new_page(size);
+            maj->next = allocate_new_page(size, 0);
             if (maj->next == NULL) break;
             maj->next->prev = maj;
             maj = maj->next;
         }
-#endif
 
-#ifdef USE_CASE2
+        // Use-case 2
         if (maj->first == NULL) {
             maj->first = (struct liballoc_minor *) ((uintptr_t) maj + sizeof(struct liballoc_major));
 
@@ -241,9 +243,8 @@ void *PREFIX(malloc)(size_t req_size)
             liballoc_unlock();
             return p;
         }
-#endif
 
-#ifdef USE_CASE3
+        // Use-case 3
         diff = (uintptr_t) (maj->first);
         diff -= (uintptr_t) maj;
         diff -= sizeof(struct liballoc_major);
@@ -264,11 +265,309 @@ void *PREFIX(malloc)(size_t req_size)
             liballoc_unlock();
             return p;
         }
-#endif
 
-#ifdef USE_CASE4
+        // Use-case 4
         min = maj->first;
+        while (min != NULL) {
+            if (min->next == NULL) {
+                diff = (uintptr_t) (maj) + maj->size;
+                diff -= (uintptr_t) min;
+                diff -= sizeof(struct liballoc_minor);
+                diff -= min->size;
+                if (diff >= (size + sizeof(struct liballoc_minor))) {
+                    min->next = (struct liballoc_minor *) ((uintptr_t) min + sizeof(struct liballoc_minor) + min->size);
+                    min->next->prev = min;
+                    min = min->next;
+                    min->next = NULL;
+                    min->magic = LIBALLOC_MAGIC;
+                    min->block = maj;
+                    min->size = size;
+                    min->req_size = req_size;
+                    maj->usage += size + sizeof(struct liballoc_minor);
+                    l_inuse += size;
+                    p = (void *) ((uintptr_t) min + sizeof(struct liballoc_minor));
+                    ALIGN(p);
+                    liballoc_unlock();
+                    return p;
+                }
+            }
+
+            if (min->next != NULL) {
+                diff = (uintptr_t) (min->next);
+                diff -= (uintptr_t) min;
+                diff -= sizeof(struct liballoc_minor);
+                diff -= min->size;
 
+                if (diff >= (size + sizeof(struct liballoc_minor))) {
+                    new_min = (struct liballoc_minor *) ((uintptr_t) min + sizeof(struct liballoc_minor) + min->size);
+                    new_min->magic = LIBALLOC_MAGIC;
+                    new_min->next = min->next;
+                    new_min->prev = min;
+                    new_min->size = size;
+                    new_min->req_size = req_size;
+                    new_min->block = maj;
+                    min->next->prev = new_min;
+                    min->next = new_min;
+                    maj->usage += size + sizeof(struct liballoc_minor);
+                    l_inuse += size;
+                    p = (void *) ((uintptr_t) new_min + sizeof(struct liballoc_minor));
+                    ALIGN(p);
+                    liballoc_unlock();
+                    return p;
+                }
+            }
+
+            min = min->next;
+        }
+
+        // Use-case 5
+        if (maj->next == NULL) {
+            if (started_bet == 1) {
+                maj = l_mem_root;
+                started_bet = 0;
+                continue;
+            }
+            maj->next = allocate_new_page(size, 0);
+            if (maj->next == NULL) break;
+            maj->next->prev = maj;
+        }
+        maj = maj->next;
+    }
+
+    liballoc_unlock();
+
+    return NULL;
+}
+
+void kfree(void *ptr)
+{
+    struct liballoc_minor *min;
+    struct liballoc_major *maj;
+
+    if (ptr == NULL) {
+        l_warning_count += 1;
+        return;
+    }
+
+    UNALIGN(ptr);
+    liballoc_lock();
+
+    min = (struct liballoc_minor *) ((uintptr_t) ptr - sizeof(struct liballoc_minor));
+
+    if (min->magic != LIBALLOC_MAGIC) {
+        l_error_count += 1;
+
+        if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
+            ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
+            ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
+            l_possible_overruns += 1;
+        }
+
+        liballoc_unlock();
+        return;
+    }
+
+    maj = min->block;
+    l_inuse -= min->size;
+    maj->usage -= (min->size + sizeof(struct liballoc_minor));
+    min->magic = LIBALLOC_DEAD;
+
+    if (min->next != NULL) min->next->prev = min->prev;
+    if (min->prev != NULL) min->prev->next = min->next;
+    if (min->prev == NULL) maj->first = min->next;
+    if (maj->first == NULL) {
+        if (l_mem_root == maj) l_mem_root = maj->next;
+        if (l_best_bet == maj) l_best_bet = NULL;
+        if (maj->prev != NULL) maj->prev->next = maj->next;
+        if (maj->next != NULL) maj->next->prev = maj->prev;
+        l_allocated -= maj->size;
+        liballoc_free(maj, maj->pages);
+    } else {
+        if (l_best_bet != NULL) {
+            int best_size = l_best_bet->size - l_best_bet->usage;
+            int majSize = maj->size - maj->usage;
+            if (majSize > best_size) l_best_bet = maj;
+        }
+    }
+    liballoc_unlock();
+}
+
+void *kcalloc(size_t nobj, size_t size)
+{
+    int real_size;
+    void *p;
+
+    real_size = nobj * size;
+
+    p = kmalloc(real_size);
+
+    liballoc_memset(p, 0, real_size);
+
+    return p;
+}
+
+void *krealloc(void *p, size_t size)
+{
+    void *ptr;
+    struct liballoc_minor *min;
+    unsigned int real_size;
+
+    if (size == 0) {
+        kfree(p);
+        return NULL;
+    }
+
+    if (p == NULL) return kmalloc(size);
+
+    ptr = p;
+    UNALIGN(ptr);
+    liballoc_lock();
+    min = (struct liballoc_minor *) ((uintptr_t) ptr - sizeof(struct liballoc_minor));
+
+    if (min->magic != LIBALLOC_MAGIC) {
+        l_error_count += 1;
+        if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
+            ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
+            ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
+            l_possible_overruns += 1;
+        }
+
+        liballoc_unlock();
+        return NULL;
+    }
+
+    real_size = min->req_size;
+
+    if (real_size >= size) {
+        min->req_size = size;
+        liballoc_unlock();
+        return p;
+    }
+
+    liballoc_unlock();
+
+    ptr = kmalloc(size);
+    liballoc_memcpy(ptr, p, real_size);
+    kfree(p);
+
+    return ptr;
+}
+
+/**
+ * USER SECTION
+*/
+
+void *umalloc(size_t req_size)
+{
+    int started_bet = 0;
+    unsigned long long best_size = 0;
+    void *p = NULL;
+    uintptr_t diff;
+    struct liballoc_major *maj;
+    struct liballoc_minor *min;
+    struct liballoc_minor *new_min;
+    unsigned long size = req_size;
+
+    if (ALIGNMENT > 1) {
+        size += ALIGNMENT + ALIGN_INFO;
+    }
+
+    liballoc_lock();
+
+    if (size == 0) {
+        l_warning_count += 1;
+        liballoc_unlock();
+        return umalloc(1);
+    }
+
+    if (l_mem_root == NULL) {
+        l_mem_root = allocate_new_page(size, 1);
+        if (l_mem_root == NULL) {
+            liballoc_unlock();
+            return NULL;
+        }
+    }
+
+    maj = l_mem_root;
+    started_bet = 0;
+
+    if (l_best_bet != NULL) {
+        best_size = l_best_bet->size - l_best_bet->usage;
+
+        if (best_size > (size + sizeof(struct liballoc_minor))) {
+            maj = l_best_bet;
+            started_bet = 1;
+        }
+    }
+
+    while (maj != NULL) {
+        diff = maj->size - maj->usage;
+        if (best_size < diff) {
+            l_best_bet = maj;
+            best_size = diff;
+        }
+
+        // Use-case 1
+        if (diff < (size + sizeof(struct liballoc_minor))) {
+            if (maj->next != NULL) {
+                maj = maj->next;
+                continue;
+            }
+
+            if (started_bet == 1) {
+                maj = l_mem_root;
+                started_bet = 0;
+                continue;
+            }
+
+            maj->next = allocate_new_page(size, 1);
+            if (maj->next == NULL) break;
+            maj->next->prev = maj;
+            maj = maj->next;
+        }
+
+        // Use-case 2
+        if (maj->first == NULL) {
+            maj->first = (struct liballoc_minor *) ((uintptr_t) maj + sizeof(struct liballoc_major));
+
+            maj->first->magic = LIBALLOC_MAGIC;
+            maj->first->prev = NULL;
+            maj->first->next = NULL;
+            maj->first->block = maj;
+            maj->first->size = size;
+            maj->first->req_size = req_size;
+            maj->usage += size + sizeof(struct liballoc_minor);
+            l_inuse += size;
+            p = (void *) ((uintptr_t) (maj->first) + sizeof(struct liballoc_minor));
+            ALIGN(p);
+            liballoc_unlock();
+            return p;
+        }
+
+        // Use-case 3
+        diff = (uintptr_t) (maj->first);
+        diff -= (uintptr_t) maj;
+        diff -= sizeof(struct liballoc_major);
+
+        if (diff >= (size + sizeof(struct liballoc_minor))) {
+            maj->first->prev = (struct liballoc_minor *) ((uintptr_t) maj + sizeof(struct liballoc_major));
+            maj->first->prev->next = maj->first;
+            maj->first = maj->first->prev;
+            maj->first->magic = LIBALLOC_MAGIC;
+            maj->first->prev = NULL;
+            maj->first->block = maj;
+            maj->first->size = size;
+            maj->first->req_size = req_size;
+            maj->usage += size + sizeof(struct liballoc_minor);
+            l_inuse += size;
+            p = (void *) ((uintptr_t) (maj->first) + sizeof(struct liballoc_minor));
+            ALIGN(p);
+            liballoc_unlock();
+            return p;
+        }
+
+        // Use-case 4
+        min = maj->first;
         while (min != NULL) {
             if (min->next == NULL) {
                 diff = (uintptr_t) (maj) + maj->size;
@@ -320,20 +619,18 @@ void *PREFIX(malloc)(size_t req_size)
 
             min = min->next;
         }
-#endif
 
-#ifdef USE_CASE5
+        // Use-case 5
         if (maj->next == NULL) {
-            if (startedBet == 1) {
-                maj = l_memRoot;
-                startedBet = 0;
+            if (started_bet == 1) {
+                maj = l_mem_root;
+                started_bet = 0;
                 continue;
             }
-            maj->next = allocate_new_page(size);
+            maj->next = allocate_new_page(size, 1);
             if (maj->next == NULL) break;
             maj->next->prev = maj;
         }
-#endif
         maj = maj->next;
     }
 
@@ -342,13 +639,13 @@ void *PREFIX(malloc)(size_t req_size)
     return NULL;
 }
 
-void PREFIX(free)(void *ptr)
+void ufree(void *ptr)
 {
     struct liballoc_minor *min;
     struct liballoc_major *maj;
 
     if (ptr == NULL) {
-        l_warningCount += 1;
+        l_warning_count += 1;
         return;
     }
 
@@ -358,12 +655,12 @@ void PREFIX(free)(void *ptr)
     min = (struct liballoc_minor *) ((uintptr_t) ptr - sizeof(struct liballoc_minor));
 
     if (min->magic != LIBALLOC_MAGIC) {
-        l_errorCount += 1;
+        l_error_count += 1;
 
         if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
             ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
             ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
-            l_possibleOverruns += 1;
+            l_possible_overruns += 1;
         }
 
         liballoc_unlock();
@@ -379,48 +676,48 @@ void PREFIX(free)(void *ptr)
     if (min->prev != NULL) min->prev->next = min->next;
     if (min->prev == NULL) maj->first = min->next;
     if (maj->first == NULL) {
-        if (l_memRoot == maj) l_memRoot = maj->next;
-        if (l_bestBet == maj) l_bestBet = NULL;
+        if (l_mem_root == maj) l_mem_root = maj->next;
+        if (l_best_bet == maj) l_best_bet = NULL;
         if (maj->prev != NULL) maj->prev->next = maj->next;
         if (maj->next != NULL) maj->next->prev = maj->prev;
         l_allocated -= maj->size;
         liballoc_free(maj, maj->pages);
     } else {
-        if (l_bestBet != NULL) {
-            int bestSize = l_bestBet->size - l_bestBet->usage;
+        if (l_best_bet != NULL) {
+            int best_size = l_best_bet->size - l_best_bet->usage;
             int majSize = maj->size - maj->usage;
-            if (majSize > bestSize) l_bestBet = maj;
+            if (majSize > best_size) l_best_bet = maj;
         }
     }
     liballoc_unlock();
 }
 
-void *PREFIX(calloc)(size_t nobj, size_t size)
+void *ucalloc(size_t nobj, size_t size)
 {
     int real_size;
     void *p;
 
     real_size = nobj * size;
 
-    p = PREFIX(malloc)(real_size);
+    p = umalloc(real_size);
 
     liballoc_memset(p, 0, real_size);
 
     return p;
 }
 
-void *PREFIX(realloc)(void *p, size_t size)
+void *urealloc(void *p, size_t size)
 {
     void *ptr;
     struct liballoc_minor *min;
     unsigned int real_size;
 
     if (size == 0) {
-        PREFIX(free)(p);
+        ufree(p);
         return NULL;
     }
 
-    if (p == NULL) return PREFIX(malloc)(size);
+    if (p == NULL) return umalloc(size);
 
     ptr = p;
     UNALIGN(ptr);
@@ -428,11 +725,11 @@ void *PREFIX(realloc)(void *p, size_t size)
     min = (struct liballoc_minor *) ((uintptr_t) ptr - sizeof(struct liballoc_minor));
 
     if (min->magic != LIBALLOC_MAGIC) {
-        l_errorCount += 1;
+        l_error_count += 1;
         if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
             ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
             ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
-            l_possibleOverruns += 1;
+            l_possible_overruns += 1;
         }
 
         liballoc_unlock();
@@ -449,9 +746,9 @@ void *PREFIX(realloc)(void *p, size_t size)
 
     liballoc_unlock();
 
-    ptr = PREFIX(malloc)(size);
+    ptr = umalloc(size);
     liballoc_memcpy(ptr, p, real_size);
-    PREFIX(free)(p);
+    ufree(p);
 
     return ptr;
 }
\ No newline at end of file
diff --git a/src/kernel/lib/stdlib/liballoc.h b/src/kernel/lib/stdlib/liballoc.h
index 6ed9efb..37a1624 100644
--- a/src/kernel/lib/stdlib/liballoc.h
+++ b/src/kernel/lib/stdlib/liballoc.h
@@ -3,8 +3,6 @@
 
 #include <stddef.h>
 
-#define PREFIX(func) k ## func
-
 int liballoc_lock();
 
 int liballoc_unlock();
@@ -13,12 +11,20 @@ void *liballoc_alloc(size_t);
 
 int liballoc_free(void *, size_t);
 
-void *PREFIX(malloc)(size_t);
+void *kmalloc(size_t);
+
+void *krealloc(void *, size_t);
+
+void *kcalloc(size_t, size_t);
+
+void kfree(void *);
+
+void *umalloc(size_t);
 
-void *PREFIX(realloc)(void *, size_t);
+void *urealloc(void *, size_t);
 
-void *PREFIX(calloc)(size_t, size_t);
+void *ucalloc(size_t, size_t);
 
-void PREFIX(free)(void *);
+void ufree(void *);
 
 #endif