Virtual Memory in FRISC OS
FRISC uses Sv39 paging (39-bit virtual addresses) providing 512 GiB of virtual address space per process. This post covers our implementation of virtual memory, page tables, and the page fault handler written in Lateralus.
◉ Why Virtual Memory
Virtual memory provides:
- Process isolation — each process has its own address space
- Memory protection — kernel code protected from user code
- Demand paging — only allocate physical memory when accessed
- Memory-mapped files — treat files as memory regions
- Shared memory — multiple processes share physical pages
◉ Sv39 Address Format
A 39-bit virtual address is split into:
// 39-bit virtual address layout
// ┌──────────────────────────────────────────────────────────────────┐
// │ 63-39: sign ext │ 38-30: VPN[2] │ 29-21: VPN[1] │ 20-12: VPN[0] │ 11-0: offset │
// │ (25 bits) │ (9 bits) │ (9 bits) │ (9 bits) │ (12 bits) │
// └──────────────────────────────────────────────────────────────────┘
const PAGE_SIZE: int = 4096 // 2^12 = 4 KiB pages
const VPN_BITS: int = 9 // 512 entries per page table
const PAGE_OFFSET_BITS: int = 12
fn extract_vpn(vaddr: u64, level: int) -> int {
let shift = PAGE_OFFSET_BITS + level * VPN_BITS
((vaddr >> shift) & 0x1FF) as int
}◉ Page Table Entry
// Page Table Entry (PTE) format
// ┌─────────────────────────────────────────────────────────────┐
// │ 63-54: reserved │ 53-10: PPN │ 9-8: RSW │ 7-0: flags │
// └─────────────────────────────────────────────────────────────┘
const PTE_VALID: u64 = 1 << 0 // Entry is valid
const PTE_READ: u64 = 1 << 1 // Readable
const PTE_WRITE: u64 = 1 << 2 // Writable
const PTE_EXEC: u64 = 1 << 3 // Executable
const PTE_USER: u64 = 1 << 4 // User accessible
const PTE_GLOBAL: u64 = 1 << 5 // Global mapping
const PTE_ACCESSED: u64 = 1 << 6 // Has been accessed
const PTE_DIRTY: u64 = 1 << 7 // Has been written
struct PageTableEntry {
bits: u64,
}
impl PageTableEntry {
fn new(ppn: u64, flags: u64) -> PageTableEntry {
PageTableEntry { bits: (ppn << 10) | flags }
}
fn is_valid(self) -> bool {
(self.bits & PTE_VALID) != 0
}
fn is_leaf(self) -> bool {
// Leaf if R, W, or X bit is set
(self.bits & (PTE_READ | PTE_WRITE | PTE_EXEC)) != 0
}
fn ppn(self) -> u64 {
(self.bits >> 10) & 0xFFFFFFFFFFF // 44-bit PPN
}
fn flags(self) -> u64 {
self.bits & 0xFF
}
}◉ Page Table Structure
// Three-level page table
// Root (L2) -> L1 -> L0 -> Physical Page
struct PageTable {
entries: [PageTableEntry; 512],
}
impl PageTable {
fn new() -> *mut PageTable {
let page = kalloc_page()
memset(page, 0, PAGE_SIZE)
page as *mut PageTable
}
fn entry(self, index: int) -> *mut PageTableEntry {
&self.entries[index]
}
}◉ Virtual-to-Physical Translation
fn translate(root: *mut PageTable, vaddr: u64) -> Option[u64] {
let mut table = root
// Walk L2 -> L1 -> L0
for level in [2, 1, 0] {
let vpn = extract_vpn(vaddr, level)
let pte = (*table).entry(vpn)
if !(*pte).is_valid() {
return None // Invalid mapping
}
if (*pte).is_leaf() {
// Found physical page
let ppn = (*pte).ppn()
let offset = vaddr & 0xFFF
return Some((ppn << 12) | offset)
}
// Next level table
table = ((*pte).ppn() << 12) as *mut PageTable
}
None // Should not reach here
}◉ Mapping Pages
fn map_page(
root: *mut PageTable,
vaddr: u64,
paddr: u64,
flags: u64
) -> Result[(), MemError] {
let mut table = root
// Walk/create L2 -> L1, stop before L0
for level in [2, 1] {
let vpn = extract_vpn(vaddr, level)
let pte = (*table).entry(vpn)
if !(*pte).is_valid() {
// Allocate new page table
let new_table = PageTable::new()
*pte = PageTableEntry::new(
(new_table as u64) >> 12,
PTE_VALID
)
}
table = ((*pte).ppn() << 12) as *mut PageTable
}
// Insert L0 entry (the actual mapping)
let vpn0 = extract_vpn(vaddr, 0)
let pte = (*table).entry(vpn0)
if (*pte).is_valid() {
return Err(MemError::AlreadyMapped)
}
*pte = PageTableEntry::new(paddr >> 12, flags | PTE_VALID)
sfence_vma(vaddr) // Flush TLB for this address
Ok(())
}◉ Page Fault Handler
// Page fault causes (scause values)
const CAUSE_FETCH_PAGE_FAULT: u64 = 12
const CAUSE_LOAD_PAGE_FAULT: u64 = 13
const CAUSE_STORE_PAGE_FAULT: u64 = 15
fn handle_page_fault(
cause: u64,
stval: u64, // Faulting address
frame: *mut TrapFrame
) {
let vaddr = stval
let proc = current_process()
serial_log("[fault] pid=" + str(proc.pid) +
" addr=0x" + hex(vaddr) +
" cause=" + str(cause))
// Find which memory region this address belongs to
let region = match proc.find_region(vaddr) {
Some(r) => r,
None => {
// Segmentation fault - invalid address
serial_log("[segfault] killing process " + str(proc.pid))
proc.terminate(SIGSEGV)
return
}
}
// Check permissions
let access = match cause {
CAUSE_FETCH_PAGE_FAULT => Access::Execute,
CAUSE_LOAD_PAGE_FAULT => Access::Read,
CAUSE_STORE_PAGE_FAULT => Access::Write,
_ => unreachable(),
}
if !region.permits(access) {
serial_log("[permission denied] killing process " + str(proc.pid))
proc.terminate(SIGSEGV)
return
}
// Demand paging: allocate physical page
let paddr = match kalloc_page() {
Some(p) => p,
None => {
// Out of memory - try to swap, or kill
if !try_swap_out() {
proc.terminate(SIGKILL)
return
}
kalloc_page().unwrap()
}
}
// Initialize page content
match region.kind {
RegionKind::Anonymous => {
// Zero-fill for anonymous mappings
memset(paddr, 0, PAGE_SIZE)
},
RegionKind::File(file, offset) => {
// Load from file
file.read_at(vaddr - region.start + offset, paddr, PAGE_SIZE)
},
RegionKind::CopyOnWrite(src) => {
// Copy from source page
memcpy(paddr, src, PAGE_SIZE)
},
}
// Map the page
let flags = region.to_pte_flags()
map_page(proc.page_table, vaddr & ~0xFFF, paddr, flags)
serial_log("[mapped] 0x" + hex(vaddr) + " -> 0x" + hex(paddr))
}◉ Memory Regions
struct MemoryRegion {
start: u64,
end: u64,
kind: RegionKind,
permissions: Permissions,
}
enum RegionKind {
Anonymous, // Zero-filled
File(File, offset: u64), // Memory-mapped file
CopyOnWrite(*mut u8), // COW after fork()
}
struct AddressSpace {
root: *mut PageTable,
regions: [MemoryRegion],
// Standard regions
code_start: u64, // 0x0000_0000_0040_0000
heap_start: u64, // After code
heap_end: u64, // brk() grows this
stack_top: u64, // 0x0000_003F_FFFF_F000
stack_bottom: u64, // Grows down
}◉ TLB Management
// RISC-V TLB flush instructions
fn sfence_vma_all() {
// Flush entire TLB
asm!("sfence.vma")
}
fn sfence_vma(vaddr: u64) {
// Flush single address
asm!("sfence.vma {}", in(reg) vaddr)
}
fn sfence_vma_asid(asid: u64) {
// Flush all entries for an address space
asm!("sfence.vma zero, {}", in(reg) asid)
}
// Use ASID to avoid flushing on context switch
impl AddressSpace {
fn switch_to(self) {
// Set satp: Mode=Sv39 (8), ASID, PPN of root table
let satp = (8 << 60) | (self.asid << 44) | (self.root as u64 >> 12)
write_csr!(satp, satp)
sfence_vma_asid(self.asid)
}
}◉ Kernel vs User Space
// FRISC memory layout
//
// 0xFFFF_FFFF_FFFF_FFFF ┌─────────────────────┐
// │ Kernel (direct │
// 0xFFFF_FFC0_0000_0000 │ mapped) │
// ├─────────────────────┤
// │ (hole) │
// 0x0000_0040_0000_0000 ├─────────────────────┤
// │ User stack │
// │ (grows down) │
// ├─────────────────────┤
// │ mmap region │
// ├─────────────────────┤
// │ heap (brk) │
// ├─────────────────────┤
// │ code + data │
// 0x0000_0000_0040_0000 └─────────────────────┘
const USER_BASE: u64 = 0x0000_0000_0040_0000
const USER_TOP: u64 = 0x0000_0040_0000_0000
const KERNEL_BASE: u64 = 0xFFFF_FFC0_0000_0000◉ Performance
- Lazy allocation — pages allocated on first access, not at mmap() time
- ASID tracking — 16-bit ASID avoids full TLB flush on context switch
- Huge pages — 2 MiB pages for large mappings (coming in FRISC 0.3)
- Page table caching — recently freed page tables kept in pool
Next up: SMP support and CPU bring-up. Full virtual memory implementation in the FRISC kernel.