This is not the current version of the class.

Kernel exercises

Exercises not as directly relevant to this year’s class are marked with ⚠️.

MIDTERM NOTE. Virtual memory questions are not relevant to the 2021 midterm. From Unit 3 material, the 2021 midterm will contain, at most, general questions about process isolation and kernel isolation. The KERN-2A-C questions are worth a look, but most of the rest of these questions concern virtual memory.

KERN-1. Virtual memory

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

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

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.

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

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.

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

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

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.

KERN-2. Virtual memory and kernel programming

The WeensyOS kernel occupies virtual addresses 0 through 0xFFFFF; the process address space starts at PROC_START_ADDR == 0x100000 and goes up to (but not including) MEMSIZE_VIRTUAL == 0x300000.

QUESTION KERN-2A. True or false: On x86-64 Linux, like on WeensyOS, the kernel occupies low virtual addresses.

QUESTION KERN-2B. On WeensyOS, which region of a process’s address space is closest to the kernel’s address space? Choose from code, data, stack, and heap.

QUESTION KERN-2C. On Linux on an x86-64 machine, which region of a process’s address space is closest to the kernel’s address space? Choose from code, data, stack, and heap.

The next problems consider implementations of virtual memory features in a WeensyOS-like operating system. Recall that the WeensyOS sys_page_alloc(addr) system call allocates a new physical page at the given virtual address. Here’s an example kernel implementation of sys_page_alloc, taken from the WeensyOS syscall function:

case SYSCALL_PAGE_ALLOC: {
    uintptr_t addr = current->regs.reg_rdi;

    /* [A] */

    void* pg = kalloc(PAGESIZE);
    if (!pg) { // no free physical pages
        console_printf(CPOS(24, 0), 0x0C00, "Out of physical memory!\n");
        return -1;
    }

    /* [B] */

    // and map it into the user’s address space
    vmiter(current->pagetable, addr).map((uintptr_t) pg, PTE_P | PTE_W | PTE_U);

    /* [C] */

    return 0;
}

(Assume that kalloc and kfree are correctly implemented.)

QUESTION KERN-2D. Thanks to insufficient checking, this implementation allows a WeensyOS process to crash the operating system or even take it over. This kernel is not isolated. What the kernel should do is return −1 when the calling process supplies bad arguments. Write code that, if executed at slot [A], would preserve kernel isolation and handle bad arguments correctly.

QUESTION KERN-2E. This implementation has another problem, which the following process would trigger:

void process_main() {
    heap_top = /* ... first address in heap region ... */;
    while (1) {
        sys_page_alloc(heap_top);
        sys_yield();
    }
}

This process code repeatedly allocates a page at the same address. What should happen is that the kernel should repeatedly deallocate the old page and replace it with a newly-allocated zeroed-out page. But that’s not what will happen given the example implementation.

What will happen instead? And what is the name of this kind of problem?

QUESTION KERN-2F. Write code that would fix the problem, and name the slot in the SYSCALL_PAGE_ALLOC implementation where your code should go. (You may assume that this version of WeensyOS never shares process pages among processes.)

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.

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:

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.

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.

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.

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.

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.

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.

KERN-4. Teensy OS VM System

The folks at Teensy Computers, Inc, need your help with their VM system. The hardware team that developed the VM system abruptly left and the folks remaining aren't quite sure how VM works. I volunteered you to help them.

The Teensy machine has a 16-bit virtual address space with 4 KB pages. The Teensy hardware specifies a single-level page table. Each entry in the page table is 16-bits. Eight of those bits are reserved for the physical page number and 8 of the bits are reserved for flag values. Sadly, the hardware designers did not document what the bits do!

QUESTION KERN-4A. How many pages are in the Teensy virtual address space?

QUESTION KERN-4B. How many bits comprise a physical address?

QUESTION KERN-4C. Is the physical address space larger or smaller than the virtual address space?

QUESTION KERN-4D. Write, in hex, a PAGE_OFFSET_MASK (the value that when anded with an address returns the offset of the address on a page).

QUESTION KERN-4E. Write a C expression that takes a virtual address, in the variable vaddr, and returns the virtual page number.

You are now going to work with the Teensy engineers to figure out what those other bits in the page table entries mean! Fortunately, they have some engineering notes from the hardware team—they need your help in making sense of them. Each letter below has the contents of a note, state what you can conclude from that note about the lower 8 bits of the page table entries.

