Heap Allocation

[utterances-bot]

This is a general purpose comment thread for the Heap Allocation post.

[Mubelotix]

Thank you I was waiting this part !

[shakram02]

Hey Philipp, thank you for the great post ( as always ✌️ )

I wanted to note that I think now it's possible to move the allocator to its own module and out of lib.rs because of this PR.

Can't wait for your next tutorial!

[toothbrush7777777]

@phil-opp As @shakram02 noted, rust-lang/rust#62735 now makes it possible to define the global allocator in a submodule.

[phil-opp]

@shakram02 @toothbrush7777777 Thank you for reporting this and sorry for the late reply. I created #714 to move the #[global_allocator] into the allocator module in the post-10 branch and I will create a second pull request to update the blog text in a moment.

Edit: Blog update in #715.

[Menschenkindlein]

The comment in the first code block in https://os.phil-opp.com/heap-allocation/#the-global-allocator-attribute should be // in src/lib.rs.

[phil-opp]

@Menschenkindlein We recently moved the definition to the allocator module in #714. Try updating your Rust nightly if you get an error.

[Menschenkindlein]

I guess it doesn't need allocator:: then, does it?

[phil-opp]

Ah, good catch! Fixed in #728.

[GuillaumeDIDIER]

How do you handle memory allocation failure gracefully in here ? (If my users starts forkbombing I’d like to avoid crashing the kernel and instead tell the user nope, your fork is a spoon)

[phil-opp]

Currently the only way is to use the try_reserve method before appending to collections. I linked the method for Vec, but it also exists for the other collection types. These methods were introduced with the fallible collection allocation 1.0 RFC.

Alternatively, you could create your own alloc library that returns a result instead of panicking for all collection methods. Or, try to get unwinding working with your kernel so that you can catch the oom panic.

[GuillaumeDIDIER]

Going down the rabbit hole in stumbled onto https://github.com/vcombey/fallible_collections not sure if other such crate exist, but this looks like a reasonable thing to use, until hopefully the original alloc crate decides on how to play nice with people who need to handle memory allocation errors. (The ability to have the allocator specify an Error type with the default being ! would imho be very nice)

[phil-opp]

Going down the rabbit hole in stumbled onto https://github.com/vcombey/fallible_collections

Looks useful!

[…] until hopefully the original alloc crate decides on how to play nice with people who need to handle memory allocation errors. (The ability to have the allocator specify an Error type with the default being ! would imho be very nice)

I'm not aware of any proposals to change the global allocator, but there is the allocators working group that works on making collections parametrizable over the separate Alloc trait. The idea is that you can write Vec<T, MyAllocatorType> to make the Vec instance use a different allocator than the global allocator. There was also a discussion on an associated error type: rust-lang/wg-allocators#23.

[n-osborne]

Hello. First, thank you for this amazing tutorial. I really enjoy it.

I do have a build error when using the linked-list-allocator:

error[E0432]: unresolved import `alloc::alloc::AllocRef`

It seems that alloc does not have AllocRef module any more.

[phil-opp]

@n-osborne Thanks! The AllocRef trait was renamed from Alloc recently. Try updating your nightly Rust version to resolve the error.

[n-osborne]

@phil-opp Thanks, it works like a charm.

[toothbrush7777777]

Thanks for the great tutorials! I am wanting to expand, and was thinking about creating a basic shell (like you announced in edition-3), however kinda confused on how to implement something like that, like how to get a constant stream of key-strokes. Would you have any suggestions?

You should read https://os.phil-opp.com/async-await/ for an example.
A crate you can use is pc-keyboard.

[aos]

Hey @phil-opp thanks for the great tutorial. This is perhaps more of a Rust question, but I'm wondering why we still need to use extern crate alloc for the code to compile?

I see your statement here:

By adding this extern crate statement, we specify that the compiler should try to include it. (Historically, all dependencies needed an extern crate statement, which is now optional).

I thought with 2018 we don't need to specify extern crate..., but the code does not compile if we remove the extern crate alloc. Is there a reason why this is only specific to alloc? I saw this SO answer: https://stackoverflow.com/questions/37843379/is-it-possible-to-use-box-with-no-std but it says we don't need it for edition 2018, but that's not true in this case.

[bjorn3]

Cargo dependencies are added to the so called "implicit prelude" meaning that they can be accessed without extern crate. Many sysroot crates like alloc are not added to the implicit prelude and as such need extern crate.

