03 Memory

Xv6 memory management connects physical page allocation, kernel virtual memory, and per-process user virtual memory.

---
config:
  layout: dagre
---
flowchart LR
    BOOT["kernel VM setup<br><br>kinit<br>kvminit<br>proc_mapstacks<br>kvminithart"] -- initializes --> PMA["physical page allocator<br><br>kalloc<br>kfree<br>kmem.freelist"]
    BOOT -- builds and enables --> KVM["kernel virtual memory<br><br>kernel_pagetable<br>direct map<br>kernel stacks<br>trampoline"]
    PMA -- "supplies 4096-byte pages to" --> KVM & PROCVM["process virtual memory<br><br>p-&gt;pagetable<br>kexec<br>kfork<br>sys_sbrk / growproc<br>p-&gt;sz"]
    PROCVM -- uses --> VMAPI["VM helper functions<br><br>walk<br>mappages<br>uvmalloc<br>uvmunmap<br>copyin / copyout<br>vmfault"]
    VMAPI -- creates / edits mappings to --> PHYS["physical memory + MMIO<br><br>RAM<br>page-table pages<br>user pages<br>trapframe page<br>trampoline page<br>UART / VIRTIO / PLIC"]
    HW["RISC-V translation backend<br><br>satp<br>TLB<br>Sv39 hardware walker<br>page fault"] -- uses active page table to access --> PHYS
    KVM -- selected in kernel mode by satp --> HW
    PROCVM -- selected in user mode by satp --> HW
     BOOT:::iface
     PMA:::iface
     KVM:::source
     PROCVM:::source
     VMAPI:::iface
     HW:::backend
     PHYS:::source
    classDef process fill:#F3EFE2,stroke:#111,stroke-width:2px,color:#111
    classDef file fill:#FFFFFF,stroke:#111,stroke-width:3px,color:#111
    classDef source fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111
    classDef iface fill:#EDE7D4,stroke:#111,stroke-width:2px,color:#111
    classDef backend fill:#F8F8F8,stroke:#111,stroke-width:2px,color:#111

Paging

The page tables are the most popular mechanism through which the operating system provides each process with its own private address space and memory.

• RISC-V instructions manipulate virtual addresses, while the machine’s RAM uses physical addresses.
• The Sv39 RISC-V architecture utilizes only the bottom 39 bits of a 64-bit virtual address, ignoring the top 25 bits.
• The page table structure physically maps these addresses:
  • Logically acts as an array of $2^{27}$ Page Table Entries (PTEs).
  • Each PTE translates a virtual address to a physical address at the granularity of a 4096-byte ($2^{12}$ bytes) page.
  • A PTE contains a 44-bit Physical Page Number (PPN) and hardware control flags.
  • The CPU constructs a 56-bit physical address by combining the 44-bit PPN from the PTE with the bottom 12 bits of the original virtual address.

RISC-V virtual and physical addresses, with a simplified logical page table:

• Three-level tree implementation:
  • A page table is stored in physical memory as a three-level tree of 4096-byte pages.
  • The root page contains 512 PTEs pointing to intermediate pages, which point to bottom-level pages containing the final physical mappings.
  • The 27-bit virtual page number is split into three 9-bit sections to index into each of the three levels.
  • This tree structure saves physical memory by omitting entirely unmapped intermediate and bottom-level page directories.

RISC-V address translation details:

• Hardware integration:
  • The Translation Look-aside Buffer (TLB) caches PTEs inside the CPU to eliminate the performance cost of loading PTEs from memory during every address translation.
  • The satp register holds the physical address of the root page-table page, telling the CPU which page table tree to use for the currently executing thread.
• PTE flags control access permissions:
  • PTE_V: Indicates the PTE is present and valid.
  • PTE_R, PTE_W, PTE_X: Control read, write, and execute permissions, respectively.
  • PTE_U: Allows access by instructions executing in user mode.
  • Note: PTE_U is per-page, not per-page-table; xv6 maps pages like the trapframe in a user process’s page table so trap entry/return code can access them, but clears PTE_U so user-mode code cannot read or modify kernel-owned state.

Memory Allocation

The kernel manages physical memory between the end of the kernel binary and PHYSTOP as a global pool of 4096-byte pages.

The allocator stores free pages in a linked list.

Allocator implementation:

• Each free page stores a struct run structure containing a pointer to the next free page.
• The free list structure is protected by a spin lock to handle concurrent allocation requests across multiple CPUs.
• Allocated and freed pages are filled with junk values to expose stale or dangling references.

kmem is the allocator’s global state.

