Section 7: Kernel exercises

In today’s section, we’ll walk through a selection of our kernel exercises, which are problems taken from prior exams. 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.

The main subjects of these exercises are:

• KERN-1: Virtual memory.
• KERN-3: Kernel programming.
• KERN-8: More virtual memory.
• KERN-14: A sample page table.

KERN-1. Virtual memory

QUESTION KERN-1A. What is the x86-64 page size? Circle all that apply.

1. 4096 bytes
2. 64 cache lines
3. 256 words
4. 0x1000 bytes
5. 2¹⁶ bits
6. None of the above

#1, #2, #4. The most common x86-64 cache line size is 64 = 2⁶ bytes, and 2⁶×2⁶ = 2¹², but there may have been some x86-64 processors with 128-byte cache lines. The word size is 8; 256×8 = 2048, not 4096. There are 8 bits per byte; 2¹⁶/8 = 2¹³, not 2¹².

The following questions concern the sizes of page tables. Answer the questions in units of pages. For instance, the page tables in WeensyOS each contained one level-4 page table page (the highest level, corresponding to address bits 39-47); one level-3 page table page; one level-2 page table page; and two level-1 page table pages, for a total size of 5 pages per page table.

QUESTION KERN-1B. What is the maximum size (in pages) of an x86-64 page table (page tables only, not destination pages)? You may write an expression rather than a number.

                      1    level-4 page table page
+                   512    level-3 page table pages
+             512 * 512    level-2 page table pages
+       512 * 512 * 512    level-1 page table pages
-----------------------
  2^27 + 2^18 + 2^9 + 1
= 0x8040201 = 134480385 page table pages

QUESTION KERN-1C. What is the minimum size (in pages) of an x86-64 page table that would allow a process to access 2²¹ distinct physical addresses?

4 is a good answer—x86-64 page tables have four levels—but the best answer is one.

Whaaat?! Consider a level-4 page table whose first entry refers to the level-4 page table page itself, and the other entries referred to different pages. Like this:

Physical address	Index	Contents
0x1000	0	0x1007
0x1008	1	0x2007
0x1010	2	0x3007
0x1018	3	0x4007
…	…	…
0x1ff8	511	0x200007

With this page table in force, the 2²¹ virtual addresses 0x0 through 0x1FFFFF access the 2²¹ distinct physical addresses 0x1000 through 0x200FFF.

The 64-bit x86-64 architecture is an extension of the 32-bit x86 architecture, which used 32-bit virtual addresses and 32-bit physical addresses. But before 64 bits came along, Intel extended 32-bit x86 in a more limited way called Physical Address Extension (PAE). Here’s how they differ.

• PAE allows 32-bit machines to access up to 2⁵² bytes of physical memory (which is about 4000000 GB). That is, virtual addresses are 32 bits, and physical addresses are 52 bits.
• The x86-64 architecture evolves the x86 architecture to a 64-bit word size. x86-64 pointers are 64 bits wide instead of 32. However, only 48 of those bits are meaningful: the upper 16 bits of each virtual address are ignored. Thus, virtual addresses are 48 bits. As with PAE, physical addresses are 52 bits.

QUESTION KERN-1D. Which of these two machines would support a higher number of concurrent processes without performance problems?

1. x86-32 with PAE with 100 GB of physical memory.
2. x86-64 with 20 GB of physical memory.

#1 x86-32 with PAE. Each concurrent process occupies some space in physical memory, and #1 has more physical memory.

