Paging Implementation

[utterances-bot]

This is a general purpose comment thread for the Paging Implementation post.

[lilyball]

The bootloader and x86_64 changelog links are swapped.

[yiweichi]

hello, when i cargo run, i got a panic:
panicked at 'assertion failed: max_phys_addr < (1 << 48) / 512'. src/main.rs:294:13
in my QEMU terminal.

[dumbinacan]

If you were still looking for a fix, this helped me solve that issue.

#1138 (comment)

[phil-opp]

@lilyball Thanks! Fixed in cc0f684.

[DanGdl]

This paging approach seems much clear and easy to understand

[phil-opp]

@DanGdl Great to hear that!

[pitust]

That's better than last time (I hope). Last time the code didn't compile.

[phil-opp]

@pitust Please open an issue when you have any problems with compiling the code. You can also find the complete code for the post in the post-10 branch. This branch is automatically tested on every new nightly using different continuous integration services, so it should always compile without problems.

[songzhi]

If I use the 'map_physical_memory' feature,and I want to create a new level_4_page_table to be switched to when I create a new process.Do I need to map the whole physical memory in the new page table manually just like what you did in 'bootloader' crate?Actually I found that snippet of code,but I am not really sure should I type it again in my code.

[phil-opp]

@songzhi If you want that your new process also has access to the physical memory then you need to add a mapping for it in its address space. As an optimization you can link the level 3 or level 2 page table from your current address space to the new address space instead of copying them, so that both address spaces share the same level 3/level 2 table.

[krsoninikhil]

For anyone who is updating x86_64 crate from 0.4.0 to required 0.5.2 and getting error like try_from not being stable, you also need to update your rustc version (rustup update). After this, you'll also be required to update your code as per new version of x86_64 which will be suggested by compiler itself or you can refer this commit.

[redamith2]

How to create global static frame_allocator so that I can move the page mapping inside the page fault handler. I have tried

In lib.rs

pub static mut FRAME_ALLOCATOR: Option<BootInfoFrameAllocator<Iterator<Item = PhysFrame>> = None

I keep getting an error "doesn't have a size known at compile-time"

[phil-opp]

How to create global static frame_allocator so that I can move the page mapping inside the page fault handler. I have tried […]

Discussed in #593

[izzabelle]

Just wanted to mention that the src/memory.rs lacks the inclusion of a use bootloader::bootinfo::{MemoryMap, MemoryRegionType}; when you get to talking about the writing the boot frame allocator. I know it's a tiny thing but it threw me for a loop the first time as my first guess would have had it somewhere in the paging structures in the x86_64 crate and not the bootloader.

[phil-opp]

@nrlsk Thanks for reporting! Fixed in 6db5ad7.

[phil-opp]

@tom7980 Seems like you deleted your comment. It was a valid question, so let me give you a short answer anyway.

Yes, the frame allocator could be implemented this way. We used a similar implementation before. The problem is that it couldn't be stored in a static then because we can't name the generic I parameter, because it depends on unnamable closure types. See #593 for a discussion of the problem.

I'm struggling to test it myself as I'm having trouble building all the dependencies with xbuild.

Could you open an issue for this with more specific information?

[tom7980]

@phil-opp I can open an issue about it tomorrow as I'm on the wrong computer currently, I was only struggling on my windows environment, once I booted into Linux and tried the build steps I managed to sort it so it might just be my windows env is mis-configured.

Regarding my question, I actually had a go at implementing it but I came up against the issue that the initialisation of the wrapper was expecting a type I where I: Iterator, but due to passing a memory map to the function and doing some transformations onto it I was getting a nested iterator and it wouldn't let me store it anyway!

I'm going to take another look at it tomorrow but I think I understand what you meant about the static still trying to wrap my head around Traits and Generic Types, and to be fair most of Rust!

[ethindp]

I'm having a lot of difficulty debugging this page fault (I got the triple fault to at least work). After using step for a bit of time and then returning to "next" the next command starts behaving just like step. Instead of (say) jumping over these lines of my code, for example:

            return MMAP
                .get()
                .unwrap()
                .iter()
                .map(|r| r.start..r.end)
                .flat_map(|r| r.step_by(4096))
                .map(|addr| PhysFrame::containing_address(PhysAddr::new(addr)))
                .nth(FPOS.load(Ordering::Relaxed));

It does this instead:

• Jump into spin::once::Once<heapless::vec::Vec<libk::memory::MemoryRegion>, spin::relax::Spin>::get<heapless::vec::Vec<libk::memory::MemoryRegion>,spin::relax::Spin>
• Which jumps into core::sync::atomic::AtomicUsize::load
• Which jumps into core::sync::atomic::atomic_load<usize>
• Which jumps back into core::sync::atomic::AtomicUsize::load
• Which jumps back into spin::once::Once<heapless::vec::Vec<libk::memory::MemoryRegion>, spin::relax::Spin>::get<heapless::vec::Vec<libk::memory::MemoryRegion>,spin::relax::Spin>
• Which jumps into spin::once::Once<heapless::vec::Vec<libk::memory::MemoryRegion>, spin::relax::Spin>::force_get<heapless::vec::Vec<libk::memory::MemoryRegion>,spin::relax::Spin>

And so on and so forth. This makes it incredibly difficult to get out of and the debugging noise makes it impossible to track where I'm trying to go. Does anyone know why GDB is behaving this way?

[ethindp]

Okay, I think I've nailed it down. For some reason, this code, or thereabouts, is causing the page fault:

    fn create_next_table<'b, A>(
        &self,
        entry: &'b mut PageTableEntry,
        insert_flags: PageTableFlags,
        allocator: &mut A,
    ) -> Result<&'b mut PageTable, PageTableCreateError>
    where
        A: FrameAllocator<Size4KiB> + ?Sized,
    {
        let created;

        if entry.is_unused() {
            if let Some(frame) = allocator.allocate_frame() {
                entry.set_frame(frame, insert_flags);
                created = true;
            } else {
                return Err(PageTableCreateError::FrameAllocationFailed);
            }
        } else {
            if !insert_flags.is_empty() && !entry.flags().contains(insert_flags) {
                entry.set_flags(entry.flags() | insert_flags);
            }
            created = false;
        }

        let page_table = match self.next_table_mut(entry) {
            Err(PageTableWalkError::MappedToHugePage) => {
                return Err(PageTableCreateError::MappedToHugePage);
            }
            Err(PageTableWalkError::NotMapped) => panic!("entry should be mapped at this point"),
            Ok(page_table) => page_table,
        };

        if created {
            page_table.zero();
        }
        Ok(page_table)
    }

To be specific, this part:

        let page_table = match self.next_table_mut(entry) {
            Err(PageTableWalkError::MappedToHugePage) => {
                return Err(PageTableCreateError::MappedToHugePage);
            }
            Err(PageTableWalkError::NotMapped) => panic!("entry should be mapped at this point"),
            Ok(page_table) => page_table,
        };

        if created {
            page_table.zero();
        }
        Ok(page_table)

I've no idea why this is causing the page fault in particular. But for some reason this is where my (15 plus) breakpoints lead me to. Thoughts?

[sosiaozomaker]

sir, I follow this post step by step. But after the session "Accessing the Page Tables", when I build and run it, the qemu window displays panic information.

panicked at assertion failed: max_phys_addr < (1 << 48) / 512' src/main.rs:291: 13

The same as the source code cloned from your github repo.

There is my develop enviroment:
host system: macOS 12.6 for intel
qemu-system-x86_64 7.1.0
rustc 1.65.0-nightly

[bjorn3]

See #1138 tl;dr: this is a bug in the bootloader crate that was exposed by a change in qemu 7.1.0.

[sosiaozomaker]

Thank you very much! It works.

[yiweichi]

hello, when i cargo run, i got a panic:
panicked at 'assertion failed: max_phys_addr < (1 << 48) / 512'. src/main.rs:294:13
in my QEMU terminal.