• kmem.lock protects allocator state from concurrent CPU access
• kmem.freelist points to the linked list of currently free physical pages
• Every kalloc and kfree call updates kmem.freelist while holding kmem.lock

---
config:
  layout: dagre
---
flowchart LR
 subgraph INIT["allocator initialization"]
    direction TB
        KINIT["kinit<br><br>starts physical allocator setup"]
        FREERANGE["freerange<br><br>adds pages from end to PHYSTOP"]
  end
 subgraph STATE["allocator state"]
    direction TB
        KMEM["kmem<br><br>spinlock lock<br>freelist"]
        RUN["struct run<br><br>next pointer stored inside free page"]
        FREEPAGES["free 4096-byte physical pages<br><br>user pages<br>page-table pages<br>kernel stacks<br>trapframes<br>pipe buffers"]
  end
 subgraph API["allocator functions"]
    direction TB
        KFREE["kfree<br><br>returns a physical page to freelist"]
        KALLOC["kalloc<br><br>removes one physical page from freelist"]
  end
    KINIT --> FREERANGE
    FREERANGE -- calls repeatedly --> KFREE
    KFREE -- protects and updates --> KMEM
    KMEM -- freelist nodes are --> RUN
    RUN -- each node represents one --> FREEPAGES
    KALLOC -- protects and updates --> KMEM
    KMEM -- hands out --> KALLOC
    KALLOC -- returns page to --> USERS["main users of kalloc<br><br>kernel page table<br>user memory<br>page-table pages<br>kernel stacks<br>trapframes<br>pipe buffers"]
     KINIT:::iface
     FREERANGE:::iface
     KMEM:::source
     RUN:::file
     FREEPAGES:::source
     KFREE:::iface
     KALLOC:::iface
     USERS:::process
    classDef process fill:#F3EFE2,stroke:#111,stroke-width:2px,color:#111
    classDef file fill:#FFFFFF,stroke:#111,stroke-width:3px,color:#111
    classDef source fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111
    classDef iface fill:#EDE7D4,stroke:#111,stroke-width:2px,color:#111
    classDef backend fill:#F8F8F8,stroke:#111,stroke-width:2px,color:#111

Kernel VM

xv6 uses one page table per process for user space and one shared kernel page table for predictable access to RAM and memory-mapped devices.

• Most physical memory and device registers are direct-mapped, so kernel virtual addresses equal physical addresses.
• The kernel image starts at KERNBASE (0x80000000), where QEMU RAM also begins, and xv6 manages RAM up to PHYSTOP.
• Memory-mapped device registers sit below KERNBASE in physical address space.
• Direct mapping lets the kernel use physical addresses directly, which simplifies operations such as copying pages during fork.
• The trampoline and kernel stacks are exceptions to the simple direct-map pattern.
• Kernel text and trampoline code are read/execute; kernel data, RAM, and kernel stacks are read/write; guard pages are invalid.

Virtual	Physical	Pages	Perm	Purpose
UART0	UART0	1	R W	Console UART registers
VIRTIO0	VIRTIO0	1	R W	Disk MMIO registers
PLIC range	Same	0x4000000 / PGSIZE	R W	Interrupt controller
KERNBASE to etext	Same	(etext - KERNBASE) / PGSIZE	R X	Kernel text
etext to PHYSTOP	Same	(PHYSTOP - etext) / PGSIZE	R W	Kernel data and RAM
TRAMPOLINE	trampoline.S	1	R X	Trap entry and return
KSTACK(p)	New page	1 per process slot	R W	Process kernel stack
Stack guard page	Unmapped	1 per process slot	None	Overflow trap

TRAMPOLINE

• is not direct-mapped,
• a high virtual address for trap entry and return code,
• mapped in kernel VM so trap code remains reachable while switching between kernel and user page tables.

KSTACK(p)

• gives each process slot a high kernel stack,
• mapped in kernel VM so the kernel has a protected stack during system calls, interrupts, and exceptions,
• a guard page is left unmapped next to each stack, so stack overflow causes a fault instead of overwriting another stack.

The VM layer provides software routines to build page-table trees, install VA-to-PA mappings, remove mappings, free page-table pages, and check whether an address is already mapped.

---
config:
  layout: dagre
