Memory manager

[ethindp]

So, I have a paging frame allocator, as the guide prompted (with my own modifications), but it looks similar. Here's what it is:

use x86_64::registers::control::*;
use bootloader::bootinfo::*;
use x86_64::{structures::paging::{FrameAllocator, MappedPageTable, Mapper, MapperAllSizes, Page, PageTable, PhysFrame, Size4KiB}, PhysAddr, VirtAddr};

pub unsafe fn init(physical_memory_offset: u64) -> impl MapperAllSizes {
let (level_4_table, _) = get_active_l4_table(physical_memory_offset);
let phys_to_virt = move |frame: PhysFrame| -> *mut PageTable {
let phys = frame.start_address().as_u64();
let virt = VirtAddr::new(phys + physical_memory_offset);
virt.as_mut_ptr()
    };
MappedPageTable::new(level_4_table, phys_to_virt)
}

pub unsafe fn get_active_l4_table(physical_memory_offset: u64)->(&'static mut PageTable, Cr3Flags) {
use x86_64::VirtAddr;
let (table_frame, flags) = Cr3::read();
let phys = table_frame.start_address();
let virt = VirtAddr::new(phys.as_u64() + physical_memory_offset);
let page_table_ptr: *mut PageTable = virt.as_mut_ptr();
(&mut *page_table_ptr, flags)
}

pub struct GlobalFrameAllocator {
memory_map: &'static MemoryMap,
next: usize,
}

impl GlobalFrameAllocator {
pub unsafe fn init (memory_map: &'static MemoryMap)->Self {
GlobalFrameAllocator {
memory_map,
next: 0,
}
}

fn iter_usable_frames(&self) -> impl Iterator<Item = PhysFrame> {
let regions = self.memory_map.iter();
let usable_regions = regions.filter(| region | region.region_type == MemoryRegionType::Usable);
let address_ranges = usable_regions.map(| region | region.range.start_addr() .. region.range.end_addr());
let frame_addresses = address_ranges.flat_map(| region | region.step_by(4096));
frame_addresses.map(| address | PhysFrame::containing_address(PhysAddr::new(address)))
}
}

unsafe impl FrameAllocator<Size4KiB> for GlobalFrameAllocator {
fn allocate_frame(&mut self)->Option<PhysFrame> {
let frame = self.iter_usable_frames().nth(self.next);
self.next += 1;
frame
}
}

How would I write a frame deallocator that works with this? I know how to allocate frames but how do I free them? Do I just use the x86_64 crate and clear the page, then set its unused flag?
Also, how would I go about implementing a heap/memory manager while I wait for the new post to come out? I can't find any memory manager that works with Rust that doesn't require some kind of host OS, and to do anything else (i.e. get keyboard input and store it in a buffer and so on) requires a memory manager or some way of allocating and freeing memory, something I don't have and am not sure how to code. Porting a memory manager would probably be a pain since (if I'm not mistaken) all the memory managers' source code out there requires an existnig host OS with frame freeing and all that, as well as a heap.

[phil-opp]

How would I write a frame deallocator that works with this? I know how to allocate frames but how do I free them? Do I just use the x86_64 crate and clear the page, then set its unused flag?

You can use the Mapper::unmap method to remove a mapping from the page tables. If successful, the function returns the PhysFrame that the page was mapped to. Is that what you meant?

Also, how would I go about implementing a heap/memory manager while I wait for the new post to come out?

You can read the draft of the upcoming post here. It already explains Rust's allocator API and how to set up the alloc crate. It doesn't explain how to construct an allocator yet, but I try to add it soon.

Update: I just finished the first draft of the bump allocation section.

I can't find any memory manager that works with Rust that doesn't require some kind of host OS

Try linked-list-allocator, it is an allocator designed for embedded. There's also the more advanced tlsf (I haven't tried it yet). Another option is to search for "buddy allocator" (a common kernel-level allocator design) on crates.io or look for allocators for the WASM ecosystem.

