Added userspace libc and began userspace based shell

6 files changed, 603 insertions, 0 deletions

diff --git a/src/kernel/lib/stdlib/atoi.c b/src/kernel/lib/stdlib/atoi.c
new file mode 100644
index 0000000..4044972
--- /dev/null
+++ b/src/kernel/lib/stdlib/atoi.c
@@ -0,0 +1,24 @@
+#include <kernel/lib/math.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <kernel/lib/string.h>
+
+int atoi(char *str)
+{
+    size_t s_str = strlen(str);
+    if (!s_str) return 0;
+
+    uint8_t negative = 0;
+    if (str[0] == '-') negative = 1;
+
+    size_t i = 0;
+    if (negative) i++;
+
+    int ret = 0;
+    for (; i < s_str; i++) {
+        ret += (str[i] - '0') * pow(10, (s_str - i) - 1);
+    }
+
+    if (negative) ret *= -1;
+    return ret;
+}
\ No newline at end of file
diff --git a/src/kernel/lib/stdlib/htoa.c b/src/kernel/lib/stdlib/htoa.c
new file mode 100644
index 0000000..85bd750
--- /dev/null
+++ b/src/kernel/lib/stdlib/htoa.c
@@ -0,0 +1,30 @@
+#include <stdint.h>
+#include <kernel/lib/string.h>
+#include <kernel/lib/stdlib.h>
+
+static const char __HTOA_TABLE[] = "0123456789ABCDEF";
+
+char *htoa(uint32_t n)
+{
+    char *ret = kmalloc(10);
+
+    int i = 0;
+    while (n) {
+        ret[i++] = __HTOA_TABLE[n & 0xF];
+        n >>= 4;
+    }
+
+    if (!i) {
+        ret[0] = '0';
+        i++;
+    }
+
+    for (; i <= 9; i++) ret[i] = 0;
+
+    char *aux = strdup(ret);
+    kfree(ret);
+    ret = aux;
+
+    strinv(ret);
+    return ret;
+}
\ No newline at end of file
diff --git a/src/kernel/lib/stdlib/htoi.c b/src/kernel/lib/stdlib/htoi.c
new file mode 100644
index 0000000..f2d4702
--- /dev/null
+++ b/src/kernel/lib/stdlib/htoi.c
@@ -0,0 +1,23 @@
+#include <kernel/lib/math.h>
+#include <stddef.h>
+#include <kernel/lib/string.h>
+
+int htoi(char *str)
+{
+    size_t s_str = strlen(str);
+
+    size_t i = 0;
+    int ret = 0;
+    for (; i < s_str; i++) {
+        char c = str[i];
+        int aux = 0;
+        if (c >= '0' && c <= '9')
+            aux = c - '0';
+        else if (c >= 'A' && c <= 'F')
+            aux = (c - 'A') + 10;
+
+        ret += aux * pow(16, (s_str - i) - 1);
+    }
+
+    return ret;
+}
\ No newline at end of file
diff --git a/src/kernel/lib/stdlib/itoa.c b/src/kernel/lib/stdlib/itoa.c
new file mode 100644
index 0000000..897fd55
--- /dev/null
+++ b/src/kernel/lib/stdlib/itoa.c
@@ -0,0 +1,45 @@
+#include <kernel/lib/math.h>
+#include <stdint.h>
+#include <kernel/lib/string.h>
+#include <kernel/lib/stdlib.h>
+#include <kernel/paging/paging.h>
+
+static const char __ITOA_TABLE[] = "0123456789";
+
+char *itoa(int n)
+{
+    if (paging_enabled == 0)
+        return "0"; // kmalloc isn't available
+
+    if (!n) {
+        char *ret = kmalloc(2);
+        ret[0] = '0';
+        ret[1] = 0;
+        return ret;
+    }
+    uint8_t negative = (uint8_t) (n < 0);
+    if (negative) n *= -1;
+
+    int sz;
+    for (sz = 0; n % pow(10, sz) != n; sz++) {}
+
+    char *ret = kmalloc(sz + 1);
+
+    for (int i = 0; i < sz; i++) {
+        int digit = (n % pow(10, i + 1)) / pow(10, i);
+        ret[i] = __ITOA_TABLE[digit];
+    }
+    ret[sz] = 0;
+
+    if (negative) {
+        char *aux = kmalloc(sz + 2);
+        strcpy(aux, ret);
+        aux[sz] = '-';
+        aux[sz + 1] = 0;
+        kfree(ret);
+        ret = aux;
+    }
+
+    strinv(ret);
+    return ret;
+}
\ No newline at end of file
diff --git a/src/kernel/lib/stdlib/liballoc.c b/src/kernel/lib/stdlib/liballoc.c
new file mode 100644
index 0000000..41c55e1
--- /dev/null
+++ b/src/kernel/lib/stdlib/liballoc.c
@@ -0,0 +1,457 @@
+#include <stddef.h>
+#include <stdint.h>
+#include <kernel/paging/paging.h>
+#include <kernel/lib/stdlib/liballoc.h>
+
+int liballoc_lock()
+{
+    // asm ("cli");
+    return 0;
+}
+
+int liballoc_unlock()
+{
+    // asm ("sti");
+    return 0;
+}
+
+void *liballoc_alloc(size_t p)
+{
+    uint32_t ptr = paging_alloc_pages((uint32_t) p);
+    return (void *) ptr;
+}
+
+int liballoc_free(void *ptr, size_t p)
+{
+    paging_set_free((uint32_t) ptr, (uint32_t) p);
+    return 0;
+}
+
+#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 ) { \
+            uintptr_t diff; \
+            ptr = (void*) ((uintptr_t) ptr + ALIGN_INFO); \
+            diff = (uintptr_t) ptr & (ALIGNMENT - 1); \
+            if (diff != 0) { \
+                diff = ALIGNMENT - diff; \
+                ptr = (void*) ((uintptr_t) ptr + diff); \
+            } \
+            *((ALIGN_TYPE*) ((uintptr_t) ptr - ALIGN_INFO)) = diff + ALIGN_INFO; \
+        }
+
+#define UNALIGN(ptr) \
+        if (ALIGNMENT > 1) { \
+            uintptr_t diff = *((ALIGN_TYPE*) ((uintptr_t) ptr - ALIGN_INFO)); \
+            if (diff < (ALIGNMENT + ALIGN_INFO)) { \
+                ptr = (void*) ((uintptr_t) ptr - diff); \
+            } \
+        }
+
+#define LIBALLOC_MAGIC 0x900df00d
+#define LIBALLOC_DEAD 0xbaadf00d
+
+struct liballoc_major {
+    struct liballoc_major *prev;
+    struct liballoc_major *next;
+    unsigned int pages;
+    unsigned int size;
+    unsigned int usage;
+    struct liballoc_minor *first;
+};
+
+struct liballoc_minor {
+    struct liballoc_minor *prev;
+    struct liballoc_minor *next;
+    struct liballoc_major *block;
+    unsigned int magic;
+    unsigned int size;
+    unsigned int req_size;
+};
+
+static struct liballoc_major *l_memRoot = NULL;
+static struct liballoc_major *l_bestBet = 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 void *liballoc_memset(void *s, int c, size_t n)
+{
+    unsigned int i;
+    for (i = 0; i < n; i++)
+        ((char *) s)[i] = c;
+
+    return s;
+}
+
+static void *liballoc_memcpy(void *s1, const void *s2, size_t n)
+{
+    char *cdest;
+    char *csrc;
+    unsigned int *ldest = (unsigned int *) s1;
+    unsigned int *lsrc = (unsigned int *) s2;
+
+    while (n >= sizeof(unsigned int)) {
+        *ldest++ = *lsrc++;
+        n -= sizeof(unsigned int);
+    }
+
+    cdest = (char *) ldest;
+    csrc = (char *) lsrc;
+
+    while (n > 0) {
+        *cdest++ = *csrc++;
+        n -= 1;
+    }
+    return s1;
+}
+
+static struct liballoc_major *allocate_new_page(unsigned int size)
+{
+    unsigned int st;
+    struct liballoc_major *maj;
+
+    st = size + sizeof(struct liballoc_major);
+    st += sizeof(struct liballoc_minor);
+
+    if ((st % l_pageSize) == 0)
+        st = st / (l_pageSize);
+    else
+        st = st / (l_pageSize) + 1;
+
+    if (st < l_pageCount) st = l_pageCount;
+
+    maj = (struct liballoc_major *) liballoc_alloc(st);
+
+    if (maj == NULL) {
+        l_warningCount += 1;
+        return NULL;
+    }
+
+    maj->prev = NULL;
+    maj->next = NULL;
+    maj->pages = st;
+    maj->size = st * l_pageSize;
+    maj->usage = sizeof(struct liballoc_major);
+    maj->first = NULL;
+
+    l_allocated += maj->size;
+
+    return maj;
+}
+
+void *PREFIX(malloc)(size_t req_size)
+{
+    int startedBet = 0;
+    unsigned long long bestSize = 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_warningCount += 1;
+        liballoc_unlock();
+        return PREFIX(malloc)(1);
+    }
+
+    if (l_memRoot == NULL) {
+        l_memRoot = allocate_new_page(size);
+        if (l_memRoot == NULL) {
+            liballoc_unlock();
+            return NULL;
+        }
+    }
+
+    maj = l_memRoot;
+    startedBet = 0;
+
+    if (l_bestBet != NULL) {
+        bestSize = l_bestBet->size - l_bestBet->usage;
+
+        if (bestSize > (size + sizeof(struct liballoc_minor))) {
+            maj = l_bestBet;
+            startedBet = 1;
+        }
+    }
+
+    while (maj != NULL) {
+        diff = maj->size - maj->usage;
+        if (bestSize < diff) {
+            l_bestBet = maj;
+            bestSize = diff;
+        }
+
+#ifdef USE_CASE1
+        if (diff < (size + sizeof(struct liballoc_minor))) {
+            if (maj->next != NULL) {
+                maj = maj->next;
+                continue;
+            }
+
+            if (startedBet == 1) {
+                maj = l_memRoot;
+                startedBet = 0;
+                continue;
+            }
+
+            maj->next = allocate_new_page(size);
+            if (maj->next == NULL) break;
+            maj->next->prev = maj;
+            maj = maj->next;
+        }
+#endif
+
+#ifdef USE_CASE2
+        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;
+        }
+#endif
+
+#ifdef USE_CASE3
+        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;
+        }
+#endif
+
+#ifdef USE_CASE4
+        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;
+        }
+#endif
+
+#ifdef USE_CASE5
+        if (maj->next == NULL) {
+            if (startedBet == 1) {
+                maj = l_memRoot;
+                startedBet = 0;
+                continue;
+            }
+            maj->next = allocate_new_page(size);
+            if (maj->next == NULL) break;
+            maj->next->prev = maj;
+        }
+#endif
+        maj = maj->next;
+    }
+
+    liballoc_unlock();
+
+    return NULL;
+}
+
+void PREFIX(free)(void *ptr)
+{
+    struct liballoc_minor *min;
+    struct liballoc_major *maj;
+
+    if (ptr == NULL) {
+        l_warningCount += 1;
+        return;
+    }
+
+    UNALIGN(ptr);
+    liballoc_lock();
+
+    min = (struct liballoc_minor *) ((uintptr_t) ptr - sizeof(struct liballoc_minor));
+
+    if (min->magic != LIBALLOC_MAGIC) {
+        l_errorCount += 1;
+
+        if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
+            ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
+            ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
+            l_possibleOverruns += 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_memRoot == maj) l_memRoot = maj->next;
+        if (l_bestBet == maj) l_bestBet = 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;
+            int majSize = maj->size - maj->usage;
+            if (majSize > bestSize) l_bestBet = maj;
+        }
+    }
+    liballoc_unlock();
+}
+
+void *PREFIX(calloc)(size_t nobj, size_t size)
+{
+    int real_size;
+    void *p;
+
+    real_size = nobj * size;
+
+    p = PREFIX(malloc)(real_size);
+
+    liballoc_memset(p, 0, real_size);
+
+    return p;
+}
+
+void *PREFIX(realloc)(void *p, size_t size)
+{
+    void *ptr;
+    struct liballoc_minor *min;
+    unsigned int real_size;
+
+    if (size == 0) {
+        PREFIX(free)(p);
+        return NULL;
+    }
+
+    if (p == NULL) return PREFIX(malloc)(size);
+
+    ptr = p;
+    UNALIGN(ptr);
+    liballoc_lock();
+    min = (struct liballoc_minor *) ((uintptr_t) ptr - sizeof(struct liballoc_minor));
+
+    if (min->magic != LIBALLOC_MAGIC) {
+        l_errorCount += 1;
+        if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
+            ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
+            ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
+            l_possibleOverruns += 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 = PREFIX(malloc)(size);
+    liballoc_memcpy(ptr, p, real_size);
+    PREFIX(free)(p);
+
+    return ptr;
+}
diff --git a/src/kernel/lib/stdlib/liballoc.h b/src/kernel/lib/stdlib/liballoc.h
new file mode 100644
index 0000000..6ed9efb
--- /dev/null
+++ b/src/kernel/lib/stdlib/liballoc.h
@@ -0,0 +1,24 @@
+#ifndef MELVIX_ALLOC_H
+#define MELVIX_ALLOC_H
+
+#include <stddef.h>
+
+#define PREFIX(func) k ## func
+
+int liballoc_lock();
+
+int liballoc_unlock();
+
+void *liballoc_alloc(size_t);
+
+int liballoc_free(void *, size_t);
+
+void *PREFIX(malloc)(size_t);
+
+void *PREFIX(realloc)(void *, size_t);
+
+void *PREFIX(calloc)(size_t, size_t);
+
+void PREFIX(free)(void *);
+
+#endif