Page Table Hacking in P.O.S.

This post covers what I think is a clever way to handle the paging data used in 32 bit x86 architectures, specifically when PAE is not enabled. It requires 4MB of the linear address range (<0.1%) and is trivially easy to setup.

In order to access the memory associated with a linear address LA, the CPU must figure out what physical address PA coresponds to that linear address. This is done through some paging circutry that maps linear pages (aligned 4K regions of the linear address range) to physical page frames (aligned 4K regions of the physical RAM.) This circutry uses a 2-level tree of tables that are stored in RAM. The root node of this tree is called the page directory, it contains 1024 pointers to the physical addresses of the secondary tables (called page tables) and the page directory takes up one page frame (4K = 1024 entries x 4 bytes per entry.) The CPU keeps track of the physical location of the page directory in the cr0 CPU register. The page tables pointed to by the page directory have the same structure: 1024 pointers to the physical addresses of individual page frames. (The pointers used in these tables are only concerned with the address of a page frame, which are aligned on 4K boundaries, so the bottom 12 bits aren't useful for finding a page and are instead used as flags and to controll permissions and things like special large 4M pages that I won't go into here.)

It's important to note here that the structure of the page directory and the page tables are identical.

With 1024 entries in the page directory (the root node) and the page tables (the leaf nodes), 10 bits of the address can be used as an index into these tables. The way this works in practice is to use the highest order 10 bits of LA as the index for the page directory, and the next 10 bits of LA as the index in the page table. This is enough to get a physical page frame (as I'll show below), and then the last 12 bits of LA are used as an offset within that page frame. We can break LA down, then, into 3 values: the highest order 10 bits will be called LAd (d for directory), the next 10 will be called LAt (t for table) and the last 12 will be called LAo (o for offset).

A single entry in a page table points to a single page frame (4K). Since a page table has 1024 of these entries, each page table maps 4M of the linear address range. Similarly, since each page table maps 4M, each entry in the page directory (which points to a page table) is associated with that 4M of the linear address range, and there being 1024 of these entries in the page directory, the entire page directory maps 4G of linear addresses, which is what we'd expect with 32 bit addresses.

For the sake of shorter examples, let's call the physical address of the page directory PD.

In order to convert the linear LA into the physical address PA, the CPU computes the following: PT (page table) = PD[LAd]; PF (page frame) = PT[LAt]; PA = PF + LAo.


What would happen if an entry in the page directory pointed to the page directory itself, rather than to a page table?

Let's assume that the last entry in PD points to PD itself (PD[0x3FF] = PD).

Now, let's figure out what memory we would be reading to/writing from if we used the linear address LA=0xFFFFFF004. Using the above notation, LAd=0x3FF, LAt=0x3FF, LA0=0x001;

First, PT = PD[PAd] = PD[0x3FF] = PD.
Then, PF = PT[LAt] = PD[0x3FF] = PD.
Finally, PA = PF + LAo = PD + 0x004

So, the linear address 0xFFFFF004 points to 4 bytes after the beginning of the page directory. Treating the page directory as an array of 1024 4-byte objects, this then coresponds to the 2nd entry in the page directory. Interpret LA as a pointer to an entry in a page directory, and *LA equates to the physical address of the page table used to map the 2nd 4MB range of linear addresses.

What about the linear address LA = 0xFFC02008? Here, LAd = 0x3FF, LAt = 0x002, LAo = 0x00B.
First, PT = PD[PAd] = PD[0x3FF] = PD.
Then, PF = PT[LAt] = PD[0x002]
Finally, PA = PF + LAo = PD[0x002] + 0x00B.

Now, the physical address you get coresponds to the 4th entry in the page table pointed to by the 3rd entry in the page directory, or, the entry that handles which physical page is used for all memory reference in the range 0x00C08000 through 0x00C08FFF.

So, if PD[0x3FF] = PD, you can do the following:

To control what physical page some 4K linear page (LA) is mapped to, write to the linear address:
0xFFC00000|((LA&0xFFFFF000)>>10)

To control which page frame the page directory points to for use as a page table for some 4MB region of linear addresses (LA), write to the linear address:
0xFFFFF000|((LA&0xFFC00000)>>20)

If one ever writes to 0xFFFFFFFC, it will break this system.

This will work on any system, even ones that use trees that are 3 or 4 levels deep, so long as the following 2 conditions hold:

1. Each 'node' in the tree is the same size, and covers the same number of bits in the linear address.
2. The size of the nodes is the same as the size of the page frames pointed to by the leaf nodes.

This doesn't seem to be an option on x86_64 machines, but I haven't looked too much into that (as I'm writing code on a 32 bit machine, I'm not worried)