From 386df39c9866a4d945de46ef0dcab2363c674e0e Mon Sep 17 00:00:00 2001 From: Nathan Ringo Date: Sun, 1 Sep 2024 19:59:44 -0500 Subject: Move almost all the kernel into crates/. --- kernel/src/allocators/buddy/mod.rs | 52 -------------------------------------- 1 file changed, 52 deletions(-) delete mode 100644 kernel/src/allocators/buddy/mod.rs (limited to 'kernel/src/allocators/buddy/mod.rs') 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); -- cgit v1.2.3