Memory on x86


What even is a pointer? What happens in the CPU when I make a memory access? That's quite a long story, let me tell you.

A simplified high-level overview of memory in x86. Suggestions or corrections? Email me!

Segmented Memory

In the Paleolithic Era (40 years ago) computers had a problem, and that problem was processes. If I have multiple processes running at the same time, and they all try to share the same memory, it gets to become a bit of dumpster fire quite quickly. What was needed was a way to chunk up memory into pieces and to allocate those pieces to each process.

Enter, memory segmentation! How memory segmentation works is quite simple. You have these memory segments, defined by their base address (where they start) and their size (how big). In x86 there are 6 memory segments: code, data, stack, extra, G, and F. Each memory segment gets a register CS, DS, SS, ES, GS, FS.

The function of these registers is dependent on the operating mode of the CPU. There are three modes in x86: real-mode, protected mode, and long mode. Real-mode is an ancient mode used when 16-bit was still the norm, protected mode is old but slightly less old and used for 32-bit, finally, long-mode is the what we all use today, and it is 64-bit. Real-mode and protected mode can use memory segmentation, while long mode and protected mode can use paging.

Paging is in its own section below, which we will get to (be patient!). Here, I will explain memory segmentation in both real-mode and protected mode. They are both very similar but differ in how memory segments are defined.

Real-mode

In real-mode each memory segment has a fixed size, 64KB, and the start of each memory segment is stored in the segment registers (CS,DS,SS,etc.). Whenever the CPU tries to do a memory access, that access address is offset by the base address of a memory segment. The type of operation you're performing changes the memory segment that the CPU will offset by.

If the CPU tries to pop from the stack, it takes the stack pointer as the lower 16-bits of a 20-bit address, and the stack segment register (SS) as the upper 16-bits of a 20-bit address, then adds them to get the effective address.

Because the offset into the memory segment is treated as the lower 16-bits of a 20-bit address, and the segment registers are treated as the upper 16-bits of a 20-bit address; Real-mode, despite being 16-bit, can address up to 20-bits or 1MB.

The OS swaps out these segment registers depending on the currently executing process. The same address can mean different things to different processes because they have different values in the segment registers.

Note that real-mode doesn't prevent segments from overlapping and doesn't stop processes from overwriting each others memory!

Protected mode

Unlike real-mode, protected mode doesn't lock you into 64KB segments, and allows each segment to have any size and/or different permissions (like read but not write) which is why it's called protected mode, it enforces permissions that protect you! If you try to violate these permissions, you'll get a segmentation fault or segfault.

Instead of storing the base address of each segment in the segment registers, in protected mode the segment registers contain an index into a list of "Segment Descriptors". Each segment descriptor contains the start of a segment and its size, followed by some permission bits that tell you what you're allowed to do with it.

There are actually two lists: the "Global Descriptor Table" (GDT) and "Local Descriptor Table" (LDT). What's the difference? Well the GDT isolates memory between the OS and the application, while the LDT isolates memory between threads. The segment descriptor tables are just structs in memory. You initialize the struct in memory somewhere, then you give the CPU a pointer to its location by setting LDTR/GDTR (LDT Register/GDT Register) with the the LGDT/LLDT instructions (Load GDT/Load LDT). Then when the CPU wants to know where something is, it reads the descriptor tables that the LDTR/GDTR hidden registers point to.

In protected mode, the segment base address is 32-bit. Unlike real-mode, instead of having to add the upper 16-bits of a 20-bit base address with the lower 16-bits of a 20-bit offset, the 32-bit base address and 32-bit offset are simply added together to get the effective address. This means protected mode can address up to 32-bits or 4GB.

Now, instead of modifying the base address in the segment registers, the OS modifies the indexes in the segment registers and the descriptor tables in memory.

Paged Memory

With paging, memory is partitioned into 4KB blocks called pages. They don't have to be 4KB though, some processors allow for "huge pages" where some pages may be 4MB or even 1GB.

Each process gets its own paged address space that no other process can see, called virtual memory. With virtual memory each process can be in its own isolated environment. Virtual memory pages are mapped to physical memory pages by the OS using a structure called a page table. Page tables, despite the name, are actually trees.

Protected mode (32-bit)

In protected mode, the page table has two levels. The page directory entry (PDE) is the topmost level, it is essentially a list of pointers to page table entries, alongside some access bits and various flags. A page table entry (PTE) is essentially a list of pointers to the actual page, alongside some more access bits and various flags. Together they form a tree-like structure with a depth of 2. Each table entry contains 1024 4-byte (32-bit) items, making each table 4KB big.

Consult the amazing diagram.

                         ┌──────────────────────┐
                         │ Page Directory Entry │
                         └──────────────────────┘
                        /           │            \
    ┌──────────────────┐   ┌──────────────────┐
    │ Page Table Entry │   │ Page Table Entry │   ...
    └──────────────────┘   └──────────────────┘
       |        |     \
    ┌──────┐ ┌──────┐ ┌──────┐
    │ Page │ │ Page │ │ Page │   ...
    └──────┘ └──────┘ └──────┘

Now we can look at the structure of a 32-bit pointer.

    ┌───────────┬───────────┬────────┐
    │ PDE Index │ PTE Index │ Offset │
    └───────────┴───────────┴────────┘
    ├───────────┼───────────┼────────┤
       10-bit      10-bit     12-bit

