Project 2

Updates

• 8 October: In step 6 of Setup_Frame, the changes are made in the original interrupt state, not the copy.
• 8 October: WaitNoPID reaps only the children of the process that calls it.

Overview

Project 2 requires you to implement signals and signal handlers. A process can send a signal to another process. The process receiving the signal will, at some point, stop what it is doing, execute a signal-handler function, and then resume what it was doing.

Quick Links

• Download Project Source: in your "network" directory, svn update (or to download a fresh copy of GeekOS, svn co https://svn.cs.umd.edu/repos/geekos/network/)
• Set or verify /geekos/projects.h variables to true as needed.
• Set or verify .submit variables as needed, if using make submit.
• Project Requirements, below
• Submission: as in project 1

Signals

A signal is an inter-process communication mechanism that allows one process to invoke a signal-handler function in another process. There are several signals that one process can send to another, each identified by a number. Each process maintains a table of signal handlers (as function pointers), one for each signal the process can handle. The signal number is used as an index into the table of signal handlers in the target process.

In this project, you will implement five system calls. The two most visible are the "signal" system call, which manipulates the table of signal handlers, and the "kill" system call, which one process uses to send a signal to another. A process calls "signal" to indicate what handler function should run when it receives a signal. In Project 1, you wrote a version of the "kill" system call that removed the target process from all thread queues so that it would stop execution immediately. You will now rewrite it so that it sends a signal to the target.

Two other system calls relate to how the kernel transfers control to a signal handler and then back to the regular code for a process. When a signal is sent to a process, the kernel arranges for the signal handler function to be called within the process. When the signal handler returns, control must pass back to the kernel, which arranges for the process to resume from wherever it was. To accomplish this, we define a system call ReturnSignal that is to be invoked by the process when its signal handler returns. However, we cannot count on every signal handler to call ReturnSignal explicitly. Instead, the compiler will include a user-side function, called the "trampoline," in every executable. The kernel sets the return address of each signal handler to go to the trampoline. How does the kernel know where the trampoline is? We must define another system call, RegDeliver, to register it at the beginning of each user program. The compiler wraps each program's main function with some code that, among other things, calls RegDeliver.

The last system call that you will implement is WaitNoPid. This call allows a parent to collect the exit status for a child that has terminated and become a zombie, without knowing its PID or going into a blocking wait. The child can then be reaped. You will arrange for the kernel to send a parent a particular signal when one of its children terminates (unless the parent is already waiting for that child). The parent can catch that signal and call WaitNoPid to collect the exit status.

1. Background

Every process runs within a context. Some parts of the context, such as open file descriptors, are stored in the User_Context for the process. For the most part, these parts of the context change infrequently. Other parts are directly related to the state of the CPU, which may change with every cycle. When we refer to a "context" in this project, we are referring to the CPU context, which is described by the values of the registers (including the stack and instruction pointers).

When process A sends a signal to B, the kernel must create a new context that causes B to execute its signal handler, then return B to its original context. This task is the core of the project. In preparation, we describe context switching here.

1.1. Context Switching

To give the impression of kernel threads running concurrently, the kernel gives each thread a small time quantum to run. When this quantum expires, or the thread blocks for some reason, the kernel will context-switch to a different thread. To do this, it must save the state of the currently-running thread, load the state of the thread to switch to, and then start running the new thread. The code to switch to a new thread is written in assembly code, in the routine Switch_To_Thread.

Two important considerations are: (1) where should the kernel save the thread context during a context-switch? (2) what should this context consist of? These questions are answered in turn.

1.2. The Kernel Stack (Thread Stack)

The kernel stack is the stack used by a Geekos kthread while it is executing in the kernel. The kernel stack stores the local variables used by the kernel thread while running GeekOS kernel routines, just as the stack does in a user program. Every kthread has a kernel stack, whether it is a system thread (such as the idle or reaper thread) or is implementing a user process. When performing a context switch from one thread to another, the context of the first thread is saved on its kernel stack.

The context of a thread consists of the current values of most of the CPU registers; more detail is given below. Because these registers include the instruction pointer and stack pointer, restoring the context allows the thread to resume execution as though it had not been interrupted. The saved context may sound familiar: it is the Interrupt_State struct that you have encountered while implementing syscalls. It is defined in include/geekos/int.h.

The fields stackPage and esp, defined in the Kernel_Thread structure, specify where the thread's kernel stack is (esp is the saved value of the kernel stack pointer). When a thread is to be resumed, the current thread sets the %esp register to the new thread's stack, and then restores the other register values from the Interrupt_State that is stored on that stack.

To prepare a kthread to be run for the first time, GeekOS pushes the same state on the kernel stack that it would have had if it had been previously running, and been preempted or received an interrupt. The code to create this initial state is in Setup_Kernel_Thread and Setup_User_Thread in kthread.c.

Stacks grow downward, from numerically higher addresses to numerically lower addresses.

1.3. User Processes

User processes have a kernel stack, for calls within the kernel when the kernel is running on the process's behalf, and a user stack, for local variables while running user-level code. The saved context for a user thread must include both stack pointers.

As described above, GeekOS prepares a user process to run for the first time by pushing a starting context onto the stack. The process can then be resumed as though it had previously been running. The state pushed onto the kernel stack includes the following:

1. Context Information: this includes (almost) all the registers used by the user (GS, FS, ES, DS, EBP, EDI, ESI, EDX, ECX, EBX, EAX)
2. Error code and Interrupt number (set to zero if the thread did not receive an interrupt).
3. Program counter: this contains the value that should be loaded into the instruction pointer register (EIP). When setting up the initial context for a user process, GeekOS pushes the entry point for the program, which is specified in the executable file.
4. Text selector: this is the selector corresponding to the code segment (CS) of the process. (For more information about selectors, see the appendix to project 1. In brief, they tell the CPU what segment of memory is available for various purposes, such as executable code, the stack, and other data.)
5. The EFlags register.
6. User stack data selector and user stack pointer: these point to the location of the user stack.

When the thread is scheduled for the first time, these initial values will be loaded into the corresponding processor registers and the thread can run. The initial stack state for a user thread is described in the following figure. (Again, you may wish to refer to Setup_User_Thread() in kthread.c.)

The items at the top of this diagram (in high memory) are pushed first, the items at the bottom (in lower memory) are pushed last (i.e., the stack grows downward). In this figure, the contents of the stack, not including the user stack location, are defined in struct Interrupt_State in geekos/int.h. This is the structure you're familiar with from modifying system calls in syscall.c. When necessary, you can cast the struct Interrupt_State to a struct User_Interrupt_State. As suggested in the table, the User_Interrupt_State gives you access to the user stack segment and user stack pointer. Since the cast effectively makes the structure go two words farther into the stack, make sure that you use it only when a user process is interrupted.

1.4. The User Stack

The user stack selector is the same as the data selector: that is, both the stack and the data segment occupy the same memory segment. The user stack starts at the high end of the data segment and grows downward. Initially, the user stack pointer should indicate an empty stack. So it points to the end of the data segment.

When switching to a thread that is in user mode (or switching from kernel to user mode within a thread), the kernel calls Switch_To_User_Context() in src/geekos/user.c. Switching the context includes the following steps:

• Save the context of the currently executing thread.
• Switch to a new address space by loading the LDT of the new thread (ldtSelector of User_Context) using the lldt assembly instruction.
• Clear the kernel stack.

2. Project Requirements

This project will require you to make changes to several files. In general, look for the calls to the TODO() macro. There are three primary goals of this project:

• Add the code necessary to support signals
• Implement a collection of system calls to set up and send signals
• Raise SIGCHLD when an attached child process terminates with no parent waiting, and implement a system call to allow the parent to collect the child's exit status

In the course of the project, you will need to add several fields to the User_Context struct.

2.1. Signals

In this project, you must implement signal handling and delivery for the following four signals (defined in include/geekos/signal.h):

SIGKILL:

This is is the signal sent to a process to kill it. The specific behavior for a process that receives SIGKILL is described below, under "Termination." The process is not permitted to install a signal handler for SIGKILL.

SIGUSR1, SIGUSR2:

"User-defined" signals with no pre-determined purpose. These will be sent only by other processes.

SIGCHLD:

When a child process dies, if its parent is not already blocked Wait()ing for it, a SIGCHLD signal should be sent to the parent process. The SIGCHLD signal is sent only for attached children (with a refcount of 2 and non-null owner), not detached ones. When a child process dies, the parent can be informed of this fact by SIGCHLD, and thus can reap the child, using the Sys_WaitNoPID system call, defined below.

Further Reading: More information about signal handling can be found in Chapter 4 of the text. A nice tutorial on UNIX signals can be found here.

2.2. System Calls

In this project, you will implement five system calls. The user-space portion of these calls is defined for you in src/libc/signal.c:

Sys_Signal

This system call handler registers a signal handler for a given signal number. The signal handler is a function that takes the signal number as an argument, processes the signal in some way, then returns nothing (void). The function prototype for a signal handler is typedef'd in include/geekos/signal.h. Note that the signal handler does not have to use the signal number passed to it. If called with SIGKILL, return EINVALID. The handler may be set as the pre-defined "SIG_DFL" or "SIG_IGN" handlers. SIG_IGN tells the kernel that the process wants to ignore the signal (it need not be delivered). SIG_DFL tells the kernel to revert to its default behavior, which is to terminate the process on KILL, USR1, and USR2, and to discard (ignore) on SIGCHLD. A process may need to use SIG_DFL to restore the default signal handling behavior after setting the handler to something else.

Sys_Kill

In project 1, this system call handler took as its argument the PID of a process to kill. In this project, it will be used to send a signal to a certain process. So in addition to the PID, Sys_Kill will take a signal number, which must be one of the four defined above. If called with a different signal number, it should return EINVALID. It should be implemented as setting a flag in the process to which the signal is to be delivered, so that when the given process is about to start executing in user space again, rather than returning to where it left off, it will execute the appropriate signal handler instead.

Sys_ReturnSignal

As we have discussed, the signal handler executes in a new context that the kernel creates. After it finishes executing, the kernel must restore the previous context. It does this when the user process invokes the ReturnSignal system call. We cannot assume that all signal handlers will call ReturnSignal on their own. Instead, the signal handler context is set up so that the handler "returns" to some stub code, which is provided in src/user/lowlevel.s. The stub code invokes the system call. The stub code is referred to as the "trampoline" function, since it enables the process to bounce from the signal-handling context back to its normal context. Since the stub calls ReturnSignal from assembly, libc does not include a C interface to call it. So while it would probably not be harmful for a signal handler to call it directly, it is not easily possible.

Sys_RegDeliver

This system call must be invoked before a user process begins to execute. It provides the kernel with the address of the trampoline function, as described for Sys_ReturnSignal. As with Sys_ReturnSignal, we cannot expect all user programs to make this system call on their own. Instead, it is invoked from a subroutine of the _Entry() function, which is compiled into all GeekOS user programs. When a program begins to execute, it starts in _Entry; _Entry performs some initialization and then calls main(). You can see the code for _Entry in src/libc/entry.c, and for the Sig_Init subroutine (which actually makes the system call) in src/libc/signal.c. Note that the the user code that calls Sys_RegDeliver and Sys_ReturnSignal is already written for you in libc. Your task is to implement them on the kernel side. As with Sys_ReturnSignal, it would probably not be harmful for user code to call Sys_RegDeliver directly, as long as it passed in the correct trampoline function. However, it is not necessary to do so.

Sys_WaitNoPID

This system call handler is not part of the signalling system, but rather is used in the SIGCHLD signal handler. Recall that the Sys_Wait system call handler takes as its argument the PID of the child process to wait for, and returns when that process dies. The Sys_WaitNoPID handler, in contrast, takes a pointer to an integer as its argument, and calls Detach_Thread for any zombie child process that happens to have terminated. (It detaches only one child process per call, even if more than one has terminated.) It places the exit status in the memory location the argument points to and returns the pid of the zombie. If there are no dead child process, then the system call returns ENOZOMBIES. WaitNoPID reaps only children of the process that calls it, leaving other zombies alone.

Termination

Reentrancy and Preemption

2.3. Signal Delivery

To implement signal delivery, you will need to implement (at least) five routines in src/geekos/signal.c:

Send_Signal:

This takes as its arguments a pointer to the kernel thread to which to deliver the signal, and the signal number to deliver. This should set a flag in the given thread to indicate that a signal is pending. This flag is used by Check_Pending_Signal, described next.

Check_Pending_Signal:

This routine is called by code in lowlevel.asm when a kernel thread is about to be context-switched in. It returns true if the following THREE conditions hold:

1. A signal is pending for that user process.
2. The process is about to start executing in user space. This can be determined by checking the Interrupt_State's CS register: if it is not equal to the kernel's CS register (see include/geekos/defs.h), then the process is about to return to user space.
3. The process is not currently handling another signal (recall that signal handling is non-reentrant).

Set_Handler:

Use this routine to register a signal handler provided by the Sys_Signal system call.

Setup_Frame:

This routine is called when switching to a user process, if Check_Pending_Signal returns true. It sets up a user process's user stack and kernel stack so that (1) when the process returns to user mode, it will execute the correct signal handler, and (2) when that handler completes, the process will return to the trampoline function so that it can go back to what it was doing. IF instead the process is relying on SIG_IGN or SIG_DFL, handle the signal within the kernel. IF the process has defined a signal handler for this signal, function Setup_Frame will have to do the following:

1. Choose the correct handler to invoke.
2. Acquire the pointer to the top of the user stack. This is available when you cast the saved Interrupt_State (on the kernel stack) to a User_Interrupt_State, as shown in the figure above.
3. Push onto the user stack a snapshot of the interrupt state that is currently stored at the top of the kernel stack.
4. Push onto the user stack the number of the signal being delivered.
5. Push onto the user stack the address of the trampoline (which invokes the Sys_ReturnSignal system call handler). The trampoline was registered by the Sys_RegDeliver system call handler, mentioned above.
6. Now that you have saved a copy of the kernel stack, change the original User_Interrupt_State such that
   1. The user stack pointer is updated to reflect the changes made in steps 3--5.
   2. The saved program counter (eip) points to the signal handler.

Complete_Handler:

This routine should be called when the Sys_ReturnSignal call handler is invoked (after a signal handler has completed). It needs to restore back on the top of the kernel stack the snapshot of the interrupt state currently on the top of the user stack.