Virtual Memory: Systems

- Supplementary material -

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 1

Agenda
 Simple Memory System Example
 Case study: Core i7/Linux memory system

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2

Simple Memory System Example
TLB
PTE
VPN
CPU Chip PTEA
PTE
hit

PTEA PTEA PTEA

miss
CPU L1 Memory
VA MMU Cache
PA PA PA (Mem)
miss

PA Data
hit
New
Data page
Victim
Page fault handler page
Exception

Disk

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3

Review of Symbols
 Basic Parameters
 N = 2n : Number of addresses in virtual address space
 M = 2m : Number of addresses in physical address space
 P = 2p : Page size (bytes)
 Components of the virtual address (VA)
 TLBI: TLB index
 TLBT: TLB tag
 VPO: Virtual page offset
 VPN: Virtual page number
 Components of the physical address (PA)
 PPO: Physical page offset (same as VPO)
 PPN: Physical page number
 CO: Byte offset within cache line
 CI: Cache index
 CT: Cache tag
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4
Addressing
 14-bit virtual addresses (VA)
 12-bit physical address (PA)
 Page size = 64 bytes

13 12 11 10 9 8 7 6 5 4 3 2 1 0

VPN VPO
Virtual Page Number Virtual Page Offset

11 10 9 8 7 6 5 4 3 2 1 0

PPN PPO
Physical Page Number Physical Page Offset
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 5
1. Page Table in Simple Memory System
 VPN uses 8 bits out of 14-bit VA
 256 entries in page table
 See the first 16 entries below

VPN PPN Valid VPN PPN Valid

00 28 1 08 13 1
01 – 0 09 17 1
02 33 1 0A 09 1
03 02 1 0B – 0
04 – 0 0C – 0
05 16 1 0D 2D 1
06 – 0 0E 11 1
07 – 0 0F 0D 1

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 6

2. TLB in Simple Memory System
 16 entries
 4-way associative

TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0

VPN VPO

Set Tag PPN Valid Tag PPN Valid Tag PPN Valid Tag PPN Valid
0 03 – 0 09 0D 1 00 – 0 07 02 1
1 03 – 0 02 – 0 04 – 0 0A – 0
2 02 – 0 08 11 1 06 – 0 03 – 0
3 07 – 0 03 0D 1 0A 34 1 02 – 0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7

3. Cache in Simple Memory System
 Direct mapped
 Physically addressed
 16 lines, 4-byte block size
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0

PPN PPO
Idx Tag Valid B0 B1 B2 B3 Idx Tag Valid B0 B1 B2 B3
0 19 1 99 11 23 11 8 24 1 3A 00 51 89
1 15 0 – – – – 9 2D 0 – – – –
2 1B 1 00 02 04 08 A 2D 1 93 15 DA 3B
3 36 0 – – – – B 0B 0 – – – –
4 32 1 43 6D 8F 09 C 12 0 – – – –
5 0D 1 36 72 F0 1D D 16 1 04 96 34 15
6 31 0 – – – – E 13 1 83 77 1B D3
7 16 1 11 C2 DF 03 F 14 0 – – – –
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8
Address Translation Exercise #1 - VA
Virtual Address: 0x03D4
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0 0 0 1 1 1 1 0 1 0 1 0 0

VPN VPO

VPN 0x0F
___ 0x3
TLBI ___ 0x03
TLBT ____ Y
TLB Hit? __ N
Page Fault? __ 0x0D
PPN: ____

Set Tag PPN Valid Tag PPN Valid Tag PPN Valid Tag PPN Valid
0 03 – 0 09 0D 1 00 – 0 07 02 1
1 03 – 0 02 – 0 04 – 0 0A – 0
2 02 – 0 08 11 1 06 – 0 03 – 0
3 07 – 0 03 0D 1 0A 34 1 02 – 0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9

Address Translation Exercise #1 - PA
Physical Address: 0X354
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0
0 0 1 1 0 1 0 1 0 1 0 0
PPN PPO

CI ___
0x5 CT___
0x0D CO ____
0x0 Hit? __
Y Byte: ____
0x36

Idx Tag Valid B0 B1 B2 B3 Idx Tag Valid B0 B1 B2 B3

0 19 1 99 11 23 11 8 24 1 3A 00 51 89
1 15 0 – – – – 9 2D 0 – – – –
2 1B 1 00 02 04 08 A 2D 1 93 15 DA 3B
3 36 0 – – – – B 0B 0 – – – –
4 32 1 43 6D 8F 09 C 12 0 – – – –
5 0D 1 36 72 F0 1D D 16 1 04 96 34 15
6 31 0 – – – – E 13 1 83 77 1B D3
7 16 1 11 C2 DF 03 F 14 0 – – – –

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10

