finchie/HexOS - Change SCGTKLIL3L6BITCIP2PGKSCJD2XQ2LKQWN63SWQXSELVGVZYMI3AC

Implement heap allocation

Basic kernel heap allocation, heavily influenced by this blog: https://os.phil-opp.com/#memory-management. The most exciting possibility this (immediately) enables is using the tracing crate in the kernel.

Created by finchie on December 29, 2023

SCGTKLIL3L6BITCIP2PGKSCJD2XQ2LKQWN63SWQXSELVGVZYMI3AC

Dependencies

In channels

main

Change contents

File addition: memory.rs (----------)

[3.1903]

use bootloader_api::info::{MemoryRegionKind, MemoryRegions};
use x86_64::addr::{PhysAddr, VirtAddr};
use x86_64::registers::control::Cr3;
use x86_64::structures::paging::{
    FrameAllocator, OffsetPageTable, PageSize, PageTable, PhysFrame, Size4KiB,
};
// Not sure how to get the configured page size, but pretty sure it's only 4kib by default
// TODO: check if this is true and enable 64-bit pages
static PAGE_SIZE: u64 = Size4KiB::SIZE;
pub struct SimpleFrameAllocator<I>
where
    I: Iterator<Item = PhysFrame>,
{
    pub usable_frames: I,
}
// TODO: increase page size here as well
unsafe impl<I> FrameAllocator<Size4KiB> for SimpleFrameAllocator<I>
where
    I: Iterator<Item = PhysFrame>,
{
    fn allocate_frame(&mut self) -> Option<PhysFrame<Size4KiB>> {
        self.usable_frames.next()
    }
}
/// Caller must ensure memory map is valid
pub unsafe fn init_frame_allocator(
    memory_regions: &'static MemoryRegions,
) -> SimpleFrameAllocator<impl Iterator<Item = PhysFrame>> {
    // Collect all physical frames marked as usable
    let usable_frames = memory_regions
        .iter()
        // Filter to only usable frames
        .filter(|region| region.kind == MemoryRegionKind::Usable)
        // Map to start+end range
        .map(|region| region.start..region.end)
        // Collect all pages in region
        .flat_map(|region| region.step_by(PAGE_SIZE as usize))
        // Map to start address
        .map(|start_address| PhysFrame::containing_address(PhysAddr::new(start_address)));
    SimpleFrameAllocator { usable_frames }
}
/// Get the current active level 4 page table
unsafe fn active_level_4_table(physical_memory_offset: VirtAddr) -> &'static mut PageTable {
    let (physical_frame, _flags) = Cr3::read();
    let frame_physical_address = physical_frame.start_address();
    let frame_virtual_address = physical_memory_offset + frame_physical_address.as_u64();
    let page_table_address = frame_virtual_address.as_mut_ptr();
    &mut *page_table_address
}
pub unsafe fn init(physical_memory_offset: VirtAddr) -> OffsetPageTable<'static> {
    let active_table = active_level_4_table(physical_memory_offset);
    OffsetPageTable::new(active_table, physical_memory_offset)
}

Insertion in kernel/src/main.rs at line 5 [3.1937]
[2.32]
[2.32]
```
mod allocator;
```
Insertion in kernel/src/main.rs at line 8 [3.1937]
[2.57]
[3.1961]
```
mod memory;
```

Replacement in kernel/src/main.rs at line 12 [3.1937]

B:BD[3.1991] → [3.1991:2036]

use bootloader_api::{entry_point, BootInfo};

[3.1991]

[3.2036]

use bootloader_api::{config::Mapping, entry_point, BootInfo, BootloaderConfig};
use x86_64::VirtAddr;

Replacement in kernel/src/main.rs at line 15 [3.1937]

B:BD[3.2037] → [3.2037:2057]

entry_point!(main);

[3.2037]

[3.2057]

static BOOTLOADER_CONFIG: BootloaderConfig = {
    let mut config = BootloaderConfig::new_default();
    config.mappings.physical_memory = Some(Mapping::Dynamic);
    config
};
entry_point!(main, config = &BOOTLOADER_CONFIG);

Replacement in kernel/src/main.rs at line 24 [3.1937]

B:BD[3.2071] → [3.2071:2125]

B:BD[3.2125] → [2.58:70]

