3 files changed, 112 insertions, 3 deletions

diff --git a/lib/src/alloc.c b/lib/src/alloc.c
new file mode 100644
index 0000000..8b05d9e
--- /dev/null
+++ b/lib/src/alloc.c
@@ -0,0 +1,87 @@
+// Copyright (c) 2021 Johannes Stoelp
+
+#include <alloc.h>
+#include <common.h>
+
+#include <stdint.h>
+
+// Extremely simple and non-thread safe implementation of a dynamic
+// memory allocator. Which will greatly suffer under fragmentation as
+// we neither use splitting nor coalesce free blocks. It uses
+// first-fit and always traverses the block list from the beginning.
+//
+// Bottom line, this allocator can be optimized in so many ways but it
+// doesn't really matter for the purpose of this studies and therefore
+// the allocator is implemented in the most naive way.
+
+// Allocation block descriptor.
+struct BlockDescriptor {
+    unsigned mFree;
+    unsigned mSize;
+    struct BlockDescriptor* mNext;
+};
+
+// Global Allocator.
+
+// Size of available memory to the allocator.
+enum { MEMORY_SIZE = 1 * 1024 * 1024 };
+// Memory for the allocator (statically reserved in the `.bss` section).
+uint8_t gMemory[MEMORY_SIZE];
+
+// Top index into `gMemory` to indicate next free memory.
+unsigned gMemoryTop;
+
+// List of allocated blocks (free + used).
+struct BlockDescriptor* gHead;
+
+// Request free memory from `gMemory` and advance the `gMemoryTop` index.
+static void* brk(unsigned size) {
+    ERROR_ON(gMemoryTop + size >= MEMORY_SIZE, "Allocator OOM!");
+    const unsigned old_top = gMemoryTop;
+    gMemoryTop += size;
+    return (void*)(gMemory + old_top);
+}
+
+// Allocate memory chunk of `size` and return pointer to the chunk.
+void* alloc(unsigned size) {
+    struct BlockDescriptor* current = 0;
+
+    // Check if we have a free block in the list of allocated blocks
+    // that matches the requested size.
+    current = gHead;
+    while (current) {
+        if (current->mFree && current->mSize < size) {
+            current->mFree = 0;
+            return (void*)(current + 1);
+        };
+        current = current->mNext;
+    }
+
+    // Compute real allocation size: Payload + BlockDescriptor.
+    unsigned real_size = size + sizeof(struct BlockDescriptor);
+
+    // No free block found in the list of blocks, allocate new block.
+    current = brk(real_size);
+
+    // Initialize new block.
+    current->mFree = 0;
+    current->mSize = size;
+    current->mNext = 0;
+
+    // Insert new block at the beginning of the list of blocks.
+    if (gHead != 0) {
+        current->mNext = gHead;
+    }
+    gHead = current;
+
+    return (void*)(current + 1);
+}
+
+void dealloc(void* ptr) {
+    // Get descriptor block.
+    struct BlockDescriptor* current = (struct BlockDescriptor*)ptr - 1;
+
+    // Mark block as free.
+    ERROR_ON(current->mFree, "Tried to de-alloc free block!");
+    current->mFree = 1;
+}
diff --git a/lib/src/fmt.c b/lib/src/fmt.c
index be1ca3a..b0840de 100644
--- a/lib/src/fmt.c
+++ b/lib/src/fmt.c
@@ -11,7 +11,7 @@ static const char* num2dec(char* buf, unsigned long len, unsigned long long num)
     }
 
     while (num > 0 && pbuf != buf) {
-        char d = (num % 10) + '0';
+      char d = (char)(num % 10) + '0';
         *(--pbuf) = d;
         num /= 10;
     }
@@ -28,7 +28,7 @@ static const char* num2hex(char* buf, unsigned long len, unsigned long long num)
 
     while (num > 0 && pbuf != buf) {
         char d = (num & 0xf);
-        *(--pbuf) = d + (d > 9 ? 'a' - 10 : '0');
+        *(--pbuf) = (char)(d + (d > 9 ? 'a' - 10 : '0'));
         num >>= 4;
     }
     return pbuf;
@@ -73,7 +73,7 @@ int vfmt(char* buf, unsigned long len, const char* fmt, va_list ap) {
                     val *= -1;
                     put('-');
                 }
-                const char* ptr = num2dec(scratch, sizeof(scratch), val);
+                const char* ptr = num2dec(scratch, sizeof(scratch), (unsigned long)val);
                 puts(ptr);
             } break;
             case 'x': {
diff --git a/lib/src/syscalls.c b/lib/src/syscalls.c
new file mode 100644
index 0000000..d6ac1a5
--- /dev/null
+++ b/lib/src/syscalls.c
@@ -0,0 +1,22 @@
+// Copyright (c) 2021 Johannes Stoelp
+
+#include <asm/unistd.h>  // __NR_*
+#include <syscall.h>
+#include <syscalls.h>
+
+int open(const char* path, int flags) {
+    return syscall2(__NR_open, path, flags);
+}
+
+ssize_t read(int fd, void* buf, size_t count) {
+    return syscall3(__NR_read, fd, buf, count);
+}
+
+off_t lseek(int fd, off_t offset, int whence) {
+    return syscall3(__NR_lseek, fd, offset, whence);
+}
+
+void _exit(int status) {
+    syscall1(__NR_exit, status);
+    __builtin_unreachable();
+}