strat9_kernel/memory/
boot_alloc.rs

1//! Allocateur physique de boot pour les structures permanentes du noyau.
2
3use crate::{
4    arch::xshim::PhysAddr,
5    boot::entry::{MemoryKind, MemoryRegion},
6    memory::phys_to_virt,
7    serial_println,
8    sync::SpinLock,
9};
10
11const PAGE_SIZE: u64 = 4096;
12pub const MAX_BOOT_ALLOC_REGIONS: usize = 512;
13pub const MAX_PROTECTED_RANGES: usize = 32;
14
15#[derive(Clone, Copy)]
16struct BootRegion {
17    start: u64,
18    end: u64,
19}
20
21impl BootRegion {
22    const fn empty() -> Self {
23        Self { start: 0, end: 0 }
24    }
25
26    #[inline]
27    const fn is_empty(&self) -> bool {
28        self.start >= self.end
29    }
30}
31
32pub struct BootAllocator {
33    regions: [BootRegion; MAX_BOOT_ALLOC_REGIONS],
34    len: usize,
35    accessible_limit: u64,
36}
37
38#[derive(Clone, Copy, Debug, Default)]
39pub struct BootAllocStats {
40    pub region_count: usize,
41    pub total_free_bytes: u64,
42    pub largest_region_bytes: u64,
43    pub accessible_limit: u64,
44}
45
46impl BootAllocator {
47    pub const fn new() -> Self {
48        Self {
49            regions: [BootRegion::empty(); MAX_BOOT_ALLOC_REGIONS],
50            len: 0,
51            accessible_limit: 0,
52        }
53    }
54
55    pub fn init(&mut self, regions: &[MemoryRegion]) {
56        // TEMP DEBUG: count init() calls - the post-switch V-storm may be this
57        // function being re-entered by a corrupted resume.
58        {
59            static INIT_CALLS: core::sync::atomic::AtomicUsize =
60                core::sync::atomic::AtomicUsize::new(0);
61            let n = INIT_CALLS.fetch_add(1, core::sync::atomic::Ordering::Relaxed) + 1;
62            unsafe {
63                let hex = b"0123456789abcdef";
64                core::arch::asm!("out 0xe9, al", in("al") b'I', options(nomem, nostack));
65                for sh in [12usize, 8, 4, 0] {
66                    let nib = hex[((n >> sh) & 0xF) as usize];
67                    core::arch::asm!("out 0xe9, al", in("al") nib, options(nomem, nostack));
68                }
69                core::arch::asm!("out 0xe9, al", in("al") b'\n', options(nomem, nostack));
70            }
71        }
72        crate::e9_println!("BI init");
73        if self.len != 0 {
74            self.reset();
75        }
76        crate::e9_println!("BI reset");
77
78        for region in regions {
79            if !matches!(region.kind, MemoryKind::Free | MemoryKind::Reclaim) {
80                continue;
81            }
82
83            let start = align_up(region.base, PAGE_SIZE);
84            let end = align_down(region.base.saturating_add(region.size), PAGE_SIZE);
85            if start >= end {
86                continue;
87            }
88
89            self.push_region(BootRegion { start, end });
90        }
91        crate::e9_println!("BI push");
92
93        self.normalize_regions();
94        crate::e9_println!("BI norm1");
95
96        crate::e9_mark!(b'U');
97        let guard = PROTECTED_RANGES.lock();
98        crate::e9_mark!(b'u');
99        for entry in guard.iter() {
100            let (base, size) = match *entry {
101                Some(v) => v,
102                None => continue,
103            };
104            if size == 0 {
105                continue;
106            }
107            crate::e9_mark!(b'V');
108            self.exclude_range(
109                align_down(base, PAGE_SIZE),
110                align_up(base.saturating_add(size), PAGE_SIZE),
111            );
112            crate::e9_mark!(b'v');
113        }
114        drop(guard);
115        crate::e9_mark!(b'W');
116
117        self.normalize_regions();
118        crate::e9_println!("BI norm2 pre");
119        self.rebuild_accessible_limit();
120        crate::e9_println!("BI done");
121    }
122
123    pub fn alloc(&mut self, size: usize, align: usize) -> PhysAddr {
124        self.try_alloc(size, align).unwrap_or_else(|| {
125            panic!(
126                "boot allocator: out of physical memory for size={} align={}",
127                size, align
128            )
129        })
130    }
131
132    pub fn try_alloc(&mut self, size: usize, align: usize) -> Option<PhysAddr> {
133        if crate::debug_cfg::is_quiet() {
134            // TEMP DEBUG: 'b' pulse per try_alloc (throttled by caller loops anyway).
135            unsafe { core::arch::asm!("out 0xe9, al", in("al") b'b', options(nomem, nostack)) };
136        }
137        if size == 0 {
138            return Some(PhysAddr::new(0));
139        }
140
141        let align = normalize_align(align) as u64;
142        let size = align_up(size as u64, PAGE_SIZE);
143
144        for idx in 0..self.len {
145            let region = self.regions[idx];
146            if region.is_empty() {
147                continue;
148            }
149
150            let alloc_start = align_up(region.start, align);
151            let alloc_end = alloc_start.checked_add(size)?;
152            if alloc_end > region.end {
153                continue;
154            }
155
156            self.consume_region(idx, alloc_start, alloc_end);
157            return Some(PhysAddr::new(alloc_start));
158        }
159
160        let stats = self.stats();
161        serial_println!(
162            "[boot_alloc] try_alloc failed: requested={} aligned={} largest_region={} regions={} total_free={}",
163            size as usize,
164            align as usize,
165            stats.largest_region_bytes as usize,
166            stats.region_count,
167            stats.total_free_bytes as usize
168        );
169        None
170    }
171
172    pub fn try_alloc_accessible(&mut self, size: usize, align: usize) -> Option<PhysAddr> {
173        if crate::debug_cfg::is_quiet() {
174            unsafe { core::arch::asm!("out 0xe9, al", in("al") b'a', options(nomem, nostack)) };
175        }
176        if size == 0 {
177            return Some(PhysAddr::new(0));
178        }
179
180        let align = normalize_align(align) as u64;
181        let size = align_up(size as u64, PAGE_SIZE);
182
183        for idx in 0..self.len {
184            let region = self.regions[idx];
185            if region.is_empty() {
186                continue;
187            }
188
189            let alloc_start = align_up(region.start, align);
190            let alloc_end = alloc_start.checked_add(size)?;
191            if alloc_end > region.end {
192                continue;
193            }
194
195            if self.accessible_limit != 0 && alloc_end > self.accessible_limit {
196                continue;
197            }
198
199            if !crate::memory::paging::is_hhdm_range_mapped_now(alloc_start, size) {
200                continue;
201            }
202
203            self.consume_region(idx, alloc_start, alloc_end);
204            return Some(PhysAddr::new(alloc_start));
205        }
206
207        let stats = self.stats();
208        serial_println!(
209            "[boot_alloc] try_alloc_accessible failed: requested={} aligned={} largest_region={} regions={} total_free={} accessible_limit={:#x}",
210            size as usize,
211            align as usize,
212            stats.largest_region_bytes as usize,
213            stats.region_count,
214            stats.total_free_bytes as usize
215            ,stats.accessible_limit
216        );
217        None
218    }
219
220    pub fn snapshot_free_regions(&self, out: &mut [MemoryRegion]) -> usize {
221        let count = core::cmp::min(self.len, out.len());
222        for (dst, region) in out.iter_mut().zip(self.regions.iter()).take(count) {
223            *dst = MemoryRegion {
224                base: region.start,
225                size: region.end.saturating_sub(region.start),
226                kind: MemoryKind::Free,
227            };
228        }
229        count
230    }
231
232    fn reset(&mut self) {
233        self.regions = [BootRegion::empty(); MAX_BOOT_ALLOC_REGIONS];
234        self.len = 0;
235        self.accessible_limit = 0;
236    }
237
238    fn push_region(&mut self, region: BootRegion) {
239        if region.is_empty() || self.len >= self.regions.len() {
240            return;
241        }
242        self.regions[self.len] = region;
243        self.len += 1;
244    }
245
246    fn exclude_range(&mut self, exclude_start: u64, exclude_end: u64) {
247        if exclude_start >= exclude_end {
248            return;
249        }
250
251        let mut idx = 0usize;
252        while idx < self.len {
253            let region = self.regions[idx];
254            if exclude_end <= region.start || exclude_start >= region.end {
255                idx += 1;
256                continue;
257            }
258
259            if exclude_start <= region.start && exclude_end >= region.end {
260                self.remove_region(idx);
261                continue;
262            }
263
264            if exclude_start <= region.start {
265                self.regions[idx].start = exclude_end.min(region.end);
266                idx += 1;
267                continue;
268            }
269
270            if exclude_end >= region.end {
271                self.regions[idx].end = exclude_start.max(region.start);
272                idx += 1;
273                continue;
274            }
275
276            let right = BootRegion {
277                start: exclude_end,
278                end: region.end,
279            };
280            self.regions[idx].end = exclude_start;
281            if self.len < self.regions.len() {
282                self.insert_region(idx + 1, right);
283            }
284            idx += 2;
285        }
286
287        self.normalize_regions();
288    }
289
290    fn consume_region(&mut self, idx: usize, alloc_start: u64, alloc_end: u64) {
291        let region = self.regions[idx];
292
293        if alloc_start <= region.start && alloc_end >= region.end {
294            self.remove_region(idx);
295            self.rebuild_accessible_limit();
296            return;
297        }
298
299        if alloc_start <= region.start {
300            self.regions[idx].start = alloc_end;
301            self.rebuild_accessible_limit();
302            return;
303        }
304
305        if alloc_end >= region.end {
306            self.regions[idx].end = alloc_start;
307            self.rebuild_accessible_limit();
308            return;
309        }
310
311        let right = BootRegion {
312            start: alloc_end,
313            end: region.end,
314        };
315        self.regions[idx].end = alloc_start;
316        if self.len < self.regions.len() {
317            self.insert_region(idx + 1, right);
318        }
319
320        self.normalize_regions();
321        self.rebuild_accessible_limit();
322    }
323
324    fn insert_region(&mut self, idx: usize, region: BootRegion) {
325        if region.is_empty() || self.len >= self.regions.len() {
326            return;
327        }
328
329        for slot in (idx..self.len).rev() {
330            self.regions[slot + 1] = self.regions[slot];
331        }
332        self.regions[idx] = region;
333        self.len += 1;
334    }
335
336    fn remove_region(&mut self, idx: usize) {
337        if idx >= self.len {
338            return;
339        }
340        for slot in idx..self.len.saturating_sub(1) {
341            self.regions[slot] = self.regions[slot + 1];
342        }
343        if self.len != 0 {
344            self.len -= 1;
345            self.regions[self.len] = BootRegion::empty();
346        }
347    }
348
349    fn normalize_regions(&mut self) {
350        crate::e9_println!("NR begin");
351        if self.len <= 1 {
352            crate::e9_mark!(b'S');
353            self.rebuild_accessible_limit();
354            crate::e9_mark!(b's');
355            return;
356        }
357
358        crate::e9_mark!(b'B');
359        for i in 1..self.len {
360            let cur = self.regions[i];
361            let mut j = i;
362            while j > 0 && self.regions[j - 1].start > cur.start {
363                self.regions[j] = self.regions[j - 1];
364                j -= 1;
365            }
366            self.regions[j] = cur;
367        }
368        crate::e9_mark!(b'b');
369
370        let mut write = 0usize;
371        for read in 0..self.len {
372            let cur = self.regions[read];
373            if cur.is_empty() {
374                continue;
375            }
376            if write == 0 {
377                self.regions[write] = cur;
378                write += 1;
379                continue;
380            }
381            let prev = self.regions[write - 1];
382            if cur.start <= prev.end {
383                self.regions[write - 1].end = prev.end.max(cur.end);
384            } else {
385                self.regions[write] = cur;
386                write += 1;
387            }
388        }
389        crate::e9_mark!(b'c');
390
391        for slot in write..self.regions.len() {
392            self.regions[slot] = BootRegion::empty();
393        }
394        self.len = write;
395        self.rebuild_accessible_limit();
396        crate::e9_mark!(b'd');
397    }
398
399    /// Recompute the highest currently reachable physical byte for HHDM-backed boot allocations.
400    fn rebuild_accessible_limit(&mut self) {
401        // TEMP DEBUG: count rebuild calls; pulse a hex digit every 65536.
402        REBUILD_CALL_COUNT.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
403        let n = REBUILD_CALL_COUNT.load(core::sync::atomic::Ordering::Relaxed);
404        if n % 65536 == 0 {
405            unsafe {
406                let hex = b"0123456789abcdef";
407                core::arch::asm!("out 0xe9, al", in("al") b'$', options(nomem, nostack));
408                for sh in [28usize, 24, 20, 16, 12, 8, 4, 0] {
409                    let nib = hex[((n >> sh) & 0xF) as usize];
410                    core::arch::asm!("out 0xe9, al", in("al") nib, options(nomem, nostack));
411                }
412                core::arch::asm!("out 0xe9, al", in("al") b'\n', options(nomem, nostack));
413            }
414        }
415        crate::e9_mark!(b'Q');
416        let mut limit = 0u64;
417        crate::e9_mark!(b'R');
418        for region in self.regions.iter().take(self.len).copied() {
419            crate::e9_mark!(b'S');
420            limit = limit.max(self.accessible_prefix_end(region));
421            crate::e9_mark!(b's');
422        }
423        crate::e9_mark!(b'T');
424        self.accessible_limit = limit;
425        crate::e9_mark!(b't');
426    }
427
428    /// Return the end of the longest mapped prefix of `region` visible through the current HHDM.
429    fn accessible_prefix_end(&self, region: BootRegion) -> u64 {
430        if region.is_empty() {
431            return 0;
432        }
433
434        let total_pages = ((region.end - region.start) / PAGE_SIZE) as usize;
435        if total_pages == 0 {
436            return 0;
437        }
438
439        let mut low = 0usize;
440        let mut high = total_pages;
441        while low < high {
442            let mid = (low + high).div_ceil(2);
443            let size = mid as u64 * PAGE_SIZE;
444            if crate::memory::paging::is_hhdm_range_mapped_now(region.start, size) {
445                low = mid;
446            } else {
447                high = mid - 1;
448            }
449        }
450
451        region.start + low as u64 * PAGE_SIZE
452    }
453
454    pub fn stats(&self) -> BootAllocStats {
455        let mut total = 0u64;
456        let mut largest = 0u64;
457        for region in self.regions.iter().take(self.len) {
458            let size = region.end.saturating_sub(region.start);
459            total = total.saturating_add(size);
460            largest = largest.max(size);
461        }
462        BootAllocStats {
463            region_count: self.len,
464            total_free_bytes: total,
465            largest_region_bytes: largest,
466            accessible_limit: self.accessible_limit,
467        }
468    }
469}
470
471static BOOT_ALLOCATOR: SpinLock<BootAllocator> = SpinLock::new(BootAllocator::new());
472static REBUILD_CALL_COUNT: core::sync::atomic::AtomicUsize =
473    core::sync::atomic::AtomicUsize::new(0);
474static PROTECTED_RANGES: SpinLock<[Option<(u64, u64)>; MAX_PROTECTED_RANGES]> =
475    SpinLock::new([None; MAX_PROTECTED_RANGES]);
476
477pub fn init_boot_allocator(regions: &[MemoryRegion]) {
478    crate::e9_println!("IBA enter");
479    let mut guard = BOOT_ALLOCATOR.lock();
480    crate::e9_println!("IBA locked");
481    guard.init(regions);
482    crate::e9_println!("IBA init done");
483    drop(guard);
484}
485
486pub fn get_boot_allocator() -> &'static SpinLock<BootAllocator> {
487    &BOOT_ALLOCATOR
488}
489
490pub fn boot_allocator_stats() -> BootAllocStats {
491    BOOT_ALLOCATOR.lock().stats()
492}
493
494pub fn alloc_bytes(size: usize, align: usize) -> Option<PhysAddr> {
495    BOOT_ALLOCATOR.lock().try_alloc(size, align)
496}
497
498pub fn alloc_bytes_accessible(size: usize, align: usize) -> Option<PhysAddr> {
499    BOOT_ALLOCATOR.lock().try_alloc_accessible(size, align)
500}
501
502pub fn snapshot_free_regions(out: &mut [MemoryRegion]) -> usize {
503    BOOT_ALLOCATOR.lock().snapshot_free_regions(out)
504}
505
506/// Seal the boot allocator so no further allocations can be made from it.
507///
508/// Called immediately after the buddy allocator consumes the remaining free
509/// regions via `snapshot_free_regions`. Any subsequent `alloc_stack` call
510/// would otherwise double-allocate pages that are already tracked in the
511/// buddy allocator's free lists.
512pub fn seal() {
513    BOOT_ALLOCATOR.lock().reset();
514}
515
516pub fn alloc_stack(size: usize) -> Option<u64> {
517    let phys = alloc_bytes(size, PAGE_SIZE as usize)?;
518    let span = align_up(size as u64, PAGE_SIZE);
519    Some(phys_to_virt(phys.as_u64()).saturating_add(span))
520}
521
522pub fn set_protected_ranges(ranges: &[Option<(u64, u64)>]) {
523    let mut protected = PROTECTED_RANGES.lock();
524    *protected = [None; MAX_PROTECTED_RANGES];
525    for (dst, src) in protected.iter_mut().zip(ranges.iter().copied()) {
526        *dst = src;
527    }
528}
529
530pub fn reset_protected_ranges() {
531    *PROTECTED_RANGES.lock() = [None; MAX_PROTECTED_RANGES];
532}
533
534pub(crate) fn protected_ranges_snapshot() -> [Option<(u64, u64)>; MAX_PROTECTED_RANGES] {
535    crate::e9_mark!(b'p');
536    let guard = PROTECTED_RANGES.lock();
537    crate::e9_mark!(b'q');
538    // Avoid large struct copy (512 bytes) which generates a memcpy call
539    // that resolves to an identity-mapped address → #UD.
540    let mut result = [None; MAX_PROTECTED_RANGES];
541    for (dst, src) in result.iter_mut().zip(guard.iter()) {
542        *dst = *src;
543    }
544    crate::e9_mark!(b'r');
545    result
546}
547
548#[inline]
549const fn normalize_align(align: usize) -> usize {
550    let align = if align == 0 { 1 } else { align };
551    let align = if align < PAGE_SIZE as usize {
552        PAGE_SIZE as usize
553    } else {
554        align
555    };
556    if align.is_power_of_two() {
557        align
558    } else {
559        align.next_power_of_two()
560    }
561}
562
563#[inline]
564const fn align_up(value: u64, align: u64) -> u64 {
565    (value + align - 1) & !(align - 1)
566}
567
568#[inline]
569const fn align_down(value: u64, align: u64) -> u64 {
570    value & !(align - 1)
571}
strat9_kernel/memory/boot_alloc.rs

strat9_kernel/memory/
boot_alloc.rs