---
flowchart LR
  classDef process fill:#F3EFE2,stroke:#111,stroke-width:2px,color:#111
  classDef file fill:#FFFFFF,stroke:#111,stroke-width:3px,color:#111
  classDef source fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111
  classDef iface fill:#EDE7D4,stroke:#111,stroke-width:2px,color:#111
  classDef backend fill:#F8F8F8,stroke:#111,stroke-width:2px,color:#111
  subgraph BUILD["kernel VM construction: software builds mappings"]
    direction TB
    KVMINIT["kvminit<br/><br/>starts kernel VM setup"]:::iface
    KVMMAKE["kvmmake<br/><br/>allocates root page table<br/>creates kernel mappings"]:::iface
    KVMMAP["kvmmap<br/><br/>kernel wrapper for mapping ranges"]:::iface
    MAPPAGES["mappages<br/><br/>install VA to PA mappings"]:::iface
    WALK["walk<br/><br/>software page-table walk<br/>finds or creates lower-level tables"]:::iface
    MAPSTACKS["proc_mapstacks<br/><br/>maps per-process kernel stacks<br/>leaves guard pages invalid"]:::iface
    KVMHART["kvminithart<br/><br/>sfence.vma<br/>w_satp(MAKE_SATP(kernel_pagetable))<br/>sfence.vma"]:::iface
  end
  subgraph KSTATE["kernel page-table state"]
    direction TB
    KPAGETABLE["kernel_pagetable<br/><br/>shared kernel address space"]:::source
    KPTPAGE["kernel page-table pages<br/><br/>4096-byte pages<br/>512 PTEs each"]:::file
    KPTE["kernel PTEs<br/><br/>PTE_V<br/>PTE_R / PTE_W / PTE_X<br/>normally no PTE_U"]:::file
  end
  subgraph VAMAP["virtual to physical address map"]
    direction TB
    subgraph DIRECT_PAIR["direct map"]
      direction LR
      DIRECTMAP["direct map region<br/><br/>kernel VA = physical address<br/>RAM + device MMIO<br/>permissions split by region"]:::source
      RAM["physical RAM<br/><br/>KERNBASE = 0x80000000<br/>PHYSTOP = KERNBASE + 128MB"]:::source
      MMIO["memory-mapped device registers<br/><br/>UART0<br/>VIRTIO0<br/>PLIC"]:::backend
    end
    subgraph TEXT_PAIR["kernel text map"]
      direction LR
      KTEXT["kernel text<br/><br/>readable + executable<br/>PTE_R | PTE_X"]:::source
      KERNELIMG["kernel image in RAM<br/><br/>entry.S<br/>kernel text<br/>kernel data<br/>end symbol"]:::source
    end
    subgraph DATA_PAIR["kernel data map"]
      direction LR
      KDATA["kernel data + usable RAM<br/><br/>readable + writable<br/>PTE_R | PTE_W"]:::source
      RAMDATA["physical RAM<br/><br/>usable RAM region"]:::source
    end
    subgraph STACK_PAIR["kernel stack map"]
      direction LR
      KSTACKS["kernel stacks<br/><br/>one stack per process<br/>mapped high<br/>invalid guard page below"]:::source
      STACKPAGES["kernel stack physical pages<br/><br/>allocated by kalloc"]:::source
    end
    subgraph TRAMP_PAIR["trampoline map"]
      direction LR
      KTRAMP["TRAMPOLINE<br/><br/>trap entry / return code<br/>same VA in kernel and user page tables"]:::source
      TRAMPPAGE["trampoline physical page<br/><br/>trampoline.S code"]:::file
    end
  end
  subgraph ALLOC["physical page allocator functions"]
    direction TB
    KALLOC["kalloc / kfree<br/><br/>allocate or release 4096-byte physical pages"]:::iface
  end
  subgraph RUNTIME["kernel-mode runtime: hardware uses mappings"]
    direction TB
    KERNELCODE["kernel code<br/><br/>load / store / fetch<br/>using kernel virtual addresses"]:::process
    CPU["RISC-V CPU"]:::process
    SATP["satp CSR<br/><br/>active root page table"]:::source
    TLB["TLB<br/><br/>cached VA to PA translations"]:::backend
    HWALKER["Sv39 hardware page-table walker<br/><br/>walks kernel_pagetable on TLB miss"]:::backend
    ACCESS["physical memory / MMIO access"]:::source
    FAULT["kernel page fault<br/><br/>invalid mapping or bad permission"]:::backend
  end
  KVMINIT --> KVMMAKE
  KVMMAKE -->|"allocates root using"| KALLOC
  KVMMAKE --> KVMMAP
  KVMMAKE --> MAPSTACKS
  KVMMAP --> MAPPAGES
  MAPPAGES --> WALK
  WALK -->|"writes / finds PTEs in"| KPAGETABLE
  WALK -->|"may allocate lower-level tables via"| KALLOC
  KALLOC -->|"returns"| KPTPAGE
  MAPSTACKS -->|"allocates stack pages via"| KALLOC
  MAPSTACKS -->|"uses"| KVMMAP
  KVMHART -->|"loads root into"| SATP
  SATP -->|"selects"| KPAGETABLE
  KPAGETABLE -->|"contains"| KPTPAGE
  KPTPAGE -->|"contains"| KPTE
  KPAGETABLE -->|"describes"| DIRECTMAP
  KPAGETABLE -->|"describes"| KTEXT
  KPAGETABLE -->|"describes"| KDATA
  KPAGETABLE -->|"describes"| KSTACKS
  KPAGETABLE -->|"describes"| KTRAMP
  DIRECTMAP -->|"maps RAM"| RAM
  DIRECTMAP -->|"maps MMIO"| MMIO
  KTEXT -->|"maps"| KERNELIMG
  KDATA -->|"maps"| RAMDATA
  KSTACKS -->|"maps"| STACKPAGES
  KTRAMP -->|"maps"| TRAMPPAGE
  KERNELCODE --> CPU
  CPU -->|"uses"| SATP
  CPU -->|"checks first"| TLB
  TLB -->|"on miss"| HWALKER
  HWALKER -->|"reads"| KPTPAGE
  HWALKER -->|"valid PTE"| ACCESS
  HWALKER -->|"invalid / bad permission"| FAULT

