Paging implementation approaches

[CRoemheld]

Hello there,

I'm new to OSDev and generally to OS development, but I really like the structure of the Wiki and its articles. Huge props to the authors!

My first question in this Forum is about the different paging implementations. I have a good grasp about the theory for the different paging levels (x86 with 2-level and x86_86 with 4-level paging). However, I'm stuck in what seems to be the actual implementation of the paging system. I would like to show what I did so far and what my researches have thaught me as well as show you why I'm genuinely confused about what approach to choose and how the approaches exactly work during runtime.

What I did so far:

I completed the Bare Bones x86 Tutorial and read a good amount of the topics of GDT, IDT, etc. The current state of my OS:

1. - Bare Bones x86 Tutorial finished
   - For loading a 64-bit kernel, I chose the approach using a separate loader

I want to implement a 4-level paging mechanism for the x86_64 OS. However, there are quite a load of approaches around.

The first approach is the one used in the Wiki, using a static array of length 1024 for the page directory on x86. However, as mentioned in the same article, this is a temporary workaround, as dynamic allocation is "too basic to be missing". Also, extending this to a 4-level paging mechanism would probably lead to something like the following:

Code: Select all

static uint64_t pml4[512];
static uint64_t pdpt[512][512];
static uint64_t pde[512][512][512];
static uint64_t pt[512][512][512][512];

which would definitely be too much for the program and the RAM to handle.

The second approach was used on a different tutorial, guiding the developer to an OS built in Rust. Here, the space for the tables is being reserved in assembler, using the resb instruction with a value of 4096. While I get why the value is 4096 (512 entries for each table in each level and 8 byte for each entry -> 512 * 8 = 4096), I don't get why only 4096 bytes for each tables is reserved. As far as I understand, the only thing happening there is reserving space for one PML4, one PDPT, one PD and one PT. What about the missing 511 PDPTs and the 511 * 512 PDs and the rest of the page tables?

Both of the approaches listed above have something in common, which is my question here: How do I set up paging in a dynamic approach?

My first intuition was initializing an array with length 512 for the PML4 table. When mapping, you would check if the entry for the given linear address has a PRESENT flag set for the PDPT. In the initial state, no entries have this flag set, so I would need to "create" a new PDPT (how? using some kind of kmalloc just for page tables?) and set the entry of the PML4 to the newly allocated PDPT. The same goes for the PD and the PT when further mapping the linear address to a physical address. But I don't know where to store the newly created tables, as the heap won't be a good idea I guess. Maybe the idea might even be completely wrong.

I hope I could properly explain my problem to you and hope, you can give me some insight about what to do exactly.

Thanks for your help!

[Brendan]

HI,

The second approach was used on a different tutorial, guiding the developer to an OS built in Rust. Here, the space for the tables is being reserved in assembler, using the resb instruction with a value of 4096. While I get why the value is 4096 (512 entries for each table in each level and 8 byte for each entry -> 512 * 8 = 4096), I don't get why only 4096 bytes for each tables is reserved. As far as I understand, the only thing happening there is reserving space for one PML4, one PDPT, one PD and one PT. What about the missing 511 PDPTs and the 511 * 512 PDs and the rest of the page tables?

Let's assume the kernel is 1234 KiB and you want to map it somewhere. Because the kernel is smaller than 2 MiB you only need a single page table; and because you only need a single page table you also only need one page directory, and... You don't waste RAM allocating PDPTs (and PDs and page tables) that you don't need - you just mark unused PML4 entries (and PDPT entries, and ...) as "not present" instead.

Both of the approaches listed above have something in common, which is my question here: How do I set up paging in a dynamic approach?

If the code was using "resb 4096" to reserve space then it wasn't using a dynamic approach to allocate memory.

My first intuition was initializing an array with length 512 for the PML4 table. When mapping, you would check if the entry for the given linear address has a PRESENT flag set for the PDPT. In the initial state, no entries have this flag set, so I would need to "create" a new PDPT (how? using some kind of kmalloc just for page tables?) and set the entry of the PML4 to the newly allocated PDPT. The same goes for the PD and the PT when further mapping the linear address to a physical address. But I don't know where to store the newly created tables, as the heap won't be a good idea I guess. Maybe the idea might even be completely wrong.

It might help to read "Brendan's Memory Management Guide" to understand the relationships between the layers (heap, virtual memory management and physical memory management).

The problem is that you need to set up paging initially so that you can get the kernel working before you can initialise things (e.g. physical memory manager) properly. That's why the initial pages are typically allocated statically (e.g. using "resb 4096" or "uint64_t bootPML4[512]" or whatever to reserve space/RAM in your ".bss" section). Of course it is entirely possible to dynamically allocate pages for the the initial setup, but this typically means having two physical memory managers - a simple (minimal) physical memory manager that is used before paging is started (which might be in a boot loader and not in the kernel); then a full physical memory manager in the kernel itself that is used after paging is started.