(Real operating systems swap, so either machine could support more processes than fit in virtual memory, but this would cause thrashing. #1 supports more processes before it starts thrashing.)

QUESTION KERN-1E. Which of these two machines would support a higher maximum number of threads per process?

1. x86-32 with PAE with 100 GB of physical memory.
2. x86-64 with 20 GB of physical memory.

#2 x86-64. Each thread in a process needs some address space for its stack, and an x86-64 process address space is much bigger than an x86-32’s.

KERN-3. Kernel programming

WeensyOS processes are quite isolated: the only way they can communicate is by using the console. Let’s design some system calls that will allow processes to explicitly share pages of memory. Then the processes can communicate by writing and reading the shared memory region. Here are two new WeensyOS system calls that allow minimal page sharing; they return 0 on success and –1 on error.

• int share(pid_t p, void* addr)
  Allow process p to access the page at address addr.
• int attach(pid_t p, void* remote_addr, void* local_addr)
  Access the page in process p’s address space at address remote_addr. That physical page is added to the calling process’s address space at address local_addr, replacing any page that was previously mapped there. It is an error if p has not shared the page at remote_addr with the calling process.

Here’s an initial implementation of these system calls, written as clauses in the WeensyOS kernel’s syscall function.

case SYSCALL_SHARE: {
    pid_t p = current->regs.reg_rdi;
    uintptr_t addr = current->regs.reg_rsi;

    /* [A] */

    int shindex = current->nshared;
    if (shindex >= MAX_NSHARED) {
        return -1;
    }

    /* [B] */

    ++current->nshared;
    current->shared[shindex].sh_addr = addr;
    current->shared[shindex].sh_partner = p;
    return 0;
}

case SYSCALL_ATTACH: {
    pid_t p = current->regs.reg_rdi;
    uintptr_t remote_addr = current->regs.reg_rsi;
    uintptr_t local_addr = current->regs.reg_rdx;

    /* [C] */

    int shindex = -1;
    for (int i = 0; i < processes[p].nshared; ++i) {
        if (processes[p].shared[i].sh_addr == remote_addr
            && processes[p].shared[i].sh_partner == current->p_pid) {
            shindex = i;
        }
    }
    if (shindex == -1) {
        return -1;
    }

    /* [D] */

    vmiter it(processes[p].pagetable, remote_addr);

    /* [E] */

    vmiter(current->pagetable, local_addr).map(it.pa(), PTE_P | PTE_W | PTE_U);

    /* [F] */

    return 0;
}

Some notes:

• The implementation stores sharing records in an array. A process may call share successfully at most MAX_NSHARED times. After that, its future share calls will return an error.
• processes[p].nshared is initialized to 0 for all processes.
• Assume that WeensyOS has been implemented as in Problem Set 3 up through step 7 (shared read-only memory).

QUESTION KERN-3A. True or false: Given this implementation, a single WeensyOS process can cause the kernel to crash simply by calling share one or more times (with no process ever calling attach). If true, give an example of a call or calls that would likely crash the kernel.

False

QUESTION KERN-3B. True or false: Given this implementation, a single WeensyOS process can cause the kernel to crash simply by calling attach one or more times (with no process ever calling share). If true, give an example of a call or calls that would likely crash the kernel.

True. If the user supplies an out-of-range process ID argument, the kernel will try to read out of bounds of the processes array. Example call: attach(0x1000000, 0, 0).

QUESTION KERN-3C. True or false: Given this implementation, WeensyOS processes 2 and 3 could work together to obtain write access to the kernel code located at address KERNEL_START_ADDR. If true, give an example of calls that would obtain this access.

True, since the attach and share code don’t check whether the user process is allowed to access its memory. An example:

#2: share(3, KERNEL_START_ADDR)
#3: attach(2, KERNEL_START_ADDR, 0x110000)

QUESTION KERN-3D. True or false: Given this implementation, WeensyOS processes 2 and 3 could work together to obtain write access to any memory, without crashing or modifying kernel code or data. If true, give an example of calls that would obtain access to a page mapped at address 0x110000 in process 5.

The best answer here is false. Processes are able to gain access to any page mapped in one of their page tables. But it’s not clear whether 5’s 0x110000 is mapped in either of the current process’s page tables. Now, 2 and 3 could first read the processes array (via share/attach) to find the physical address of 5’s page table; then, if 2 and 3 are in luck and the page table itself is mapped in their page table, they could read that page table to find the physical address of 0x110000; and then, if 2 and 3 are in luck again, map that page using the VA accessible in one of their page tables (which would differ from 0x110000). But that might not work.

QUESTION KERN-3E. True or false: Given this implementation, WeensyOS child processes 2 and 3 could work together to modify the code run by a their shared parent, process 1, without crashing or modifying kernel code or data. If true, give an example of calls that would obtain write access to process 1’s code, which is mapped at address PROC_START_ADDR.

True; since process code is shared after step 7, the children can map their own code read/write, and this is the same code as the parent’s.

#2: share(3, PROC_START_ADDR)
#3: attach(2, PROC_START_ADDR, PROC_START_ADDR)

QUESTION KERN-3F. Every “true” answer to the preceding questions is a bug in WeensyOS’s process isolation. Fix these bugs. Write code snippets that address these problems, and say where they go in the WeensyOS code (for instance, you could refer to bracketed letters to place your snippets); or for partial credit describe what your code should do.

Here’s one possibility.

Prevent share from sharing an invalid address in [A]:

if ((addr & 0xFFF) || addr < PROC_START_ADDR) {
    return -1;
}

NB don’t need to check addr < MEMSIZE_VIRTUAL as long as we check the permissions from vmiter below (but that doesn’t hurt).

Prevent attach from accessing an invalid process or mapping at an invalid address in [B]:

if (p >= NPROC
    || (local_addr & 0xFFF)
    || local_addr < PROC_START_ADDR
    || local_addr >= MEMSIZE_VIRTUAL) {
    return -1;
}

We do need to check MEMSIZE_VIRTUAL here.

Check the mapping at remote_addr before installing it in [E]:

if (!it.user()) {
    return -1;
}

Also, in the ….map call, use it.perm() instead of PTE_P|PTE_W|PTE_U.

For greatest justice we would also fix a potential memory leak caused by attaching over an address that already had a page, but this isn’t necessary.

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.

Many paged-virtual-memory architectures can be characterized in terms of the PLX constants:

• P = the length of the page offset, in bits.
• L = the number of different page indexes (equivalently, the number of page table levels).
• X = the length of each page index, in bits.

QUESTION KERN-8E. What are the numeric values for P, L, and X for x86-64?

P=12, L=4, X=9.

Assume for the remaining parts that, as in x86-64, each page table page fits within a single page, and each page table entry holds an address and some flags, including a Present flag.

QUESTION KERN-8F. Write a PLX formula for the number of bytes per page, using both mathematical and C notation.

Mathematical notation: _____________________

C notation: _____________________________

2^P, 1 << P

QUESTION KERN-8G. Write a PLX formula for the number of meaningful bits in a virtual address.

P + L*X

QUESTION KERN-8H. Write a PLX formula that is an upper bound on the number of bits in a physical address. (Your upper bound should be relatively tight; P^X100L is a bad answer.)

There are several good answers. The best answer uses the fact that a physical address fits inside a page table entry, so the number of bits in a physical address is limited by the number of bits in an entry. So what’s an entry’s size? A page table contains 2^X entries, and a page table fits in 2^P bytes. That leaves the number of bits as:

8 * sizeof(entry) = 8 * 2^P/2^X = 8 * 2^P–X

Another reasonable answer assumes that virtual addresses aren’t likely to be smaller than physical addresses, giving the answer P + L*X. (On some machines, physical addresses have been larger than virtual addresses—see Question KERN-1D—but as a general rule, virtual addresses are bigger.)

QUESTION KERN-8I. Write a PLX formula for the minimum number of pages it would take to store a page table that allows access to 2^X distinct destination physical pages.

L (for a well-formed page table with distinct pages for each level), or 1 (for a “trick” page table that reuses the top-level page for all subsequent levels; see question KERN-1C).

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 0x20000.
• You may change any part of memory.
• (PTE_P | PTE_U | PTE_W) == 0x7.

For some 0xWXYZ, you need:

0x202000 ⟶ 0xWXYZ007
0xWXYZ800 ⟶ 0x9'9999'9007
0xWXYZ808 ⟶ 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 0x20000. That memory holds 0x1f007. The flags indicate the level-3 page table is present, so the system proceeds to the level-3 page table page at 0x1f000.
  • Entry #0 in the level-3 page table page is located at pa 0x1f000. 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 0x202000, 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.