[sosiaozomaker]

There is a solution below the issue #1138.
In short, add this entry to Cargo.toml:

[package.metadata.bootloader]
physical-memory-offset = "0x0000f00000000000"

[yiweichi]

it works, thank you very much!

[dchinmay2]

In "mapping the complete physical memory", can someone explain the 132KiB number?

32 GiB / 4 KiB = 8388608 pages

Each level 2 page table has 2MiB / 8B = 262144 entries

Therefore there are 8388608 / 262144 = 32 level 2 page tables, and 1 level 3 page table with 32 entries.

Space occupied = $(1\cdot 32 \cdot 8) + (32 \cdot 262144 \cdot 8) + (8388608 \cdot 8)$ B = 131072.25 B = 131.07225 KiB. Am I doing this right?

[kayoch1n]

Each level 2 page table has 2MiB / 8B = 262144 entries

I think each page table should contain exactly 512 entries regardless of which level it is. With huge page enabled, each L2 table entry points to a frame of 2MiB memory. The 132KiB number is mentioned in a previous comment

Each level 2 table can manage 512 * 2MiB = 1GiB of memory. So for 32 GiB physical memory, we need 32 level 2 tables, one level 3 table, and one level 4 table. I didn't mention the level 4 table because you always need it and there can be only a single instance of it anyway.

[dchinmay2]

I see, thanks

[kayoch1n]

The post ended with the problem that we can’t access the page tables from our kernel because they are stored in physical memory and our kernel already runs on virtual addresses.

Before this post, we wrote bytes to 0xb8000 to print something on screen. Does that mean bootloader was using an identity mapping by default?

[make-things-better]

The post ended with the problem that we can’t access the page tables from our kernel because they are stored in physical memory and our kernel already runs on virtual addresses.

Before this post, we wrote bytes to 0xb8000 to print something on screen. Does that mean bootloader was using an identity mapping by default?

Let me share what I observed. The bootloader that this project is using identity-maps the vga_map_frame_buffer which resides in the physical address range of 0xa0000 and 0xc0000. You can refer to the 3rd stage of the bootloader calling the vga_map_frame_buffer label at the last line of the set_up_page_tables label, and the vga_map_frame_buffer label identity-mapping the memory region between 0xa0000 and 0xc0000.

[make-things-better]

I guess the bootloader is not necessary anymore once the kernel is properly loaded and starts executing, but the bootloader seems to identity-map the initial page tables and the bootloader itself's code and data sections as seen here at the 3rd stage and never unload or unmap them even until the control is transferred to the kernel. Is the bootloader code and data used to communicate with the kernel or for any other reasons after the kernel is loaded?

[Cacatina]

When I use cargo run to compile the kernel, why is it always stuck？I have to try it again and agian.
PS F:\rust\blog_os> cargo run
Compiling blog_os v0.1.0 (F:\rust\blog_os)
PS F:\rust\blog_os> cargo run==========> ] 28/29: blog_os(bin)
Compiling blog_os v0.1.0 (F:\rust\blog_os)
PS F:\rust\blog_os> cargo run==========> ] 28/29: blog_os(bin)
Compiling blog_os v0.1.0 (F:\rust\blog_os)
PS F:\rust\blog_os> cargo run==========> ] 28/29: blog_os(bin)
Compiling blog_os v0.1.0 (F:\rust\blog_os)
PS F:\rust\blog_os> cargo run==========> ] 28/29: blog_os(bin)
Compiling blog_os v0.1.0 (F:\rust\blog_os)
PS F:\rust\blog_os> cargo run==========> ] 28/29: blog_os(bin)

[AlexandreMarcq]

Hello, I have trouble understanding the code for the usable_frames method.
I don't get why we need to map and flat_map in order to get the start address of each frame.
Couldn't we just .map(|r| r.range.start_addr()) ?

After playing a bit in Rust Playground, I think I understood. Are MemoryRegions "made up" of multiple frames ?

[sauravdeshpande]

