Physical Memory, Page Tables, and Allocation

By the end of this lesson, you will be able to...

• Distinguish a physical frame, a virtual page, and a page-table mapping.

• Trace a valid user-memory access from an absent mapping through allocation, mapping, and instruction retry.

• Locate the ownership or permission error in a small page-map ledger.

Idea in one sentence: Physical memory provides scarce frames, while page tables give each program a private, permission-checked story about which frames its virtual addresses mean.

calc has entered the kernel through a trap and returned safely. Now it grows an array, receives virtual address 0x4000, and stores a number at 0x4008. The number looks like a normal pointer to the program. It is not yet a promise that any RAM exists there.

The processor tries to translate the address. It finds no usable mapping. A page fault enters the trap path from lesson 003. This time the kernel has a choice: is this an invalid access that should end calc, or a valid request for another page of its memory? If it is valid, the kernel must find a free physical frame, record who owns it, create a permission-checked mapping, make the translation visible to the processor, and then retry the original store.

That sequence is the small engine beneath process memory. It explains how two programs can both use address 0x4000 without sharing the same bytes, why an address range can exist before RAM is committed to it, and why a forgotten page-table update can look like a mysterious repeated fault.

Core Insight

Memory management has three different objects. Keeping them separate prevents most early confusion.

On a common RISC-V system, the base page size is 4 KiB. A virtual address is therefore naturally split into a page-aligned portion and an offset. For 0x4008, the virtual page is 0x4000 and the offset is 0x008. If a page-table entry maps that virtual page to physical frame 0x80204000, the resulting physical address is 0x80204008.

Plain meaning:

RAM is a limited collection of numbered boxes. A page table is a per-address-space lookup table that says which box a program's page name refers to and what it may do with it.

In this scenario:

calc calls its new page “0x4000.” The kernel allocates one real 4 KiB box and gives that page name a mapping to it. Another process may also use virtual 0x4000, but its lookup table can point to a different box.

Technical name:

The real box is a physical page frame; the lookup structure is a page table; the cache of recent translations inside the processor is a TLB (translation lookaside buffer).

Frames Are Resources; Mappings Are Policy

The page allocator owns the supply of physical frames. At boot, the kernel learns which regions are RAM and which regions are reserved for firmware, kernel code, device memory, or other platform use. It puts the usable page-aligned frames on a free list, bitmap, buddy tree, or another allocation structure.

A minimal allocator can answer two questions:

allocate_frame() -> one free, page-aligned physical frame or failure
free_frame(frame) -> return exactly one owned frame to the free pool

That is deliberately smaller than a general heap. The allocator in this lesson manages whole frames. Lesson 005 will use these frames to build longer-lived kernel objects and will make cleanup ownership more explicit.

Page-table code decides whether a virtual page is mapped, which frame it reaches, and which permissions apply. A leaf page-table entry on RISC-V records a physical page number and flags such as valid, read, write, execute, and U-mode access. Page tables themselves also occupy physical frames.

This separation gives a useful invariant:

Every allocated frame has one clear current owner, and every present mapping points only to a frame that remains allocated for as long as the mapping can be used.

If a mapping points to a frame returned to the free list, a later allocation can reuse that RAM. One process may then read or write bytes belonging to an unrelated process or the kernel. If a frame is allocated but no mapping or owner ledger records it, the frame leaks. The page-table bits are not administrative decoration; they connect isolation policy to physical ownership.

The Naive Model: A Pointer Is a Physical Location

The naive model says that address 0x4008 names a particular byte in RAM. That would make every program compete for the same numeric addresses. It would also make moving a program, sharing read-only code, reserving sparse regions, and protecting kernel memory much harder.

The protected model makes a pointer meaningful only together with an active address space. The root of that address space is selected by satp on RISC-V when paged translation is active. satp identifies the root page table and the translation mode; the processor walks the page tables or finds a cached answer in the TLB.

For a 64-bit RISC-V kernel using Sv39, a virtual address contains three virtual-page-number fields and a 12-bit page offset. The processor uses the fields to walk three levels of page-table pages. A non-leaf entry points to the next page-table level. A leaf entry supplies the physical frame and permissions. You do not need to memorize every bit position yet. What matters is the decision sequence:

