summaryrefslogtreecommitdiff
path: root/kernel
diff options
context:
space:
mode:
authorNathan Ringo <nathan@remexre.com>2024-09-01 19:59:44 -0500
committerNathan Ringo <nathan@remexre.com>2024-09-01 19:59:44 -0500
commit386df39c9866a4d945de46ef0dcab2363c674e0e (patch)
treec0572ce6a2c81c93546210f599dff553783c5760 /kernel
parent6b98b6afea6e790abe738a67aa28bab54c91afe0 (diff)
Move almost all the kernel into crates/.
Diffstat (limited to 'kernel')
-rw-r--r--kernel/Cargo.lock121
-rw-r--r--kernel/src/allocators/buddy/bitvec.rs50
-rw-r--r--kernel/src/allocators/buddy/mod.rs52
-rw-r--r--kernel/src/allocators/buddy/stripe.rs148
-rw-r--r--kernel/src/allocators/buddy/tree.rs112
-rw-r--r--kernel/src/allocators/mod.rs24
-rw-r--r--kernel/src/allocators/physical_memory_free_list.rs322
-rw-r--r--kernel/src/arch/hosted/mod.rs19
-rw-r--r--kernel/src/arch/mod.rs9
-rw-r--r--kernel/src/arch/riscv64/interrupts.rs82
-rw-r--r--kernel/src/arch/riscv64/mod.rs8
-rw-r--r--kernel/src/collections/mod.rs3
-rw-r--r--kernel/src/collections/stack_linked_list.rs78
-rw-r--r--kernel/src/device_tree.rs641
-rw-r--r--kernel/src/drivers/mod.rs2
-rw-r--r--kernel/src/drivers/riscv_timer.rs43
-rw-r--r--kernel/src/lib.rs99
-rw-r--r--kernel/src/panic.rs13
-rw-r--r--kernel/src/prelude.rs4
-rw-r--r--kernel/src/util.rs99
20 files changed, 0 insertions, 1929 deletions
diff --git a/kernel/Cargo.lock b/kernel/Cargo.lock
deleted file mode 100644
index 71a1b88..0000000
--- a/kernel/Cargo.lock
+++ /dev/null
@@ -1,121 +0,0 @@
-# This file is automatically @generated by Cargo.
-# It is not intended for manual editing.
-version = 3
-
-[[package]]
-name = "allocator-api2"
-version = "0.2.18"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5c6cb57a04249c6480766f7f7cef5467412af1490f8d1e243141daddada3264f"
-
-[[package]]
-name = "bstr"
-version = "1.10.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "40723b8fb387abc38f4f4a37c09073622e41dd12327033091ef8950659e6dc0c"
-dependencies = [
- "memchr",
-]
-
-[[package]]
-name = "cfg-if"
-version = "1.0.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
-
-[[package]]
-name = "contracts"
-version = "0.6.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "f1d1429e3bd78171c65aa010eabcdf8f863ba3254728dbfb0ad4b1545beac15c"
-dependencies = [
- "proc-macro2",
- "quote",
- "syn",
-]
-
-[[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 = [
- "allocator-api2",
- "bstr",
- "cfg-if",
- "contracts",
- "either",
- "log",
- "spin",
- "static_assertions",
- "void",
-]
-
-[[package]]
-name = "log"
-version = "0.4.20"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b5e6163cb8c49088c2c36f57875e58ccd8c87c7427f7fbd50ea6710b2f3f2e8f"
-
-[[package]]
-name = "memchr"
-version = "2.7.4"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "78ca9ab1a0babb1e7d5695e3530886289c18cf2f87ec19a575a0abdce112e3a3"
-
-[[package]]
-name = "proc-macro2"
-version = "1.0.78"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "e2422ad645d89c99f8f3e6b88a9fdeca7fabeac836b1002371c4367c8f984aae"
-dependencies = [
- "unicode-ident",
-]
-
-[[package]]
-name = "quote"
-version = "1.0.35"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef"
-dependencies = [
- "proc-macro2",
-]
-
-[[package]]
-name = "spin"
-version = "0.9.8"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "6980e8d7511241f8acf4aebddbb1ff938df5eebe98691418c4468d0b72a96a67"
-
-[[package]]
-name = "static_assertions"
-version = "1.1.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a2eb9349b6444b326872e140eb1cf5e7c522154d69e7a0ffb0fb81c06b37543f"
-
-[[package]]
-name = "syn"
-version = "1.0.109"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "72b64191b275b66ffe2469e8af2c1cfe3bafa67b529ead792a6d0160888b4237"
-dependencies = [
- "proc-macro2",
- "quote",
- "unicode-ident",
-]
-
-[[package]]
-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/src/allocators/buddy/bitvec.rs b/kernel/src/allocators/buddy/bitvec.rs
deleted file mode 100644
index c7f415a..0000000
--- a/kernel/src/allocators/buddy/bitvec.rs
+++ /dev/null
@@ -1,50 +0,0 @@
-use core::mem::transmute;
-
-use contracts::requires;
-
-/// A fixed-length vector of bits.
-pub struct BitVec([usize]);
-
-impl BitVec {
- fn from_mut(words: &mut [usize]) -> &mut BitVec {
- // SAFETY: The types have a newtype relationship.
- unsafe { transmute(words) }
- }
-
- fn from_ref(words: &[usize]) -> &BitVec {
- // SAFETY: The types have a newtype relationship.
- unsafe { transmute(words) }
- }
-
- /// Retrieves the value of a bit from the BitVec.
- #[requires(i < self.len())]
- pub fn get(&self, i: usize) -> bool {
- let word_index = i / usize::BITS as usize;
- let subword_index = i % usize::BITS as usize;
- let one_hot = 1 << subword_index;
- (self.0[word_index] & one_hot) != 0
- }
-
- /// Returns whether the BitVec is empty.
- pub fn is_empty(&self) -> bool {
- self.0.is_empty()
- }
-
- /// Returns the number of bits in the BitVec.
- pub fn len(&self) -> usize {
- self.0.len() * usize::BITS as usize
- }
-
- /// Sets the value of a bit in the BitVec.
- #[requires(i < self.len())]
- pub fn set(&mut self, i: usize, value: bool) {
- let word_index = i / usize::BITS as usize;
- let subword_index = i % usize::BITS as usize;
- let one_hot = 1 << subword_index;
- if value {
- self.0[word_index] |= one_hot;
- } else {
- self.0[word_index] &= !one_hot;
- }
- }
-}
diff --git a/kernel/src/allocators/buddy/mod.rs b/kernel/src/allocators/buddy/mod.rs
deleted file mode 100644
index 08b30a7..0000000
--- a/kernel/src/allocators/buddy/mod.rs
+++ /dev/null
@@ -1,52 +0,0 @@
-//! A buddy allocator, used to allocate pages.
-//!
-//! The allocator can be split into three abstractions: stripes, trees, and the allocator.
-//!
-//! TODO: See if there's standard terminology for these.
-//!
-//! ## Stripes
-//!
-//! The buddy allocator works in terms of size classes, which are power-of-two sized, starting at a
-//! single page and going up from there. Each stripe corresponds to a single size class and a
-//! particular region of memory.
-//!
-//! A stripe contains a circular doubly-linked free-list for subregions of that size class, and a
-//! bitset marking whether a particular region has been allocated or not. Being a circular
-//! doubly-linked list makes it cheap to remove an element whose address we know, as well as cheap
-//! to push and pop elements.
-//!
-//! It's efficient to go from the address of a subregion to the index of its corresponding bit, so
-//! when we hand out a subregion from the free-list or put one back, it's cheap to read or write
-//! its bit.
-//!
-//! ## Trees
-//!
-//! A tree is logically a collection of stripes, one per size class. To pack the structures more
-//! efficiently, they are stored interleaved with each other, and the tree manages this.
-//!
-//! The important logic at the level of trees happens when we allocate a subregion from a size
-//! class whose stripe's free-list is empty, and when we free subregions.
-//!
-//! When a stripe's free-list is empty, the tree instead allocates a subregion of a larger size
-//! from the next stripe. It can then store the unused portion in the current size class.
-//!
-//! The really important bit is the ability to merge subregions when they're freed. When we free a
-//! subregion of a certain size class, we can check whether its neighbor (its buddy) is unallocated
-//! as well. If so, we can remove it from the free-list by its address. We can combine the two
-//! subregions into one of the next larger size class, and then return that subregion to the next
-//! stripe.
-//!
-//! ## The buddy allocator
-//!
-//! Finally, the overall buddy allocator needs to be able to handle multiple memory regions. To
-//! facilitate this, the trees are stored in an array, which forms the overall allocator.
-
-mod bitvec;
-mod stripe;
-mod tree;
-
-/// The index of the largest size class; i.e., one less than the number of size classes.
-const MAX_ORDER: usize = 18;
-
-// The max order comes out to a largest size class of 1GiB pages.
-static_assertions::const_assert_eq!(4096 << MAX_ORDER, 1024 * 1024 * 1024);
diff --git a/kernel/src/allocators/buddy/stripe.rs b/kernel/src/allocators/buddy/stripe.rs
deleted file mode 100644
index 9ec5985..0000000
--- a/kernel/src/allocators/buddy/stripe.rs
+++ /dev/null
@@ -1,148 +0,0 @@
-use crate::allocators::{buddy::bitvec::BitVec, PAGE_SIZE_BITS};
-use core::ptr::NonNull;
-
-/// A single size class for a single region of the allocator. See the comment on the
-/// `crate::allocators::buddy` module for more information.
-pub struct Stripe<'buddy> {
- /// The base address of the tree this stripe is a part of.
- pub base: *const (),
-
- /// The order of the stripe. Order `n` means the subregions are `2ⁿ` pages in size.
- pub order: usize,
-
- /// The sentinel node of the free-list for this node. As an invariant of the type, there are no
- /// live references to any node in this list.
- pub free_list: NonNull<FreeListNode>,
-
- /// The bitset used to track whether a given subregion is allocated or not. A `true` bit
- /// corresponds to an allocated subregion.
- pub bitset: &'buddy mut BitVec,
-
- /// The offset from the start of the bitset to the region used by this stripe.
- pub bitset_offset: usize,
-}
-
-impl<'buddy> Stripe<'buddy> {
- /// Returns the buddy of the given pointer.
- ///
- /// ## Safety
- ///
- /// - The pointer must actually be part of this region.
- unsafe fn buddy_of(&self, ptr: NonNull<FreeListNode>) -> NonNull<FreeListNode> {
- let index = self.buddy_of_index(self.index_of(ptr));
- let addr = self.base as usize + (index << (PAGE_SIZE_BITS + self.order));
- NonNull::new_unchecked(addr as *mut FreeListNode)
- }
-
- /// Returns the buddy of the given index.
- fn buddy_of_index(&self, index: usize) -> usize {
- index ^ (1 << (PAGE_SIZE_BITS + self.order))
- }
-
- /// Returns the index the given pointer should have in the BitVec.
- fn index_of(&self, ptr: NonNull<FreeListNode>) -> usize {
- (ptr.as_ptr() as usize - self.base as usize) >> (PAGE_SIZE_BITS + self.order)
- }
-
- /// Pops a subregion from the free-list.
- pub fn pop(&mut self) -> Option<NonNull<FreeListNode>> {
- // SAFETY: The `free_list` is guaranteed to be valid by the invariants of the buddy
- // allocator. Retrieving the next pointer doesn't, on its own, break aliasing rules.
- let next = unsafe { self.free_list.read().next };
-
- // If the sentinel and the next pointer refer to the same spot, the free-list was empty, so
- // we can't pop from it.
- if self.free_list == next {
- return None;
- }
-
- // Otherwise, remove the node from the free-list.
- unsafe {
- FreeListNode::remove(next);
- }
-
- // Finally, mark the node as allocated in the bitvec.
- let index = self.index_of(next);
- assert!(self.bitset.get(self.bitset_offset + index));
- self.bitset.set(self.bitset_offset + index, true);
-
- Some(next)
- }
-
- /// Pushes a subregion back into the free-list.
- ///
- /// # Safety
- ///
- /// - There must be no live references to `subregion`.
- /// - `subregion` must not be a member of any list.
- pub unsafe fn push(&mut self, subregion: NonNull<FreeListNode>) {
- // Insert the subregion as the first element of the free-list.
- //
- // SAFETY: The free-list is guaranteed to be valid by the invariants of the buddy
- // allocator.
- unsafe {
- FreeListNode::insert(self.free_list, subregion);
- }
-
- // Mark the node as unallocated in the bitvec.
- let index = self.index_of(subregion);
- assert!(self.bitset.get(self.bitset_offset + index));
- self.bitset.set(self.bitset_offset + index, false);
- }
-
- /// Pushes a subregion into the free-list for the first time.
- ///
- /// # Safety
- ///
- /// - There must be no live references to `subregion`.
- /// - `subregion` must not be a member of any list.
- pub unsafe fn push_initial(&mut self, subregion: NonNull<FreeListNode>) {
- // Insert the subregion as the first element of the free-list.
- //
- // SAFETY: The free-list is guaranteed to be valid by the invariants of the buddy
- // allocator.
- unsafe {
- FreeListNode::insert(self.free_list, subregion);
- }
-
- // Mark the node as unallocated in the bitvec.
- let index = self.index_of(subregion);
- assert!(self.bitset.get(self.bitset_offset + index));
- self.bitset.set(self.bitset_offset + index, false);
- }
-}
-
-pub struct FreeListNode {
- next: NonNull<FreeListNode>,
- prev: NonNull<FreeListNode>,
-}
-
-impl FreeListNode {
- /// Inserts `new` after `prev`, initializing it. `prev` may be the sentinel.
- ///
- /// # Safety
- ///
- /// - There must be no live references to any node in the list that includes `prev`, including
- /// the sentinel.
- /// - There must be no live references to `new`.
- /// - `new` must not be a member of any list.
- pub unsafe fn insert(prev: NonNull<FreeListNode>, new: NonNull<FreeListNode>) {
- let next = prev.read().next;
- (*prev.as_ptr()).next = new;
- (*next.as_ptr()).prev = new;
- new.write(FreeListNode { next, prev });
- }
-
- /// Removes this node from the free list it is a part of.
- ///
- /// # Safety
- ///
- /// - The pointer must point to a node that is part of a free list.
- /// - There must be no live references to any node in the list, including the sentinel.
- /// - The pointer must not point to the sentinel node.
- pub unsafe fn remove(ptr: NonNull<FreeListNode>) {
- let FreeListNode { next, prev } = ptr.read();
- (*next.as_ptr()).prev = prev;
- (*prev.as_ptr()).next = next;
- }
-}
diff --git a/kernel/src/allocators/buddy/tree.rs b/kernel/src/allocators/buddy/tree.rs
deleted file mode 100644
index 3953f39..0000000
--- a/kernel/src/allocators/buddy/tree.rs
+++ /dev/null
@@ -1,112 +0,0 @@
-use crate::allocators::{
- buddy::{
- bitvec::BitVec,
- stripe::{FreeListNode, Stripe},
- MAX_ORDER,
- },
- PAGE_SIZE_BITS,
-};
-use contracts::requires;
-use core::ptr::NonNull;
-
-/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for
-/// more information.
-pub struct Tree<'buddy> {
- /// The base address of the tree.
- pub base: *const (),
-
- /// The log2 of the number of pages in the region represented by the tree.
- pub log2_page_count: usize,
-
- /// The array of sentinel nodes of the free-list for this node. As an invariant of the type,
- /// there are no live references to any node in any list in this array, and there are
- /// MAX_ORDER + 1 nodes.
- pub free_lists: NonNull<FreeListNode>,
-
- /// The bitset used to track whether subregion are allocated or not in this tree.
- pub bitset: &'buddy mut BitVec,
-}
-
-impl<'buddy> Tree<'buddy> {
- /// Tries to allocate a subregion with the given order, possibly splitting a larger subregion
- /// in order to so so.
- #[requires(order <= MAX_ORDER)]
- pub fn alloc(&mut self, order: usize) -> Option<NonNull<FreeListNode>> {
- if let Some(ptr) = self.stripe(order).pop() {
- Some(ptr)
- } else if order == MAX_ORDER {
- None
- } else {
- // Get a larger region.
- let ptr = self.alloc(order + 1)?;
-
- // Get a pointer to the higher half.
- //
- // SAFETY: This has to be in-bounds, it's part of the same allocation!
- let higher_half = unsafe { ptr.byte_add(1 << (PAGE_SIZE_BITS + order)) };
-
- // Put the higher half in the current buddy's stripe.
- //
- // SAFETY: The higher half is from this region, not in the higher stripe, and of the
- // right size.
- unsafe {
- self.stripe(order).push(higher_half);
- }
-
- // Return the pointer.
- Some(ptr)
- }
- }
-
- /// Returns the stripe with the given order.
- #[requires(order <= MAX_ORDER)]
- fn stripe<'stripe>(&'stripe mut self, order: usize) -> Stripe<'stripe> {
- // TODO: There should be some smart bitwise-math version of this...
- let mut bitset_offset = 0;
- for i in 0..order {
- bitset_offset += (1 << self.log2_page_count) >> i;
- }
-
- Stripe {
- base: self.base,
- order,
- // SAFETY: order is constrained to be in-bounds.
- free_list: unsafe { self.free_lists.add(order) },
- bitset: self.bitset,
- bitset_offset,
- }
- }
-}
-
-/// Evil bitwise version of the reasonable loop to compute the `bitset_offset` of a stripe.
-#[requires(log2_page_count < usize::BITS as usize)]
-#[requires(order < usize::BITS as usize)]
-fn compute_bitset_offset(log2_page_count: usize, order: usize) -> usize {
- let ones = |i: usize| !(usize::MAX << i);
-
- if order > log2_page_count + 1 {
- ones(log2_page_count + 1)
- } else {
- ones(order).wrapping_shl((log2_page_count + 1 - order) as u32)
- }
-}
-
-#[test]
-fn compute_bitset_offset_test() {
- fn compute_bitset_offset_loop(log2_page_count: usize, order: usize) -> usize {
- let mut bitset_offset = 0;
- for i in 0..order {
- bitset_offset += (1 << log2_page_count) >> i;
- }
- bitset_offset
- }
-
- for log2_page_count in 0..64 {
- for order in 0..64 {
- assert_eq!(
- compute_bitset_offset(log2_page_count, order),
- compute_bitset_offset_loop(log2_page_count, order),
- );
- }
- }
-}
diff --git a/kernel/src/allocators/mod.rs b/kernel/src/allocators/mod.rs
deleted file mode 100644
index 49f29e2..0000000
--- a/kernel/src/allocators/mod.rs
+++ /dev/null
@@ -1,24 +0,0 @@
-use core::{ffi::c_void, ops::Range, ptr::addr_of};
-
-pub mod buddy;
-pub mod physical_memory_free_list;
-
-/// The number of bits in the offset in a page.
-pub const PAGE_SIZE_BITS: usize = 12;
-
-/// The size of a page, in bytes.
-pub const PAGE_SIZE: usize = 1 << PAGE_SIZE_BITS;
-
-/// Returns the physical address range the kernel is in.
-pub fn kernel_boundaries() -> Range<usize> {
- extern "C" {
- static kernel_start: c_void;
- static kernel_end: c_void;
- }
-
- // SAFETY: We only use these as addresses, we never dereference them.
- let (kernel_start_addr, kernel_end_addr) =
- unsafe { (addr_of!(kernel_start), addr_of!(kernel_end)) };
-
- kernel_start_addr as usize..kernel_end_addr as usize
-}
diff --git a/kernel/src/allocators/physical_memory_free_list.rs b/kernel/src/allocators/physical_memory_free_list.rs
deleted file mode 100644
index 0d2f1b4..0000000
--- a/kernel/src/allocators/physical_memory_free_list.rs
+++ /dev/null
@@ -1,322 +0,0 @@
-//! A free-list allocator that runs in physical memory. This should only be used to bootstrap the
-//! buddy allocator for physical memory.
-
-use crate::{
- allocators::{kernel_boundaries, PAGE_SIZE, PAGE_SIZE_BITS},
- device_tree::FlattenedDeviceTree,
- prelude::*,
- util::ranges_overlap,
-};
-use contracts::requires;
-use core::{
- fmt, iter,
- ops::Range,
- ptr::{self, NonNull},
-};
-
-/// A free-list allocator that runs in physical memory. This should only be used to bootstrap the
-/// buddy allocator for physical memory.
-pub struct FreeList<'dt> {
- /// The DeviceTree the machine was booted with.
- device_tree: &'dt FlattenedDeviceTree<'dt>,
-
- /// The physical address of the head of the free-list allocator.
- ///
- /// The free-list is sorted by size, smallest to largest.
- head: Option<FreeListAddr>,
-
- /// The number of regions in the free-list.
- len: usize,
-}
-
-impl<'dt> FreeList<'dt> {
- /// Creates a new, empty free-list that checks addresses against the given DeviceTree.
- pub fn new(device_tree: &'dt FlattenedDeviceTree<'dt>) -> FreeList {
- let out = FreeList {
- device_tree,
- head: None,
- len: 0,
- };
-
- // Log the memory reservations.
- let reservation_count = out.iter_reserved().count();
- debug!(
- "found {} memory reservations{}",
- reservation_count,
- if reservation_count == 0 { "" } else { ":" }
- );
- for reservation in out.iter_reserved() {
- debug!(
- "{:p}..{:p} ({} byte{})",
- reservation.start as *const u8,
- reservation.end as *const u8,
- reservation.len(),
- if reservation.len() == 1 { "" } else { "s" }
- )
- }
-
- out
- }
-
- /// Adds a physical address range to the free-list allocator.
- ///
- /// ## Safety
- ///
- /// - This allocator must have been created with the DeviceTree that gave us this memory.
- /// - The region must be a valid physical memory range.
- /// - Paging must not be enabled for the entire lifetime of this allocator.
- pub unsafe fn add_range(&mut self, mut addrs: Range<usize>) {
- // Clamp the range, so that we can't somehow end up with the zero address or with
- // higher-half addresses.
- addrs.start = addrs.start.max(1);
- addrs.end = addrs.end.min(isize::MAX as usize);
-
- // Trim the range to be page-aligned.
- addrs.start = (addrs.start + (PAGE_SIZE - 1)) & !(PAGE_SIZE - 1);
- addrs.end &= !(PAGE_SIZE - 1);
-
- // Add each unreserved subrange to the allocator's list.
- loop {
- assert_eq!(addrs.start & (PAGE_SIZE - 1), 0);
- assert_eq!(addrs.end & (PAGE_SIZE - 1), 0);
-
- // Walk forwards until the first page is unreserved.
- loop {
- // Ensure the range is non-empty.
- if addrs.end <= addrs.start {
- return;
- }
-
- // If the start of the range is reserved, walk forwards a page.
- let first_page = addrs.start..addrs.start + PAGE_SIZE;
- if self
- .iter_reserved()
- .any(|range| ranges_overlap(&range, &first_page))
- {
- addrs.start = first_page.end;
- } else {
- break;
- }
- }
-
- // Find the first reservation that overlaps.
- if let Some(reservation) = self
- .iter_reserved()
- .filter(|range| ranges_overlap(range, &addrs))
- .min_by_key(|range| range.start)
- {
- // Get the range that's before the reservation.
- let mut unreserved = addrs.start..reservation.start;
-
- // Trim the range to be page-aligned. We don't need to trim the start, because
- // addrs.start is already aligned (by our loop invariant).
- unreserved.end &= !(PAGE_SIZE - 1);
-
- // Add the range up to the start of that overlap.
- self.add_range_unchecked(unreserved);
-
- // Adjust the remaining range to be after the overlap.
- addrs.start = reservation.end;
-
- // Trim the range to be page-aligned. We don't need to trim the end, because it's
- // unchanged.
- addrs.start = (addrs.start + (PAGE_SIZE - 1)) & !(PAGE_SIZE - 1);
- } else {
- // If no range overlaps, the entire remaining range is valid.
- self.add_range_unchecked(addrs);
- return;
- }
- }
- }
-
- /// Adds a physical address range to the free-list allocator, without checking for reservations
- /// inside it.
- ///
- /// ## Safety
- ///
- /// - This allocator must have been created with the DeviceTree that gave us this memory.
- /// - The region must be a valid physical memory range.
- /// - The region must be page-aligned.
- /// - The region must not overlap with any reservations.
- /// - Paging must not be enabled for the entire lifetime of this allocator.
- pub unsafe fn add_range_unchecked(&mut self, addrs: Range<usize>) {
- // Initialize the list node.
- let mut new_node = FreeListAddr::new(addrs);
-
- // Walk forwards through the list until the node we're going to put ourselves before has a
- // size greater or equal to ours.
- let mut spot_to_store = &mut self.head;
- while let Some(existing_node) = spot_to_store {
- if existing_node.pages_after() < new_node.pages_after() {
- spot_to_store = spot_to_store.as_mut().unwrap().next_mut();
- } else {
- break;
- }
- }
-
- *new_node.next_mut() = spot_to_store.take();
- *spot_to_store = Some(new_node);
- self.len += 1;
- }
-
- /// Returns an iterator that removes ranges from the free-list. Ranges are returned sorted from
- /// smallest to largest.
- pub fn drain<'iter: 'dt>(&'iter mut self) -> impl 'dt + Iterator<Item = Range<usize>> {
- iter::from_fn(move || self.pop())
- }
-
- /// Returns whether the free-list is empty.
- pub fn is_empty(&self) -> bool {
- self.len == 0
- }
-
- /// Returns an iterator over the reserved ranges of addresses.
- ///
- /// Addresses may be reserved by:
- ///
- /// - Overlapping with the kernel, including the early-boot kernel stack.
- /// - Overlapping with the DeviceTree.
- /// - Overlapping with any memory reservations in the DeviceTree.
- fn iter_reserved(&self) -> impl '_ + Iterator<Item = Range<usize>> {
- // Get the boundaries of the kernel.
- let kernel = kernel_boundaries();
-
- // As a sanity check, make sure this function is inside those boundaries...
- assert!(kernel.contains(&(FreeList::iter_reserved as usize)));
-
- // Check if the address is either in the kernel or somewhere in the DeviceTree.
- iter::once(kernel).chain(self.device_tree.iter_reserved())
- }
-
- /// Returns the number of regions in the free-list.
- pub fn len(&self) -> usize {
- self.len
- }
-
- /// Pops the smallest range from the free-list, returning it.
- pub fn pop(&mut self) -> Option<Range<usize>> {
- match self.head.take() {
- Some(head) => {
- let (addrs, next) = head.take();
- self.head = next;
- Some(addrs)
- }
- None => None,
- }
- }
-}
-
-impl<'dt> fmt::Debug for FreeList<'dt> {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- struct FreeListDebug<'a>(&'a Option<FreeListAddr>);
-
- impl<'a> fmt::Debug for FreeListDebug<'a> {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- let mut addr = self.0;
- fmt.debug_list()
- .entries(iter::from_fn(|| match addr {
- Some(head) => {
- addr = head.next();
- Some(head)
- }
- None => None,
- }))
- .finish()
- }
- }
-
- fmt.debug_struct("FreeList")
- .field("device_tree", &self.device_tree)
- .field("addrs", &FreeListDebug(&self.head))
- .finish()
- }
-}
-
-/// An address in the free-list.
-///
-/// # Invariants
-///
-/// - The pointer must point to physical memory.
-/// - The FreeListHeader must be initialized.
-/// - The region being pointed to must actually be free.
-/// - The region being pointed to must be unreserved.
-struct FreeListAddr(NonNull<FreeListHeader>);
-
-impl FreeListAddr {
- /// Initializes the page with the given address range, with no next address.
- ///
- /// # Safety
- ///
- /// - All of the invariants in the struct-level documentation, except the header being
- /// initialized (this function will initialize it).
- #[requires(addrs.start != 0)]
- #[requires(addrs.start & (PAGE_SIZE - 1) == 0)]
- #[requires(addrs.end & (PAGE_SIZE - 1) == 0)]
- #[requires(addrs.start < addrs.end)]
- unsafe fn new(addrs: Range<usize>) -> FreeListAddr {
- let addr = addrs.start;
- *(addr as *mut FreeListHeader) = FreeListHeader {
- next: None,
- pages_after: ((addrs.end - addrs.start) >> PAGE_SIZE_BITS) - 1,
- };
-
- FreeListAddr(NonNull::new_unchecked(addr as *mut FreeListHeader))
- }
-
- /// Returns the `next` field of the header.
- fn next(&self) -> &Option<FreeListAddr> {
- // SAFETY: The invariants of FreeListAddr::new are sufficient to make this valid.
- unsafe { &self.0.as_ref().next }
- }
-
- /// Returns a mutable reference to the `next` field of the header.
- fn next_mut(&mut self) -> &mut Option<FreeListAddr> {
- // SAFETY: The invariants of FreeListAddr::new are sufficient to make this valid.
- unsafe { &mut self.0.as_mut().next }
- }
-
- /// Returns the number of pages *after* the first one in this region.
- fn pages_after(&self) -> usize {
- // SAFETY: The invariants of FreeListAddr::new are sufficient to make this valid.
- unsafe { self.0.as_ref().pages_after }
- }
-
- /// Returns the range of addresses in the region and the address of the next region.
- fn take(self) -> (Range<usize>, Option<FreeListAddr>) {
- let start = self.0.as_ptr() as usize;
- let len_pages = 1 + self.pages_after();
- let len_bytes = len_pages << PAGE_SIZE_BITS;
- let addrs = start..start + len_bytes;
-
- // SAFETY: The invariants of FreeListAddr::new are sufficient to make the read valid.
- // Because we drop the address, we know we won't accidentally have any ownership issues
- // with passing ownership up.
- let header = unsafe { ptr::read(self.0.as_ptr()) };
-
- (addrs, header.next)
- }
-}
-
-impl fmt::Debug for FreeListAddr {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- let addr = self.0.as_ptr() as *const u8;
- let len_pages = 1 + self.pages_after();
- let len_bytes = len_pages << PAGE_SIZE_BITS;
- write!(
- fmt,
- "{:p}..{:p} ({} page{})",
- addr,
- addr.wrapping_add(len_bytes),
- len_pages,
- if len_pages == 1 { "" } else { "s" }
- )
- }
-}
-
-struct FreeListHeader {
- /// The physical address of the next free-list header.
- next: Option<FreeListAddr>,
-
- /// The number of pages after this one.
- pages_after: usize,
-}
diff --git a/kernel/src/arch/hosted/mod.rs b/kernel/src/arch/hosted/mod.rs
deleted file mode 100644
index c1fb0ff..0000000
--- a/kernel/src/arch/hosted/mod.rs
+++ /dev/null
@@ -1,19 +0,0 @@
-//! Support for running under an operating system that provides libstd, for testing.
-
-extern crate std;
-
-use std::{thread::sleep, time::Duration};
-
-/// No-opped interrupt support.
-///
-/// TODO: Should this use Unix signals?
-pub mod interrupts {
- pub fn disable_interrupts() {}
-}
-
-/// Sleeps forever, in one-second chunks.
-pub fn sleep_forever() -> ! {
- loop {
- sleep(Duration::from_secs(1));
- }
-}
diff --git a/kernel/src/arch/mod.rs b/kernel/src/arch/mod.rs
deleted file mode 100644
index d23dd81..0000000
--- a/kernel/src/arch/mod.rs
+++ /dev/null
@@ -1,9 +0,0 @@
-cfg_if::cfg_if! {
- if #[cfg(not(target_os = "none"))] {
- mod hosted;
- pub use self::hosted::*;
- } else if #[cfg(target_arch = "riscv64")] {
- mod riscv64;
- pub use self::riscv64::*;
- }
-}
diff --git a/kernel/src/arch/riscv64/interrupts.rs b/kernel/src/arch/riscv64/interrupts.rs
deleted file mode 100644
index 302fc4f..0000000
--- a/kernel/src/arch/riscv64/interrupts.rs
+++ /dev/null
@@ -1,82 +0,0 @@
-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/arch/riscv64/mod.rs b/kernel/src/arch/riscv64/mod.rs
deleted file mode 100644
index 32731e8..0000000
--- a/kernel/src/arch/riscv64/mod.rs
+++ /dev/null
@@ -1,8 +0,0 @@
-pub mod interrupts;
-
-/// Halts the hart.
-pub fn sleep_forever() -> ! {
- loop {
- unsafe { core::arch::asm!("wfi") }
- }
-}
diff --git a/kernel/src/collections/mod.rs b/kernel/src/collections/mod.rs
deleted file mode 100644
index ebcfad3..0000000
--- a/kernel/src/collections/mod.rs
+++ /dev/null
@@ -1,3 +0,0 @@
-//! 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
deleted file mode 100644
index 19b9272..0000000
--- a/kernel/src/collections/stack_linked_list.rs
+++ /dev/null
@@ -1,78 +0,0 @@
-//! 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>(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)))
- }
-
- /// Attempts to return the head and tail of the list.
- pub fn uncons(&self) -> Option<(&T, &'list StackLinkedList<'list, T>)> {
- let (hd, tl) = self.0.as_ref()?;
- Some((hd, tl))
- }
-
- /// 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()
- }
-}
-
-impl<'list, T: Copy> IntoIterator for StackLinkedList<'list, T> {
- type Item = T;
-
- type IntoIter = OwnedIter<'list, T>;
-
- fn into_iter(self) -> OwnedIter<'list, T> {
- OwnedIter(self)
- }
-}
-
-/// An (owned) iterator over a `StackLinkedList`.
-#[derive(Clone)]
-pub struct OwnedIter<'list, T>(StackLinkedList<'list, T>);
-
-impl<'list, T: Copy> Iterator for OwnedIter<'list, T> {
- type Item = T;
-
- fn next(&mut self) -> Option<T> {
- match (self.0).0 {
- Some((hd, tl)) => {
- self.0 = *tl;
- Some(hd)
- }
- None => None,
- }
- }
-}
diff --git a/kernel/src/device_tree.rs b/kernel/src/device_tree.rs
deleted file mode 100644
index c045cfd..0000000
--- a/kernel/src/device_tree.rs
+++ /dev/null
@@ -1,641 +0,0 @@
-//! Support for the DeviceTree format.
-
-use crate::{collections::stack_linked_list::StackLinkedList, prelude::*, util::FromEndianBytes};
-use bstr::BStr;
-use contracts::requires;
-use core::{
- fmt, iter,
- num::ParseIntError,
- ops::Range,
- slice,
- str::{self, Utf8Error},
-};
-use either::Either;
-
-/// A reference to a flattened DeviceTree (DTB) in memory.
-pub struct FlattenedDeviceTree<'dt> {
- header: &'dt FdtHeader,
- struct_block: &'dt [u32],
- strings_block: &'dt BStr,
- memrsv_block: &'dt [FdtMemRsv],
-}
-
-impl<'dt> FlattenedDeviceTree<'dt> {
- /// Looks for a DeviceTree at the given address, and returns it if it looks valid.
- ///
- /// # Safety
- ///
- /// - `ptr` must point to a spec-compliant flattened DeviceTree.
- /// - The memory contained by the flattened DeviceTree must be valid for the duration of
- /// lifetime `'dt`.
- /// - The memory contained by the flattened DeviceTree must not be mutated for the duration of
- /// lifetime `'dt`.
- #[requires((ptr as *const FdtHeader).is_aligned())]
- pub unsafe fn from_ptr(ptr: *const u8) -> Result<FlattenedDeviceTree<'dt>, DeviceTreeError> {
- // Check that the header appears to point to a valid flattened DeviceTree.
- let header: &'dt FdtHeader = &*(ptr as *const FdtHeader);
- let magic = u32::from_be(header.magic);
- if magic != 0xd00dfeed {
- return Err(DeviceTreeError::BadMagic(magic));
- }
- let version = u32::from_be(header.version);
- let last_comp_version = u32::from_be(header.last_comp_version);
- if last_comp_version > 17 {
- return Err(DeviceTreeError::IncompatibleVersion(
- version,
- last_comp_version,
- ));
- }
-
- // Get pointers to each block.
- let off_dt_struct = u32::from_be(header.off_dt_struct) as usize;
- let size_dt_struct = u32::from_be(header.size_dt_struct) as usize;
- let off_dt_strings = u32::from_be(header.off_dt_strings) as usize;
- let size_dt_strings = u32::from_be(header.size_dt_strings) as usize;
- let off_mem_rsvmap = u32::from_be(header.off_mem_rsvmap) as usize;
-
- // Check that the structure block has an aligned size.
- if (size_dt_struct & 0b11) != 0 {
- return Err(DeviceTreeError::InvalidDeviceTree);
- }
-
- // Extract the structure and strings blocks.
- let struct_block: &[u32] =
- slice::from_raw_parts(ptr.add(off_dt_struct).cast(), size_dt_struct / 4);
- let strings_block = BStr::new(slice::from_raw_parts(
- ptr.add(off_dt_strings),
- size_dt_strings,
- ));
-
- // Read memory reservations until the terminating one is found, then construct the block of
- // the appropriate length.
- let mut memrsv_count = 0;
- let memrsv_ptr: *const FdtMemRsv = ptr.add(off_mem_rsvmap).cast();
- let memrsv_block = loop {
- let memrsv = *memrsv_ptr.add(memrsv_count);
-
- // We can skip the endian conversion, since we're just testing against zero.
- if memrsv == (FdtMemRsv { addr: 0, size: 0 }) {
- break slice::from_raw_parts(memrsv_ptr, memrsv_count);
- }
-
- memrsv_count += 1;
- };
-
- // Try parsing all of the events in the structure block, so we can report errors from doing
- // so before anything outside this module can get their hands on them.
- let fdt = FlattenedDeviceTree {
- header,
- struct_block,
- strings_block,
- memrsv_block,
- };
- fdt.iter_struct_events_from(0)
- .try_for_each(|r| r.map(|_| ()))?;
-
- // Check that the overall structure of the structure block is correct, so we don't need to
- // worry about errors later.
- for_each_node(&fdt, &mut |_| Ok(()), &|err| err, 0, StackLinkedList::NIL)?;
-
- Ok(fdt)
- }
-
- /// Returns the string at the given offset of the strings block.
- fn get_string(&self, offset: u32) -> Result<&BStr, DeviceTreeError> {
- let out = &self.strings_block[offset as usize..];
- let i = out
- .iter()
- .position(|&b| b == b'\0')
- .ok_or(DeviceTreeError::StringMissingNulTerminator(offset))?;
- Ok(&out[..i])
- }
-
- /// Parses nodes out of a flattened DeviceTree and calls the function with each one. This does
- /// not allocate memory, and may be called before the allocator is configured (at the cost of
- /// decreased performance).
- pub fn for_each_node<E>(
- &'dt self,
- mut func: impl for<'a> FnMut(FdtNode<'dt, 'a>) -> Result<(), E>,
- ) -> Result<(), E> {
- for_each_node(
- self,
- &mut func,
- &|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"),
- 0,
- StackLinkedList::NIL,
- )?;
- Ok(())
- }
-
- /// Returns an iterator over the reserved ranges of addresses.
- ///
- /// Addresses may be reserved by:
- ///
- /// - Overlapping with the DeviceTree itself.
- /// - Overlapping with any memory reservations in the DeviceTree.
- pub fn iter_reserved(&self) -> impl '_ + Iterator<Item = Range<usize>> {
- // Make the address range of the DeviceTree.
- let dt_start = self.header as *const FdtHeader as usize;
- let dt_end = dt_start + u32::from_be(self.header.totalsize) as usize;
-
- iter::once(dt_start..dt_end).chain(self.memrsv_block.iter().map(|memrsv| {
- let addr = u64::from_be(memrsv.addr) as usize;
- let size = u64::from_be(memrsv.size) as usize;
- addr..addr + size
- }))
- }
-
- /// Returns an iterator over the events in the structure block of the DeviceTree, starting at
- /// the current offset from the start of the structure block.
- ///
- /// Panics if the offset is out-of-bounds.
- fn iter_struct_events_from<'iter: 'dt>(
- &'iter self,
- start: u32,
- ) -> impl 'iter + Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>> {
- let mut i = start;
- iter::from_fn(move || match self.next_struct_event_from(i) {
- Some(Ok((next, event))) => {
- let prev = i;
- assert!(prev < next);
- i = next;
- Some(Ok(event))
- }
- Some(Err(err)) => Some(Err(err)),
- None => None,
- })
- }
-
- /// Parses a single point in the structure block of the DeviceTree, returning the offset to
- /// parse at next and the parse event.
- ///
- /// Panics if the offset is out-of-bounds.
- fn next_struct_event_from<'iter: 'dt>(
- &'iter self,
- mut offset: u32,
- ) -> Option<Result<(u32, FdtStructEvent<'dt>), DeviceTreeError>> {
- loop {
- // Read the token type and advance the offset.
- let token_type = u32::from_be(*self.struct_block.get(offset as usize)?);
- offset += 1;
-
- // Branch on the token type to recognize an event.
- let event = match token_type {
- // FDT_BEGIN_NODE
- 0x00000001 => {
- // Save a pointer to the start of the extra data.
- let name_ptr = (&self.struct_block[offset as usize]) as *const u32 as *const u8;
-
- // Look for a null terminator. `name_len` is the length of the name, _without_
- // the null terminator.
- //
- // SAFETY: This method can only be called when the FlattenedDeviceTree was
- // constructed from a valid flattened DeviceTree.
- let mut name_len = 0;
- while unsafe { *name_ptr.add(name_len) } != b'\0' {
- name_len += 1;
- }
-
- // Create the name as a BStr.
- //
- // SAFETY: Well, we already accessed this memory above when finding the null
- // terminator... But yes, this being valid is guaranteed by this being a
- // flattened DeviceTree.
- let name = BStr::new(unsafe { slice::from_raw_parts(name_ptr, name_len) });
-
- // Parse the name.
- let Ok(name) = FdtNodeName::parse(name) else {
- return Some(Err(DeviceTreeError::InvalidNodeName));
- };
-
- // Compute the count and advance the offset.
- offset += (name_len as u32 + 4) >> 2;
-
- // Create the event.
- FdtStructEvent::BeginNode(name)
- }
- // FDT_END_NODE
- 0x00000002 => FdtStructEvent::EndNode,
- // FDT_PROP
- 0x00000003 => {
- // Get the length of the property data and the offset of the name in the
- // strings block.
- let data_len = u32::from_be(self.struct_block[offset as usize]) as usize;
- let name_off = u32::from_be(self.struct_block[offset as usize + 1]);
- offset += 2;
-
- // Get the property data as a BStr.
- //
- // SAFETY: This is valid by the requirements of a flattened DeviceTree.
- //
- // TODO: We could refactor this out to a to_bytes call plus a bounds-checked
- // slicing operation to get a _bit_ of safety back, at least...
- let data = BStr::new(unsafe {
- slice::from_raw_parts(
- &self.struct_block[offset as usize] as *const u32 as *const u8,
- data_len,
- )
- });
-
- // Advance past the property data.
- offset += (data_len as u32 + 3) >> 2;
-
- // Get the property name as a BStr.
- let name = match self.get_string(name_off) {
- Ok(name) => name,
- Err(err) => return Some(Err(err)),
- };
-
- // Create the event.
- FdtStructEvent::Prop(name, data)
- }
- // FDT_NOP
- 0x00000004 => continue,
- // FDT_END
- 0x00000009 => return None,
- _ => return Some(Err(DeviceTreeError::InvalidTokenType(token_type))),
- };
-
- // Return the new offset and the event.
- return Some(Ok((offset, event)));
- }
- }
-}
-
-impl<'dt> fmt::Debug for FlattenedDeviceTree<'dt> {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- let addr = self.header as *const FdtHeader;
- // Intentionally not using `fmt.debug_tuple`, it's wasted space here.
- write!(fmt, "FlattenedDeviceTree::from_ptr({addr:p})")
- }
-}
-
-/// An error encountered when reading a DeviceTree.
-#[derive(Debug)]
-pub enum DeviceTreeError {
- BadMagic(u32),
- IncompatibleVersion(u32, u32),
- InvalidDeviceTree,
- InvalidNodeName,
- InvalidTokenType(u32),
- StringMissingNulTerminator(u32),
-
- UnexpectedEndOfStructBlock,
- UnexpectedEvent,
-}
-
-/// The flattened DeviceTree header.
-///
-/// All fields are big-endian.
-#[derive(Debug)]
-#[repr(C)]
-struct FdtHeader {
- magic: u32,
- totalsize: u32,
- off_dt_struct: u32,
- off_dt_strings: u32,
- off_mem_rsvmap: u32,
- version: u32,
- last_comp_version: u32,
- boot_cpuid_phys: u32,
- size_dt_strings: u32,
- size_dt_struct: u32,
-}
-
-/// A memory reservation from the appropriate block of the DeviceTree.
-///
-/// All fields are big-endian.
-#[derive(Clone, Copy, Debug, Eq, PartialEq)]
-#[repr(C)]
-struct FdtMemRsv {
- addr: u64,
- size: u64,
-}
-
-/// An event returned from iterating over the structure block of a flattened DeviceTree.
-#[derive(Clone, Copy, Debug)]
-enum FdtStructEvent<'dt> {
- BeginNode(FdtNodeName<'dt>),
- EndNode,
- Prop(&'dt BStr, &'dt BStr),
-}
-
-/// The name of a node.
-#[derive(Clone, Copy, Debug, Eq, PartialEq)]
-pub struct FdtNodeName<'dt> {
- /// The full name, including the unit address.
- pub full_name: &'dt BStr,
-
- // The length of the unit name (i.e., the part of the name before the unit address).
- unit_name_len: usize,
-
- /// The address of the node.
- pub unit_address: Option<u64>,
-}
-
-impl<'dt> FdtNodeName<'dt> {
- /// Returns the unit name; i.e., the part of the name that does not include the unit address.
- pub fn unit_name(&self) -> &'dt BStr {
- &self.full_name[..self.unit_name_len]
- }
-
- /// Parses an `FdtNodeName` from bytes.
- pub fn parse(bytes: &'dt BStr) -> Result<FdtNodeName<'dt>, Either<ParseIntError, Utf8Error>> {
- if let Some(at_sign_index) = bytes.iter().position(|&b| b == b'@') {
- let unit_address =
- str::from_utf8(&bytes[at_sign_index + 1..]).map_err(Either::Right)?;
- let unit_address = u64::from_str_radix(unit_address, 16).map_err(Either::Left)?;
- Ok(FdtNodeName {
- full_name: bytes,
- unit_name_len: at_sign_index,
- unit_address: Some(unit_address),
- })
- } else {
- Ok(FdtNodeName {
- full_name: bytes,
- unit_name_len: bytes.len(),
- unit_address: None,
- })
- }
- }
-}
-
-impl<'dt> fmt::Display for FdtNodeName<'dt> {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- write!(fmt, "{}", self.full_name)
- }
-}
-
-/// A reference to a node in a flattened DeviceTree.
-#[derive(Clone, Copy)]
-pub struct FdtNode<'dt, 'iter> {
- fdt: &'dt FlattenedDeviceTree<'dt>,
- index: u32,
- parents: StackLinkedList<'iter, u32>,
-}
-
-impl<'dt, 'iter> FdtNode<'dt, 'iter> {
- /// A constructor that checks the type's invariants.
- #[requires(matches!(
- fdt.next_struct_event_from(index),
- Some(Ok((_, FdtStructEvent::BeginNode(_)))))
- )]
- #[requires(parents.into_iter().all(|parent| {
- matches!(
- fdt.next_struct_event_from(parent),
- Some(Ok((_, FdtStructEvent::BeginNode(_))))
- )
- }))]
- fn new(
- fdt: &'dt FlattenedDeviceTree<'dt>,
- index: u32,
- parents: StackLinkedList<'iter, u32>,
- ) -> FdtNode<'dt, 'iter> {
- FdtNode {
- fdt,
- index,
- parents,
- }
- }
-
- /// Returns the value corresponding to a prop name for this node.
- pub fn get_prop<U>(&self, name: U) -> Option<&'dt BStr>
- where
- BStr: PartialEq<U>,
- {
- self.iter_props().find(|&(k, _)| k == &name).map(|(_, v)| v)
- }
-
- /// Returns the value corresponding to a prop name for this node as a big-endian `u32`.
- pub fn get_prop_u32<U>(&self, name: U) -> Option<u32>
- where
- BStr: PartialEq<U>,
- U: Copy + fmt::Display,
- {
- let value = self.get_prop(name)?;
- if value.len() != 4 {
- warn!(
- "{}{} was expected to be 4 bytes, but was {:?}",
- self.name(),
- name,
- value
- );
- return None;
- }
- let value = value.first_chunk()?;
- Some(u32::from_be_bytes(*value))
- }
-
- /// Returns the `reg` property of this node as an iterator over `(addr, size)` pairs.
- pub fn get_reg(&self) -> Option<impl Iterator<Item = (&'dt BStr, &'dt BStr)>> {
- // Get the parent node.
- let Some(parent) = self.parent() else {
- warn!("{} did not have a parent", self.name());
- return None;
- };
-
- // Get the size of addresses and sizes from the parent.
- let Some(address_cells) = parent.get_prop_u32("#address-cells") else {
- warn!(
- "{} did not have a valid #address-cells property",
- parent.name()
- );
- return None;
- };
- let Some(size_cells) = parent.get_prop_u32("#size-cells") else {
- warn!(
- "{} did not have a valid #size-cells property",
- parent.name()
- );
- return None;
- };
-
- // Convert the numbers to bytes.
- let address_size = (address_cells << 2) as usize;
- let size_size = (size_cells << 2) as usize;
-
- // Get the `reg` property's value.
- let value = self.get_prop("reg")?;
- if value.len() % (address_size + size_size) != 0 {
- warn!(
- "{}reg was expected to be a multiple of ({} + {}) bytes, but was {:?}",
- self.name(),
- address_size,
- size_size,
- value,
- );
- return None;
- }
-
- Some(
- (0..value.len())
- .step_by(address_size + size_size)
- .map(move |i| {
- (
- &value[i..i + address_size],
- &value[i + address_size..i + address_size + size_size],
- )
- }),
- )
- }
-
- /// Returns the `reg` property of this node as an iterator over `(addr, size)` pairs, requiring
- /// that they're correctly-sized for `usize`s.
- pub fn get_reg_usize(&self) -> Option<impl 'dt + Iterator<Item = (usize, usize)>> {
- let iter = self.get_reg()?.map(|(addr, size)| {
- (
- usize::from_big_endian_bytes(addr),
- usize::from_big_endian_bytes(size),
- )
- });
- Some(iter)
- }
-
- /// Returns whether the unit path (i.e., the path to this node, only taking unit names) matches
- /// the argument.
- pub fn is_unit<U>(&self, name: &[U]) -> bool
- where
- BStr: PartialEq<U>,
- {
- self.iter_names_rev()
- .map(|name| name.unit_name())
- .eq(name.iter().rev())
- }
-
- /// Returns an iterator over the properties of the node.
- pub fn iter_props(&self) -> impl '_ + Iterator<Item = (&'dt BStr, &'dt BStr)> {
- // Skip the BeginNode.
- let offset = match self.fdt.next_struct_event_from(self.index) {
- Some(Ok((offset, FdtStructEvent::BeginNode(_)))) => offset,
- _ => unreachable!("checked in FlattenedDeviceTree::from_ptr"),
- };
-
- // Yield Prop nodes as long as we can get them.
- self.fdt
- .iter_struct_events_from(offset)
- .map_while(|r| match r {
- Ok(FdtStructEvent::Prop(key, value)) => Some((key, value)),
- Ok(FdtStructEvent::BeginNode(_) | FdtStructEvent::EndNode) => None,
- Err(_) => unreachable!("checked in FlattenedDeviceTree::from_ptr"),
- })
- }
-
- /// Returns a value that can be `Display`ed as the fully-qualified name of the node.
- pub fn name(&self) -> impl '_ + fmt::Display {
- struct NameDisplay<'a, 'dt, 'iter>(&'a FdtNode<'dt, 'iter>);
-
- impl<'a, 'dt, 'iter> fmt::Display for NameDisplay<'a, 'dt, 'iter> {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- fn fmt_name_rev<'dt>(
- fmt: &mut fmt::Formatter,
- mut iter: impl Iterator<Item = FdtNodeName<'dt>>,
- ) -> fmt::Result {
- match iter.next() {
- Some(name) => {
- fmt_name_rev(fmt, iter)?;
- write!(fmt, "{name}/")
- }
- None => Ok(()),
- }
- }
-
- fmt_name_rev(fmt, self.0.iter_names_rev())
- }
- }
-
- NameDisplay(self)
- }
-
- /// Returns the parent of this node.
- pub fn parent(&self) -> Option<FdtNode<'dt, 'iter>> {
- let (&hd, &tl) = self.parents.uncons()?;
- Some(FdtNode::new(self.fdt, hd, tl))
- }
-
- /// Returns an iterator over the names of the node and its parents, in reverse order.
- fn iter_names_rev(&self) -> impl '_ + Clone + Iterator<Item = FdtNodeName<'dt>> {
- self.parents.cons(self.index).into_iter().map(move |i| {
- match self.fdt.next_struct_event_from(i) {
- Some(Ok((_, FdtStructEvent::BeginNode(name)))) => name,
- _ => unreachable!("checked in FlattenedDeviceTree::from_ptr"),
- }
- })
- }
-}
-
-impl<'dt, 'iter> fmt::Debug for FdtNode<'dt, 'iter> {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- write!(fmt, "{} ", self.name())?;
- fmt.debug_map().entries(self.iter_props()).finish()
- }
-}
-
-/// Parses nodes out of a flattened DeviceTree and calls the function with each one. This does not
-/// allocate memory, and may be called before the allocator is configured (at the cost of decreased
-/// performance). Returns the offset after parsing the one starting at `index`.
-///
-/// - `'dt` is the lifetime of the DeviceTree.
-/// - `'a` is the lifetime of this function call.
-/// - `'b` is the lifetime of the recursive call to this function that parses its children.
-///
-/// - `E` is the type of errors. We do a pass in `FlattenedDeviceTree::from_ptr` with this as
-/// `DeviceTreeError` (and a `func` that's a no-op) to find any errors we might encounter. In
-/// actual user invocations of this function, it's replaced with the actual user error type (and
-/// `on_error` panics).
-///
-/// - `fdt` is flattened DeviceTree we're parsing inside.
-/// - `func` is the callback to call with nodes.
-/// - `on_error` is a function to call to convert a `DeviceTreeError` to an `E`.
-/// - `index` is the index of the word in the structure block to start parsing at.
-/// - `parents` is an accumulated list of the indices of nodes that are parents of this one.
-fn for_each_node<'dt, 'iter, E>(
- fdt: &'dt FlattenedDeviceTree<'dt>,
- func: &mut impl for<'a> FnMut(FdtNode<'dt, 'a>) -> Result<(), E>,
- on_error: &impl Fn(DeviceTreeError) -> E,
- index: u32,
- parents: StackLinkedList<'iter, u32>,
-) -> Result<u32, E> {
- // Read the first event, which should be the BeginNode starting the node we're trying to read.
- // We need to ensure that `index` refers to a `BeginNode` so that methods on `FdtNode` (e.g.
- // `iter_names_rev`) can rely on this. We also take as an inductive invariant that every index
- // in `parents` refers to a valid `BeginNode`.
- let (mut offset, event) = fdt
- .next_struct_event_from(index)
- .ok_or_else(|| on_error(DeviceTreeError::UnexpectedEndOfStructBlock))?
- .unwrap_or_else(|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"));
- if !matches!(event, FdtStructEvent::BeginNode(_)) {
- dbg!((event, index, parents));
- return Err(on_error(DeviceTreeError::UnexpectedEvent));
- }
-
- // Create the node and call the callback with it.
- func(FdtNode::new(fdt, index, parents))?;
-
- // Create a new parents list that includes this node.
- let new_parents = parents.cons(index);
-
- // Advance past any prop events.
- loop {
- let (next_offset, event) = fdt
- .next_struct_event_from(offset)
- .ok_or_else(|| on_error(DeviceTreeError::UnexpectedEndOfStructBlock))?
- .unwrap_or_else(|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"));
- if !matches!(event, FdtStructEvent::Prop(_, _)) {
- break;
- }
- offset = next_offset;
- }
-
- // Until we find an end node, parse child nodes.
- loop {
- let (next_offset, event) = fdt
- .next_struct_event_from(offset)
- .ok_or_else(|| on_error(DeviceTreeError::UnexpectedEndOfStructBlock))?
- .unwrap_or_else(|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"));
- if matches!(event, FdtStructEvent::EndNode) {
- break Ok(next_offset);
- }
-
- offset = for_each_node(fdt, func, on_error, offset, new_parents)?;
- }
-}
diff --git a/kernel/src/drivers/mod.rs b/kernel/src/drivers/mod.rs
deleted file mode 100644
index 2ccd5ae..0000000
--- a/kernel/src/drivers/mod.rs
+++ /dev/null
@@ -1,2 +0,0 @@
-#[cfg(target_arch = "riscv64")]
-pub mod riscv_timer;
diff --git a/kernel/src/drivers/riscv_timer.rs b/kernel/src/drivers/riscv_timer.rs
deleted file mode 100644
index a702f7b..0000000
--- a/kernel/src/drivers/riscv_timer.rs
+++ /dev/null
@@ -1,43 +0,0 @@
-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/lib.rs b/kernel/src/lib.rs
deleted file mode 100644
index e369864..0000000
--- a/kernel/src/lib.rs
+++ /dev/null
@@ -1,99 +0,0 @@
-#![no_std]
-
-#[macro_use]
-pub mod util;
-
-pub mod allocators;
-pub mod arch;
-pub mod collections;
-pub mod console;
-pub mod device_tree;
-pub mod drivers;
-mod panic;
-pub mod prelude;
-
-use crate::{allocators::physical_memory_free_list::FreeList, arch::sleep_forever, 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.
-///
-/// # Safety
-///
-/// - The `device_tree` pointer must be a valid pointer into physical memory. See
-/// `device_tree::FlattenedDeviceTree::from_ptr` for the precise requirements.
-/// - This must be called in supervisor mode with paging and traps disabled, but with all traps
-/// delegated to supervisor mode.
-/// - Any other harts must not be running concurrently with us. TODO: Define their state.
-#[no_mangle]
-pub unsafe extern "C" fn hart0_boot(device_tree: *const u8) -> ! {
- // Set up the logger.
- //
- // TODO: This should really be named something better than console.
- console::init();
-
- // Parse the DeviceTree.
- let flattened_device_tree = unsafe { device_tree::FlattenedDeviceTree::from_ptr(device_tree) }
- .expect("invalid DeviceTree");
-
- // Find the available physical memory areas and initialize the physical memory
- // free-list.
- let mut physical_memory_free_list = FreeList::new(&flattened_device_tree);
- flattened_device_tree
- .for_each_node(|node| {
- if node.is_unit(&["", "memory"]) {
- // Get the memory ranges.
- let Some(reg) = node.get_reg_usize() else {
- warn!("{}reg was not valid", node.name());
- return Ok(());
- };
-
- for (addr, size) in reg {
- physical_memory_free_list.add_range(addr..addr + size);
- }
- }
- Ok(())
- })
- .unwrap_or_else(|err| void::unreachable(err));
-
- // Log the physical memory we found.
- debug!(
- "found {} usable regions of physical memory{}",
- physical_memory_free_list.len(),
- if physical_memory_free_list.is_empty() {
- ""
- } else {
- ":"
- }
- );
- for region in physical_memory_free_list.drain() {
- debug!(
- "{:p}..{:p} ({} byte{})",
- region.start as *const u8,
- region.end as *const u8,
- region.len(),
- if region.len() == 1 { "" } else { "s" }
- )
- }
-
- // After this point, everything else is for debugging.
- #[cfg(target_arch = "riscv64")]
- {
- flattened_device_tree
- .for_each_node(|node| {
- if node.is_unit(&["", "cpus"]) {
- if let Some(timebase_frequency) = node.get_prop_u32("timebase-frequency") {
- // SAFETY: Other harts are not concurrently running, so they can't be
- // concurrently accessing or modifying this.
- unsafe {
- drivers::riscv_timer::TIMEBASE_FREQUENCY = timebase_frequency;
- }
- }
- }
- Ok(())
- })
- .unwrap_or_else(|err| void::unreachable(err));
- arch::interrupts::example_timer();
- }
- info!("sleeping forever...");
- sleep_forever();
-}
diff --git a/kernel/src/panic.rs b/kernel/src/panic.rs
deleted file mode 100644
index 7b53638..0000000
--- a/kernel/src/panic.rs
+++ /dev/null
@@ -1,13 +0,0 @@
-//! The kernel panic handler.
-
-use crate::arch::{interrupts::disable_interrupts, sleep_forever};
-use core::panic::PanicInfo;
-
-#[cfg(target_os = "none")]
-#[panic_handler]
-fn panic(info: &PanicInfo) -> ! {
- log::error!("{info}");
-
- disable_interrupts();
- sleep_forever();
-}
diff --git a/kernel/src/prelude.rs b/kernel/src/prelude.rs
deleted file mode 100644
index 05bd9ca..0000000
--- a/kernel/src/prelude.rs
+++ /dev/null
@@ -1,4 +0,0 @@
-//! A prelude for use inside the kernel.
-
-pub use bstr::B;
-pub use log::{debug, error, info, trace, warn};
diff --git a/kernel/src/util.rs b/kernel/src/util.rs
deleted file mode 100644
index dbcb228..0000000
--- a/kernel/src/util.rs
+++ /dev/null
@@ -1,99 +0,0 @@
-//! Miscellaneous utilities.
-
-use core::{mem::size_of, ops::Range};
-
-#[cold]
-#[inline(always)]
-fn cold() {}
-
-/// A hint that `b` is likely to be true. See `core::intrinsics::likely`.
-#[inline(always)]
-pub fn likely(b: bool) -> bool {
- if !b {
- cold()
- }
- b
-}
-
-/// A hint that `b` is likely to be false. See `core::intrinsics::unlikely`.
-#[inline(always)]
-pub fn unlikely(b: bool) -> bool {
- if b {
- cold()
- }
- b
-}
-
-/// A version of `std::dbg` built on top of `log::debug` instead of
-/// `std::eprintln`.
-///
-/// This code is copied from libstd, and inherits its copyright.
-#[macro_export]
-macro_rules! dbg {
- // NOTE: We cannot use `concat!` to make a static string as a format
- // argument of `log::debug!` because the `$expr` expression could be a
- // block (`{ .. }`), in which case the format string will be malformed.
- () => {
- log::debug!("")
- };
- ($expr:expr $(,)?) => {
- // Use of `match` here is intentional because it affects the lifetimes
- // of temporaries - https://stackoverflow.com/a/48732525/1063961
- match $expr {
- tmp => {
- log::debug!("{} = {:#?}", core::stringify!($expr), &tmp);
- tmp
- }
- }
- };
- ($($expr:expr),+ $(,)?) => {
- ($($crate::dbg!($expr)),+,)
- };
-}
-
-/// Returns whether the two ranges overlap.
-pub fn ranges_overlap<T: Copy + Ord>(r1: &Range<T>, r2: &Range<T>) -> bool {
- r1.start.max(r2.start) < r1.end.min(r2.end)
-}
-
-/// A trait for types that can be converted to from big-endian or little-endian byte slices.
-pub trait FromEndianBytes {
- /// Converts from a big-endian byte slice.
- fn from_big_endian_bytes(bytes: &[u8]) -> Self;
-
- /// Converts from a little-endian byte slice.
- fn from_little_endian_bytes(bytes: &[u8]) -> Self;
-}
-
-macro_rules! impl_FromEndianBytes {
- ($($ty:ty),* $(,)?) => {
- $(impl FromEndianBytes for $ty {
- fn from_big_endian_bytes(bytes: &[u8]) -> $ty {
- let chunk = match bytes.last_chunk() {
- Some(chunk) => *chunk,
- None => {
- let mut chunk = [0; size_of::<$ty>()];
- chunk[size_of::<$ty>() - bytes.len()..]
- .copy_from_slice(bytes);
- chunk
- },
- };
- <$ty>::from_be_bytes(chunk)
- }
-
- fn from_little_endian_bytes(bytes: &[u8]) -> $ty {
- let chunk = match bytes.first_chunk() {
- Some(chunk) => *chunk,
- None => {
- let mut chunk = [0; size_of::<$ty>()];
- chunk[.. bytes.len()].copy_from_slice(bytes);
- chunk
- },
- };
- <$ty>::from_le_bytes(chunk)
- }
- })*
- };
-}
-
-impl_FromEndianBytes!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize);