Project 2

CMSC 412, Fall 2008

Due Monday, October 13, at 11:59pm


In this project, you are going to implement support for signals in the GeekOS. Signals are to user processes what interrupts are to the kernel: by sending a process a signal, one can cause the process to temporarily stop what it is doing to attend to an event.

Quick Links

1. Preliminaries

Before we speak specifically about delivering signals to processes, we describe how context switching works in GeekOS.  This is important for the implementation of signal delivery: when a process receives a signal, it does not continue executing as it would have, but is instead redirected to the signal handler.  When this handler completes, it can go back to what it was doing (unless another signal arrived in the meantime!).  This is implemented via hooks into the context-switching code in GeekOS.

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 I 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 kernel thread while it is executing in the kernel.  As usual, the kernel stack stores the local variables used by the kernel thread whilst running GeekOS kernel routines.  This could be for kernel threads performing system processes, like the reaper thread, or it could be for kernel threads implementing user processes, executing system calls on their behalf.

When performing a context switch, the current state (or "context") of a thread is saved on its kernel stack.  This state consists of the current values of (most of) the registers.  The fields stackPage and esp defined in the Kernel_Thread structure, specify where the thread's kernel stack is (esp is the kernel stack pointer).  This way, when a thread is to be context-switched to, the current thread switches to the new thread's stack, and then restores the context.

1.3. User Processes

User processes have two stacks: the kernel stack and a user stack. The user stack is used as the program stack for local variables and so forth when running the user program. The kernel stack (described above) is used by the GeekOS kernel when running within the kernel on the process's behalf, i.e., when performing system calls.

To prepare a user process to be run for the first time, GeekOS sets up the kernel stack to look as if the thread had previously been running and then context-switched to the ready queue.  To present this illusion requires setting up the kernel stack properly.  In particular, the OS pushes the initial values for all of the processor registers onto the kernel stack when the thread is created. The information pushed into the user process' 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.

3- Program counter: this contains the value that should be loaded into the instruction pointer register (EIP). Initially, when the user process is about to run, GeekOS pushes the entry point for the process and this value will be subsequently loaded into EIP.

4- Text selector: this is the selector corresponding to the code segment (CS) of the process.

5- The EFlags register.

6- User stack data selector and user stack pointer: these point to the location of the user stack

(For more information about selectors, see the appendix to project 1.)

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 (check Start_User_Thread() in src/geekos/kthread.c):

User Stack Data Selector (data selector)

User Stack Location