QUESTION KERN-4F. “Robin, I ran 8 tests using a kernel that did nothing other than loop infinitely -- for each test I set a different bit in all the PTEs of the page table. All of them ended up in the exception handler except for the one where I set bit 4. Any idea what this means?”

QUESTION KERN-4G. “Lynn, I'm writing a memory test that iterates over all of memory making sure that I can read back the same pattern I write into memory. If I don't set bit 7 of the page table entries to 1, I get permission faults. Do you know what might be happening?”

QUESTION KERN-4H. “Pat, I almost have user level processes running! It seems that the user processes take permission faults unless I have both bit 4 and bit 3 set. Do you know why?”

KERN-5. Teensy OS Page Tables

The Teensy engineers are well on their way now, but they do have a few bugs and they need your help debugging the VM system. They hand you the following page table, using x86-64 notation for permissions, and need your help specifying correct behavior for the operations that follow.

Index

Entry contents:

Page number of
physical page

Permissions

0

0x00

PTE_U

1

0x01

PTE_P

2

0x02

PTE_P|PTE_W

3

0x03

PTE_P|PTE_W|PTE_U

4

0xFF

PTE_W|PTE_U

5

0xFE

PTE_U

6

0x80

PTE_W

7

0x92

PTE_P|PTE_W|PTE_U

8

0xAB

PTE_P|PTE_W|PTE_U

9

0x09

PTE_P|PTE_U

10

0xFE

PTE_P|PTE_U

11

0x00

PTE_W

12

0x11

PTE_U

All others

(Invalid)

0

For each problem below, write either the physical address of the given virtual address or identify what fault would be produced. The fault types should be one of:

  1. Missing page (there is no mapping for the requested page)
  2. Privilege violation (user level process trying to access a supervisor page)
  3. Permission violation (attempt to write a read-only page)

QUESTION KERN-5A. The kernel dereferences a null pointer

QUESTION KERN-5B. A user process dereferences a null pointer

QUESTION KERN-5C. The kernel writes to the address 0x8432

QUESTION KERN-5D. A user process writes to the address 0xB123

QUESTION KERN-5E. The kernel reads from the address 0x9876

QUESTION KERN-5F. A user process reads from the address 0x7654

QUESTION KERN-5G. A user process writes to the address 0xABCD

QUESTION KERN-5H. A user process writes to the address 0x2321

KERN-6. Virtual Memory

You may recall that Professor Seltzer loves inventing strange and wonderful virtual memory systems—she’s at it again! The Tom and Ginny (TAG) processor has 16-bit virtual addresses and 256-byte pages. Virtual memory translation is provided via two-level page tables as shown in the figure below.

TAG virtual memory translation

QUESTION KERN-6A. How many entries are in an L1 page table?

QUESTION KERN-6B. How many entries are in an L2 page table?

QUESTION KERN-6C. If each page table entry occupies 2 bytes of memory, how large (in bytes) is a single page table?

QUESTION KERN-6D. What is the maximum number of L1 page table pages that a process can have?

QUESTION KERN-6E. What is the maximum number of L2 page table pages that a process can have?

QUESTION KERN-6F. The figure below shows how the PTEs are organized.

TAG PTE organization

Given the number of bits allocated to the physical page number in the PTE, how much physical memory can the TAG processor support?

QUESTION KERN-6G. Finally, you’ll actually perform virtual address translation in software. We will define a TAG page table entry as follows:

typedef uint16_t tag_pageentry;

Write a function unsigned virtual_to_physical(tag_pageentry* pagetable, unsigned vaddr) that takes as arguments:

and returns a physical address if a valid mapping exists and an invalid physical address if no valid mapping exists. Comment your code to explain each step that you want the function to take. You may assume that the current page table is identity-mapped page table (i.e., each virtual address maps to the physical address with the same numeric value), and that all page table pages are accessible via that current page table.

KERN-7. Cost expressions

In the following questions, you will reason about the abstract costs of various operations, using the following tables of constants.

Table of Basic Costs
S System call overhead (i.e., entering and exiting the kernel)
F Page fault cost (i.e., entering and exiting the kernel)
P Cost of allocating a new physical page
M Cost of installing a new page mapping
B Cost of copying a byte

Table of Sizes
nk Number of memory pages allocated to the kernel
np Number of memory pages allocated to process p
rp Number of read-only memory pages allocated to process p
wp = np − rp Number of writable memory pages allocated to process p
mp Number of memory pages actually modified by process p after its previous fork()

