Virtual Memory I CSE 351 Autumn 2016
Roadmap
1
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CMPT 295
Virtual Memory I
1
Virtual Memory (VM*)
Overview and motivation
VM as a tool for caching
Address translation
VM as a tool for memory management
VM as a tool for memory protection
2
*Not to be confused with “Virtual Machine” which is a whole other thing.
Warning: Virtual memory is pretty complex, but crucial for understanding how processes work and for debugging performance
CMPT 295
Virtual Memory I
2
Memory as we know it so far… is virtual!
Programs refer to virtual memory addresses
Conceptually memory is just a very large array of bytes
System provides private address space to each process
Allocation: Compiler and run-time system
Where different program objects should be stored
All allocation within single virtual address space
But…
We probably don’t have bytes of physical memory
We certainly don’t have bytes of physical memory
for every process
Processes should not interfere with one another
Except in certain cases where they want to share code or data
3
0xFF∙∙∙∙∙∙F
0x00∙∙∙∙∙∙0
CMPT 295
Virtual Memory I
3
Problem 1: How Does Everything Fit?
4
64-bit virtual addresses can address
several exabytes
(18,446,744,073,709,551,616 bytes)
Physical main memory offers
a few gigabytes
(e.g. 8,589,934,592 bytes)
?
1 virtual address space per process, with many processes…
(Not to scale; physical memory would be smaller than the period at the end of this sentence compared to the virtual address space.)
CMPT 295
Virtual Memory I
4
Problem 2: Memory Management
5
Physical main memory
What goes where?
stack
heap
.text
.data
…
Process 1
Process 2
Process 3
…
Process n
x
Each process has…
We have multiple
processes:
CMPT 295
Virtual Memory I
5
Problem 3: How To Protect
6
Physical main memory
Process i
Process j
Problem 4: How To Share?
Physical main memory
Process i
Process j
CMPT 295
Virtual Memory I
6
How can we solve these problems?
“Any problem in computer science can be solved by adding another level of indirection.” – David Wheeler, inventor of the subroutine
Without Indirection
With Indirection
7
What if I want to move Thing?
P2
Thing
P1
P3
P2
Thing
P3
P1
NewThing
NewThing
CMPT 295
Virtual Memory I
Quote attributed to David Wheeler or Butler Lampson (http://en.wikipedia.org/wiki/Butler_Lampson)
7
Indirection
Indirection: The ability to reference something using a name, reference, or container instead of the value itself. A flexible mapping between a name and a thing allows changing the thing without notifying holders of the name.
Adds some work (now have to look up 2 things instead of 1)
But don’t have to track all uses of name/address (single source!)
Examples:
Phone system: cell phone number portability
Domain Name Service (DNS): translation from name to IP address
Call centers: route calls to available operators, etc.
Dynamic Host Configuration Protocol (DHCP): local network address assignment
8
CMPT 295
Virtual Memory I
A System Using Physical Addressing
9
Used in “simple” systems with (usually) just one process:
Embedded microcontrollers in devices like cars, elevators, and digital picture frames
0:
1:
M-1:
Main memory
CPU
2:
3:
4:
5:
6:
7:
Physical address (PA)
Data (int/float)
8:
…
0x4
CMPT 295
Virtual Memory I
9
A System Using Virtual Addressing
10
Physical addresses are completely invisible to programs
Used in all modern desktops, laptops, servers, smartphones…
One of the great ideas in computer science
0:
1:
M-1:
Main memory
MMU
2:
3:
4:
5:
6:
7:
Physical address
(PA)
Data (int/float)
8:
…
CPU
Virtual address
(VA)
CPU Chip
0x4
0x4100
Memory Management Unit
CMPT 295
Virtual Memory I
10
Indirection in Virtual Memory
11
Each process gets its own private virtual address space
Solves the previous problems!
Physical memory
Virtual memory
Virtual memory
Process 1
Process
mapping
CMPT 295
Virtual Memory I
11
Address Spaces
Virtual address space: Set of virtual addr
{0, 1, 2, 3, …, -1}
Physical address space: Set of physical addr
{0, 1, 2, 3, …, -1}
Every byte in main memory has:
one physical address (PA)
zero, one, or more virtual addresses (VAs)
12
CMPT 295
Virtual Memory I
12
https://xkcd.com/1495/
CMPT 295
Virtual Memory I
Why Virtual Memory (VM)?
Efficient use of limited main memory (RAM)
Use RAM as a cache for the parts of a virtual address space
Some non-cached parts stored on disk
Some (unallocated) non-cached parts stored nowhere
Keep only active areas of virtual address space in memory
Transfer data back and forth as needed
Simplifies memory management for programmers
Each process “gets” the same full, private linear address space
Isolates address spaces (protection)
One process can’t interfere with another’s memory
They operate in different address spaces
User process cannot access privileged information
Different sections of address spaces have different permissions
14
CMPT 295
Virtual Memory I
Adds disks to memory hierarchy
Simplifies memory for processes & programmers
Security/protection
14
VM and the Memory Hierarchy
Think of virtual memory as array of contiguous bytes
Pages of virtual memory are usually stored in physical memory, but sometimes spill to disk
Pages are another unit of aligned memory (size is bytes)
Each virtual page can be stored in any physical page (no fragmentation!)
15
VP 0
VP 1
VP 2n-p-1
Virtual memory
Unallocated
Unallocated
0
2n-1
PP 2m-p-1
Physical memory
Empty
Empty
PP 0
PP 1
Empty
2m-1
0
Virtual pages (VP’s)
Disk
Physical pages (PP’s)
“Swap Space”
CMPT 295
Virtual Memory I
Swap space: https://www.linux.com/news/all-about-linux-swap-space
15
Why does VM work on RAM/disk?
Avoids disk accesses because of locality
Same reason that L1 / L2 / L3 caches work
The set of virtual pages that a program is “actively” accessing at any point in time is called its working set
If (working set of one process ≤ physical memory):
Good performance for one process (after compulsory misses)
If (working sets of all processes > physical memory):
Thrashing: Performance meltdown where pages are swapped between memory and disk continuously (CPU always waiting or paging)
This is why your computer can feel faster when you add RAM
16
CMPT 295
Virtual Memory I
Improving a program’s temporal locality can lead to a smaller working set (using data in one place in the program rather than many places).
Full quote: “Every problem in computer science can be solved by adding another level of indirection, but that usually will create another problem.”
16
Virtual Memory (VM)
Overview and motivation
VM as a tool for caching
Address translation
VM as a tool for memory management
VM as a tool for memory protection
17
CMPT 295
Virtual Memory I
17
Address Translation
18
0:
1:
M-1:
Main memory
MMU
2:
3:
4:
5:
6:
7:
Physical address
(PA)
Data (int/float)
8:
…
CPU
Virtual address
(VA)
CPU Chip
0x4
0x4100
Memory Management Unit
How do we perform the virtual physical address translation?
CMPT 295
Virtual Memory I
18
Address Translation: Page Tables
CPU-generated address can be split into:
Request is Virtual Address (VA), want Physical Address (PA)
Note that Physical Offset = Virtual Offset (page-aligned)
Use lookup table that we call the page table (PT)
Replace Virtual Page Number (VPN) for Physical Page Number (PPN) to generate Physical Address
Index PT using VPN: page table entry (PTE) stores the PPN plus management bits (e.g. Valid, Dirty, access rights)
Has an entry for every virtual page
19
Virtual Page Number
Page Offset
-bit address:
CMPT 295
Virtual Memory I
Page Table Diagram
Page tables stored in physical memory
Too big to fit elsewhere – managed by MMU & OS
How many page tables in the system?
One per process
20
Page Table
(DRAM)
null
null
0
1
0
0
1
1
0
1
Valid
PPN/Disk Addr
PTE 0: 0
PTE 7: 7
PTE 1: 1
PTE 2: 2
PTE 3: 3
PTE 4: 4
PTE 5: 5
PTE 6: 6
…
…
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
Virtual page #
Physical memory
(DRAM)
PP 0
PP 3
PP 2
PP 1
VP 1
VP 2
VP 7
VP 4
Physical page #
CMPT 295
Virtual Memory I
Space allocated for pages in disk called Swap Space
20
CPU
Page Table Address Translation
21
Virtual page number (VPN)
Virtual page offset (VPO)
Physical page number (PPN)
Physical page offset (PPO)
Virtual address (VA)
Physical address (PA)
Valid
PPN
Page table
base register
(PTBR)
Page table
Page table address
for process
Valid bit = 0:
page not in memory
(page fault)
In most cases, the MMU can perform this translation without software assistance
CMPT 295
Virtual Memory I
PTBR is another name for control register 3 (CR3) in x86: http://en.wikipedia.org/wiki/Control_register#CR3
21
Peer Question
How many bits wide are the following fields?
16 KiB pages
48-bit virtual addresses
16 GiB physical memory
22
34 24
(A)
32 18
(B)
30 20
(C)
34 20
(D)
VPN PPN
CMPT 295
Virtual Memory I
22
Page Hit
Page hit: VM reference is in physical memory
23
Page Table (DRAM)
null
null
0
1
0
0
1
1
0
1
Valid
PPN/Disk Addr
PTE 0
PTE 7
…
…
Virtual address
Example: Page size = 4 KiB
0x00740b
Virtual Addr:
VPN:
PPN:
Physical Addr:
Physical memory
(DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 4
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
CMPT 295
Virtual Memory I
4kB page = 2^12
3 hex digits
23
Page Fault
Page fault: VM reference is NOT in physical memory
24
Page Table (DRAM)
null
null
0
1
0
0
1
1
0
1
Valid
PPN/Disk Addr
PTE 0
PTE 7
…
…
Physical memory
(DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 4
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
Virtual address
Example: Page size = 4 KiB
Provide a virtual address request (in hex) that results in this particular page fault:
Virtual Addr:
CMPT 295
Virtual Memory I
24
Reminder: Page Fault Exception
User writes to memory location
That portion (page) of user’s memory
is currently on disk
Page fault handler must load page into physical memory
Returns to faulting instruction: LD is executed again!
Successful on second try
25
int a[1000];
int main () {
a[500] = 13;
}
80483b7: c7 05 10 9d 04 08 0d LD %t1,0x8049d10
User code
OS Kernel code
exception: page fault
Create page and
load into memory
returns
LD
handle_page_fault:
CMPT 295
Virtual Memory I
25
Handling a Page Fault
Page miss causes page fault (an exception)
26
Page Table (DRAM)
null
null
0
1
0
0
1
1
0
1
Valid
PPN/Disk Addr
PTE 0
PTE 7
…
…
Physical memory
(DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 4
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
Virtual address
CMPT 295
Virtual Memory I
26
Handling a Page Fault
Page miss causes page fault (an exception)
Page fault handler selects a victim to be evicted (here VP 4)
27
Page Table (DRAM)
null
null
0
1
0
0
1
1
0
1
Valid
PPN/Disk Addr
PTE 0
PTE 7
…
…
Physical memory
(DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 4
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
Virtual address
CMPT 295
Virtual Memory I
Check dirty bit on eviction!
27
Handling a Page Fault
Page miss causes page fault (an exception)
Page fault handler selects a victim to be evicted (here VP 4)
28
Page Table (DRAM)
null
null
0
1
0
0
1
1
1
0
Valid
PPN/Disk Addr
PTE 0
PTE 7
…
…
Physical memory
(DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 3
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
Virtual address
CMPT 295
Virtual Memory I
28
Handling a Page Fault
Page miss causes page fault (an exception)
Page fault handler selects a victim to be evicted (here VP 4)
Offending instruction is restarted: page hit!
29
Page Table (DRAM)
null
null
0
1
0
0
1
1
1
0
Valid
PPN/Disk Addr
PTE 0
PTE 7
…
…
Physical memory
(DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 3
Virtual memory
(DRAM/disk)
VP 1
VP 2
VP 4
VP 6
VP 7
VP 3
Virtual address
CMPT 295
Virtual Memory I
29
VM for Managing Multiple Processes
Key abstraction: each process has its own virtual address space
It can view memory as a simple linear array
With virtual memory, this simple linear virtual address space need not be contiguous in physical memory
Process needs to store data in another VP? Just map it to any PP!
30
Virtual Address Space for Process 1:
Physical
Address
Space (DRAM)
0
N-1
(e.g., read-only
library code)
Virtual Address Space for Process 2:
VP 1
VP 2
…
0
N-1
VP 1
VP 2
…
PP 2
PP 6
PP 8
…
0
M-1
Address
translation
CMPT 295
Virtual Memory I
30
Simplifying Linking and Loading
Linking
Each program has similar virtual address space
Code, Data, and Heap always start at the same addresses
Loading
execve allocates virtual pages for .text and .data sections & creates PTEs marked as invalid
The .text and .data sections are copied, page by page, on demand by the virtual memory system
31
Kernel virtual memory
Memory-mapped region for
shared libraries
Run-time heap
(created by malloc)
User stack
(created at runtime)
Unused
0
%sp
(stack
pointer)
Memory
invisible to
user code
brk
Read/write segment
(.data, .bss)
Read-only segment
(.init, .text, .rodata)
Loaded
from the
executable
file
CMPT 295
Virtual Memory I
31
Virtual Memory (VM)
Overview and motivation
VM as a tool for caching
Address translation
VM as a tool for memory management
VM as a tool for memory protection
32
CMPT 295
Virtual Memory I
32
VM for Protection and Sharing
The mapping of VPs to PPs provides a simple mechanism to protect memory and to share memory between processes
Sharing: map virtual pages in separate address spaces to the same physical page (here: PP 6)
Protection: process can’t access physical pages to which none of its virtual pages are mapped (here: Process 2 can’t access PP 2)
33
Virtual Address Space for Process 1:
Physical
Address
Space (DRAM)
0
N-1
(e.g., read-only
library code)
Virtual Address Space for Process 2:
VP 1
VP 2
…
0
N-1
VP 1
VP 2
…
PP 2
PP 6
PP 8
…
0
M-1
Address
translation
CMPT 295
Virtual Memory I
33
Memory Protection Within Process
VM implements read/write/execute permissions
Extend page table entries with permission bits
MMU checks these permission bits on every memory access
If violated, raises exception and OS sends SIGSEGV signal to process
(segmentation fault)
34
•
•
•
Physical
Address Space
PP 2
PP 4
PP 6
PP 8
PP 9
PP 11
Process i:
PPN
WRITE
EXEC
PP 6
No
No
PP 4
No
Yes
PP 2
Yes
No
READ
Yes
Yes
Yes
VP 0:
VP 1:
VP 2:
Yes
Yes
Yes
Valid
Process j:
WRITE
EXEC
PP 9
Yes
No
PP 6
No
No
PP 11
Yes
No
READ
Yes
Yes
Yes
VP 0:
VP 1:
VP 2:
Yes
Yes
Yes
Valid
PPN
CMPT 295
Virtual Memory I
Why no Dirty bit? Typically handled by OS.
34
Peer Question
What should the permission bits be for pages from the following sections of virtual memory?
35
Section Read Write Execute
Stack
Heap
Static Data
Literals
Instructions
CMPT 295
Virtual Memory I
/docProps/thumbnail.jpeg