User Stack Pointer (to end of user's data segment)



Text Selector (code selector)

Program Counter (entry addr)

Error Code (0)

Interrupt Number (0)

EAX (0)

EBX (0)

ECX (0)

EDX (0)

ESI (Argument Block address)

EDI (0)

EBP (0)

DS (data selector)

ES (data selector)

FS (data selector)

GS (data selector)

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 the above figure, all of the stack aside from the user stack location is defined in the struct Interrupt_State, defined in geekos/int.h.  Indeed, this state is what is passed into each of the system calls in syscall.c, with which you are now quite familiar.

1.4. The User Stack

The user stack selector is the same as the data selector (i.e. both the stack and the data segment occupy the same memory segment). The user stack starts at the very end of the data segment and grows down (as is typically the case). Initially, the user stack pointer should indicate an empty stack. So it points at the end of the data segment.

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


2. Project Requirements

This project will require you to make changes to several files. In general, look for the calls to the TODO() macro. These are places where you will need to add code, and they will generally contain a comment giving you some hints on how to proceed. There are three primary goals of this project:

2.1. Signals

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


1- SIGKILL: This is is the signal sent to a process to kill it. You should write the handler for this signal such that it results in the same behavior as in project 1's Sys_Kill.


2&3- SIGUSR1 and SIGUSR2: These are "user-defined" signals with no pre-determined purpose.


4- SIGCHLD: Whenever a child process dies, a SIGCHLD signal should be sent to its parent process.  In this project, we will change how we implement background processes to not be "detached" (i.e. the refCount of a background process will start as 2, rather than 1, as in project 1).  Instead, when a background process dies, the parent will be informed of this fact by SIGCHLD, and thus can reap the child, using the Sys_WaitNoPID system call, defined below.  This is the default action taken by a process that receives SIGCHLD; see 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 src/libc/signal.c:

1- Sys_Signal: This system call registers a signal handler for a particular signal. A signal handler is merely a function that takes no arguments and returns no result---the appropriate handler is called when the process is sent the signal for which it is registered. This system call takes as its arguments the pointer to signal handler function and the signal number that it handles. A user process is not permitted to register a handler for signal SIGKILL; attempting to do so should result in an error (a negative return code).  In addition to specifying a specific handler function defined by the user process, Sys_Signal may be passed SIG_IGN, to indicate the signal should be ignored, or SIG_DFL, to say that the default signal handler should be used.

The initial handler registered for SIGCHLD is Def_Child_Handler, defined in src/libc/signal.c.  This routine is registered automatically in _Entry (in src/libc/entry.c), by using the Sys_Signal system call.  It will reap all zombie processes that are children of the current process.

2- Sys_RegDeliver: The signal handling infrastructure requires that three functions be implemented for each user space program. The first is the handler that should be used when a signal is to be "ignored". The second is the "default" handler, which terminates the process by calling Exit. The third is the bit of code---a "trampoline"---that invokes the system call Sys_ReturnSignal (see below) at the conclusion of signal handler. All three of these functions/code snippets are registered with the kernel using the Sys_RegDeliver system call; check out the user-space implementation in src/libc/signal.c. User-programs should not invoke this system call directly; rather it will be invoked in the _Entry function in src/libc/entry.c which is always invoked prior to running a user program's main() function.

3- Sys_Kill: In project 1, this system call 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---one of the four defined above. 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.


An important question is how to determine which handler to use for a delivered signal.  If a process receives a signal and no explicit signal handler has been defined for that signal by Sys_Signal, then the default signal handler will be invoked (the address of this handler for this process should have been provided by the Sys_RegDeliver system call). In src/libc/process.c you will see that the default handler calls Exit to terminate the process after printing a termination message. For example, assume that a user process P has not called Sys_Signal with signal number SIGUSR1. So if Sys_Kill is executed upon this process with signal number SIGUSR1, the default handler will be executed and the target process will terminate.

- You should implement signal handling to be non-reentrant. That is, when a process is handling a signal, that handler should not be preempted due to another signal to be delivered. Instead, the kernel sets a flag to indicate the signal that was received but not delivered. When the current signal handler completes, the pending signal will be eligible for delivery. Note that the flag will be the same even if the same signal is received more than once while a handler is executing. For example, if SIGCHLD is sent to process P twice while it's in its SIGUSR1 handler, when that SIGUSR1 handler completes, process P's SIGCHLD handler will only be called once, not twice. When several signals are pending, the order that they are delivered is unspecified (i.e., they could be delivered in any order).

4- Sys_ReturnSignal: This system call is not invoked by user-space programs directly, but rather is executed by some stub code at the completion of a signal handler. That is, Sys_Kill/Send_Signal sends process P a signal, which causes it to run its signal handler. When this handler completes, we will have set up its stack so that it will "return" to the trampoline registered by Sys_RegDeliver.  This trampoline wil invoke Sys_ReturnSignal to indicate that signal handling is complete.

5- Sys_WaitNoPID: The Sys_Wait system call takes as its argument the PID of the child process to wait for, and returns when that process dies. The Sys_WaitNoPID call, in contrast, reaps ANY zombie child process that happens to have terminated, and whose refCount is 1. Its argument is a pointer to an integer. If there is a zombie child process whose refCount is 1, then the exitCode of that process should be stored in the pointed-to user memory, and that process's PID should be returned. If there is no dead child process, then the system call should return -1.

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 to.  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 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 Check_Pending_Signal returns true, to set up a user process's user stack and kernel stack so that when it starts executing, it will execute the correct signal handler, and when that handler completes, it will invoke the Sys_ReturnSignal system call to go back to what it was doing. This function 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 essentially below the saved interrupt state stored on the kernel stack as visualized above.
3- Push onto the user stack a snapshot of the interrupt state that is currently stored at the top of the kernel stack.  The interrupt state is the topmost portion of the kernel stack, defined in include/geekos/int.h in struct Interrupt_State, visualized above.
4- Push onto the user stack the address of the "signal trampoline" that invokes the Sys_ReturnSignal system call, and was registered by the Sys_RegDeliver system call, mentioned above.
5- Change the current kernel stack such that (notice that you already saved a copy in the user stack)

(1) The user stack pointer is updated to reflect the changes made in step 3 & 4.
(2) The saved program counter (eip) points to the signal handler.


- Complete_Handler: this routine should be called (by your code) when the Sys_ReturnSignal call is invoked, to indicate 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.


You can either build this project directly from the kernel we provide here, or merge the provided kernel with your project 1 solution.  The advantage of merging is that you will get a more full featured kernel, which may make things easier to test.  For example, the Sys_PS system call will be handy for testing. We will not subtract points from your project 2 score for features implemented in project 1.  In particular: