diff options
Diffstat (limited to 'crates')
| -rw-r--r-- | crates/Cargo.lock | 62 | ||||
| -rw-r--r-- | crates/Cargo.toml | 2 | ||||
| -rw-r--r-- | crates/alloc_buddy/src/lib.rs | 8 | ||||
| -rw-r--r-- | crates/arches.nix | 6 | ||||
| -rw-r--r-- | crates/default.nix | 43 | ||||
| -rw-r--r-- | crates/device_tree/Cargo.toml | 11 | ||||
| -rw-r--r-- | crates/device_tree/src/lib.rs | 645 | ||||
| -rw-r--r-- | crates/device_tree/src/stack_linked_list.rs | 78 | ||||
| -rw-r--r-- | crates/driver_riscv_timer/Cargo.toml | 7 | ||||
| -rw-r--r-- | crates/driver_riscv_timer/src/lib.rs | 47 | ||||
| -rw-r--r-- | crates/kernel/Cargo.toml | 17 | ||||
| -rw-r--r-- | crates/kernel/src/arch/hosted.rs | 29 | ||||
| -rw-r--r-- | crates/kernel/src/arch/mod.rs | 11 | ||||
| -rw-r--r-- | crates/kernel/src/arch/riscv64/interrupts.rs | 80 | ||||
| -rw-r--r-- | crates/kernel/src/arch/riscv64/mod.rs | 14 | ||||
| -rw-r--r-- | crates/kernel/src/lib.rs | 101 | ||||
| -rw-r--r-- | crates/kernel/src/panic.rs | 12 | ||||
| -rw-r--r-- | crates/utils/src/lib.rs | 95 |
18 files changed, 1262 insertions, 6 deletions
diff --git a/crates/Cargo.lock b/crates/Cargo.lock index 7c772d4..e49301e 100644 --- a/crates/Cargo.lock +++ b/crates/Cargo.lock @@ -36,6 +36,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "b048fb63fd8b5923fc5aa7b340d8e156aec7ec02f0c78fa8a6ddc2613f6f71de" [[package]] +name = "bstr" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "40723b8fb387abc38f4f4a37c09073622e41dd12327033091ef8950659e6dc0c" +dependencies = [ + "memchr", +] + +[[package]] name = "byteorder" version = "1.5.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -74,6 +83,12 @@ dependencies = [ ] [[package]] +name = "either" +version = "1.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "60b1af1c220855b6ceac025d3f6ecdd2b7c4894bfe9cd9bda4fbb4bc7c0d4cf0" + +[[package]] name = "fuchsia-cprng" version = "0.1.1" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -92,6 +107,18 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "d8adc4bb1803a324070e64a98ae98f38934d91957a99cfb3a43dcbc01bc56439" [[package]] +name = "log" +version = "0.4.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7a70ba024b9dc04c27ea2f0c0548feb474ec5c54bba33a7f72f873a39d07b24" + +[[package]] +name = "memchr" +version = "2.7.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "78ca9ab1a0babb1e7d5695e3530886289c18cf2f87ec19a575a0abdce112e3a3" + +[[package]] name = "nix" version = "0.29.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -319,10 +346,45 @@ dependencies = [ ] [[package]] +name = "vernos_device_tree" +version = "0.1.0" +dependencies = [ + "bstr", + "contracts", + "either", + "log", + "vernos_utils", +] + +[[package]] +name = "vernos_driver_riscv_timer" +version = "0.1.0" + +[[package]] +name = "vernos_kernel" +version = "0.1.0" +dependencies = [ + "cfg-if", + "log", + "vernos_alloc_buddy", + "vernos_alloc_physmem_free_list", + "vernos_device_tree", + "vernos_driver_riscv_timer", + "vernos_utils", + "void", +] + +[[package]] name = "vernos_utils" version = "0.1.0" [[package]] +name = "void" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6a02e4885ed3bc0f2de90ea6dd45ebcbb66dacffe03547fadbb0eeae2770887d" + +[[package]] name = "winapi" version = "0.3.9" source = "registry+https://github.com/rust-lang/crates.io-index" diff --git a/crates/Cargo.toml b/crates/Cargo.toml index 192869b..855d815 100644 --- a/crates/Cargo.toml +++ b/crates/Cargo.toml @@ -1,3 +1,3 @@ [workspace] -members = ["alloc_buddy", "alloc_physmem_free_list", "utils"] +members = ["alloc_buddy", "alloc_physmem_free_list", "device_tree", "driver_riscv_timer", "kernel", "utils"] resolver = "2" diff --git a/crates/alloc_buddy/src/lib.rs b/crates/alloc_buddy/src/lib.rs index fa14848..c890e79 100644 --- a/crates/alloc_buddy/src/lib.rs +++ b/crates/alloc_buddy/src/lib.rs @@ -1,10 +1,6 @@ //! A buddy allocator, used to allocate pages. #![no_std] -mod bitset; -mod free_list; -mod tree; - use crate::{ bitset::{Bitset, SubregionStatus}, free_list::{FreeList, FreeListNode}, @@ -16,6 +12,10 @@ use core::{fmt, mem, ptr::NonNull}; use vernos_alloc_physmem_free_list::FreeListAllocator; use vernos_utils::debug; +mod bitset; +mod free_list; +mod tree; + /// A buddy allocator. pub struct BuddyAllocator< 'allocator, diff --git a/crates/arches.nix b/crates/arches.nix new file mode 100644 index 0000000..257ad7d --- /dev/null +++ b/crates/arches.nix @@ -0,0 +1,6 @@ +{ + riscv64 = { + crossSystem = "riscv64-unknown-none-elf"; + rust-target = "riscv64gc-unknown-none-elf"; + }; +} diff --git a/crates/default.nix b/crates/default.nix new file mode 100644 index 0000000..d615e29 --- /dev/null +++ b/crates/default.nix @@ -0,0 +1,43 @@ +{ + fenix, + nixpkgs, + system, +}: + +let + arches = import ./arches.nix; + + toml = builtins.fromTOML (builtins.readFile ./kernel/Cargo.toml); + + mkLibKernel = + _: + { crossSystem, rust-target }: + let + pkgs = import nixpkgs { + inherit system; + crossSystem.config = crossSystem; + }; + + rust-toolchain = fenix.combine [ + fenix.stable.cargo + fenix.stable.rustc + fenix.stable.clippy + fenix.targets.${rust-target}.stable.rust-std + ]; + + rust = pkgs.makeRustPlatform { + cargo = rust-toolchain; + rustc = rust-toolchain; + }; + in + + rust.buildRustPackage { + pname = toml.package.name; + version = toml.package.version; + src = ./.; + cargoLock.lockFile = ./Cargo.lock; + dontFixup = true; + }; +in + +nixpkgs.lib.recurseIntoAttrs (builtins.mapAttrs mkLibKernel arches) diff --git a/crates/device_tree/Cargo.toml b/crates/device_tree/Cargo.toml new file mode 100644 index 0000000..e85aa2c --- /dev/null +++ b/crates/device_tree/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "vernos_device_tree" +version = "0.1.0" +edition = "2021" + +[dependencies] +bstr = { version = "1.10.0", default-features = false } +contracts = { version = "0.6.3", default-features = false } +either = { version = "1.13.0", default-features = false } +log = { version = "0.4.20", default-features = false } +vernos_utils = { path = "../utils" } diff --git a/crates/device_tree/src/lib.rs b/crates/device_tree/src/lib.rs new file mode 100644 index 0000000..531f7ef --- /dev/null +++ b/crates/device_tree/src/lib.rs @@ -0,0 +1,645 @@ +//! Support for the DeviceTree format. +#![no_std] + +use crate::stack_linked_list::StackLinkedList; +use bstr::BStr; +use contracts::requires; +use core::{ + fmt, iter, + num::ParseIntError, + ops::Range, + slice, + str::{self, Utf8Error}, +}; +use either::Either; +use log::warn; +use vernos_utils::FromEndianBytes; + +mod stack_linked_list; + +/// 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(_)) { + 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/crates/device_tree/src/stack_linked_list.rs b/crates/device_tree/src/stack_linked_list.rs new file mode 100644 index 0000000..19b9272 --- /dev/null +++ b/crates/device_tree/src/stack_linked_list.rs @@ -0,0 +1,78 @@ +//! 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/crates/driver_riscv_timer/Cargo.toml b/crates/driver_riscv_timer/Cargo.toml new file mode 100644 index 0000000..bdecf38 --- /dev/null +++ b/crates/driver_riscv_timer/Cargo.toml @@ -0,0 +1,7 @@ +[package] +name = "vernos_driver_riscv_timer" +version = "0.1.0" +edition = "2021" +publish = false + +[dependencies] diff --git a/crates/driver_riscv_timer/src/lib.rs b/crates/driver_riscv_timer/src/lib.rs new file mode 100644 index 0000000..aebaba2 --- /dev/null +++ b/crates/driver_riscv_timer/src/lib.rs @@ -0,0 +1,47 @@ +//! Support for RISC-V's timers, using the Sstc extension. +#![cfg(target_arch = "riscv64")] +#![no_std] + +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/crates/kernel/Cargo.toml b/crates/kernel/Cargo.toml new file mode 100644 index 0000000..3d7b61b --- /dev/null +++ b/crates/kernel/Cargo.toml @@ -0,0 +1,17 @@ +[package] +name = "vernos_kernel" +version = "0.1.0" +edition = "2021" + +[lib] +crate-type = ["staticlib"] + +[dependencies] +cfg-if = { version = "1.0.0", default-features = false } +log = { version = "0.4.20", default-features = false } +vernos_alloc_buddy = { path = "../alloc_buddy" } +vernos_alloc_physmem_free_list = { path = "../alloc_physmem_free_list" } +vernos_device_tree = { path = "../device_tree" } +vernos_driver_riscv_timer = { path = "../driver_riscv_timer" } +vernos_utils = { path = "../utils" } +void = { version = "1.0.2", default-features = false } diff --git a/crates/kernel/src/arch/hosted.rs b/crates/kernel/src/arch/hosted.rs new file mode 100644 index 0000000..df62bab --- /dev/null +++ b/crates/kernel/src/arch/hosted.rs @@ -0,0 +1,29 @@ +//! Support for running under an operating system that provides libstd, for testing. + +extern crate std; + +use std::{thread::sleep, time::Duration}; + +/// The size of a page of memory. +/// +/// Obviously, this value is unrealistic, but for now we just need the hosted arch to compile. +pub const PAGE_SIZE: usize = 64; + +/// The number of bits in the size of a page of memory. +/// +/// Obviously, this value is unrealistic, but for now we just need the hosted arch to compile. +pub const PAGE_SIZE_BITS: usize = 6; + +/// 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/crates/kernel/src/arch/mod.rs b/crates/kernel/src/arch/mod.rs new file mode 100644 index 0000000..bfdfcc7 --- /dev/null +++ b/crates/kernel/src/arch/mod.rs @@ -0,0 +1,11 @@ +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::*; + } else { + compile_error!("unsupported platform"); + } +} diff --git a/crates/kernel/src/arch/riscv64/interrupts.rs b/crates/kernel/src/arch/riscv64/interrupts.rs new file mode 100644 index 0000000..84f2258 --- /dev/null +++ b/crates/kernel/src/arch/riscv64/interrupts.rs @@ -0,0 +1,80 @@ +use core::{ + arch::{asm, global_asm}, + time::Duration, +}; +use log::info; +use vernos_driver_riscv_timer::{set_timer, Instant}; + +/// 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/crates/kernel/src/arch/riscv64/mod.rs b/crates/kernel/src/arch/riscv64/mod.rs new file mode 100644 index 0000000..216a90c --- /dev/null +++ b/crates/kernel/src/arch/riscv64/mod.rs @@ -0,0 +1,14 @@ +pub mod interrupts; + +/// The size of a page of memory. +pub const PAGE_SIZE: usize = 4096; + +/// The number of bits in the size of a page of memory. +pub const PAGE_SIZE_BITS: usize = 12; + +/// Halts the hart. +pub fn sleep_forever() -> ! { + loop { + unsafe { core::arch::asm!("wfi") } + } +} diff --git a/crates/kernel/src/lib.rs b/crates/kernel/src/lib.rs new file mode 100644 index 0000000..eff6d36 --- /dev/null +++ b/crates/kernel/src/lib.rs @@ -0,0 +1,101 @@ +//! The static library that forms the core of the kernel. +#![no_std] + +use crate::arch::{sleep_forever, PAGE_SIZE}; +use log::{debug, info, warn}; +use vernos_alloc_physmem_free_list::FreeListAllocator; +use vernos_device_tree::FlattenedDeviceTree; +use vernos_utils::dbg; + +#[cfg(target_os = "none")] +mod panic; + +pub mod arch; + +/// 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 { 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 = FreeListAllocator::<PAGE_SIZE>::new(); + dbg!(physical_memory_free_list); + + /* + 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 { + vernos_driver_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/crates/kernel/src/panic.rs b/crates/kernel/src/panic.rs new file mode 100644 index 0000000..dcb8d31 --- /dev/null +++ b/crates/kernel/src/panic.rs @@ -0,0 +1,12 @@ +//! The kernel panic handler. + +use crate::arch::{interrupts::disable_interrupts, sleep_forever}; +use core::panic::PanicInfo; + +#[panic_handler] +fn panic(info: &PanicInfo) -> ! { + log::error!("{info}"); + + disable_interrupts(); + sleep_forever(); +} diff --git a/crates/utils/src/lib.rs b/crates/utils/src/lib.rs index 248227a..3649666 100644 --- a/crates/utils/src/lib.rs +++ b/crates/utils/src/lib.rs @@ -1,6 +1,7 @@ +//! Common utilities. #![no_std] -use core::fmt; +use core::{fmt, mem::size_of}; /// Creates an ad-hoc `Debug` instance. pub fn debug(f: impl Fn(&mut fmt::Formatter) -> fmt::Result) -> impl fmt::Debug { @@ -14,3 +15,95 @@ pub fn debug(f: impl Fn(&mut fmt::Formatter) -> fmt::Result) -> impl fmt::Debug Debug(f) } + +/// A hint that this branch is unlikely to be called. +#[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)),+,) + }; +} + +/// 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); |