buddy_slab_allocator/buddy/
mod.rs

1//! Buddy page allocator — page-metadata-based with intrusive free lists.
2//!
3//! The allocator manages one or more contiguous virtual address ranges ("sections").
4//! Each section stores its own [`BuddySection`] descriptor and [`PageMeta`] array
5//! in the caller-provided region prefix, enabling O(1) free-list operations
6//! without any dynamic allocation.
7
8pub mod page_meta;
9
10use core::ptr;
11
12pub use page_meta::{PFN_NONE, PageFlags, PageMeta};
13use page_meta::{free_list_push, free_list_remove};
14
15use crate::{
16    align_up, eii,
17    error::{AllocError, AllocResult},
18    is_aligned,
19};
20
21/// Maximum buddy order. With 4 KiB pages this gives 2^20 × 4 KiB = 4 GiB blocks.
22pub const MAX_ORDER: usize = 20;
23
24/// DMA32 zone upper bound (4 GiB physical).
25const DMA32_LIMIT: usize = 0x1_0000_0000;
26
27fn normalize_region(
28    region_start: usize,
29    region_size: usize,
30    granule: usize,
31) -> Option<(usize, usize)> {
32    if region_size == 0 || !granule.is_power_of_two() {
33        return None;
34    }
35    let region_end = region_start.checked_add(region_size)?;
36    let usable_start = align_up(region_start, granule);
37    let usable_end = region_end & !(granule - 1);
38    if usable_end <= usable_start {
39        return None;
40    }
41    Some((usable_start, usable_end - usable_start))
42}
43
44pub(crate) struct RegionLayout {
45    pub(crate) section_start: usize,
46    pub(crate) meta_start: usize,
47    pub(crate) managed_heap_start: usize,
48    pub(crate) managed_heap_size: usize,
49}
50
51pub(crate) struct SectionInitSpec {
52    pub(crate) region_start: usize,
53    pub(crate) region_size: usize,
54    pub(crate) section_ptr: *mut BuddySection,
55    pub(crate) meta_ptr: *mut u8,
56    pub(crate) meta_size: usize,
57    pub(crate) heap_start: usize,
58    pub(crate) heap_size: usize,
59}
60
61/// Public read-only summary of a managed section.
62#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63pub struct ManagedSection {
64    pub start: usize,
65    pub size: usize,
66    pub free_pages: usize,
67    pub total_pages: usize,
68}
69
70/// Per-region buddy state stored in the region prefix.
71#[repr(C)]
72pub(crate) struct BuddySection {
73    pub(crate) next: *mut BuddySection,
74    pub(crate) region_start: usize,
75    pub(crate) region_size: usize,
76    pub(crate) meta: *mut PageMeta,
77    pub(crate) max_pages: usize,
78    pub(crate) heap_start: usize,
79    pub(crate) heap_size: usize,
80    pub(crate) free_lists: [u32; MAX_ORDER + 1],
81    pub(crate) free_pages: usize,
82    pub(crate) total_pages: usize,
83}
84
85impl BuddySection {
86    const fn metadata_align() -> usize {
87        let section_align = core::mem::align_of::<BuddySection>();
88        let meta_align = core::mem::align_of::<PageMeta>();
89        if section_align > meta_align {
90            section_align
91        } else {
92            meta_align
93        }
94    }
95
96    fn metadata_layout_for_pages(pages: usize) -> Option<(usize, usize)> {
97        let meta_offset = align_up(
98            core::mem::size_of::<BuddySection>(),
99            core::mem::align_of::<PageMeta>(),
100        );
101        let page_meta_size = pages.checked_mul(core::mem::size_of::<PageMeta>())?;
102        let meta_size = meta_offset.checked_add(page_meta_size)?;
103        Some((meta_offset, meta_size))
104    }
105
106    fn available_heap_pages<const PAGE_SIZE: usize>(
107        region_end: usize,
108        section_start: usize,
109        meta_size: usize,
110        heap_align: usize,
111    ) -> Option<usize> {
112        let managed_heap_start = align_up(section_start.checked_add(meta_size)?, heap_align);
113        if managed_heap_start > region_end {
114            return Some(0);
115        }
116        Some((region_end - managed_heap_start) / PAGE_SIZE)
117    }
118
119    fn can_manage_pages<const PAGE_SIZE: usize>(
120        region_end: usize,
121        section_start: usize,
122        pages: usize,
123        heap_align: usize,
124    ) -> bool {
125        let Some((_, meta_size)) = Self::metadata_layout_for_pages(pages) else {
126            return false;
127        };
128        let Some(available_pages) = Self::available_heap_pages::<PAGE_SIZE>(
129            region_end,
130            section_start,
131            meta_size,
132            heap_align,
133        ) else {
134            return false;
135        };
136        available_pages >= pages
137    }
138
139    pub(crate) fn compute_region_layout_with_heap_align<const PAGE_SIZE: usize>(
140        region_start: usize,
141        region_size: usize,
142        heap_align: usize,
143    ) -> Option<RegionLayout> {
144        if region_size == 0 || !PAGE_SIZE.is_power_of_two() || !heap_align.is_power_of_two() {
145            return None;
146        }
147
148        let region_end = region_start.checked_add(region_size)?;
149        let section_start = align_up(region_start, Self::metadata_align());
150        if section_start >= region_end {
151            return None;
152        }
153
154        let heap_search_start = align_up(
155            section_start.checked_add(core::mem::size_of::<BuddySection>())?,
156            PAGE_SIZE,
157        );
158        let max_pages = if heap_search_start >= region_end {
159            0
160        } else {
161            (region_end - heap_search_start) / PAGE_SIZE
162        };
163
164        let mut low = 0usize;
165        let mut high = max_pages;
166        while low < high {
167            let mid = low + (high - low).div_ceil(2);
168            if Self::can_manage_pages::<PAGE_SIZE>(region_end, section_start, mid, heap_align) {
169                low = mid;
170            } else {
171                high = mid - 1;
172            }
173        }
174
175        if low == 0 {
176            return None;
177        }
178
179        let (meta_offset, meta_size) = Self::metadata_layout_for_pages(low)?;
180        let meta_start = section_start.checked_add(meta_offset)?;
181        let managed_heap_start = align_up(section_start.checked_add(meta_size)?, heap_align);
182        let managed_heap_size = low.checked_mul(PAGE_SIZE)?;
183
184        Some(RegionLayout {
185            section_start,
186            meta_start,
187            managed_heap_start,
188            managed_heap_size,
189        })
190    }
191
192    fn compute_region_layout<const PAGE_SIZE: usize>(
193        region_start: usize,
194        region_size: usize,
195    ) -> Option<RegionLayout> {
196        Self::compute_region_layout_with_heap_align::<PAGE_SIZE>(
197            region_start,
198            region_size,
199            PAGE_SIZE,
200        )
201    }
202
203    unsafe fn init_at<const PAGE_SIZE: usize>(
204        section_ptr: *mut BuddySection,
205        region_start: usize,
206        region_size: usize,
207        meta_ptr: *mut u8,
208        meta_size: usize,
209        heap_start: usize,
210        heap_size: usize,
211    ) -> AllocResult {
212        unsafe {
213            if !PAGE_SIZE.is_power_of_two() {
214                return Err(AllocError::InvalidParam);
215            }
216            if !is_aligned(heap_start, PAGE_SIZE) || heap_size == 0 {
217                return Err(AllocError::InvalidParam);
218            }
219
220            let total_pages = heap_size / PAGE_SIZE;
221            let required = BuddyAllocator::<PAGE_SIZE>::required_meta_size(heap_size);
222            if meta_size < required {
223                return Err(AllocError::InvalidParam);
224            }
225
226            let meta = meta_ptr as *mut PageMeta;
227            for i in 0..total_pages {
228                meta.add(i).write(PageMeta::new());
229            }
230
231            section_ptr.write(BuddySection {
232                next: ptr::null_mut(),
233                region_start,
234                region_size,
235                meta,
236                max_pages: total_pages,
237                heap_start,
238                heap_size,
239                free_lists: [PFN_NONE; MAX_ORDER + 1],
240                free_pages: 0,
241                total_pages,
242            });
243
244            let section = &mut *section_ptr;
245            let mut pfn: usize = 0;
246            while pfn < total_pages {
247                let mut order = MAX_ORDER;
248                loop {
249                    let block_pages = 1usize << order;
250                    if block_pages <= total_pages - pfn && (pfn & (block_pages - 1)) == 0 {
251                        break;
252                    }
253                    if order == 0 {
254                        break;
255                    }
256                    order -= 1;
257                }
258                let block_pages = 1usize << order;
259                let m = &mut *section.meta.add(pfn);
260                m.flags = PageFlags::Free;
261                m.order = order as u8;
262                free_list_push(section.meta, &mut section.free_lists, pfn as u32, order);
263                section.free_pages += block_pages;
264                pfn += block_pages;
265            }
266
267            Ok(())
268        }
269    }
270
271    #[inline]
272    fn contains_heap_addr(&self, addr: usize) -> bool {
273        addr >= self.heap_start && addr < self.heap_start + self.heap_size
274    }
275
276    #[inline]
277    fn summary(&self) -> ManagedSection {
278        ManagedSection {
279            start: self.heap_start,
280            size: self.heap_size,
281            free_pages: self.free_pages,
282            total_pages: self.total_pages,
283        }
284    }
285}
286
287/// Page-metadata-based buddy allocator.
288///
289/// `PAGE_SIZE` must be a power of two (commonly 0x1000 = 4 KiB).
290pub struct BuddyAllocator<const PAGE_SIZE: usize = 0x1000> {
291    sections_head: *mut BuddySection,
292    sections_tail: *mut BuddySection,
293    section_count: usize,
294}
295
296// SAFETY: The allocator is designed to be wrapped in a SpinMutex.
297// All section pointers point into caller-provided regions whose lifetime is managed externally.
298unsafe impl<const PAGE_SIZE: usize> Send for BuddyAllocator<PAGE_SIZE> {}
299
300impl<const PAGE_SIZE: usize> BuddyAllocator<PAGE_SIZE> {
301    /// Calculate the metadata-region size (in bytes) required for `heap_size` bytes.
302    pub const fn required_meta_size(heap_size: usize) -> usize {
303        let pages = heap_size / PAGE_SIZE;
304        pages * core::mem::size_of::<PageMeta>()
305    }
306
307    /// Create an uninitialised allocator. Call [`init`](Self::init) before use.
308    pub const fn new() -> Self {
309        Self {
310            sections_head: ptr::null_mut(),
311            sections_tail: ptr::null_mut(),
312            section_count: 0,
313        }
314    }
315}
316
317impl<const PAGE_SIZE: usize> Default for BuddyAllocator<PAGE_SIZE> {
318    fn default() -> Self {
319        Self::new()
320    }
321}
322
323impl<const PAGE_SIZE: usize> BuddyAllocator<PAGE_SIZE> {
324    pub(crate) fn reset(&mut self) {
325        self.sections_head = ptr::null_mut();
326        self.sections_tail = ptr::null_mut();
327        self.section_count = 0;
328    }
329
330    /// Initialise the allocator over the first section.
331    ///
332    /// # Safety
333    /// - `region` must be writable and remain valid for the lifetime of this allocator.
334    /// - Bytes consumed by metadata become unavailable for allocation.
335    pub unsafe fn init(&mut self, region: &mut [u8]) -> AllocResult {
336        unsafe {
337            self.reset();
338            self.add_region(region)
339        }
340    }
341
342    /// Add a new managed region after initialisation.
343    ///
344    /// # Safety
345    /// - `region` must be writable and remain valid for the lifetime of this allocator.
346    /// - The region must not overlap any existing managed region.
347    pub unsafe fn add_region(&mut self, region: &mut [u8]) -> AllocResult {
348        unsafe {
349            let region_start = region.as_mut_ptr() as usize;
350            let region_size = region.len();
351            let (region_start, region_size) =
352                normalize_region(region_start, region_size, PAGE_SIZE)
353                    .ok_or(AllocError::InvalidParam)?;
354            let layout =
355                BuddySection::compute_region_layout::<PAGE_SIZE>(region_start, region_size)
356                    .ok_or(AllocError::InvalidParam)?;
357            self.add_region_raw(SectionInitSpec {
358                region_start,
359                region_size,
360                section_ptr: layout.section_start as *mut BuddySection,
361                meta_ptr: layout.meta_start as *mut u8,
362                meta_size: Self::required_meta_size(layout.managed_heap_size),
363                heap_start: layout.managed_heap_start,
364                heap_size: layout.managed_heap_size,
365            })
366        }
367    }
368
369    pub(crate) unsafe fn add_region_raw(&mut self, spec: SectionInitSpec) -> AllocResult {
370        unsafe {
371            let region_size = spec.region_size;
372            let region_end = spec
373                .region_start
374                .checked_add(region_size)
375                .ok_or(AllocError::InvalidParam)?;
376            let heap_end = spec
377                .heap_start
378                .checked_add(spec.heap_size)
379                .ok_or(AllocError::InvalidParam)?;
380            if heap_end > region_end {
381                return Err(AllocError::InvalidParam);
382            }
383
384            let mut section = self.sections_head;
385            while !section.is_null() {
386                let existing = &*section;
387                let existing_end = existing
388                    .region_start
389                    .checked_add(existing.region_size)
390                    .ok_or(AllocError::InvalidParam)?;
391                if spec.region_start < existing_end && existing.region_start < region_end {
392                    return Err(AllocError::MemoryOverlap);
393                }
394                section = existing.next;
395            }
396
397            BuddySection::init_at::<PAGE_SIZE>(
398                spec.section_ptr,
399                spec.region_start,
400                spec.region_size,
401                spec.meta_ptr,
402                spec.meta_size,
403                spec.heap_start,
404                spec.heap_size,
405            )?;
406
407            if self.sections_head.is_null() {
408                self.sections_head = spec.section_ptr;
409            } else {
410                (*self.sections_tail).next = spec.section_ptr;
411            }
412            self.sections_tail = spec.section_ptr;
413            self.section_count += 1;
414
415            log::debug!(
416                "BuddyAllocator: add section region {:#x}+{:#x}, heap {:#x}..{:#x}, {} pages",
417                spec.region_start,
418                spec.region_size,
419                spec.heap_start,
420                heap_end,
421                spec.heap_size / PAGE_SIZE,
422            );
423
424            Ok(())
425        }
426    }
427
428    /// Number of managed sections.
429    pub fn section_count(&self) -> usize {
430        self.section_count
431    }
432
433    /// Read-only summary for a managed section by registration order.
434    pub fn section(&self, index: usize) -> Option<ManagedSection> {
435        let mut current = self.sections_head;
436        let mut i = 0usize;
437        while !current.is_null() {
438            if i == index {
439                return Some(unsafe { (&*current).summary() });
440            }
441            current = unsafe { (*current).next };
442            i += 1;
443        }
444        None
445    }
446
447    /// Total number of pages managed across all sections.
448    pub fn total_pages(&self) -> usize {
449        let mut total = 0usize;
450        let mut current = self.sections_head;
451        while !current.is_null() {
452            total += unsafe { (*current).total_pages };
453            current = unsafe { (*current).next };
454        }
455        total
456    }
457
458    /// Total managed heap bytes across all sections.
459    ///
460    /// This counts only bytes in allocatable heaps, excluding region-prefix metadata.
461    pub fn managed_bytes(&self) -> usize {
462        let mut total = 0usize;
463        let mut current = self.sections_head;
464        while !current.is_null() {
465            total += unsafe { (*current).heap_size };
466            current = unsafe { (*current).next };
467        }
468        total
469    }
470
471    /// Number of currently free pages across all sections.
472    pub fn free_pages(&self) -> usize {
473        let mut total = 0usize;
474        let mut current = self.sections_head;
475        while !current.is_null() {
476            total += unsafe { (*current).free_pages };
477            current = unsafe { (*current).next };
478        }
479        total
480    }
481
482    /// Allocated backend bytes across all sections.
483    ///
484    /// This is computed as managed heap bytes minus currently free page bytes.
485    /// It reflects page-level occupancy, so it includes slab pages, alignment
486    /// amplification, and internal fragmentation.
487    pub fn allocated_bytes(&self) -> usize {
488        self.managed_bytes()
489            .saturating_sub(self.free_pages().saturating_mul(PAGE_SIZE))
490    }
491
492    /// Allocate `count` contiguous pages, returning the virtual address.
493    pub fn alloc_pages(&mut self, count: usize, align: usize) -> AllocResult<usize> {
494        if count == 0 {
495            return Err(AllocError::InvalidParam);
496        }
497        let align = if align == 0 { PAGE_SIZE } else { align };
498        if !align.is_power_of_two() || align < PAGE_SIZE {
499            return Err(AllocError::InvalidParam);
500        }
501
502        let order = count.next_power_of_two().trailing_zeros() as usize;
503        if order > MAX_ORDER {
504            return Err(AllocError::InvalidParam);
505        }
506
507        let mut section = self.sections_head;
508        while !section.is_null() {
509            if let Ok(addr) =
510                unsafe { Self::alloc_from_section_aligned(&mut *section, order, align) }
511            {
512                return Ok(addr);
513            }
514            section = unsafe { (*section).next };
515        }
516
517        Err(AllocError::NoMemory)
518    }
519
520    fn alloc_from_section_aligned(
521        section: &mut BuddySection,
522        order: usize,
523        align: usize,
524    ) -> AllocResult<usize> {
525        for search_order in order..=MAX_ORDER {
526            let mut pfn_u32 = section.free_lists[search_order];
527            while pfn_u32 != PFN_NONE {
528                let block_pfn = pfn_u32 as usize;
529                if let Some(target_pfn) = Self::find_aligned_pfn_in_block(
530                    section.heap_start,
531                    block_pfn,
532                    search_order,
533                    order,
534                    align,
535                ) {
536                    unsafe {
537                        free_list_remove(
538                            section.meta,
539                            &mut section.free_lists,
540                            pfn_u32,
541                            search_order,
542                        );
543                    }
544
545                    let mut current_order = search_order;
546                    let mut current_pfn = block_pfn;
547                    while current_order > order {
548                        current_order -= 1;
549                        let left_pfn = current_pfn;
550                        let right_pfn = current_pfn + (1 << current_order);
551                        let (next_pfn, free_pfn) = if target_pfn >= right_pfn {
552                            (right_pfn, left_pfn)
553                        } else {
554                            (left_pfn, right_pfn)
555                        };
556                        unsafe {
557                            let bm = &mut *section.meta.add(free_pfn);
558                            bm.flags = PageFlags::Free;
559                            bm.order = current_order as u8;
560                            free_list_push(
561                                section.meta,
562                                &mut section.free_lists,
563                                free_pfn as u32,
564                                current_order,
565                            );
566                        }
567                        current_pfn = next_pfn;
568                    }
569
570                    unsafe {
571                        let m = &mut *section.meta.add(current_pfn);
572                        m.flags = PageFlags::Allocated;
573                        m.order = order as u8;
574                    }
575
576                    section.free_pages -= 1 << order;
577                    return Ok(section.heap_start + current_pfn * PAGE_SIZE);
578                }
579                pfn_u32 = unsafe { (*section.meta.add(pfn_u32 as usize)).next };
580            }
581        }
582
583        Err(AllocError::NoMemory)
584    }
585
586    fn find_aligned_pfn_in_block(
587        heap_start: usize,
588        block_pfn: usize,
589        block_order: usize,
590        alloc_order: usize,
591        align: usize,
592    ) -> Option<usize> {
593        let subblock_pages = 1usize << alloc_order;
594        let align_pages = align / PAGE_SIZE;
595        let heap_page_offset = (heap_start / PAGE_SIZE) & (align_pages - 1);
596        let offset = (align_pages - heap_page_offset) & (align_pages - 1);
597
598        let candidate = if align_pages <= subblock_pages {
599            if !heap_start.is_multiple_of(align) {
600                return None;
601            }
602            block_pfn
603        } else {
604            if !offset.is_multiple_of(subblock_pages) {
605                return None;
606            }
607            let rem = block_pfn & (align_pages - 1);
608            let delta = (offset + align_pages - rem) & (align_pages - 1);
609            block_pfn + delta
610        };
611
612        let block_pages = 1usize << block_order;
613        let last_start = block_pfn + block_pages - subblock_pages;
614        (candidate <= last_start).then_some(candidate)
615    }
616
617    /// Allocate pages whose *physical* address is below 4 GiB (DMA32 zone).
618    pub fn alloc_pages_lowmem(&mut self, count: usize, align: usize) -> AllocResult<usize> {
619        if count == 0 {
620            return Err(AllocError::InvalidParam);
621        }
622        let align = if align == 0 { PAGE_SIZE } else { align };
623        if !align.is_power_of_two() || align < PAGE_SIZE {
624            return Err(AllocError::InvalidParam);
625        }
626
627        let order = count.next_power_of_two().trailing_zeros() as usize;
628        if order > MAX_ORDER {
629            return Err(AllocError::InvalidParam);
630        }
631
632        let mut section = self.sections_head;
633        while !section.is_null() {
634            if let Ok(addr) =
635                unsafe { Self::alloc_lowmem_from_section(&mut *section, order, align) }
636            {
637                return Ok(addr);
638            }
639            section = unsafe { (*section).next };
640        }
641
642        Err(AllocError::NoMemory)
643    }
644
645    fn alloc_lowmem_from_section(
646        section: &mut BuddySection,
647        alloc_order: usize,
648        align: usize,
649    ) -> AllocResult<usize> {
650        for search_order in alloc_order..=MAX_ORDER {
651            let mut pfn_u32 = section.free_lists[search_order];
652            while pfn_u32 != PFN_NONE {
653                let block_pfn = pfn_u32 as usize;
654                let Some(target_pfn) = Self::find_aligned_pfn_in_block(
655                    section.heap_start,
656                    block_pfn,
657                    search_order,
658                    alloc_order,
659                    align,
660                ) else {
661                    pfn_u32 = unsafe { (*section.meta.add(pfn_u32 as usize)).next };
662                    continue;
663                };
664                let addr = section.heap_start + target_pfn * PAGE_SIZE;
665                let phys = eii::virt_to_phys(addr);
666                let block_bytes = (1usize << alloc_order) * PAGE_SIZE;
667                if phys + block_bytes <= DMA32_LIMIT && addr.is_multiple_of(align) {
668                    unsafe {
669                        free_list_remove(
670                            section.meta,
671                            &mut section.free_lists,
672                            pfn_u32,
673                            search_order,
674                        );
675                    }
676
677                    let mut current_order = search_order;
678                    let mut current_pfn = block_pfn;
679                    while current_order > alloc_order {
680                        current_order -= 1;
681                        let left_pfn = current_pfn;
682                        let right_pfn = current_pfn + (1 << current_order);
683                        let (next_pfn, free_pfn) = if target_pfn >= right_pfn {
684                            (right_pfn, left_pfn)
685                        } else {
686                            (left_pfn, right_pfn)
687                        };
688                        unsafe {
689                            let bm = &mut *section.meta.add(free_pfn);
690                            bm.flags = PageFlags::Free;
691                            bm.order = current_order as u8;
692                            free_list_push(
693                                section.meta,
694                                &mut section.free_lists,
695                                free_pfn as u32,
696                                current_order,
697                            );
698                        }
699                        current_pfn = next_pfn;
700                    }
701
702                    unsafe {
703                        let m = &mut *section.meta.add(current_pfn);
704                        m.flags = PageFlags::Allocated;
705                        m.order = alloc_order as u8;
706                    }
707                    section.free_pages -= 1 << alloc_order;
708                    return Ok(addr);
709                }
710                pfn_u32 = unsafe { (*section.meta.add(pfn_u32 as usize)).next };
711            }
712        }
713
714        Err(AllocError::NoMemory)
715    }
716
717    /// Free pages previously obtained via [`alloc_pages`](Self::alloc_pages).
718    ///
719    /// `addr` must be the exact address returned by alloc. The allocator frees
720    /// the full block size recorded in page metadata, which may be larger than
721    /// `count` if the original allocation was rounded up for buddy order or alignment.
722    pub fn dealloc_pages(&mut self, addr: usize, count: usize) {
723        let Some(section) = self.find_section_by_addr_mut(addr) else {
724            debug_assert!(
725                false,
726                "dealloc_pages called with address outside all sections"
727            );
728            return;
729        };
730
731        debug_assert!(is_aligned(addr, PAGE_SIZE));
732        debug_assert!(count > 0);
733
734        let pfn = (addr - section.heap_start) / PAGE_SIZE;
735        debug_assert!(pfn < section.max_pages);
736        let stored = unsafe { &*section.meta.add(pfn) };
737        debug_assert!(
738            stored.flags == PageFlags::Allocated || stored.flags == PageFlags::Slab,
739            "dealloc_pages called on non-allocated block"
740        );
741
742        let expected_order = count.next_power_of_two().trailing_zeros() as usize;
743        let order = stored.order as usize;
744        debug_assert!(
745            expected_order <= order,
746            "dealloc_pages count implies larger order than the allocated block"
747        );
748        Self::dealloc_in_section(section, pfn, order);
749    }
750
751    /// Mark the page at `addr` with the given flags (used by slab to tag pages).
752    ///
753    /// # Safety
754    /// The caller must ensure `addr` is valid and properly allocated.
755    pub unsafe fn set_page_flags(&mut self, addr: usize, flags: PageFlags) -> AllocResult {
756        unsafe {
757            let section = self
758                .find_section_by_addr_mut(addr)
759                .ok_or(AllocError::NotFound)?;
760            let pfn = (addr - section.heap_start) / PAGE_SIZE;
761            (*section.meta.add(pfn)).flags = flags;
762            Ok(())
763        }
764    }
765
766    /// Read the flags of the page containing `addr`.
767    pub fn page_flags(&self, addr: usize) -> AllocResult<PageFlags> {
768        let section = self
769            .find_section_by_addr(addr)
770            .ok_or(AllocError::NotFound)?;
771        let pfn = (addr - section.heap_start) / PAGE_SIZE;
772        Ok(unsafe { (*section.meta.add(pfn)).flags })
773    }
774
775    fn dealloc_in_section(section: &mut BuddySection, mut pfn: usize, mut order: usize) {
776        let freed_pages = 1usize << order;
777
778        while order < MAX_ORDER {
779            let buddy_pfn = pfn ^ (1 << order);
780            if buddy_pfn >= section.max_pages {
781                break;
782            }
783            let buddy = unsafe { &*section.meta.add(buddy_pfn) };
784            if buddy.flags != PageFlags::Free || buddy.order as usize != order {
785                break;
786            }
787            unsafe {
788                free_list_remove(
789                    section.meta,
790                    &mut section.free_lists,
791                    buddy_pfn as u32,
792                    order,
793                );
794            }
795            pfn = pfn.min(buddy_pfn);
796            order += 1;
797        }
798
799        unsafe {
800            let m = &mut *section.meta.add(pfn);
801            m.flags = PageFlags::Free;
802            m.order = order as u8;
803            free_list_push(section.meta, &mut section.free_lists, pfn as u32, order);
804        }
805        section.free_pages += freed_pages;
806    }
807
808    fn find_section_by_addr(&self, addr: usize) -> Option<&BuddySection> {
809        let mut section = self.sections_head;
810        while !section.is_null() {
811            let current = unsafe { &*section };
812            if current.contains_heap_addr(addr) {
813                return Some(current);
814            }
815            section = current.next;
816        }
817        None
818    }
819
820    fn find_section_by_addr_mut(&mut self, addr: usize) -> Option<&mut BuddySection> {
821        let mut section = self.sections_head;
822        while !section.is_null() {
823            let current = unsafe { &mut *section };
824            if current.contains_heap_addr(addr) {
825                return Some(current);
826            }
827            section = current.next;
828        }
829        None
830    }
831}
buddy_slab_allocator/buddy/mod.rs

buddy_slab_allocator/buddy/
mod.rs