virtual address
  -> choose entries using page-number fields
  -> reach a valid leaf mapping
  -> check R/W/X and U-mode permissions
  -> combine frame base with offset
  -> physical memory access

If a required entry is absent, invalid, or lacks the needed permission, translation does not produce a successful access. The processor raises an instruction, load, or store page-fault exception. The trap code from the previous lesson provides the fault cause, the saved program counter, and often the faulting virtual address as evidence for the kernel's policy.

Worked Trace: Turn a First Store into a Mapped Page

Suppose the kernel has already approved an anonymous user-memory region from 0x4000 through 0x7fff for calc. Approval is not the same thing as immediate allocation. The kernel initially leaves the page at 0x4000 unmapped so it does not consume RAM until the program actually touches it.

Input: calc executes this store in U-mode:

store value 99 at virtual address 0x4008

The address is inside the approved range, but the leaf page-table entry for virtual page 0x4000 is absent.

1. Translation stops before the store

The processor walks calc's active page table. It either reaches a missing entry or an invalid leaf entry. It raises a store page fault instead of writing an arbitrary physical address. The trap frame records the interrupted instruction address; supervisor trap state identifies a store fault and can report 0x4008 as the relevant virtual address.

Intermediate state: no data frame has been changed. The desired store has not partially become a write somewhere else.

2. The fault handler checks the request against policy

The kernel rounds the fault address down to the page boundary, 0x4000. It looks up the process's allowed regions and asks:

Is 0x4000 within a user allocation?
Is this a store allowed for that region?
Is the address a guard page, kernel page, or unmapped hole?

For this trace, the answer is yes: it is the first writable page of the new array. If the address were outside the approved range, the same mechanism would lead to a different policy—usually delivering an error or ending the process. A page fault is evidence, not an automatic order to allocate memory.

3. The allocator transfers one frame from free to owned

The handler asks the physical-page allocator for one 4 KiB frame. The allocator chooses 0x80204000, removes it from the free structure, and records ownership as process calc, anonymous page 0x4000. The kernel clears the frame before exposing it to the process. Otherwise, stale bytes from a previous owner could become a confidentiality leak.

An ownership ledger at this point could look like:

4. Mapping code installs a leaf entry

The kernel finds or allocates the required page-table path and installs a leaf mapping conceptually like:

VA page 0x00004000
  -> PA frame 0x80204000
  -> valid, readable, writable, U-mode accessible

The permission choice matters. The new array page is writable but not executable. Kernel text would have a different mapping; a user program should not get U-mode permission to write it. A read-only program-code page would likewise deny stores even if its physical frame exists.

After changing page tables, the kernel must ensure subsequent translation uses the new entry rather than a stale cached translation. On RISC-V, page-table updates are not automatically ordered with later translation-cache use merely by writing the table or satp; the kernel uses SFENCE.VMA when the architecture requires it. This is one reason mapping code belongs in a small, carefully specified subsystem.

5. Return and retry produce the actual write

The handler returns to the same saved instruction rather than advancing past it. This is unlike ecall: the store was not completed before the fault. On retry, the page-table walk finds the new leaf entry. It combines frame base 0x80204000 with offset 0x008, reaches physical address 0x80204008, checks write and U-mode permission, and stores 99.

Output: calc sees a normal successful store at virtual 0x4008. The kernel sees a specific allocated frame and a traceable mapping. The program never needs to know 0x80204008.

Naive failure contrast: If the handler had returned without creating the mapping, the identical store would fault again. If it reused a frame still mapped by another process, the store could corrupt someone else's data. If it installed a read-only mapping, the retry would fault again for a different reason. A page fault is resolved only when policy, ownership, mapping, and cache visibility agree.

Check: Two processes both store to virtual address 0x4008. Does that prove they modify the same physical byte?

Think first, then reveal.

Answer: No. Each process normally has a different active page table. One mapping may send 0x4008 to frame 0x80204008; another may send it to a different frame. They share bytes only if the kernel deliberately maps a shared frame into both address spaces with compatible permissions.

