From 8956fb12f781532221c1f8c80e1b2c691c92ab8f Mon Sep 17 00:00:00 2001
From: Kit Rhett Aultman <kit@kitaultman.com>
Date: Sun, 30 Jun 2024 12:38:01 -0400
Subject: [PATCH] heap/linker/main: set up a heap allocator

This commit sets up a heap allocator.  Again, I cannot sufficiently
stress the usefulness of Meyer Zinn for getting things this far, and
much of what I needed to know about getting linker symbols propagated
into Rust code comes from:
https://meyerzinn.tech/posts/2023/03/08/p1-printing-and-allocating/

Meyer steps through the process of setting up the linked list allocator.
However, there's a buddy list allocator that can be used as a drop-in
replacement, and since this is a more common allocator scheme, and since
doing my own thing means writing my own code and getting more familiar
with Rust, it seemed a divergence worth taking.
---
 Cargo.lock    | 19 +++++++++++++++++++
 Cargo.toml    |  1 +
 src/heap.rs   | 31 +++++++++++++++++++++++++++++++
 src/linker.ld | 11 ++++++++++-
 src/main.rs   | 10 ++++++++++
 5 files changed, 71 insertions(+), 1 deletion(-)
 create mode 100644 src/heap.rs

diff --git a/Cargo.lock b/Cargo.lock
index 75e1067..d7e35c5 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -20,6 +20,15 @@ version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
 
+[[package]]
+name = "buddy_system_allocator"
+version = "0.9.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d44d578cadd17312c75e7d0ef489361f160ace58f7139aa32001fee1a51b89b5"
+dependencies = [
+ "spin",
+]
+
 [[package]]
 name = "lock_api"
 version = "0.4.12"
@@ -43,6 +52,7 @@ dependencies = [
 name = "riscv"
 version = "0.1.0"
 dependencies = [
+ "buddy_system_allocator",
  "spinning_top",
  "uart_16550",
 ]
@@ -59,6 +69,15 @@ version = "1.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49"
 
+[[package]]
+name = "spin"
+version = "0.9.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6980e8d7511241f8acf4aebddbb1ff938df5eebe98691418c4468d0b72a96a67"
+dependencies = [
+ "lock_api",
+]
+
 [[package]]
 name = "spinning_top"
 version = "0.3.0"
diff --git a/Cargo.toml b/Cargo.toml
index f88d624..ab3c17d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,6 +7,7 @@ edition = "2021"
 target = "riscv64gc-unknown-none-elf"
 
 [dependencies]
+buddy_system_allocator = "0.9.1"
 spinning_top = "0.3.0"
 uart_16550 = "0.3.0"
 
diff --git a/src/heap.rs b/src/heap.rs
new file mode 100644
index 0000000..6eca8bb
--- /dev/null
+++ b/src/heap.rs
@@ -0,0 +1,31 @@
+
+
+use buddy_system_allocator::LockedHeap;
+
+// The recommended order for the heap is 32, which to me says the largest
+// block size would be 2^32, or 4GiB.  We don't actually have that available
+// but at the same time, when I tried to reduce the order down to 16 the init
+// simply stalled out.  So...32 is is. ((shrug))
+
+#[global_allocator]
+static HEAP_ALLOCATOR: LockedHeap<32> = LockedHeap::<32>::empty();
+
+pub unsafe fn init() {
+    let heap_start: usize;
+    let heap_size: usize;
+    // UNSAFE: This is fine, just loading some constants.
+    unsafe {
+        // using inline assembly is easier to access linker constants
+        use core::arch::asm;
+        asm!(
+          "la {heap_start}, _heap_start",
+          "la {heap_size}, _heap_size",
+          heap_start = out(reg) heap_start,
+          heap_size = out(reg) heap_size,
+          options(nomem)
+        )
+    };
+    println!("Kernel heap symbols: start: {:#x}, size: {}", heap_start, heap_size);
+
+    unsafe { HEAP_ALLOCATOR.lock().init(heap_start, heap_size); }
+}
diff --git a/src/linker.ld b/src/linker.ld
index 21ec60b..364615a 100644
--- a/src/linker.ld
+++ b/src/linker.ld
@@ -37,8 +37,17 @@ SECTIONS {
     *(.sbss .sbss.*) *(.bss .bss.*)
     PROVIDE(_bss_end = .); # ... and one at the end
   } >RAM AT>RAM :bss # and this goes into the bss segment
-
+  PROVIDE(_kernel_end = .);
+
+  # heap reserved space starts where the kernel ends and
+  # continues until it reaches the stack.  Because the stack
+  # is a fixed size, as the kernel grows, the heap will shrink
+  PROVIDE(_heap_start = .);
+  PROVIDE(_heap_size = _stack_bottom - _heap_start);
+  
   # start the stack at the end of memory and let it grow downward
+  # capped at 1M
+  PROVIDE(_stack_bottom = ORIGIN(RAM) + LENGTH(RAM) - 1M);
   PROVIDE(_stack_top = ORIGIN(RAM) + LENGTH(RAM));
 }
 
diff --git a/src/main.rs b/src/main.rs
index 3e9bc53..99941da 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -2,7 +2,9 @@
 #![no_main]
 #![feature(naked_functions)] // enable functions that are pure inline assembly
 
+#[macro_use]
 mod console;
+mod heap;
 
 use core::panic::PanicInfo;
 
@@ -60,8 +62,16 @@ unsafe extern "C" fn _start() -> ! {
 
 #[no_mangle] // Again, being mindful of the C calling convention
 extern "C" fn entry() -> ! {
+    // Init serial console
     use crate::console;
     console::init_console();
     println!("KIT-- hello works from println!");
+
+    // Init heap
+    use crate::heap;
+    // Safety: initialize once (and that's done now)
+    unsafe { heap::init() };
+
+    println!("Kernel init complete");
     loop {}
 }
-- 
2.34.1