Virtual Memory & Physical Pages
ECE 391 · Discussion 8
Walking an Sv39 page table
building the MP3 CP2 free-page allocator
ECE 391 · Discussion 8
1
Announcements
ECE 391 · Discussion 8
2
What is virtual memory?
Programs use virtual addresses.
The MMU maps each one to a physical address using a page table that the kernel builds.
The mapping works page by page: the page number changes, the offset does not.
Each process can get its own mapping, so it cannot touch other processes' memory.
Virtual memory: a kernel-managed mapping from virtual pages to physical pages.
ECE 391 · Discussion 8
3
Virtual pages and physical pages
ECE 391 · Discussion 8 · the Sv39 walk and the free-page allocator
Page offset:
12 bits,
copied unchanged
Only the page number is translated.
ECE 391 · Discussion 8
4
Three levels in Sv39
virtual address (39 bits used)
VPN[2]
VPN[1]
VPN[0]
page offset
38–30
29–21
20–12
11–0
9 bits
9 bits
9 bits
12 bits
Each table is one 4 KiB page: 512 PTEs × 8 bytes.
Nine bits pick one of the 512 entries.
non-leaf PTE
V=1
R=W=X=0
PPN
next table
leaf PTE
V=1
R|W|X ≠ 0
PPN
mapped page
ECE 391 · Discussion 8
5
The root comes from satp
MODE · bits 63–60
8 = Sv39
0 = Bare: no translation
PPN · bits 43–0
root = PPN << 12
page number × 4096 = root table address
ECE 391 · Discussion 8
6
A full virtual mapping looks like a tree
Sv39, our kernel
Field | Size |
Page size | 4 KiB |
VA bits | 9+9+9+12 = 39 |
PA bits | 44+12 = 56 |
PTE size | 64 bits |
PTEs per table | 512 |
Same shape, wider fan-out: every table has 512 slots (8 drawn).
Gray slots are invalid PTEs, so there is no subtree below them. One walk is one root-to-leaf path.
ECE 391 · Discussion 8
7
Walk: locate the root table
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
// fake_satp: MODE 8 (Sv39) in bits 63:60, root PPN in 43:0
struct pte { uint64_t flags:8, rsw:2, ppn:44, reserved:10; };
#define PAGE_ORDER 12 // PAGE_SIZE = 1UL << 12 = 4096
root · level 2
[0] V
[1]
⋮
[510]
[511]
↑ table
table: root
pte: (not read yet)
paddr: ?
<< 20 drops MODE and ASID; >> 8 leaves PPN << 12, the root's page-aligned address.
ECE 391 · Discussion 8
8
Walk: inspect the level-2 entry
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
unsigned long vpn[3]; vpn[2] = VPN2(vaddr); // = 0
#define VPN(vma) ((vma) / PAGE_SIZE) // 0xC000 -> 12
#define VPN2(vma) ((VPN(vma) >> (2 * 9)) % PTE_CNT)
#define PTE_CNT (1U << (PAGE_ORDER - PTE_ORDER)) // 512
#define PTE_VALID(pte) (((pte).flags & PTE_V) != 0)
#define PTE_LEAF(pte) (((pte).flags & (PTE_R|PTE_W|PTE_X))!=0)
root · level 2
[0] V
[1]
⋮
[510]
[511]
↑ table
V = 1
R = W = X = 0
→ PPN names a table
table: root
pte: V · ppn = level1
paddr: ?
vpn[2] = 0 selects root[0]. V = 1 and R = W = X = 0, so both asserts on the next line pass.
ECE 391 · Discussion 8
9
Walk: follow the level-2 PPN
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
#define PAGE_ORDER 12 // PAGE_SIZE = 1UL << 12 = 4096
struct pte { uint64_t flags:8, rsw:2, ppn:44, reserved:10; };
// ppn is a page number; << 12 gives that page's address
root · level 2
[0] V
[1]
⋮
[510]
[511]
level1 · level 1
[0] V
[1]
⋮
[510]
[511]
↑ table
table: level1
pte: V · ppn = level1
paddr: ?
pte.ppn << 12 turns the page number back into an address: table now points at level1.
ECE 391 · Discussion 8
10
Walk: inspect the level-1 entry
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
unsigned long vpn[3]; vpn[1] = VPN1(vaddr); // = 0
#define VPN(vma) ((vma) / PAGE_SIZE) // 0xC000 -> 12
#define VPN1(vma) ((VPN(vma) >> (1 * 9)) % PTE_CNT)
#define PTE_CNT (1U << (PAGE_ORDER - PTE_ORDER)) // 512
#define PTE_VALID(pte) (((pte).flags & PTE_V) != 0)
#define PTE_LEAF(pte) (((pte).flags & (PTE_R|PTE_W|PTE_X))!=0)
root · level 2
[0] V
[1]
⋮
[510]
[511]
level1 · level 1
[0] V
[1]
⋮
[510]
[511]
↑ table
V = 1
R = W = X = 0
→ still a table
table: level1
pte: V · ppn = level0
paddr: ?
Same index, different table: this reads level1[0], not root[0]. R = W = X = 0, so not the final page.
ECE 391 · Discussion 8
11
Walk: follow the level-1 PPN
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
#define PAGE_ORDER 12 // PAGE_SIZE = 1UL << 12 = 4096
struct pte { uint64_t flags:8, rsw:2, ppn:44, reserved:10; };
// ppn is a page number; << 12 gives that page's address
root · level 2
[0] V
[1]
⋮
[510]
[511]
level1 · level 1
[0] V
[1]
⋮
[510]
[511]
level0 · level 0
[0]
⋮
[12] V R
⋮
[511]
↑ table
table: level0
pte: V · ppn = level0
paddr: ?
Same shift, one level down. table now points at level0, the last level.
ECE 391 · Discussion 8
12
Walk: inspect the level-0 leaf
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
unsigned long vpn[3]; vpn[0] = VPN0(vaddr); // = 12
#define VPN(vma) ((vma) / PAGE_SIZE) // PTE_CNT = 512
#define VPN0(vma) ((VPN(vma) >> (0 * 9)) % PTE_CNT)
#define PTE_VALID(pte) (((pte).flags & PTE_V) != 0)
#define PTE_LEAF(pte) (((pte).flags & (PTE_R|PTE_W|PTE_X))!=0)
#define PTE_V (1 << 0) #define PTE_R (1 << 1)
root · level 2
[0] V
[1]
⋮
[510]
[511]
level1 · level 1
[0] V
[1]
⋮
[510]
[511]
level0 · level 0
[0]
⋮
[12] V R
⋮
[511]
↑ table
data page
0x80005000
table: level0
pte: V|R · ppn = 0x80005
paddr: ?
R = 1 makes level0[12] a readable leaf, so all three asserts pass. Its PPN names the data page.
ECE 391 · Discussion 8
13
Walk: form the physical address
vaddr = 0xC000
vpn[2] = VPN2(vaddr) = 0
vpn[1] = VPN1(vaddr) = 0
vpn[0] = VPN0(vaddr) = 12
offset = 0x000
table = (struct pte *)((fake_satp << 20) >> 8);
pte = table[vpn[2]]; // level 2 (root)
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[1]]; // level 1
assert(PTE_VALID(pte)); assert(!PTE_LEAF(pte));
table = (struct pte *)((uintptr_t)pte.ppn << PAGE_ORDER);
pte = table[vpn[0]]; // level 0 (leaf)
assert(PTE_VALID(pte)); assert(PTE_LEAF(pte));
assert((pte.flags & PTE_R) != 0);
offset = vaddr & (PAGE_SIZE - 1);
paddr = ((unsigned long)pte.ppn << PAGE_ORDER) | offset;
Definitions used on this step
#define PAGE_ORDER 12
#define PAGE_SIZE (1UL << PAGE_ORDER) // 4096; - 1 = 0xFFF
struct pte { uint64_t flags:8, rsw:2, ppn:44, reserved:10; };
unsigned long vaddr = 0xC000;
root · level 2
[0] V
[1]
⋮
[510]
[511]
level1 · level 1
[0] V
[1]
⋮
[510]
[511]
level0 · level 0
[0]
⋮
[12] V R
⋮
[511]
↑ table
data page
0x80005000
table: level0
pte: V|R · ppn = 0x80005
paddr: 0x80005000
0x80005 << 12 | 0x000 = 0x80005000. The demo hardcoded this page. Where would a real mapper get one?
ECE 391 · Discussion 8
14
Page tables need physical pages
free physical pages
each box: one 4 KiB page
alloc_phys_page()
a new page subtable
[0]
⋮
[511]
Needed when a walk would reach an invalid non-leaf entry: allocate, zero, point the PTE at it.
a mapped data page
0x80005000
(demo value, illustrative)
The page a leaf PTE's PPN names. The demo hardcoded one; a real mapper allocates it.
One new mapping can cost up to three pages: a level-1 table, a level-0 table, and the data page.
ECE 391 · Discussion 8
15
MP3 CP2 allocator contract
sys/memory.h (release)
void * alloc_phys_page(void);
void free_phys_page(void * pp);
void * alloc_phys_pages(unsigned int cnt);
void free_phys_pages(void * pp, unsigned int cnt);
unsigned long free_phys_page_count(void);
Exact fit: remove that chunk and return it.
Otherwise: split the smallest chunk that is large enough.
Nothing fits: alloc_phys_pages should panic.
Free with the same cnt you allocated.
alloc_phys_page() → one page
pp
alloc_phys_pages(3) → a contiguous run
pp
pp+P
pp+2P
returns pp, the first page
Physically contiguous = adjacent page frames, not merely consecutive virtual addresses.
P = PAGE_SIZE = 4096
ECE 391 · Discussion 8
16
Build the initial free runs
physical RAM (low → high address)
RAM_START
RAM_END
firmware
(reserved)
kernel image
text · rodata · data
free
reserved
free
hdr
hdr
X
Y
free_chunk_list
@X
pagecnt = n₁
@Y
pagecnt = n₂
NULL
memory_init must never put reserved or already-used pages on the list.
ECE 391 · Discussion 8
17
A chunk describes a run
sys/memory.c (release)
struct page_chunk {
struct page_chunk * next; // next page chunk in list
unsigned long pagecnt; // number of pages in chunk
};
16 bytes of bookkeeping, stored inside the free memory it describes.
next chunk: anywhere in RAM
next
pagecnt=4
X
X+P
X+2P
X+3P
one chunk
(4 free pages)
The node's address is the run's start: chunk == (void *)X.
One node covers pagecnt consecutive pages.
Free memory stores its own list. No separate array of page records.
ECE 391 · Discussion 8
18
The free-chunk list
list order
free_chunk_list
A
pagecnt = 6
B
pagecnt = 2
C
pagecnt = 4
NULL
address order
low → high
used
used
hdr
hdr
hdr
C
C+P
C+2P
C+3P
A
A+P
A+2P
A+3P
A+4P
A+5P
B
B+P
P = PAGE_SIZE = 4096 · each box is one page
free pages = 6 + 2 + 4 = 12
List order is not address order. The count sums pagecnt; it does not count nodes.
ECE 391 · Discussion 8
19
Allocate one page: select and split
list order
6 ≥ 1: fits
2 ≥ 1: smallest
4 ≥ 1: fits
free_chunk_list
A
pagecnt = 6
B
pagecnt = 1
C
pagecnt = 4
NULL
address order
low → high
used
used
out
hdr
hdr
hdr
C
C+P
C+2P
C+3P
A
A+P
A+2P
A+3P
A+4P
A+5P
B
B+P
alloc_phys_page() returns B+P
free pages = 6 + 1 + 4 = 11
Split from the end: B's header stays where it is, and only its pagecnt drops from 2 to 1.
ECE 391 · Discussion 8
20
Exact fit removes a node
list order
6 ≥ 1: fits
1 = 1: exact
not reached
free_chunk_list
A
pagecnt = 6
B (unlinked)
pagecnt = 1
C
pagecnt = 4
NULL
address order
low → high
used
used
out
in use
hdr
hdr
C
C+P
C+2P
C+3P
A
A+P
A+2P
A+3P
A+4P
A+5P
B
B+P
alloc_phys_page() returns B
free pages = 6 + 4 = 10
B has exactly 1 page: unlink it and return B itself. Never leave a node with pagecnt = 0.
ECE 391 · Discussion 8
21
Unlink through the owning pointer
struct page_chunk ** chunkptr = &free_chunk_list;
... advance: chunkptr = &chunk->next; ...
*chunkptr = chunk->next; // unlink chunk
chunkptr holds the address of whichever pointer points at the current chunk.
free_chunk_list
A
next
6
B (chunk)
next
1
C
next
4
after: A.next = B.next = C
chunkptr
chunkptr == &A->next
If B were the head, chunkptr would be &free_chunk_list, and the same line would update the head.
One write through the owning pointer: no special case for the head.
ECE 391 · Discussion 8
22
Allocate three contiguous pages
list order
6 ≥ 3: fits
4 ≥ 3: smallest
free_chunk_list
A
pagecnt = 6
C
pagecnt = 1
NULL
address order
low → high
out
out
out
used
used
in use
in use
hdr
hdr
C
C+P
C+2P
C+3P
A
A+P
A+2P
A+3P
A+4P
A+5P
B
B+P
alloc_phys_pages(3) returns C+P
free pages = 6 + 1 = 7
The caller gets C+P, C+2P, C+3P: three adjacent frames. Three scattered pages would not do.
ECE 391 · Discussion 8
23
How to Free a Page
list order
new head
free_chunk_list
B
pagecnt = 1
A
pagecnt = 6
C
pagecnt = 1
NULL
address order
low → high
in use
in use
in use
used
used
in use
hdr
hdr
hdr
C
C+P
C+2P
C+3P
A
A+P
A+2P
A+3P
A+4P
A+5P
B
B+P
free_phys_page(B)
free pages = 1 + 6 + 1 = 8
Write a header at B (pagecnt = 1, next = old head), then make B the new head.
ECE 391 · Discussion 8
24
Free total versus largest run
list: B1 → A6 → C1 · address order below
in use (3)
used
used
in use
hdr
hdr
hdr
C: 1
A: 6 pages
B: 1
total free
8
1 + 6 + 1
largest run
6
chunk A
alloc_phys_pages(7)
panic
no single chunk has 7 pages
inset: freed neighbours stay separate
hdr
hdr
C
C+P
If C+P..C+3P are freed later, they become a new node beside C1. Without coalescing that is two chunks (1 + 3), not one chunk of 4.
ECE 391 · Discussion 8
25
Try the next allocation
list order
1 < 5: too small
6 ≥ 5: only fit
1 < 5: too small
free_chunk_list
B
pagecnt = 1
A
pagecnt = 6
A
pagecnt = 1
C
pagecnt = 1
NULL
address order
low → high
in use (3)
used
out: 5 adjacent pages
used
in use
hdr
hdr
hdr
C
A
A+P
A+2P
A+3P
A+4P
A+5P
B
B+P
alloc_phys_pages(5) →
A+P
free pages =
1 + 1 + 1 = 3
Justify it: which chunk, what return address, the new list, the new count?
Recap: exact fit first, else the smallest fit · split from the end · free pushes a header at the head
ECE 391 · Discussion 8
26