Paging for Beginners: How Your Kernel Controls Memory

Paging often looks intimidating because it introduces several new ideas at once: virtual addresses, physical addresses, page tables, mappings, permissions, and page faults.

The basic idea, however, is simple:

Paging lets the kernel decide where every memory address leads.

This article explains that idea step by step for a beginner building an x86-64 operating system.

Physical Memory

Physical memory is the RAM installed in the computer. Each byte has a physical address.

For example:

Physical address 0x00100000
Physical address 0x00100001
Physical address 0x00100002

Without paging, programs would need to work directly with these physical addresses. That creates serious problems. Two programs might try to use the same memory, a program could overwrite the kernel, and programs would need to know exactly where they were loaded in RAM.

Paging gives the kernel control over these addresses.

Virtual Memory

When paging is active, programs normally use virtual addresses instead of physical addresses.

The processor asks the kernel's page tables how each virtual address should be translated:

Virtual address -> Page tables -> Physical address

For example, the kernel could create this mapping:

Virtual address 0x00400000 -> Physical address 0x01200000

A program accesses 0x00400000, but the processor actually reads or writes RAM at physical address 0x01200000. The program does not need to know where its memory is physically located.

Different programs can even use the same virtual address:

Program A: 0x00400000 -> Physical 0x01200000
Program B: 0x00400000 -> Physical 0x02800000

Both programs believe they are using address 0x00400000, but they are using different areas of RAM. That is how paging helps keep processes separate.

Pages and Frames

Paging manages memory in blocks instead of individual bytes.

A block of virtual memory is called a page. A block of physical memory is often called a frame.

The standard page size on x86-64 is 4 KiB, which is 4096 bytes.

Virtual page -> Physical frame

Because pages are 4096 bytes, page addresses must normally be aligned to 4096-byte boundaries.

These addresses are page-aligned:

0x0000
0x1000
0x2000
0x3000

This address is not page-aligned:

0x2345

The lowest 12 bits of an address select a byte inside a 4 KiB page.

For example:

Virtual address: 0x00401234
Page begins at:  0x00401000
Offset in page:  0x234

If virtual page 0x00401000 maps to physical frame 0x01200000, then:

Virtual 0x00401234 -> Physical 0x01200234

The offset stays the same. Paging changes which frame contains the page, not the position inside that page.

What Is a Page Table?

A page table is a data structure that tells the processor how virtual pages map to physical frames.

You can imagine it as a large translation list:

Virtual page      Physical frame
0x00400000   ->   0x01200000
0x00401000   ->   0x00800000
0x00402000   ->   0x03000000

Each mapping also contains permission flags. These flags can say whether a page may be written to, executed, or accessed by a user program.

Real x86-64 page tables are not stored as one enormous list. They are arranged in several levels.

Why Are There Several Levels?

A complete list of every possible virtual page would consume a huge amount of memory, even if most of the address space were unused.

Instead, x86-64 uses a tree of page tables. The normal four-level structure is:

PML4
  `-- PDPT
        `-- Page Directory
              `-- Page Table
                    `-- Physical frame

You may also see the shorter names:

PML4 -> PDPT -> PD -> PT -> Frame

Each table is one 4 KiB page and contains 512 entries.

An entry in one level points to a table in the next level. The final page-table entry points to the physical frame containing the actual data.

You do not need to memorize all four levels immediately. The important idea is that the processor follows a chain of entries until it reaches the physical frame.

Dividing a Virtual Address

For a normal four-level x86-64 address, different groups of bits select entries from the four tables:

Virtual address
+------------+------+------+------+------+--------+
| Sign bits  | PML4 | PDPT |  PD  |  PT  | Offset |
+------------+------+------+------+------+--------+
               9      9      9      9      12 bits

The indices can be calculated like this:

uint64_t pml4_index = (address >> 39) & 0x1FF;
uint64_t pdpt_index = (address >> 30) & 0x1FF;
uint64_t pd_index   = (address >> 21) & 0x1FF;
uint64_t pt_index   = (address >> 12) & 0x1FF;
uint64_t offset     = address & 0xFFF;

The value 0x1FF keeps nine bits. Nine bits can represent values from 0 to 511, which selects one of the 512 entries in a table.

The processor effectively performs these steps:

1. Select an entry from the PML4.
2. Follow it to a PDPT.
3. Select an entry from the PDPT.
4. Follow it to a page directory.
5. Select an entry from the page directory.
6. Follow it to a page table.
7. Select an entry from the page table.
8. Use that entry to find the physical frame.
9. Add the offset from the original address.

The processor performs this work automatically. The kernel's job is to construct the tables correctly.

Page-Table Entries

Each page-table entry is a 64-bit value containing a physical address and several flags.

Some of the most useful flags are:

• Present: The entry is valid and may be used.
• Writable: Code may write through the mapping.
• User: User-mode programs may access the mapping.
• No-execute: Instructions may not be executed from the page.
• Accessed: The processor has accessed the page.
• Dirty: The processor has written to the page.

Some basic flag definitions might look like this:

#define PAGE_PRESENT  (1ULL << 0)
#define PAGE_WRITABLE (1ULL << 1)
#define PAGE_USER     (1ULL << 2)
#define PAGE_NOEXEC   (1ULL << 63)

#define PAGE_ADDRESS_MASK 0x000FFFFFFFFFF000ULL

A simple page-table entry could be created like this:

entry = physical_address | PAGE_PRESENT | PAGE_WRITABLE;

The physical address must be page-aligned. The bottom 12 bits are available for flags because those bits are zero in an aligned address.

The Root Page Table

The PML4 is the root of an x86-64 address space.

The processor's CR3 register contains the physical address of the active root page table:

CR3 -> PML4 -> PDPT -> PD -> PT -> Frame

Changing CR3 lets the kernel switch to a different address space.

A kernel can therefore give every process its own PML4. When the scheduler changes processes, it can load the next process's root table into CR3.

If your bootloader starts the kernel in 64-bit mode, paging is already enabled. The bootloader may give you an existing paging setup that you can inspect, extend, or replace.

Allocating Page Tables

Page tables occupy physical memory, so the kernel needs a way to allocate physical frames.

At first, this allocator can be simple. It only needs to find an unused 4 KiB frame and return its physical address.

Every new page table must be cleared:

void *allocate_page_table(void)
{
    void *table = allocate_physical_page();
    memset(table, 0, 4096);
    return table;
}

Clearing the table is essential. Random data might contain the Present flag, causing the processor to interpret garbage as valid mappings.

There is one complication: a page-table entry stores a physical address, but C code normally accesses memory through virtual addresses.

Your kernel therefore needs some way to access a table after allocating it. Common solutions include:

• Identity-mapping the table
• Mapping all physical memory into a kernel region
• Temporarily mapping the required frame
• Asking the bootloader for a physical-memory mapping

For a first kernel, having a known virtual address where physical memory is mapped is usually the easiest approach.

Mapping One Page

To map a virtual page, the kernel walks through the four levels. If an intermediate table does not exist, the kernel allocates one.

The general algorithm is:

1. Find the required PML4 entry.
2. Create its PDPT if it is missing.
3. Find the required PDPT entry.
4. Create its page directory if it is missing.
5. Find the required page-directory entry.
6. Create its page table if it is missing.
7. Put the physical frame and flags in the final entry.

Simplified pseudocode looks like this:

bool map_page(
    page_table_t *pml4,
    uint64_t virtual_address,
    uint64_t physical_address,
    uint64_t flags)
{
    if (!is_page_aligned(virtual_address))
        return false;

    if (!is_page_aligned(physical_address))
        return false;

    page_table_t *pdpt =
        get_or_create_table(pml4, pml4_index(virtual_address));

    page_table_t *pd =
        get_or_create_table(pdpt, pdpt_index(virtual_address));

    page_table_t *pt =
        get_or_create_table(pd, pd_index(virtual_address));

    uint64_t *entry = &pt->entries[pt_index(virtual_address)];

    if (*entry & PAGE_PRESENT)
        return false;

    *entry = physical_address | flags | PAGE_PRESENT;
    invalidate_page(virtual_address);
    return true;
}

In a real implementation, get_or_create_table must check the Present flag, allocate and clear a table when needed, store the table's physical address, and return a virtual address the kernel can access.

Identity Mapping

An identity mapping uses the same virtual and physical address:

Virtual 0x00100000 -> Physical 0x00100000

Identity mappings are useful during early startup. If the processor switches to a new set of page tables, the currently running code and stack must still be mapped. Otherwise, the processor will be unable to fetch its next instruction or access the stack.

A beginner-friendly first paging setup might identity-map:

• The kernel's current physical location
• The kernel stack
• The page tables themselves
• Boot information that the kernel still needs
• Early display or serial hardware memory

After the kernel has moved to its final virtual-memory layout, unnecessary identity mappings can be removed.

The Higher-Half Kernel

Many kernels place themselves in the upper part of virtual memory. This is called a higher-half kernel.

For example:

Kernel virtual address -> Physical address
0xFFFFFFFF80000000     -> 0x00100000

The kernel can live at a high virtual address even if it was loaded near the beginning of physical RAM.

This gives you a clean layout:

Lower virtual addresses -> User programs
Upper virtual addresses -> Kernel

You do not need a higher-half kernel for your first paging experiment. Start with an identity-mapped kernel if that makes debugging easier. Move the kernel higher once basic mapping and page faults work reliably.

Page Permissions

Paging is not only about translation. It also protects memory.

A sensible layout uses different permissions for different kinds of memory:

Kernel code      Readable and executable
Kernel data      Readable and writable
Kernel stack     Readable and writable
User code        User-accessible and executable
User data        User-accessible and writable

Writable data should normally not be executable. Kernel pages should normally not be accessible from user mode.

