Recursive mapping questions

[eryjus]

Hi,

I have been trying to work through recursive mapping of my paging tables in my mind off and on for a couple of weeks now. Some days I feel I have better success, than others. In reality, I haven't got a clue. At this point, I am so confused I probably will not be able to articulate my questions well and I'm likely to have many follow-up questions. I might even ramble. I'm also going to try to use the words "physical" and "virtual" in front of each instance of "address" (and synonym) to help me keep them straight in my mind. Thanks in advance for being patient.

I'm setting up recursive mapping (in a 64-bit system) and let's say that I am going to use entry/index 511 for my recursive map. My first thought is that I want to map PML4[511] point to the physical address of my PML4 table. This way, when I want to access a PML4 entry, I can refer to the proper offset from 0xfffffffffffff000 and get to the proper PLML4 entry. However, on closer inspection, that logic does not seem sound. What if I need to add a new PD to a PDPT, how would I get to that structure? Besides, it would make a mess of accessing the other pages above 0xffffff8000000000. So, my current thinking is that I need to drive the actual mapping down to the page level, so that if I set up PML4[511][511][511][511] (meaning PML4[511] to get a PDPT; PDPT[511] to get a PD; PD[511] to get a PT; PT[511] to get the physical address [or page] of the PML4 table), I'm in much better shape. Is this current thinking correct?

Now, I am calculating that I have 1 page for the PML4 table. I am calculating that I have 511 pages for each of the possible PDPTables. 0xfffffffffffff000 - 0xffffffffffe00000 = 0x1ff000 / 0x1000 = 0x1ff = 511. So, if I needed to maintain the Page Table at PML4[511][511][511], how would I access that table? Same thing with the PD tables (255 * 256 -- 1 less than I am expecting in my mind). Or are these all statically at initialization? This then requires 1 PDPT + 512 PD + 512 X 512 PT frames (or 262,657 frames, or 1GB + 2MB + 4K) to be statically setup at initialization. I'm missing something very fundamental here.

