ostd/boot/
memory_region.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! Information of memory regions in the boot phase.
4
5use core::ops::Deref;
6
7use align_ext::AlignExt;
8
9use crate::mm::{PAGE_SIZE, Paddr, Vaddr, kspace::kernel_loaded_offset};
10
11/// The type of initial memory regions that are needed for the kernel.
12#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
13pub enum MemoryRegionType {
14    /// Maybe points to an unplugged DIMM module. It's bad anyway.
15    BadMemory = 0,
16    /// Some holes not specified by the bootloader/firmware. It may be used for
17    /// I/O memory but we don't know for sure.
18    Unknown = 1,
19    /// In ACPI spec, this area needs to be preserved when sleeping.
20    NonVolatileSleep = 2,
21    /// Reserved by BIOS or bootloader, do not use.
22    Reserved = 3,
23    /// The place where kernel sections are loaded.
24    Kernel = 4,
25    /// The place where kernel modules (e.g. initrd) are loaded, could be reused.
26    Module = 5,
27    /// The memory region provided as the framebuffer.
28    Framebuffer = 6,
29    /// Once used in the boot phase. Kernel can reclaim it after initialization.
30    Reclaimable = 7,
31    /// Directly usable by the frame allocator.
32    Usable = 8,
33}
34
35impl MemoryRegionType {
36    /// Returns whether the memory region corresponds to physical memory.
37    ///
38    /// The linear mapping will cover memory addresses up to the top of the physical memory.
39    /// Therefore, if this method returns `false`, the memory region may not be included in the
40    /// linear mapping.
41    pub fn is_physical(self) -> bool {
42        // Bad memory or I/O memory is not physical. All other memory should be physical.
43        !matches!(
44            self,
45            Self::BadMemory | Self::Unknown | Self::Reserved | Self::Framebuffer
46        )
47    }
48}
49
50/// The information of initial memory regions that are needed by the kernel.
51///
52/// The sections are **not** guaranteed to not overlap. The region must be page aligned.
53#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
54pub struct MemoryRegion {
55    base: usize,
56    len: usize,
57    typ: MemoryRegionType,
58}
59
60impl MemoryRegion {
61    /// Constructs a valid memory region.
62    pub const fn new(base: Paddr, len: usize, typ: MemoryRegionType) -> Self {
63        MemoryRegion { base, len, typ }
64    }
65
66    /// Constructs a bad memory region.
67    pub const fn bad() -> Self {
68        MemoryRegion {
69            base: 0,
70            len: 0,
71            typ: MemoryRegionType::BadMemory,
72        }
73    }
74
75    /// Constructs a memory region where kernel sections are loaded.
76    ///
77    /// Most boot protocols do not mark the place where the kernel loads as unusable. In this case,
78    /// we need to explicitly construct and append this memory region.
79    pub fn kernel() -> Self {
80        // These are physical addresses provided by the linker script.
81        unsafe extern "C" {
82            fn __kernel_start();
83            fn __kernel_end();
84        }
85        MemoryRegion {
86            base: __kernel_start as *const () as usize - kernel_loaded_offset(),
87            len: __kernel_end as *const () as usize - __kernel_start as *const () as usize,
88            typ: MemoryRegionType::Kernel,
89        }
90    }
91
92    /// Constructs a framebuffer memory region.
93    pub fn framebuffer(fb: &crate::boot::BootloaderFramebufferArg) -> Self {
94        Self {
95            base: fb.address,
96            len: (fb.width * fb.height * fb.bpp).div_ceil(8), // round up when divide with 8 (bits/Byte)
97            typ: MemoryRegionType::Framebuffer,
98        }
99    }
100
101    /// Constructs a module memory region from a byte slice that lives in the linear mapping.
102    ///
103    /// # Panics
104    ///
105    /// This method will panic if the byte slice does not live in the linear mapping.
106    pub fn module(bytes: &[u8]) -> Self {
107        let vaddr = bytes.as_ptr() as Vaddr;
108        assert!(crate::mm::kspace::LINEAR_MAPPING_VADDR_RANGE.contains(&vaddr));
109
110        Self {
111            base: vaddr - crate::mm::kspace::LINEAR_MAPPING_BASE_VADDR,
112            len: bytes.len(),
113            typ: MemoryRegionType::Reclaimable,
114        }
115    }
116
117    /// Returns the physical address of the base of the region.
118    pub fn base(&self) -> Paddr {
119        self.base
120    }
121
122    /// Returns the length in bytes of the region.
123    pub fn len(&self) -> usize {
124        self.len
125    }
126
127    /// Returns the physical address of the end of the region.
128    pub fn end(&self) -> Paddr {
129        self.base + self.len
130    }
131
132    /// Checks whether the region is empty
133    pub fn is_empty(&self) -> bool {
134        self.len == 0
135    }
136
137    /// Returns the type of the region.
138    pub fn typ(&self) -> MemoryRegionType {
139        self.typ
140    }
141
142    fn as_aligned(&self) -> Self {
143        let (base, len) = match self.typ() {
144            MemoryRegionType::Usable => {
145                let aligned_base = self.base().align_up(PAGE_SIZE);
146                let aligned_end = self.end().align_down(PAGE_SIZE);
147                (aligned_base, aligned_end.saturating_sub(aligned_base))
148            }
149            _ => {
150                let aligned_base = self.base().align_down(PAGE_SIZE);
151                let aligned_end = self.end().align_up(PAGE_SIZE);
152                (aligned_base, aligned_end - aligned_base)
153            }
154        };
155        MemoryRegion {
156            base,
157            len,
158            typ: self.typ,
159        }
160    }
161}
162
163/// The maximum number of regions that can be handled.
164///
165/// The choice of 512 is probably fine since old Linux boot protocol only
166/// allows 128 regions.
167//
168// TODO: confirm the number or make it configurable.
169const MAX_REGIONS: usize = 512;
170
171/// A heapless set of memory regions.
172///
173/// The set cannot contain more than `LEN` regions.
174pub(crate) struct MemoryRegionArray<const LEN: usize = MAX_REGIONS> {
175    regions: [MemoryRegion; LEN],
176    count: usize,
177}
178
179impl<const LEN: usize> Default for MemoryRegionArray<LEN> {
180    fn default() -> Self {
181        Self::new()
182    }
183}
184
185impl<const LEN: usize> Deref for MemoryRegionArray<LEN> {
186    type Target = [MemoryRegion];
187
188    fn deref(&self) -> &Self::Target {
189        &self.regions[..self.count]
190    }
191}
192
193/// An error returned by [`MemoryRegionArray::push`] when the array is full.
194#[derive(Debug)]
195pub(crate) struct ArrayFullError;
196
197impl<const LEN: usize> MemoryRegionArray<LEN> {
198    /// Constructs an empty set.
199    pub(crate) const fn new() -> Self {
200        Self {
201            regions: [MemoryRegion::bad(); LEN],
202            count: 0,
203        }
204    }
205
206    /// Appends a region to the set.
207    ///
208    /// If the set is full, an error is returned.
209    pub(crate) fn push(&mut self, region: MemoryRegion) -> Result<(), ArrayFullError> {
210        if self.count >= self.regions.len() {
211            return Err(ArrayFullError);
212        }
213
214        self.regions[self.count] = region;
215        self.count += 1;
216
217        Ok(())
218    }
219
220    /// Sorts the regions and returns a full set of non-overlapping regions.
221    ///
222    /// If an address is in multiple regions, the region with the lowest
223    /// usability will be its type.
224    ///
225    /// All the addresses between 0 and the end of the last region will be in
226    /// the resulting set. If an address is not in any region, it will be marked
227    /// as [`MemoryRegionType::Unknown`].
228    ///
229    /// If any of the region boundaries are not page-aligned, they will be aligned
230    /// according to the type of the region.
231    ///
232    /// # Panics
233    ///
234    /// This method will panic if the number of output regions is greater than `LEN`.
235    pub(crate) fn into_non_overlapping(mut self) -> Self {
236        // Align the regions and drop those that become empty after alignment.
237        let mut count = 0;
238        for i in 0..self.count {
239            let region = self.regions[i].as_aligned();
240            if !region.is_empty() {
241                self.regions[count] = region;
242                count += 1;
243            }
244        }
245        self.count = count;
246
247        let max_addr = self.iter().map(|r| r.end()).max().unwrap_or(0);
248
249        let mut result = MemoryRegionArray::<LEN>::new();
250
251        let mut cur_right = 0;
252
253        while cur_right < max_addr {
254            // Find the most restrictive type.
255            let typ = self
256                .iter()
257                .filter(|region| (region.base()..region.end()).contains(&cur_right))
258                .map(|region| region.typ())
259                .min()
260                .unwrap_or(MemoryRegionType::Unknown);
261
262            // Find the right boundary.
263            let right = self
264                .iter()
265                .filter_map(|region| {
266                    if region.base() > cur_right {
267                        Some(region.base())
268                    } else if region.end() > cur_right {
269                        Some(region.end())
270                    } else {
271                        None
272                    }
273                })
274                .min()
275                .unwrap();
276
277            result
278                .push(MemoryRegion::new(cur_right, right - cur_right, typ))
279                .unwrap();
280
281            cur_right = right;
282        }
283
284        if result.is_empty() {
285            return result;
286        }
287
288        // Merge the adjacent regions with the same type.
289        let mut merged_count = 1;
290        for i in 1..result.count {
291            if result[i].typ() == result.regions[merged_count - 1].typ() {
292                result.regions[merged_count - 1] = MemoryRegion::new(
293                    result.regions[merged_count - 1].base(),
294                    result.regions[merged_count - 1].len() + result[i].len(),
295                    result.regions[merged_count - 1].typ(),
296                );
297            } else {
298                result.regions[merged_count] = result[i];
299                merged_count += 1;
300            }
301        }
302        result.count = merged_count;
303
304        result
305    }
306}
307
308#[cfg(ktest)]
309mod test {
310    use super::*;
311    use crate::prelude::ktest;
312
313    #[ktest]
314    fn sort_full_non_overlapping() {
315        let mut regions = MemoryRegionArray::<64>::new();
316        // Regions that can be combined.
317        regions
318            .push(MemoryRegion::new(
319                0,
320                PAGE_SIZE + 1,
321                MemoryRegionType::Usable,
322            ))
323            .unwrap();
324        regions
325            .push(MemoryRegion::new(
326                PAGE_SIZE - 1,
327                PAGE_SIZE + 2,
328                MemoryRegionType::Usable,
329            ))
330            .unwrap();
331        regions
332            .push(MemoryRegion::new(
333                PAGE_SIZE * 2,
334                PAGE_SIZE * 5,
335                MemoryRegionType::Usable,
336            ))
337            .unwrap();
338        // A punctured region.
339        regions
340            .push(MemoryRegion::new(
341                PAGE_SIZE * 3 + 1,
342                PAGE_SIZE - 2,
343                MemoryRegionType::BadMemory,
344            ))
345            .unwrap();
346        // A far region that left a hole in the middle.
347        regions
348            .push(MemoryRegion::new(
349                PAGE_SIZE * 9,
350                PAGE_SIZE * 2,
351                MemoryRegionType::Usable,
352            ))
353            .unwrap();
354
355        let regions = regions.into_non_overlapping();
356
357        assert_eq!(regions.count, 5);
358        assert_eq!(regions[0].base(), 0);
359        assert_eq!(regions[0].len(), PAGE_SIZE * 3);
360        assert_eq!(regions[0].typ(), MemoryRegionType::Usable);
361
362        assert_eq!(regions[1].base(), PAGE_SIZE * 3);
363        assert_eq!(regions[1].len(), PAGE_SIZE);
364        assert_eq!(regions[1].typ(), MemoryRegionType::BadMemory);
365
366        assert_eq!(regions[2].base(), PAGE_SIZE * 4);
367        assert_eq!(regions[2].len(), PAGE_SIZE * 3);
368        assert_eq!(regions[2].typ(), MemoryRegionType::Usable);
369
370        assert_eq!(regions[3].base(), PAGE_SIZE * 7);
371        assert_eq!(regions[3].len(), PAGE_SIZE * 2);
372        assert_eq!(regions[3].typ(), MemoryRegionType::Unknown);
373
374        assert_eq!(regions[4].base(), PAGE_SIZE * 9);
375        assert_eq!(regions[4].len(), PAGE_SIZE * 2);
376        assert_eq!(regions[4].typ(), MemoryRegionType::Usable);
377    }
378
379    #[ktest]
380    fn into_non_overlapping_drops_usable_subpage_regions() {
381        let mut regions = MemoryRegionArray::<64>::new();
382        let bases = [
383            100 * PAGE_SIZE,       // page-aligned
384            100 * PAGE_SIZE + 123, // unaligned
385        ];
386        let subpage_lens = [0, PAGE_SIZE / 2, PAGE_SIZE - 1];
387        for base in bases {
388            for len in subpage_lens {
389                regions
390                    .push(MemoryRegion::new(base, len, MemoryRegionType::Usable))
391                    .unwrap();
392            }
393        }
394        // `into_non_overlapping` drops usable regions whose lengths are smaller than a page.
395        let regions = regions.into_non_overlapping();
396        assert!(regions.is_empty());
397    }
398}
ostd/boot/memory_region.rs

ostd/boot/
memory_region.rs