User VM

Each process has an independent page table, giving it a private virtual address space. User memory starts at virtual address zero and grows upward through text, data, stack, and heap regions toward MAXVA.

• The trampoline and trapframe sit at the top of the user address space to support safe user-kernel transitions.
• A guard page below the user stack is made inaccessible so stack overflow becomes a fault instead of silent memory corruption.
• Dynamic memory growth and shrinkage are exposed through sbrk; the VM layer adjusts mappings and physical backing as needed.
• User VM routines create page tables, allocate and remove mappings, copy address spaces during fork, and clear user access for guard pages.
• User/kernel copy helpers validate user pointers through the process page table before copying data across the protection boundary.
• Lazy allocation uses page faults to allocate missing heap pages on demand.

A process’s user address space, with its initial stack:

User virtual memory looks contiguous, but physical pages may be scattered anywhere in RAM.

Virtual region	Physical backing
text	Physical RAM pages allocated from the free-memory pool, then filled from the ELF file.
data	Physical RAM pages allocated from the free-memory pool.
heap	Physical RAM pages allocated from the free-memory pool as the heap grows.
stack	Physical RAM pages allocated from the free-memory pool.
guard page	No physical page; the mapping is left invalid.
trapframe	One per-process physical page allocated from the free-memory pool.
trampoline	One shared kernel code page, mapped into every process.

VA Translation

User VA translation is the runtime path from a process virtual address to a physical page. The active root is selected through satp, and the MMU checks valid, user, and permission bits before allowing a load, store, or instruction fetch.

• Valid leaf PTEs map user virtual pages to physical pages.
• Missing or invalid PTEs may represent lazy heap holes if the address is still below p->sz.
• Failed translation or permission checks raise a user page fault and record the faulting address in stval.
• Lazy allocation handles eligible load/store faults by allocating, zero-filling, and mapping a new physical page.
• Invalid addresses, already-mapped pages, allocation failure, or mapping failure take the fail path.
• Kernel copy helpers validate user pointers through the process page table before copying across the protection boundary.
• copyin and copyout may allocate lazy pages; copyinstr requires the string page to already be mapped.