Porting a memory manager would probably be a pain since (if I'm not mistaken) all the memory managers' source code out there requires an existnig host OS with frame freeing and all that, as well as a heap.

Yeah, you typically use different allocator designs in the kernel that are much simpler. So porting an userspace allocator isn't the way to go in my opinion.

---

I hope this helps! Let me know if you have any more questions.

[ethindp]

OK... so I found a buddy system allocator (ironically, its called buddy_system_allocator) and have slipped that into my kernel as rusts default allocator. Here's my issues.

1. I'm not really "mapping" pages by this point. I don't know if I have to or not, or what I should map. The mapper initialization code is there but I'm not mapping anything with it (should I do this?).
2. I'm attempting to "scan" (iterate) over the bootloaders provided memory map with the buddy_system_allocator. That allocator crate contains a LockedFrameallocator and a LockedHeap that (I believe) both qualify as possible rust memory allocators. Issue: you can't have two rust memory allocators simultaneously active, I don't think. So what I've done instead is something like this:

// in src/main.rs
#[global_allocator]
static allocator: LockedHeap = LockedHeap::empty();

And in my main code, I do this:

for region in boot_info.memory_map.iter() {
if region.region_type == MemoryRegionType::Usable {
unsafe {
allocator.lock().add_to_heap(region.range.start_addr() as usize, region.range.end_addr() as usize);
}
}
}

The reason I do the type cast is because this function takes an "usize" as parameter, not u64. This naturally causes a page fault:

Loading kernel
Configuring heap
Page fault: Protection violation
Caused by read from memory address VirtAddr(0x27c000) in supervisor mode
CPU reports that PF was caused by reserved read of bit 1 from PTT entry

This, of course, isn't very helpful. So if I request it to dump the stack frame, I get this (slightly) more useful message:

Loading kernel
Configuring heap
Page fault: Protection violation
Caused by read from memory address VirtAddr(0x27c000) in supervisor mode
CPU reports that PF was caused by reserved read of bit 1 from PTT entry
Error code: PROTECTION_VIOLATION | MALFORMED_TABLE | INSTRUCTION_FETCH, stack frame: InterruptStackFrame {
    instruction_pointer: VirtAddr(0x2191b9),
    code_segment: 8,
    cpu_flags: 0x206,
    stack_pointer: VirtAddr(0x57ac001ff860),
    stack_segment: 0,
}

And...
Update: I solved the problem! For future people having this problem, the key is to add the physical memory offset to the start and end range of usable memory regions. So this code:

for region in boot_info.memory_map.iter() {
if region.region_type == MemoryRegionType::Usable {
unsafe {
ALLOCATOR.lock().add_to_heap((boot_info.physical_memory_offset+region.range.start_addr()) as usize, (boot_info.physical_memory_offset+region.range.end_addr()) as usize);
}
}
}

Also, adding a memory allocator to the crate (along with a heap) is far simpler this way. I'll outline the steps below.

1. Add the crate buddy_system_allocator to your OS crate, with the feature "use_spin" on. So your dependency sould look something like buddy_system_allocator = {version="*", features=["use_spin"]}.
2. In your main crate, before rust 1.36 or so, you had to add, to yoru crates attributes, #![feature(alloc)]. According to the rust compiler, "the feature alloc has been stable since 1.36.0 and no longer requires an attribute to enable". So you don't need that. What you do need to add is the alloc_error_handler feature (#![feature(alloc_error_handler)].
3. Import the crate:

use buddy_system_allocator::*;

4. Set the allocator as your default:

#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();

What this does is set the global memory allocator that the rust (and the stdlib later on) will use as its default. It may or may not be your system allocator, but it will be your kernel allocator. The ::empty() method sets up the allocator and ensures it has nothing in it so we can populate it.
5. In your kernel_main() function, or whatever you called your main function via entry_point!(), add the following, somewhere after interrupts are initialized (if you do this improperly you'll cause a triple fault):

for region in boot_info.memory_map.iter() {
if region.region_type == MemoryRegionType::Usable {
unsafe {
ALLOCATOR.lock().add_to_heap((boot_info.physical_memory_offset+region.range.start_addr()) as usize, (boot_info.physical_memory_offset+region.range.end_addr()) as usize);
}
}
}

This loops through the memory map provided by the bootloader and loads it into the buddy system allocator, making your system memory available to the heap. I do not believe, however, that this makes your "pages" available.
6. We're still missing one more thing -- the "alloc_error_handler". Try to compile your kernel now -- rust won't like you. This is because rust has no way of reporting memory allocation failures! You need to know somehow, right? For mine, I did this, at the bottom of my main.rs:

#[alloc_error_handler]
fn handle_alloc_failure(layout: core::alloc::Layout) -> ! {
panic!("Cannot allocate memory of min. size {} and min. alignment of {}", layout.size(), layout.align())
}

This is primitive but effective. Try compiling your kernel and see if it page faults. It should not.
7. Try allocating something! Go to the top of your kernel and add:

extern crate alloc;

Hello, DMA! Let's allocate a vec, shall we?

use alloc::vec::Vec;
let mut v = Vec::new();
v.push(1);
v.push(2);
v.push(3);

Test that and see if you can print it! You've now got a memory allocator, albeit one that ignors your frame allocator completely. (I don't know how safe this is,and I don't know if it will clean up after itself or whether we still need to use the paging frame allocator.)

This brings me back to one of my other problems -- how do I safely handle page faults? The OSDev wiki says:

Page Faults
A page fault exception is caused when a process is seeking to access an area of virtual memory that is not mapped to any physical memory, when a write is attempted on a read-only page, when accessing a PTE or PDE with the reserved bit or when permissions are inadequate.
Handling
The CPU pushes an error code on the stack before firing a page fault exception. The error code must be analyzed by the exception handler to determine how to handle the exception. The bottom 3 bits of the exception code are the only ones used, bits 3-31 are reserved.
Bit 0 (P) is the Present flag.
Bit 1 (R/W) is the Read/Write flag.
Bit 2 (U/S) is the User/Supervisor flag.
The combination of these flags specify the details of the page fault and indicate what action to take:
US RW  P - Description
0  0  0 - Supervisory process tried to read a non-present page entry
0  0  1 - Supervisory process tried to read a page and caused a protection fault
0  1  0 - Supervisory process tried to write to a non-present page entry
0  1  1 - Supervisory process tried to write a page and caused a protection fault
1  0  0 - User process tried to read a non-present page entry
1  0  1 - User process tried to read a page and caused a protection fault
1  1  0 - User process tried to write to a non-present page entry
1  1  1 - User process tried to write a page and caused a protection fault
When the CPU fires a page-not-present exception the CR2 register is populated with the linear address that caused the exception. The upper 10 bits specify the page directory entry (PDE) and the middle 10 bits specify the page table entry (PTE). First check the PDE and see if it's present bit is set, if not setup a page table and point the PDE to the base address of the page table, set the present bit and iretd. If the PDE is present then the present bit of the PTE will be cleared. You'll need to map some physical memory to the page table, set the present bit and then iretd to continue processing.

I'm not really sure how to do this in rust? Could someone help me out with that part?

[ethindp]

Update: OK, so this issue isn't solved. I can get a temporary allocator working, but that's only if I increase the memory limit to 16 GB in QEMU the buddy system allocator throws an error and panics because the overall amount of indexes in the list of free blocks grows beyond 32. So I'm not really sure what to do.
Questions, if someone could help:

1. if I manually implement the allocator trait, do I map a page of memory to a frame given to me by the frame allocator in the alloc() function of that trait?
2. Would I then unmap the page when its released by calling dealloc()?
   I might be missing something, I don't know. I'll poke in the code again, but would love guidance.

[phil-opp]

Update: I solved the problem! For future people having this problem, the key is to add the physical memory offset to the start and end range of usable memory regions.

While this works, I wouldn't recommend this approach. Instead, try creating a separate virtual heap memory area and mapping it:

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


pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError> {
    let page_range = {
        let heap_start = VirtAddr::new(HEAP_START as u64);
        let heap_end = heap_start + HEAP_SIZE - 1u64;
        let heap_start_page = Page::containing_address(heap_start);
        let heap_end_page = Page::containing_address(heap_end);
        Page::range_inclusive(heap_start_page, heap_end_page)
    };

    for page in page_range {
        let frame = frame_allocator
            .allocate_frame()
            .ok_or(MapToError::FrameAllocationFailed)?;
        let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
        unsafe { mapper.map_to(page, frame, flags, frame_allocator)?.flush() };
    }

    unsafe {
        super::ALLOCATOR.inner.lock().init(HEAP_START, HEAP_SIZE);
    }

    Ok(())
}

This brings me back to one of my other problems -- how do I safely handle page faults? The OSDev wiki says: […] I'm not really sure how to do this in rust?

The page fault error code gets passed a PageFaultErrorCode argument, which contains exactly this information. Unfortunately, there is still issue rust-lang/rust#57270, which causes invalid error codes in some situations.

Questions, if someone could help:

The simplest solution is to map the complete heap up front, as shown in the code example above. On alloc and dealloc, you only keep track of which parts are used and free, but do not map/unmap anything. (It's possible to dynamically grow the heap when it runs out of memory by mapping new pages, but I wouldn't recommend this for kernel code.)

OK, so this issue isn't solved. I can get a temporary allocator working, but that's only if I increase the memory limit to 16 GB in QEMU the buddy system allocator throws an error and panics because the overall amount of indexes in the list of free blocks grows beyond 32.

I don't know anything about the buddy allocator crate, but you could try the linked-list-allocator crate instead. It is used by Redox and some embedded projects and shouldn't have such issues.

[ethindp]

I'll try this (I've switched to using the slab allocator that Redox has up on their github repo). The allocator requires that the "Heap size should be a multiple of minimum heap size". That's hardcoded to:

pub const NUM_OF_SLABS: usize = 8;
pub const MIN_SLAB_SIZE: usize = 4096;
pub const MIN_HEAP_SIZE: usize = NUM_OF_SLABS * MIN_SLAB_SIZE;

So, I could calculate the right page by using something like heap_size % 32768. The difficulty is locating a small page -- I would like it if the kernel operated in a tiny memory page (max should be 2-5 MB) so that it takes up as little RAM as possible to leave room for as many usermode programs as needed.

[phil-opp]

AFAIK, the Redox kernel allocator is automatically growing, which makes things a bit more complicated. Also, the slab allocator uses the linked-list-allocator in the background if I remember correctly.

[ethindp]

I don't think it auto-grows; I remember there being a function to grow it that was pub... so I don't know why it would auto-grow. That wouldn't make any sense.

[phil-opp]

Seems like the slab allocator doesn't auto grow. The default linked list allocator, however, does: https://github.com/redox-os/kernel/blob/78e79fc4d629069a65c1b7c8f65231953db6c99c/src/allocator/linked_list.rs#L28-L42

[ethindp]

Yeah, it does use the linked list allocator. Not sure of any way of turning the auto-growing feature off, unfortunately. If it amkes things more complex, I can probably live with it if its not ridiculously so. :)

