How to implement microkernel recursive paging?

[austanss]

I was having a circular dependency/chicken and egg issue with mapping memory when page tables haven't been mapped, and after asking around I came to the idea of recursive/fractal paging.

I read up on an article about it, took a THC gummy, and grasped the concept easily.

I entered my PML4 structure as the last entry in the PML4 structure.

Code: Select all

	memory::paging::pml_4 = (memory::paging::page_table *)memory::paging::allocation::request_page();
	
	memory::operations::memset(memory::paging::pml_4, 0, 0x1000);

        memory::paging::page_directory_entry pml_4_pde;
        pml_4_pde.set_address((uint64_t)memory::paging::pml_4);
        pml_4_pde.set_flag(memory::paging::pt_flag::present, true);
        pml_4_pde.set_flag(memory::paging::pt_flag::read_write, true);

        memory::paging::pml_4->entries[512 - 1] = pml_4_pde;

        memory::paging::map_memory((void*)memory::paging::pml_4, (void*)memory::paging::pml_4);

Alas, this did increase the mapped address space of my tables, but not quite all the way.

What am I missing? I am definitely missing something.

[nullplan]

I was having a circular dependency/chicken and egg issue with mapping memory when page tables haven't been mapped, and after asking around I came to the idea of recursive/fractal paging.

In 64-bit mode, you have such a surplus of virtual memory that it might just be simpler to map all physical memory linearly. That is what I am doing: All physical memory is mapped to 0xffff_8000_0000_0000. This means, translating between virtual and physical address becomes trivial, and it solves way more problems than just paging.

But yes, fractal mapping. If the functions do what their names claim then this should work. But what code model are you using for the kernel? I am using the "kernel" code model, which requires access to the topmost 2GB of address space, and this mapping will block the highest 512GB. Beyond that it doesn't make sense that it would partially work. It should either work or not, since only a single mapping makes it happen. What addresses are you missing?

[nexos]

I would never map all memory linearly. Imagine if a hacker exploited Meltdown. They could literally destroy the hardware!

[nullplan]

I would never map all memory linearly. Imagine if a hacker exploited Meltdown. They could literally destroy the hardware!

If a hacker has the ability to write into kernel space (as you are claiming here), you have already lost. The hacker can then write into the page tables and map arbitrary memory. Whatever damage you imagine they can do by writing into physical memory, they can do however you choose to manage your virtual memory. I was under the impression, however, that Meltdown merely allows a hacker to read from kernel space. And only until you implement page table isolation. Which you can also do however you choose to manage your virtual memory. In short, your objection does not depend on the way you choose to manage virtual memory, and is therefore irrelevant to this discussion. And neither does it explain how the OP managed to fractally map his page tables, but only partially.

[nexos]

IMO it seems to better to limit the attack surface. On topic now
x86_64 recursive paging always hurt my brain . A good document on it (in Rust) is at https://os.phil-opp.com/paging-implementation/

[thewrongchristian]

I would never map all memory linearly. Imagine if a hacker exploited Meltdown. They could literally destroy the hardware!

As I understand it, Meltdown is allows processes to protected read memory, not write it. Any hardware that can be destroyed simply by reading MMIO deserves to be in the dumpster already.

[austanss]

I was having a circular dependency/chicken and egg issue with mapping memory when page tables haven't been mapped, and after asking around I came to the idea of recursive/fractal paging.

In 64-bit mode, you have such a surplus of virtual memory that it might just be simpler to map all physical memory linearly. That is what I am doing: All physical memory is mapped to 0xffff_8000_0000_0000. This means, translating between virtual and physical address becomes trivial, and it solves way more problems than just paging.

But yes, fractal mapping. If the functions do what their names claim then this should work. But what code model are you using for the kernel? I am using the "kernel" code model, which requires access to the topmost 2GB of address space, and this mapping will block the highest 512GB. Beyond that it doesn't make sense that it would partially work. It should either work or not, since only a single mapping makes it happen. What addresses are you missing?

I am confused by what you refer to as "code model".

[Octocontrabass]

I am confused by what you refer to as "code model".

The "-mcmodel" option you pass to your compiler.

[austanss]

I am confused by what you refer to as "code model".

The "-mcmodel" option you pass to your compiler.

I never do/did such thing...

[Octocontrabass]

That means you're using the default, which is the small code model ("-mcmodel=small").

[nullplan]

I never do/did such thing...

As Octo said, that means you are using the small model. Are all your link time addresses below 2GB? If you want to build a lower-half kernel, that is fine, I had just assumed you wanted to build a higher-half one, given that the most popular kernels are higher-half (and also, the existing toolchains fit in much more nicely if the userspace is in the lower half).

By the way, if you base your kernel at -2GB and use the kernel code model, you can still use fractal mappings. Just not in the last slot of the PML4. I had at one point developed a view of memory if you used the first higher-half PML4 entry (i.e. the 256th one) as the fractal entry. Looked something like this:

Code: Select all

#define REC_ENTRY 256
#define KERNEL_VADDR(pml4i, pdpti, pdi, pti) ({static_assert(pml4i >= 256); 0xffff000000000000 | pti << 12 | pdi << 21 | pdpti << 30 | pml4i << 39;})
#define PML4_ADDR (uint64_t*)KERNEL_VADDR(REC_ENTRY, REC_ENTRY, REC_ENTRY, REC_ENTRY)
#define PDPT_ADDR(pml4i) (uint64_t*)KERNEL_VADDR(REC_ENTRY, REC_ENTRY, REC_ENTRY, pml4i)
#define PDT_ADDR(pml4i, pdpi) (uint64_t*)KERNEL_VADDR(REC_ENTRY, REC_ENTRY, pml4i, pdpi)
#define PT_ADDR(pml4i, pdpi, pdi) (uint64_t*)KERNEL_VADDR(REC_ENTRY, pml4i, pdpi, pdi)

[nexos]

(and also, the existing toolchains fit in much more nicely if the userspace is in the lower half)

Yes. I personally don't find much reason for a higher half kernel besides the fact that most toolchains will only make binaries with their base in the lower half. Also, for portability, I believe MIPS requires that all address with bit 31 set are only accessed by kernel mode.

[sj95126]

I was struggling with this problem for a while, so frustrated that I didn't code for a couple weeks because I couldn't wrap my head around it. My 64-bit kernel uses a high-load space at 0xffff_8000_0000_0000. As my memory manager was bootstrapping itself and allocating pages for free page lists and other purposes, you inevitably end up at the point where you need to create a new PD or PT that has to have an entry for itself ... the classic chicken-and-egg problem.

I had tried implementing some ugly solution involving a temporary linear page entry that could be mapped to whatever I needed, so I could add a new page tables with an entry for themselves, but it was ugly. Among other things, you'd have to flush the TLB every time you reuse that linear address so that you don't update the wrong place.

I finally hit on a somewhat simpler solution. It's not especially elegant, but really, it's hard to make a memory manager bootstrapping itself elegant. Since I have my own boot block, I can identity map memory before going into 64-bit mode and enabling paging. I created an additional identity mapped space at 0xffff_ffff_0000_0000 for the first 1GB of memory. This only means one additional PDPT and one PD, using 2MB pages, and only added about 55 bytes to my boot code. As I'm populating the initial page tables, I can update them by referencing a 0xffff_ffff_xxx address and avoid any hassles. I may or may not end up abandoning that range in favor of an identity mapped range that includes all memory and reflects range gaps from the E820 table, but for now it's sufficient to get memory management up and running.