Week 8.b. CS 5600 10/29 2021 On the board ------------ 1. Last time 2. multilevel page table 3. x86-64: addresses - virtual - physical 4. x86-64: page table structures --------------------------------------------------------------------------- Admin: - Lab1 -- two problems -- a problem: header file (a lesson for us!) -- another problem (bug): return a stack variable? --undefined behavior --dude, we emphasized this in class, in handout, and in homework! - HW5 and Lab3 on the way - midterm -- highest: 98 (out of 100) -- where is the 2pts? doesn't follow Mike D's rules in the coding! -- Why so many student use "sleep"? --the description has "sleep"? --intended; you haven't internalize the material --------- 1. Last time Virtual Memory +--> Paging +--> multilevel page table +--> x86-64 page table Virtual Memory: VA --> PA page table conceptually implements a map from VPN --> PPN NOTE: VPN and PPN need not (and do not, in our case study) have the same number of bits review: top bits index into page table. contents at that index are the PPN. bottom bits are the offset. not changed by the mapping physical address = PPN + offset 2. multilevel page table --idea: represent the page table as a tree ... root node has pointers to other nodes children point to pages Then, we map addresses by using the root for the uppermost address bits, the next level for the next address bits, etc. --the tree is sparse; example: Say we want to map 2MB of physical memory at virtual memory 0,...,2^{21}-1 48 bits: 9 9 9 9 (VPN) | 12 (offset) bottom one, points to physical pages. NOTICE: enormous address space, but we've used very few physical resources -- just 512 + 4 physical pages (why? because page table also consumes memory) --tradeoffs --between large and small page sizes: --large page sizes means wasting actual memory --small page sizes means lots of page table entries (which may or may not get consumed) --between many levels of mapping and few: --more levels of mapping means less space spent on page structures when address space is sparse (which they nearly always are) but more costly for hardware to walk the page tables --fewer levels of mapping is the other way around: need to allocate larger page tables (which cost more space), but the hardware has fewer levels of mapping --alternative --new address translation data structure? (instead of page table) Dimitrios Skarlatos, Apostolos Kokolis, Tianyin Xu, and Josep Torrellas "Elastic Cuckoo Page Tables: Rethinking Virtual Memory Translation for Parallelism" (ASPLOS'20) 3. x86-64: addresses x86 architecture is 64-bits. registers and addresses are 64-bits wide VIRTUAL ADDRESSES on currently-available x86-64 machines, only 48 bits "matter". (conclusion: not all 64-bit patterns correspond to meaningful virtual addresses) Bit patterns that are valid addresses are called _canonical addresses_. Canonical address has all 0s or all 1s in the upper 16 bits (bits 63 through 48). Has to match whatever bit 47 is. [see 3.3.7.1 in the Intel software developer's manual] Result: address space is 2^{48} = 256 TB [ Another way to look at it: The x86-64 architecture divides canonical addresses into two groups, low and high. Low canonical addresses range from 0x0000'0000'0000'0000 to 0x0000'7FFF'FFFF'FFFF. High canonical addresses range from 0xFFFF'8000'0000'0000 to 0xFFFF'FFFF'FFFF'FFFF. Considered as signed 64-bit numbers, all canonical addresses range between -2^47 and 2^47-1. ] [Intel 5-level paging: --extend virtual addresses from 48 bits to 57 bits --increase the addressable memory from 256 TB to 128 PB --implemented in the Ice Lake processors, and Linux kernel 4.14 ] PHYSICAL ADDRESSES 52 bits Question: why 52? see handout week8.b panel 3, 4 [answer: 40bit (in PTE) + 12bit (page)] Means a single machine can address up to 4 PB of physical memory. of course, if the machine only has 16 GB (say), then physical addresses will (roughly speaking) only have 34 bits that matter, and thus the top 18 (=52-34) bits of physical addresses will generally be zero [NOTE: this is a simplification, owing to the "physical memory map"; however, we will not encounter that too much in this class.] MAPPING have to map 48-bit number (virtual address) to 52-bit number (physical address), at the granularity of ranges of 2^{12} 4. x86-64: page table structures [walk through the handout] %cr3 is the address of the top-level directory (L1 page table) Question: is that address a physical address or virtual address? [answer: it is a physical address. hardware needs to be able to follow the page table structure.] bunch of bits includes dirty (set by hardware) acccessed (set by hardware) present (set by OS) cache disabled (set by OS) write through (set by OS) what will happen if the present bit is 0 but a program accesses the memory? [answer: page fault; we will study it later.] what do the U/S and R/W bits do? --are these for the kernel, the hardware, what? --who is setting them? what is the point? (OS is setting them to indicate protection; hardware is enforcing them) -- what if the permission is violated? [answer: again, page fault] An example: What if OS wants to map a process's virtual address 0x0202000 to physical address 0x3000 and make it accessible to user-level but read-only? what do the page structures look like? solution: take off the bottom 12 bits of offset vpn = 0x0202. write it out in bits: 0....0 000000001 000000010 18 0 bits L1 (0th entry) --> L2 (0th entry) --> L3 ........... ........... ........... ........... [entry 1] ........... PGTABLE <40 bits> |0x00'0000'0003 | U=1,W=0,P=1| [entry 2] | | | [entry 1] | | | [entry 0] ______________________________ --Question: how much memory can one L1 page entry address? --answer: each entry in the L1 page table corresponds to 512GB of virtual address space ("corresponds to" means "selects the next-level page tables that actually govern the mapping"). for others: --each entry in the L2 page table corresponds to 1 GB of virtual address space --each entry in the L3 page table corresponds to 2 MB of virtual address space --each entry in the L4 page table corresponds to 1 page (4 KB) of virtual address space --Question: so how much virtual memory is each L4 page *table* responsible for translating? 4KB? 2MB? 1GB? [answer: 2MB] --each page table itself consumes 4KB of physical memory, i.e., each one of these fits on a page [see Intel reference manual for more. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3a https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.pdf ]