The User flag must permit access at every level of the page-table path. Setting it only in the final page-table entry is not enough if an earlier entry blocks user access.

It is acceptable to begin with simple permissions while bringing up the kernel. Once paging works, tighten them so memory is only writable or executable when necessary.

Page Faults

A page fault happens when the processor cannot complete a virtual-memory access.

Common causes include:

• The requested page is not present.
• Code attempted to write to a read-only page.
• A user program attempted to access kernel memory.
• The processor attempted to execute a non-executable page.
• A page-table entry contains an invalid combination of bits.

When a page fault occurs, the processor places the faulting virtual address in the CR2 register. It also provides an error code describing the kind of access.

An early page-fault handler can simply print useful information and stop:

void page_fault_handler(
    interrupt_frame_t *frame,
    uint64_t error_code)
{
    uint64_t address = read_cr2();

    print("Page fault!\n");
    print("Address: ", address);
    print("Error:   ", error_code);
    print("RIP:     ", frame->instruction_pointer);

    halt();
}

Install this handler before experimenting with complicated mappings. A readable page-fault message is much more helpful than a silent reset.

Later, page faults can become useful. The kernel might allocate memory only when a program first accesses it or copy a shared page when a process tries to modify it. For a first implementation, focus on detecting and reporting faults correctly.

The TLB

Page-table walking takes time, so the processor caches recent translations in the Translation Lookaside Buffer, usually called the TLB.

Suppose you change this mapping:

Before: Virtual 0x4000 -> Physical 0x8000
After:  Virtual 0x4000 -> Physical 0xA000

The processor may still have the old translation cached. You must invalidate it after changing the active page tables.

For one page, x86-64 provides the invlpg instruction:

static inline void invalidate_page(uint64_t address)
{
    __asm__ volatile (
        "invlpg (%0)"
        :
        : "r"(address)
        : "memory"
    );
}

Reloading CR3 can invalidate a larger set of cached translations.

For a first single-core kernel, invalidating a modified page is usually enough. Multiprocessor kernels require additional work because other CPU cores may also have cached the old translation.

Unmapping a Page

Unmapping removes a virtual-to-physical mapping.

The basic steps are:

1. Walk the tables to find the final entry.
2. Check whether it is present.
3. Clear the entry.
4. Invalidate the virtual address from the TLB.
5. Free the physical frame if the mapping owns it.

Be careful with the final step. More than one virtual address can map the same physical frame:

Virtual 0x4000 -> Physical 0x9000
Virtual 0x8000 -> Physical 0x9000

Removing the first mapping does not mean the physical frame is unused. The second mapping still needs it.

A larger kernel can solve this with reference counting or clear ownership rules.

Large Pages

Besides normal 4 KiB pages, x86-64 supports larger pages:

• 2 MiB pages
• 1 GiB pages on supported processors

Large pages can reduce the number of tables needed for large regions. They can be helpful for mapping the kernel or a large area of physical memory.

However, they require larger aligned regions and provide less precise control over permissions.

For your first paging implementation, use 4 KiB pages. Add large pages only after normal mappings work.

Common Beginner Mistakes

Paging bugs can cause page faults, general-protection faults, freezes, or complete machine resets.

Check these common mistakes first:

• A newly allocated page table was not cleared.
• A physical address was confused with a virtual address.
• The current kernel code was not mapped.
• The current stack was not mapped.
• A page or table address was not properly aligned.
• The Present flag was forgotten.
• A page-table entry contains unsupported bits.
• The TLB was not invalidated after changing a mapping.
• The kernel tried to access a physical frame that had no virtual mapping.
• User access was enabled in the final entry but blocked by an earlier level.
• A physical frame was freed while another mapping still used it.

Log each page-table allocation and mapping while debugging:

Allocated PT at physical 0x00300000
Mapped virtual 0xFFFFFFFF80000000
     to physical 0x00100000
Flags: present, executable, read-only

Simple logging can turn a mysterious crash into an obvious incorrect address.

A Good Implementation Order

Build paging in small stages:

1. Create a basic physical-frame allocator.
2. Create and clear a PML4.
3. Identity-map the running kernel and stack.
4. Switch to or extend the new page tables.
5. Install a page-fault handler.
6. Implement a function that maps one 4 KiB page.
7. Implement page lookup and unmapping.
8. Add proper writable and executable permissions.
9. Map the kernel at its final virtual address.
10. Create a separate address space for a test user program.
11. Add advanced features only after the basics are reliable.

Test after every step. Paging becomes much harder to debug when several untested features are introduced at the same time.

Final Mental Model

If the details become overwhelming, return to this simple picture:

A program provides a virtual address.
              |
The processor divides it into table indices.
              |
The processor follows the page-table entries.
              |
The final entry identifies a physical frame.
              |
The page offset identifies a byte in that frame.

The kernel creates the tables. The processor follows them.

Start by mapping one page correctly. Then map the kernel. Once you can deliberately create a mapping, access it, remove it, and receive a useful page fault, you have the foundation of a real virtual-memory manager.