Page tables in plain words

A program never touches real memory addresses. It uses virtual addresses, and the CPU translates each one to a physical address before the access happens. Page tables are the data the CPU reads to do that translation. They are not code. They are tables in memory, written by the kernel, read by the hardware on every access.

That split is the whole idea. The kernel decides which virtual pages map to which physical pages, and with what permissions. The CPU enforces the decision on every load and store.

One address, two parts

Translation works at page granularity. On x86-64 a normal page is 4096 bytes. The low 12 bits of a virtual address are the offset inside the page, and they pass through unchanged. The remaining bits are an index chain. They tell the CPU which entries to read.

With four level paging, the virtual address above the offset splits into four fields of 9 bits each. Each field indexes one table. The first table is pointed to by the CR3 register. Read entry one, it gives the address of the next table. Read entry two in that table, it gives the next table. After four reads you reach an entry that holds a physical page frame plus permission bits. Add the offset, and you have the physical address.

Nine bits means 512 entries per table, and each entry is 8 bytes, so one table is exactly one page. That fit is not an accident.

Why not one flat table

A flat table for a 48 bit virtual space would need one entry for every possible page. Almost every program uses a small part of its address space, in a few separate regions. Code in one place, heap in another, stack somewhere else, with large empty gaps between them.

A tree solves that. Empty regions need no lower tables at all. The top level entry for an unmapped region is marked not present, and no memory is spent below it. A process with three real regions pays for a few tables, not for the whole space. The cost is the walk. Up to four memory reads stand behind a translation, before the access itself.

The TLB is the cache for the walk

Four reads per access would be too slow, so the CPU caches finished translations in the TLB. When a translation is already there, the walk does not happen. Most accesses in a running program hit the TLB, because programs reuse the same pages for long stretches.

This is why changing a mapping has a second step. Editing a page table entry changes memory, but the CPU may still hold the old translation in its TLB. The kernel has to invalidate that entry, and on a multiprocessor system it may have to invalidate it on other cores too. A mapping change that forgets the invalidation looks like a bug where the old page refuses to go away. The table is right. The cache is stale.

Large pages skip levels

The walk can stop early. If an entry in the third level table has its large page bit set, it maps a 2 MB page directly, and the bits below the offset widen to 21. At the second level, the same trick maps 1 GB. Large pages use fewer TLB entries for the same memory, which helps big, dense workloads. They cost granularity. You cannot set different permissions for two 4 KB parts of one 2 MB page, because there is only one entry and one set of permission bits.

Permissions live in the entry

Each entry carries more than an address. A present bit says whether the mapping exists at all. Read and write bits, user and supervisor bits, and the no execute bit decide what kind of access is allowed. The CPU checks them on every access, including accesses from code that never asked for a check.

When a check fails, or when the present bit is clear, the CPU raises a page fault and hands the kernel the faulting address in CR2, plus an error code that says what kind of access failed and why. The kernel then decides. Grow the stack, load the page from storage, map a fresh zero page, or kill the process because the address was never valid. The same fault mechanism covers ordinary demand paging and real bugs. The error code and the address are how you tell them apart.

How I read a translation bug

When memory looks wrong, I check the walk before I check the code. Is CR3 pointing at the table I think it is. Some systems keep more than one top level table, and reading the right entries in the wrong table gives clean, wrong answers. Then I walk the address by hand, one level at a time, and write down each entry, its frame, and its permission bits. I compare that against the physical page I expected.

Most of the bugs I have found this way were plain. An entry written at the wrong index because the field was shifted by 12 instead of 9. A new table page used before it was zeroed, so old bytes read as valid entries. A mapping updated in the table while the TLB kept the old one. None of these show up if you only look at the virtual address. They all show up in the walk.

Page tables look abstract until you walk one address yourself. After that they read as what they are. A tree of tables, a cache in front of it, and a set of permission bits the hardware checks for you on every single access.