ruvix_physmem/
lib.rs

1//! # RuVix Physical Memory Allocator
2//!
3//! This crate provides a buddy allocator for physical page frame allocation
4//! as part of the RuVix Cognition Kernel (ADR-087).
5//!
6//! ## Overview
7//!
8//! The buddy allocator manages physical memory using power-of-two block sizes,
9//! enabling efficient allocation and deallocation with minimal fragmentation.
10//! It supports block sizes from 4KB (single page) to 2MB (512 pages).
11//!
12//! ## Architecture
13//!
14//! ```text
15//! +------------------+
16//! | BuddyAllocator   |
17//! |------------------|
18//! | free_lists[10]   | <- One list per order (0-9)
19//! | base_addr        | <- Start of managed memory
20//! | total_pages      | <- Total pages under management
21//! | stats            | <- Allocation statistics
22//! +------------------+
23//!          |
24//!          v
25//! +------------------+
26//! | Free Lists       |
27//! |------------------|
28//! | Order 0: 4KB     | <- Single pages
29//! | Order 1: 8KB     | <- 2 pages
30//! | Order 2: 16KB    | <- 4 pages
31//! | ...              |
32//! | Order 9: 2MB     | <- 512 pages
33//! +------------------+
34//! ```
35//!
36//! ## Features
37//!
38//! - `std`: Enable standard library support
39//! - `alloc`: Enable alloc crate support
40//! - `stats`: Enable detailed statistics collection
41//! - `debug-alloc`: Enable debug assertions for allocation tracking
42//!
43//! ## Example
44//!
45//! ```rust,ignore
46//! use ruvix_physmem::{BuddyAllocator, PhysAddr, PAGE_SIZE};
47//!
48//! // Create allocator for 16MB of memory starting at physical address 0x1000_0000
49//! let mut allocator = BuddyAllocator::new(PhysAddr::new(0x1000_0000), 4096);
50//!
51//! // Allocate 4 contiguous pages (16KB)
52//! if let Some(addr) = allocator.alloc_pages(4) {
53//!     // Use the memory...
54//!     allocator.dealloc_pages(addr, 4);
55//! }
56//! ```
57
58#![no_std]
59#![forbid(unsafe_code)]
60#![deny(missing_docs)]
61#![deny(clippy::all)]
62#![warn(clippy::pedantic)]
63#![allow(clippy::module_name_repetitions)]
64
65#[cfg(feature = "alloc")]
66extern crate alloc;
67
68#[cfg(feature = "std")]
69extern crate std;
70
71mod addr;
72mod allocator;
73mod error;
74mod frame;
75mod stats;
76
77pub use addr::PhysAddr;
78pub use allocator::BuddyAllocator;
79pub use error::PhysMemError;
80pub use frame::{PageFrame, PageOrder};
81pub use stats::AllocatorStats;
82
83// Re-export kernel error for convenience
84pub use ruvix_types::KernelError;
85
86/// Page size in bytes (4KB).
87pub const PAGE_SIZE: usize = 4096;
88
89/// Page size shift (log2(PAGE_SIZE)).
90pub const PAGE_SHIFT: usize = 12;
91
92/// Maximum order for buddy allocation (2^9 = 512 pages = 2MB).
93pub const MAX_ORDER: usize = 10;
94
95/// Minimum allocation unit (single page).
96pub const MIN_ORDER: usize = 0;
97
98/// Maximum block size in pages (2^(MAX_ORDER-1) = 512 pages).
99pub const MAX_BLOCK_PAGES: usize = 1 << (MAX_ORDER - 1);
100
101/// Maximum block size in bytes (2MB).
102pub const MAX_BLOCK_SIZE: usize = MAX_BLOCK_PAGES * PAGE_SIZE;
103
104/// Calculates the order required for a given number of pages.
105///
106/// Returns the smallest order `n` such that `2^n >= pages`.
107///
108/// # Examples
109///
110/// ```rust
111/// use ruvix_physmem::pages_to_order;
112///
113/// assert_eq!(pages_to_order(1), 0);  // 2^0 = 1 page
114/// assert_eq!(pages_to_order(2), 1);  // 2^1 = 2 pages
115/// assert_eq!(pages_to_order(3), 2);  // 2^2 = 4 pages (rounds up)
116/// assert_eq!(pages_to_order(4), 2);  // 2^2 = 4 pages
117/// assert_eq!(pages_to_order(5), 3);  // 2^3 = 8 pages (rounds up)
118/// ```
119#[inline]
120#[must_use]
121pub const fn pages_to_order(pages: usize) -> usize {
122    if pages == 0 {
123        return 0;
124    }
125
126    // Calculate ceiling of log2(pages)
127    let leading_zeros = (pages - 1).leading_zeros() as usize;
128    let bits = core::mem::size_of::<usize>() * 8;
129
130    if leading_zeros >= bits {
131        0
132    } else {
133        bits - leading_zeros
134    }
135}
136
137/// Calculates the number of pages for a given order.
138///
139/// Returns `2^order` pages.
140///
141/// # Examples
142///
143/// ```rust
144/// use ruvix_physmem::order_to_pages;
145///
146/// assert_eq!(order_to_pages(0), 1);   // 2^0 = 1 page
147/// assert_eq!(order_to_pages(1), 2);   // 2^1 = 2 pages
148/// assert_eq!(order_to_pages(2), 4);   // 2^2 = 4 pages
149/// assert_eq!(order_to_pages(9), 512); // 2^9 = 512 pages
150/// ```
151#[inline]
152#[must_use]
153pub const fn order_to_pages(order: usize) -> usize {
154    1 << order
155}
156
157/// Calculates the block size in bytes for a given order.
158///
159/// Returns `2^order * PAGE_SIZE` bytes.
160///
161/// # Examples
162///
163/// ```rust
164/// use ruvix_physmem::{order_to_bytes, PAGE_SIZE};
165///
166/// assert_eq!(order_to_bytes(0), PAGE_SIZE);       // 4KB
167/// assert_eq!(order_to_bytes(1), 2 * PAGE_SIZE);   // 8KB
168/// assert_eq!(order_to_bytes(9), 512 * PAGE_SIZE); // 2MB
169/// ```
170#[inline]
171#[must_use]
172pub const fn order_to_bytes(order: usize) -> usize {
173    order_to_pages(order) * PAGE_SIZE
174}
175
176/// Checks if an address is page-aligned.
177///
178/// # Examples
179///
180/// ```rust
181/// use ruvix_physmem::is_page_aligned;
182///
183/// assert!(is_page_aligned(0));
184/// assert!(is_page_aligned(4096));
185/// assert!(is_page_aligned(0x1000_0000));
186/// assert!(!is_page_aligned(1));
187/// assert!(!is_page_aligned(4097));
188/// ```
189#[inline]
190#[must_use]
191pub const fn is_page_aligned(addr: u64) -> bool {
192    addr & ((PAGE_SIZE as u64) - 1) == 0
193}
194
195/// Aligns an address down to the nearest page boundary.
196///
197/// # Examples
198///
199/// ```rust
200/// use ruvix_physmem::align_down;
201///
202/// assert_eq!(align_down(0), 0);
203/// assert_eq!(align_down(4095), 0);
204/// assert_eq!(align_down(4096), 4096);
205/// assert_eq!(align_down(4097), 4096);
206/// assert_eq!(align_down(8192), 8192);
207/// ```
208#[inline]
209#[must_use]
210pub const fn align_down(addr: u64) -> u64 {
211    addr & !((PAGE_SIZE as u64) - 1)
212}
213
214/// Aligns an address up to the nearest page boundary.
215///
216/// # Examples
217///
218/// ```rust
219/// use ruvix_physmem::align_up;
220///
221/// assert_eq!(align_up(0), 0);
222/// assert_eq!(align_up(1), 4096);
223/// assert_eq!(align_up(4095), 4096);
224/// assert_eq!(align_up(4096), 4096);
225/// assert_eq!(align_up(4097), 8192);
226/// ```
227#[inline]
228#[must_use]
229pub const fn align_up(addr: u64) -> u64 {
230    let page_mask = (PAGE_SIZE as u64) - 1;
231    (addr + page_mask) & !page_mask
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237
238    #[test]
239    fn test_pages_to_order() {
240        assert_eq!(pages_to_order(0), 0);
241        assert_eq!(pages_to_order(1), 0);
242        assert_eq!(pages_to_order(2), 1);
243        assert_eq!(pages_to_order(3), 2);
244        assert_eq!(pages_to_order(4), 2);
245        assert_eq!(pages_to_order(5), 3);
246        assert_eq!(pages_to_order(8), 3);
247        assert_eq!(pages_to_order(9), 4);
248        assert_eq!(pages_to_order(16), 4);
249        assert_eq!(pages_to_order(17), 5);
250        assert_eq!(pages_to_order(256), 8);
251        assert_eq!(pages_to_order(512), 9);
252    }
253
254    #[test]
255    fn test_order_to_pages() {
256        assert_eq!(order_to_pages(0), 1);
257        assert_eq!(order_to_pages(1), 2);
258        assert_eq!(order_to_pages(2), 4);
259        assert_eq!(order_to_pages(3), 8);
260        assert_eq!(order_to_pages(4), 16);
261        assert_eq!(order_to_pages(9), 512);
262    }
263
264    #[test]
265    fn test_order_to_bytes() {
266        assert_eq!(order_to_bytes(0), 4096);
267        assert_eq!(order_to_bytes(1), 8192);
268        assert_eq!(order_to_bytes(2), 16384);
269        assert_eq!(order_to_bytes(9), 2 * 1024 * 1024);
270    }
271
272    #[test]
273    fn test_page_alignment() {
274        assert!(is_page_aligned(0));
275        assert!(is_page_aligned(PAGE_SIZE as u64));
276        assert!(is_page_aligned(0x1000_0000));
277        assert!(!is_page_aligned(1));
278        assert!(!is_page_aligned(PAGE_SIZE as u64 - 1));
279    }
280
281    #[test]
282    fn test_align_down() {
283        assert_eq!(align_down(0), 0);
284        assert_eq!(align_down(1), 0);
285        assert_eq!(align_down(4095), 0);
286        assert_eq!(align_down(4096), 4096);
287        assert_eq!(align_down(4097), 4096);
288        assert_eq!(align_down(8191), 4096);
289        assert_eq!(align_down(8192), 8192);
290    }
291
292    #[test]
293    fn test_align_up() {
294        assert_eq!(align_up(0), 0);
295        assert_eq!(align_up(1), 4096);
296        assert_eq!(align_up(4095), 4096);
297        assert_eq!(align_up(4096), 4096);
298        assert_eq!(align_up(4097), 8192);
299        assert_eq!(align_up(8192), 8192);
300    }
301
302    #[test]
303    fn test_roundtrip_order_pages() {
304        for order in 0..MAX_ORDER {
305            let pages = order_to_pages(order);
306            let back = pages_to_order(pages);
307            assert_eq!(back, order, "Order {order} -> {pages} pages -> order {back}");
308        }
309    }
310}
ruvix_physmem/lib.rs

ruvix_physmem/
lib.rs
