The start of interrupt and timer support, with some DeviceTree parsing.

13 files changed, 331 insertions, 14 deletions

diff --git a/kernel/Cargo.lock b/kernel/Cargo.lock
index d831a4f..5ab50e3 100644
--- a/kernel/Cargo.lock
+++ b/kernel/Cargo.lock
@@ -23,13 +23,21 @@ dependencies = [
 ]
 
 [[package]]
+name = "either"
+version = "1.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "60b1af1c220855b6ceac025d3f6ecdd2b7c4894bfe9cd9bda4fbb4bc7c0d4cf0"
+
+[[package]]
 name = "kernel"
 version = "0.1.0"
 dependencies = [
  "bstr",
  "contracts",
+ "either",
  "log",
  "spin",
+ "void",
 ]
 
 [[package]]
@@ -84,3 +92,9 @@ name = "unicode-ident"
 version = "1.0.12"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b"
+
+[[package]]
+name = "void"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6a02e4885ed3bc0f2de90ea6dd45ebcbb66dacffe03547fadbb0eeae2770887d"
diff --git a/kernel/Cargo.toml b/kernel/Cargo.toml
index ea81d5d..5eb15af 100644
--- a/kernel/Cargo.toml
+++ b/kernel/Cargo.toml
@@ -9,8 +9,10 @@ crate-type = ["staticlib"]
 [dependencies]
 bstr = { version = "1.10.0", default-features = false }
 contracts = { version = "0.6.3", default-features = false }
+either = { version = "1.13.0", default-features = false }
 log = { version = "0.4.20", default-features = false }
 spin = { version = "0.9.8", default-features = false, features = ["mutex", "use_ticket_mutex"] }
+void = { version = "1.0.2", default-features = false }
 
 [profile.release]
 codegen-units = 1
diff --git a/kernel/src/allocators.rs b/kernel/src/allocators.rs
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/kernel/src/allocators.rs
diff --git a/kernel/src/collections/mod.rs b/kernel/src/collections/mod.rs
new file mode 100644
index 0000000..ebcfad3
--- /dev/null
+++ b/kernel/src/collections/mod.rs
@@ -0,0 +1,3 @@
+//! Useful data structures for the kernel.
+
+pub mod stack_linked_list;
diff --git a/kernel/src/collections/stack_linked_list.rs b/kernel/src/collections/stack_linked_list.rs
new file mode 100644
index 0000000..ce9ee8e
--- /dev/null
+++ b/kernel/src/collections/stack_linked_list.rs
@@ -0,0 +1,44 @@
+//! A linked list whose nodes can be stack-allocated.
+
+use core::fmt;
+
+/// A linked list whose nodes can be stack-allocated.
+#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
+pub struct StackLinkedList<'list, T>(pub Option<(T, &'list StackLinkedList<'list, T>)>);
+
+impl<'list, T> StackLinkedList<'list, T> {
+    /// An empty linked list.
+    pub const NIL: StackLinkedList<'list, T> = StackLinkedList(None);
+
+    /// Prepends an element to the linked list, returning the new head node.
+    pub fn cons(&'list self, head: T) -> StackLinkedList<'list, T> {
+        StackLinkedList(Some((head, self)))
+    }
+
+    /// Returns an iterator over the elements in the list.
+    pub fn iter<'iter: 'list>(&'iter self) -> impl 'iter + Iterator<Item = &'list T> {
+        struct Iter<'iter, 'list, T>(&'iter StackLinkedList<'list, T>);
+
+        impl<'iter: 'list, 'list, T> Iterator for Iter<'iter, 'list, T> {
+            type Item = &'list T;
+
+            fn next(&mut self) -> Option<&'list T> {
+                match &(self.0).0 {
+                    Some((hd, tl)) => {
+                        self.0 = tl;
+                        Some(hd)
+                    }
+                    None => None,
+                }
+            }
+        }
+
+        Iter(self)
+    }
+}
+
+impl<'list, T: fmt::Debug> fmt::Debug for StackLinkedList<'list, T> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_list().entries(self.iter()).finish()
+    }
+}
diff --git a/kernel/src/console.rs b/kernel/src/console.rs
index 626edef..1c0fe78 100644
--- a/kernel/src/console.rs
+++ b/kernel/src/console.rs
@@ -1,9 +1,8 @@
 //! The console subsystem, used for the kernel to log things.
 
-use core::fmt::Write;
-
 use crate::util::likely;
 use contracts::{ensures, invariant};
+use core::fmt::Write;
 use log::Log;
 use spin::Mutex;
 