---
config:
layout: dagre
---
flowchart LR
classDef process fill:#F3EFE2,stroke:#111,stroke-width:2px,color:#111
classDef file fill:#FFFFFF,stroke:#111,stroke-width:3px,color:#111
classDef source fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111
classDef iface fill:#EDE7D4,stroke:#111,stroke-width:2px,color:#111
classDef backend fill:#F8F8F8,stroke:#111,stroke-width:2px,color:#111
subgraph USTATE["running user VM state"]
direction TB
UPAGETABLE["p-&gt;pagetable<br><br>root of the process's active<br>three-level Sv39 user page table"]:::source
UPTE["user PTEs<br><br>valid leaf PTEs map user pages<br>absent or invalid entries may represent<br>lazy holes when the VA is below p-&gt;sz"]:::file
VAMAP["runtime VA-to-PA map<br><br>text, data, stack, mapped heap pages,<br>and lazy sbrk heap range below p-&gt;sz"]:::source
end
subgraph ACCESSPATH["user access, translation, and lazy fault resolution"]
direction TB
USERACCESS["user instruction<br><br>load, store, or fetch<br>uses a user virtual address"]:::process
MMU["RISC-V address translation<br><br>satp selects p-&gt;pagetable<br>TLB may cache the translation<br>Sv39 walker checks PTE bits on miss"]:::backend
ACCESSOK["physical access succeeds<br><br>VA translates to PA<br>and requested R / W / X access<br>is allowed"]:::source
PAGEFAULT["user page fault<br><br>missing mapping, invalid PTE,<br>or permission failure<br>reported with faulting VA in stval"]:::backend
USERTRAP["usertrap<br><br>handles traps from user mode<br>load/store page faults<br>scause 13 or 15 may call vmfault"]:::process
VMFAULT["vmfault<br><br>lazy allocator for unmapped VA<br>VA must be below p-&gt;sz<br>and not already mapped<br><br>on success, zero-fills the page<br>and installs a user mapping"]:::iface
KALLOC["kalloc<br><br>allocates one 4096-byte<br>physical backing page"]:::iface
MAP["mappages / walk<br><br>vmfault calls mappages<br>mappages calls walk<br><br>walk may allocate missing<br>page-table pages if needed"]:::iface
FAIL["fail path<br><br>user fault kills process<br>kernel copy helper returns -1"]:::process
end
subgraph COPYPATH["kernel access to user buffers"]
direction TB
SYSCALL["system call<br><br>kernel receives a user pointer<br>but must translate and validate it<br>through the user page table"]:::process
COPYIN["copyin<br><br>copy bytes from user VA<br>to kernel buffer<br>may allocate lazy source page"]:::iface
COPYOUT["copyout<br><br>copy bytes from kernel buffer<br>to user VA<br>may allocate lazy destination page"]:::iface
COPYINSTR["copyinstr<br><br>copy null-terminated user string<br>requires the string page<br>to already be mapped"]:::iface
WALKADDR["walkaddr<br><br>software user VA translation<br>returns PA only if PTE_V<br>and PTE_U are set"]:::iface
PAOK["physical address found<br><br>valid user-accessible mapping<br>returned to copy helper"]:::source
WRITECHK["copyout write check<br><br>after translation,<br>destination PTE must also<br>have PTE_W set"]:::backend
COPYBYTES["copy bytes<br><br>copyin / copyout use memmove<br>copyinstr scans byte-by-byte<br>until NUL or max"]:::process
end
UPAGETABLE -->|"contains leaf and non-leaf entries"| UPTE
UPTE -->|"leaf entries define mapped portions of"| VAMAP
USERACCESS -->|"issued while process runs in user mode"| MMU
MMU -->|"valid PTE and permission bits allow access"| ACCESSOK
MMU -->|"unmapped lazy page or failed permission check"| PAGEFAULT
PAGEFAULT -->|"trap switches from user to kernel"| USERTRAP
USERTRAP -->|"only load/store page faults are lazy-allocation candidates"| VMFAULT
VMFAULT -->|"VA is below p-&gt;sz and currently unmapped"| KALLOC
KALLOC -->|"returns physical page to vmfault"| VMFAULT
VMFAULT -->|"zero-fills page, then installs mapping with"| MAP
VMFAULT -->|"VA outside p-&gt;sz, already mapped,<br>out of memory, or mapping failure"| FAIL
MAP -->|"updates the page-table tree rooted at"| UPAGETABLE
SYSCALL --> COPYIN
SYSCALL --> COPYOUT
SYSCALL --> COPYINSTR
COPYIN -->|"translate source user VA"| WALKADDR
COPYOUT -->|"translate destination user VA"| WALKADDR
COPYINSTR -->|"translate string user VA"| WALKADDR
WALKADDR -->|"walks and checks mappings in"| UPAGETABLE
WALKADDR -->|"valid PTE_V and PTE_U mapping found"| PAOK
WALKADDR -->|"missing page: copyin / copyout ask vmfault to allocate"| VMFAULT
WALKADDR -->|"missing page: copyinstr does not allocate"| FAIL
PAOK -->|"copyin / copyinstr source PA is available"| COPYBYTES
PAOK -->|"copyout destination needs one more check"| WRITECHK
WRITECHK -->|"PTE_W set on destination"| COPYBYTES
WRITECHK -->|"read-only destination, e.g. text page"| FAIL

VM Construction

User VM is constructed when a process image is created or replaced. xv6 either builds a fresh ELF-backed image for exec, or copies an existing address space for fork.