[aos]

Got it -- thank you! For others wondering: https://doc.rust-lang.org/nightly/edition-guide/rust-2018/path-changes.html#no-more-extern-crate here's more information about this.

[MysticalUser]

Why can't we use PhysFrame::range instead of doing PhysFrame::range_inclusive and decrementing?

[bjorn3]

If you did do Page::containing_address(heap_start + HEAP_SIZE) then the result may be either the last page of the heap or the page after it. If it is the last page PhysFrame::range will give a too small range, but PhysFrame::range_inclusive would give one page too much in case Page::containing_address returned the page after the last page of the heap. Using Page::containing_address(heap_start + HEAP_SIZE - 1), you know that it will always return the last page of the heap and thus PhysFrame::range_inclusive will always return the exact right range. Not too small and not too big.

[MysticalUser]

Thank you!

[MysticalUser]

If you did do Page::containing_address(heap_start + HEAP_SIZE) then the result may be either the last page of the heap or the page after it.

Why?

[bjorn3]

heap_start + HEAP_SIZE is the byte after the end of the heap. If the heap ends at the last address of a page, Page::containing_address(heap_start + HEAP_SIZE) will thus return the page after the last page of the heap. heap_start + HEAP_SIZE - 1 on the other hand is the last byte of the heap. Page::containing_address(heap_start + HEAP_SIZE - 1) will this give the last page of the heap.

[MysticalUser]

Why is the partial sum function in large_vec written as (n - 1) * n / 2 while on the linked Wikipedia page it's written as (n + 1) * n / 2? And why is the for loop exclusive (i.e. 0..n instead of 0..=n)?

[bjorn3]

Why is the partial sum function in large_vec written as (n - 1) * n / 2 while on the linked Wikipedia page it's written as (n + 1) * n / 2?

Because it is starting the count from 0, while the wikipedia page starts from 1.

And why is the for loop exclusive (i.e. 0..n instead of 0..=n)?

If it would be an inclusive range, there would be 1001 elements, not 1000 as required for the formula to work.

[kennystrawnmusic]

Is there a way, by chance, to avoid deadlocking the Logger when crates like acpi for example are initialized like so? (Handler struct is inspired by snooping through the bootloader source code)

//snip

use acpi::{
    AcpiError, AcpiHandler, AcpiTables, HpetInfo, PciConfigRegions, PhysicalMapping,
    PlatformInfo, RsdpError,
};
use printk::LockedPrintk; // https://github.com/kennystrawnmusic/printk
use conquer_once::spin::OnceCell;
use spin::Mutex;
use crate::mem::frames::Falloc; // my custom name for the frame allocator in this tutorial
use x86_64::{
    structures::paging::{Mapper, Page, PageTableFlags, OffsetPageTable, PhysFrame, Size4KiB},
    PhysAddr, VirtAddr,
};
use bootloader::{BootInfo,entry_point};

//snip

pub static PRINTK: OnceCell<LockedPrintk> = OnceCell::uninit();
pub static MAPPER: OnceCell<Mutex<OffsetPageTable>> = OnceCell::uninit();
pub static FRAME_ALLOCATOR: OnceCell<Mutex<Falloc>> = OnceCell::uninit();

#[derive(Clone)]
pub struct KernelAcpi;

impl AcpiHandler for KernelAcpi {
    unsafe fn map_physical_region<T>(
        &self,
        physical_address: usize,
        size: usize,
    ) -> PhysicalMapping<Self, T> {
        let physical_mapping_frame = PhysFrame::<Size4KiB>::containing_address(PhysAddr::new(physical_address as u64));
        let physical_mapping_page = Page::<Size4KiB>::containing_address(VirtAddr::new(physical_address as u64));        

        let res = MAPPER.get().unwrap().lock().map_to(
            physical_mapping_page,
            physical_mapping_frame,
            PageTableFlags::PRESENT | PageTableFlags::WRITABLE,
            &mut *FRAME_ALLOCATOR.get().unwrap().lock(),
        );

        let mapped = match res {
            Ok(page) => page,
            Err(e) => panic!("Error mapping pages: {:#?}", e)
        };

        mapped.flush();

        PhysicalMapping::new(
            physical_address,
            NonNull::new((physical_address as usize) as *mut _).unwrap(), //page must exist
            size,
            size,
            Self,
        )
    }

