CS530: Graduate Operating Systems (Spring 2006)
IA32/Linux Virtual Memory Architecture

IA32 VM Architecture (1)

Basic execution environment
General-purpose registers EAX AH AL EBX ECX EDX EBP ESI EDI ESP BH CH DH BP SI DI SP System Segment Registers TR seg. selector LDTR seg. selector BL CL DL Segment registers CS DS SS ES FS GS seg. selector seg. selector seg. selector seg. selector seg. selector seg. selector Control registers 31 CR0 CR1 CR2 CR3 CR4 MXCSR 0
System Table Registers 31 EIP EFLAGS 0 GDTR IDTR linear base address table limit linear base address table limit
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr)

IA32 VM Architecture (2)

Logical address (far pointer)

Users view, segmented

Segment selector (16bits) Segment selector (16bits) Offset (32bits) Offset (32bits)

Linear address

32-bit, flat

Physical address

32-bit, flat Pentium Pro and later processors support an extension of the physical address space to 236 bytes. Invoked with the physical address extension (PAE) flag located in CR4 register.
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 3

IA32 VM Architecture (3)

Segmentation (1)
Logical to linear address
Locate the segment descriptor for the segment in the GDT or LDT using the segment selector. Examine the segment descriptor to check the access rights and the offset is within the limits. Adds the base address of the segment from the segment descriptor to the offset to form a linear address.

Segmentation (2)

Segment selector

Segment registers

Segmentation (3)
Segment descriptor tables
Each system must have one GDT (Global Descriptor Table), which may be used for all programs and tasks. Optionally, one or more LDTs (Local Descriptor Tables) can be defined. GDT is not a segment, but a data structure in the linear address space pointed to by the GDTR register. LDT is located in a system segment of the LDT type. GDT must contain a segment descriptor for the LDT segment. The first descriptor in GDT is not used. The LDTR register caches the segment descriptor of the current LDT segment.

Segmentation (4)

Global and local descriptor tables

Segmentation (5)

Segment descriptor

Paging (1)

Linear to physical address
The physical address of the current page directory is stored in the CR3 register (a.k.a. page directory base register or PDBR).

Paging (2)

Page tables and directories

Page directory

An array of 32-bit page-directory entries (PDEs) contained in a 4KB page (1024 PDEs/page).

Page table

An array of 32-bit page-table entries (PTEs) contained in a 4KB page (1024 PTEs/page). Page tables are not used for 2MB or 4MB pages.
Supports page sizes of 4KB, 2MB, and 4MB.
Page-directory-pointer table
An array of four 64-bit entries pointing to a page directory. Only used when the physical address extension is enabled.
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 11

Paging (3)

Linear to physical address (PAE enabled)

Paging (4)

Page directory entry (PDE)

Paging (5)

Page table entry (PTE)

Paging (6)

The P6 family and Pentium processors have separate TLBs for the data and instruction. (DTLB & ITLB) All TLBs are automatically invalidated if the PDBR register is loaded.
by explicit MOV instruction implicitly by executing a task switch
A specific page-table entry in the TLB can be invalidated using INVLPG instruction. The page global enable (PGE) flag in CR4 and the global (G) flag of a PDE or PTE can be used to prevent frequently used pages from being automatically invalidated.
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 15

IA32 VM References

For more information, see
IA-32 Intel Architecture Software Developers Manual
Volume 1: Basic Architecture Volume 2: Instruction Set Reference Volume 3: System Programming Guide
Available at Intels web site
http://www.intel.com/design/pentium4/manuals/

EM64T (IA32e)

Intel Extended Memory 64 Technology
An enhancement to Intels IA32 architecture (originally from AMD64) IA32e 64-bit mode
Full support for 64-bit integers Larger virtual/physical address space
Currently 248 virtual address space, up to 264 Currently 240 physical address space, up to 252
64-bit wide GPRs and instruction pointers Additional registers (GPRs, XMM registers) Extended and new instructions Removal of older features (e.g., segmentation)

IA32e compatibility mode

32-bit applications under 64-bit operating system No recompilation is required.
Legacy mode for 16-bit or 32-bit OS
http://www.intel.com/technology/64bitextensions/
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 17
Linux VM Architecture (1)

Virtual memory

0x00000000 Kernel code Kernel data
Page tables Freelists, etc.

PAGE_OFFSET = 0xC0000000

Physical memory

0x00000000

Available Page Frames

0x3FFFFFFF

