Understanding Page Tables in Linux/seL4

Question

Why are entries in the Page Global Directory offset? What is the significance of the offset, if any?

Page Global Directory

Address	Entry 1	Entry 2
0000000080036000:	0x0000000000000000	0x0000000000000000
...	...	...
0000000080036bf0:	0x0000000000000000	0x0000000000000000
0000000080036c00:	0x000000002000d401	0x0000000000000000
0000000080036c10:	0x0000000000000000	0x0000000000000000
...	...	...
0000000080036ff0:	0x0000000000000000	0x0000000000000000

Why not start the entries at position 0 at 0x80036000?

Linux and seL4 for RISC-V (sv39) use a three level page table that has a Page Global Directory (PGD), Page Middle Directory (PMD), and Page Table Entries (PTE). The PTE entries point to executable data. It's exactly this: http://www.science.unitn.it/~fiorella/guidelinux/tlk/node34.html

Each table is 4096 bytes or 0x1000. The entries are 64 bytes each. Each table can have 512 entries (0x200). Some of the tables--particularly PGD and PMD have entries that are offset. In other words, instead of starting at position 0 in the table, the entries are 0 until halfway or even 3/4 of the way through the table. I'm trying to understand why that is.

The question is about the location within the table rather than the contents of the location. That is why start at 0x80036c00 vs. what 0x2000d401 means? I know that 0x2000d401 points to an entry in the PMD which points to an entry in PTE and that finally points to executable code.

I can walk the page table conceptually without a problem. My problem is that I've moved the payload in my binary and modified the page tables to use 4KB instead of 2MB pages. This works in a special case, but no the general case and I'm trying to understand why. I suspect I've got something wrong in the page tables based on QEMU outputs I get.

Answer 1

Why are entries in the Page Global Directory offset? What is the significance of the offset, if any?

The entries in the PGD are not offsets they are pointers to another page table. The offsets in the page tables are contained within the virtual address.

Linux and seL4 use a three level page table that has a Page Global Directory (PGD), Page Middle Directory (PMD), and Page Table Entries (PTE).

To my knowledge, this is outdated information. I don't know anything about seL4 but Linux uses 4 level page tables. This probably also depends on the architecture like x86-64 vs ARM. Even then, I'm quite sure Linux uses 4 levels regardless of the architecture and simply discards some levels based on the architecture's requirement.

Each table is 4096 bytes or 0x1000. The entries are 64 bytes each. Each table can have 512 entries (0x200). Some of the tables--particularly PGD and PMD have entries that are offset. In other words, instead of starting at position 0 in the table, the entries are 0 until halfway or even 3/4 of the way through the table. I'm trying to understand why that is.

This paragraph gives me a hint (maybe I'm wrong) that your question is regarding the x86-64 architecture. On x86-64 there is 4 levels of page tables. Paging is partially implemented by hardware in that the MMU of the processor will automatically cross the page tables to translate virtual addresses to physical ones. It is also partially implemented by software (the operating-system) in that the OS will fill the page tables and such.

There are several reasons why some portions of the page tables could be zero. What I'm thinking of is maybe the portion of the memory represented by the page table entry is not in the address space of the process. This means that a user mode process can access this address but it will trigger a page fault and the kernel should thus kill the process.

Also, if it is a kernel page table, it could only be that a portion of the virtual address space was currently unused by the kernel and can thus be discarded by placing zeroes in the different entries. Several reasons can explain why some portions of the page tables are zero.

It is certain that it is always a good idea to fill the page tables with zeroes before "giving" the page table to a user mode process because otherwise an access that touches the address space of another process could happen and this would be a security threat. For example, if you have an entry in the page tables of a user mode process that wasn't zeroed out, you could have a process which accesses that virtual address. It could have the present bit set (it would not trigger a page fault) and could translate to the address space of another process. This would be a vulnerability.

Don't forget that page tables are also memory protection because they isolate one process from another in that the page tables should not translate to addresses belonging to another process. They also have the user vs supervisor bit which allows to isolate user mode from the kernel.

As to paging, the 4 level paging scheme on x86-64 has PML4, PGD, PDT and PT. The virtual address looks like the following (in binary):

  Index in PML4    Index in PGD   Index in PDT    Index in PT     Offset in physical frame (12 bits)
0b000000000        000000000      000000000       000000000       000000000000

Here I represented only 48 bits because the upper 16 bits are unused (unless 5 level paging is enabled which is present on newer processors). Basically, each 9 bits is an index/offset in the corresponding page table. The 12 least significant bits are the offset in the physical frame. Linux simply gave general names to its page tables because it supports several architectures. The names on Linux are PGD, PUD (Page Upper Directory), PMD and PTE.

The page table entry points to another page table which will be used as the table for the translation using the offset found in the virtual address.

Hope this clears any misconceptions! Feel free to comment for anything.