[ethindp]

I meant make (git hub is not allowing me to edit my comments for some reason :()

[phil-opp]

The linked list allocator itself doesn't do any auto-growing, just the linked list module of redox. So you should be fine

[ethindp]

Oh. Good to know.

[ethindp]

Trying to use your code in any way gives me "error[E0107]: wrong number of type arguments: expected 2, found 1". I'm passing it my frame allocator and mapper that I initialized and its still complaining, not sure what I'm doing wrong. (Other han the fact that I'm obviously bad at generic types in rust. :))

[ethindp]

OK, fixed it.

[ethindp]

So, as I wrote above, I fixed it. The way I did it was: the slab allocator requires that the heap size be a multiple of the minimum heap size, or exactly 32 KB. Knowing this, I located the first unused memory region with the boot memory map, mapped it into the page table, then allocated it as my kernel heap (on anything above 5 MB of RAM its always between 1.5-1.6 MB or so). In that same for loop to iterate through free regions, I added a while loop that determined if the heap size was a multiple of 32 KB. If it wasn't, it would keep subtracting the end address ntil it was. I didn't want ot have it add because that could easily cause huge problems. Then I mapped that now subtracted address (only 16384 subtractions, so 16 KB unused) and used that as the heap. I tested this, pushing my krnel to its limits to see how low it could go on RAM, and using that I found it could not even boot on anything under 5 MB of RAM. That was (mainly) because the bootlaoder ran into problems; I think the kernel could safely operate on 2 MB of RAM if directly booted without a boot loader, though it wouldn't be able to do much.

[phil-opp]

This seems to be solved.