diff options
Diffstat (limited to 'kernel')
| -rw-r--r-- | kernel/Cargo.lock | 121 | ||||
| -rw-r--r-- | kernel/src/allocators/buddy/bitvec.rs | 50 | ||||
| -rw-r--r-- | kernel/src/allocators/buddy/mod.rs | 52 | ||||
| -rw-r--r-- | kernel/src/allocators/buddy/stripe.rs | 148 | ||||
| -rw-r--r-- | kernel/src/allocators/buddy/tree.rs | 112 | ||||
| -rw-r--r-- | kernel/src/allocators/mod.rs | 24 | ||||
| -rw-r--r-- | kernel/src/allocators/physical_memory_free_list.rs | 322 | ||||
| -rw-r--r-- | kernel/src/arch/hosted/mod.rs | 19 | ||||
| -rw-r--r-- | kernel/src/arch/mod.rs | 9 | ||||
| -rw-r--r-- | kernel/src/arch/riscv64/interrupts.rs | 82 | ||||
| -rw-r--r-- | kernel/src/arch/riscv64/mod.rs | 8 | ||||
| -rw-r--r-- | kernel/src/collections/mod.rs | 3 | ||||
| -rw-r--r-- | kernel/src/collections/stack_linked_list.rs | 78 | ||||
| -rw-r--r-- | kernel/src/device_tree.rs | 641 | ||||
| -rw-r--r-- | kernel/src/drivers/mod.rs | 2 | ||||
| -rw-r--r-- | kernel/src/drivers/riscv_timer.rs | 43 | ||||
| -rw-r--r-- | kernel/src/lib.rs | 99 | ||||
| -rw-r--r-- | kernel/src/panic.rs | 13 | ||||
| -rw-r--r-- | kernel/src/prelude.rs | 4 | ||||
| -rw-r--r-- | kernel/src/util.rs | 99 |
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); |