Permissions Turn Translation into Isolation

A present mapping is not automatically usable for every access. The processor checks the kind of access against the leaf entry:

This table links the previous lesson's privilege boundary to a concrete mechanism. U-mode tells the processor that calc is ordinary code; the U bit and read/write/execute flags state what ordinary code can do with each mapped page. Neither one alone expresses the full policy.

The page-table hierarchy makes sparse spaces practical: a process can reserve a large virtual range without immediately consuming a frame for every page.

Costs, TLBs, and Large Pages

Translation adds work. A multi-level walk may read several page-table entries before reaching a leaf; the TLB caches recent translations to hide much of that cost.

The trade-off in page size makes the cost visible. Small base pages reduce internal fragmentation: allocating 4 KiB for a 4.1 KiB object wastes less than allocating a much larger page. But many small pages require more page-table entries and give the TLB less memory coverage per cached entry. Large pages improve TLB reach and can reduce page-table overhead, but they waste RAM for sparse allocations and impose stricter alignment and allocation constraints.

This mechanism does not solve every memory problem. A correct mapping can still point to a frame whose contents are logically wrong. A valid user pointer can still be unsafe for a kernel to retain after a syscall boundary. Page-table operations can race with other cores unless the kernel synchronizes ownership and invalidation. The next lesson narrows the question from “which frame backs this page?” to “who owns this longer-lived kernel object, and when may it be released?”

Common Confusions

Confusion: Allocating a frame automatically makes it visible to a process

Why it is tempting:

The allocator has returned RAM, so it feels as if the process now has memory.

Better model:

Allocation changes the frame's ownership. A page-table mapping with permissions changes what a particular address space can access. Both steps are required.

Confusion: A page fault means the program did something invalid

Why it is tempting:

The same exception mechanism reports invalid pointers and missing permissions.

Better model:

A fault says the current translation could not complete with its permissions. The kernel applies policy: it may map a valid demand-allocated page and retry, or reject an out-of-range or forbidden access.

Confusion: Changing a page-table entry immediately changes every CPU's view

Why it is tempting:

The memory containing the entry has been written.

Better model:

Processors cache translations. The kernel must use the architecture's invalidation and synchronization rules, such as SFENCE.VMA on RISC-V when needed, so later accesses do not use stale translations.

Practice: Review a Page Ownership Ledger

Review this proposed state for a process calc and decide what is wrong before proposing the smallest repair.

Use this rubric:

• The data mapping is unsafe because its frame is marked free. Mark the frame as owned by calc before another allocation can reuse it.
• The kernel-data mapping is unsafe because U-mode access is allowed. Remove U-mode accessibility; user page tables may omit it entirely or mark it supervisor-only according to the kernel layout.
• The text and guard entries express plausible policies: text is executable but not writable, and the guard page intentionally has no valid mapping.

Check: A kernel installs the correct mapping for a recovered page fault but returns with the faulting store skipped. What value appears in the newly mapped page?

Think first, then reveal.

Answer: The store did not run, so the page still contains its initialized value, usually zero. For a recoverable page fault, the kernel normally returns to retry the interrupted instruction after the mapping is ready.

Resources

• [REFERENCE] RISC-V Supervisor-Level ISA — Focus: satp, page-table entries, Sv39 translation, permissions, and SFENCE.VMA.
• [BOOK] xv6 RISC-V textbook — Focus: Chapter 3's page tables, physical allocation, and per-process address spaces.
• [COURSE] MIT 6.1810 page tables lab — Focus: inspecting mappings and connecting kernel/kalloc.c to page-table code.

Key Takeaways

• Physical frames, virtual pages, and mappings are distinct: supply, per-process names, and access policy.
• A recoverable page fault can allocate a frame, install a mapping, invalidate stale translation state as required, and retry the same instruction.
• A frame must remain owned for as long as any usable mapping reaches it; a mapping must carry the permissions intended for that address-space role.
• Page tables make equal virtual addresses in different processes independent unless the kernel deliberately maps shared physical memory.
• Translation has real costs in page-table memory, TLB behavior, invalidation, and fragmentation; page-size choices move those costs rather than removing them.