free_list/
lib.rs

1//! A free-list-based page/frame allocator.
2//!
3//! The main type of this crate is [`FreeList`], which allocates [`PageRange`]s.
4//!
5//! # Examples
6//!
7//! ```
8//! use free_list::{FreeList, PageLayout};
9//!
10//! let mut free_list = FreeList::<16>::new();
11//!
12//! unsafe {
13//!     free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
14//! }
15//! assert_eq!(free_list.free_space(), 0x4000);
16//!
17//! let layout = PageLayout::from_size(0x4000).unwrap();
18//! assert_eq!(free_list.allocate(layout).unwrap(), (0x1000..0x5000).try_into().unwrap());
19//! ```
20
21#![cfg_attr(not(test), no_std)]
22#![cfg_attr(docsrs, feature(doc_auto_cfg))]
23#![warn(missing_docs)]
24#![doc(test(attr(deny(warnings))))]
25
26#[doc = include_str!("../README.md")]
27#[cfg(doctest)]
28pub struct ReadmeDoctests;
29
30mod page_layout;
31mod page_list;
32mod page_range;
33
34use core::fmt;
35use core::num::NonZeroUsize;
36
37pub use self::page_layout::{PageLayout, PageLayoutError};
38use self::page_list::PageList;
39pub use self::page_range::{PageRange, PageRangeError, PageRangeSub};
40
41/// The base page size.
42///
43/// [`PageRange`] and [`PageLayout`] may only refer to whole pages of this size.
44pub const PAGE_SIZE: usize = 4096;
45
46/// A free-list-based page/frame allocator.
47///
48/// This type can be used for managing (allocating and deallocating) physical and virtual memory at [`PAGE_SIZE`] granularity.
49/// This is useful for ensuring pages and frames being currently unused before mapping them.
50///
51/// The `const N: usize` generic specifies how many internal [`PageRange`]s the free list can hold before needing to allocate more memory from the global allocator.
52///
53/// Before allocating, the free list has to be provided a page range to allocate from via [`FreeList::deallocate`].
54///
55/// # Examples
56///
57/// ```
58/// use free_list::{FreeList, PageLayout};
59///
60/// let mut free_list = FreeList::<16>::new();
61///
62/// unsafe {
63///     free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
64/// }
65/// assert_eq!(free_list.free_space(), 0x4000);
66///
67/// let layout = PageLayout::from_size(0x4000).unwrap();
68/// assert_eq!(free_list.allocate(layout).unwrap(), (0x1000..0x5000).try_into().unwrap());
69/// ```
70#[derive(Debug)]
71pub struct FreeList<const N: usize> {
72    list: PageList<N>,
73}
74
75/// Allocation failure.
76#[derive(Clone, PartialEq, Eq, Debug)]
77#[non_exhaustive]
78pub struct AllocError;
79
80impl fmt::Display for AllocError {
81    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
82        f.write_str("memory allocation failed")
83    }
84}
85
86impl<const N: usize> FreeList<N> {
87    /// Creates a new free list without any free space.
88    ///
89    /// # Examples
90    ///
91    /// ```
92    /// # #![allow(unused_variables)]
93    /// use free_list::FreeList;
94    ///
95    /// let free_list = FreeList::<16>::new();
96    /// ```
97    pub const fn new() -> Self {
98        Self {
99            list: PageList::new(),
100        }
101    }
102
103    /// Attempts to deallocates a page range.
104    ///
105    /// This should also be used to add more free pages to the allocator, such as after initialization.
106    /// This returns an error, if `range` overlaps with any pages that are already deallocated.
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// use free_list::FreeList;
112    ///
113    /// let mut free_list = FreeList::<16>::new();
114    ///
115    /// unsafe {
116    ///     free_list.deallocate((0x1000..0x2000).try_into().unwrap()).unwrap();
117    /// }
118    /// ```
119    ///
120    /// # Safety
121    ///
122    /// `range` must be valid to be allocated and used (again).
123    pub unsafe fn deallocate(&mut self, range: PageRange) -> Result<(), AllocError> {
124        self.list.add(range).map_err(|_| AllocError)
125    }
126
127    /// Attempts to allocate a page range.
128    ///
129    /// On success, returns a [`PageRange`] meeting the size and alignment guarantees of `layout`.
130    ///
131    /// This call can only succeed if the free list has previously been provided a free page range to allocate from via [`FreeList::deallocate`].
132    ///
133    /// # Examples
134    ///
135    /// ```
136    /// use free_list::{FreeList, PageLayout};
137    ///
138    /// let mut free_list = FreeList::<16>::new();
139    ///
140    /// unsafe {
141    ///     free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
142    /// }
143    ///
144    /// let layout = PageLayout::from_size(0x4000).unwrap();
145    /// assert_eq!(free_list.allocate(layout).unwrap(), (0x1000..0x5000).try_into().unwrap());
146    /// ```
147    pub fn allocate(&mut self, layout: PageLayout) -> Result<PageRange, AllocError> {
148        self.allocate_with(|range| range.fit(layout))
149    }
150
151    /// Attempts to allocate a specific page range.
152    ///
153    /// # Examples
154    ///
155    /// ```
156    /// use free_list::FreeList;
157    ///
158    /// let mut free_list = FreeList::<16>::new();
159    ///
160    /// unsafe {
161    ///     free_list.deallocate((0x1000..0x2000).try_into().unwrap()).unwrap();
162    ///     free_list.deallocate((0x3000..0x4000).try_into().unwrap()).unwrap();
163    /// }
164    ///
165    /// free_list.allocate_at((0x3000..0x4000).try_into().unwrap()).unwrap();
166    /// ```
167    pub fn allocate_at(&mut self, range: PageRange) -> Result<(), AllocError> {
168        self.list.remove(range).map_err(|_| AllocError)
169    }
170
171    /// Attempts to allocate a page range outside of a given page range.
172    ///
173    /// On success, returns a [`PageRange`] meeting the size and alignment guarantees of `layout` outside of `range`.
174    ///
175    /// # Examples
176    ///
177    /// ```
178    /// use free_list::{FreeList, PageLayout, PageRange};
179    ///
180    /// let mut free_list = FreeList::<16>::new();
181    ///
182    /// unsafe {
183    ///     free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
184    /// }
185    ///
186    /// let layout = PageLayout::from_size(0x1000).unwrap();
187    /// let range = PageRange::new(0x0000, 0x2000).unwrap();
188    /// let allocated = free_list.allocate_outside_of(layout, range);
189    /// assert_eq!(allocated.unwrap(), (0x2000..0x3000).try_into().unwrap());
190    /// ```
191    pub fn allocate_outside_of(
192        &mut self,
193        layout: PageLayout,
194        range: PageRange,
195    ) -> Result<PageRange, AllocError> {
196        self.allocate_with(|entry| match entry - range {
197            PageRangeSub::None => None,
198            PageRangeSub::One(a) => a.fit(layout),
199            PageRangeSub::Two(a, b) => a.fit(layout).or_else(|| b.fit(layout)),
200        })
201    }
202
203    /// Attempts to allocate a page range according to a function.
204    ///
205    /// On success, allocates and returns the first non-none [`PageRange`] returned by `f`.
206    ///
207    /// # Examples
208    ///
209    /// ```
210    /// use free_list::{FreeList, PageLayout};
211    ///
212    /// let mut free_list = FreeList::<16>::new();
213    ///
214    /// unsafe {
215    ///     free_list.deallocate((0x1000..0x2000).try_into().unwrap()).unwrap();
216    ///     free_list.deallocate((0x3000..0x4000).try_into().unwrap()).unwrap();
217    /// }
218    ///
219    /// let layout = PageLayout::from_size(0x1000).unwrap();
220    /// let allocated = free_list.allocate_with(|range| {
221    ///     (range.start() > 0x2000)
222    ///         .then_some(range)
223    ///         .and_then(|range| range.fit(layout))
224    /// });
225    /// assert_eq!(allocated.unwrap(), (0x3000..0x4000).try_into().unwrap());
226    /// ```
227    pub fn allocate_with<F>(&mut self, f: F) -> Result<PageRange, AllocError>
228    where
229        F: FnMut(PageRange) -> Option<PageRange>,
230    {
231        let mut f = f;
232
233        let (index, fit) = self
234            .list
235            .iter()
236            .enumerate()
237            .find_map(|(index, entry)| f(entry).map(|fit| (index, fit)))
238            .ok_or(AllocError)?;
239
240        self.list.remove_at(index, fit).unwrap();
241
242        Ok(fit)
243    }
244
245    /// Returns how much free space this allocator has in bytes.
246    ///
247    /// # Examples
248    ///
249    /// ```
250    /// use free_list::FreeList;
251    ///
252    /// let mut free_list = FreeList::<16>::new();
253    ///
254    /// unsafe {
255    ///     free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
256    /// }
257    /// assert_eq!(free_list.free_space(), 0x4000);
258    /// ```
259    pub fn free_space(&self) -> usize {
260        self.list
261            .iter()
262            .map(PageRange::len)
263            .map(NonZeroUsize::get)
264            .sum()
265    }
266}
267
268impl<const N: usize> Default for FreeList<N> {
269    fn default() -> Self {
270        Self::new()
271    }
272}
273
274impl<const N: usize> fmt::Display for FreeList<N> {
275    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
276        self.list.fmt(f)
277    }
278}
279
280#[cfg(all(target_arch = "x86_64", feature = "x86_64"))]
281mod frame_allocator {
282    use x86_64::structures::paging::{FrameAllocator, FrameDeallocator, PageSize, PhysFrame};
283    use x86_64::PhysAddr;
284
285    use super::*;
286
287    unsafe impl<S: PageSize, const N: usize> FrameAllocator<S> for FreeList<N> {
288        fn allocate_frame(&mut self) -> Option<PhysFrame<S>> {
289            let size = S::SIZE.try_into().unwrap();
290            let layout = PageLayout::from_size_align(size, size).unwrap();
291            let range = self.allocate(layout).ok()?;
292            let address = PhysAddr::new(range.start().try_into().unwrap());
293            Some(PhysFrame::from_start_address(address).unwrap())
294        }
295    }
296
297    impl<S: PageSize, const N: usize> FrameDeallocator<S> for FreeList<N> {
298        unsafe fn deallocate_frame(&mut self, frame: PhysFrame<S>) {
299            unsafe {
300                self.deallocate(frame.into())
301                    .expect("frame could not be deallocated");
302            }
303        }
304    }
305
306    impl<S: PageSize> From<PhysFrame<S>> for PageRange {
307        fn from(value: PhysFrame<S>) -> Self {
308            let start = value.start_address().as_u64().try_into().unwrap();
309            let len = value.size().try_into().unwrap();
310            Self::from_start_len(start, len).unwrap()
311        }
312    }
313}
free_list/lib.rs

free_list/
lib.rs
