2014/ExerciseVM

Computer Science 61 and E61
Systems Programming and Machine Organization

Exercise VM: Virtual Memory

x86 virtual addresses have three component parts.

• Bits 0 through 11 (the least significant 12 bits) are the page offset. We’ll say PAGEOFFSET for short.
• Bits 12 through 21 (the next most significant 10 bits) are the level 2 page table index. We’ll say L2PAGEINDEX for short.
• Bits 22 through 31 (the most significant 10 bits) are the level 1 page table index. We’ll say L1PAGEINDEX for short.

These parts are calculated in C as follows:

```#define PAGESIZE (1 << 12)

unsigned PAGEOFFSET(uintptr_t va) {
return va & (PAGESIZE - 1);
}

unsigned L2PAGEINDEX(uintptr_t va) {
return (va >> 12) & 0x3FF;
}

unsigned L1PAGEINDEX(uintptr_t va) {
return va >> 22;
}```

• PAGEOFFSET(0xMNOPQRST) == 0xRST. That’s just the lower 3 hex digits.
• L2PAGEINDEX(0xMNOPQRST) == (0xOPQ & 0x3FF). That’s the next 3 hex digits, except that you need to mask off the top two bits, to get a number between 0x000 and 0x3FF.
• L1PAGEINDEX(0xMNOPQRST) == (0xMNO >> 2). That’s the top 3 hex digits shifted right by two. This is not as easy as the other ones. If you’re confused write it in binary.

Part A. What is:

1. PAGEOFFSET(0)?
2. L2PAGEINDEX(0)?
3. L1PAGEINDEX(0x9000)?
4. PAGEOFFSET(1023)?
5. L1PAGEINDEX(0x10000000)?
6. L2PAGEINDEX(0x10000000)?
7. L2PAGEINDEX(0x10000FFF)?
8. PAGEOFFSET(0x00801000)?
9. L2PAGEINDEX(0x00801000)?
10. L1PAGEINDEX(0x00801000)?
11. PAGEOFFSET(0x00F0089A)?
12. L2PAGEINDEX(0x00F0089A)?
13. L1PAGEINDEX(0x00F0089A)?

Part B. For each question, give a virtual address that satisfies the constraints.

1. PAGEOFFSET = 0
2. PAGEOFFSET = 0 and L1PAGEINDEX = 12
3. L1PAGEINDEX = 8, L2PAGEINDEX = 128, PAGEOFFSET = 256
4. L1PAGEINDEX = 0, L2PAGEINDEX = 0xC, PAGEOFFSET = 0x7FF

Pages

The x86 page size is 4KB = 212 bytes = 4096 bytes = 0x1000 bytes.

A page is 4096 bytes of contiguous memory whose first address is a multiple of 4096.

For instance, we might refer to “physical page 0x1000.” This means the physical page of memory comprising addresses 0x1000 through 0x1FFF.

Not every 4096 bytes of contiguous memory is a page. For example, consider 4096 bytes of memory starting at physical address 0x1800. The byte range is 0x1800 through 0x27FF. This overlaps with two physical pages: the portion from 0x1800–0x1FFF is part of physical page 0x1000, and the portion from 0x2000-0x27FF is part of physical page 0x2000.

Any single byte belongs to exactly one page. Two contiguous bytes may belong to 1 or 2 physical pages, it depends how they’re aligned.

x86 virtual address translation uses a two-level page table. This is a two-level radix tree with fanout 1024.

The tree has a single root node, called the level 1 page table, and between 0 and 1024 level-1 nodes, which called level 2 page tables. Each of these nodes occupy a single physical page. (Note that these “levels” are completely different from the levels of processor caches—“level-1 cache,” “level-2 cache.”)

Both level-1 and level-2 and page tables are arrays of 1024 four-byte entries.

Each CPU has a current page table register, which holds the physical address of the currently active level-1 page table. This register is called `%cr3`.

To look up the physical address corresponding to virtual address va, the processor’s memory management unit does the following steps. This version is incomplete because we are ignoring flags.

1. Split va into its components (PAGEOFFSET, L2PAGEINDEX, L1PAGEINDEX).
2. Let pagetable be the contents of the current page table register.
3. Let l1pte = pagetable->entry[L1PAGEINDEX(va)]. That is, look up the entry at index L1PAGEINDEX(va) in pagetable and call it l1pte.
4. Treat l1pte as the physical address of a page table page.
5. Let l2pte = l1pte->entry[L2PAGEINDEX(va)]. That is, look up the entry at index L2PAGEINDEX(va) in l1pte and call it l2pte.
6. Treat l2pte as the physical address of a data page.

In C pseudocode, we might write it this way. Again, this version is incomplete because we are ignoring flags.

```typedef struct x86_pagetable {
x86_pageentry_t entry[1024];
} x86_pagetable;

typedef struct vamapping {
uintptr_t pa;
} vamapping;

vamapping virtual_memory_lookup(x86_pagetable* pagetable, uintptr_t va) {
unsigned l1idx = L1PAGEINDEX(va);
x86_pageentry_t l1pte = pagetable->entry[l1idx];   // physical lookup

unsigned l2idx = L2PAGEINDEX(va);
x86_pageentry_t l2pte = ((x86_pagetable*) l1pte)->entry[l2idx];   // physical lookup

return (vamapping) { pa: l2pte + PAGEOFFSET(va) };
}```

Flags

The lower 12 bits of every entry are used for flags. These flags determine whether pages exist and set access permissions.

The flags are:

