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_align_down, usize_checked_align_up, usize_is_aligned_to};
7
8use crate::{PAGE_SIZE, PageLayout};
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    /// Returns the page range containing the half-open address interval `start..end`.
231    ///
232    /// # Examples
233    ///
234    /// ```
235    /// use free_list::PageRange;
236    ///
237    /// let range = PageRange::containing(0x1900, 0x4100).unwrap();
238    /// let expected = PageRange::new(0x1000, 0x5000).unwrap();
239    /// assert_eq!(range, expected);
240    /// ```
241    pub const fn containing(start: usize, end: usize) -> Result<Self, PageRangeError> {
242        let start = usize_align_down(start, PAGE_SIZE);
243        let Some(end) = usize_checked_align_up(end, PAGE_SIZE) else {
244            return Err(PageRangeError);
245        };
246        Self::new(start, end)
247    }
248
249    /// Returns the intersection of `self` and `rhs` as a new `PageRange` if non-empty.
250    ///
251    /// # Examples
252    ///
253    /// ```
254    /// use free_list::PageRange;
255    ///
256    /// let lhs = PageRange::new(0x1000, 0x3000).unwrap();
257    /// let rhs = PageRange::new(0x2000, 0x5000).unwrap();
258    /// let expected = PageRange::new(0x2000, 0x3000).unwrap();
259    /// assert_eq!(lhs.and(rhs), Some(expected));
260    /// ```
261    pub const fn and(self, rhs: Self) -> Option<Self> {
262        let start = if rhs.start() < self.start() {
263            self.start()
264        } else {
265            rhs.start()
266        };
267        let end = if rhs.end() < self.end() {
268            rhs.end()
269        } else {
270            self.end()
271        };
272        match Self::new(start, end) {
273            Ok(page_range) => Some(page_range),
274            Err(_) => None,
275        }
276    }
277}
278
279impl TryFrom<Range<usize>> for PageRange {
280    type Error = PageRangeError;
281
282    fn try_from(value: Range<usize>) -> Result<Self, Self::Error> {
283        Self::new(value.start, value.end)
284    }
285}
286
287impl fmt::Debug for PageRange {
288    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
289        self.start.fmt(f)?;
290        f.write_str("..")?;
291        self.end.fmt(f)?;
292        Ok(())
293    }
294}
295
296impl fmt::Display for PageRange {
297    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
298        let Self { start, end } = self;
299        let len = self.len();
300        let pages = self.pages();
301        if f.alternate() {
302            write!(
303                f,
304                "{start:#18x}..{end:#18x} (len = {len:#18x}, pages = {pages:16})"
305            )
306        } else {
307            write!(f, "{start:#x}..{end:#x} (len = {len:#x}, pages = {pages})")
308        }
309    }
310}
311
312impl PartialOrd for PageRange {
313    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
314        if self.end() <= other.start {
315            Some(Ordering::Less)
316        } else if self.start >= other.end() {
317            Some(Ordering::Greater)
318        } else if self == other {
319            Some(Ordering::Equal)
320        } else {
321            None
322        }
323    }
324}
325
326impl Add for PageRange {
327    type Output = Option<Self>;
328
329    fn add(self, rhs: Self) -> Self::Output {
330        if !(self.touches(rhs) || self.overlaps(rhs)) {
331            return None;
332        }
333
334        Some(PageRange::new(self.start.min(rhs.start), self.end().max(rhs.end())).unwrap())
335    }
336}
337
338impl Sub for PageRange {
339    type Output = PageRangeSub;
340
341    fn sub(self, rhs: Self) -> Self::Output {
342        if !self.overlaps(rhs) {
343            return PageRangeSub::One(self);
344        }
345
346        let before = PageRange::new(self.start, rhs.start).ok();
347        let after = PageRange::new(rhs.end(), self.end()).ok();
348
349        match (before, after) {
350            (None, None) => PageRangeSub::None,
351            (None, Some(range)) | (Some(range), None) => PageRangeSub::One(range),
352            (Some(a), Some(b)) => PageRangeSub::Two(a, b),
353        }
354    }
355}
356
357/// The output of [`PageRange::sub`].
358pub enum PageRangeSub {
359    /// The result is empty.
360    None,
361
362    /// The result contains one page range.
363    One(PageRange),
364
365    /// The result contains two page ranges.
366    Two(PageRange, PageRange),
367}
368
369#[cfg(test)]
370mod tests {
371    use core::alloc::Layout;
372
373    use super::*;
374
375    #[test]
376    fn niche() {
377        assert_eq!(
378            Layout::new::<Option<PageRange>>(),
379            Layout::new::<PageRange>()
380        );
381    }
382
383    #[test]
384    fn overlaps() {
385        let assert = |a, b, c: bool| {
386            let a = PageRange::try_from(a).unwrap();
387            let b = PageRange::try_from(b).unwrap();
388            assert_eq!(c, a.overlaps(b), "{a}.overlaps({b})");
389        };
390
391        assert(0x2000..0x5000, 0x0000..0x1000, false);
392        assert(0x2000..0x5000, 0x0000..0x2000, false);
393        assert(0x2000..0x5000, 0x0000..0x3000, true);
394        assert(0x2000..0x5000, 0x0000..0x4000, true);
395        assert(0x2000..0x5000, 0x0000..0x5000, true);
396        assert(0x2000..0x5000, 0x0000..0x6000, true);
397        assert(0x2000..0x5000, 0x0000..0x7000, true);
398        assert(0x2000..0x5000, 0x0000..0x7000, true);
399        assert(0x2000..0x5000, 0x1000..0x7000, true);
400        assert(0x2000..0x5000, 0x2000..0x7000, true);
401        assert(0x2000..0x5000, 0x3000..0x7000, true);
402        assert(0x2000..0x5000, 0x4000..0x7000, true);
403        assert(0x2000..0x5000, 0x5000..0x7000, false);
404        assert(0x2000..0x5000, 0x6000..0x7000, false);
405    }
406
407    #[test]
408    fn add() {
409        let assert = |a, b, c: Option<Range<usize>>| {
410            let a = PageRange::try_from(a).unwrap();
411            let b = PageRange::try_from(b).unwrap();
412            let c = c.map(|range| PageRange::try_from(range).unwrap());
413            assert_eq!(c, a + b, "{a} + {b}");
414        };
415
416        assert(0x2000..0x5000, 0x0000..0x1000, None);
417        assert(0x2000..0x5000, 0x0000..0x2000, Some(0x0000..0x5000));
418        assert(0x2000..0x5000, 0x0000..0x3000, Some(0x0000..0x5000));
419        assert(0x2000..0x5000, 0x0000..0x4000, Some(0x0000..0x5000));
420        assert(0x2000..0x5000, 0x0000..0x5000, Some(0x0000..0x5000));
421        assert(0x2000..0x5000, 0x0000..0x6000, Some(0x0000..0x6000));
422        assert(0x2000..0x5000, 0x0000..0x7000, Some(0x0000..0x7000));
423        assert(0x2000..0x5000, 0x1000..0x7000, Some(0x1000..0x7000));
424        assert(0x2000..0x5000, 0x2000..0x7000, Some(0x2000..0x7000));
425        assert(0x2000..0x5000, 0x3000..0x7000, Some(0x2000..0x7000));
426        assert(0x2000..0x5000, 0x4000..0x7000, Some(0x2000..0x7000));
427        assert(0x2000..0x5000, 0x5000..0x7000, Some(0x2000..0x7000));
428        assert(0x2000..0x5000, 0x6000..0x7000, None);
429
430        assert(0x2000..0x5000, 0x2000..0x3000, Some(0x2000..0x5000));
431        assert(0x2000..0x5000, 0x2000..0x4000, Some(0x2000..0x5000));
432        assert(0x2000..0x5000, 0x2000..0x5000, Some(0x2000..0x5000));
433        assert(0x2000..0x5000, 0x3000..0x5000, Some(0x2000..0x5000));
434        assert(0x2000..0x5000, 0x4000..0x5000, Some(0x2000..0x5000));
435
436        assert(0x2000..0x5000, 0x3000..0x4000, Some(0x2000..0x5000));
437    }
438
439    #[allow(clippy::single_range_in_vec_init)]
440    #[test]
441    fn sub() {
442        let assert = |a, b, c: &[Range<usize>]| {
443            let a = PageRange::try_from(a).unwrap();
444            let b = PageRange::try_from(b).unwrap();
445            let c = c
446                .iter()
447                .cloned()
448                .map(|range| PageRange::try_from(range).unwrap())
449                .collect::<Vec<_>>();
450            let v = match a - b {
451                PageRangeSub::None => vec![],
452                PageRangeSub::One(a) => vec![a],
453                PageRangeSub::Two(a, b) => vec![a, b],
454            };
455            assert_eq!(c, v, "{a} - {b}");
456        };
457
458        assert(0x2000..0x5000, 0x0000..0x1000, &[0x2000..0x5000]);
459        assert(0x2000..0x5000, 0x0000..0x2000, &[0x2000..0x5000]);
460        assert(0x2000..0x5000, 0x0000..0x3000, &[0x3000..0x5000]);
461        assert(0x2000..0x5000, 0x0000..0x4000, &[0x4000..0x5000]);
462        assert(0x2000..0x5000, 0x0000..0x5000, &[]);
463        assert(0x2000..0x5000, 0x0000..0x6000, &[]);
464        assert(0x2000..0x5000, 0x0000..0x7000, &[]);
465        assert(0x2000..0x5000, 0x1000..0x7000, &[]);
466        assert(0x2000..0x5000, 0x2000..0x7000, &[]);
467        assert(0x2000..0x5000, 0x3000..0x7000, &[0x2000..0x3000]);
468        assert(0x2000..0x5000, 0x4000..0x7000, &[0x2000..0x4000]);
469        assert(0x2000..0x5000, 0x5000..0x7000, &[0x2000..0x5000]);
470        assert(0x2000..0x5000, 0x6000..0x7000, &[0x2000..0x5000]);
471
472        assert(0x2000..0x5000, 0x2000..0x3000, &[0x3000..0x5000]);
473        assert(0x2000..0x5000, 0x2000..0x4000, &[0x4000..0x5000]);
474        assert(0x2000..0x5000, 0x2000..0x5000, &[]);
475        assert(0x2000..0x5000, 0x3000..0x5000, &[0x2000..0x3000]);
476        assert(0x2000..0x5000, 0x4000..0x5000, &[0x2000..0x4000]);
477
478        assert(
479            0x2000..0x5000,
480            0x3000..0x4000,
481            &[0x2000..0x3000, 0x4000..0x5000],
482        );
483    }
484
485    #[test]
486    fn fit() {
487        let range = PageRange::new(0x1000, 0x5000).unwrap();
488        let layout = PageLayout::from_size_align(0x3000, 0x2000).unwrap();
489        let expected = PageRange::new(0x2000, 0x5000).unwrap();
490        assert_eq!(range.fit(layout), Some(expected));
491
492        let range = PageRange::new(0x1000, 0x5000).unwrap();
493        let layout = PageLayout::from_size_align(0, 0x2000).unwrap();
494        assert_eq!(range.fit(layout), None);
495
496        let range = PageRange::new(0xffff_ffff_ffff_0000, 0xffff_ffff_ffff_f000).unwrap();
497        let layout = PageLayout::from_size_align(0x1000, 0x10_0000).unwrap();
498        assert_eq!(range.fit(layout), None);
499    }
500}
free_list/page_range.rs

free_list/
page_range.rs
