aboutsummaryrefslogtreecommitdiff
path: root/src/kernel/lib/stdlib/liballoc.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/kernel/lib/stdlib/liballoc.c')
-rw-r--r--src/kernel/lib/stdlib/liballoc.c431
1 files changed, 364 insertions, 67 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