• kexec builds a replacement address space from an ELF file.
• kfork creates a child address space by copying the parent’s mapped user pages.
• Both paths start from a per-process page table with trampoline and trapframe mappings.
• Physical memory comes from kalloc for user data pages and page-table pages.
• The final result is p->pagetable, a three-level Sv39 user page table with user-accessible leaf mappings and the required permissions.

---
config:
  layout: dagre
---
flowchart LR
  subgraph KEXECPATH["exec path: replace current VM"]
    direction TB
    KEXEC["kexec<br><br>builds a new address space<br>from an ELF file<br>then commits it to p-&gt;pagetable"]
    LOADSEG["loadseg<br><br>copies ELF segment bytes<br>into mapped user pages"]
    FLAGS2PERM["flags2perm<br><br>translates ELF flags<br>to PTE_X / PTE_W"]
  end
  subgraph KFORKPATH["fork path: copy parent VM"]
    direction TB
    KFORK["kfork<br><br>allocates child process state<br>then duplicates parent memory"]
    PROCPGTBL["proc_pagetable<br><br>creates a user page table<br>with trampoline and trapframe<br>kernel-only mappings"]
  end
  subgraph COMMON["shared construction helpers"]
    direction TB
    UVMCREATE["uvmcreate<br><br>allocates and zeroes<br>an Sv39 root page-table page"]
    UVMALLOC["uvmalloc<br><br>allocates user pages<br>and maps them with<br>PTE_R | PTE_U | xperm"]
    UVMCOPY["uvmcopy<br><br>copies mapped parent pages<br>and preserves PTE flags"]
    MAPPAGES["mappages<br><br>creates leaf PTEs<br>for an aligned VA range"]
    WALK["walk<br><br>finds or creates PTE slots<br>in the three-level tree"]
  end
  subgraph USTATE["process user VM state"]
    direction TB
    UPAGETABLE["p-&gt;pagetable<br><br>root of the user address space"]
    UPTPAGE["user page-table pages<br><br>root and lower-level pages"]
    UPTE["user PTEs<br><br>non-leaf PTEs point downward<br>leaf PTEs encode PA and flags"]
  end
  subgraph MAPBOX["virtual-to-physical map"]
    direction TB
    VAMAP["resulting user map<br><br>ELF text, data, bss,<br>user stack, guard page,<br>trapframe, trampoline"]
  end
  subgraph ALLOC["physical page allocator"]
    direction TB
    KALLOC["kalloc / kfree<br><br>allocates or releases<br>one 4096-byte page"]
  end
  KEXEC -- "creates fresh page table" --> UVMCREATE
  KEXEC -- "allocates segment and stack pages" --> UVMALLOC
  KEXEC -- "copies file-backed bytes" --> LOADSEG
  KEXEC -- "derives page permissions" --> FLAGS2PERM
  KFORK -- "gets child page table" --> PROCPGTBL
  KFORK -- "duplicates mapped parent memory" --> UVMCOPY
  PROCPGTBL -- "starts from empty root" --> UVMCREATE
  PROCPGTBL -- "maps trampoline and trapframe without PTE_U" --> MAPPAGES
  UVMCREATE -- "allocates root page" --> KALLOC
  UVMCREATE -- "returns root pointer" --> UPAGETABLE
  UVMALLOC -- "gets zero-filled pages" --> KALLOC
  UVMALLOC -- "maps each page" --> MAPPAGES
  UVMCOPY -- "allocates child pages" --> KALLOC
  UVMCOPY -- "maps copied pages" --> MAPPAGES
  MAPPAGES -- "uses" --> WALK
  WALK -- "traverses" --> UPAGETABLE
  WALK -- "may allocate lower-level pages" --> KALLOC
  UPAGETABLE -- contains --> UPTPAGE
  UPTPAGE -- holds --> UPTE
  UPTE -- "leaf PTEs define" --> VAMAP
  KALLOC -- "also supplies" --> UPTPAGE
  KEXEC:::iface
  LOADSEG:::iface
  FLAGS2PERM:::iface
  KFORK:::iface
  PROCPGTBL:::iface
  UVMCREATE:::iface
  UVMALLOC:::iface
  UVMCOPY:::iface
  MAPPAGES:::iface
  WALK:::iface
  UPAGETABLE:::source
  UPTPAGE:::file
  UPTE:::file
  VAMAP:::source
  KALLOC:::iface
  classDef file fill:#FFFFFF,stroke:#111,stroke-width:3px,color:#111
  classDef source fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111
  classDef iface fill:#EDE7D4,stroke:#111,stroke-width:2px,color:#111
  classDef path fill:#F7F7F7,stroke:#111,stroke-width:2px,color:#111