When the CPU wants to translate a virtual address into a physical address. It first indexes into the PDE using the PDE index, which gives it a pointer to the PTE. Then it indexes into the PTE using the PTE index, which gives it a pointer to the page. Then it offsets into that page using the page offset, to get the exact byte you're looking for. If the permission bits are violated or the page does not exist, the CPU will throw a segfault, which the OS will have to catch. We still call it segfault even though we're using pages instead of segments, this is mainly just a vestige of the past.

The page table indexes are all 10 bits because each level is a list of 1024 entries. 210 = 1024.

The OS informs the CPU about the location of the page table through the CR3 register (control 3), which holds a pointer to the PDE. When switching between process address spaces, the OS changes the CR3 register to point to a different table. Additionally, the OS may need to flush caches or use the invlpg instruction to invalidate pages.

Protected mode with paging can address up to 4GB.

Physical Address Extension (PAE)

If the CPU supports it and Physical Address Extension (PAE) is enabled, an additional level is added above the PDE: the Page Directory Pointer Table (PDPT) is a list of 4 64-bit entries, making it 32 bytes in size. The PDE and PTE are now lists of 512 64-bit entries, and are still 4KB in size.

With PAE enabled, the virtual address space is still 4GB but you can now have up to 4PiB (Petabyte!) of physical address space.

Long mode (64-bit)

Long mode works in almost exactly the same way as protected mode, except a few things:

Alongside PDPT, PDE, and PTE, there is a fourth page table level, Page Map Level 4 (PML4). Additionally, if the processor supports it and it is enabled, you can have a fifth page table level, PML5. Every level is now a list of 512 64-bit entries, making them all 4KB.

Consult the amazing diagram for 4 levels of paging.

              ┌──────┐
              │ PML4 │ <- 512 entries, each 64-bit (4KB)
              └──────┘
            /    |    \
              ┌──────┐
        ...   │ PDPT │   ...
              └──────┘
            /    |    \
              ┌─────┐
        ...   │ PDE │   ...
              └─────┘
            /    |    \
              ┌─────┐
        ...   │ PTE │   ...
              └─────┘
            /    |    \
     ┌──────┐ ┌──────┐ ┌──────┐
     │ Page │ │ Page │ │ Page │   ...
     └──────┘ └──────┘ └──────┘

Now we can look at the structure of a 64-bit pointer for 4 levels of paging. Each page table index is now 9-bit, because each level has 512 entries and 29 = 512.

    ┌───────┬───────┬───────┬───────┬───────┬────────┐
    │  ???  │ PML4  │ PDPT  │  PDE  │  PTE  │ Offset │
    └───────┴───────┴───────┴───────┴───────┴────────┘
    ├───────┼───────┼───────┼───────┼───────┼────────┤
     16-bit   9-bit   9-bit   9-bit   9-bit   12-bit

But... now we have all this empty space in the upper 16-bits of our pointer. Turns out, 64-bit pointers in x86 just have empty space at the top of them, and of course, we can use this empty space! This is exactly how pointer tagging works. But there are some caveats, the CPU needs our pointer to be "canonicalized" before it will let us dereference it, so we can put whatever data we want in the upper 16-bits as long as we canonicalize the pointer before accessing the data at the end of it.

In x86 pointer is canonical if its upper 16-bits are set to either all 0s or all 1s.

All zeroes

    *(ptr & !(0xffff << 48))

Or all ones

    *(ptr |  (0xffff << 48))

On a 5-level paging scheme the upper 7-bits are unused.

Recursive Mapping

The OS exists in a virtual address space too, and it needs to map the page tables into its virtual address space to be able to modify them. There's a neat trick to do this easily by making the top-level page table point to itself.

Imagine we have a 4-level paging scheme, where the last entry of PML4 (the entry at index 511) points to itself.

A pointer to a byte in a specific page would look like this.

    ┌───────┬───────┬───────┬───────┬────────┐
    │ PML4  │ PDPT  │  PDE  │  PTE  │ Offset │
    └───────┴───────┴───────┴───────┴────────┘

The CPU indexes into PML4, then PDPT, then PDE, then PTE, then offsets into the page.

But look what happens when we do this:

    ┌───────┬───────┬───────┬───────┬────────┐
    │  511  │ PML4  │ PDPT  │  PDE  │ Offset │
    └───────┴───────┴───────┴───────┴────────┘

The CPU indexes into the 511th entry of PML4, which is PML4, then it indexes into PML4 again, then PDPT, then PDE, then offsets into PTE. We can now access and modify a PTE!

If we want to access a PDE we just do it again.

    ┌───────┬───────┬───────┬───────┬────────┐
    │  511  │  511  │ PML4  │ PDPT  │ Offset │
    └───────┴───────┴───────┴───────┴────────┘

The CPU indexes into the 511th entry of PML4, which is PML4, then it indexes into the 511th entry of PML4, which is PML4, then it indexes into PML4, then PDPT, then offsets into PDE.

This only really works if every page table level is in the same format, which it is on long mode since every table is 4KB of 512 64-bit entries.

Where Do We Go From Here???

I wrote this because while implementing an OS following this blog post, I found a lot of the documentation on x86 paging was too specific. I just wanted a nice high level overview of what paging even is before getting into all the nitty gritty details of registers, and structs, and bit flags I need to flip.

But, if you're up for the challenge, I think you're ready for all those nitty gritty details now. You'll want to be looking at osdev.org - X86 Paging, you'll notice the website is eerily similar (hehe). Additionally, there's this x86 Paging Tutorial which I have not read but on skimming seems like it may be useful to you.

Good luck!