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.

[phil-opp]

@dalnefre Sorry, your comment somehow slipped through my notifications. You're completely right, the method should be removed from the code of the subsequent posts. I fixed this in 3a230d0. Thanks for reporting!

[nanoadam]

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?

Or maybe ideas on how to expand on these posts? Challenges? Thanks!

[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.

[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.