Operating System: Xv6 on RISC-V - Part 3
Published:
Operating System: Xv6 on RISC-V - Paging & Page Table
Paging
- Physical memory partitioned into equal-sized page frames. The typical size of a page frame is 4KB. Other possible page sizes: 512B, 64KB, 1MB, 4MB, etc
- Memory only allocatied in page frames. No external fragmentation. Can still have internal fragmentation(no enought space left within a page frame).
Physical Address
- A physical address can be split into a pait (f, o)
- f: frame number (f_max frames)
- o: offset within the frame (O_max bytes/frame)
- Physical address = f * O_max + o
- As long as frame size is power of 2, easy to split address using bitwise operations
Physical Address Example
Suppose a 16-bit address space with 512(2^9) byte page frames.
Address 1542(0x0606) can be translated to:
- Frame: 1542 / 512 = 0x606 » 9 = 3
- Offset: 1542 % 512 = 0x606 & 0x1ff = 6
Virtual Address
- A process’s virtual address space is partitioned into equal-sized pages. A virtual address is a pair (p, o)
Virtual page size = Physical frame size- p: page number (p_max pages)
- o: offset within the page (O_max bytes/page)
- Virtual address = p * O_max + o
Page Mapping
- 1:1 mapping of page-aligned virtual addresses to physical frames
- Imagine a big ole’ table (BOT):
- Number of table entries = number of virtual page addresses/page size
- Address translation:
- Virtual page number -> BOT entry -> Physical frame number
- Add offset to physical frame number to get physical address
- Pages are contiguous in virtual address space, but not necessarily in physical address space
- Not all pages are mapped to physical memory at all times
- Some pages may be swapped out to disk
- Some pages may be shared between processes
Page Table
Dealing with Large Tables
- Add additional levels of page table
- Sub-dividing page number into k parts
A single-level, 1-1 page table takes enormous space.
- Linked list – too slow to walk
- Hashed table – collision
- Multi-level page table
32-bit x86 Page Table
- Each table is exactly one page. 4KB(4096) for x86
- Two-level of page table
- Page Directory: 1024 entries
- Page Table: 1024 entries
- CR3 (a control register): stores the physical base (PA » 12) of the page directory table
Page Table Entries(PTEs)
- Fixed bits for the PFN (Page frame number) of the next PTs or pages.
- Physical address = PFN * page size
- The remaining bits are used for flags, or reserved for OS use
- P (Present): Is the page present or not?
- R/W (Read/Write): Is the page read-only or readable/writable?
- U/S (User or Supervisor): User or kernel page?
- A (Accessed): page has been read
- D (Dirty): page has been written
- G (Global): page is shared among processes
32-bit Paging Example
In the 32-bit x86 architecture, the size of the page is 4KB. So the offset need multiple 4.
- A 32-bit page table can reference up to 4GB of physical memory.
Question 1
- If you have:
- 34-bit address space (both VA & PA)
- 1024-byte pages
- Each PTE needs at least 6 flags and 2 bits reserved
- How many levels of page tables?
Calculate the number of levels of page tables
- Offset: log2(1024) = 10 bits
- Virtual Page Number (VPN) Bits: 34 bits - 10 offset bits = 24 bits
- Physical Page Frame Number (PPN) Bits: 34 bits - 10 offset bits = 24 bits
- Page Table Entry (PTE) Size: Each PTE needs to hold the PPN (24 bits), 6 flags (F) and 2 reserved bits.
- PTE Size = PPN bits + F bits + reserved bits = 24 + 6 + 2 = 32 bits
- Number of bytes per PTE: 32 bits / 8 bits/byte = 4 bytes
- Levels of page tables (Multi-level paging):
- The number of levels is determined by the size of the VPN and the maximum size a single page table can accommodate.
- L = VPN bits / log2(page size/bytes per PTE)
= 24 / log2(1024/4)
= 24 / log2(256)
= 24 / 8
= 3 levels
Question 2
- How many levels of page tables are needed for 64-bit address space?
- Each page is still 4KB
- Each PTE or PDE or any intermediate-level entry is 64 bits (8 bytes)
- Is it practical to map all 0~2^{64} -1 VAs to all 0~2^{64} -1 PAs?
Calculate the number of levels of page tables
- Number of PTEs per page: 4KB / 8 bytes = 512 PTEs
- PTE bits: 9 bits
- VPN bits: 64 bits - 12 offset bits = 52 bits
- Levels: 52 / 9 = 6 levels
64-bit Page Table (4-Level)
RISC-V Page Table Entry
- Physical page number: Identifies 44-bit physical page location; MMU replaces virtual bits with these physical bits
- V: If set, an entry for this virtual address exists
- U: If set, userspace can access this virtual address
- X, W, R: If set, the CPU can execute, write, or read this virtual address
RISC-V Page Table Flags
Translation Lookaside Buffer (TLB)
Managing TLB
- Address translations are mostly handled by TLB
- Software loaded TLB (OS); TLB miss faults to OS, OS finds right PTE and loads TLB; OS picks the page table format; May be slow (20-200 cycles typically)
- Hardware (memory management unit (MMU)); Hardware knows where page tables are in memory (e.g., from CR3)
Lager Page Size
- Even with TLB, TLB misses can be expensive
- Happens at the first time any page is accessed (unless with TLB prefetching)
- For random (non-sequential) access patterns, may have more TLB misses
- Making TLB misses cheaper -> Larger page sizes!
- Pages larger than the default 4KB size -> Called huge pages or super pages
- Huge pages can be any power of 2
- Minimizes TLB misses
- Reduces the number of page table entries
- Improves I/O performance
Huge Pages
- Allocating huge pages can be hard
- Need to allocate 2MB or 1GB contiguous physical memory
- Causes external fragmentation
- Explicitly specifying huge pages
mmap(NULL, 8*1024 *1024, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB, -1, 0))
madvise(ptr, 8*1024*1024, MADV_HUGEPAGE)
advice to the OS
- Transparently using huge pages
- The OS can transparently replace continuous 2MB or 1GB memory blocks with huge pages