Skip to main content

os/allocator/
linked_list.rs

1//! Interrupt-safe wrapper around `linked_list_allocator::Heap`.
2//!
3//! The allocator is used after timer interrupts and preemptive scheduling are
4//! enabled. Holding the heap lock across a timer interrupt can deadlock when the
5//! scheduler resumes another task that also allocates, so global alloc/dealloc
6//! run with interrupts disabled.
7
8use super::Locked;
9use alloc::alloc::{GlobalAlloc, Layout};
10use core::{ptr, ptr::NonNull};
11use linked_list_allocator::Heap;
12
13pub struct LinkedListAllocator {
14    heap: Heap,
15    heap_start: usize,
16    heap_end: usize,
17}
18
19impl LinkedListAllocator {
20    pub const fn new() -> Self {
21        Self {
22            heap: Heap::empty(),
23            heap_start: 0,
24            heap_end: 0,
25        }
26    }
27
28    /// # Safety
29    ///
30    /// The caller must provide an unused, valid heap region for the lifetime of
31    /// the kernel.
32    pub unsafe fn init(&mut self, heap_start: usize, heap_size: usize) {
33        self.heap_start = heap_start;
34        self.heap_end = heap_start + heap_size;
35        unsafe {
36            self.heap.init(heap_start as *mut u8, heap_size);
37        }
38    }
39
40    fn contains_allocation(&self, ptr: *mut u8, layout: Layout) -> bool {
41        if ptr.is_null() || layout.size() == 0 {
42            return false;
43        }
44
45        let addr = ptr as usize;
46        let Some(end) = addr.checked_add(layout.size()) else {
47            return false;
48        };
49
50        addr >= self.heap_start && end <= self.heap_end
51    }
52}
53
54impl Default for LinkedListAllocator {
55    fn default() -> Self {
56        Self::new()
57    }
58}
59
60unsafe impl GlobalAlloc for Locked<LinkedListAllocator> {
61    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
62        crate::interrupts::without_interrupts(|| {
63            let mut allocator = self.lock();
64            match allocator.heap.allocate_first_fit(layout) {
65                Ok(ptr) => ptr.as_ptr(),
66                Err(_) => ptr::null_mut(),
67            }
68        })
69    }
70
71    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
72        crate::interrupts::without_interrupts(|| {
73            let mut allocator = self.lock();
74            if !allocator.contains_allocation(ptr, layout) {
75                return;
76            }
77
78            let Some(ptr) = NonNull::new(ptr) else {
79                return;
80            };
81            unsafe {
82                allocator.heap.deallocate(ptr, layout);
83            }
84        });
85    }
86}