Heap Allocation

Heap allocation is controlled by the process size boundary and the user page table. An address can be logically valid because it is below p->sz, even if no physical page has been mapped yet.

• Eager growth allocates and maps physical pages immediately.
• Lazy growth increases p->sz only; the first access to the unmapped range triggers lazy fault handling.
• Shrink removes mappings above the new size and frees any physical pages that were actually mapped.
• Missing or invalid PTEs are skipped during shrink because lazy holes have no physical backing.
• p->sz defines the legal heap range; the page table records the pages that actually exist.

---
config:
  layout: dagre
---
flowchart LR
  classDef actual fill:#DFF3E3,stroke:#111,stroke-width:2px,color:#111
  classDef logical fill:#FFF2CC,stroke:#111,stroke-width:2px,color:#111
  classDef state fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111
  classDef file fill:#FFFFFF,stroke:#111,stroke-width:3px,color:#111
  classDef backend fill:#F8F8F8,stroke:#111,stroke-width:2px,color:#111
  subgraph HEAPSTATE["heap-related user VM state"]
    direction TB
    PROCSZ["p-&gt;sz<br><br>declared user memory size<br>and heap validity boundary"]:::state
    UPAGETABLE["p-&gt;pagetable<br><br>user page table edited by<br>heap growth, shrink, and faults"]:::state
    UPTE["heap PTE state<br><br>valid leaf PTEs map heap pages<br>absent or invalid entries may be<br>lazy holes below p-&gt;sz"]:::file
    VAMAP["heap VA-to-PA state<br><br>mapped heap pages,<br>unmapped lazy heap range,<br>and mappings removed by shrink"]:::state
  end
  subgraph SBRKPATH["sbrk heap request"]
    direction TB
    SBRK["sys_sbrk(n, t)<br><br>actual function<br>returns old p-&gt;sz<br>then chooses eager, lazy,<br>or shrink behavior"]:::actual
    EAGER["eager growth branch<br><br>logical path<br>SBRK_EAGER with n &gt; 0<br>allocates and maps pages now"]:::logical
    LAZY["lazy growth branch<br><br>logical path<br>non-eager n &gt;= 0<br>extends p-&gt;sz only"]:::logical
    SHRINK["shrink branch<br><br>logical path<br>n &lt; 0<br>removes mappings above<br>the new heap size"]:::logical
    FAULTREF["first access to lazy hole<br><br>logical continuation<br>later load/store fault is handled<br>by lazy fault resolution"]:::backend
  end
  subgraph VMHELPERS["heap VM helper functions"]
    direction TB
    GROWPROC["growproc<br><br>actual function<br>handles eager growth<br>and all shrinking<br>n == 0 is a no-op"]:::actual
    UVMALLOC["uvmalloc<br><br>actual function<br>allocates zeroed heap pages<br>and maps them with<br>PTE_R, PTE_U, and PTE_W"]:::actual
    UVMDEALLOC["uvmdealloc<br><br>actual function<br>reduces user memory size<br>and unmaps pages if needed"]:::actual
    UVMUNMAP["uvmunmap<br><br>actual function<br>removes existing mappings<br>skips missing or invalid PTEs<br>optionally frees pages"]:::actual
    MAP["mappages / walk<br><br>actual function group<br>mappages installs leaf PTEs<br>walk finds or creates PTE slots<br>and may allocate page-table pages"]:::actual
  end
  subgraph ALLOC["physical page allocator functions"]
    direction TB
    KALLOC["kalloc<br><br>actual function<br>allocates one 4096-byte<br>physical page"]:::actual
    KFREE["kfree<br><br>actual function<br>returns a mapped heap page<br>to the allocator"]:::actual
  end
  UPAGETABLE -->|"contains heap-related leaf and non-leaf entries"| UPTE
  UPTE -->|"leaf entries define mapped heap pages in"| VAMAP
  PROCSZ -->|"bounds valid eager and lazy heap addresses"| VAMAP
  SBRK -->|"t == SBRK_EAGER or n &lt; 0"| GROWPROC
  SBRK -->|"t != SBRK_EAGER and n &gt;= 0"| LAZY
  GROWPROC -->|"n &gt; 0"| EAGER
  GROWPROC -->|"n &lt; 0"| SHRINK
  GROWPROC -->|"on success, records final size in"| PROCSZ
  EAGER -->|"calls"| UVMALLOC
  UVMALLOC -->|"requests physical heap pages from"| KALLOC
  KALLOC -->|"returns page to caller"| UVMALLOC
  UVMALLOC -->|"installs heap mappings with"| MAP
  MAP -->|"updates page-table tree rooted at"| UPAGETABLE
  MAP -->|"adds immediate heap VA-to-PA mappings to"| VAMAP
  LAZY -->|"after overflow and TRAPFRAME checks,<br>updates only"| PROCSZ
  VAMAP -->|"later user load/store to<br>valid but unmapped heap VA causes"| FAULTREF
  SHRINK -->|"calls"| UVMDEALLOC
  UVMDEALLOC -->|"uses when mapped pages must be removed"| UVMUNMAP
  UVMUNMAP -->|"walks existing mappings in"| UPAGETABLE
  UVMUNMAP -->|"removes mapped heap pages<br>and skips lazy holes"| VAMAP
  UVMUNMAP -->|"do_free = 1 frees old backing pages through"| KFREE
  SHRINK -->|"sets p-&gt;sz to deallocated size"| PROCSZ

