Move MemoryAllocator to libk

3 files changed, 130 insertions, 0 deletions

diff --git a/libk/makefile b/libk/makefile
index f3b9aeb..eafa98c 100644
--- a/libk/makefile
+++ b/libk/makefile
@@ -1,4 +1,5 @@
 CXX_OBJ = string/integerview.o string/memory.o \
+	  memory/allocator.o \
 	  stdlib/abort.o stdlib/console.o stdlib/virtual.o
 CXX_OBJ := $(addprefix $(OBJ_DIR)/, $(CXX_OBJ))
 CXX_DEP = $(CXX_OBJ:%.o=%.d)
diff --git a/libk/memory.h b/libk/memory.h
new file mode 100644
index 0000000..a01252c
--- /dev/null
+++ b/libk/memory.h
@@ -0,0 +1,39 @@
+#pragma once
+
+#include <types.h>
+
+class MemoryAllocator {
+public:
+  MemoryAllocator(uint32_t start, size_t size);
+
+  void* allocate(size_t size);
+  void deallocate(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/libk/memory/allocator.cc b/libk/memory/allocator.cc
new file mode 100644
index 0000000..351646f
--- /dev/null
+++ b/libk/memory/allocator.cc
@@ -0,0 +1,90 @@
+#include <memory.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::allocate(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::deallocate(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->allocate(sz);
+}
+void* operator new[](unsigned sz, const std::nothrow_t&) noexcept {
+  if (mem_alloc == nullptr) return nullptr;
+  return mem_alloc->allocate(sz);
+}
+
+void operator delete(void* ptr) {
+  if (mem_alloc != nullptr) mem_alloc->deallocate(ptr);
+}
+void operator delete[](void* ptr) {
+  if (mem_alloc != nullptr) mem_alloc->deallocate(ptr);
+}
+
+void* operator new(unsigned /* size_bytes */, void* ptr) {
+  return ptr;
+}
+void* operator new[](unsigned /* size_bytes */, void* ptr) {
+  return ptr;
+}