wip allocating heap memory in user mode

9 files changed, 136 insertions, 22 deletions

diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt
index 3d6d2c7..0a6ab9c 100644
--- a/arch/x86_64/CMakeLists.txt
+++ b/arch/x86_64/CMakeLists.txt
@@ -64,6 +64,7 @@ target_sources("_memory" PRIVATE
   "src/memory/paging/active_page_table.cpp"
   "src/memory/paging/inactive_page_table.cpp"
   "src/memory/heap/bump_allocator.cpp"
+  "src/memory/heap/user_heap_allocator.cpp"
   "src/memory/heap/memory_block.cpp"
   "src/memory/heap/linked_list_allocator.cpp"
   "src/memory/heap/global_heap_allocator.cpp"
diff --git a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp
index bfc7b67..d0d1080 100644
--- a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp
@@ -2,6 +2,7 @@
 #define TEACHOS_ARCH_X86_64_MEMORY_HEAP_GLOBAL_HEAP_ALLOCATOR_HPP
 
 #include "arch/memory/heap/heap_allocator.hpp"
+#include "arch/memory/heap/user_heap_allocator.hpp"
 
 namespace teachos::arch::memory::heap
 {
@@ -76,7 +77,8 @@ namespace teachos::arch::memory::heap
 
   private:
     static heap_allocator * kernel_allocator_instance;  ///< Instance used to allocate and deallocate kernel heap memory
-    static heap_allocator * user_allocator_instance;    ///< Instance used to allocate and deallocate user heap memory
+    static user_heap_allocator *
+        user_allocator_instance;  ///< Instance used to allocate and deallocate user heap memory
 
     /**
      * @brief Either returns the previously registered heap allocated or halts further execution
@@ -90,7 +92,8 @@ namespace teachos::arch::memory::heap
      *
      * @return Reference to the registered user heap allocation
      */
-    static auto user() -> heap_allocator &;
+    [[gnu::section(".user_text")]]
+    static auto user() -> user_heap_allocator &;
   };
 }  // namespace teachos::arch::memory::heap
 
diff --git a/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp
new file mode 100644
index 0000000..1dab047
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp
@@ -0,0 +1,48 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_USER_HEAP_ALLOCATOR_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_USER_HEAP_ALLOCATOR_HPP
+
+#include "arch/memory/heap/heap_allocator.hpp"
+
+#include <atomic>
+#include <cstdint>
+
+namespace teachos::arch::memory::heap
+{
+  /**
+   * @brief Simple heap allocator, which allocates linearly and leaks all allocated memory, because it does not really
+   * deallocate anything.
+   */
+  struct user_heap_allocator
+  {
+    /**
+     * @brief Constructor.
+     *
+     * @param heap_start Start of the allocatable heap area
+     * @param heap_end End of the allocatable heap area (Start + Size)
+     */
+    user_heap_allocator(std::size_t heap_start, std::size_t heap_end)
+        : heap_start{heap_start}
+        , heap_end{heap_end}
+        , next{heap_start}
+    {
+      // Nothing to do
+    }
+
+    auto allocate(std::size_t size) -> void *;
+
+    /**
+     * @copybrief heap_allocator::deallocate
+     *
+     * @note Simply does nothing, because this allocator leaks all memory
+     */
+    auto deallocate(void * pointer) noexcept -> void;
+
+  private:
+    std::size_t heap_start;     ///< Start of the allocatable heap area
+    std::size_t heap_end;       ///< End of the allocatable heap area
+    std::atomic_uint64_t next;  ///< Current address, which is the start of still unused allocatable heap area
+  };
+
+}  // namespace teachos::arch::memory::heap
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_HEAP_USER_HEAP_ALLOCATOR_HPP
diff --git a/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp b/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp
index ce74b98..6459107 100644
--- a/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp
+++ b/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp
@@ -143,7 +143,7 @@ namespace teachos::arch::memory::paging
         // statically allocated variables), .boot_rodata (Contains constant data stored in ROM)
         // Not required: .text, .rodata, .ctors, .dtors, .bss, .data, .boot_data, .boot_text, .init
         if (section.physical_address == 0x100000 || section.physical_address == 0x102000 ||
-            section.physical_address == 0x216000)
+            section.physical_address == 0x217000)
         {
           entry.set_user_accesible();
         }
