diff options
Diffstat (limited to 'crates')
| -rw-r--r-- | crates/Cargo.lock | 25 | ||||
| -rw-r--r-- | crates/alloc_genmalloc/Cargo.toml | 3 | ||||
| -rw-r--r-- | crates/alloc_genmalloc/src/lib.rs | 348 | ||||
| -rw-r--r-- | crates/alloc_vma_tree/Cargo.toml | 2 | ||||
| -rw-r--r-- | crates/alloc_vma_tree/src/lib.rs | 11 | ||||
| -rw-r--r-- | crates/kernel/Cargo.toml | 2 | ||||
| -rw-r--r-- | crates/kernel/src/alloc.rs | 159 | ||||
| -rw-r--r-- | crates/kernel/src/arch/riscv64/mod.rs | 15 | ||||
| -rw-r--r-- | crates/kernel/src/cpu_locals.rs | 72 | ||||
| -rw-r--r-- | crates/kernel/src/lib.rs | 5 | ||||
| -rw-r--r-- | crates/utils/src/lib.rs | 4 |
11 files changed, 587 insertions, 59 deletions
diff --git a/crates/Cargo.lock b/crates/Cargo.lock index 41dfbb3..63385f0 100644 --- a/crates/Cargo.lock +++ b/crates/Cargo.lock @@ -95,12 +95,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba" [[package]] -name = "ghost-cell" -version = "0.2.6" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d8449d342b1c67f49169e92e71deb7b9b27f30062301a16dbc27a4cc8d2351b7" - -[[package]] name = "lazy_static" version = "1.5.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -314,10 +308,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "6980e8d7511241f8acf4aebddbb1ff938df5eebe98691418c4468d0b72a96a67" [[package]] -name = "static-rc" -version = "0.6.1" +name = "sptr" +version = "0.3.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "b91d0104a7b28aeda24b30919f83222570111ac0bf1aab23aaffb8f59330e654" +checksum = "3b9b39299b249ad65f3b7e96443bad61c02ca5cd3589f46cb6d610a0fd6c0d6a" + +[[package]] +name = "static_assertions" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a2eb9349b6444b326872e140eb1cf5e7c522154d69e7a0ffb0fb81c06b37543f" [[package]] name = "syn" @@ -354,6 +354,9 @@ version = "0.1.0" dependencies = [ "allocator-api2", "contracts", + "log", + "sptr", + "static_assertions", ] [[package]] @@ -370,8 +373,6 @@ version = "0.1.0" dependencies = [ "allocator-api2", "contracts", - "ghost-cell", - "static-rc", "vernos_utils", ] @@ -401,7 +402,9 @@ dependencies = [ "either", "log", "spin", + "static_assertions", "vernos_alloc_buddy", + "vernos_alloc_genmalloc", "vernos_alloc_physmem_free_list", "vernos_alloc_vma_tree", "vernos_device_tree", diff --git a/crates/alloc_genmalloc/Cargo.toml b/crates/alloc_genmalloc/Cargo.toml index 1099020..945ba0f 100644 --- a/crates/alloc_genmalloc/Cargo.toml +++ b/crates/alloc_genmalloc/Cargo.toml @@ -7,3 +7,6 @@ publish = false [dependencies] allocator-api2 = { version = "0.2.18", default-features = false } contracts = { version = "0.6.3", default-features = false } +log = { version = "0.4.20", default-features = false } +sptr = { version = "0.3.2", default-features = false } +static_assertions = { version = "1.1.0", default-features = false } diff --git a/crates/alloc_genmalloc/src/lib.rs b/crates/alloc_genmalloc/src/lib.rs index 06bc667..bb024a8 100644 --- a/crates/alloc_genmalloc/src/lib.rs +++ b/crates/alloc_genmalloc/src/lib.rs @@ -1,64 +1,282 @@ -//! A general-purpose allocator, based on the design of mimalloc [0, 1]. +//! A general-purpose allocator, based on the design of mimalloc [0, 1]. The design is summarized +//! below. +//! +//! Objects are separated into four classes, by size: +//! +//! - Small objects are less than or equal to 1KiB in size. Small objects get access to a special +//! fast-path for allocation that avoids performing a `.next_power_of_two()` on their size. This +//! fast-path is designed to be inlined. They get stored in 64KiB pages, which are stored in 4MiB +//! segments. +//! - Medium objects are greater than 1KiB in size, but less than or equal to 8KiB. Medium objects +//! have another fast-path, but it isn't inlinable and performs a `.next_power_of_two()`. Like +//! small objects, they get stored in 64KiB pages, which are stored in 4MiB segments. +//! - Large objects are greater than 8KiB in size, but less than or equal to 512KiB. Their pages +//! span the entire 4MiB of a segment. +//! - Huge objects are greater than 512KiB in size. They get a custom segment size with a single +//! page, sized to fit the object. +//! +//! This design has the property that the first address of an object will be less than 4MiB from +//! the start of the segment. By aligning segments to 4MiB, this lets us cheaply get a pointer to +//! the segment from a pointer to the object. //! //! [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 allocator_api2::alloc::{AllocError, Allocator, Layout}; use contracts::requires; use core::{ - ptr::NonNull, + cell::RefCell, + marker::PhantomData, + mem::MaybeUninit, + ptr::{addr_of_mut, null_mut, slice_from_raw_parts_mut, NonNull}, sync::atomic::{AtomicPtr, AtomicU16, Ordering}, }; +use sptr::invalid_mut; +use static_assertions::const_assert_eq; -/// The per-CPU structure. -struct Heap { +/// The per-CPU structure. This uses a `RefCell` for interior mutability. +#[derive(Debug)] +pub struct Heap<OS: OSServices>(RefCell<HeapInner<OS>>); + +#[derive(Debug)] +struct HeapInner<OS: OSServices> { /// Small objects (<=1024 bytes) have pointers directly to the page they allocate into. These /// are non-owning pointers. - pages_direct: [NonNull<Page>; 128], + pages_direct: [NonNull<Page>; LARGEST_SMALL_OBJECT >> 3], /// 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], + /// to and including 512KiB, plus one more for objects over 512KiB (huge objects). + pages: [PageLink; LARGEST_LARGE_OBJECT_SIZE_CLASS + 2], + + /// The sentinel node for segments that store small or medium objects that have free pages. + small_medium_segments_free: SegmentLink, + + /// The sentinel node for segments that store small or medium objects that have no free pages. + small_medium_segments_full: SegmentLink, + + /// The sentinel node for segments that store large or huge objects. + large_huge_segments: SegmentLink, + + _phantom: PhantomData<OS>, +} + +/// The log2 of the number of bytes in a segment (other than a segment created for a huge object). +pub const NON_HUGE_SEGMENT_SIZE_BITS: usize = 22; + +/// The number of bytes in a segment (other than a segment created for a huge object). +pub const NON_HUGE_SEGMENT_SIZE: usize = 4 << 20; + +const_assert_eq!(NON_HUGE_SEGMENT_SIZE, 1 << NON_HUGE_SEGMENT_SIZE_BITS); + +const SMALL_MEDIUM_PAGE_SIZE_BITS: u32 = 16; +const SMALL_MEDIUM_PAGE_SIZE: usize = 1 << SMALL_MEDIUM_PAGE_SIZE_BITS; +const SMALL_MEDIUM_PAGES_PER_SEGMENT: usize = + 1 << (NON_HUGE_SEGMENT_SIZE_BITS - SMALL_MEDIUM_PAGE_SIZE_BITS as usize); + +const LARGEST_SMALL_OBJECT: usize = 1024; +const LARGEST_MEDIUM_OBJECT: usize = 8 * 1024; +const LARGEST_LARGE_OBJECT: usize = 512 * 1024; +const LARGEST_SMALL_OBJECT_SIZE_CLASS: usize = 7; +const LARGEST_MEDIUM_OBJECT_SIZE_CLASS: usize = 10; +const LARGEST_LARGE_OBJECT_SIZE_CLASS: usize = 16; + +const_assert_eq!( + size_class(LARGEST_SMALL_OBJECT), + LARGEST_SMALL_OBJECT_SIZE_CLASS +); +const_assert_eq!( + size_class(LARGEST_MEDIUM_OBJECT), + LARGEST_MEDIUM_OBJECT_SIZE_CLASS +); +const_assert_eq!( + size_class(LARGEST_LARGE_OBJECT), + LARGEST_LARGE_OBJECT_SIZE_CLASS +); + +impl<OS: OSServices> Heap<OS> { + /// Initializes a `Heap`. After this, the `MaybeUninit` is initialized. + pub fn init(maybe_uninit: &mut MaybeUninit<Heap<OS>>) { + // Initialize the `RefCell` part. This... might not be sound. Hm. It also might blow the + // stack in debug builds, defeating the point of this whole function... + let refcell = unsafe { + maybe_uninit + .as_mut_ptr() + .cast::<MaybeUninit<RefCell<MaybeUninit<HeapInner<OS>>>>>() + .as_mut() + .unwrap_unchecked() + .write(RefCell::new(MaybeUninit::uninit())) + }; + + // Make accessors for the fields of the HeapInner. + let inner_ptr = refcell.get_mut().as_mut_ptr(); + let pages_direct_ptr = |i: usize| { + // SAFETY: For the `maybe_uninit` to have been valid, this must be sound. + unsafe { NonNull::new_unchecked(addr_of_mut!((*inner_ptr).pages_direct[i])) } + }; + let pages_ptr = |i: usize| { + // SAFETY: For the `maybe_uninit` to have been valid, this must be sound. + unsafe { NonNull::new_unchecked(addr_of_mut!((*inner_ptr).pages[i])) } + }; + + // Make a helper to self-link the segment lists. + // + // SAFETY: See the call sites. + let self_link_segments = |ptr: NonNull<SegmentLink>| unsafe { + (*ptr.as_ptr()).prev = ptr; + (*ptr.as_ptr()).next = ptr; + }; + + // Initialize each field. + for i in 0..128 { + // SAFETY: The returned pointer is valid. + unsafe { pages_direct_ptr(i).write(NonNull::from(&EMPTY_PAGE)) } + } + for i in 0..18 { + let ptr = pages_ptr(i); + // SAFETY: The returned pointer is valid. + unsafe { + ptr.write(PageLink { + prev: ptr, + next: ptr, + }) + } + } + // SAFETY: For the `maybe_uninit` to have been valid, getting these pointers must be sound. + // Self-linking the pointers is also sound as a result. + unsafe { + self_link_segments(NonNull::new_unchecked(addr_of_mut!( + (*inner_ptr).small_medium_segments_free + ))); + self_link_segments(NonNull::new_unchecked(addr_of_mut!( + (*inner_ptr).small_medium_segments_full + ))); + self_link_segments(NonNull::new_unchecked(addr_of_mut!( + (*inner_ptr).large_huge_segments + ))); + } + } + + /// Donates a segment to be used for small or medium objects. + /// + /// # Safety + /// + /// - `ptr` must convey ownership over the entire region. + /// - `thread_id` must be correct. + pub unsafe fn donate_small_medium_segment(&self, ptr: NonNull<[u8; NON_HUGE_SEGMENT_SIZE]>) { + self.0.borrow_mut().add_small_medium_segment(ptr) + } } -impl Heap { +impl<OS: OSServices> HeapInner<OS> { + /// Initializes a segment for small or medium objects, adding it to this heap. + unsafe fn add_small_medium_segment(&mut self, ptr: NonNull<[u8; NON_HUGE_SEGMENT_SIZE]>) { + // Initialize the segment to be self-linked. + let maybe_uninit: &mut MaybeUninit<Segment> = ptr.cast().as_mut(); + maybe_uninit.write(Segment { + link: SegmentLink { + prev: ptr.cast(), + next: ptr.cast(), + }, + header: SegmentHeader { + thread_id: OS::current_thread_id(), + page_shift: SMALL_MEDIUM_PAGE_SIZE_BITS, + }, + }); + + // Add the segment to the list of segments with free pages. + SegmentLink::add_next(NonNull::from(&self.small_medium_segments_free), ptr.cast()); + } + + /// Allocates small blocks of naturally-aligned memory. #[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]; + #[requires(size <= LARGEST_SMALL_OBJECT)] + #[inline] + fn alloc_small(&mut self, size: usize) -> Result<NonNull<[u8]>, AllocError> { + let size = (size + 7) & !0b111; + let small_size_class = (size >> 3) - 1; + let mut page = self.pages_direct[small_size_class]; 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()) + // SAFETY: `block` is a `NonNull`, so the slice pointer will non-null. + Ok(unsafe { + NonNull::new_unchecked(slice_from_raw_parts_mut(block.as_ptr().cast(), size)) + }) } - None => self.alloc_generic(size), + None => self.alloc_generic(size, size), } } - fn alloc_generic(&mut self, size: usize) -> Result<NonNull<u8>, AllocError> { + /// The slow-path of allocation. Allocates a block of any size and alignment, and does some + /// book-keeping tasks along the way. + fn alloc_generic(&mut self, size: usize, align: 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() }; + page = unsafe { (*page.as_ptr()).next }; todo!("{page:#?}") } - todo!() + */ + todo!("{:p}.alloc_generic({size}, {align})", self) } } -/// 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); +unsafe impl<OS: OSServices> Allocator for Heap<OS> { + #[inline] + fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> { + // Special-case ZSTs. + if layout.size() == 0 { + return Ok(unsafe { + NonNull::new_unchecked(slice_from_raw_parts_mut(invalid_mut(layout.align()), 0)) + }); + } + + // An objects with an alignment this big would break our invariants (namely, that we can + // get to the address of the segment by aligning down the address of the object to a 4MiB + // boundary). + if layout.align() >= NON_HUGE_SEGMENT_SIZE { + return Err(AllocError); + } + + let mut inner = self.0.borrow_mut(); + let size_if_small = layout.size().max(layout.align()); + if size_if_small <= LARGEST_SMALL_OBJECT { + // Fast path. + inner.alloc_small(size_if_small) + } else { + // Slow path. + inner.alloc_generic(layout.size(), layout.align()) + } + } - // Figure out the size class. - (size.next_power_of_two().trailing_zeros() - 3) as usize + #[inline] + unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) { + // Special-case ZSTs. + if layout.size() == 0 { + return; + } + + let self_ptr = self as *const Heap<OS>; + todo!("{self_ptr:p}.deallocate({ptr:p}, {layout:?})") + } +} + +/// Returns the index in the `pages` array of objects with the given size. +const fn size_class(size: usize) -> usize { + if size < 8 { + 0 + } else if size > LARGEST_LARGE_OBJECT { + 17 + } else { + (size.next_power_of_two().trailing_zeros() - 3) as usize + } } #[test] @@ -79,6 +297,53 @@ fn expected_size_class_values() { assert_eq!(size_class(4 * 1024 * 1024), 17); } +/// A segment is a container for pages, to amortize some of the overhead of allocating new pages. +#[repr(C)] +struct Segment { + /// The intrusive link in the circular doubly-linked list of segments . + link: SegmentLink, + + /// The fields other than the intrusive link in a segment's header. + header: SegmentHeader, +} + +/// The intrusive link in the circular doubly-linked list of pages of each size class. +#[derive(Debug)] +struct SegmentLink { + /// The previous page. + prev: NonNull<SegmentLink>, + + /// The next page. + next: NonNull<SegmentLink>, +} + +impl SegmentLink { + #[requires(SegmentLink::self_linked(item))] + pub unsafe fn add_next(list: NonNull<SegmentLink>, item: NonNull<SegmentLink>) { + let next = (*list.as_ptr()).next; + (*item.as_ptr()).next = next; + (*item.as_ptr()).prev = list; + + (*list.as_ptr()).next = item; + (*next.as_ptr()).prev = item; + } + + pub unsafe fn self_linked(ptr: NonNull<SegmentLink>) -> bool { + let SegmentLink { prev, next } = *ptr.as_ptr(); + ptr == prev && ptr == next + } +} + +/// The fields other than the intrusive link in a segment's header. +struct SegmentHeader { + /// The ID of the thread. + thread_id: usize, + + /// The amount to right-shift the offset of an object from the start of the segment by to get + /// its page index. + page_shift: u32, +} + /// A page is a block of memory that contains objects of a single size class. #[repr(C)] struct Page { @@ -89,13 +354,35 @@ struct Page { header: PageHeader, } +unsafe impl Send for Page {} +unsafe impl Sync for Page {} + +/// A fake page that causes allocation to go into the "slow path," so that we can allocate an +/// initial page of that size class. +static EMPTY_PAGE: Page = unsafe { + Page { + link: PageLink { + prev: NonNull::new_unchecked(&EMPTY_PAGE.link as *const PageLink as *mut PageLink), + next: NonNull::new_unchecked(&EMPTY_PAGE.link as *const PageLink as *mut PageLink), + }, + header: PageHeader { + alloc_list: None, + local_free_list: None, + thread_free_list: AtomicPtr::new(null_mut()), + used: AtomicU16::new(0), + thread_freed: AtomicU16::new(0), + }, + } +}; + /// The intrusive link in the circular doubly-linked list of pages of each size class. +#[derive(Debug)] struct PageLink { /// The previous page. - prev: Option<NonNull<PageLink>>, + prev: NonNull<PageLink>, /// The next page. - next: Option<NonNull<PageLink>>, + next: NonNull<PageLink>, } /// The fields other than the intrusive link in a page's header. @@ -133,3 +420,14 @@ fn atomic_push(node: &mut Block, list: &AtomicPtr<Block>) { } } } + +/// The OS services the allocator needs. +/// +/// # Safety +/// +/// All methods must be implemented according to their doc comments. +pub unsafe trait OSServices { + /// Returns the ID of the current thread. This can be arbitrary, so long as it is consistent + /// within a thread and no two threads with the same thread ID run at the same time. + fn current_thread_id() -> usize; +} diff --git a/crates/alloc_vma_tree/Cargo.toml b/crates/alloc_vma_tree/Cargo.toml index 20b1189..a927769 100644 --- a/crates/alloc_vma_tree/Cargo.toml +++ b/crates/alloc_vma_tree/Cargo.toml @@ -7,6 +7,4 @@ publish = false [dependencies] allocator-api2 = { version = "0.2.18", default-features = false } contracts = { version = "0.6.3", default-features = false } -ghost-cell = { version = "0.2.6", default-features = false } -static-rc = { version = "0.6.1", default-features = false } vernos_utils = { path = "../utils" } diff --git a/crates/alloc_vma_tree/src/lib.rs b/crates/alloc_vma_tree/src/lib.rs index 38dd312..e188ff7 100644 --- a/crates/alloc_vma_tree/src/lib.rs +++ b/crates/alloc_vma_tree/src/lib.rs @@ -21,6 +21,11 @@ pub struct VMATree<const PAGE_SIZE_BITS: usize, ALLOCATOR: Allocator> { } impl<const PAGE_SIZE_BITS: usize, ALLOCATOR: Allocator> VMATree<PAGE_SIZE_BITS, ALLOCATOR> { + /// The layout of a node in the tree. + /// + /// This is used in bootstrapping a mutually dependent allocator and `VMATree`. + pub const NODE_LAYOUT: Layout = Layout::new::<VMANode<PAGE_SIZE_BITS>>(); + /// Creates a new VMATree that will use the given allocator. pub const fn new_in(allocator: ALLOCATOR) -> VMATree<PAGE_SIZE_BITS, ALLOCATOR> { VMATree { @@ -167,19 +172,19 @@ impl<const PAGE_SIZE_BITS: usize> VMANode<PAGE_SIZE_BITS> { let mut ptr: NonNull<MaybeUninit<Self>> = allocator.allocate(layout)?.cast(); // SAFETY: This needs to be OK for the allocator to meet the conditions of its trait. - VMANode::init_in(unsafe { ptr.as_mut() }, addrs); + VMANode::init(unsafe { ptr.as_mut() }, addrs); Ok(ptr.cast()) } - /// Initializes a node. + /// Initializes a node. After this, the `MaybeUninit` is initialized. /// /// The node has the given range of addresses and is in the `Free` state. All of its pointers /// are self-pointers. #[requires(PAGE_SIZE_BITS > 0)] #[requires(addrs.start & ((1 << PAGE_SIZE_BITS) - 1) == 0)] #[requires(addrs.end & ((1 << PAGE_SIZE_BITS) - 1) == 0)] - pub fn init_in(maybe_uninit: &mut MaybeUninit<VMANode<PAGE_SIZE_BITS>>, addrs: Range<usize>) { + pub fn init(maybe_uninit: &mut MaybeUninit<VMANode<PAGE_SIZE_BITS>>, addrs: Range<usize>) { let ptr = NonNull::from(&*maybe_uninit).cast(); maybe_uninit.write(VMANode { addr_and_state: addrs.start, diff --git a/crates/kernel/Cargo.toml b/crates/kernel/Cargo.toml index 5fef50b..a447470 100644 --- a/crates/kernel/Cargo.toml +++ b/crates/kernel/Cargo.toml @@ -14,7 +14,9 @@ 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"] } +static_assertions = { version = "1.1.0", default-features = false } vernos_alloc_buddy = { path = "../alloc_buddy" } +vernos_alloc_genmalloc = { path = "../alloc_genmalloc" } vernos_alloc_physmem_free_list = { path = "../alloc_physmem_free_list" } vernos_alloc_vma_tree = { path = "../alloc_vma_tree" } vernos_device_tree = { path = "../device_tree" } diff --git a/crates/kernel/src/alloc.rs b/crates/kernel/src/alloc.rs index 203ef5c..920fe0a 100644 --- a/crates/kernel/src/alloc.rs +++ b/crates/kernel/src/alloc.rs @@ -1,13 +1,21 @@ //! Global structures for the allocators. -use crate::paging::{ - BuddyAllocator, MapError, MappingFlags, PageTable, ASID, HIMEM_BOT, LOMEM_TOP, - MAX_PAGE_SIZE_BITS, PAGE_SIZE, PAGE_SIZES, PAGE_SIZE_BITS, +use crate::{ + cpu_locals::CPULocals, + paging::{ + BuddyAllocator, MapError, MappingFlags, PageTable, ASID, HIMEM_BOT, LOMEM_TOP, + MAX_PAGE_SIZE_BITS, PAGE_SIZE, PAGE_SIZES, PAGE_SIZE_BITS, + }, }; -use allocator_api2::alloc::{AllocError, Global, GlobalAlloc, Layout}; +use allocator_api2::alloc::{AllocError, Allocator, GlobalAlloc, Layout}; use contracts::requires; -use core::{num::NonZero, ptr::NonNull}; +use core::{ + mem::MaybeUninit, + num::NonZero, + ptr::{null_mut, NonNull}, +}; use spin::mutex::FairMutex; +use vernos_alloc_genmalloc::{OSServices, NON_HUGE_SEGMENT_SIZE, NON_HUGE_SEGMENT_SIZE_BITS}; use vernos_alloc_vma_tree::VMATree; /// The global instance of the physical page allocator. @@ -17,12 +25,15 @@ static BUDDY_ALLOCATOR: FairMutex<Option<BuddyAllocator>> = FairMutex::new(None) static KERNEL_PAGE_TABLE: FairMutex<Option<&'static mut PageTable>> = FairMutex::new(None); /// The kernel's virtual memory allocator. -static KERNEL_VM_ALLOC: FairMutex<VMATree<PAGE_SIZE_BITS, Global>> = - FairMutex::new(VMATree::new_in(Global)); +static KERNEL_VM_ALLOC: FairMutex<VMATree<PAGE_SIZE_BITS, CPULocalHeap>> = + FairMutex::new(VMATree::new_in(CPULocalHeap)); /// The global allocator. #[global_allocator] -static GLOBAL_ALLOC: GlobalGenMalloc = GlobalGenMalloc; +static GLOBAL_ALLOC: CPULocalHeap = CPULocalHeap; + +/// The type of the kernel's allocator. +pub type Heap = vernos_alloc_genmalloc::Heap<HeapOSServices>; /// Initializes the kernel page table and enables paging. /// @@ -82,13 +93,73 @@ pub unsafe fn init_kernel_page_table(buddy_allocator: BuddyAllocator) { #[requires(himem_top & (PAGE_SIZE - 1) == 0)] #[requires(HIMEM_BOT < himem_top)] pub unsafe fn init_kernel_virtual_memory_allocator(himem_top: usize) { - // TODO: Bootstrap the allocator. + let mut himem_bot = HIMEM_BOT; + let mut himem_top = himem_top; + + // To bootstrap the allocator, we make an initial heap. First, we figure out where it should be + // laid out in himem, including putting a guard page beneath it. + let heap_top = himem_top; + himem_top -= size_of::<Heap>(); + const _: () = assert!(align_of::<Heap>() < PAGE_SIZE); + himem_top &= !(PAGE_SIZE - 1); + let heap_bot = himem_top; + let heap = (himem_top as *mut MaybeUninit<Heap>).as_mut().unwrap(); + himem_top -= PAGE_SIZE; + assert!(himem_bot < himem_top); + + // Map memory to back the heap. + for i in (heap_bot >> PAGE_SIZE_BITS)..(heap_top >> PAGE_SIZE_BITS) { + let vaddr = i << PAGE_SIZE_BITS; + let paddr = + alloc_page(PAGE_SIZE).expect("failed to allocate memory to bootstrap hart0's heap"); + kernel_map( + vaddr, + paddr.into(), + PAGE_SIZE, + MappingFlags::R | MappingFlags::W, + ) + .expect("failed to map memory to bootstrap hart0's heap"); + } + + // Next, we initialize the heap, which lets us initialize the CPU-locals as well. + Heap::init(heap); + CPULocals::init(0, heap.assume_init_mut()); + + // We need to initialize the heap with a segment that will let the virtual memory allocator + // allocate nodes. We lay it out at the _bottom_ of himem, since we know that'll be aligned. We + // add a guard page as well. + assert_eq!(himem_bot % NON_HUGE_SEGMENT_SIZE, 0); + let bootstrap_segment = himem_bot; + himem_bot += NON_HUGE_SEGMENT_SIZE; + assert_eq!(himem_bot & (PAGE_SIZE - 1), 0); + himem_bot += PAGE_SIZE; + + // We map the bootstrap segment. + for i in 0..(1 << (NON_HUGE_SEGMENT_SIZE_BITS - PAGE_SIZE_BITS)) { + let vaddr = bootstrap_segment + (i << PAGE_SIZE_BITS); + let paddr = alloc_page(PAGE_SIZE) + .expect("failed to allocate memory for hart0's heap's initial segment"); + kernel_map( + vaddr, + paddr.into(), + PAGE_SIZE, + MappingFlags::R | MappingFlags::W, + ) + .expect("failed to map memory for hart0's heap's initial segment"); + } + + // Donate the bootstrap segment to the heap. + // + // UNWRAP: Himem cannot be null. + CPULocals::get().heap().donate_small_medium_segment( + NonNull::new(bootstrap_segment as *mut [u8; NON_HUGE_SEGMENT_SIZE]).unwrap(), + ); // The error here _really_ ought to be impossible, because we just bootstrapped the allocator! // It definitely has free memory. let mut kernel_vm_alloc = KERNEL_VM_ALLOC.lock(); kernel_vm_alloc - .add(HIMEM_BOT..himem_top) + .add(himem_bot..himem_top) .expect("failed to set up the kernel's virtual memory allocator"); } @@ -136,20 +207,78 @@ pub fn kernel_map( kernel_page_table.map(&mut *buddy_allocator, vaddr, paddr, len, flags)?; vernos_utils::first_time! { log::warn!("TODO: sfence.vma"); - log::warn!("TODO: TLB shootdown"); } Ok(()) } /// A global allocator backed by a hart-local `vernos_alloc_genmalloc::Heap`. -struct GlobalGenMalloc; +struct CPULocalHeap; + +unsafe impl Allocator for CPULocalHeap { + fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> { + CPULocals::get().heap().allocate(layout) + } + + unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) { + CPULocals::get().heap().deallocate(ptr, layout) + } -unsafe impl GlobalAlloc for GlobalGenMalloc { + fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> { + CPULocals::get().heap().allocate_zeroed(layout) + } + + unsafe fn grow( + &self, + ptr: NonNull<u8>, + old_layout: Layout, + new_layout: Layout, + ) -> Result<NonNull<[u8]>, AllocError> { + CPULocals::get().heap().grow(ptr, old_layout, new_layout) + } + + unsafe fn grow_zeroed( + &self, + ptr: NonNull<u8>, + old_layout: Layout, + new_layout: Layout, + ) -> Result<NonNull<[u8]>, AllocError> { + CPULocals::get() + .heap() + .grow_zeroed(ptr, old_layout, new_layout) + } + + unsafe fn shrink( + &self, + ptr: NonNull<u8>, + old_layout: Layout, + new_layout: Layout, + ) -> Result<NonNull<[u8]>, AllocError> { + CPULocals::get().heap().shrink(ptr, old_layout, new_layout) + } +} + +unsafe impl GlobalAlloc for CPULocalHeap { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { - todo!("GlobalGenMalloc.alloc({layout:?})") + match self.allocate(layout) { + Ok(ptr) => ptr.as_ptr().cast(), + Err(AllocError) => null_mut(), + } } unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) { - todo!("GlobalGenMalloc.dealloc({ptr:?}, {layout:?})") + match NonNull::new(ptr) { + Some(ptr) => self.deallocate(ptr, layout), + None => unreachable!("dealloc({ptr:p}, {layout:?})"), + } + } +} + +/// The OS services provided to the allocator. +#[derive(Debug)] +pub struct HeapOSServices; + +unsafe impl OSServices for HeapOSServices { + fn current_thread_id() -> usize { + CPULocals::get().cpu_number } } diff --git a/crates/kernel/src/arch/riscv64/mod.rs b/crates/kernel/src/arch/riscv64/mod.rs index 011e244..48718c2 100644 --- a/crates/kernel/src/arch/riscv64/mod.rs +++ b/crates/kernel/src/arch/riscv64/mod.rs @@ -1,9 +1,22 @@ +use crate::cpu_locals::CPULocals; +use core::{arch::asm, ptr::NonNull}; + pub mod interrupts; pub mod paging; +/// Returns a pointer to the per-CPU locals. +pub fn get_cpu_locals() -> NonNull<CPULocals> { + // SAFETY: The entrypoint sets this up, and safe code cannot invalidate it. + unsafe { + let tp; + asm!("mv {out}, tp", out = out(reg) tp); + NonNull::new_unchecked(tp) + } +} + /// Halts the hart. pub fn sleep_forever() -> ! { loop { - unsafe { core::arch::asm!("wfi") } + unsafe { asm!("wfi") } } } diff --git a/crates/kernel/src/cpu_locals.rs b/crates/kernel/src/cpu_locals.rs new file mode 100644 index 0000000..fd826aa --- /dev/null +++ b/crates/kernel/src/cpu_locals.rs @@ -0,0 +1,72 @@ +use crate::{alloc::Heap, arch}; +use core::{cell::RefCell, marker::PhantomData, ops::DerefMut, ptr::addr_of_mut}; +use static_assertions::{assert_eq_size, assert_not_impl_any}; + +/// The data that is stored in a per-CPU structure. +#[derive(Debug)] +pub struct CPULocals { + /// The index of this CPU. + pub cpu_number: usize, + + /// The heap used by this CPU's allocator. + pub heap: RefCell<&'static mut Heap>, + + /// A canary for the `CPULocals` being initialized. + canary: usize, + + // This ensures that the type is not `Send`. + _phantom: PhantomData<*mut ()>, +} + +impl CPULocals { + /// Creates a new instance of the `CPULocals`, using it to initialize this CPU's `CPULocals`. + /// + /// # Safety + /// + /// - The CPULocals must not have already been initialized. + pub unsafe fn init(cpu_number: usize, heap: &'static mut Heap) { + arch::get_cpu_locals().write(CPULocals { + cpu_number, + heap: RefCell::new(heap), + canary: CANARY, + _phantom: PhantomData, + }); + } + + /// Returns the instance of the `CPULocals` for this CPU. + pub fn get() -> &'static CPULocals { + let ptr = arch::get_cpu_locals(); + // SAFETY: The entrypoint sets this up for hart0, and we allocate this for other harts. + unsafe { + let canary_ptr = addr_of_mut!((*ptr.as_ptr()).canary); + assert_eq!( + *canary_ptr, CANARY, + "CPULocals were not initialized (and we probably just did UB)" + ); + ptr.as_ref() + } + } + + /// Retrieves a reference to the heap. + /// + /// # Panics + /// + /// - Panics if the CPU-local heap was already borrowed. + /// - The returned guard will panic on deref if the heap was not initialized. + pub fn heap(&'static self) -> impl DerefMut<Target = &'static mut Heap> { + self.heap.borrow_mut() + } +} + +assert_eq_size!(CPULocals, [usize; 4]); +assert_not_impl_any!(CPULocals: Send); + +cfg_if::cfg_if! { + if #[cfg(target_pointer_width = "32")] { + const CANARY: usize = usize::from_le_bytes(*b"locl"); + } else if #[cfg(target_pointer_width = "64")] { + const CANARY: usize = usize::from_le_bytes(*b"CPULocal"); + } else { + compile_error!("unsupported platform"); + } +} diff --git a/crates/kernel/src/lib.rs b/crates/kernel/src/lib.rs index 7421649..fc96950 100644 --- a/crates/kernel/src/lib.rs +++ b/crates/kernel/src/lib.rs @@ -21,6 +21,7 @@ mod panic; pub mod alloc; pub mod arch; pub mod constants; +pub mod cpu_locals; pub mod logger; pub mod paging; @@ -98,6 +99,10 @@ pub unsafe extern "C" fn hart0_early_boot(early_boot_addrs: &mut EarlyBootAddrs) assert!(early_boot_addrs.initial_stack_start.is_aligned()); assert!(early_boot_addrs.stack_end.is_aligned()); assert!(early_boot_addrs.trampoline_start.is_aligned()); + assert_eq!( + arch::get_cpu_locals().as_ptr().wrapping_add(1) as *const (), + early_boot_addrs.stack_end.cast() + ); // Parse the DeviceTree. let flattened_device_tree = unsafe { early_boot_addrs.flattened_device_tree() }; diff --git a/crates/utils/src/lib.rs b/crates/utils/src/lib.rs index 1e8ddfb..2181046 100644 --- a/crates/utils/src/lib.rs +++ b/crates/utils/src/lib.rs @@ -134,10 +134,10 @@ impl_FromEndianBytes!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize); /// Runs the body block the first time it is encountered. #[macro_export] macro_rules! first_time { - ($($stmt:stmt)*) => {{ + ($($stmt:stmt;)*) => {{ use spin::lazy::Lazy; static LAZY: Lazy<()> = Lazy::new(|| { - $($stmt)* + $($stmt;)* }); *Lazy::force(&LAZY) }}; |