    fn unmap_physical_region<T>(_region: &PhysicalMapping<Self, T>) {}
}

// snip

pub fn printk_init(buffer: &'static mut [u8], info: FrameBufferInfo) {
    let p = PRINTK.get_or_init(move || LockedPrintk::new(buffer, info));
    set_logger(p).expect("Logger has already been set!");
    set_max_level(LevelFilter::Trace);
    info!("Hello, Kernel!");
}

//snip

entry_point! maink;

fn maink(info: &'static mut BootInfo) -> ! {
    let buffer_optional = &mut _info.framebuffer;
    let buffer_option = buffer_optional.as_mut();
    let buffer = buffer_option.unwrap();
    let bi = buffer.info().clone();
    let raw_buffer = buffer.buffer_mut();

    printk_init(raw_buffer, bi);

    //snip

    let offset = VirtAddr::new(_info.physical_memory_offset.clone().into_option().unwrap());
    let map = unsafe { map_memory(offset) };
    let falloc = unsafe { Falloc::new(&_info.memory_regions) };

    MAPPER.get_or_init(move || Mutex::new(map));
    FRAME_ALLOCATOR.get_or_init(move || Mutex::new(falloc));

    crate::mem::heap_init(
        &mut *MAPPER.get().unwrap().lock(),
        &mut *FRAME_ALLOCATOR.get().unwrap().lock(),
    )
    .unwrap_or_else(|e| error!("Failed to map{:#?}", e));

    let rsdp = info.rsdp_addr.clone().into_option().unwrap();
    let tables = unsafe { AcpiTables::from_rsdp(KernelAcpi, rsdp as usize).unwrap() };

    info!(
        "Interrupt model: {:#?}",
        tables.platform_info().unwrap().interrupt_model
    );
    //snip
}

The last info! line for debugging the interrupt model is never logged (likely indicating a deadlock), despite the logger having been initialized the whole time. If it is a deadlock, why would it be happening given the sheer separation between the locked heap and the framebuffer addresses, and is there any other way to allow for global access to the frame allocator by code that desperately needs it to avoid page-faulting (the ACPI handler implementation is of course a case-in-point on this) without blocking? And I tried using Box::into_raw to map the virtual ACPI handler address onto the heap directly; that didn't work either (identical outcome).

[kennystrawnmusic]