Now, if I nave to add a new Page Table (or Page Directory or PDP Table) to my paging structures, I need to allocate a frame for this new structure. (I think I just answered this question as I'm trying to write it, but I'm going to continue anyway in case I'm wrong -- very like at this point ) Before I insert this new frame into my paging structures, I want to clear it to make sure nothing accesses it while it still has garbage in it. So, I want to clear it, of course. But I cannot do that with a physical address; I need to make that structure available at a virtual address in order to clear it. Do I need to put this into a temporary page to clear it before adding it to the recursive page location? I think several people would say, "No, that's what the recursive location is for." Which is why I think I've answered this question in my head since I forgot the actual page will appear in the entire page structures twice -- once as a page and once in it's real location in the paging structure tree. Do I at least have this part right???

Thanks in advance for the assistance!!

[Combuster]

I'm setting up recursive mapping (in a 64-bit system) and let's say that I am going to use entry/index 511 for my recursive map. My first thought is that I want to map PML4[511] point to the physical address of my PML4 table. This way, when I want to access a PML4 entry, I can refer to the proper offset from 0xfffffffffffff000 and get to the proper PLML4 entry. However, on closer inspection, that logic does not seem sound. What if I need to add a new PD to a PDPT, how would I get to that structure? Besides, it would make a mess of accessing the other pages above 0xffffff8000000000. So, my current thinking is that I need to drive the actual mapping down to the page level, so that if I set up PML4[511][511][511][511] (meaning PML4[511] to get a PDPT; PDPT[511] to get a PD; PD[511] to get a PT; PT[511] to get the physical address [or page] of the PML4 table), I'm in much better shape. Is this current thinking correct?

Only mapping one entry in the top layer is enough.
You'll find your PML4 mapped at the last 4K of virtual memory: PML4[511] = PML4, which means that PML4[511][511] is also PML4 and PML4[511][511][511][511] is also PML4, leading the processor to map the physical content of PML4 at fffffffffffff000 - ...fff. In the 2MB minus 4K before that, the page tables map as PML4[511][511][511][x] which is PML4[x], i.e. the actual PDPT. Basically, you just need one function for each level of tables to get to them in this manner.

[eryjus]

Combuster, thanks for your reply.

Only mapping one entry in the top layer is enough.

So my original thought was correct?

PML4[511] = PML4

I get that, but I also think that is the source of my confusion.

In the 2MB minus 4K before that, the page tables map as PML4[511][511][511][x] which is PML4[x], i.e. the actual PDPT.

It took a while for significance of this statement to sink in. Ultimately, PML4[511] removed a bottom layer of the table tree from the processor's MMU, giving you access to the structures 1 layer up in the tree. So:

• PML4[511][511][511][511] is the PML4 itself
• PML4[511][511][511][x] is PML4[x] which is the physical address of the xth PDPT table
• PML4[511][511][x][y] is PML4[[x][y] which is the physical address of the yth PD table
• PML4[511][x][y][z] is PML4[x][y][z] which is the physical address of the zth PT table

However, since PML4[511] == PML4, all of the above only works as long as 0 <= x < 511, 0 <= y < 511, and 0 <= z < 511, right? How would I access PML4[511][511] (or put another way the highest PDPT table)? We say that PML4[511][511][511][x] is the PDPT structure at PML4[x]; so if x == 511, then PML4[511] is still PML4. Should I set up a special virtual address for the highest PDPT, PD, and PT physical addresses? Or, is there some magic here that is still alluding me? Sorry, I still can't quite get my head wrapped around this part.

Also, since I am not really inserting a page of the structure into the "recursive side" and then into the "production side" [which is a completely wrong way of thinking about it], I really need to find a way to clear a new PDPT, PD, and PT before inserting it into the tree at its final location -- just to be safe. Is this thought correct? I'm thinking SMP though I'm no where close to implementing SMP yet.

[Combuster]

However, since PML4[511] == PML4, all of the above only works as long as 0 <= x < 511, 0 <= y < 511, and 0 <= z < 511, right?

Nope.

From the top of memory, you have the following addresses
ffff ffff ffff f000 - ffff ffff ffff ffff = PML4[511][511][511][511] = the content of PML4
ffff ffff ffff e000 - ffff ffff ffff efff = PML4[511][511][511][510] = the 511th PDPT
ffff ffff ffe0 0000 - ffff ffff ffe0 0fff = PML4[511][511][511][0] = the 1st PDPT
ffff ffff ffdf f000 - ffff ffff ffdf ffff = PML4[511][511][510][511] = the 261632th PD (note the 511 in the last entry)
(...)

[Brendan]

Hi,

I really need to find a way to clear a new PDPT, PD, and PT before inserting it into the tree at its final location -- just to be safe. Is this thought correct? I'm thinking SMP though I'm no where close to implementing SMP yet.

Yes, or no. You either need to make sure that any new PDPTs, PDs or PTs that you insert are full of zeros before you insert them; or make sure that no CPU can access anything in the effected area of the virtual address space after you've inserted a "dirty" PDPT, PD or PT and before you've cleared it.

However, there are other things you'd need to worry about; like atomicity in multi-CPU (e.g. ensuring different CPUs aren't trying to allocate the same PDPT at the same time), and like TLB invalidation. In general, these things mean that (for multi-CPU) you will need some way to guarantee that no CPU can access anything in the effected area of the virtual address space until after you've done TLB invalidation (including the "multi-CPU TLB shootdown"); and therefore it will be safe to insert a "dirty" PDPT/PD/PT, then clear it, then do the TLB invalidation stuff.


Cheers,

Brendan

[eryjus]

Nope.

From the top of memory, you have the following addresses
ffff ffff ffff f000 - ffff ffff ffff ffff = PML4[511][511][511][511] = the content of PML4
ffff ffff ffff e000 - ffff ffff ffff efff = PML4[511][511][511][510] = the 511th PDPT
ffff ffff ffe0 0000 - ffff ffff ffe0 0fff = PML4[511][511][511][0] = the 1st PDPT
ffff ffff ffdf f000 - ffff ffff ffdf ffff = PML4[511][511][510][511] = the 261632th PD (note the 511 in the last entry)
(...)

Wait a minute!! So, there is no 512th PDPT. There are only 511 of them (0 through 510) and this is the magic I'm missing. Correct?

[Combuster]

Because one entry of the PML4 maps to itself, it can't map to a PDPT, so you end up "missing" one.

[eryjus]

Because one entry of the PML4 maps to itself, it can't map to a PDPT, so you end up "missing" one.

... and you don't need it.

I swear I'm quick no matter how long it takes me!!!

Thank you for your responses!! I think (read: hope) I have it now.

[Pavlo]

You'll find your PML4 mapped at the last 4K of virtual memory

Hello.
Could you please tell me where to find documentation that describes this behaviour? I see that PML4 is mapped at the last portion of the virtual address space, but I cannot find docs/specs about the behaviour.

Thanks in advance.

[BrightLight]

Hello.
Could you please tell me where to find documentation that describes this behaviour? I see that PML4 is mapped at the last portion of the virtual address space, but I cannot find docs/specs about the behaviour.

Thanks in advance.

Did you really have to bump this 2-year-old thread?

[max]

Did you really have to bump this 2-year-old thread?

Why should he not? Better than creating a new thread about the same topic.

[Pavlo]

Did you really have to bump this 2-year-old thread?

Hello.

My question directly relates to this topic. Hope that links to the appropriate resources will add value to the thread.

[Octocontrabass]

Could you please tell me where to find documentation that describes this behaviour? I see that PML4 is mapped at the last portion of the virtual address space, but I cannot find docs/specs about the behaviour.

The Intel and AMD manuals have sections on paging, and that covers everything you need to know to figure out how recursive mapping works. They don't specifically document recursive mapping because it's not a specific feature of the CPU; it's just an unusual way of using the page tables.

In the most basic 32-bit x86 paging, you have a page directory, some page tables, and some pages. The clever trick is placing the address of the page directory in one of the page directory entries, so when the CPU is looking for a page table, it reads the page directory as if it were a page table.

The usual paging looks like this:

Page Directory -> Page Table -> a normal page

Recursive mapping looks like this:

Page Directory -> Page Directory (being interpreted as a page table) -> Page Table (being mapped as a page)
Page Directory -> Page Directory (being interpreted as a page table) -> Page Directory (being mapped as a page)

It works the same way in long mode, with a couple more levels to the structure:

PML4 -> PDPT -> PD -> PT -> page
PML4 -> PML4 (as PDPT) -> PDPT (as PD) -> PD (as PT) -> PT (as page)
PML4 -> PML4 (as PDPT) -> PML4 (as PD) -> PDPT (as PT) -> PD (as page)
PML4 -> PML4 (as PDPT) -> PML4 (as PD) -> PML4 (as PT) -> PDPT (as page)
PML4 -> PML4 (as PDPT) -> PML4 (as PD) -> PML4 (as PT) -> PML4 (as page)

[Pavlo]

Thank you for your detailed answer. The only issue is I am not asking about recursive mapping in general. I am asking exactly about:

PML4 mapped at the last 4K of virtual memory

I mean, I totally understand how recursive mapping works. I just can not find a document that describes "PML4 mapped at the last X of virtual memory" piece.

Sorry, if I was not clear in my initial question.

[Rusky]

That is also not documented explicitly. You can figure it out because each level's entry maps a fixed size (e.g. a PT entry maps 4k, a PML4 entry maps 1/512th the address space) to a fixed location based on its position in the table and the table's position in its parent and so on.