Exercise VM: Virtual Memory

Parts of addresses

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;
}

How to do this in your head? If you have an address in hexadecimal 0xMNOPQRST (where each capital letter represents a hexadecimal digit), then:

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:

PAGEOFFSET(0)?
L2PAGEINDEX(0)?
L1PAGEINDEX(0x9000)?
PAGEOFFSET(1023)?
L1PAGEINDEX(0x10000000)?
L2PAGEINDEX(0x10000000)?
L2PAGEINDEX(0x10000FFF)?
PAGEOFFSET(0x00801000)?
L2PAGEINDEX(0x00801000)?
L1PAGEINDEX(0x00801000)?
PAGEOFFSET(0x00F0089A)?
L2PAGEINDEX(0x00F0089A)?
L1PAGEINDEX(0x00F0089A)?

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

PAGEOFFSET = 0
PAGEOFFSET = 0 and L1PAGEINDEX = 12
L1PAGEINDEX = 8, L2PAGEINDEX = 128, PAGEOFFSET = 256
L1PAGEINDEX = 0, L2PAGEINDEX = 0xC, PAGEOFFSET = 0x7FF

Pages

The x86 page size is 4KB = 2¹² 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.

Virtual address translation

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.

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

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.

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

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 Address)	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.

Q1. Which physical address corresponds to virtual address 0x0?

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.

Q5. Which physical address corresponds to virtual address 0x0?

Q6. Which physical address corresponds to virtual address 0x100?

Q7. Which physical address corresponds to virtual address 0x1050?

Q8. Which physical address corresponds to virtual address 0x2040?

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 Address)	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).

0x00000000
0x00000001
0x00000FFF
0x00001000
0x00C08003
0x00C80003
0x00C00F00
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).

0x00007000
0x00000000
0x0000AFFF
0x00008888
0xA0000000
0x00008001
0x0000A002

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

How many different physical data pages may be addressed using this page table?
How many accessible virtual addresses exist for this page table?

Q14. Assume the current page table has physical address 0x6000.

Give a physical address that is inaccessible from this page table (has no corresponding virtual address).
Write C statements that, if executed under this page table, would make the physical address you named above accessible at some virtual address you choose. (Remember that all addresses used in C programs are virtual.)
Give the virtual address you chose for the last part.