Address Translation Exercise #2 - VA
Virtual Address: 0x0369
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0 0 0 1 1 0 1 1 0 1 0 0 1

VPN VPO

VPN0x0D
___ TLBI 0x01 0x03
___ TLBT ____ N
TLB Hit? __ Page Fault? __ PPN: ____

Set Tag PPN Valid Tag PPN Valid Tag PPN Valid Tag PPN Valid
0 03 – 0 09 0D 1 00 – 0 07 02 1
1 03 – 0 02 – 0 04 – 0 0A – 0
2 02 – 0 08 11 0 06 – 0 03 – 0
3 07 – 0 03 0D 1 0A 34 1 02 – 0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 11

Address Translation Exercise #2 - VA
Virtual Address: 0x0369
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0 0 0 1 1 0 1 1 0 1 0 0 1

VPN VPO

VPN0x0D
___ TLBI 0x00 0x00
___ TLBT ____ N
TLB Hit? __ N
Page Fault? __ 0x2D
PPN: ____

VPN PPN Valid VPN PPN Valid

00 28 1 08 13 1
01 – 0 09 17 1
02 33 1 0A 09 1
03 02 1 0B – 0
04 – 0 0C – 0
05 16 1 0D 2D 1
06 – 0 0E 11 1
07 – 0 0F 0D 1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12
Address Translation Exercise #2 - PA
Physical Address: 0XB69
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0
1 0 1 1 0 1 1 0 1 0 0 1
PPN PPO

CI ___
0xA CT____
0x2D CO ____
0x1 Hit? __
Y Byte: 0x15
____

Idx Tag Valid B0 B1 B2 B3 Idx Tag Valid B0 B1 B2 B3

0 19 1 99 11 23 11 8 24 1 3A 00 51 89
1 15 0 – – – – 9 2D 0 – – – –
2 1B 1 00 02 04 08 A 2D 1 93 15 DA 3B
3 36 0 – – – – B 0B 0 – – – –
4 32 1 43 6D 8F 09 C 12 0 – – – –
5 0D 1 36 72 F0 1D D 16 1 04 96 34 15
6 31 0 – – – – E 13 1 83 77 1B D3
7 16 1 11 C2 DF 03 F 14 0 – – – –

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13

Address Translation Exercise #3
Virtual Address: 0x0020
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0

VPN VPO

VPN 0x00
___ 0x0
TLBI ___ 0x00
TLBT ____ N
TLB Hit? __ N
Page Fault? __ PPN: 0x28
____

Physical Address
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0
1 0 1 0 0 0 1 0 0 0 0 0
PPN PPO
0x8
CI___ 0x28
CT___ 0x0
C0 ____ N
Hit? __ Mem
Byte: ____

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14

Agenda
 Simple memory system example
 Case study: Core i7/Linux memory system

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 15

Intel Core i7 Memory System
Processor package
Core x4
Instruction MMU
Registers
fetch (addr translation)

L1 d-cache L1 i-cache L1 d-TLB L1 i-TLB

32 KB, 8-way 32 KB, 8-way 64 entries, 4-way 128 entries, 4-way

L2 unified cache L2 unified TLB

256 KB, 8-way 512 entries, 4-way
To other
QuickPath interconnect cores
4 links @ 25.6 GB/s each To I/O
bridge
L3 unified cache DDR3 Memory controller
8 MB, 16-way 3 x 64 bit @ 10.66 GB/s
(shared by all cores) 32 GB/s total (shared by all cores)

Main memory
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16
Review of Symbols
 Basic Parameters
 N = 2n : Number of addresses in virtual address space
 M = 2m : Number of addresses in physical address space
 P = 2p : Page size (bytes)
 Components of the virtual address (VA)
 TLBI: TLB index
 TLBT: TLB tag
 VPO: Virtual page offset
 VPN: Virtual page number
 Components of the physical address (PA)
 PPO: Physical page offset (same as VPO)
 PPN: Physical page number
 CO: Byte offset within cache line
 CI: Cache index
 CT: Cache tag

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17

End-to-end Core i7 Address Translation
32/64
CPU L2, L3, and
Result
Virtual address (VA) main memory
36 12
VPN VPO L1 L1
hit miss
32 4
TLBT TLBI
L1 d-cache
TLB (64 sets, 8 lines/set)
hit
TLB
...

