diff options
31 files changed, 315 insertions, 987 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/kernel/src/device_tree.rs b/crates/device_tree/src/lib.rs index c045cfd..531f7ef 100644 --- a/kernel/src/device_tree.rs +++ b/crates/device_tree/src/lib.rs @@ -1,6 +1,7 @@ //! Support for the DeviceTree format. +#![no_std] -use crate::{collections::stack_linked_list::StackLinkedList, prelude::*, util::FromEndianBytes}; +use crate::stack_linked_list::StackLinkedList; use bstr::BStr; use contracts::requires; use core::{ @@ -11,6 +12,10 @@ use core::{ 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> { @@ -604,7 +609,6 @@ fn for_each_node<'dt, 'iter, E>( .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)); } diff --git a/kernel/src/collections/stack_linked_list.rs b/crates/device_tree/src/stack_linked_list.rs index 19b9272..19b9272 100644 --- a/kernel/src/collections/stack_linked_list.rs +++ b/crates/device_tree/src/stack_linked_list.rs 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/kernel/src/drivers/riscv_timer.rs b/crates/driver_riscv_timer/src/lib.rs index a702f7b..aebaba2 100644 --- a/kernel/src/drivers/riscv_timer.rs +++ b/crates/driver_riscv_timer/src/lib.rs @@ -1,3 +1,7 @@ +//! 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. 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/kernel/src/arch/hosted/mod.rs b/crates/kernel/src/arch/hosted.rs index c1fb0ff..df62bab 100644 --- a/kernel/src/arch/hosted/mod.rs +++ b/crates/kernel/src/arch/hosted.rs @@ -4,6 +4,16 @@ 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? diff --git a/kernel/src/arch/mod.rs b/crates/kernel/src/arch/mod.rs index d23dd81..bfdfcc7 100644 --- a/kernel/src/arch/mod.rs +++ b/crates/kernel/src/arch/mod.rs @@ -5,5 +5,7 @@ cfg_if::cfg_if! { } else if #[cfg(target_arch = "riscv64")] { mod riscv64; pub use self::riscv64::*; + } else { + compile_error!("unsupported platform"); } } diff --git a/kernel/src/arch/riscv64/interrupts.rs b/crates/kernel/src/arch/riscv64/interrupts.rs index 302fc4f..84f2258 100644 --- a/kernel/src/arch/riscv64/interrupts.rs +++ b/crates/kernel/src/arch/riscv64/interrupts.rs @@ -1,11 +1,9 @@ -use crate::{ - drivers::riscv_timer::{set_timer, Instant}, - prelude::*, -}; 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)] 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/kernel/src/lib.rs b/crates/kernel/src/lib.rs index e369864..eff6d36 100644 --- a/kernel/src/lib.rs +++ b/crates/kernel/src/lib.rs @@ -1,18 +1,16 @@ +//! The static library that forms the core of the kernel. #![no_std] -#[macro_use] -pub mod util; +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; -pub mod allocators; -pub mod arch; -pub mod collections; -pub mod console; -pub mod device_tree; -pub mod drivers; +#[cfg(target_os = "none")] mod panic; -pub mod prelude; -use crate::{allocators::physical_memory_free_list::FreeList, arch::sleep_forever, prelude::*}; +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. @@ -29,15 +27,18 @@ 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(); + // console::init(); // Parse the DeviceTree. - let flattened_device_tree = unsafe { device_tree::FlattenedDeviceTree::from_ptr(device_tree) } - .expect("invalid 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 = FreeList::new(&flattened_device_tree); + 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"]) { @@ -74,6 +75,7 @@ pub unsafe extern "C" fn hart0_boot(device_tree: *const u8) -> ! { if region.len() == 1 { "" } else { "s" } ) } + */ // After this point, everything else is for debugging. #[cfg(target_arch = "riscv64")] @@ -85,7 +87,7 @@ pub unsafe extern "C" fn hart0_boot(device_tree: *const u8) -> ! { // 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; + vernos_driver_riscv_timer::TIMEBASE_FREQUENCY = timebase_frequency; } } } diff --git a/kernel/src/panic.rs b/crates/kernel/src/panic.rs index 7b53638..dcb8d31 100644 --- a/kernel/src/panic.rs +++ b/crates/kernel/src/panic.rs @@ -3,7 +3,6 @@ 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}"); 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); @@ -23,18 +23,16 @@ pkgs = nixpkgs.legacyPackages.${system}; fenix = fenix-flake.packages.${system}; - rust-toolchain = fenix.combine [ - fenix.stable.cargo - fenix.stable.rustc - fenix.stable.clippy - # fenix.targets.riscv64gc-unknown-none-elf.stable.rust-std - ]; - rust = pkgs.makeRustPlatform { - cargo = rust-toolchain; - rustc = rust-toolchain; - }; - - packages = { }; + rust-toolchain = fenix.combine ( + [ + fenix.stable.cargo + fenix.stable.rustc + fenix.stable.clippy + ] + ++ (builtins.map ({ rust-target, ... }: fenix.targets.${rust-target}.stable.rust-std) ( + builtins.attrValues (import ./crates/arches.nix) + )) + ); in /* pkgsHost = import nixpkgs { @@ -117,7 +115,7 @@ */ devShells.default = pkgs.mkShell { - inputsFrom = builtins.attrValues (flake-utils.lib.flattenTree packages); + # inputsFrom = builtins.attrValues (flake-utils.lib.flattenTree packages); nativeBuildInputs = [ (pkgs.callPackage ./nix/miri.nix { inherit fenix; }) pkgs.cargo-watch @@ -128,7 +126,10 @@ # CARGO_BUILD_TARGET = "riscv64gc-unknown-none-elf"; }; - packages = flake-utils.lib.flattenTree packages; + lib = import ./crates { inherit fenix nixpkgs system; }; + packages = flake-utils.lib.flattenTree { + libkernel = import ./crates { inherit fenix nixpkgs system; }; + }; } ); } 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/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/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/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); |