Documentation on how to set up GDB for newer editions than Edition 1 (what the sole related tutorial I could find on this site seems geared towards, given that it assumes you're using Multiboot and Makefiles instead of the bootloader crate) would be sorely needed at this point.

I was, meanwhile, able to get the cfg! macro to work for specifying UEFI vs BIOS through some target-JSON hacks and slight helper crate refactoring, which got rid of the problem before with discrepancies between BIOS and UEFI behavior, which is why I deleted that comment.

[kennystrawnmusic]

Ended up using -d in_asm,out_asm to effectively disassemble the whole thing with QEMU while it’s running — going to have to narrow this down further though to figure out where exactly the problem is. Whatever is writing that sneaky 3 into a field that should be 0 is very hard to find.

[Freax13]

Does the panic handler need to return something for GDB to recognize it, or is it just a QEMU bug?

Nope, AFAIK there's not way for the virtual machine to tell QEMU that a panic occured. This is not a bug in QEMU or gdb, that's just the way it is. What I usually do is put and endless loop inside the panic handler instead of requesting a shutdown. That way you can wait for the panic and then pause the VM with ctrl+C in gdb. Once you've done that, you should be able to use the backtrace command in gdb.

[kennystrawnmusic]

Does the panic handler need to return something for GDB to recognize it, or is it just a QEMU bug?

What I usually do is put and endless loop inside the panic handler instead of requesting a shutdown.

That's what I do too but I wasn't aware of the Ctrl-C trick. Thanks, trying that next.

[kennystrawnmusic]

Finally figured out what the problem was ― see kwzhao/x2apic-rs#11 for details.

[kennystrawnmusic]

So, for those who are also looking to use this tutorial to get the ACPI tables parsed, here's the code that worked on my end:

// snip
use acpi::{
    AcpiError, AcpiHandler, AcpiTables, HpetInfo, InterruptModel, PciConfigRegions,
    PhysicalMapping, PlatformInfo, RsdpError,
};
use conquer_once::spin::OnceCell;

// snip
pub static PHYS_OFFSET: OnceCell<u64> = OnceCell::uninit();

// snip
#[derive(Clone)]
pub struct KernelAcpi;

impl AcpiHandler for KernelAcpi {
    unsafe fn map_physical_region<T>(
        &self,
        physical_address: usize,
        size: usize,
    ) -> PhysicalMapping<Self, T> {
        let physical_mapping_page = Page::<Size4KiB>::containing_address(VirtAddr::new(
            (physical_address + PHYS_OFFSET.get().unwrap().clone() as usize) as u64,
        ));

        let page_size = physical_mapping_page.size() as usize;

        //round to nearest page/frame size
        let page_padded = ((size - 1) / page_size + 1) * page_size;

        PhysicalMapping::new(
            physical_address,
            NonNull::new(
                (physical_address + PHYS_OFFSET.get().unwrap().clone() as usize) as *mut _,
            )
            .unwrap(), //page must exist
            size,
            page_padded,
            Self,
        )
    }

    fn unmap_physical_region<T>(_region: &PhysicalMapping<Self, T>) {}
}

// snip
entry_point!(maink);

fn maink(system_info: &'static mut BootInfo) -> ! {
    // snip
    let cloned_offset = system_info
        .physical_memory_offset
        .clone()
        .into_option()
        .unwrap();
    PHYS_OFFSET.get_or_init(move || cloned_offset);
    // snip
}

Takes a lot of working around stumbling blocks, that's for sure.

[ChocolateLoverRaj]

This example made me realize that there was no need to actually create a mapping if the entire physical memory is mapped at a offset. Nice.

[ChocolateLoverRaj]

Also this worked, which is an even easier solution:

use core::ptr::NonNull;

use acpi::{AcpiHandler, AcpiTables};
use x86_64::VirtAddr;

#[derive(Clone, Debug)]
struct OffsetMapAcpiHandler {
    phys_map_offset: VirtAddr,
}

impl AcpiHandler for OffsetMapAcpiHandler {
    unsafe fn map_physical_region<T>(
        &self,
        physical_address: usize,
        size: usize,
    ) -> acpi::PhysicalMapping<Self, T> {
        acpi::PhysicalMapping::new(
            physical_address,
            NonNull::new((self.phys_map_offset + physical_address as u64).as_mut_ptr::<T>())
                .unwrap(), //page must exist
            size,
            size,
            self.clone(),
        )
    }

    fn unmap_physical_region<T>(_region: &acpi::PhysicalMapping<Self, T>) {}
}

pub fn init_apic(rsdp_addr: usize, phys_map_offset: VirtAddr) {
    log::info!("RSDP: {:?}", rsdp_addr);
    let acpi_tables =
        unsafe { AcpiTables::from_rsdp(OffsetMapAcpiHandler { phys_map_offset }, rsdp_addr) };
    log::info!("ACPI Tables: {:#?}", acpi_tables);
}

[kennystrawnmusic]

[kennystrawnmusic]

Update: worked fine after I decided to map it to the start address of a test page. Still not detecting anything though.

[kennystrawnmusic]

Does anyone know what to plug into acpi::PciConfigRegions::physical_address() to look for a SATA/AHCI controller? Tried all of the following to no avail:

physical_address(0x0, 0x1, 0x6, 0x0) // 8086:29c0
physical_address(0x0, 0x1, 0x6, 0x1) // 8086:29c0
physical_address(0x0, 0x1, 0x6, 0x2) // 8086:29c0
physical_address(0x1, 0x6, 0x0, 0x0) // None
physical_address(0x1, 0x6, 0x1, 0x0) // None
physical_address(0x1, 0x6, 0x2, 0x0) // None

In all of those attempts the only pieces of hardware I was able to find were memory controllers and host bridges, despite the official documentation clearly stating that a device class of 0x1 and subclass of 0x6 is the standard for AHCI controllers. So what other possibilities are there? Are the devices and classes meant to be plugged into that function and if not, what is? Pinging @IsaacWoods since he's that crate's largest contributor.

[kennystrawnmusic]

Alright, after using objdump to debug this further, it seems depending on redox_syscall for an in-kernel operation is the problem — attempts to use Mmio<T> and Dma<T> from that crate are to trying to send a system call instruction from inside the kernel itself.

So, next up on the todo!() list: define new Mmio<T> andDma<T> structures that use my own page-mapping macros instead of the ones the Redox team exported to that crate. Then it should work properly.

Edit: Opened kennystrawnmusic/cryptos#1 as a personal reminder.

[kennystrawnmusic]

@IsaacWoods Unrelated but if you were wondering how I was planning on getting those interrupt pins properly routed: kennystrawnmusic/cryptos@b5abbb6

[kennystrawnmusic]

Decided as a bit of a side project to compile a database of real hardware I've run acpi-dumper on. Should make the process of actually supporting real hardware much easier.

[kennystrawnmusic]

In case anyone thinks the description of kennystrawnmusic/cryptos#1 reveals too little information, this is what I was able to trace the #UD back to. Throwing a SYS_PHYSMAP system call doesn't work if you are the kernel that's supposed to catch and handle it.

[kennystrawnmusic]

Was finally able to get rid of the #UD by defining my own Dma<T> and PageBox<T> structures but still not getting any feedback, suggesting possible page misalignment — any ideas as to why? Could probably figure it out on my own, but seems a bit odd given the striking similarities to a known working driver.

[nintendaii]

Hey. I am currently following the 10 post but I have run into some troubles. When I try to compile my project with linked_list_allocator crate I got a compile error. The weird thing is that in my cargo.toml file I stated the 0.9.0 version, but on the screenshot I attached it actually compiles the 0.9.1 version. Probably I have some mismatching in the versions of my crates. The rustc version I use isrustc 1.59.0-nightly (23f69235a 2021-12-20)

[bjorn3]

The rustc version I use isrustc 1.59.0-nightly (23f69235a 2021-12-20)

Your rustc version is almost a year old. You will need to use a much newer nightly.

The weird thing is that in my cargo.toml file I stated the 0.9.0 version, but on the screenshot I attached it actually compiles the 0.9.1 version.

Cargo will pick the latest semver compatible version if there is no entry in Cargo.lock yet. In this case 0.9.1.

[nintendaii]

After I updated to the rustc 1.67.0-nightly (c1a859b25 2022-11-10) I have errors related to llvm_asm. Probably, I am using old version of bootloader (`0.9.8`). Which version of bootloader should I use?

[nintendaii]

Sry, wrong screenshot

[bjorn3]

Try bootloader 0.9.23. cargo update -p bootloader should do the trick.

[nintendaii]

yep, it helped. thanks a lot👌

[Kangaxx-0]

In the first figure of section Local Variables, why i=1 is pushed before return address ? Shouldn't the return address be pushed first ?

The Interrupt Stack Frame also calls this out

On a normal function call (using the call instruction), the CPU pushes the return address before jumping to the target function. On function return (using the ret instruction), the CPU pops this return address and jumps to it. So the stack frame of a normal function call looks like this:

[bjorn3]

i is an argument which needs to be pushed before calling inner. As calling inner pushes the return address i has to be pushed before the return address.

[danhunsaker]

When trying to run the tests at the end of this post, I get the following error:

the trait `FrameAllocator<x86_64::structures::paging::Size4KiB>` is not implemented for `BootInfoFrameAllocator`

I get that the fix is to implement the trait, but it might be useful to do so in the blog, too. Especially since we probably need to implement the other two sizes as well.

[Th3F0x-code]

i was trying to implement the heap and ended up with this error. does anyone know how to solve it?
rust version: nightly-aarch64-apple-darwin - Up to date : 1.77.0-nightly (88189a71e 2024-01-19)
panicked at /Users/alessio/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/r ustlib/src/rust/library/alloc/src/alloc.rs:418:13: memory allocation of 4 bytes failed

[Freax13]

This error occurs when the GlobalAlloc implementation returns a null pointer (indicating that allocation failed). You've likely either run out of memory or your GlobalAlloc implementation is buggy.

[Th3F0x-code]

this is my code:

unsafe impl GlobalAlloc for Dummy {
    unsafe fn alloc(&self, _layout: Layout) -> *mut u8 {
        null_mut()
    }

    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
        panic!("dealloc should be never called")
    }
}

