free_list/
page_range.rs

1use core::cmp::Ordering;
2use core::fmt;
3use core::num::NonZeroUsize;
4use core::ops::{Add, Range, Sub};
5
6use align_address::{usize_checked_align_up, usize_is_aligned_to};
7
8use crate::{PageLayout, PAGE_SIZE};
9
10/// Invalid parameters in [`PageRange`] construction.
11#[non_exhaustive]
12#[derive(Clone, PartialEq, Eq, Debug)]
13pub struct PageRangeError;
14
15impl fmt::Display for PageRangeError {
16    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
17        f.write_str("invalid parameters to PageLayout::new")
18    }
19}
20
21/// A non-empty page-aligned memory range.
22#[derive(Copy, Clone, PartialEq, Eq, Hash)]
23pub struct PageRange {
24    start: usize,
25    end: NonZeroUsize,
26}
27
28impl PageRange {
29    /// Constructs a new `PageRange` from a given `start` and `end`,
30    /// or returns `PageRangeError` if any of the following conidtions
31    /// are not met:
32    ///
33    /// * `start` must be smaller than `end`,
34    ///
35    /// * `start` and `end` must be aligned to [`PAGE_SIZE`].
36    ///
37    /// # Examples
38    ///
39    /// ```
40    /// # #![allow(unused_variables)]
41    /// use free_list::PageRange;
42    ///
43    /// let range = PageRange::new(0x1000, 0x5000).unwrap();
44    /// ```
45    pub const fn new(start: usize, end: usize) -> Result<Self, PageRangeError> {
46        if start >= end {
47            return Err(PageRangeError);
48        }
49
50        if !usize_is_aligned_to(start, PAGE_SIZE) {
51            return Err(PageRangeError);
52        }
53
54        if !usize_is_aligned_to(end, PAGE_SIZE) {
55            return Err(PageRangeError);
56        }
57
58        let end = match NonZeroUsize::new(end) {
59            Some(end) => end,
60            None => unreachable!(),
61        };
62
63        Ok(Self { start, end })
64    }
65
66    /// Constructs a new `PageRange` from a given `start` and `end`,
67    /// or returns `PageRangeError` if any of the following conidtions
68    /// are not met:
69    ///
70    /// * `len` must not be zero,
71    ///
72    /// * `start` and `len` must be aligned to [`PAGE_SIZE`],
73    ///
74    /// * `start + len` must not overflow.
75    ///
76    /// # Examples
77    ///
78    /// ```
79    /// # #![allow(unused_variables)]
80    /// use free_list::PageRange;
81    ///
82    /// let range = PageRange::from_start_len(0x1000, 0x4000).unwrap();
83    /// ```
84    pub const fn from_start_len(start: usize, len: usize) -> Result<Self, PageRangeError> {
85        let end = match start.checked_add(len) {
86            Some(end) => end,
87            None => return Err(PageRangeError),
88        };
89        Self::new(start, end)
90    }
91
92    /// Returns the start address of this page range.
93    ///
94    /// # Examples
95    ///
96    /// ```
97    /// use free_list::PageRange;
98    ///
99    /// let range = PageRange::new(0x1000, 0x5000).unwrap();
100    /// assert_eq!(range.start(), 0x1000);
101    /// ```
102    pub const fn start(self) -> usize {
103        self.start
104    }
105
106    /// Returns the end address of this page range.
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// use free_list::PageRange;
112    ///
113    /// let range = PageRange::new(0x1000, 0x5000).unwrap();
114    /// assert_eq!(range.end(), 0x5000);
115    /// ```
116    pub const fn end(self) -> usize {
117        self.end.get()
118    }
119
120    /// Returns the length of this page range in bytes.
121    ///
122    /// # Examples
123    ///
124    /// ```
125    /// use free_list::PageRange;
126    ///
127    /// let range = PageRange::new(0x1000, 0x5000).unwrap();
128    /// assert_eq!(range.len().get(), 0x4000);
129    /// ```
130    pub const fn len(self) -> NonZeroUsize {
131        match NonZeroUsize::new(self.end() - self.start) {
132            Some(len) => len,
133            None => unreachable!(),
134        }
135    }
136
137    /// Returns the length of this page range in pages of size [`PAGE_SIZE`].
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// use free_list::PageRange;
143    ///
144    /// let range = PageRange::new(0x1000, 0x5000).unwrap();
145    /// assert_eq!(range.pages().get(), 4);
146    /// ```
147    pub const fn pages(self) -> NonZeroUsize {
148        match NonZeroUsize::new(self.len().get() / PAGE_SIZE) {
149            Some(pages) => pages,
150            None => unreachable!(),
151        }
152    }
153
154    /// Returns true if `self` overlaps with `other`.
155    ///
156    /// This property is exclusive with [`PageRange::touches`].
157    ///
158    /// # Examples
159    ///
160    /// ```
161    /// use free_list::PageRange;
162    ///
163    /// let a = PageRange::new(0x1000, 0x5000).unwrap();
164    /// let b = PageRange::new(0x3000, 0x7000).unwrap();
165    /// assert!(a.overlaps(b));
166    /// ```
167    pub const fn overlaps(self, other: Self) -> bool {
168        self.end() > other.start && self.start < other.end()
169    }
170
171    /// Returns true if `self` touches `other`.
172    ///
173    /// This is exclusive with [`PageRange::overlaps`].
174    ///
175    /// # Examples
176    ///
177    /// ```
178    /// use free_list::PageRange;
179    ///
180    /// let a = PageRange::new(0x1000, 0x5000).unwrap();
181    /// let b = PageRange::new(0x5000, 0x9000).unwrap();
182    /// assert!(a.touches(b));
183    /// ```
184    pub const fn touches(self, other: Self) -> bool {
185        self.end() == other.start || self.start == other.end()
186    }
187
188    /// Returns true if `self` contains `other`.
189    ///
190    /// # Examples
191    ///
192    /// ```
193    /// use free_list::PageRange;
194    ///
195    /// let a = PageRange::new(0x1000, 0x5000).unwrap();
196    /// let b = PageRange::new(0x1000, 0x3000).unwrap();
197    /// assert!(a.contains(b));
198    /// ```
199    pub const fn contains(self, other: Self) -> bool {
200        self.start <= other.start && self.end() >= other.end()
201    }
202
203    /// Returns the first page range that is contained in `self` and satisfies `layout`.
204    ///
205    /// # Examples
206    ///
207    /// ```
208    /// use free_list::{PageLayout, PageRange};
209    ///
210    /// let range = PageRange::new(0x1000, 0x5000).unwrap();
211    /// let layout = PageLayout::from_size_align(0x3000, 0x2000).unwrap();
212    /// let expected = PageRange::new(0x2000, 0x5000).unwrap();
213    /// assert_eq!(range.fit(layout), Some(expected));
214    /// ```
215    pub const fn fit(self, layout: PageLayout) -> Option<PageRange> {
216        // FIXME: use `?` instead, once possible in constant functions
217        let Some(start) = usize_checked_align_up(self.start, layout.align()) else {
218            return None;
219        };
220        let Ok(range) = Self::from_start_len(start, layout.size()) else {
221            return None;
222        };
223        if self.contains(range) {
224            Some(range)
225        } else {
226            None
227        }
228    }
229}
230
231impl TryFrom<Range<usize>> for PageRange {
232    type Error = PageRangeError;
233
234    fn try_from(value: Range<usize>) -> Result<Self, Self::Error> {
235        Self::new(value.start, value.end)
236    }
237}
238
239impl fmt::Debug for PageRange {
240    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
241        self.start.fmt(f)?;
242        f.write_str("..")?;
243        self.end.fmt(f)?;
244        Ok(())
245    }
246}
247
248impl fmt::Display for PageRange {
249    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
250        let Self { start, end } = self;
251        let len = self.len();
252        let pages = self.pages();
253        if f.alternate() {
254            write!(
255                f,
256                "{start:#18x}..{end:#18x} (len = {len:#18x}, pages = {pages:16})"
257            )
258        } else {
259            write!(f, "{start:#x}..{end:#x} (len = {len:#x}, pages = {pages})")
260        }
261    }
262}
263
264impl PartialOrd for PageRange {
265    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
266        if self.end() <= other.start {
267            Some(Ordering::Less)
268        } else if self.start >= other.end() {
269            Some(Ordering::Greater)
270        } else if self == other {
271            Some(Ordering::Equal)
272        } else {
273            None
274        }
275    }
276}
277
278impl Add for PageRange {
279    type Output = Option<Self>;
280
281    fn add(self, rhs: Self) -> Self::Output {
282        if !(self.touches(rhs) || self.overlaps(rhs)) {
283            return None;
284        }
285
286        Some(PageRange::new(self.start.min(rhs.start), self.end().max(rhs.end())).unwrap())
287    }
288}
289
290impl Sub for PageRange {
291    type Output = PageRangeSub;
292
293    fn sub(self, rhs: Self) -> Self::Output {
294        if !self.overlaps(rhs) {
295            return PageRangeSub::One(self);
296        }
297
298        let before = PageRange::new(self.start, rhs.start).ok();
299        let after = PageRange::new(rhs.end(), self.end()).ok();
300
301        match (before, after) {
302            (None, None) => PageRangeSub::None,
303            (None, Some(range)) | (Some(range), None) => PageRangeSub::One(range),
304            (Some(a), Some(b)) => PageRangeSub::Two(a, b),
305        }
306    }
307}
308
309/// The output of [`PageRange::sub`].
310pub enum PageRangeSub {
311    /// The result is empty.
312    None,
313
314    /// The result contains one page range.
315    One(PageRange),
316
317    /// The result contains two page ranges.
318    Two(PageRange, PageRange),
319}
320
321#[cfg(test)]
322mod tests {
323    use core::alloc::Layout;
324
325    use super::*;
326
327    #[test]
328    fn niche() {
329        assert_eq!(
330            Layout::new::<Option<PageRange>>(),
331            Layout::new::<PageRange>()
332        );
333    }
334
335    #[test]
336    fn overlaps() {
337        let assert = |a, b, c: bool| {
338            let a = PageRange::try_from(a).unwrap();
339            let b = PageRange::try_from(b).unwrap();
340            assert_eq!(c, a.overlaps(b), "{a}.overlaps({b})");
341        };
342
343        assert(0x2000..0x5000, 0x0000..0x1000, false);
344        assert(0x2000..0x5000, 0x0000..0x2000, false);
345        assert(0x2000..0x5000, 0x0000..0x3000, true);
346        assert(0x2000..0x5000, 0x0000..0x4000, true);
347        assert(0x2000..0x5000, 0x0000..0x5000, true);
348        assert(0x2000..0x5000, 0x0000..0x6000, true);
349        assert(0x2000..0x5000, 0x0000..0x7000, true);
350        assert(0x2000..0x5000, 0x0000..0x7000, true);
351        assert(0x2000..0x5000, 0x1000..0x7000, true);
352        assert(0x2000..0x5000, 0x2000..0x7000, true);
353        assert(0x2000..0x5000, 0x3000..0x7000, true);
354        assert(0x2000..0x5000, 0x4000..0x7000, true);
355        assert(0x2000..0x5000, 0x5000..0x7000, false);
356        assert(0x2000..0x5000, 0x6000..0x7000, false);
357    }
358
359    #[test]
360    fn add() {
361        let assert = |a, b, c: Option<Range<usize>>| {
362            let a = PageRange::try_from(a).unwrap();
363            let b = PageRange::try_from(b).unwrap();
364            let c = c.map(|range| PageRange::try_from(range).unwrap());
365            assert_eq!(c, a + b, "{a} + {b}");
366        };
367
368        assert(0x2000..0x5000, 0x0000..0x1000, None);
369        assert(0x2000..0x5000, 0x0000..0x2000, Some(0x0000..0x5000));
370        assert(0x2000..0x5000, 0x0000..0x3000, Some(0x0000..0x5000));
371        assert(0x2000..0x5000, 0x0000..0x4000, Some(0x0000..0x5000));
372        assert(0x2000..0x5000, 0x0000..0x5000, Some(0x0000..0x5000));
373        assert(0x2000..0x5000, 0x0000..0x6000, Some(0x0000..0x6000));
374        assert(0x2000..0x5000, 0x0000..0x7000, Some(0x0000..0x7000));
375        assert(0x2000..0x5000, 0x1000..0x7000, Some(0x1000..0x7000));
376        assert(0x2000..0x5000, 0x2000..0x7000, Some(0x2000..0x7000));
377        assert(0x2000..0x5000, 0x3000..0x7000, Some(0x2000..0x7000));
378        assert(0x2000..0x5000, 0x4000..0x7000, Some(0x2000..0x7000));
379        assert(0x2000..0x5000, 0x5000..0x7000, Some(0x2000..0x7000));
380        assert(0x2000..0x5000, 0x6000..0x7000, None);
381
382        assert(0x2000..0x5000, 0x2000..0x3000, Some(0x2000..0x5000));
383        assert(0x2000..0x5000, 0x2000..0x4000, Some(0x2000..0x5000));
384        assert(0x2000..0x5000, 0x2000..0x5000, Some(0x2000..0x5000));
385        assert(0x2000..0x5000, 0x3000..0x5000, Some(0x2000..0x5000));
386        assert(0x2000..0x5000, 0x4000..0x5000, Some(0x2000..0x5000));
387
388        assert(0x2000..0x5000, 0x3000..0x4000, Some(0x2000..0x5000));
389    }
390
391    #[allow(clippy::single_range_in_vec_init)]
392    #[test]
393    fn sub() {
394        let assert = |a, b, c: &[Range<usize>]| {
395            let a = PageRange::try_from(a).unwrap();
396            let b = PageRange::try_from(b).unwrap();
397            let c = c
398                .iter()
399                .cloned()
400                .map(|range| PageRange::try_from(range).unwrap())
401                .collect::<Vec<_>>();
402            let v = match a - b {
403                PageRangeSub::None => vec![],
404                PageRangeSub::One(a) => vec![a],
405                PageRangeSub::Two(a, b) => vec![a, b],
406            };
407            assert_eq!(c, v, "{a} - {b}");
408        };
409
410        assert(0x2000..0x5000, 0x0000..0x1000, &[0x2000..0x5000]);
411        assert(0x2000..0x5000, 0x0000..0x2000, &[0x2000..0x5000]);
412        assert(0x2000..0x5000, 0x0000..0x3000, &[0x3000..0x5000]);
413        assert(0x2000..0x5000, 0x0000..0x4000, &[0x4000..0x5000]);
414        assert(0x2000..0x5000, 0x0000..0x5000, &[]);
415        assert(0x2000..0x5000, 0x0000..0x6000, &[]);
416        assert(0x2000..0x5000, 0x0000..0x7000, &[]);
417        assert(0x2000..0x5000, 0x1000..0x7000, &[]);
418        assert(0x2000..0x5000, 0x2000..0x7000, &[]);
419        assert(0x2000..0x5000, 0x3000..0x7000, &[0x2000..0x3000]);
420        assert(0x2000..0x5000, 0x4000..0x7000, &[0x2000..0x4000]);
421        assert(0x2000..0x5000, 0x5000..0x7000, &[0x2000..0x5000]);
422        assert(0x2000..0x5000, 0x6000..0x7000, &[0x2000..0x5000]);
423
424        assert(0x2000..0x5000, 0x2000..0x3000, &[0x3000..0x5000]);
425        assert(0x2000..0x5000, 0x2000..0x4000, &[0x4000..0x5000]);
426        assert(0x2000..0x5000, 0x2000..0x5000, &[]);
427        assert(0x2000..0x5000, 0x3000..0x5000, &[0x2000..0x3000]);
428        assert(0x2000..0x5000, 0x4000..0x5000, &[0x2000..0x4000]);
429
430        assert(
431            0x2000..0x5000,
432            0x3000..0x4000,
433            &[0x2000..0x3000, 0x4000..0x5000],
434        );
435    }
436
437    #[test]
438    fn fit() {
439        let range = PageRange::new(0x1000, 0x5000).unwrap();
440        let layout = PageLayout::from_size_align(0x3000, 0x2000).unwrap();
441        let expected = PageRange::new(0x2000, 0x5000).unwrap();
442        assert_eq!(range.fit(layout), Some(expected));
443
444        let range = PageRange::new(0x1000, 0x5000).unwrap();
445        let layout = PageLayout::from_size_align(0, 0x2000).unwrap();
446        assert_eq!(range.fit(layout), None);
447
448        let range = PageRange::new(0xffff_ffff_ffff_0000, 0xffff_ffff_ffff_f000).unwrap();
449        let layout = PageLayout::from_size_align(0x1000, 0x10_0000).unwrap();
450        assert_eq!(range.fit(layout), None);
451    }
452}
free_list/page_range.rs

free_list/
page_range.rs