diff --git a/arch/x86_64/src/kernel/main.cpp b/arch/x86_64/src/kernel/main.cpp
index 05c879e..43b5f90 100644
--- a/arch/x86_64/src/kernel/main.cpp
+++ b/arch/x86_64/src/kernel/main.cpp
@@ -63,6 +63,9 @@ namespace teachos::arch::kernel
     memory::heap::global_heap_allocator::register_heap_allocator(memory::heap::heap_allocator_type::LINKED_LIST);
     // heap_test();
 
+    auto address = memory::heap::global_heap_allocator::kmalloc(8U);
+    (void)address;
+
     context_switching::switch_to_user_mode();
   }
 }  // namespace teachos::arch::kernel
diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp
index 51f6261..acba02d 100644
--- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp
@@ -3,11 +3,12 @@
 #include "arch/exception_handling/assert.hpp"
 #include "arch/memory/heap/bump_allocator.hpp"
 #include "arch/memory/heap/linked_list_allocator.hpp"
+#include "arch/memory/heap/user_heap_allocator.hpp"
 
 namespace teachos::arch::memory::heap
 {
   heap_allocator * global_heap_allocator::kernel_allocator_instance = nullptr;
-  heap_allocator * global_heap_allocator::user_allocator_instance = nullptr;
+  user_heap_allocator * global_heap_allocator::user_allocator_instance = nullptr;
 
   auto global_heap_allocator::kmalloc(std::size_t size) -> void * { return kernel().allocate(size); }
 
@@ -30,20 +31,17 @@ namespace teachos::arch::memory::heap
       case heap_allocator_type::BUMP: {
         static bump_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE};
         kernel_allocator_instance = &kernel_allocator;
-
-        static bump_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE};
-        user_allocator_instance = &user_allocator;
         break;
       }
       case heap_allocator_type::LINKED_LIST: {
         static linked_list_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE};
         kernel_allocator_instance = &kernel_allocator;
-
-        static linked_list_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE};
-        user_allocator_instance = &user_allocator;
         break;
       }
     }
+
+    static user_heap_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE};
+    user_allocator_instance = &user_allocator;
   }
 
   auto global_heap_allocator::kernel() -> heap_allocator &
@@ -55,11 +53,11 @@ namespace teachos::arch::memory::heap
     return *kernel_allocator_instance;
   }
 
-  auto global_heap_allocator::user() -> heap_allocator &
+  auto global_heap_allocator::user() -> user_heap_allocator &
   {
-    exception_handling::assert(user_allocator_instance != nullptr,
-                               "Attempted to allocate or deallocate using the global_heap_allocator before "
-                               "register_heap_allocation_type was called.");
+    // exception_handling::assert(user_allocator_instance != nullptr,
+    //                            "Attempted to allocate or deallocate using the global_heap_allocator before "
+    //                            "register_heap_allocation_type was called.");
 
     return *user_allocator_instance;
   }
diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp
new file mode 100644
index 0000000..f09811d
--- /dev/null
+++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp
@@ -0,0 +1,55 @@
+#include "arch/memory/heap/user_heap_allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+#include <limits>
+#include <type_traits>
+
+namespace teachos::arch::memory::heap
+{
+  namespace
+  {
+    template<typename T>
+    [[gnu::section(".user_text")]]
+    auto saturating_add(T x, T y) -> T
+      requires std::is_unsigned_v<T>
+    {
+      if (x > std::numeric_limits<T>::max() - y)
+      {
+        return std::numeric_limits<T>::max();
+      }
+      T result = x + y;
+      return result;
+    }
+  }  // namespace
+
+  auto user_heap_allocator::allocate(std::size_t size) -> void *
+  {
+    // Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the
+    // exchange failed, becuase the value was not the expected one.
+    auto alloc_start = next.load(std::memory_order::relaxed);
+    // Repeat allocation until it succeeds, has to be done, because another allocator could overtake it at any time
+    // causing the value to differ and the calculation to have to be redone.
+    for (;;)
+    {
+      auto const alloc_end = saturating_add(alloc_start, size);
+      arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory");
+      // Check if the atomic value is still the one initally loaded, if it isn't we have been overtaken by another
+      // thread and need to redo the calculation. Spurious failure by weak can be ignored, because the whole allocation
+      // is wrapped in an infinite for loop so a failure that wasn't actually one will simply be retried until it works.
+      auto const updated = next.compare_exchange_weak(alloc_start, alloc_end, std::memory_order::relaxed);
+      if (updated)
+      {
+        return reinterpret_cast<void *>(alloc_start);
+      }
+    }
+  }
+
+  auto user_heap_allocator::deallocate(void * pointer) noexcept -> void
+  {
+    if (pointer)
+    {
+    }
+  }
+
+}  // namespace teachos::arch::memory::heap
diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp
index 558fbce..4cdfa80 100644
--- a/arch/x86_64/src/memory/main.cpp
+++ b/arch/x86_64/src/memory/main.cpp
@@ -20,18 +20,23 @@ namespace teachos::arch::memory
     }
 
     template<allocator::FrameAllocator T>
-    auto remap_heap(T & allocator, paging::active_page_table & active_table) -> void
+    auto remap_heap(T & allocator, paging::active_page_table & active_table, bool is_user_heap = false) -> void
     {
-      auto const start_page = paging::virtual_page::containing_address(heap::KERNEL_HEAP_START);
-      auto const end_page =
-          ++(paging::virtual_page::containing_address(heap::KERNEL_HEAP_START + heap::KERNEL_HEAP_SIZE - 1));
+      auto const heap_start = is_user_heap ? heap::USER_HEAP_START : heap::KERNEL_HEAP_START;
+      auto const heap_size = is_user_heap ? heap::USER_HEAP_SIZE : heap::KERNEL_HEAP_SIZE;
+
+      auto const start_page = paging::virtual_page::containing_address(heap_start);
+      auto const end_page = ++(paging::virtual_page::containing_address(heap_start + heap_size - 1));
       paging::page_container::iterator const begin{start_page};
       paging::page_container::iterator const end{end_page};
       paging::page_container const pages{begin, end};
 
+      constexpr auto base_flags = paging::entry::WRITABLE;
+      auto const flags = is_user_heap ? base_flags | paging::entry::USER_ACCESSIBLE : base_flags;
+
       for (auto const & page : pages)
       {
-        active_table.map_page_to_next_free_frame(allocator, page, paging::entry::WRITABLE);
+        active_table.map_page_to_next_free_frame(allocator, page, flags);
       }
     }
   }  // namespace
@@ -54,7 +59,8 @@ namespace teachos::arch::memory
     video::vga::text::write("Kernel remapping successful", video::vga::text::common_attributes::green_on_black);
     video::vga::text::newline();
 
-    remap_heap(allocator, active_table);
+    remap_heap(allocator, active_table);        // Remap kernel heap
+    remap_heap(allocator, active_table, true);  // Remap user heap
     video::vga::text::write("Heap remapping successful", video::vga::text::common_attributes::green_on_black);
     video::vga::text::newline();
   }
diff --git a/arch/x86_64/src/user/main.cpp b/arch/x86_64/src/user/main.cpp
index 4f6e688..59647f8 100644
--- a/arch/x86_64/src/user/main.cpp
+++ b/arch/x86_64/src/user/main.cpp
@@ -17,8 +17,8 @@ namespace teachos::arch::user
 
     // kernel::cpu::clear_interrupt_flag();  // Causes crash Kernel Code (.text) is not mapped in User mMde
 
-    auto test = memory::heap::global_heap_allocator::malloc(20U);
-    (void)test;
+    auto address = memory::heap::global_heap_allocator::malloc(8U);
+    (void)address;
 
     // auto test = new int{20};  // Causes crash Heap is not mapped in User Mode
     // (void)test;