I can't understand why I get that error instead of:

panicked at 'allocation error: Layout & size_: 4, align_: 4}', src/lib.rs: 89:5

[AtomicGamer9523]

null_mut returns a null pointer, which isn't allowed. That's why you get the panic.

Edit: And the reason that it panics in alloc is because that is where the methods get invoked (internally)

Edit2: Seems to be related to this:

418: core::panicking::panic_nounwind_fmt(
419:     format_args!("memory allocation of {size} bytes failed"),
420:     /* force_no_backtrace */ false,
421: )

[Freax13]

TL;DR: The error message doesn't matter much. You can move on without getting the error message to match the screenshot from the post.

An older blog post version used an attribute macro called alloc_error_handler. This attribute could be set on a function that would be called every time an allocation error occurs. This is where the panic message you saw in the screenshot comes from. alloc_error_handler used to be required but is no longer required. At some point in time, it was removed from Rust and so it was also removed from the post in #1216. (The removal of alloc_error_handler was reverted, though it's planned to remove it again, so it's probably not worth starting to use it now).

[Redskaber]

linked_list_allocator vulnerable to out-of-bound writes on Heap initialization and Heap::extend High, Can you recommend some secure heap allocators? Thank you

[tsatke]

Assuming that this is what you're referring to. It states that Patched Versions: 0.10.2. The latest published version is 0.10.5, so we should be good here.