@@ -44,10 +43,10 @@ impl Log for Console {
         let mut inner = self.0.lock();
         let mut body = |line| {
             let level = match record.level() {
-                log::Level::Error => "ERR",
-                log::Level::Warn => "WRN",
-                log::Level::Info => "INF",
-                log::Level::Debug => "DBG",
+                log::Level::Error => "\x1b[1;31mERR\x1b[0m",
+                log::Level::Warn => "\x1b[1;33mWRN\x1b[0m",
+                log::Level::Info => "\x1b[1;36mINF\x1b[0m",
+                log::Level::Debug => "\x1b[1;35mDBG\x1b[0m",
                 log::Level::Trace => "TRC",
             };
             let file = record.file().unwrap_or("???");
diff --git a/kernel/src/device_tree.rs b/kernel/src/device_tree.rs
index 04f873c..d843234 100644
--- a/kernel/src/device_tree.rs
+++ b/kernel/src/device_tree.rs
@@ -1,9 +1,10 @@
 //! Support for the DeviceTree format.
 
-use core::{iter, slice};
-
+use crate::collections::stack_linked_list::StackLinkedList;
 use bstr::BStr;
 use contracts::requires;
+use core::{fmt, iter, slice};
+use either::Either;
 
 /// A reference to a flattened DeviceTree (DTB) in memory.
 #[derive(Debug)]
@@ -94,10 +95,22 @@ impl<'dt> FlattenedDeviceTree<'dt> {
         Ok(&out[..i])
     }
 
+    /// Iterates over the properties stored in the DeviceTree, only allocating memory on the stack.
+    pub fn for_each_property<'iter: 'dt, E>(
+        &'iter self,
+        mut func: impl for<'a> FnMut(FdtNodePath<'dt, 'a>, &'dt BStr, &'dt BStr) -> Result<(), E>,
+    ) -> Result<(), Either<DeviceTreeError, E>> {
+        for_each_property(
+            &mut self.struct_events().peekable(),
+            &mut func,
+            StackLinkedList::NIL,
+        )
+    }
+
     /// Returns an iterator over the events in the flattened DeviceTree's structure block.
-    pub fn struct_events(
-        &self,
-    ) -> impl '_ + Iterator<Item = Result<FdtStructEvent, DeviceTreeError>> {
+    pub fn struct_events<'iter: 'dt>(
+        &'iter self,
+    ) -> impl 'iter + Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>> {
         let mut ptr = self.struct_block;
         iter::from_fn(move || loop {
             break match u32::from_be(ptr[0]) {
@@ -185,6 +198,46 @@ pub enum DeviceTreeError {
     InvalidDeviceTree,
     InvalidTokenType(u32),
     StringMissingNulTerminator(u32),
+
+    UnexpectedEndOfStructBlock,
+    UnexpectedEvent,
+}
+
+fn for_each_property<'dt, E>(
+    events: &mut iter::Peekable<impl Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>>>,
+    func: &mut impl for<'a> FnMut(FdtNodePath<'dt, 'a>, &'dt BStr, &'dt BStr) -> Result<(), E>,
+    node: StackLinkedList<&'dt BStr>,
+) -> Result<(), Either<DeviceTreeError, E>> {
+    // Read the first event, which should be the BeginNode starting the node we're trying to read.
+    let event = events
+        .next()
+        .ok_or(Either::Left(DeviceTreeError::UnexpectedEndOfStructBlock))?
+        .map_err(Either::Left)?;
+    let FdtStructEvent::BeginNode(node_name) = event else {
+        return Err(Either::Left(DeviceTreeError::UnexpectedEvent));
+    };
+    let node = node.cons(node_name);
+
+    // Parse properties and subnodes until we get to the end.
+    loop {
+        if matches!(events.peek(), Some(Ok(FdtStructEvent::BeginNode(_)))) {
+            for_each_property(events, func, node)?;
+        } else {
+            let event = events
+                .next()
+                .ok_or(Either::Left(DeviceTreeError::UnexpectedEndOfStructBlock))?
+                .map_err(Either::Left)?;
+            match event {
+                FdtStructEvent::BeginNode(_) => {
+                    return Err(Either::Left(DeviceTreeError::UnexpectedEvent))
+                }
+                FdtStructEvent::EndNode => break Ok(()),
+                FdtStructEvent::Prop(prop, value) => {
+                    func(FdtNodePath(node), prop, value).map_err(Either::Right)?
+                }
+            }
+        }
+    }
 }
 
 /// The flattened DeviceTree header.
@@ -222,3 +275,34 @@ pub enum FdtStructEvent<'dt> {
     EndNode,
     Prop(&'dt BStr, &'dt BStr),
 }
+
+/// The path to a node. Note that the list this contains is in _reverse_ order.
+#[derive(Debug, Eq, PartialEq)]
+pub struct FdtNodePath<'dt, 'list>(pub StackLinkedList<'list, &'dt BStr>);
+
+impl<'dt, 'list> fmt::Display for FdtNodePath<'dt, 'list> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        match (self.0).0 {
+            Some((hd, tl)) => write!(fmt, "{}{}/", FdtNodePath(*tl), hd),
+            None => Ok(()),
+        }
+    }
+}
+
+impl<'dt, 'list, U> PartialEq<[U]> for FdtNodePath<'dt, 'list>
+where
+    &'dt BStr: PartialEq<U>,
+{
+    fn eq(&self, other: &[U]) -> bool {
+        self.0.iter().eq(other.iter().rev())
+    }
+}
+
+impl<'dt, 'list, U, const N: usize> PartialEq<[U; N]> for FdtNodePath<'dt, 'list>
+where
+    &'dt BStr: PartialEq<U>,
+{
+    fn eq(&self, other: &[U; N]) -> bool {
+        self.0.iter().eq(other.iter().rev())
+    }
+}
diff --git a/kernel/src/drivers/mod.rs b/kernel/src/drivers/mod.rs
new file mode 100644
index 0000000..fd55e62
--- /dev/null
+++ b/kernel/src/drivers/mod.rs
@@ -0,0 +1 @@
+pub mod riscv_timer;
diff --git a/kernel/src/drivers/riscv_timer.rs b/kernel/src/drivers/riscv_timer.rs
new file mode 100644
index 0000000..a702f7b
--- /dev/null
+++ b/kernel/src/drivers/riscv_timer.rs
@@ -0,0 +1,43 @@
+use core::{arch::asm, ops::Add, time::Duration};
+
+/// The number of `Instant` "ticks" in a second. Initialized by the early-boot DeviceTree parser.
+pub static mut TIMEBASE_FREQUENCY: u32 = 0;
+
+/// A moment in time.
+#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
+pub struct Instant(u64);
+
+impl Instant {
+    /// Returns the current time as an `Instant`.
+    pub fn now() -> Instant {
+        let out;
+        // SAFETY: We require the Sstc extension, enable it before jumping to Rust, and never
+        // disable it.
+        unsafe {
+            asm!("rdtime {out}", out = out(reg) out, options(nomem, nostack));
+        }
+        Instant(out)
+    }
+}
+
+impl Add<Duration> for Instant {
+    type Output = Instant;
+
+    #[allow(clippy::suspicious_arithmetic_impl)]
+    fn add(self, duration: Duration) -> Instant {
+        // SAFETY: TIMEBASE_FREQUENCY is never concurrently written to.
+        let ticks_per_second = unsafe { TIMEBASE_FREQUENCY };
+        let ticks = duration.as_nanos().wrapping_mul(ticks_per_second as u128) / 1_000_000_000;
+        Instant(self.0.wrapping_add(ticks as u64))
+    }
+}
+
+/// Sets the timer interrupt to fire at the given instant. Note that this sets a global value,
+/// rather than interacting with the scheduler in any way.
+pub fn set_timer(instant: Instant) {
+    // SAFETY: We require the Sstc extension, enable it before jumping to Rust, and never
+    // disable it.
+    unsafe {
+        asm!("csrw stimecmp, {instant}", instant = in(reg) instant.0, options(nomem, nostack));
+    }
+}
diff --git a/kernel/src/interrupts.rs b/kernel/src/interrupts.rs
new file mode 100644
index 0000000..302fc4f
--- /dev/null
+++ b/kernel/src/interrupts.rs
@@ -0,0 +1,82 @@
+use crate::{
+    drivers::riscv_timer::{set_timer, Instant},
+    prelude::*,
+};
+use core::{
+    arch::{asm, global_asm},
+    time::Duration,
+};
+
+/// Sets up the timer interrupt.
+#[inline(never)]
+pub(crate) fn example_timer() {
+    let now = Instant::now();
+    info!("now = {now:?}");
+
+    let in_a_sec = now + Duration::from_secs(1);
+    info!("in_a_sec = {in_a_sec:?}");
+    info!("setting a timer for 1s...");
+    set_timer(in_a_sec);
+
+    enable_interrupts();
+}
+
+/// Disables interrupts.
+pub fn disable_interrupts() {
+    // Set SSTATUS.SIE to 0, which disables interrupts.
+    //
+    // SAFETY: Not running interrupts shouldn't be able to compromise safety.
+    unsafe {
+        asm!(
+            "csrc sstatus, {sie}",
+            sie = in(reg) (1 << 1),
+            options(nomem, nostack)
+        );
+    }
+}
+
+/// Enables interrupts.
+pub fn enable_interrupts() {
+    // Set STVEC.BASE to the handler function, and STVEC.MODE to Direct. Since the trap_handler_asm
+    // has a `.align 4` before it, the lower two bits of its address should already be zero.
+    //
+    // SAFETY: Even if interrupts were already enabled, this is a valid handler.
+    unsafe {
+        asm!(
+            "csrw stvec, {stvec}",
+            stvec = in(reg) trap_handler_asm,
+            options(nomem, nostack)
+        );
+    }
+
+    // Set SSTATUS.SIE to 1, which enables interrupts.
+    //
+    // SAFETY: We just initialized STVEC, so it should be able to handle interrupts.
+    unsafe {
+        asm!(
+            "csrs sstatus, {sie}",
+            sie = in(reg) (1 << 1),
+            options(nomem, nostack)
+        );
+    }
+}
+
+fn trap_handler() {
+    todo!("trap_handler")
+}
+
+// The assembly code that calls the Rust trap handler, after saving all caller-save registers
+// to the stack.
+global_asm! {
+    // Declare the handler's symbol.
+    ".align 4",
+    "trap_handler_asm:",
+    // TODO
+    "nop",
+    "call {trap_handler}",
+    trap_handler = sym trap_handler
+}
+
+extern "C" {
+    fn trap_handler_asm();
+}
diff --git a/kernel/src/lib.rs b/kernel/src/lib.rs
index 0a724c6..840f397 100644
--- a/kernel/src/lib.rs
+++ b/kernel/src/lib.rs
@@ -1,12 +1,21 @@
 #![no_std]
 
+#[macro_use]
+pub mod util;
+
+pub mod allocators;
+pub mod collections;
 pub mod console;
 pub mod device_tree;
-pub mod util;
+pub mod drivers;
+pub mod interrupts;
+pub mod prelude;
 
 #[cfg(not(test))]
 mod panic;
 
+use crate::prelude::*;
+
 /// The entrypoint to the kernel. This should be executed by hart0 alone. It performs some early
 /// boot tasks, then wakes up any other harts.
 ///
@@ -20,7 +29,7 @@ mod panic;
 pub unsafe extern "C" fn hart0_boot(device_tree: *const u8) -> ! {
     console::init();
 
-    log::info!("device_tree = {device_tree:?}");
+    info!("device_tree = {device_tree:?}");
     let flattened_device_tree = unsafe { device_tree::FlattenedDeviceTree::from_ptr(device_tree) }
         .expect("invalid DeviceTree");
     for event in flattened_device_tree.struct_events() {
@@ -28,5 +37,35 @@ pub unsafe extern "C" fn hart0_boot(device_tree: *const u8) -> ! {
         dbg!(event);
     }
 
-    todo!()
+    // Set up the allocator and the timer subsystem.
+    //
+    // TODO: The timer really oughta be later...
+    flattened_device_tree
+        .for_each_property(|node, prop, value| {
+            if node == ["", "cpus"] && prop == "timebase-frequency" {
+                if value.len() == 4 {
+                    let value = [value[0], value[1], value[2], value[3]];
+                    let timebase_frequency = u32::from_be_bytes(value);
+                    // SAFETY: Nobody is concurrently running, so they can't be concurrently
+                    // modifying this.
+                    unsafe {
+                        drivers::riscv_timer::TIMEBASE_FREQUENCY = timebase_frequency;
+                    }
+                    dbg!(timebase_frequency);
+                } else {
+                    warn!("/cpus/timebase-frequency was not a 4-byte quantity");
+                }
+            } else {
+                info!("{node}{prop} = {value:?}");
+            }
+            Ok(())
+        })
+        .map_err(|err| err.left_or_else(|void| void::unreachable(void)))
+        .expect("invalid DeviceTree");
+
+    interrupts::example_timer();
+    info!("sleeping forever...");
+    loop {
+        unsafe { core::arch::asm!("wfi") }
+    }
 }
diff --git a/kernel/src/panic.rs b/kernel/src/panic.rs
index aa7df78..14bddf1 100644
--- a/kernel/src/panic.rs
+++ b/kernel/src/panic.rs
@@ -1,11 +1,13 @@
 //! The kernel panic handler.
 
+use crate::interrupts::disable_interrupts;
 use core::{arch::asm, panic::PanicInfo};
 
 #[panic_handler]
 fn panic(info: &PanicInfo) -> ! {
     log::error!("{info}");
 
+    disable_interrupts();
     loop {
         unsafe { asm!("wfi") }
     }
diff --git a/kernel/src/prelude.rs b/kernel/src/prelude.rs
new file mode 100644
index 0000000..05bd9ca
--- /dev/null
+++ b/kernel/src/prelude.rs
@@ -0,0 +1,4 @@
+//! A prelude for use inside the kernel.
+
+pub use bstr::B;
+pub use log::{debug, error, info, trace, warn};