ostd/mm/heap/
slot_list.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! Implementation of the free heap slot list.
4
5use core::ptr::NonNull;
6
7use super::HeapSlot;
8
9/// A singly-linked list of [`HeapSlot`]s from [`super::Slab`]s.
10///
11/// The slots inside this list will have a size of `SLOT_SIZE`. They can come
12/// from different slabs.
13#[derive(Debug)]
14pub struct SlabSlotList<const SLOT_SIZE: usize> {
15    /// The head of the list.
16    head: Option<NonNull<u8>>,
17}
18
19// SAFETY: Any access or modification (i.e., push and pop operations) to the
20// data pointed to by `head` requires a `&mut SlabSlotList`. Therefore, at any
21// given time, only one task can access the inner `head`. Additionally, a
22// `HeapSlot` will not be allocated again as long as it remains in the list.
23unsafe impl<const SLOT_SIZE: usize> Sync for SlabSlotList<SLOT_SIZE> {}
24unsafe impl<const SLOT_SIZE: usize> Send for SlabSlotList<SLOT_SIZE> {}
25
26impl<const SLOT_SIZE: usize> Default for SlabSlotList<SLOT_SIZE> {
27    fn default() -> Self {
28        Self::new()
29    }
30}
31
32impl<const SLOT_SIZE: usize> SlabSlotList<SLOT_SIZE> {
33    /// Creates a new empty list.
34    pub const fn new() -> Self {
35        Self { head: None }
36    }
37
38    /// Pushes a slot to the front of the list.
39    ///
40    /// # Panics
41    ///
42    /// Panics if
43    ///  - the slot does not come from a slab
44    ///    (i.e., `!matches(slot.info(), SlotInfo::SlabSlot(_))`);
45    ///  - the size of the slot does not match `SLOT_SIZE`.
46    pub fn push(&mut self, slot: HeapSlot) {
47        let slot_ptr = slot.as_ptr();
48        let super::SlotInfo::SlabSlot(slot_size) = slot.info() else {
49            panic!("The slot does not come from a slab");
50        };
51
52        assert_eq!(slot_size, SLOT_SIZE);
53        const { assert!(SLOT_SIZE >= size_of::<usize>()) };
54
55        let original_head = self.head;
56
57        debug_assert!(!slot_ptr.is_null());
58        // SAFETY: A pointer to a slot must not be NULL;
59        self.head = Some(unsafe { NonNull::new_unchecked(slot_ptr) });
60        // Write the original head to the slot.
61        // SAFETY: A heap slot must be free so the pointer to the slot can be
62        // written to. The slot size is at least the size of a pointer.
63        unsafe {
64            slot_ptr
65                .cast::<usize>()
66                .write(original_head.map_or(0, |h| h.as_ptr() as usize));
67        }
68    }
69
70    /// Pops a slot from the front of the list.
71    ///
72    /// It returns `None` if the list is empty.
73    pub fn pop(&mut self) -> Option<HeapSlot> {
74        let original_head = self.head?;
75
76        // SAFETY: The head is a valid pointer to a free slot.
77        // The slot contains a pointer to the next slot.
78        let next = unsafe { original_head.as_ptr().cast::<usize>().read() } as *mut u8;
79
80        self.head = if next.is_null() {
81            None
82        } else {
83            // SAFETY: We already verified that the next slot is not NULL.
84            Some(unsafe { NonNull::new_unchecked(next) })
85        };
86
87        Some(unsafe { HeapSlot::new(original_head, super::SlotInfo::SlabSlot(SLOT_SIZE)) })
88    }
89}
ostd/mm/heap/slot_list.rs

ostd/mm/heap/
slot_list.rs