[Redskaber]

thanks for your reminder.

[strood]

For those who may run into same thing after me. I found I was getting an unsafe impl for safe trait rust-analyzer error when trying to impl GlobalAlloc in the allocator.rs (or later in the custom allocator implementations), but if I didnt mark as unsafe I got the inverse error of add 'unsafe' to this trait implementation: 'unsafe'

Fixed by changing the GlobalAlloc import from:
use alloc::alloc::{Layout, GlobalAlloc};
^like in the notes, to its own input from core like below:
use core::alloc::GlobalAlloc;
^ this resolved my issues

[ChocolateLoverRaj]

Is there a way of knowing which virtual address ranges are already being used? So instead of doing

pub const HEAP_START: usize = 0x_4444_4444_0000;
pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB

the available virtual addresses usable for dynamic allocation could be figured out at runtime.

[tsatke]

Generally speaking - it's your kernel, you decide what addresses to use. (very simply put) your heap happens before anything uses virtual addresses (with the exception of the stuff that the boot loader maps for you, but you get that info through the BootInfo struct). You are free to use 0x0000_0000_0000_0000 up to 0xFFFF_FFFF_FFFF_FFFF as you please (with some limitations of the processor of course - canonical addresses etc).

You can keep track of used virtual memory manually, but when you init your heap, that will probably always be the same address.

To actually answer the question:
You can iterate through the page tables and check for the PRESENT flag. Once you have a decent amount of memory allocated, this will be noticeably slow.

[ChocolateLoverRaj]

Thanks for the answer.

Here is what I did:

use core::ops::Range;
use x86_64::{
    structures::paging::{
        page_table::FrameError, PageOffset, PageSize, PageTable, PageTableIndex, Size1GiB,
        Size2MiB, Size4KiB,
    },
    VirtAddr,
};

use crate::virt_addr_from_indexes::{
    virt_addr_from_indexes_1_gib, virt_addr_from_indexes_2_mib, virt_addr_from_indexes_4_kib,
};

