free_list/
page_range.rs

Help
1use core::cmp::Ordering;
2use core::fmt;
3use core::num::NonZeroUsize;
4use core::ops::{Add, Range, Sub};
5
6use align_address::{usize_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        let start = usize_align_up(self.start, layout.align());
217        let range = match Self::from_start_len(start, layout.size()) {
218            Ok(range) => range,
219            Err(_) => unreachable!(),
220        };
221        if self.contains(range) {
222            Some(range)
223        } else {
224            None
225        }
226    }
227}
228
229impl TryFrom<Range<usize>> for PageRange {
230    type Error = PageRangeError;
231
232    fn try_from(value: Range<usize>) -> Result<Self, Self::Error> {
233        Self::new(value.start, value.end)
234    }
235}
236
237impl fmt::Debug for PageRange {
238    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
239        self.start.fmt(f)?;
240        f.write_str("..")?;
241        self.end.fmt(f)?;
242        Ok(())
243    }
244}
245
246impl fmt::Display for PageRange {
247    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
248        let Self { start, end } = self;
249        let len = self.len();
250        let pages = self.pages();
251        if f.alternate() {
252            write!(
253                f,
254                "{start:#18x}..{end:#18x} (len = {len:#18x}, pages = {pages:16})"
255            )
256        } else {
257            write!(f, "{start:#x}..{end:#x} (len = {len:#x}, pages = {pages})")
258        }
259    }
260}
261
262impl PartialOrd for PageRange {
263    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
264        if self.end() <= other.start {
265            Some(Ordering::Less)
266        } else if self.start >= other.end() {
267            Some(Ordering::Greater)
268        } else if self == other {
269            Some(Ordering::Equal)
270        } else {
271            None
272        }
273    }
274}
275
276impl Add for PageRange {
277    type Output = Option<Self>;
278
279    fn add(self, rhs: Self) -> Self::Output {
280        if !(self.touches(rhs) || self.overlaps(rhs)) {
281            return None;
282        }
283
284        Some(PageRange::new(self.start.min(rhs.start), self.end().max(rhs.end())).unwrap())
285    }
286}
287
288impl Sub for PageRange {
289    type Output = PageRangeSub;
290
291    fn sub(self, rhs: Self) -> Self::Output {
292        if !self.overlaps(rhs) {
293            return PageRangeSub::One(self);
294        }
295
296        let before = PageRange::new(self.start, rhs.start).ok();
297        let after = PageRange::new(rhs.end(), self.end()).ok();
298
299        match (before, after) {
300            (None, None) => PageRangeSub::None,
301            (None, Some(range)) | (Some(range), None) => PageRangeSub::One(range),
302            (Some(a), Some(b)) => PageRangeSub::Two(a, b),
303        }
304    }
305}
306
307/// The output of [`PageRange::sub`].
308pub enum PageRangeSub {
309    /// The result is empty.
310    None,
311
312    /// The result contains one page range.
313    One(PageRange),
314
315    /// The result contains two page ranges.
316    Two(PageRange, PageRange),
317}
318
319#[cfg(test)]
320mod tests {
321    use core::alloc::Layout;
322
323    use super::*;
324
325    #[test]
326    fn niche() {
327        assert_eq!(
328            Layout::new::<Option<PageRange>>(),
329            Layout::new::<PageRange>()
330        );
331    }
332
333    #[test]
334    fn overlaps() {
335        let assert = |a, b, c: bool| {
336            let a = PageRange::try_from(a).unwrap();
337            let b = PageRange::try_from(b).unwrap();
338            assert_eq!(c, a.overlaps(b), "{a}.overlaps({b})");
339        };
340
341        assert(0x2000..0x5000, 0x0000..0x1000, false);
342        assert(0x2000..0x5000, 0x0000..0x2000, false);
343        assert(0x2000..0x5000, 0x0000..0x3000, true);
344        assert(0x2000..0x5000, 0x0000..0x4000, true);
345        assert(0x2000..0x5000, 0x0000..0x5000, true);
346        assert(0x2000..0x5000, 0x0000..0x6000, true);
347        assert(0x2000..0x5000, 0x0000..0x7000, true);
348        assert(0x2000..0x5000, 0x0000..0x7000, true);
349        assert(0x2000..0x5000, 0x1000..0x7000, true);
350        assert(0x2000..0x5000, 0x2000..0x7000, true);
351        assert(0x2000..0x5000, 0x3000..0x7000, true);
352        assert(0x2000..0x5000, 0x4000..0x7000, true);
353        assert(0x2000..0x5000, 0x5000..0x7000, false);
354        assert(0x2000..0x5000, 0x6000..0x7000, false);
355    }
356
357    #[test]
358    fn add() {
359        let assert = |a, b, c: Option<Range<usize>>| {
360            let a = PageRange::try_from(a).unwrap();
361            let b = PageRange::try_from(b).unwrap();
362            let c = c.map(|range| PageRange::try_from(range).unwrap());
363            assert_eq!(c, a + b, "{a} + {b}");
364        };
365
366        assert(0x2000..0x5000, 0x0000..0x1000, None);
367        assert(0x2000..0x5000, 0x0000..0x2000, Some(0x0000..0x5000));
368        assert(0x2000..0x5000, 0x0000..0x3000, Some(0x0000..0x5000));
369        assert(0x2000..0x5000, 0x0000..0x4000, Some(0x0000..0x5000));
370        assert(0x2000..0x5000, 0x0000..0x5000, Some(0x0000..0x5000));
371        assert(0x2000..0x5000, 0x0000..0x6000, Some(0x0000..0x6000));
372        assert(0x2000..0x5000, 0x0000..0x7000, Some(0x0000..0x7000));
373        assert(0x2000..0x5000, 0x1000..0x7000, Some(0x1000..0x7000));
374        assert(0x2000..0x5000, 0x2000..0x7000, Some(0x2000..0x7000));
375        assert(0x2000..0x5000, 0x3000..0x7000, Some(0x2000..0x7000));
376        assert(0x2000..0x5000, 0x4000..0x7000, Some(0x2000..0x7000));
377        assert(0x2000..0x5000, 0x5000..0x7000, Some(0x2000..0x7000));
378        assert(0x2000..0x5000, 0x6000..0x7000, None);
379
380        assert(0x2000..0x5000, 0x2000..0x3000, Some(0x2000..0x5000));
381        assert(0x2000..0x5000, 0x2000..0x4000, Some(0x2000..0x5000));
382        assert(0x2000..0x5000, 0x2000..0x5000, Some(0x2000..0x5000));
383        assert(0x2000..0x5000, 0x3000..0x5000, Some(0x2000..0x5000));
384        assert(0x2000..0x5000, 0x4000..0x5000, Some(0x2000..0x5000));
385
386        assert(0x2000..0x5000, 0x3000..0x4000, Some(0x2000..0x5000));
387    }
388
389    #[allow(clippy::single_range_in_vec_init)]
390    #[test]
391    fn sub() {
392        let assert = |a, b, c: &[Range<usize>]| {
393            let a = PageRange::try_from(a).unwrap();
394            let b = PageRange::try_from(b).unwrap();
395            let c = c
396                .iter()
397                .cloned()
398                .map(|range| PageRange::try_from(range).unwrap())
399                .collect::<Vec<_>>();
400            let v = match a - b {
401                PageRangeSub::None => vec![],
402                PageRangeSub::One(a) => vec![a],
403                PageRangeSub::Two(a, b) => vec![a, b],
404            };
405            assert_eq!(c, v, "{a} - {b}");
406        };
407
408        assert(0x2000..0x5000, 0x0000..0x1000, &[0x2000..0x5000]);
409        assert(0x2000..0x5000, 0x0000..0x2000, &[0x2000..0x5000]);
410        assert(0x2000..0x5000, 0x0000..0x3000, &[0x3000..0x5000]);
411        assert(0x2000..0x5000, 0x0000..0x4000, &[0x4000..0x5000]);
412        assert(0x2000..0x5000, 0x0000..0x5000, &[]);
413        assert(0x2000..0x5000, 0x0000..0x6000, &[]);
414        assert(0x2000..0x5000, 0x0000..0x7000, &[]);
415        assert(0x2000..0x5000, 0x1000..0x7000, &[]);
416        assert(0x2000..0x5000, 0x2000..0x7000, &[]);
417        assert(0x2000..0x5000, 0x3000..0x7000, &[0x2000..0x3000]);
418        assert(0x2000..0x5000, 0x4000..0x7000, &[0x2000..0x4000]);
419        assert(0x2000..0x5000, 0x5000..0x7000, &[0x2000..0x5000]);
420        assert(0x2000..0x5000, 0x6000..0x7000, &[0x2000..0x5000]);
421
422        assert(0x2000..0x5000, 0x2000..0x3000, &[0x3000..0x5000]);
423        assert(0x2000..0x5000, 0x2000..0x4000, &[0x4000..0x5000]);
424        assert(0x2000..0x5000, 0x2000..0x5000, &[]);
425        assert(0x2000..0x5000, 0x3000..0x5000, &[0x2000..0x3000]);
426        assert(0x2000..0x5000, 0x4000..0x5000, &[0x2000..0x4000]);
427
428        assert(
429            0x2000..0x5000,
430            0x3000..0x4000,
431            &[0x2000..0x3000, 0x4000..0x5000],
432        );
433    }
434}
free_list/page_range.rs

free_list/
page_range.rs
