1 files changed, 147 insertions, 0 deletions
diff --git a/libraries/euler/allocator.cpp b/libraries/euler/allocator.cpp
new file mode 100644
index 0000000..5242df1
--- /dev/null
+++ b/libraries/euler/allocator.cpp
@@ -0,0 +1,147 @@
+#include <euler/syscall.hpp>
+
+//i guess we could figure out which parts of the pages the kernel allocated to
+//load the application were not actually needed and add those to the memory
+//that is available to be allocated, but whatever.
+
+namespace euler::allocator {
+
+  struct block_info {
+    //vaddr, divisible by size
+    uint64_t start;
+    //power of 2, 0 for unused
+    uint64_t size;
+  };
+
+  struct block_info_page {
+    block_info infos[255];
+    block_info_page *next;
+  };
+
+  static_assert(sizeof(block_info_page) == 4088);
+
+  static block_info_page *first_bi_page = 0;
+
+  static block_info *try_find_block(uint64_t start, uint64_t size) {
+    for (block_info_page *bip = first_bi_page; bip; bip = bip->next)
+      for (int i = 0; i < 255; ++i)
+        if (bip->infos[i].start == start && bip->infos[i].size == size)
+          return bip->infos + i;
+    return 0;
+  }
+
+  static block_info *add_block(uint64_t start, uint64_t size) {
+    for (block_info_page *bip = first_bi_page; bip; bip = bip->next)
+      for (int i = 0; i < 255; ++i)
+        if (bip->infos[i].size == 0) {
+          bip->infos[i].start = start;
+          bip->infos[i].size = size;
+          return bip->infos + i;
+        }
+    block_info_page *new_bip = (block_info_page *)_syscall_get_new_pages(1);
+    new_bip->infos[0].start = start;
+    new_bip->infos[0].size = size;
+    for (int i = 1; i < 255; ++i)
+      new_bip->infos[i].size = 0;
+    new_bip->next = first_bi_page;
+    first_bi_page = new_bip;
+    return new_bip->infos;
+  }
+
+  static block_info *find_minimal_block(uint64_t minimum_length) {
+    block_info *minimal_so_far = 0;
+    uint64_t length_so_far = UINT64_MAX;
+    for (block_info_page *bip = first_bi_page; bip; bip = bip->next)
+      for (int i = 0; i < 255; ++i)
+        if (bip->infos[i].size == minimum_length)
+          return bip->infos + i;
+        else if (
+          bip->infos[i].size > minimum_length &&
+          bip->infos[i].size < length_so_far
+        ) {
+          minimal_so_far = bip->infos + i;
+          length_so_far = bip->infos[i].size;
+        }
+    if (minimal_so_far != 0)
+      return minimal_so_far;
+    uint64_t pages_needed = (minimum_length - 1) / 4096 + 1;
+    void *block_start = _syscall_get_new_pages(pages_needed);
+    return add_block((uint64_t)block_start, pages_needed * 4096);
+  }
+
+  static void deallocate_aligned(uint64_t start, uint64_t length) {
+    block_info *buddy = try_find_block(start ^ length, length);
+    if (buddy) {
+      buddy->size = 0;
+      deallocate_aligned(start & ~length, length * 2);
+      return;
+    }
+    add_block(start, length);
+  }
+
+  static void deallocate(void *start, uint64_t length) {
+    uint64_t at = (uint64_t)start;
+    uint64_t left = length;
+    uint64_t i;
+    for (i = 1; i <= left; i *= 2)
+      if (at & i) {
+        deallocate_aligned(at, i);
+        at += i;
+        left -= i;
+      }
+    for (i /= 2; left > 0; i /= 2)
+      if (i <= left) {
+        deallocate_aligned(at, i);
+        at += i;
+        left -= i;
+      }
+  }
+
+  [[nodiscard]] static void *allocate(uint64_t length) {
+    block_info *bi = find_minimal_block(length);
+    void *to_return = (void *)bi->start;
+    void *new_start = (void *)(bi->start + length);
+    uint64_t new_length = bi->size - length;
+    bi->size = 0;
+    deallocate(new_start, new_length);
+    return to_return;
+  }
+
+  static void deallocate_with_length(void *start) {
+    uint64_t real_start = (uint64_t)start - 8;
+    deallocate((void *)real_start, *(uint64_t *)real_start);
+  }
+
+  [[nodiscard]] static void *allocate_with_length(uint64_t length) {
+    uint64_t *real_start = (uint64_t *)allocate(length + 8);
+    *real_start = length + 8;
+    return real_start + 1;
+  }
+
+}
+
+using namespace euler::allocator;
+
+void operator delete[](void *start) {
+  deallocate_with_length(start);
+}
+
+void operator delete(void *start) {
+  deallocate_with_length(start);
+}
+
+void operator delete[](void *start, uint64_t) {
+  deallocate_with_length(start);
+}
+
+void operator delete(void *start, uint64_t) {
+  deallocate_with_length(start);
+}
+
+void *operator new[](uint64_t size) {
+  return allocate_with_length(size);
+}
+
+void *operator new(uint64_t size) {
+  return allocate_with_length(size);
+}