pub fn find_used_virt_addrs<const N: usize>(
    l4_page_table: &PageTable,
    phys_mem_offset: VirtAddr,
) -> heapless::Vec<Range<VirtAddr>, N> {
    // We keep this sorted, and we assume that there are no overlaps (because that is unsafe and should never happen)
    let mut ranges = heapless::Vec::<Range<VirtAddr>, N>::new();
    // We assume that this function is being called in an increasing way (0..2, 2..4, 10..16), not (10..16, 1..2)
    let mut add_range = |range: Range<VirtAddr>| match ranges.last_mut() {
        Some(last_range) => {
            if last_range.end == range.start {
                last_range.end = range.end;
            } else {
                ranges.push(range).unwrap();
            }
        }
        None => {
            ranges.push(range).unwrap();
        }
    };
    for (l4_index, entry) in l4_page_table.iter().enumerate() {
        match entry.frame() {
            Ok(frame) => {
                let virt_frame_addr = phys_mem_offset + frame.start_address().as_u64();
                let l3_table_ptr: *const PageTable = virt_frame_addr.as_ptr();
                let l3_table = unsafe { &*l3_table_ptr };
                for (l3_index, entry) in l3_table.iter().enumerate() {
                    match entry.frame() {
                        Ok(frame) => {
                            let virt_frame_addr = phys_mem_offset + frame.start_address().as_u64();
                            let l2_table_ptr: *const PageTable = virt_frame_addr.as_ptr();
                            let l2_table = unsafe { &*l2_table_ptr };
                            for (l2_index, entry) in l2_table.iter().enumerate() {
                                match entry.frame() {
                                    Ok(frame) => {
                                        let virt_frame_addr =
                                            phys_mem_offset + frame.start_address().as_u64();
                                        let l1_table_ptr: *const PageTable =
                                            virt_frame_addr.as_ptr();
                                        let l1_table = unsafe { &*l1_table_ptr };
                                        for (l1_index, entry) in l1_table.iter().enumerate() {
                                            if !entry.is_unused() {
                                                add_range({
                                                    let start_addr = virt_addr_from_indexes_4_kib(
                                                        PageTableIndex::new(l4_index as u16),
                                                        PageTableIndex::new(l3_index as u16),
                                                        PageTableIndex::new(l2_index as u16),
                                                        PageTableIndex::new(l1_index as u16),
                                                        PageOffset::new(0),
                                                    );
                                                    Range {
                                                        start: start_addr,
                                                        end: start_addr + Size4KiB::SIZE,
                                                    }
                                                });
                                            }
                                        }
                                    }
                                    Err(FrameError::FrameNotPresent) => {}
                                    Err(FrameError::HugeFrame) => {
                                        add_range({
                                            let start_addr = virt_addr_from_indexes_2_mib(
                                                PageTableIndex::new(l4_index as u16),
                                                PageTableIndex::new(l3_index as u16),
                                                PageTableIndex::new(l2_index as u16),
                                                0,
                                            );
                                            Range {
                                                start: start_addr,
                                                end: start_addr + Size2MiB::SIZE,
                                            }
                                        });
                                    }
                                }
                            }
                        }
                        Err(FrameError::FrameNotPresent) => {}
                        Err(FrameError::HugeFrame) => add_range({
                            let start_addr = virt_addr_from_indexes_1_gib(
                                PageTableIndex::new(l4_index as u16),
                                PageTableIndex::new(l3_index as u16),
                                0,
                            );
                            Range {
                                start: start_addr,
                                end: start_addr + Size1GiB::SIZE,
                            }
                        }),
                    }
                }
            }
            Err(FrameError::FrameNotPresent) => {}
            Err(FrameError::HugeFrame) => {
                panic!("An L4 page table entry was a huge. This is not allowed.")
            }
        }
    }
    ranges
}

In main.rs:

    let ranges = find_used_virt_addrs::<512>(mapper.level_4_table(), phys_mem_offset);
    log::info!("Virtual address ranges: {:?}", ranges);
    let total_virt_addresses_used: u64 = ranges.iter().map(|range| range.end - range.start).sum();
    log::info!("Total virt addresses used: {}", total_virt_addresses_used);

Which results in

So before I modify the page tables, I can read the L4 table to get which virtual address ranges are already used, and then I can edit the list of used ranges as I modify page tables without reading the entire L4 table again.

[tsatke]

Well done!

Keep the following points in mind when you expand on this.

• mapped pages may alias physical memory (which contradicts your first assumption)
• virtual memory may not be mapped but reserved (page swapping for example, where you map on demand with the help of your page fault handler)
• with enough memory that is fragmented enough, you'll run out of kernel stack with the heapless vec (be sure to map a guard page)
• that one vec you get is only valid for a single value in Cr3

[ChocolateLoverRaj]

mapped pages may alias physical memory (which contradicts your first assumption)

I'm not sure what you mean. For a single value in Cr3, I thought it's impossible for more than one page table entry to include a virtual address.

with enough memory that is fragmented enough, you'll run out of kernel stack with the heapless vec (be sure to map a guard page)

I think the heapless vec reserves its entire capacity on the stack (if used as a local variable) when calling new. If there are >512 different ranges, the function will panic since pushing to a full heapless vec just panics.

[tsatke]

1. You are correct. But two distinct virtual addresses may translate to the same physical address.

2. You are correct. But the compiler won't stop you to create a Vec<T, 65536>, which could not panic and just overflow the stack. Those things are really difficult to debug, because they might corrupt seemingly unrelated memory.

Regarding the fragmented stuff I mentioned - I've noticed your optimization that you keep extending the last range instead of creating a new one when the next piece of memory starts where the last one stopped. So as long as you only have one segment mapped, your vec only contains one element. So really fragmented memory will make the amount of ranges in the vec grow.