Cheers,

Brendan

[CRoemheld]

Let's assume the kernel is 1234 KiB and you want to map it somewhere. Because the kernel is smaller than 2 MiB you only need a single page table; and because you only need a single page table you also only need one page directory, and... You don't waste RAM allocating PDPTs (and PDs and page tables) that you don't need - you just mark unused PML4 entries (and PDPT entries, and ...) as "not present" instead.

This would mean, even if you map the kernel in a table, the PML4 would have only one present entry, which would be the PDPT which is statically initialized with another array, also using only one entry pointing to a PD and so on? So it would basically be just for the kernel to map it?

If the code was using "resb 4096" to reserve space then it wasn't using a dynamic approach to allocate memory.

That is clear to me. Sorry when I explained it bad.

It might help to read "Brendan's Memory Management Guide" to understand the relationships between the layers (heap, virtual memory management and physical memory management).

Thanks for the article, I will definitely read it.

The problem is that you need to set up paging initially so that you can get the kernel working before you can initialise things (e.g. physical memory manager) properly. That's why the initial pages are typically allocated statically (e.g. using "resb 4096" or "uint64_t bootPML4[512]" or whatever to reserve space/RAM in your ".bss" section).

Further emphasizing the first quote, only neccessary tables for the boot.

Of course it is entirely possible to dynamically allocate pages for the the initial setup, but this typically means having two physical memory managers - a simple (minimal) physical memory manager that is used before paging is started (which might be in a boot loader and not in the kernel); then a full physical memory manager in the kernel itself that is used after paging is started.

So, to conclude: I would need to set up paging for the kernel only and after I'm further into my OS, set up tables for the general use after the boot is already set up. But would that mean I need to map the kernel before entering long mode or after I'm already in my 64-bit kernel?

Thanks for your answer.

[Brendan]

Hi,

Let's assume the kernel is 1234 KiB and you want to map it somewhere. Because the kernel is smaller than 2 MiB you only need a single page table; and because you only need a single page table you also only need one page directory, and... You don't waste RAM allocating PDPTs (and PDs and page tables) that you don't need - you just mark unused PML4 entries (and PDPT entries, and ...) as "not present" instead.

This would mean, even if you map the kernel in a table, the PML4 would have only one present entry, which would be the PDPT which is statically initialized with another array, also using only one entry pointing to a PD and so on? So it would basically be just for the kernel to map it?

Yes (sort of).

Of course it is entirely possible to dynamically allocate pages for the the initial setup, but this typically means having two physical memory managers - a simple (minimal) physical memory manager that is used before paging is started (which might be in a boot loader and not in the kernel); then a full physical memory manager in the kernel itself that is used after paging is started.

So, to conclude: I would need to set up paging for the kernel only and after I'm further into my OS, set up tables for the general use after the boot is already set up. But would that mean I need to map the kernel before entering long mode or after I'm already in my 64-bit kernel?

It's slightly more complicated.

Typically the kernel is loaded at a fixed physical address (e.g. at 0x00100000), and you tell the linker that the kernel will be running at (e.g.) virtual address 0xFFFFFFFF80000000, so you need to setup a PML4, PDPT, PD and PT so that physical addresses starting at 0x00100000 are mapped to virtual addresses starting at 0xFFFFFFFF80000000. However this code is using physical addresses and not using addresses that the linker expects, so it ends up being a slightly tricky (and hopefully tiny) piece of assembly that has explicit address fixups to work around the "not running where linker thinks it is" problem (plus some other tricky stuff, like code to switch from protected mode to long mode, etc).

Also; at the instant that paging is enabled the next instruction has to exist. For example if you enable paging using some instructions that happen to be at physical address 0x00100123 then immediately after paging is enabled the CPU will try to fetch the next instruction from RIP which will be near 0x00100123 and won't be where the kernel actually got mapped, so if that tiny little area (e.g. a single "jump" instruction to correct RIP) is not identity mapped the OS will crash. This means you may need a second PDPT and PD and PT just for that one instruction (and those can be freed/removed as soon as that one instruction is finished).

The end result of all this is a small amount of "extremely early boot" paging setup code that often uses pre-allocated physical pages (the "resb 4096" stuff) just so that the kernel can start running properly. You can't postpone this early paging setup until later, because you can't even run any 64-bit code without enabling paging (and you don't want that "not running where linker thinks it is" problem to be spread all over the kernel).

Of course this is just how it's typically done by beginners (especially those using multi-boot); and there are a large number of potential alternatives.

For one alternative; my boot loaders setup a simple physical memory manager and paging before they bother to load the kernel into RAM, and then dynamically allocate and map pages as the kernel is being loaded into RAM. One of the advantages of this approach is that the kernel can be pure 64-bit code without any messy startup assembly (that is only needed once) and without any "not running where linker thinks it is" problem (because the kernel only ever uses the virtual addresses that the linker was told it would be running at).


Cheers,

Brendan