`PTE_P` == 1
Present. If set, this virtual page is present in physical memory. If not set, the page doesn’t exist (and the rest of the entry isn’t used).
`PTE_W` == 2
Writable. If set, this virtual page may be written. If not set, any attempt, by the kernel or by a process, to write to this virtual page will cause a page fault.
`PTE_U` == 4
Unprivileged (or User). If set, this virtual page may be accessed by unprivileged user processes. If not set, any attempt by a process to read or write this virtual page will cause a page fault. The kernel can still use the page.

With flags, the lookup procedure is as follows.

1. Split va into its components (PAGEOFFSET, L2PAGEINDEX, L1PAGEINDEX).
2. Let pagetable be the contents of the current page table register.
3. Let l1pte = pagetable->entry[L1PAGEINDEX(va)]. That is, look up the entry at index L1PAGEINDEX(va) in pagetable and call it l1pte.
4. If (l1pte & `PTE_P`) == 0, the address is not present. Induce a page fault exception.
5. If (l1pte & `PTE_W`) == 0 and the access is a write, induce a page fault exception.
6. If (l1pte & `PTE_U`) == 0 and the access is by an unprivileged process, induce a page fault exception.
7. Otherwise, clear the lowest 12 bits of l1pte and treat the result as the physical address of a page table page.
8. Let l2pte = l1pte->entry[L2PAGEINDEX(va)]. That is, look up the entry at index L2PAGEINDEX(va) in l1pte and call it l2pte.
9. If (l2pte & `PTE_P`) == 0, the address is not present. Induce a page fault exception.
10. If (l2pte & `PTE_W`) == 0 and the access is a write, induce a page fault exception.
11. If (l2pte & `PTE_U`) == 0 and the access is by an unprivileged process, induce a page fault exception.
12. Otherwise, clear the lowest 12 bits of l2pte and treat the result as the physical address of a data page.

Again in C pseudocode:

```vamapping virtual_memory_lookup(x86_pagetable* pagetable,
bool iswrite, bool isunprivileged,
uintptr_t va) {
uintptr_t l1pte = pagetable->entry[L1PAGEINDEX(va)];
if (!(l1pte & PTE_P)
|| (iswrite && !(l1pte & PTE_W))
|| (isunprivileged && !(l1pte & PTE_U)))
return (vamapping) { isfault: 1};
l1pte &= ~(PAGESIZE - 1);

uintptr_t l2pte = ((x86_pagetable*) l1pte)->entry[L2PAGEINDEX(va)];
if (!(l2pte & PTE_P)
|| (iswrite && !(l2pte & PTE_W))
|| (isunprivileged && !(l2pte * PTE_U)))
return (vamapping) { isfault: 1 };
l2pte &= ~(PAGESIZE - 1);

return (vamapping) { isfault: 0, pa: l2pte + PAGEOFFSET(va) };
}```

Example

Assume that the contents of physical memory are as follows. The “Contents” are 4-byte integers. The “Index”es treat the page as an array of four-byte integers, so “Physical Address” always equals “Physical Page + 4 × Index.” Contents not given are 0.

Physical
Page
Index (Physical
Contents
`0x1000` 0 `(0x1000)` `0x2007`
`0x2000` 0 `(0x2000)` `0x3007`
`0x3000` 0 `(0x3000)` `1`
1 `(0x3004)` `2`
2 `(0x3008)` `3`

Assume that the current level-1 page table has physical address 0x1000.

A1. The physical address 0x3000. Here PAGEOFFSET = L2PAGEINDEX = L1PAGEINDEX = 0. Index 0 (L1PAGEINDEX) in the level-1 page table holds 0x2007. Mask away the flags and the level-2 page table is at 0x2000. Index 0 (L2PAGEINDEX) in the level-2 page table holds 0x3007. Mask away the flags and the data page is at 0x3000.

Q2. How many different physical pages are accessible through this page table?

A2. Exactly one, the physical page at address 0x3000.

Q3. How many virtual addresses are accessible (a byte load from that address will not cause a page fault)?

A3. 4096: one page’s worth.

Q4. What will happen if the kernel attempts to access virtual address 0x3000?

A4. A page fault. Even the kernel is subject to virtual memory translation.

Now assume the same memory contents, but that the current page directory has physical address 0x2000.

Q9. How many different physical data pages are accessible through this page directory?

Q10. How many virtual addresses are accessible (a byte load from that address will not cause a page fault)?

Exercises

Consider this different memory map. Again, all memory contents not mentioned are 0.

Physical
Page
Index (Physical
Contents
`0x1000` 0 (`0x1000`) `0x7007`
1 (`0x1004`) `0x8007`
`0x2000` 0 (`0x2000`) `0x1007`
3 (`0x200C`) `0x3007`
`0x3000` 128 (`0x3200`) `0xA007`
`0x6000` 0 (`0x6000`) `0x2007`
1 (`0x6004`) `0x8007`
`0x7000` 0 (`0x7000`) `0x9007`
`0x8000` 0 (`0x8000`) `0x2007`
1 (`0x8004`) `0x2007`
2 (`0x8008`) `0x2007`
3 (`0x800C`) `0x2007`

Q11. Assume the current page table has physical address 0x2000. (That phrasing means the current level-1 page table has physical address 0x2000.) For each virtual address, give the corresponding physical address (or FAULT if accessing the address would cause a fault).

1. 0x00000000
2. 0x00000001
3. 0x00000FFF
4. 0x00001000
5. 0x00C08003
6. 0x00C80003
7. 0x00C00F00
8. 0x00001F00

Q12. Assume the current page table has physical address 0x2000. For each physical address, give all virtual addresses that map to that physical address (or NONE if no virtual address maps to that physical address).

1. 0x00007000
2. 0x00000000
3. 0x0000AFFF
4. 0x00008888
5. 0xA0000000
6. 0x00008001
7. 0x0000A002

Q13. Assume the current page table has physical address 0x1000.