Excellent questions! These touch on fundamental OS memory management concepts. Let me answer each one with examples from xv6.
1. Are Page Tables Stored in Pages?
YES! Page tables themselves are stored in 4KB pages.
Where are they allocated?
Perfect! Now let me give you comprehensive answers with code examples.
Comprehensive Answers
1. ✅ YES: Page Tables Are Stored in Pages
Each page table occupies exactly ONE 4KB page.
Where are they defined and allocated?
Code example from vm.c:
// Creating kernel page table
pagetable_t kvmmake(void) {
pagetable_t kpgtbl;
kpgtbl = (pagetable_t) kalloc(); // ← Allocates ONE 4KB page!
memset(kpgtbl, 0, PGSIZE); // Zero out the page
// Now use this page as a page table...
return kpgtbl;
}
The walk() function dynamically allocates page tables:
pte_t *walk(pagetable_t pagetable, uint64 va, int alloc) {
for(int level = 2; level > 0; level--) {
pte_t *pte = &pagetable[PX(level, va)];
if(*pte & PTE_V) {
pagetable = (pagetable_t)PTE2PA(*pte);
} else {
// Page table doesn't exist yet!
if(!alloc || (pagetable = (pde_t*)kalloc()) == 0) // ← Allocate new page table page
return 0;
memset(pagetable, 0, PGSIZE); // Zero it out
*pte = PA2PTE(pagetable) | PTE_V; // Link it in
}
}
return &pagetable[PX(0, va)];
}
Where are they stored?
In physical RAM, managed by the kernel memory allocator (kalloc.c):
Physical Memory Layout:
┌─────────────────────────────────────────┐
│ 0x80000000: Kernel code & data │
│ ... │
│ 0x80xxxxxx: end (end of kernel) │
├─────────────────────────────────────────┤
│ FREE MEMORY POOL (managed by kalloc) │
│ │
│ - Page table pages allocated here │ ← kalloc() gives you pages from here
│ - User process pages │
│ - Kernel stacks │
│ - Pipe buffers │
│ - Any other dynamic allocations │
│ │
│ 0x88000000: PHYSTOP (end of RAM) │
└─────────────────────────────────────────┘
The allocator (kalloc.c) maintains a free list:
struct {
struct spinlock lock;
struct run *freelist; // ← Linked list of free pages
} kmem;
// Allocate one 4KB page
void *kalloc(void) {
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist; // Take first free page
if(r)
kmem.freelist = r->next; // Update free list
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // Fill with junk
return (void*)r; // Return pointer to the page
}
2. Why 4KB Pages Instead of 2MB Pages?
YES! Using 4KB pages avoids excessive memory waste.
The Trade-off
| Aspect | 4KB Pages | 2MB Pages |
|---|---|---|
| Granularity | Fine (4KB units) | Coarse (2MB units) |
| Internal Fragmentation | Low (max 4KB waste/allocation) | High (up to 2MB waste) |
| TLB Entries | More entries needed | Fewer entries needed |
| Page Table Size | Larger (3 levels) | Smaller (2 levels) |
| Best Use | General purpose | Large databases, scientific computing |
Example: Allocating a Small Program
With 4KB pages:
With 2MB pages:
Real-World OS Approach
Modern OSes use BOTH:
- 4KB pages: Default for most allocations
- 2MB/1GB huge pages: Optional for large applications (databases, VMs)
- Linux: hugetlbfs
- Requires explicit request from application
3. ✅ YES: xv6 and Real OSes Use Dynamic Allocation
Pages are allocated on-demand, not pre-allocated!
xv6's On-Demand Allocation
Example 1: Growing User Stack
搜索 page fault (**/kernel/trap.c) 文本，无结果
Perfect! Now I have all the code I need.
3. Dynamic Page Allocation (Continued)
✅ YES: Pages Are Allocated On-Demand
Key Principle: "Don't allocate memory until you actually need it"
Example 1: Growing Process Memory (uvmalloc)
// Allocate PTEs and physical memory to grow process from oldsz to newsz
uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm) {
char *mem;
uint64 a;
oldsz = PGROUNDUP(oldsz);
for(a = oldsz; a < newsz; a += PGSIZE){
mem = kalloc(); // ← Allocate physical page ON-DEMAND
if(mem == 0){
uvmdealloc(pagetable, a, oldsz);
return 0;
}
memset(mem, 0, PGSIZE);
// Create page table mapping
if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
kfree(mem);
uvmdealloc(pagetable, a, oldsz);
return 0;
}
}
return newsz;
}
What happens:
1. Process calls sbrk() to grow heap
2. Kernel allocates pages one by one
3. Each page gets mapped into page table
4. Only allocates what's needed!
Example 2: Creating Page Tables On-Demand (walk)
pte_t *walk(pagetable_t pagetable, uint64 va, int alloc) {
for(int level = 2; level > 0; level--) {
pte_t *pte = &pagetable[PX(level, va)];
if(*pte & PTE_V) {
// Page table exists, follow it
pagetable = (pagetable_t)PTE2PA(*pte);
} else {
// Page table DOESN'T exist yet!
if(!alloc)
return 0; // Caller said don't allocate
// Allocate a new page table page NOW
pagetable = (pde_t*)kalloc();
if(pagetable == 0)
return 0;
memset(pagetable, 0, PGSIZE);
*pte = PA2PTE(pagetable) | PTE_V; // Link it in
}
}
return &pagetable[PX(0, va)];
}
What happens: - When mapping a new VA, if intermediate page tables don't exist - They are created ON-THE-FLY - No need to pre-allocate all possible page tables!
Memory Savings Example
Scenario: Process with sparse memory usage
Process wants to map:
- 4KB at VA 0x0000 (code)
- 4KB at VA 0x1000 (data)
- 4KB at VA 0x3FFFFF000 (stack at top of address space)
❌ Pre-allocation Approach (Terrible!)
Would need:
- Level 2: 1 page table (512 entries)
- Level 1: 512 page tables (one for each L2 entry)
- Level 0: 512 × 512 page tables
Total page tables: 1 + 512 + 262,144 = 262,657 pages
= 262,657 × 4KB = 1,050 MB just for page tables!
Plus 3 pages for actual data = 1,050 MB + 12 KB
✅ On-Demand Allocation (Smart!)
Actually need:
- Level 2: 1 page table (root)
- Level 1: 2 page tables (one for low memory, one for high memory)
- Level 0: 2 page tables (one for code/data, one for stack)
Total page tables: 1 + 2 + 2 = 5 pages
= 5 × 4KB = 20 KB for page tables
Plus 3 pages for actual data = 20 KB + 12 KB = 32 KB total
Savings: 1,050 MB - 32 KB ≈ 1,050 MB saved! 🎉
Real-World OS: Linux Example
Linux uses even MORE sophisticated techniques:
1. Copy-on-Write (COW)
// When fork() creates child process:
// - Don't copy pages immediately
// - Mark all pages as read-only
// - When either process writes, THEN copy the page
Parent writes → triggers page fault → copy page → both have separate copies
2. Demand Paging
// When exec() loads a program:
// - Don't load all pages from disk
// - Mark pages as "not present"
// - When accessed → page fault → load from disk NOW
Access code page → page fault → read from executable → map it
3. Swap (Linux/Windows)
// When memory is full:
// - Move unused pages to disk
// - Mark PTEs as "swapped out"
// - When accessed → page fault → load from disk
Access swapped page → page fault → read from swap → restore to RAM
4. Huge Pages (Optional)
// Application can request 2MB pages:
mmap(..., MAP_HUGETLB, ...);
// Kernel uses 2-level page table instead of 3-level
// Fewer TLB misses for large data structures
Summary Table
| Question | Answer | Key Point |
|---|---|---|
| Are page tables stored in pages? | ✅ YES | Each page table = 1 × 4KB page |
| Where defined? | kalloc() in kalloc.c |
From free memory pool |
| Where stored? | Physical RAM above kernel | Between end and PHYSTOP |
| Why 4KB not 2MB? | ✅ Reduces waste | 4KB = fine granularity, less fragmentation |
| Dynamic allocation? | ✅ YES | Pages allocated on-demand, not pre-allocated |
| Page tables dynamic? | ✅ YES | Created by walk() as needed |
| Real OS same? | ✅ YES + more | + COW, demand paging, swap, huge pages |
Visual Summary
Memory Allocation Timeline:
Time 0: Process created
┌────────────────────┐
│ Root page table │ ← 1 page allocated
└────────────────────┘
Time 1: Map first page at VA 0x0
┌────────────────────┐
│ Root page table │
├────────────────────┤
│ Level 1 page table │ ← 1 more page allocated
├────────────────────┤
│ Level 0 page table │ ← 1 more page allocated
├────────────────────┤
│ Data page │ ← 1 more page allocated
└────────────────────┘
Total: 4 pages
Time 2: Map another page at VA 0x1000 (same L1/L0 table)
┌────────────────────┐
│ Root page table │
├────────────────────┤
│ Level 1 page table │
├────────────────────┤
│ Level 0 page table │
├────────────────────┤
│ Data page 1 │
├────────────────────┤
│ Data page 2 │ ← Only 1 more page needed!
└────────────────────┘
Total: 5 pages (reused page tables!)
🎯 On-demand = allocate only when needed = huge savings!
This design is fundamental to making virtual memory practical and efficient! 🚀