How to modify page tables?

[TylerH]

Given a page directory entry, and thus the physical address of a page table, what is the usual way to modify the page table? Should I just keep a page aligned 4kB slot open in my virtual address space or is there a cleaner way than that?

[Cognition]

I'd imagine most people would use the fractal mapping technique of mapping in the PML4/page directory into one of it's own entries. A simple example of which is covered under the manipulation section of the paging page on the wiki.

[Nessphoro]

I modify by writing to the memory, because by mapping to 1023 table you lose use perfectly good address space.

[NickJohnson]

I modify by writing to the memory, because by mapping to 1023 table you lose use perfectly good address space.

Except that you only lose 4 MB of address space (which is really not that bad, considering you've got 4 GB of it total), and make it so you don't have to store page tables in the kernel heap while also reducing the number of TLB flushes you need to access them. If you need to map in the page tables to modify them (or even worse, turn paging off and on again) you are adding complexity and overhead simultaneously.

[Nessphoro]

I don't need to turn off paging, I simply store the virtual location + physical location and use the virtual location to modify the page table. Just read the JamesM's kernel development tutorials, it is explained there mode in-depth

[bluemoon]

I simply store the virtual location + physical location and use the virtual location to modify the page table.

If that means you store the lookup table in kernel heap, In fact you saved the 1023'th entry but you need to store it elsewhere. That would not make benefit.

In many processes situation you need more that 4MiB to store all entries and perhaps some locking mechanism; while the recursive page table method it use a constant 4MiB (address space) per process.

[TylerH]

In many processes situation you need more that 4MiB to store all entries and perhaps some locking mechanism; while the recursive page table method it use a constant 4MiB (address space) per process.

Another benefit is the constant physical memory usage.

Despite the benefits, I think I'll use the method where the page table is mapped in (the method I described), because it is less intrusive on the higher level representation of memory management. I'm trying to create a portable OS that has a portable concept of an address space that can be accessed to do almost all (all but initialization) physical and virtual memory management. With the fractal method, I'd have to do something to stop mapping of the last 4MB on x86 and allow it on other architectures or stop it on other architectures, but that would be wasting 4MB for absolutely no reason. But, with the map in method, all architectures could be uniform.

Is there anyone who has implemented the fractal method in a portable way (in a way such that they 1: have a portable interface to pmm and vmm and 2: they don't limit other architectures from mapping in the top 4MB)?

[Cognition]

In general the actual mapping and unmapping code is going to be architecture or even feature set dependent. Basic x86 paging is different from x86-64 paging and x86-PAE paging due to the size of table entries, number of entries per a table and overall levels of paging structures that exist. There isn't a clean and efficient way to make that portable. Have your build system and preprocessor take care of these things when the kernel is built, instead of having a slower system that can't make rational expectations about the processor it's running on.

[bluemoon]

If you consider limiting to usage of topmost 4Mib is weird, think about x86-64 that have a huge hole in middle
You can come up with a design that generalize the support of memory hole in logical address space.

[TylerH]

In general the actual mapping and unmapping code is going to be architecture or even feature set dependent. Basic x86 paging is different from x86-64 paging and x86-PAE paging due to the size of table entries, number of entries per a table and overall levels of paging structures that exist. There isn't a clean and efficient way to make that portable. Have your build system and preprocessor take care of these things when the kernel is built, instead of having a slower system that can't make rational expectations about the processor it's running on.

It isn't that inefficient the way I'm doing it. I just implement the address space as a class that allows mapping of arbitrary memory along with a way to allocate/free a block of virtual memory (to a physical page determined by the address space class) and a method to allocate code/data pages. The address space implementation isn't coded in a portable way. It is fully aware of paging structures, so as to be able to take advantage of the architecture dependent abilities.

If you consider limiting to usage of topmost 4Mib is weird, think about x86-64 that have a huge hole in middle
You can come up with a design that generalizes the support of memory hole in logical address space.

Now that I think about it, it wouldn't be that bad for me to just build the limitations of virtual address space into the address space class for each CPU and disallow usage of the arbitrary mapping methods. Although that will cause me to have to declare some friends, because there are a few places where the arbitrary mapping functions are needed, like in the arch dependent init function.

[Kevin]

I don't need to turn off paging, I simply store the virtual location + physical location and use the virtual location to modify the page table. Just read the JamesM's kernel development tutorials, it is explained there mode in-depth

So if you have a virtual location... That doesn't take away perfectly good address space, just because it's not in a single place but spreaded all over the kernel memory?

In fact you even lose more virtual address space this way because you always have all page tables of all processes mapped instead of just those of the current process.

[Brendan]

Hi,

I'd imagine most people would use the fractal mapping technique of mapping in the PML4/page directory into one of it's own entries. A simple example of which is covered under the manipulation section of the paging page on the wiki.

This is the method I use, but it's not always enough on its own because it only allows you to modify the "currently in use" paging structures.

For example, for "plain 32-bit paging", if you want to add a new page table in kernel space then you have to modify the page directory for every address space but can only access the page directory for the current address space via. the fractal mapping. The easiest way around this is to map every page directory into kernel space so that you can modify all of them (then do the "multi-CPU TLB shootdown" thing); but there are alternatives (e.g. maintaining one master copy and using version numbers, and updating page directories during task switches if "new process page directory version < master copy version").

For PAE this problem may not occur, as you can map the same "kernel page directory" into every PDPT and may never need to modify a PDPT entry in every address space at the same time.

For long mode you can do the same trick with PDPTs (have one "kernel PDPT" that is mapped into every PLM4) if you limit the size of kernel space to 512 GiB. If you don't want to limit the size of kernel space size then you end up with the same problem as "plain 32-bit paging" for adding/removing kernel space PDPTs.

Of course all of the above assumes that virtual address spaces are split into 2 areas (user space and kernel space) and all threads belonging to a process share the same user space, and all virtual address spaces have share the same kernel space. These assumptions are correct for most OSs (but not mine).


Cheers,

Brendan

[bluemoon]

maintaining one master copy and using version numbers, and updating page directories during task switches if "new process page directory version < master copy version"

For adding page:
How about leave that work on page fault, and only sync partial/full version if fault in the dynamic part of kernel space?

For modifying page(will that ever happen?):
You may still need to sync version on task switches.

[Brendan]

Hi,

maintaining one master copy and using version numbers, and updating page directories during task switches if "new process page directory version < master copy version"

For adding page:
How about leave that work on page fault, and only sync partial/full version if fault in the dynamic part of kernel space?

For modifying page(will that ever happen?):
You may still need to sync version on task switches.

You're right - there should be an effective way to combine it with the "lazy TLB invalidation" logic. It gets complicated though..

Note: For most OSs, you shouldn't have to do this when adding/removing/modifying a page, because the page table/s (and page table entries) would be shared by every virtual address space that uses the page. It's only when you add/remove page tables (for "plain 32-bit paging") because the page directory (and page directory entries) can't be shared by every virtual address space that uses the page table.

You'd end up with 4 cases (for "plain 32-bit paging"):

• the page directory wasn't changed; TLB invalidation can be done with "lazy TLB invalidation"
• the page directory wasn't changed; TLB invalidation has to be done with "multi-CPU TLB shootdown"
• the page directory was changed; page directory update and TLB invalidation can both be done with "lazy TLB invalidation"
• the page directory was changed; TLB invalidation has to be done with "multi-CPU TLB shootdown" and extended to update the page directory for currently running processes, and "page_directory_version++" can be used to cause "not currently running" processes to update their page directory during the next task switch

Cheers,

Brendan