Hello, In the technique Map the Complete Physical Memory, how can I create a new PageTable for another process. Since OffsetPageTable requires the that complete physical memory to be mapped, how do I achieve that?

Thank you.

[LeulShiferaw]

Did you mean virtual address on the paragraph before Using OffsetTable? Because if you add the physical offset you get the virtual address not the physical address

[criskell]

We first use the usable_frames method to get an iterator of usable frames from the memory map. Then, we use the Iterator::nth function to get the frame with index self.next (thereby skipping (self.next - 1) frames). Before returning that frame, we increase self.next by one so that we return the following frame on the next call.

shouldn't it be ((self.next) frames)? self.next is initially 0 so it wouldn't make sense to skip -1 frames.

[DragonDev1906]

Really good blog/post, thank you.

I think the "Address Calculation" in "Recursive Page Tables" can be simplified while making the code easier to read/review. The current code snippet has a lot of magic numbers in it:
In the table you talk about multiplying indexes by 8 to "convert/use" them as offset: 0o_SSSSSS_RRR_RRR_AAA_BBB_CCCC Instead you could just say the last octet is always 0: 0o_SSSSSS_RRR_RRR_AAA_BBB_CCC0. This has the same effect but leads to a simpler (+faster?) Rust code that doesn't shift everything to the lowest 8 bit and then back:

// Untested code, level must be 0..=4
fn virtual2rpt_addr(mut addr: u64, level: usize) -> u64 {
    // Shift right until everything is in the right place.
    addr >>= (9*level);
    // Set sign extension and recursive index bits (assuming r=0o777 for simplicity)
    addr |= u64::MAX << (48-9*level);
    // Set the last 3 bit to 0, since we want the address to the entry.
    addr &= !7u64;
    addr
}

Most of this is constant and only depends on level, so if level is hard coded all of this likely gets compiled to a ((addr >> A) | B) & C for each level.

By using i64 (so shifting extends with 1) and setting the sign-extend bits to 1 before doing the shifting it could even be faster, esp. when all levels are needed:

let addr = (addr | u64::MAX << 48) as i64;
let lvl1 = (addr >> 9) as u64 & !7;
let lvl2 = (addr >> 18) as u64 & !7;
let lvl3 = (addr >> 27) as u64 & !7;
let lvl4 = (addr >> 36) as u64 & !7;

// Or by shifting back (they generate identical assembly)
let lvl1 =( (addr >> 12) << 3) as u64

It's not as intuitive to get to, but should still be easy enough to understand with the explanation above it.

=> You can get the address for all 4 levels with just 8 shifts (or 4 shits and 4 AND) and an OR (while being pipelining friendly given enough ALUs and needing only a minimal amount of registers).

Compiler Explorer

[gokulsan29]

This approach still has the disadvantage that we need to create a new mapping
whenever we create a new page table. Also, it does not allow accessing page tables
of other address spaces, which would be useful when creating a new process.

Hello, In the section Accessing Page Tables, subsection Mapping at Fixed Offset, it is written that this method does not allow us to access other address spaces. I am unable to understand why this would be the case. If the OS makes a new process, the OS should be able to add a mapping for the page table frame of the newly created process, and as all the processes that are currently running should have their page tables set up by the OS, the OS should have mappings for the address spaces for all the currently running processes, right?

[gokulsan29]

@phil-opp

[ChocolateLoverRaj]

I think it is incorrect if it says that offset mapping does not allow accessing page tables of other address spaces.

[prasadashu]

Equally, it makes it much more difficult to create new page tables because we need to find physical frames whose corresponding pages aren’t already in use. For example, let’s assume that we reserved the virtual 1000 KiB memory region starting at 1008 KiB for our memory-mapped file. Now we can’t use any frame with a physical address between 1000 KiB and 2008 KiB anymore, because we can’t identity map it.

Very basic question, but if we reserve 1000 KiB memory region starting at 1008 KiB, shouldn't we not be able to use physical address between 1008 KiB (vs. 1000 KiB) and 2008 KiB?