kernel/memory: implement basic bitmap allocator

1 files changed, 56 insertions, 0 deletions

diff --git a/kernel/include/kernel/memory/bitmap_allocator.hpp b/kernel/include/kernel/memory/bitmap_allocator.hpp
new file mode 100644
index 0000000..fb5bf55
--- /dev/null
+++ b/kernel/include/kernel/memory/bitmap_allocator.hpp
@@ -0,0 +1,56 @@
+#ifndef TEACHOS_KERNEL_MEMORY_BITMAP_ALLOCATOR_HPP
+#define TEACHOS_KERNEL_MEMORY_BITMAP_ALLOCATOR_HPP
+
+#include "kapi/memory.hpp"
+
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <utility>
+
+namespace kernel::memory
+{
+
+  //! A generic, bitmap base frame allocator.
+  //!
+  //! This frame allocator manages the allocation state of each frame present in the system using a single bit per
+  //! frame. All state information is stored in a contiguous region of memory.
+  struct bitmap_frame_allocator final : kapi::memory::frame_allocator
+  {
+    //! Construct a new, empty bitmap allocator.
+    //!
+    //! @param storage A contiguous region of virtual memory for state storage.
+    //! @param total_frame The total number of frames in the system.
+    bitmap_frame_allocator(std::span<std::uint64_t> storage, std::size_t frame_count) noexcept;
+
+    bitmap_frame_allocator(bitmap_frame_allocator const &) = delete;
+    bitmap_frame_allocator(bitmap_frame_allocator &&) = delete;
+    auto operator=(bitmap_frame_allocator const &) -> bitmap_frame_allocator & = delete;
+    auto operator=(bitmap_frame_allocator &&) -> bitmap_frame_allocator & = delete;
+
+    //! @copydoc kapi::memory::frame_allocator::allocate_many
+    [[nodiscard]] auto allocate_many(std::size_t count = 1) noexcept
+        -> std::optional<std::pair<kapi::memory::frame, std::size_t>> override;
+
+    //! @copydoc kapi::memory::frame_allocator::release_many
+    auto release_many(std::pair<kapi::memory::frame, std::size_t> frame_set) -> void override;
+
+    //! Mark a given frame as being used.
+    //!
+    //! This function is used during bootstrap to hand the platform allocator state over to this allocator.
+    auto mark_used(kapi::memory::frame frame) -> void override;
+
+  private:
+    [[nodiscard]] auto test(std::size_t index) const noexcept -> bool;
+    auto set(std::size_t index) noexcept -> void;
+    auto clear(std::size_t index) noexcept -> void;
+
+    std::span<std::uint64_t> m_bitmap;
+    std::uint64_t m_frame_count;
+    std::uint64_t m_last_index;
+  };
+
+}  // namespace kernel::memory
+
+#endif