strat9_kernel/memory/
zone.rs

1// Memory zone management for buddy allocator
2
3use crate::arch::xshim::PhysAddr;
4use core::{ptr, slice};
5
6/// Memory zone types
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8#[repr(u8)]
9pub enum ZoneType {
10    /// DMA zone: 0-16MB (for legacy ISA DMA)
11    DMA = 0,
12    /// Normal zone: 16MB-896MB (for most allocations)
13    Normal = 1,
14    /// HighMem zone: > 896MB (for high memory)
15    HighMem = 2,
16}
17
18impl ZoneType {
19    /// Number of zones supported in Phase 1
20    pub const COUNT: usize = 3;
21}
22
23/// Maximum buddy order (0-11 for 4KB to 8MB blocks)
24pub const MAX_ORDER: usize = 11;
25
26/// Pageblock order used by the compaction-friendly migratetype grouping.
27///
28/// Order 9 corresponds to 2 MiB pageblocks, which is a pragmatic starting
29/// point on x86_64 because it matches the huge-page granularity commonly used
30/// by mature kernels for anti-fragmentation grouping.
31pub const PAGEBLOCK_ORDER: usize = 9;
32
33/// Number of 4 KiB pages inside one pageblock.
34pub const PAGEBLOCK_PAGES: usize = 1 << PAGEBLOCK_ORDER;
35
36/// Minimal free-block classes used by the buddy allocator.
37///
38/// This is intentionally smaller than Linux's full migratetype/pageblock
39/// matrix. The current design separates long-lived kernel pages from more
40/// reclaimable or relocatable user pages without introducing full migration
41/// machinery yet.
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43#[repr(u8)]
44pub enum Migratetype {
45    /// Default class for kernel data, page tables and other pinned pages.
46    Unmovable = 0,
47    /// Preferred class for user-space data and frames that can later be moved.
48    Movable = 1,
49}
50
51impl Migratetype {
52    /// Number of migratetypes tracked by the allocator.
53    pub const COUNT: usize = 2;
54
55    /// Stable iteration order used by diagnostics.
56    pub const ALL: [Self; Self::COUNT] = [Self::Unmovable, Self::Movable];
57
58    /// Returns the free-list index for this migratetype.
59    #[inline]
60    pub const fn index(self) -> usize {
61        self as usize
62    }
63
64    /// Returns the donor probing order for an allocation request.
65    ///
66    /// Bidirectional fallback is intentional: when the preferred migratetype
67    /// list is empty, the allocator can borrow from the other class. This
68    /// prevents allocation failures when one class is exhausted while the
69    /// other has free pages. The trade-off is potential cross-class
70    /// fragmentation, but this is acceptable for the current 2-class design.
71    #[inline]
72    pub const fn fallback_order(self) -> [Self; Self::COUNT] {
73        match self {
74            Self::Unmovable => [Self::Unmovable, Self::Movable],
75            Self::Movable => [Self::Movable, Self::Unmovable],
76        }
77    }
78}
79
80/// Bitmap used by buddy coalescing logic.
81///
82/// The storage is provided externally (stolen from early boot free pages)
83/// and addressed through HHDM.
84#[derive(Debug, Clone, Copy)]
85pub struct BuddyBitmap {
86    pub data: *mut u8,
87    pub num_bits: usize,
88}
89
90impl BuddyBitmap {
91    /// Empty bitmap for const initialization.
92    pub const fn empty() -> Self {
93        Self {
94            data: core::ptr::null_mut(),
95            num_bits: 0,
96        }
97    }
98
99    /// Returns whether empty.
100    #[inline]
101    pub fn is_empty(&self) -> bool {
102        self.data.is_null() || self.num_bits == 0
103    }
104
105    /// Toggle a bit and return its new value.
106    #[inline]
107    pub fn toggle(&self, idx: usize) -> bool {
108        debug_assert!(idx < self.num_bits);
109        let byte_idx = idx >> 3;
110        let mask = 1u8 << (idx & 7);
111        unsafe {
112            let byte = self.data.add(byte_idx);
113            let new_val = *byte ^ mask;
114            *byte = new_val;
115            (new_val & mask) != 0
116        }
117    }
118
119    /// Performs the test operation.
120    #[inline]
121    pub fn test(&self, idx: usize) -> bool {
122        if idx >= self.num_bits || self.is_empty() {
123            return false;
124        }
125        let byte_idx = idx >> 3;
126        let mask = 1u8 << (idx & 7);
127        unsafe { (*self.data.add(byte_idx) & mask) != 0 }
128    }
129
130    /// Performs the set operation.
131    #[inline]
132    pub fn set(&self, idx: usize) {
133        debug_assert!(idx < self.num_bits);
134        let byte_idx = idx >> 3;
135        let mask = 1u8 << (idx & 7);
136        unsafe {
137            *self.data.add(byte_idx) |= mask;
138        }
139    }
140
141    /// Performs the clear operation.
142    #[inline]
143    pub fn clear(&self, idx: usize) {
144        debug_assert!(idx < self.num_bits);
145        let byte_idx = idx >> 3;
146        let mask = 1u8 << (idx & 7);
147        unsafe {
148            *self.data.add(byte_idx) &= !mask;
149        }
150    }
151}
152
153/// One contiguous buddy-managed extent inside a zone.
154#[derive(Clone, Copy)]
155pub struct ZoneSegment {
156    /// Base physical address of this contiguous segment.
157    pub base: PhysAddr,
158
159    /// Number of pages managed by this segment.
160    pub page_count: usize,
161
162    /// Free lists for each order within this segment, split by migratetype.
163    pub free_lists: [[u64; MAX_ORDER + 1]; Migratetype::COUNT],
164
165    /// Per-order parity bitmaps scoped to this segment only.
166    pub buddy_bitmaps: [BuddyBitmap; MAX_ORDER + 1],
167
168    /// Per-pageblock migratetype tags used to keep movable and unmovable frees grouped.
169    pub pageblock_tags: *mut u8,
170
171    /// Number of pageblocks described by `pageblock_tags`.
172    pub pageblock_count: usize,
173
174    /// Optional debug bitmap: 1 bit per page = allocated.
175    #[cfg(debug_assertions)]
176    pub alloc_bitmap: BuddyBitmap,
177}
178
179impl ZoneSegment {
180    /// Empty segment for const initialization.
181    pub const fn empty() -> Self {
182        Self {
183            base: PhysAddr::new(0),
184            page_count: 0,
185            free_lists: [[0; MAX_ORDER + 1]; Migratetype::COUNT],
186            buddy_bitmaps: [BuddyBitmap::empty(); MAX_ORDER + 1],
187            pageblock_tags: core::ptr::null_mut(),
188            pageblock_count: 0,
189            #[cfg(debug_assertions)]
190            alloc_bitmap: BuddyBitmap::empty(),
191        }
192    }
193
194    /// Returns whether this segment is populated.
195    #[inline]
196    pub fn is_populated(&self) -> bool {
197        self.page_count != 0
198    }
199
200    /// Returns whether an address falls within the segment.
201    #[inline]
202    pub fn contains_address(&self, addr: PhysAddr) -> bool {
203        if !self.is_populated() {
204            return false;
205        }
206        let start = self.base.as_u64();
207        let end = start + (self.page_count as u64 * 4096);
208        let value = addr.as_u64();
209        value >= start && value < end
210    }
211
212    /// Returns the exclusive end address of the segment.
213    #[inline]
214    pub fn end_address(&self) -> u64 {
215        self.base.as_u64() + (self.page_count as u64 * 4096)
216    }
217
218    /// Compare by base address for binary search.
219    #[inline]
220    pub fn base_cmp(&self, addr: u64) -> core::cmp::Ordering {
221        self.base.as_u64().cmp(&addr)
222    }
223
224    /// Count the number of free blocks at a given order.
225    pub fn free_list_count(&self, order: u8) -> usize {
226        Migratetype::ALL
227            .into_iter()
228            .map(|migratetype| self.free_list_count_for(order, migratetype))
229            .sum()
230    }
231
232    /// Count the number of free blocks at a given order and migratetype.
233    pub fn free_list_count_for(&self, order: u8, migratetype: Migratetype) -> usize {
234        let mut count = 0usize;
235        let mut phys = self.free_lists[migratetype.index()][order as usize];
236        while phys != 0 {
237            count += 1;
238            let meta = crate::memory::frame::get_meta(PhysAddr::new(phys));
239            phys = if meta.next() == crate::memory::frame::FRAME_META_LINK_NONE {
240                0
241            } else {
242                meta.next()
243            };
244        }
245        count
246    }
247}
248
249/// Memory zone with buddy allocator free lists
250pub struct Zone {
251    /// Zone type
252    pub zone_type: ZoneType,
253
254    /// Base physical address of this zone
255    pub base: PhysAddr,
256
257    /// Total number of managed pages in this zone.
258    pub page_count: usize,
259
260    /// Pages reported as usable RAM by the boot memory map for this zone.
261    pub present_pages: usize,
262
263    /// Total address span covered by this zone metadata, in pages.
264    ///
265    /// Unlike `page_count`, this includes holes and is kept for diagnostics.
266    pub span_pages: usize,
267
268    /// Number of allocated pages
269    pub allocated: usize,
270
271    /// Pages removed from management during boot reservations.
272    pub reserved_pages: usize,
273
274    /// Hard reserve kept available for lower zones or emergency paths.
275    pub lowmem_reserve_pages: usize,
276
277    /// Watermark below which this zone should be avoided when possible.
278    pub watermark_min: usize,
279
280    /// Advisory low watermark for diagnostics and future reclaim hooks.
281    pub watermark_low: usize,
282
283    /// Advisory high watermark for diagnostics and future reclaim hooks.
284    pub watermark_high: usize,
285
286    /// Number of populated contiguous segments in this zone.
287    pub segment_count: usize,
288
289    /// Total number of segment slots reserved for this zone.
290    pub segment_capacity: usize,
291
292    /// Independently managed contiguous segments inside this zone.
293    pub segments: *mut ZoneSegment,
294}
295
296impl Zone {
297    /// Create a new empty zone
298    pub const fn new(zone_type: ZoneType) -> Self {
299        Zone {
300            zone_type,
301            base: PhysAddr::new(0),
302            page_count: 0,
303            present_pages: 0,
304            span_pages: 0,
305            allocated: 0,
306            reserved_pages: 0,
307            lowmem_reserve_pages: 0,
308            watermark_min: 0,
309            watermark_low: 0,
310            watermark_high: 0,
311            segment_count: 0,
312            segment_capacity: 0,
313            segments: ptr::null_mut(),
314        }
315    }
316
317    /// Returns the reserved segment storage as a slice.
318    #[inline]
319    pub fn segments(&self) -> &[ZoneSegment] {
320        if self.segment_capacity == 0 || self.segments.is_null() {
321            &[]
322        } else {
323            unsafe { slice::from_raw_parts(self.segments, self.segment_capacity) }
324        }
325    }
326
327    /// Returns the reserved segment storage as a mutable slice.
328    #[inline]
329    pub fn segments_mut(&mut self) -> &mut [ZoneSegment] {
330        if self.segment_capacity == 0 || self.segments.is_null() {
331            &mut []
332        } else {
333            unsafe { slice::from_raw_parts_mut(self.segments, self.segment_capacity) }
334        }
335    }
336
337    /// Reset the zone's segment storage metadata.
338    #[inline]
339    pub fn clear_segments(&mut self) {
340        self.segment_count = 0;
341        self.segment_capacity = 0;
342        self.segments = ptr::null_mut();
343    }
344
345    /// Check if an address is within this zone
346    pub fn contains_address(&self, addr: PhysAddr) -> bool {
347        self.segments()
348            .iter()
349            .take(self.segment_count)
350            .any(|segment| segment.contains_address(addr))
351    }
352
353    /// Get number of available (free) pages
354    pub fn available_pages(&self) -> usize {
355        self.page_count.saturating_sub(self.allocated)
356    }
357
358    /// Count the number of free blocks at a given order.
359    ///
360    /// Walks the buddy free list. Safe because we only read the next link from
361    /// the per-frame [`crate::memory::frame::MetaSlot`] (not from mapped page bytes).
362    pub fn free_list_count(&self, order: u8) -> usize {
363        self.segments()
364            .iter()
365            .take(self.segment_count)
366            .map(|segment| segment.free_list_count(order))
367            .sum()
368    }
369
370    /// Count the number of free blocks at a given order for one migratetype.
371    pub fn free_list_count_for(&self, order: u8, migratetype: Migratetype) -> usize {
372        self.segments()
373            .iter()
374            .take(self.segment_count)
375            .map(|segment| segment.free_list_count_for(order, migratetype))
376            .sum()
377    }
378
379    /// Returns the total free pages by migratetype across all orders.
380    pub fn free_pages_by_migratetype(&self) -> [usize; Migratetype::COUNT] {
381        let mut totals = [0usize; Migratetype::COUNT];
382        for migratetype in Migratetype::ALL {
383            let idx = migratetype.index();
384            for order in 0..=MAX_ORDER {
385                let blocks = self.free_list_count_for(order as u8, migratetype);
386                totals[idx] = totals[idx].saturating_add(blocks << order);
387            }
388        }
389        totals
390    }
391
392    /// Returns the number of free pages currently available in blocks of at least `order`.
393    ///
394    /// This is the relevant numerator for fragmentation analysis of an
395    /// allocation request at `order`: pages on smaller free lists exist, but
396    /// cannot satisfy that request without prior coalescing.
397    pub fn free_pages_at_or_above_order(&self, order: u8) -> usize {
398        let mut pages = 0usize;
399        for current_order in order as usize..=MAX_ORDER {
400            pages =
401                pages.saturating_add(self.free_list_count(current_order as u8) << current_order);
402        }
403        pages
404    }
405
406    /// Returns a simple fragmentation score for `order`, expressed as a percentage.
407    ///
408    /// `0` means all currently free pages are still usable for an allocation of
409    /// that order. `100` means all free pages are trapped in blocks smaller than
410    /// the requested order. `cached_order0_pages` accounts for pages parked in
411    /// per-CPU caches, which behave like order-0 fragments until drained.
412    pub fn fragmentation_score(&self, order: u8, cached_order0_pages: usize) -> usize {
413        if order == 0 {
414            return 0;
415        }
416
417        let total_free = self.available_pages().saturating_add(cached_order0_pages);
418        if total_free == 0 {
419            return 0;
420        }
421
422        let usable = self.free_pages_at_or_above_order(order);
423        let fragmented = total_free.saturating_sub(usable);
424        fragmented.saturating_mul(100) / total_free
425    }
426
427    /// Compute both free pages at or above order and fragmentation score in a single pass.
428    ///
429    /// Returns `(usable_pages, fragmentation_score)`. This avoids redundant free list
430    /// walks when both values are needed (e.g., in compaction candidate selection).
431    pub fn usable_pages_and_fragmentation(
432        &self,
433        order: u8,
434        cached_order0_pages: usize,
435    ) -> (usize, usize) {
436        if order == 0 {
437            return (
438                self.available_pages().saturating_add(cached_order0_pages),
439                0,
440            );
441        }
442
443        let total_free = self.available_pages().saturating_add(cached_order0_pages);
444        if total_free == 0 {
445            return (0, 0);
446        }
447
448        let usable = self.free_pages_at_or_above_order(order);
449        let fragmented = total_free.saturating_sub(usable);
450        let score = fragmented.saturating_mul(100) / total_free;
451        (usable, score)
452    }
453
454    /// Returns the largest order that currently has at least one free block.
455    pub fn largest_free_order(&self) -> Option<u8> {
456        for order in (0..=MAX_ORDER).rev() {
457            if self.free_list_count(order as u8) > 0 {
458                return Some(order as u8);
459            }
460        }
461        None
462    }
463}
464
465// SAFETY: access is protected by the allocator lock.
466unsafe impl Send for BuddyBitmap {}
467// SAFETY: raw segment storage is owned and mutated only under the allocator lock.
468unsafe impl Send for Zone {}
strat9_kernel/memory/zone.rs

strat9_kernel/memory/
zone.rs
