bootloader 0.2.0-alpha-001

An experimental pure-Rust x86 bootloader.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

use x86_64::PhysAddr;
use x86_64::structures::paging::{PAGE_SIZE, PhysFrame};
use os_bootinfo::{MemoryMap, MemoryRegion, MemoryRegionType};

pub(crate) struct FrameAllocator<'a> {
    pub memory_map: &'a mut MemoryMap,
}

impl<'a> FrameAllocator<'a> {
    pub(crate) fn allocate_frame(&mut self) -> PhysFrame {
        let page_size = u64::from(PAGE_SIZE);
        let mut frame = None;
        for region in self.memory_map.iter_mut() {
            if region.start_addr < PhysAddr::new(1024 * 1024) {
                // don't allocate memory below 1M, since it might be used by bootloader or BIOS
                continue;
            }
            if region.region_type != MemoryRegionType::Usable {
                continue;
            }
            if region.len < page_size {
                continue;
            }
            assert_eq!(0, region.start_addr.as_u64() & 0xfff,
                "Region start address must be aligned");

            frame = Some(PhysFrame::containing_address(region.start_addr));
            region.start_addr += page_size;
            break;
        }
        if let Some(frame) = frame {
            self.mark_as_used(frame.start_address(), page_size);
            frame
        } else {
            panic!("Out of physical memory");
        }
    }

    pub(crate) fn mark_as_used(&mut self, addr: PhysAddr, len: u64) {
        let mut used_region = Some(MemoryRegion {
            start_addr: addr,
            len,
            region_type: MemoryRegionType::InUse,
        });
        let mut new_region = None;

        // check if it overlaps with another region
        for region in self.memory_map.iter_mut() {
            let region_start = region.start_addr;
            let region_end = region.start_addr + region.len;
            let used_start = addr;
            let used_end = addr + len;

            if region_start < used_end && region_end > used_start {
                // used area overlaps with region
                assert!(region.region_type == MemoryRegionType::Usable);
                if region_start < used_start && region_end > used_end {
                    // Case: (R = region, U = used_area)
                    // ----RRRRRRRRRRR----
                    // ------UUUU---------
                    region.len = used_start - region_start;
                    assert!(new_region.is_none(), "area overlaps with multiple regions");
                    new_region = Some(MemoryRegion {
                        start_addr: used_end,
                        len: region_end - used_end,
                        region_type: MemoryRegionType::Usable,
                    });
                } else if used_start <= region_start {
                    // Case: (R = region, U = used_area)
                    // ----RRRRRRRRRRR----
                    // --UUUU-------------
                        region.start_addr = used_end;
                } else if used_end >= used_end {
                    // Case: (R = region, U = used_area)
                    // ----RRRRRRRRRRR----
                    // -------------UUUU--
                    region.len = used_start - region_start;
                }
            }
            if region.region_type == MemoryRegionType::InUse {
                if used_end == region_start {
                    // merge regions
                    if let Some(used_region) = used_region.take() {
                        region.start_addr = used_region.start_addr;
                        region.len += used_region.len;
                    }
                } else if region_end == used_start {
                    // merge regions
                    if let Some(used_region) = used_region.take() {
                        region.len += used_region.len;
                    }
                }
            }
        }

        if let Some(new_region) = new_region {
            self.memory_map.add_region(new_region);
        }
        if let Some(used_region) = used_region {
            self.memory_map.add_region(used_region);
        }
    }
}