summaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
Diffstat (limited to 'crates')
-rw-r--r--crates/Cargo.lock16
-rw-r--r--crates/Cargo.toml2
-rw-r--r--crates/alloc_buddy/Cargo.toml1
-rw-r--r--crates/alloc_genmalloc/Cargo.toml9
-rw-r--r--crates/alloc_genmalloc/src/lib.rs135
-rw-r--r--crates/kernel/Cargo.toml1
-rw-r--r--crates/kernel/src/arch/riscv64/paging.rs197
7 files changed, 324 insertions, 37 deletions
diff --git a/crates/Cargo.lock b/crates/Cargo.lock
index 41384f7..3f75ce1 100644
--- a/crates/Cargo.lock
+++ b/crates/Cargo.lock
@@ -308,12 +308,6 @@ 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"
@@ -338,12 +332,19 @@ dependencies = [
"contracts",
"nix",
"proptest",
- "static_assertions",
"vernos_alloc_physmem_free_list",
"vernos_utils",
]
[[package]]
+name = "vernos_alloc_genmalloc"
+version = "0.1.0"
+dependencies = [
+ "allocator-api2",
+ "contracts",
+]
+
+[[package]]
name = "vernos_alloc_physmem_free_list"
version = "0.1.0"
dependencies = [
@@ -372,6 +373,7 @@ version = "0.1.0"
dependencies = [
"cfg-if",
"contracts",
+ "either",
"log",
"spin",
"vernos_alloc_buddy",
diff --git a/crates/Cargo.toml b/crates/Cargo.toml
index dd1f42a..10aeec4 100644
--- a/crates/Cargo.toml
+++ b/crates/Cargo.toml
@@ -1,5 +1,5 @@
[workspace]
-members = ["alloc_buddy", "alloc_physmem_free_list", "device_tree", "driver_riscv_timer", "kernel", "utils"]
+members = ["alloc_buddy", "alloc_genmalloc", "alloc_physmem_free_list", "device_tree", "driver_riscv_timer", "kernel", "utils"]
resolver = "2"
[profile.release]
diff --git a/crates/alloc_buddy/Cargo.toml b/crates/alloc_buddy/Cargo.toml
index 43e1cee..3d58409 100644
--- a/crates/alloc_buddy/Cargo.toml
+++ b/crates/alloc_buddy/Cargo.toml
@@ -7,7 +7,6 @@ publish = false
[dependencies]
allocator-api2 = { version = "0.2.18", default-features = false }
contracts = { version = "0.6.3", default-features = false }
-static_assertions = { version = "1.1.0", default-features = false }
vernos_alloc_physmem_free_list = { path = "../alloc_physmem_free_list" }
vernos_utils = { path = "../utils" }
diff --git a/crates/alloc_genmalloc/Cargo.toml b/crates/alloc_genmalloc/Cargo.toml
new file mode 100644
index 0000000..1099020
--- /dev/null
+++ b/crates/alloc_genmalloc/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "vernos_alloc_genmalloc"
+version = "0.1.0"
+edition = "2021"
+publish = false
+
+[dependencies]
+allocator-api2 = { version = "0.2.18", default-features = false }
+contracts = { version = "0.6.3", default-features = false }
diff --git a/crates/alloc_genmalloc/src/lib.rs b/crates/alloc_genmalloc/src/lib.rs
new file mode 100644
index 0000000..06bc667
--- /dev/null
+++ b/crates/alloc_genmalloc/src/lib.rs
@@ -0,0 +1,135 @@
+//! A general-purpose allocator, based on the design of mimalloc [0, 1].
+//!
+//! [0]: https://www.microsoft.com/en-us/research/publication/mimalloc-free-list-sharding-in-action/
+//! [1]: https://github.com/microsoft/mimalloc
+#![no_std]
+
+use allocator_api2::alloc::AllocError;
+use contracts::requires;
+use core::{
+ ptr::NonNull,
+ sync::atomic::{AtomicPtr, AtomicU16, Ordering},
+};
+
+/// The per-CPU structure.
+struct Heap {
+ /// Small objects (<=1024 bytes) have pointers directly to the page they allocate into. These
+ /// are non-owning pointers.
+ pages_direct: [NonNull<Page>; 128],
+
+ /// The sentinel nodes for the circular doubly-linked lists that compose the size classes, up
+ /// to and including 512KiB, plus one more for objects over 512KiB.
+ pages: [PageLink; 18],
+}
+
+impl Heap {
+ #[requires(size > 0)]
+ #[requires(size <= 1024)]
+ fn alloc_small(&mut self, size: usize) -> Result<NonNull<u8>, AllocError> {
+ let mut page = self.pages_direct[(size + 7) >> 3];
+ let page = unsafe { page.as_mut() };
+ match page.header.alloc_list.as_mut() {
+ Some(&mut block) => {
+ let next = unsafe { block.as_ref() }.next.load(Ordering::SeqCst);
+ page.header.alloc_list = NonNull::new(next);
+ page.header.used.fetch_add(1, Ordering::SeqCst);
+ Ok(block.cast())
+ }
+ None => self.alloc_generic(size),
+ }
+ }
+
+ fn alloc_generic(&mut self, size: usize) -> Result<NonNull<u8>, AllocError> {
+ let size_class = size_class(size);
+ let sentinel: NonNull<PageLink> = NonNull::from(&self.pages[size_class]);
+ let mut page = sentinel;
+ loop {
+ page = unsafe { (*page.as_ptr()).next.unwrap() };
+
+ todo!("{page:#?}")
+ }
+ todo!()
+ }
+}
+
+/// Returns the index in the `pages` array of objects with the given size.
+fn size_class(size: usize) -> usize {
+ // Clamp the size to the range the bitwise trick will work on.
+ let size = size.clamp(8, 1024 * 1024);
+
+ // Figure out the size class.
+ (size.next_power_of_two().trailing_zeros() - 3) as usize
+}
+
+#[test]
+fn expected_size_class_values() {
+ assert_eq!(size_class(1), 0);
+ assert_eq!(size_class(8), 0);
+
+ let mut size = 8;
+ let mut expected = 0;
+ while size <= 512 * 1024 {
+ assert_eq!(size_class(size), expected);
+ size <<= 1;
+ expected += 1;
+ }
+
+ assert_eq!(size_class(512 * 1024), 16);
+ assert_eq!(size_class((512 * 1024) + 1), 17);
+ assert_eq!(size_class(4 * 1024 * 1024), 17);
+}
+
+/// A page is a block of memory that contains objects of a single size class.
+#[repr(C)]
+struct Page {
+ /// The intrusive link in the circular doubly-linked list of pages of each size class.
+ link: PageLink,
+
+ /// The fields other than the intrusive link in a page's header.
+ header: PageHeader,
+}
+
+/// The intrusive link in the circular doubly-linked list of pages of each size class.
+struct PageLink {
+ /// The previous page.
+ prev: Option<NonNull<PageLink>>,
+
+ /// The next page.
+ next: Option<NonNull<PageLink>>,
+}
+
+/// The fields other than the intrusive link in a page's header.
+struct PageHeader {
+ /// The free list that the owning thread pops from.
+ alloc_list: Option<NonNull<Block>>,
+
+ /// The free list that the owning thread pushes onto.
+ local_free_list: Option<NonNull<Block>>,
+
+ /// The free list that other threads push onto.
+ thread_free_list: AtomicPtr<Block>,
+
+ /// The number of objects in the page that have been allocated.
+ used: AtomicU16,
+
+ /// The number of objects in the thread free list.
+ thread_freed: AtomicU16,
+}
+
+/// An object in a free list.
+struct Block {
+ next: AtomicPtr<Block>,
+}
+
+fn atomic_push(node: &mut Block, list: &AtomicPtr<Block>) {
+ loop {
+ let old_list = list.load(Ordering::Acquire);
+ node.next = AtomicPtr::from(old_list);
+ if list
+ .compare_exchange(old_list, node, Ordering::Release, Ordering::Acquire)
+ .is_ok()
+ {
+ break;
+ }
+ }
+}
diff --git a/crates/kernel/Cargo.toml b/crates/kernel/Cargo.toml
index 6fbabc1..cbdac2a 100644
--- a/crates/kernel/Cargo.toml
+++ b/crates/kernel/Cargo.toml
@@ -9,6 +9,7 @@ crate-type = ["staticlib"]
[dependencies]
cfg-if = { version = "1.0.0", default-features = false }
contracts = { version = "0.6.3", default-features = false }
+either = { version = "1.13.0", default-features = false }
log = { version = "0.4.20", default-features = false }
spin = { version = "0.9.8", default-features = false, features = ["fair_mutex", "use_ticket_mutex"] }
vernos_alloc_buddy = { path = "../alloc_buddy" }
diff --git a/crates/kernel/src/arch/riscv64/paging.rs b/crates/kernel/src/arch/riscv64/paging.rs
index 5ebdb5f..6b81881 100644
--- a/crates/kernel/src/arch/riscv64/paging.rs
+++ b/crates/kernel/src/arch/riscv64/paging.rs
@@ -1,6 +1,8 @@
-use crate::arch::PAGE_SIZE;
+use crate::arch::{PAGE_SIZE, PAGE_SIZE_BITS};
use contracts::requires;
-use core::{arch::asm, fmt, str};
+use core::{arch::asm, fmt, iter, ops::RangeInclusive, str};
+use either::Either;
+use vernos_utils::debug;
/// The number of bits looked up in each page table entry.
pub const PAGE_TABLE_BITS: usize = 9;
@@ -18,7 +20,6 @@ impl ASID {
}
/// A single page table.
-#[derive(Debug)]
#[repr(align(4096))]
pub struct PageTable([PageTableEntry; 512]);
@@ -50,6 +51,57 @@ impl PageTable {
}
}
+impl fmt::Debug for PageTable {
+ fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+ // Get an iterator over the valid leaf page table entries.
+ let mut mappings = iter_level_2_mappings(&self.0, 0).peekable();
+
+ // Make an iterator that merges adjacent entries that have the same flags.
+ let mappings = iter::from_fn(|| {
+ let (entry, mut vaddrs) = mappings.next()?;
+ let paddrs_start = entry.addr() as usize;
+ let mut len = (vaddrs.end() - vaddrs.start()) + 1;
+
+ while let Some((next_entry, next_vaddrs)) = mappings.peek() {
+ let next_paddrs_start = next_entry.addr() as usize;
+
+ if entry.flag_bits() != next_entry.flag_bits()
+ || vaddrs.end().wrapping_add(1) != *next_vaddrs.start()
+ || paddrs_start.wrapping_add(len) != next_paddrs_start
+ {
+ break;
+ }
+ // UNWRAP: .peek() already showed us that there's a next entry.
+ let (_, next_vaddrs) = mappings.next().unwrap();
+ vaddrs = *vaddrs.start()..=*next_vaddrs.end();
+ len = (next_vaddrs.end() - vaddrs.start()) + 1;
+ }
+ let paddrs = paddrs_start..=paddrs_start + (len - 1);
+ Some((entry, vaddrs, paddrs))
+ });
+
+ // Turn the iterator into an iterator over Debugs.
+ let debug_mappings = mappings.map(|(entry, vaddrs, paddrs)| {
+ debug(move |fmt| {
+ let flags = entry.flags_str();
+ // UNWRAP: The flags must be ASCII by the postcondition of flags_str().
+ let flags = str::from_utf8(&flags).unwrap();
+ write!(
+ fmt,
+ "[V|{:16x}-{:16x}][P|{:16x}-{:16x}][F|{}]",
+ *vaddrs.start(),
+ *vaddrs.end(),
+ *paddrs.start(),
+ *paddrs.end(),
+ flags
+ )
+ })
+ });
+
+ fmt.debug_list().entries(debug_mappings).finish()
+ }
+}
+
/// An entry in a page table.
#[derive(Clone, Copy, Default, Eq, PartialEq)]
pub struct PageTableEntry(u64);
@@ -62,11 +114,52 @@ impl PageTableEntry {
(self.0 >> 10) & 0x0000_0fff_ffff_ffff
}
+ /// Returns the bits of the entry that correspond to flags.
+ ///
+ /// This isn't `pub` because this isn't portable, though maybe it makes sense to instead export
+ /// a predicate for "do these two entries have the _same_ flags bits," since that should be
+ /// more portable.
+ #[requires(self.valid())]
+ #[ensures((ret & !0xffc0_0000_0000_03ff) == 0)]
+ fn flag_bits(&self) -> u64 {
+ self.0 & 0xffc0_0000_0000_03ff
+ }
+
+ /// Returns bytes that correspond to an ASCII string with the flags.
+ #[requires(self.valid())]
+ #[ensures(ret.iter().all(|ch| ch.is_ascii()))]
+ fn flags_str(&self) -> [u8; 7] {
+ let mut flags = *b"rwxugad";
+ let char_disabled = b'-';
+ if !self.readable() {
+ flags[0] = char_disabled;
+ }
+ if !self.writable() {
+ flags[1] = char_disabled;
+ }
+ if !self.executable() {
+ flags[2] = char_disabled;
+ }
+ if !self.user() {
+ flags[3] = char_disabled;
+ }
+ if !self.global() {
+ flags[4] = char_disabled;
+ }
+ if !self.accessed() {
+ flags[5] = char_disabled;
+ }
+ if !self.dirty() {
+ flags[6] = char_disabled;
+ }
+ flags
+ }
+
/// Returns the physical address of the backing page or next level page table.
#[requires(self.valid())]
#[ensures((ret & !0x003f_ffff_ffff_fc00) == 0)]
pub fn addr(&self) -> u64 {
- self.ppn() << PAGE_TABLE_BITS
+ self.ppn() << PAGE_SIZE_BITS
}
/// Returns a pointer to the backing page.
@@ -228,31 +321,9 @@ impl PageTableEntry {
impl fmt::Debug for PageTableEntry {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
if self.valid() {
- let mut flags = *b"DAGUXWRV";
- if !self.dirty() {
- flags[0] = b' ';
- }
- if !self.accessed() {
- flags[1] = b' ';
- }
- if !self.global() {
- flags[2] = b' ';
- }
- if !self.user() {
- flags[3] = b' ';
- }
- if !self.executable() {
- flags[4] = b' ';
- }
- if !self.writable() {
- flags[5] = b' ';
- }
- if !self.readable() {
- flags[6] = b' ';
- }
-
- // UNWRAP: The flags must be ASCII.
let addr = self.addr() as *const ();
+ let flags = self.flags_str();
+ // UNWRAP: The flags must be ASCII by the postcondition of flags_str().
let flags = str::from_utf8(&flags).unwrap();
write!(fmt, "PageTableEntry({addr:018p}, {flags})")
} else {
@@ -260,3 +331,73 @@ impl fmt::Debug for PageTableEntry {
}
}
}
+
+/// See `PageTable::iter_mappings`. This needs to be its own function because of `impl Trait`; we
+/// can't allocate here, and we want a fixed-size iterator.
+fn iter_level_2_mappings(
+ table: &[PageTableEntry; 512],
+ base_addr: usize,
+) -> impl '_ + Iterator<Item = (PageTableEntry, RangeInclusive<usize>)> {
+ const ENTRY_SIZE: usize = 1 << (12 + 9 + 9);
+ table
+ .iter()
+ .enumerate()
+ .filter(|(_, entry)| entry.valid())
+ .flat_map(move |(i, &entry)| {
+ let mut start_addr = base_addr + i * ENTRY_SIZE;
+ if i >= 256 {
+ start_addr += 0xffff_ff80_0000_0000;
+ }
+ if entry.leaf_pte() {
+ Either::Left(iter::once((
+ entry,
+ start_addr..=start_addr + (ENTRY_SIZE - 1),
+ )))
+ } else {
+ let next_table = unsafe { &(*entry.page_table()).0 };
+ Either::Right(iter_level_1_mappings(next_table, start_addr))
+ }
+ })
+}
+
+/// See `PageTable::iter_mappings`. This needs to be its own function because of `impl Trait`; we
+/// can't allocate here, and we want a fixed-size iterator.
+fn iter_level_1_mappings(
+ table: &[PageTableEntry; 512],
+ base_addr: usize,
+) -> impl '_ + Iterator<Item = (PageTableEntry, RangeInclusive<usize>)> {
+ const ENTRY_SIZE: usize = 1 << (12 + 9);
+ table
+ .iter()
+ .enumerate()
+ .filter(|(_, entry)| entry.valid())
+ .flat_map(move |(i, &entry)| {
+ let start_addr = base_addr + i * ENTRY_SIZE;
+ if entry.leaf_pte() {
+ Either::Left(iter::once((
+ entry,
+ start_addr..=start_addr + (ENTRY_SIZE - 1),
+ )))
+ } else {
+ let next_table = unsafe { &(*entry.page_table()).0 };
+ Either::Right(iter_level_0_mappings(next_table, start_addr))
+ }
+ })
+}
+
+/// See `PageTable::iter_mappings`. This needs to be its own function because of `impl Trait`; we
+/// can't allocate here, and we want a fixed-size iterator.
+fn iter_level_0_mappings(
+ table: &[PageTableEntry; 512],
+ base_addr: usize,
+) -> impl '_ + Iterator<Item = (PageTableEntry, RangeInclusive<usize>)> {
+ const ENTRY_SIZE: usize = 1 << 12;
+ table
+ .iter()
+ .enumerate()
+ .filter(|(_, entry)| entry.valid())
+ .map(move |(i, &entry)| {
+ let start_addr = base_addr + i * ENTRY_SIZE;
+ (entry, start_addr..=start_addr + (ENTRY_SIZE - 1))
+ })
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-28 16:30:48 +0000