Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Map complete physical memory instead of using recursive page tables? #545

phil-opp opened this Issue Jan 29, 2019 · 4 comments


3 participants
Copy link

phil-opp commented Jan 29, 2019

There was a comment on hacker news that proposed a complete mapping of the physical address space instead of using recursive page tables:

It really doesn't save anything, and makes some operations like finding the physical address for a virtual address more complicated. His description of "identity mapping" is also a bit too focused on page-tables and kinda misses the bigger picture. x86_64 has a 48-bit memory space, so you can literally get away with identity-mapping all of your physical memory into a higher-half location with no issues, because the virtual-address space is much larger then the amount of physical memory a 64-bit computer is going to have. Ergo, even if you went with his described approach and just made a single identity mapping for each page table, it would still use so little virtual memory space you could just allocate from elsewhere for your memory-mapped files and such with no worry of them touching eachother. And by doing a single large allocation of all of physical memory, you can use very large page sizes to setup the identity map, significantly reducing the number of pages required.


I originally did not implement it this way because I didn't want to map too much virtual memory in the bootloader (so that the kernel can decide on its own mapping scheme). The recursive page table is only a single entry and can easily be undone by the kernel, so it seemed like a way to give the kernel all possibilities.

However, recursive page tables are a complicated concept. I heard from a lot of people that they were struggeling with the paging posts of the first edition, which also used recursive page tables. I tried my best to make the second edition post as accessible as possible, but maybe a complete mapping of the physical memory is a better choice for learnability.

I thought a bit on how we could implement it:

  • Add Cargo features to the bootloader:

    • The recursive_level_4_table feature enables the recursive mapping of a level 4 entry that we currently have. Provides a RECURSIVE_LEVEL_4_TABLE_ADDR constant to the kernel.
    • The map_physical_memory feature maps the complete physical address space to some virtual address. Provides a PHYSICAL_MEMORY_OFFSET constant to the kernel.

    This way both variants are supported by the bootloader and users can decide which one to use (or maybe both of them).

  • Add a Mapper implementation that supports this approach to x86_64. Alternatively, add a generic mapper implementation that works with any phys->virt closure.

With this implemented, we could deprecate the advanced paging post and release a new "Paging Implementation" post that uses the mapped physical memory.



This comment has been minimized.

Copy link

koutheir commented Feb 4, 2019

I found the recursive technique pretty interesting, and you explained it pretty clearly. For simplicity's sake on a 46 bits CPU, nothing beats identity mapping. Recursive mapping remains as a powerful technique that might be interpolated to other architectures (with less MMU bits) so I think it is worth keeping.


This comment has been minimized.

Copy link
Owner Author

phil-opp commented Feb 7, 2019

@koutheir Thanks for the feedback! I plan to keep the explanation of recursive paging around, either as part of the new post or in a linked extra post.

@phil-opp phil-opp added this to Planned in Roadmap Feb 11, 2019


This comment has been minimized.

Copy link

bemeurer commented Mar 1, 2019

@phil-opp Could you explain the pros/cons of the two approaches? I'm pondering now on whether to wait for the new post or go ahead with the current one. From what I read it seems like recursive page tables are more complex, but far more flexible, while the mapping approach is simpler and can support more architectures. Am I on the right track? What are the other main differences?

@phil-opp phil-opp moved this from Planned to In Progress in Roadmap Mar 4, 2019


This comment has been minimized.

Copy link
Owner Author

phil-opp commented Mar 4, 2019

@bemeurer Yes, you're on the right track. From my current draft of the new post:

Recursive Paging is a interesting technique that shows how powerful a single mapping in a page table can be. It is relatively easy to implement and only requires a minimal amount of setup (just a single recursive entry), so it's a good choice for first experiments with paging.

However, it also has some disadvantages:

  • It occupies a large amount of virtual memory (512GiB). This isn't a big problem in the large 48-bit address space, but it might lead to suboptimal cache behavior.
  • It only allows accessing the currently active address space easily. Accessing other address spaces is still possible by changing the recursive entry, but a temporary mapping is required for switching back. We described how to do this in the (outdated) Remap The Kernel post.
  • It heavily relies on the page table format of x86 and might not work on other architectures.

I wouldn't say that recursive page tables are more flexible. It's more the other way around: A mapping of the complete physical memory allows accessing arbitrary physical frames, including page table frames of other address spaces or frames used for DMA. So I think that it's the better choice for the blog.

I just pushed my current prototype implementation of the new code in the physical-mem-map-wip branch (diff). Note that the code depends on very unstable preview versions of the x86_64 and bootloader crates.

I'll do my best to finish the new post soon.

Roadmap automation moved this from In Progress to Done Mar 14, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.