QUESTION KERN-7A. Our tiny operating systems’ processes start out with a single stack page each. A recursive function can cause the stack pointer to move beyond this page, and the program to crash.

This problem can be solved in the process itself. The process can examine its stack pointer before calling a recursive function and call sys_page_alloc to map a new stack page when necessary.

Write an expression for the cost of this sys_page_alloc() system call in terms of the constants above.

QUESTION KERN-7B. Another solution to the stack overflow issue uses the operating system’s page fault handler. When a fault occurs in a process’s stack region, the operating system allocates a new page to cover the corresponding address. Write an expression for the cost of such a fault in terms of the constants above.

QUESTION KERN-7C. Design a revised version of sys_page_alloc that supports batching. Give its signature and describe its behavior.

QUESTION KERN-7D. Write an expression for the cost of a call to your batching allocation API.

In the remaining questions, a process p calls fork(), which creates a child process, c.

Assume that the base cost of performing a fork() system call is Φ. This cost includes the fork() system call overhead (S), the overhead of allocating a new process, the overhead of allocating a new page directory with kernel mappings, and the overhead of copying registers. But it does not include overhead from allocating, copying, or mapping other memory.

QUESTION KERN-7E. Consider the following implementations of fork():

  1. Naive fork: Copy all process memory.
  2. Eager fork: Copy all writable process memory; share read-only process memory, such as code.
  3. Copy-on-write fork: Initially share all memory as read-only. Create writable copies later, on demand, in response to write faults.

Which expression best represents the total cost of the fork() system call in process p, for each of these fork implementations? Only consider the system call itself, not later copy-on-write faults.

(Note: Per-process variables, such as n, are defined for each process. So, for example, np is the number of pages allocated to the parent process p, and nc is the number of pages allocated to the child process c.)

  1. Φ
  2. Φ + np × M
  3. Φ + (np + wp) × M
  4. Φ + np × 212 × (B + F)
  5. Φ + np × (212B + P + M)
  6. Φ + np × (P + M)
  7. Φ + wp × (212B + P + M)
  8. Φ + np × (212B + P + M) − rp × (212B + P)
  9. Φ + np × M + mc × (P + F)
  10. Φ + np × M + mc × (212B + F + P)
  11. Φ + np × M + (mp+mc) × (P + F)
  12. Φ + np × M + (mp+mc) × (212B + F + P)

QUESTION KERN-7F. When would copy-on-write fork be more efficient than eager fork (meaning that the sum of all fork-related overheads, including faults for pages that were copied on write, would be less for copy-on-write fork than eager fork)? Choose the best answer.

  1. When np < nk.
  2. When wp × F < wp × (M + P).
  3. When mc × (F + M + P) < wp × (M + P).
  4. When (mp+mc) × (F + M + P + 212B) < wp × (P + 212B).
  5. When (mp+mc) × (F + P + 212B) < wp × (P + M + 212B).
  6. When mp < mc.
  7. None of the above.

KERN-8. Virtual memory

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

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

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

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

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

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

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: _____________________________

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

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; PX100L is a bad answer.)

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 2X distinct destination physical pages.

KERN-9. Weensy signals

WeensyOS lacks signals. Let’s add them.

⚠️ Signals are covered in the Shell unit.

Here’s sys_kill, a system call that should deliver a signal to a process.

// sys_kill(pid, sig)
//    Send signal `sig` to process `pid`.
inline int sys_kill(pid_t pid, int sig) {
    register uintptr_t rax asm("rax") = SYSCALL_KILL;
    asm volatile ("syscall"
                  : "+a" (rax), "+D" (pid), "+S" (sig)
                  :
                  : "cc", "rcx", "rdx", …, "memory");
    return rax;
}

QUESTION KERN-9A. Implement the WeensyOS kernel syscall case for SYSCALL_KILL. Your implementation should simply change the receiving process’s state to P_BROKEN. Check arguments as necessary to avoid kernel isolation violations; return 0 on success and -1 if the receiving process does not exist or is not running. A process may kill itself.