pub fn main(_boot_info: &'static mut BootInfo) -> ! {
    init();

[3.2071]

[2.70]

pub fn main(boot_info: &'static mut BootInfo) -> ! {
    init(boot_info);

Replacement in kernel/src/main.rs at line 30 [3.1937]
B:BD[3.2140] → [2.72:84]
```
fn init() {
```
[3.2140]
[2.84]
```
fn init(boot_info: &'static mut BootInfo) {
```

Insertion in kernel/src/main.rs at line 33 [3.1937]

[2.125]

    let mut offset_table = unsafe {
        memory::init(VirtAddr::new(
            boot_info
                .physical_memory_offset
                .into_option()
                .unwrap_or_default(),
        ))
    };
    let mut frame_allocator = unsafe { memory::init_frame_allocator(&boot_info.memory_regions) };
    allocator::init_heap(&mut offset_table, &mut frame_allocator).unwrap();

File addition: allocator.rs (----------)

[3.1903]

use linked_list_allocator::LockedHeap;
use x86_64::structures::paging::mapper::MapToError;
use x86_64::structures::paging::{FrameAllocator, Mapper, Page, PageTableFlags, Size4KiB};
use x86_64::VirtAddr;
#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();
// TODO: choose a better start address
pub const HEAP_START: usize = 0x_2222_0000_0000;
pub const HEAP_SIZE: usize = 512 * 1024; // 500 KiB
/// Initialize the kernel heap
pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError<Size4KiB>> {
    let heap_start = VirtAddr::new(HEAP_START as u64);
    let heap_end = heap_start + HEAP_SIZE - 1u64;
    // Get the pages between start & end adresses (inclusive)
    let page_range = {
        // TODO: larger page sizes
        let start_page: Page<Size4KiB> = Page::containing_address(heap_start);
        let end_page = Page::containing_address(heap_end);
        Page::range_inclusive(start_page, end_page)
    };
    // Map pages to be usable later
    for page in page_range {
        let frame = frame_allocator
            .allocate_frame()
            .ok_or(MapToError::FrameAllocationFailed)?;
        let page_flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
        unsafe { mapper.map_to(page, frame, page_flags, frame_allocator) }?.flush();
    }
    // Initialize the allocator
    unsafe {
        ALLOCATOR.lock().init(heap_start.as_mut_ptr(), HEAP_SIZE);
    }
    Ok(())
}

Insertion in kernel/Cargo.toml at line 9 [3.2242]
[2.2393]
[2.2393]
```
linked_list_allocator = "0.10.5"
```
Replacement in Cargo.lock at line 7 [3.2547]
B:BD[3.2680] → [3.2680:2699]
```
version = "1.0.76"
```
[3.2680]
[3.2699]
```
version = "1.0.77"
```

Replacement in Cargo.lock at line 9 [3.2547]

B:BD[3.2764] → [3.2764:2842]

checksum = "59d2a3357dde987206219e78ecfbbb6e8dad06cbb65292758d3270e6254f7355"

[3.2764]

[3.2842]

checksum = "c9d19de80eff169429ac1e9f48fffb163916b448a44e8e046186232046d9e1f9"

Replacement in Cargo.lock at line 193 [3.2547]
B:BD[3.7070] → [3.7070:7089]
```
version = "0.11.4"
```
[3.7070]
[3.7089]
```
version = "0.11.5"
```

Replacement in Cargo.lock at line 195 [3.2547]

B:BD[3.7154] → [3.7154:7232]

checksum = "e092090f6e2b68cee8dc291ec60e4706f6b0c5cd90b666a5248a20f30591ccb0"

[3.7154]

[3.7232]

checksum = "0668e5a71825bbf8d9af46b68441e4426f070e7465b45070464977214dfada9e"

Replacement in Cargo.lock at line 212 [3.2547]
B:BD[3.7460] → [3.7460:7479]
```
version = "0.11.4"
```
[3.7460]
[3.7479]
```
version = "0.11.5"
```

Replacement in Cargo.lock at line 214 [3.2547]

B:BD[3.7544] → [3.7544:7622]

checksum = "a36c0df7b26b44254828ece99ed72aa01695cc37f007a97afe8aee29feb26e3e"

[3.7544]

[3.7622]

checksum = "be20fe897a953c6f2e63d392ea067237af98d02cd15ef97a48fef2768c1ed269"

Replacement in Cargo.lock at line 221 [3.2547]
B:BD[3.7688] → [3.7688:7707]
```
version = "0.11.4"
```
[3.7688]
[3.7707]
```
version = "0.11.5"
```

Replacement in Cargo.lock at line 223 [3.2547]

B:BD[3.7772] → [3.7772:7850]

checksum = "88f843888771a490c3ad246e58bf25e62da70d2c653d74a3eca92acbab599e02"

[3.7772]

[3.7850]

checksum = "daaa1fb791aea49e19db7b7b3662665d511eb4e30a0627fa525fd92652f39358"

Insertion in Cargo.lock at line 512 [3.2547]
[2.2624]
[2.2624]
```
 "linked_list_allocator",
```

Insertion in Cargo.lock at line 567 [3.2547]

[3.16130]

name = "linked_list_allocator"
version = "0.10.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "9afa463f5405ee81cdb9cc2baf37e08ec7e4c8209442b5d72c04cfb2cd6e6286"
dependencies = [
 "spinning_top",
]
[[package]]

Insertion in Cargo.lock at line 594 [3.2547]

[3.16719]

name = "lock_api"
version = "0.4.11"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "3c168f8615b12bc01f9c17e2eb0cc07dcae1940121185446edc3744920e8ef45"
dependencies = [
 "autocfg",
 "scopeguard",
]
[[package]]

Replacement in Cargo.lock at line 624 [3.2547]
B:BD[3.17199] → [3.17199:17217]
```
version = "2.6.4"
```
[3.17199]
[3.17217]
```
version = "2.7.1"
```

Replacement in Cargo.lock at line 626 [3.2547]

B:BD[3.17282] → [3.17282:17360]

checksum = "f665ee40bc4a3c5590afb1e9677db74a508659dfd71e126420da8274909a0167"

[3.17282]

[3.17360]

checksum = "523dc4f511e55ab87b694dc30d0f820d60906ef06413f93d4d7a1385599cc149"

Insertion in Cargo.lock at line 786 [3.2547]

[3.21250]

name = "scopeguard"
version = "1.2.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49"
[[package]]

Insertion in Cargo.lock at line 870 [3.2547]

[2.3232]


[[package]]
name = "spinning_top"
version = "0.2.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "5b9eb1a2f4c41445a3a0ff9abc5221c5fcd28e1f13cd7c0397706f9ac938ddb0"
dependencies = [
 "lock_api",
]

Replacement in Cargo.lock at line 899 [3.2547]
B:BD[3.23529] → [3.23529:23547]
```
version = "3.8.1"
```
[3.23529]
[3.23547]
```
version = "3.9.0"
```

Replacement in Cargo.lock at line 901 [3.2547]

B:BD[3.23612] → [3.23612:23690]

checksum = "7ef1adac450ad7f4b3c28589471ade84f25f731a7a0fe30d71dfa9f60fd808e5"

[3.23612]

[3.23690]

checksum = "01ce4141aa927a6d1bd34a041795abd0db1cccba5d5f24b009f694bdf3a1f3fa"

Replacement in Cargo.lock at line 907 [3.2547]
B:BD[3.23774] → [3.23774:23797]
```
 "windows-sys 0.48.0",
```
[3.23774]
[3.23797]
```
 "windows-sys 0.52.0",
```
Replacement in Cargo.lock at line 912 [3.2547]
B:BD[3.23831] → [3.23831:23850]
```
version = "1.0.51"
```
[3.23831]
[3.23850]
```
version = "1.0.52"
```

Replacement in Cargo.lock at line 914 [3.2547]

B:BD[3.23915] → [3.23915:23993]

checksum = "f11c217e1416d6f036b870f14e0413d480dbf28edbee1f877abaf0206af43bb7"

[3.23915]

[3.23993]

checksum = "83a48fd946b02c0a526b2e9481c8e2a17755e47039164a86c4070446e3a4614d"

Replacement in Cargo.lock at line 921 [3.2547]
B:BD[3.24068] → [3.24068:24087]
```
version = "1.0.51"
```
[3.24068]
[3.24087]
```
version = "1.0.52"
```

Replacement in Cargo.lock at line 923 [3.2547]

B:BD[3.24152] → [3.24152:24230]

checksum = "01742297787513b79cf8e29d1056ede1313e2420b7b3b15d0a768b4921f549df"

[3.24152]

[3.24230]

checksum = "e7fbe9b594d6568a6a1443250a7e67d80b74e1e96f6d1715e1e21cc1888291d3"

Implement heap allocation

Dependencies

In channels

Change contents

File addition: memory.rs (----------)

Insertion in kernel/src/main.rs at line 5 [3.1937]

Insertion in kernel/src/main.rs at line 8 [3.1937]

Replacement in kernel/src/main.rs at line 12 [3.1937]

Replacement in kernel/src/main.rs at line 15 [3.1937]

Replacement in kernel/src/main.rs at line 24 [3.1937]

Replacement in kernel/src/main.rs at line 30 [3.1937]

Insertion in kernel/src/main.rs at line 33 [3.1937]

File addition: allocator.rs (----------)

Insertion in kernel/Cargo.toml at line 9 [3.2242]

Replacement in Cargo.lock at line 7 [3.2547]

Replacement in Cargo.lock at line 9 [3.2547]

Replacement in Cargo.lock at line 193 [3.2547]

Replacement in Cargo.lock at line 195 [3.2547]

Replacement in Cargo.lock at line 212 [3.2547]

Replacement in Cargo.lock at line 214 [3.2547]

Replacement in Cargo.lock at line 221 [3.2547]

Replacement in Cargo.lock at line 223 [3.2547]

Insertion in Cargo.lock at line 512 [3.2547]

Insertion in Cargo.lock at line 567 [3.2547]

Insertion in Cargo.lock at line 594 [3.2547]

Replacement in Cargo.lock at line 624 [3.2547]

Replacement in Cargo.lock at line 626 [3.2547]

Insertion in Cargo.lock at line 786 [3.2547]

Insertion in Cargo.lock at line 870 [3.2547]

Replacement in Cargo.lock at line 899 [3.2547]

Replacement in Cargo.lock at line 901 [3.2547]

Replacement in Cargo.lock at line 907 [3.2547]

Replacement in Cargo.lock at line 912 [3.2547]

Replacement in Cargo.lock at line 914 [3.2547]

Replacement in Cargo.lock at line 921 [3.2547]

Replacement in Cargo.lock at line 923 [3.2547]