Implement heap allocation

finchie

Dec 29, 2023, 5:38 PM

SCGTKLIL3L6BITCIP2PGKSCJD2XQ2LKQWN63SWQXSELVGVZYMI3AC

Dependencies

[2] QJPM62J2 Implement double-fault handling
[3] K5LGXRU2 Create simple kernel toolchain

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)
}
edit in kernel/src/main.rs at line 5

[2.32]

[2.32]

mod allocator;
edit in kernel/src/main.rs at line 8

[2.57]

[3.1961]

mod memory;
replacement in kernel/src/main.rs at line 12

[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.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.2071]→[3.2071:2125](∅→∅),[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.2140]→[2.72:84](∅→∅)

fn init() {

[3.2140]

[2.84]

fn init(boot_info: &'static mut BootInfo) {
edit in kernel/src/main.rs at line 33

[2.125]

[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(())
}
edit in kernel/Cargo.toml at line 9

[2.2393]

[2.2393]

linked_list_allocator = "0.10.5"
replacement in Cargo.lock at line 7

[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.2764]→[3.2764:2842](∅→∅)

checksum = "59d2a3357dde987206219e78ecfbbb6e8dad06cbb65292758d3270e6254f7355"

[3.2764]

[3.2842]

checksum = "c9d19de80eff169429ac1e9f48fffb163916b448a44e8e046186232046d9e1f9"
replacement in Cargo.lock at line 193

[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.7154]→[3.7154:7232](∅→∅)

checksum = "e092090f6e2b68cee8dc291ec60e4706f6b0c5cd90b666a5248a20f30591ccb0"

[3.7154]

[3.7232]

checksum = "0668e5a71825bbf8d9af46b68441e4426f070e7465b45070464977214dfada9e"
replacement in Cargo.lock at line 212

[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.7544]→[3.7544:7622](∅→∅)

checksum = "a36c0df7b26b44254828ece99ed72aa01695cc37f007a97afe8aee29feb26e3e"

[3.7544]

[3.7622]

checksum = "be20fe897a953c6f2e63d392ea067237af98d02cd15ef97a48fef2768c1ed269"
replacement in Cargo.lock at line 221

[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.7772]→[3.7772:7850](∅→∅)

checksum = "88f843888771a490c3ad246e58bf25e62da70d2c653d74a3eca92acbab599e02"

[3.7772]

[3.7850]

checksum = "daaa1fb791aea49e19db7b7b3662665d511eb4e30a0627fa525fd92652f39358"
edit in Cargo.lock at line 512

[2.2624]

[2.2624]

"linked_list_allocator",
edit in Cargo.lock at line 567

[3.16130]

[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]]
edit in Cargo.lock at line 594

[3.16719]

[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.17199]→[3.17199:17217](∅→∅)

version = "2.6.4"

[3.17199]

[3.17217]

version = "2.7.1"
replacement in Cargo.lock at line 626

[3.17282]→[3.17282:17360](∅→∅)

checksum = "f665ee40bc4a3c5590afb1e9677db74a508659dfd71e126420da8274909a0167"

[3.17282]

[3.17360]

checksum = "523dc4f511e55ab87b694dc30d0f820d60906ef06413f93d4d7a1385599cc149"
edit in Cargo.lock at line 786

[3.21250]

[3.21250]

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

[[package]]
edit in Cargo.lock at line 870

[2.3232]

[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.23529]→[3.23529:23547](∅→∅)

version = "3.8.1"

[3.23529]

[3.23547]

version = "3.9.0"
replacement in Cargo.lock at line 901

[3.23612]→[3.23612:23690](∅→∅)

checksum = "7ef1adac450ad7f4b3c28589471ade84f25f731a7a0fe30d71dfa9f60fd808e5"

[3.23612]

[3.23690]

checksum = "01ce4141aa927a6d1bd34a041795abd0db1cccba5d5f24b009f694bdf3a1f3fa"
replacement in Cargo.lock at line 907

[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.23831]→[3.23831:23850](∅→∅)

version = "1.0.51"

[3.23831]

[3.23850]

version = "1.0.52"
replacement in Cargo.lock at line 914

[3.23915]→[3.23915:23993](∅→∅)

checksum = "f11c217e1416d6f036b870f14e0413d480dbf28edbee1f877abaf0206af43bb7"

[3.23915]

[3.23993]

checksum = "83a48fd946b02c0a526b2e9481c8e2a17755e47039164a86c4070446e3a4614d"
replacement in Cargo.lock at line 921

[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.24152]→[3.24152:24230](∅→∅)

checksum = "01742297787513b79cf8e29d1056ede1313e2420b7b3b15d0a768b4921f549df"

[3.24152]

[3.24230]

checksum = "e7fbe9b594d6568a6a1443250a7e67d80b74e1e96f6d1715e1e21cc1888291d3"