uintptr_t syscall(...) { ...
case SYSCALL_KILL:
    // your code here

The WeensyOS signal handling mechanism is based on that of Unix. When a signal is delivered to a WeensyOS process:

  1. The kernel saves the receiving process’s registers and switches the process to signal-handling mode.
  2. The kernel causes the receiving process to execute its signal handler.
    • It creates a stack frame for the signal handler by subtracting at least 128 bytes from the process’s stack pointer. This ensures that the signal handler’s local variables (if any) do not overwrite those of the interrupted function.
    • It sets the signal handler’s arguments. A WeensyOS signal handler takes one argument, the signal number.
    • It sets the process’s instruction pointer to the signal handler address and resumes the process.
  3. The signal handler can tell the kernel to resume normal processing by calling the sigreturn system call. This will restore the registers to their saved values and resume the process.

Implement this. Begin from the following system call definitions and changes to the WeensyOS kernel’s struct proc.

inline int sys_kill(pid_t pid, int sig) { ... } // as above

// sys_signal(sighandler)
//    Set the current process’s signal handler to `sighandler`.
inline int sys_signal(void (*sighandler)(int)) {
    register uintptr_t rax asm("rax") = SYSCALL_SIGNAL;
    asm volatile ("syscall"
                  : "+a" (rax), "+D" (sighandler)
                  : ...);
    return rax;
}

// sys_sigreturn()
//    Returns from a signal handler to normal mode. Does nothing if in normal mode already.
inline int sys_sigreturn() {
    register uintptr_t rax asm("rax") = SYSCALL_SIGRETURN;
    asm volatile ("syscall"
                  : "+a" (rax)
                  : ...);
    return rax;
}

struct proc {
    x86_64_pagetable* pagetable;
    pid_t pid;
    regstate regs;
    procstate_t state;

    // Signal support:
    uintptr_t sighandler;         // signal handler (0 means default)
    bool sigmode;                 // true iff in signal-handling mode
    regstate saved_regs;          // saved registers, if in signal-handling mode
};

QUESTION KERN-9B. Implement the WeensyOS kernel syscall case for SYSCALL_SIGNAL.

uintptr_t syscall(...) { ...
case SYSCALL_SIGNAL:
    // your code here (< 5 lines)

QUESTION KERN-9C. Implement the WeensyOS kernel syscall case for SYSCALL_SIGRETURN. If the current process is in signal-handling mode (current->p_sigmode != 0), restore the saved registers and leave signal-handling mode; otherwise simply return 0.

void syscall(...) { ...
case SYSCALL_SIGRETURN:
    // your code here (< 10 lines)

QUESTION KERN-9D. Implement the WeensyOS kernel syscall case for SYSCALL_KILL. If the receiving process’s sighandler is 0, behave as in part A. Otherwise, if the receiving process is in signal-handling mode, return -1 to the calling process rather than delivering the signal. Otherwise, save the receiving process’s registers and cause it to call its signal handler in signal-handling mode, as described above.

uintptr_t syscall(...) { ...
case SYSCALL_KILL:
    // your code here (< 25 lines)

QUESTION KERN-9E. Unix has some signals that cannot be caught or handled, especially SIGKILL (signal 9), which unconditionally exits a process. Which kernel and/or process code would change to support equivalent functionality in WeensyOS? List all that apply.

QUESTION KERN-9F. Is it necessary to verify the signal handler address to avoid kernel-isolation violations? Explain briefly why or why not.

QUESTION KERN-9G. BONUS QUESTION. A WeensyOS signal handler function must end with a call to sys_sigreturn(). Describe how the WeensyOS kernel could set it up so that sys_sigreturn() is called automatically when a signal-handler function returns.

KERN-10. Weensy threads

⚠️ Threads are covered in the Synchronization unit.

Betsy Ross is changing her WeensyOS to support threads. There are many ways to implement threads, but Betsy wants to implement threads using the ptable array. “After all,” she says, “a thread is just like a process, except it shares memory with some other process!”

Betsy has defined a new system call, sys_create_thread, that starts a new thread running a given thread function, with a given argument, and a given stack pointer:

typedef void* (*thread_function)(void*);
pid_t sys_create_thread(thread_function f, void* arg, void* stack_top);

The system call’s return value is the ID of the new thread.

Betsy’s kernel contains the following code for her sys_fork implementation.

// in syscall()
case SYSCALL_FORK:
    return handle_fork(current);
...

uint64_t handle_fork(proc* p) {
    proc* new_p = find_unused_process();
    if (!new_p)
        return -1;

    new_p->pagetable = copy_pagetable(p->pagetable);
    if (!new_p->pagetable)
        return -1;

    new_p->regs = p->regs;
    new_p->regs.reg_rax = 0;
    new_p->state = P_RUNNABLE;
    return 0;
}

And here’s the start of her sys_create_thread implementation.

// in syscall()
case SYSCALL_CREATE_THREAD:
    return handle_create_thread(current);
...

uint64_t handle_create_thread(proc* p) {
    // Whoops! Got a revolution to run, back later
    return -1;
}

QUESTION KERN-10A. Complete her handle_create_thread implementation. Assume for now that the thread function never exits. You may use these helper functions if you need them (you may not):

Recall that system call arguments are passed according to the x86-64 calling convention: first argument in %rdi, second in %rsi, third in %rdx, etc.

QUESTION KERN-10B. Betsy’s friend Prince Dimitri Galitzin thinks Betsy should give processes even more flexibility. He suggests that sys_create_thread take a full set of registers, rather than just a new instruction pointer and a new stack pointer. That way, the creating thread can supply all registers to the new thread, rather than just a single argument.

pid_t sys_create_thread(x86_64_registers* new_registers);

The kernel will simply copy *new_registers into the proc structure for the new thread. Easy!

Which of the following properties of x86_64_registers would allow Dimitri’s plan to violate kernel isolation? List all that apply.

  1. reg_rax contains the thread’s %rax register.
  2. reg_rip contains the thread’s instruction pointer.
  3. reg_cs contains the thread’s privilege level, which is 3 for unprivileged.
  4. reg_intno contains the number of the last interrupt the thread caused.
  5. reg_rflags contains the EFLAGS_IF flag, which indicates that the thread runs with interrupts enabled.
  6. reg_rsp contains the thread’s stack pointer.

Now Betsy wants to handle thread exit. She introduces two new system calls, sys_exit_thread and sys_join_thread:

void sys_exit_thread(void* exit_value);
void* sys_join_thread(pid_t thread);

sys_exit_thread causes the thread to exit with the given exit value; it does not return. sys_join_thread behaves like pthread_join or waitpid. If thread corresponds is a thread of the same process, and thread has exited, sys_join_thread cleans up the thread and returns its exit value; otherwise, sys_join_thread returns (void*) -1.

QUESTION KERN-10C. Is the sys_join_thread specification blocking or polling?

QUESTION KERN-10D. Betsy makes the following changes to WeensyOS internal structures to support thread exit.

  1. She adds a void* exit_value member to struct proc.
  2. She adds a new process state, P_EXITED, that corresponds to exited threads.

Complete the case for SYSCALL_EXIT_THREAD in syscall(). Don’t worry about the case where the last thread in a process calls sys_exit_thread instead of sys_exit.

case SYSCALL_EXIT_THREAD:

QUESTION KERN-10E. Complete the following helper function.

// Test whether `test_pid` is the PID of a thread in the same process as `p`.
// Return 1 if it is; return 0 if `test_pid` is an illegal PID, it corresponds to
// a freed process, or it corresponds to a thread in a different process.
int is_thread_in(pid_t test_pid, proc* p) {

QUESTION KERN-10F. Complete the case for SYSCALL_JOIN_THREAD in syscall(). Remember that a thread may be successfully joined at most once: after it is joined, its PID is made available for reallocation.

case SYSCALL_JOIN_THREAD:

QUESTION KERN-10G. In pthreads, a thread can exit by returning from its thread function; the return value is used as an exit value. So far, that’s not true in Weensy threads: a thread returning from its thread function will execute random code, depending on what random garbage was stored in its initial stack in the return address position. But Betsy thinks she can implement pthread-style behavior entirely at user level, with two changes:

  1. She’ll write a two-instruction function called thread_exit_vector.
  2. Her create_thread library function will write a single 8-byte value to the thread’s new stack before calling sys_create_thread.

Explain how this will work. What instructions will thread_exit_vector contain? What 8-byte value will create_thread write to the thread’s new stack? And where will that value be written relative to sys_create_thread’s stack_top argument?

KERN-11. Virtual memory cache

x86-64 processors maintain a cache of page table entries called the TLB (translation lookaside buffer). This cache maps virtual page addresses to the corresponding page table entries in the current page table. TLB lookup ignores page offset: two virtual addresses with the same L1–L4 page indexes use the same TLB entry.

QUESTION KERN-11A. A typical x86-64 TLB has 64 distinct entries. How many virtual addresses are covered by the entries in a full TLB? (You can use hexadecimal or exponential notation.)

QUESTION KERN-11B. What should happen to the TLB when the processor executes an lcr3 instruction?

QUESTION KERN-11C. Multi-level page table designs can naturally support multiple sizes of physical page. Which of the following is the most sensible set of sizes for x86-64 physical pages (in bytes)? Explain briefly.

  1. 212, 214, 216
  2. 212, 224, 236
  3. 212, 221, 230
  4. 212, 239

QUESTION KERN-11D. In a system with multiple physical page sizes, which factors are reasons to prefer allocating process memory using small pages? List all that apply.

  1. TLB hit rate.
  2. Page table size (number of page table pages).
  3. Page table depth (number of levels).
  4. Memory fragmentation.
  5. None of the above.

KERN-12. Page tables

QUESTION KERN-12A. How big is an x86-64 page?

QUESTION KERN-12B. How many page table entries are there in an x86-64 page?

QUESTION KERN-12C. How many bytes of virtual address space are accessible starting at level-3 page table page in x86-64?

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

Physical address -> Content
0x1f000 -> 0x202007
0x20000 -> 0x1f007

KERN-13. Urgent!!!!!

This problem concerns a new system call, urgent, with the following specification.

int urgent(pid_t p, long v)
If p != 0, then p must be the process ID of a running process. That process is placed into urgent mode with value v. All future system calls by p, except for sys_urgent, will return immediately with return value v, rather than performing as normal. If the process is currently blocked in a system call, then it is unblocked and the system call returns v.
If p == 0, then the current process is taken out of urgent mode.
Returns 0 on success, -1 on failure. Failure occurs if p != 0 and p is not the ID of a running process.

The urgent system call in some ways resembles kill, which causes signals, in that it allows one process to disrupt the normal execution of another. However, urgent only disrupts the operation of system calls—it does not interrupt normal process computation.

QUESTION KERN-13A. Process isolation: list all that apply; explain briefly if unsure.

  1. The urgent system call violates process isolation because any process can disrupt the execution of any other process, without regard to parent–child relationships or user privileges.
  2. The urgent system call violates process isolation because it can allow a process to gain control of the kernel, which runs with process ID 1.
  3. The urgent system call does not violate process isolation because operating system policy defines exactly what process isolation means.
  4. The urgent system call is likely to make it much harder to build robust software.
  5. None of the above.

QUESTION KERN-13B. The timed-wait example from lecture aimed to write a program that exited after a 0.75 second timeout, or its child process exited, whichever came first. Many attempts were subject to a race condition, including the following:

void signal_handler(int signal) {
    (void) signal;
}

int main() {
    int r = set_signal_handler(SIGCHLD, signal_handler);
    pid_t p1 = fork();
    if (p1 == 0) {
        ... do something ...
    }
    r = usleep(750000);  // will be interrupted if SIGCHLD occurs
    (void) r;
}

What best describes the race condition? List all that apply.

  1. The race condition can occur when the child exits before usleep begins.
  2. The race condition can occur when the child exits after usleep completes.
  3. The race condition can occur if set_signal_handler does not install the signal handler before the child runs.
  4. The race condition can occur if the kernel neglects to send the process a SIGCHLD signal when the child exits.
  5. None of the above.

QUESTION KERN-13C. Describe how to modify the timed-wait example code from part B to avoid the race condition using urgent. Either write code or explain briefly. Make sure you include a call to urgent(0, 0) so that the parent process can exit!

QUESTION KERN-13D. Describe how to modify the WeensyOS kernel to support sys_urgent. You will want to refer to your WeensyOS code, and change at least 3 locations marked below. (WeensyOS has no blocking system calls so don’t worry about urgent’s unblocking behavior.)

// Process descriptor type
struct proc {
    x86_64_pagetable* pagetable;        // process's page table
    pid_t pid;                          // process ID
    int state;                          // process state (P_RUNNABLE, P_FREE, etc.)
    regstate regs;                      // process's current registers

    // (1) Your code here
};

extern proc ptable[NPROC];

uintptr_t syscall(regstate* regs) {
    // Copy the saved registers into the `current` process descriptor.
    current->regs = *regs;
    regs = &current->regs;
    console_show_cursor(cursorpos);
    memshow();
    check_keyboard();

    if (regs->reg_rax == SYSCALL_URGENT) {
        // (2) Your code here to handle the `sys_urgent` system call
    }

    // (3) Your code here to check for and handle urgent mode

    // Normal system calls
    switch (regs->reg_rax) { ...