...
miss

L1 TLB (16 sets, 4 entries/set)

9 9 9 9 40 12 40 6 6
VPN1 VPN2 VPN3 VPN4
PPN PPO CT CI CO
Physical
CR3 address
PTE PTE PTE PTE (PA)

Page tables 18
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Core i7 Level 1-3 Page Table Entries
63 62 52 51 12 11 9 8 7 6 5 4 3 2 1 0
XD Unused Page table physical base address Unused G PS A CD WT U/S R/W P=1

Available for OS (page table location on disk) P=0

Each entry references a 4K child page table. Significant fields:

P: Child page table present in physical memory (1) or not (0).
R/W: Read-only or read-write access access permission for all reachable pages.
U/S: user or supervisor (kernel) mode access permission for all reachable pages.
WT: Write-through or write-back cache policy for the child page table.
A: Reference bit (set by MMU on reads and writes, cleared by software).
PS: Page size either 4 KB or 4 MB (defined for Level 1 PTEs only).
Page table physical base address: 40 most significant bits of physical page table
address (forces page tables to be 4KB aligned)
XD: Disable or enable instruction fetches from all pages reachable from this PTE.

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 19

Core i7 Level 4 Page Table Entries
63 62 52 51 12 11 9 8 7 6 5 4 3 2 1 0
XD Unused Page physical base address Unused G D A CD WT U/S R/W P=1

Available for OS (page location on disk) P=0

Each entry references a 4K child page. Significant fields:

P: Child page is present in memory (1) or not (0)
R/W: Read-only or read-write access permission for child page
U/S: User or supervisor mode access
WT: Write-through or write-back cache policy for this page
A: Reference bit (set by MMU on reads and writes, cleared by software)
D: Dirty bit (set by MMU on writes, cleared by software)
Page physical base address: 40 most significant bits of physical page address
(forces pages to be 4KB aligned)
XD: Disable or enable instruction fetches from this page.

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20

Core i7 Page Table Translation
9 9 9 9 12 Virtual
VPN 1 VPN 2 VPN 3 VPN 4 VPO
address

L1 PT L2 PT L3 PT L4 PT
Page global Page upper Page middle Page
40 directory 40 directory 40 directory 40 table
CR3 / / / /
Physical
address Offset into
of L1 PT /12 physical and
L1 PTE L2 PTE L3 PTE L4 PTE virtual page
Physical
address
512 GB 1 GB 2 MB 4 KB of page
region region region region
per entry per entry per entry per entry

40
/

40 12 Physical
PPN PPO
address
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21
Cute Trick for Speeding Up L1 Access
CT Tag Check

40 6 6
Physical CT CI CO
address
(PA) PPN PPO

Address No
Change
Virtual Translation
CI
address
VPN VPO L1 Cache
(VA)
36 12
 Observation
 Bits that determine CI identical in virtual and physical address
 Can index into cache while address translation taking place
 Generally we hit in TLB, so PPN bits (CT bits) available next
 “Virtually indexed, physically tagged”
 Cache carefully sized to make this possible
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22
Virtual Address Space of a Linux Process
Process-specific data
structs (ptables,
Different for
task and mm structs,
each process Kernel
kernel stack)
virtual
Physical memory memory
Identical for
each process Kernel code and data

User stack
%rsp

Memory mapped region

for shared libraries
Process
brk virtual
Runtime heap (malloc) memory
Uninitialized data (.bss)
Initialized data (.data)
0x00400000 Program text (.text)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23
0
Linux Organizes VM as Collection of “Areas”
Process virtual memory
vm_area_struct
task_struct
mm_struct vm_end
mm pgd vm_start
vm_prot
mmap vm_flags
Shared libraries
vm_next

vm_end
 pgd: vm_start
vm_prot
 Page global directory address vm_flags
Data
 Points to L1 page table
 vm_prot: vm_next
 Read/write permissions for Text
this area vm_end
vm_start
 vm_flags vm_prot
 Pages shared with other vm_flags
processes or private to this vm_next 0
process
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24
Linux Page Fault Handling
vm_area_struct Process virtual memory

vm_end
vm_start
vm_prot
vm_flags
shared libraries
vm_next
1
read Segmentation fault:
accessing a non-existing page
vm_end
vm_start 3
vm_prot
data read Normal page fault
vm_flags

vm_next
2 Protection exception:
text
write e.g., violating permission by
vm_end
vm_start writing to a read-only page (Linux
vm_prot reports as Segmentation fault)
vm_flags
vm_next
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25