0xFFFFFFFF
Linux VM Architecture (2)
Segmentation: Minimal approach
For better portability across machines
NULL 0x00 NULL (not used) 0x08 (not used) 0x10 Kernel text from 0 (4GB) Kernel text from 0 (4GB) 0x18 Kernel data from 0 (4GB) Kernel data from 0 (4GB) 0x20 User text from 0 (4GB) User text from 0 (4GB) 0x28 User data from 0 (4GB) User data from 0 (4GB) (not used) (not used) (not used) (not used) Used for APM Used for APM (4 entries) (4 entries) Used for PNPBIOS Used for PNPBIOS (8 entries) (8 entries) 0xa0

Segment selectors

__KERNEL_CS __KERNEL_CS __KERNEL_DS __KERNEL_DS __USER_CS __USER_CS __USER_DS __USER_DS
0x10 0x10 0x18 0x18 0x23 0x23 0x2b 0x2b
4 entries per CPU 4 entries per CPU For TSSs & LDTs For TSSs & LDTs
Linux VM Architecture (3)
Paging: Three-level address translation
In i386, the size of Page Middle Directory (PMD) is 1, if the physical address extension (PAE) flag is disabled.

pgd pgd

Page Directory Base

pmd pmd

pte pte

offset offset

Page Directory

Page Middle Directory

Page Table
Linux VM Architecture (4)
Virtual memory areas (VMA)
Nonoverlapping regions, each region representing a continuous, page-aligned subset of the virtual address space. Described by a single vm_area_struct VMAs are linked into a balanced binary tree to allow fast lookup of the region corresponding to any virtual address.
VMAs form a red-black tree.
Linux VM Architecture (5)

task_struct

Virtual address space mm_struct
map_count map_count pgd pgd

vm_area_struct

vm_start vm_start vm_end vm_end vm_mm vm_mm vm_rb vm_rb

VM Area 1

mmap mmap mm_rb mm_rb
vm_ops vm_ops vm_next vm_next
vm_start vm_start vm_end vm_end

VM Area 2

PFN page directory
vm_mm vm_mm vm_rb vm_rb vm_ops vm_ops vm_next vm_next
Linux VM Architecture (6)

VMA example

permission offset device i-node

mapped file

Linux Memory Management (1)

Page descriptors

struct page
Flags, reference count, mapped or anonymous, etc.
For each physical page frame (32bytes)

Memory zones

ZONE_DMA: ZONE_NORMAL: ZONE_HIGHMEM: struct zone below 16MB 16MB ~ 896MB above 896MB
Linux Memory Management (2)
Zoned page frame allocator
alloc_pages(), __get_free_pages() Allocate 2order contiguous physical pages From buddy system

Slab allocator

General purpose objects
13 geometrically distributed lists of free memory areas 32 bytes ~ 131,072 bytes kmalloc()

Specific slab objects

kmem_cache_alloc()
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 25
Linux Memory Management (3)
Noncontiguous memory area management
vmalloc() Allocate a memory area in high memory. Page tables are dynamically changed. Virtually contiguous, but physically noncontiguous
Linux Page Replacement (1)

Target pages

Swappable: backed by swap areas
Anonymous pages in user mode address space
Syncable: backed by file systems
Mapped pages in user mode address space Pages included in the page cache Block device buffer pages Pages of some disk caches (inode cache, etc.) Reserved pages (PG_reserved) Temporarily locked pages (PG_locked) Memory locked pages (VM_LOCKED) Pages dynamically allocated by the kernel

Unreclaimable pages

Linux Page Replacement (2)

Two LRU lists

inactive_list

Pages not known to be very important. A dirty page can stay a few passes in the inactive_list while getting written to disk by the file system. New pages are added to the head of the inactive_list.

active_list

Pages known to be referenced frequently. Defines the working set.
When low on memory, we first refill some page from the active_list to the inactive_list head, and then we start freeing pages from the tail of the inactive_list. The detected working set is moved in the active_list.
CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 28
Linux Page Replacement (3)
Moving pages across the LRU lists
Linux Page Replacement (4)
shrink_cache(): Not freeable INACTIVE LIST

inactive_list.next

head head mark_page_accessed(): Referenced

tail tail

inactive_list.prev
lru_cache_add(): New page
refill_inactive_zone(): Not referenced ACTIVE LIST

shrink_cache(): Evicted

active_list.next

active_list.prev

head head
refill_inactive_zone(): Referenced CS530 (Spring 2006) -- Jin-Soo Kim (jinsoo@cs.kaist.ac.kr) 30

Discussion

IA32/Linux vs. VAX/VMS VM management
Whats similar? Whats different?