VM Cleanup

VM cleanup destroys an old user address space by editing and freeing the page-table tree rooted at the old p->pagetable. The VA-to-PA map is only the result of that tree.

• exec frees the old address space only after the new image has been installed successfully.
• Process destruction frees the trapframe page separately, then frees the old user page table if one exists.
• Special trampoline and trapframe mappings are removed without freeing their physical pages here.
• Normal user mappings are removed across the old p->sz range.
• Mapped text, data, heap, and stack pages are returned to the allocator.
• Missing or invalid PTEs, including lazy holes, are skipped.
• After all leaf mappings are gone, the remaining Sv39 page-table pages are freed recursively.

---
config:
layout: dagre
---
flowchart LR
subgraph OLDSTATE["old process VM state"]
direction TB
PAGETABLE["old p-&gt;pagetable<br><br>user page table being destroyed<br>all cleanup works through this tree"]
USERMAP["old user VA-to-PA map<br><br>conceptual result of the page table:<br>text, data, heap, stack,<br>TRAPFRAME, and TRAMPOLINE"]
end
subgraph ENTRY["cleanup entry paths"]
direction TB
EXECREPLACE["exec replacement<br><br>logical path<br>new image replaces old image"]
FREEPROC["freeproc<br><br>actual function<br>destroys process state<br>and frees p-&gt;trapframe separately"]
PROCFREE["proc_freepagetable<br><br>actual function<br>main per-process VM cleanup"]
SPECIAL["uvmunmap special mappings<br><br>removes TRAMPOLINE and TRAPFRAME PTEs<br>with do_free = 0<br><br>does not free trampoline code<br>does not free trapframe page here"]
UVMFREE["uvmfree<br><br>frees normal user memory first<br>then frees the page-table tree"]
UVMUNMAP["uvmunmap normal mappings<br><br>removes text, data, heap, and stack PTEs<br>with do_free = 1<br><br>frees mapped user physical pages<br>skips missing or invalid PTEs"]
FREEWALK["freewalk<br><br>recursively frees Sv39 page-table pages<br>after all leaf mappings are gone"]
KFREE["kfree<br><br>returns freed physical pages<br>to the allocator"]
end
PAGETABLE -- defines --> USERMAP
EXECREPLACE -- after new image is installed,<br>free old address space --> PROCFREE
FREEPROC -- "if p-&gt;pagetable exists" --> PROCFREE
FREEPROC -- "frees p-&gt;trapframe separately with" --> KFREE
PROCFREE -- first remove special mappings --> SPECIAL
SPECIAL -- edits special PTEs in --> PAGETABLE
PROCFREE -- then free normal user VM --> UVMFREE
UVMFREE -- unmap user memory range --> UVMUNMAP
UVMUNMAP -- walks and clears leaf PTEs in --> PAGETABLE
UVMUNMAP -- frees mapped user pages through --> KFREE
UVMFREE -- after leaf mappings are gone --> FREEWALK
FREEWALK -- "walks and frees page-table tree rooted at" --> PAGETABLE
FREEWALK -- "frees page-table pages through" --> KFREE
PAGETABLE:::state
USERMAP:::state
EXECREPLACE:::logical
FREEPROC:::actual
PROCFREE:::actual
SPECIAL:::actual
UVMFREE:::actual
UVMUNMAP:::actual
FREEWALK:::actual
KFREE:::actual
classDef actual fill:#DFF3E3,stroke:#111,stroke-width:2px,color:#111
classDef logical fill:#FFF2CC,stroke:#111,stroke-width:2px,color:#111
classDef state fill:#E9F1FF,stroke:#111,stroke-width:2px,color:#111