Operating System: Xv6 on RISC-V - Part 3

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