Add allocator

6 files changed, 159 insertions, 9 deletions

diff --git a/libk/stdlib/memory.cc b/libk/stdlib/memory.cc
index c197519..b5c8f6d 100644
--- a/libk/stdlib/memory.cc
+++ b/libk/stdlib/memory.cc
@@ -1,10 +1,5 @@
 #include <stdlib.h>
 
-void operator delete(void*) {
-  printk("Calling delete\n");
-  abort();
-}
-
 extern "C" void __cxa_pure_virtual() {
   printk("__cxa_pure_virtual\n");
   abort();
diff --git a/src/allocator.cc b/src/allocator.cc
new file mode 100644
index 0000000..77736cc
--- /dev/null
+++ b/src/allocator.cc
@@ -0,0 +1,90 @@
+#include "allocator.h"
+
+static MemoryAllocator* mem_alloc = nullptr;
+
+MemoryAllocator::MemoryAllocator(uint32_t start, size_t size) {
+  if (size < sizeof(MemoryChunk)) {
+    begin = nullptr;
+    return;
+  }
+  begin = new (reinterpret_cast<void*>(start)) MemoryChunk{.size = static_cast<size_t>(size - sizeof(MemoryChunk))};
+  if (mem_alloc == nullptr) mem_alloc = this;
+}
+
+void* MemoryAllocator::malloc(size_t size) {
+  // TODO spinlock
+  // TODO memset 0 over allocated memory
+  MemoryChunk* result = nullptr;
+
+  // find the first chunk that is at least size and not allocated
+  for (auto* iter = begin; iter != nullptr; iter = iter->next) {
+    if (iter->size >= size && !iter->allocated) {
+      result = iter;
+
+      // split chunk if there is at least one byte left over
+      if (result->size >= size + sizeof(MemoryChunk) + 1) {
+        auto* _new = new (result + sizeof(MemoryChunk) + size) MemoryChunk{
+            .prev = result, .next = result->next, .size = static_cast<size_t>(result->size - sizeof(MemoryChunk))};
+        result->next = _new;
+      }
+
+      break;
+    }
+  }
+
+  return result + sizeof(MemoryChunk);
+}
+void MemoryAllocator::free(void* ptr) {
+  auto* chunk = reinterpret_cast<MemoryChunk*>(reinterpret_cast<uint32_t>(ptr) - sizeof(MemoryChunk));
+  chunk->allocated = false;
+
+  // merge in next chunk
+  if (chunk->next != nullptr && !chunk->next->allocated) {
+    chunk->size += chunk->next->size + sizeof(MemoryChunk);
+    chunk->next = chunk->next->next;
+    if (chunk->next != nullptr) chunk->next->prev = chunk;
+  }
+
+  // merge into previous chunk
+  if (chunk->prev != nullptr && !chunk->prev->allocated) {
+    chunk->prev->size += chunk->size + sizeof(MemoryChunk);
+    chunk->prev->next = chunk->next;
+    if (chunk->next != nullptr) chunk->next->prev = chunk->prev;
+  }
+};
+
+size_t MemoryAllocator::free_space() const {
+  size_t r = 0;
+  for (auto* iter = begin; iter != nullptr; iter = iter->next)
+    if (!iter->allocated) r += iter->size;
+  return r;
+}
+size_t MemoryAllocator::used_space() const {
+  size_t r = 0;
+  for (auto* iter = begin; iter != nullptr; iter = iter->next)
+    if (iter->allocated) r += iter->size;
+  return r;
+}
+
+void* operator new(unsigned sz, const std::nothrow_t&) noexcept {
+  if (mem_alloc == nullptr) return nullptr;
+  return mem_alloc->malloc(sz);
+}
+void* operator new[](unsigned sz, const std::nothrow_t&) noexcept {
+  if (mem_alloc == nullptr) return nullptr;
+  return mem_alloc->malloc(sz);
+}
+
+void operator delete(void* ptr) {
+  if (mem_alloc != nullptr) mem_alloc->free(ptr);
+}
+void operator delete[](void* ptr) {
+  if (mem_alloc != nullptr) mem_alloc->free(ptr);
+}
+
+void* operator new(unsigned /* size_bytes */, void* ptr) {
+  return ptr;
+}
+void* operator new[](unsigned /* size_bytes */, void* ptr) {
+  return ptr;
+}
diff --git a/src/allocator.h b/src/allocator.h
new file mode 100644
index 0000000..8a12be8
--- /dev/null
+++ b/src/allocator.h
@@ -0,0 +1,39 @@
+#pragma once
+
+#include <types.h>
+
+class MemoryAllocator {
+public:
+  MemoryAllocator(uint32_t start, size_t size);
+
+  void* malloc(size_t size);
+  void free(void* ptr);
+
+  size_t free_space() const;
+  size_t used_space() const;
+
+private:
+  struct MemoryChunk {
+    MemoryChunk* prev = nullptr;
+    MemoryChunk* next = nullptr;
+    bool allocated = false;
+    size_t size = 0;
+  };
+  MemoryChunk* begin;
+};
+
+namespace std {
+struct nothrow_t {
+  explicit nothrow_t() = default;
+};
+};  // namespace std
+
+void* operator new(unsigned, const std::nothrow_t&) noexcept;
+void* operator new[](unsigned, const std::nothrow_t&) noexcept;
+
+void operator delete(void* ptr);
+void operator delete[](void* ptr);
+
+// placement new
+void* operator new(unsigned, void*);
+void* operator new[](unsigned, void*);
diff --git a/src/kernel.cc b/src/kernel.cc
index 3110419..05e0daf 100644
--- a/src/kernel.cc
+++ b/src/kernel.cc
@@ -10,6 +10,7 @@
 
 #include <stdlib.h>
 #include <types.h>
+#include "allocator.h"
 #include "cga.h"
 #include "cpu/cpu.h"
 #include "gdt.h"
@@ -23,12 +24,15 @@
 vmm kvmm;
 #include "hardware.h"
 
+char buffer[4096];
+
+uint32_t check_multiboot(uint32_t, uint32_t);
+
 extern "C" {
 void dump_multiboot(uint32_t mb_magic, uint32_t mb_addr);
 void dump_gdt();
 
-void kernel_main([[maybe_unused]] uint32_t mb_magic, [[maybe_unused]] uint32_t mb_addr) {
-
+void kernel_main(uint32_t mb_magic, uint32_t mb_addr) {
 #ifdef HAS_SERIAL0
   if constexpr (serial0_console)
     if (serial0.self_check()) Console::set(&serial0);
@@ -52,8 +56,16 @@ void kernel_main([[maybe_unused]] uint32_t mb_magic, [[maybe_unused]] uint32_t m
   // dump_gdt();
   //
 
-  if (const auto mb_addr_r = kvmm.map(mb_addr, 0xc03fe000)) {
+  {
+    const auto mb_addr_r = kvmm.map(mb_addr, 0xc03fe000);
+    runtime_assert(mb_addr_r, "Failed to map mb_addr");
+
     mb_addr = mb_addr_r.value();
+    const auto mb_size = check_multiboot(mb_magic, mb_addr);
+    runtime_assert((mb_size != 0), "Invalid multiboot header");
+
+    printk("Multiboot2 header at ", uhex{mb_addr}, " size: ", mb_size, '\n');
+
     // dump_multiboot(mb_magic, mb_addr);
   }
 
@@ -62,6 +74,9 @@ void kernel_main([[maybe_unused]] uint32_t mb_magic, [[maybe_unused]] uint32_t m
   // Scheduler s{gdt.descriptor(GDT::kcode)};
   Keyboard kb;
 
+  MemoryAllocator ma(reinterpret_cast<uint32_t>(buffer), sizeof(buffer));
+  printk("memory free: ", ma.free_space(), '\n');
+
   idt.enable();
 
   while (true) asm volatile("hlt");
diff --git a/src/kernel/multiboot.cc b/src/kernel/multiboot.cc
new file mode 100644
index 0000000..024916e
--- /dev/null
+++ b/src/kernel/multiboot.cc
@@ -0,0 +1,10 @@
+#include <multiboot2.h>
+#include <types.h>
+
+uint32_t check_multiboot(uint32_t mb_magic, uint32_t mb_addr) {
+  if (mb_magic != MULTIBOOT2_BOOTLOADER_MAGIC) return 0;
+  if (mb_addr & 7) return 0;
+
+  const uint32_t size = *reinterpret_cast<uint32_t*>(mb_addr);
+  return size;
+}
diff --git a/src/makefile b/src/makefile
index 68ec6d6..6e8545d 100644
--- a/src/makefile
+++ b/src/makefile
@@ -2,13 +2,14 @@ AS_OBJ += src/boot.o \
 	  src/idt/stubs.o
 
 CXX_OBJ += src/kernel.o \
-	   src/kernel/dump_gdt.o src/kernel/dump_multiboot.o \
+	   src/kernel/dump_gdt.o src/kernel/dump_multiboot.o src/kernel/multiboot.o \
 	   src/cpu/cpu.o \
 	   src/gdt.o \
 	   src/gdt/segmentdescriptor.o \
 	   src/idt.o \
 	   src/idt/exception.o src/idt/interruptgate.o src/idt/interrupthandler.o \
 	   src/vmm.o \
+	   src/allocator.o \
 	   src/scheduler.o src/scheduler/task.o
 
 src/cpu/irq.h: $(OBJ_DIR)/src/idt/stubs.o