Section 5

In today’s section, we'll build familiarity with virtual memory and pagetables through a selection of our kernel exercises. Also take the opportunity to ask questions about the problem set and class material.

All exercises assume a 64-bit x86-64 architecture unless otherwise stated.

KERN-8. More virtual memory

QUESTION KERN-8A. What kind of address is stored in x86-64 register %cr3, virtual or physical?

Physical. Since %cr3 is used by the processor as the base of all virtual-to-physical address translation, it must be a physical address.

QUESTION KERN-8B. What kind of address is stored in x86-64 register %rip, virtual or physical?

Virtual. All addresses interpreted by the CPU are virtual except %cr3.

QUESTION KERN-8C. What kind of address is stored in an x86-64 page table entry, virtual or physical?

Physical, for the same reason as in 8A: addresses used to perform virtual-to-physical translations must be physical.

QUESTION KERN-8D. What is the x86-64 word size in bits?

64. Registers are 64 bits wide.

KERN-14. A sample page table

QUESTION KERN-14A. Describe contents of x86-64 physical memory that would ensure virtual addresses 0x10'0ff3 through 0x10'11f2 map to a contiguous range of 512 physical addresses 0x9'9999'9ff3 through 0x9'9999'a1f2. We’ve given you the contents of 2 words of physical memory; you should list more. Assume and/or recall:

• The %cr3 register holds the value 0x2'0000.
• You may change any part of memory.
• (PTE_P | PTE_U | PTE_W) == 0x7.

Physical address	⟶	Content
0x1'f000	⟶	0x20'2007
0x2'0000	⟶	0x1'f007

Hints

This problem asks you to describe the contents of physical memory so that certain virtual addresses map to certain physical addresses. A page table is the data structure that describes those mappings, so you will need to specify the addresses and contents of some entries in the L4 to L1 page tables. Below are some representations of page table pages, where each row contains the address of a page table entry and it's content in the format address : content. You will not need to fill in every entry in order to solve the problem. (Most will be left blank). Start with the given information, and then figure out what else you need in order to complete the mappings. If needed, you can make up addresses.

An L4 page table page		An L3 page table page		An L2 page table page		An L1 page table page
: : ⋮ : : ⋮ : :		: : ⋮ : : ⋮ : :		: : ⋮ : : ⋮ : :		: : ⋮ : : ⋮ : :

You might find it useful to decode page table entries (PTEs) using this chart.

PTE	63 (NX)	62-48	47-12 (Physical address)	11-0 (Permissions)

You might find it useful to decode virtual addresses using this chart.

Virtual address	63-48	47-39 (L4 index)	38-30 (L3 index)	29-21 (L2 index)	20-12 (L1 index)	11-0 (Offset)

For some 0xWXYZ, you need:

0x20'2000 ⟶ 0xWXY'Z007
0xWXY'Z800 ⟶ 0x9'9999'9007
0xWXY'Z808 ⟶ 0x9'9999'A007

Why? Well, assume 0xWXYZ = 0x1000.

• The virtual addresses 0x10'0ff3 and 0x10'11f3 divide into the following offsets and indexes.
  • 0x10'0ff3: offset (bits 0–11) 0xff3, level 1 index (bits 12–20) 0x100, level 2–4 indexes all 0.
  • 0x10'11f2: offset (bits 0–11) 0x1f2, level 1 index (bits 12-20) 0x101, level 2–4 indexes all 0.
• Since the level 2–4 indexes are all 0 for all addresses in the range, the processor’s virtual memory system will access entry #0 in the level 4, 3, and 2 page table pages in sequence, stopping if it finds an entry without the present flag (PTE_P).
  • Entry #0 in the level-4 page table page is located at pa 0x2'0000. That memory holds 0x1'f007. The flags indicate the level-3 page table is present, so the system proceeds to the level-3 page table page at 0x1'f000.
  • Entry #0 in the level-3 page table page is located at pa 0x1'f000. That memory holds 0x20'2007, and the system proceeds to the level-2 page table page at 0x20'2000.
  • Entry #0 in the level-2 page table page is located at pa 0x20'2000, which is unspecified. To solve the problem, that entry must contain a valid physical address for a level-1 page table page, and flags indicating the address is present. So we store 0x100'0007 in address 0x20'2000, indicating a level-1 page table page at 0x100'0000.
• The first addresses in the range will access entry #0x100 in the level 1 page table page, and the last addresses in the range will access entry #0x101. We therefore must store references to pages 0x9'9999'9000 and 0x9'9999'A000 in the memory words storing those entries, which are 0x100'0800 (= 0x100'0000 + 8 * 0x100) and 0x100'0808.