CS 354 Spring 2023

Lab 2: Synchronous Interrupt Handling in x86 XINU and Trapped System Call Implementation [255 pts]

Due: 02/22/2023 (Wed.), 11:59 PM

1. Objectives

The objectives of this lab are to understand XINU's basic interrupt handling on x86 Galileo backends for synchronous interrupts: source of interrupt is either an exception (also called fault) or software interrupt int. We will then utilize the int instruction to change XINU system calls from regular function calls into trapped system calls, which follows the traditional method for implementing systems calls in Linux and Windows on x86 computers.

2. Readings


When working on lab2:

For the written components of the problems below, please write your answers in a file, lab2ans.pdf, and put it under lab2/. You may use any word processing software as long as they are able to export content as pdf files using standard fonts. Written answers in any other format will not be accepted.

Please use a fresh copy of XINU, xinu-spring2023.tar.gz, but for preserving the mymotd() function from lab1 and removing all code related to xsh from main() (i.e., you are starting with an empty main() before adding code to perform testing). As noted before, main() serves as an app for your own testing purposes. The TAs when evaluating your code will use their own main() to evaluate your XINU kernel modifications.

3. Custom handling of synchronous x86 interrupts [75 pts]

3.1 Divide-by-zero exception and kernel response: process termination

x86 generates a divide-by-zero exception or fault, which is interrupt number 0, if an instruction tries to divide a number by zero. For example, C code

int main() { int r, s = 5; r = s / 0; return; }
when translated into machine code will trigger divide-by-zero exception. As discussed in the lectures, the first entry in IDT set up by XINU during system initialization (the same goes for Linux and Windows) for interrupt number 0 will contain a function pointer to an interrupt handler that x86 will jump to. The function pointer -- more precisely, entry point or label that represents an address in main memory -- is _Xint0 in system/intr.S. Modify the code at _Xint0 so that instead of jumping to Xtrap which, in turn, calls trap() in evec.c _Xint0 calls your code, void divzero1(void), in system/divzero1.c. Create a subdirectory codeversions/ under xinu-spring2023/ and and deposit a copy of the modified intr.S as intr1.S in subdirectory codeversions/. After calling divzero1() _Xint0 executes iret. Code divzero1() to call kprintf() to output a suitable message indicating that divide-by-zero has occurred, then calls kill(), instead of calling panic() which hangs a process in an infinite loop, to terminate the process. Hence _Xint0 does not get a chance to execute iret since divzero1() does not return.

3.2 Divide-by-zero exception and kernel response: return from interrupt

When an interrupt is triggered in x86, the hardware saves essential state (or context) of the process that has been interrupted onto the process's stack. If a process is in kernel mode when an interrupt occurs, x86 saves the content of registers EFLAGS, CS, and EIP by pushing their values onto the process's run-time stack. EFLAGS is pushed first, followed by CS, then EIP. It does so atomically meaning that the three operations are carried out as one code unit without interruption. If a process is in user mode when an interrupt occurs, x86 first saves the content of registers SS and ESP before saving EFLAGS, CS, EIP. In XINU where all processes start out in kernel mode, stay in kernel mode during the entirety of their execution, and terminate in kernel mode, the stack will contain EFLAGS, CS, EIP. In the case of divide-by-zero exception (i.e., interrupt number 0) of 3.1, when x86 jumps to _Xint0 the stack pointer ESP points to the top of the stack which contains the value EIP pushed by x86. For some interrupts -- but not divide-by-zero -- a 4-byte error code may be pushed by x86 onto the top of the stack to convey additional details about an interrupt. For example, the most common interrupt your XINU code is likely to generate due to bugs is GPF (general protection fault), i.e., interrupt number 13 where x86 pushes an error code. For our purposes, we will use the terms "exception" and "fault" interchangeably to mean synchronous interrupt.

For some synchronous interrupts the return address (i.e., content of EIP) pushed by x86 onto the stack is the address of the next instruction of the interrupted process to execute upon return. More commonly the address of the instruction that caused an exception is saved which helps identify the address of the interrupt causing instruction. Knowing the address of the instruction that triggered an interrupt is useful for diagnosing system behavior and in cases where it makes sense to re-execute the interrupt causing instruction after the lower half has mounted a response. For example, in the case of page fault (interrupt number 14) which is triggered when a valid reference to main memory fails because the kernel kept the referenced content on disk due to main memory pressure, the lower half's job is to bring the missing content back into main memory and re-execute the memory reference instruction that failed earlier causing a page fault. Re-executing the same instruction will now succeed. Code void divzero2(void), in system/divzero2.c, that may be called by _Xint0 in place of divzero1(). Instead of calling kill() to terminate the current process, divzero2() returns to the caller after printing the same message as divzero1(). Use a static variable in divzero2() to keep track of how many times it has been called. If the count exceeds 10, make divzero2() call kill() instead of returning to its caller.

Upon returning from divzero2() to _Xint0, the next instruction executed by _Xint0 is iret. Whereas the regular ret instruction pops the content in the stack pointed to by register ESP into register EIP, iret assumes that the top of the stack contains three values (EFLAGS, CS, EIP) saved by x86 upon encountering an interrupt and pops them atomically. Thus before executing ret or iret, it is important to make sure that ESP points to the correct location in the stack where the return address (and possibly saved CS and EFLAGS values) are contained. For example, if a process triggers interrupt number 13 (GPF) x86 pushes a 4-byte error code onto the stack and ESP points to the error code. Before executing iret ESP would need to be increased by 4 to point to the return address. Keeping track of what happens to the run-time stack, when relevant, is the programmer's responsibility. Deposit a copy of intr.S as codeversions/intr2.S. Test the behavior of divide-by-zero exception when _Xint0 calls divzero2() and describe your finding in lab2ans.pdf.

3.3 Generating synchronous interrupts using instruction INT

In 3.1 and 3.2 we used actual division by 0 (i.e., executing a DIV instruction stemming from C code "r = s / 0") to generate interrupt number 0. Another way of generating an interrupt is via instruction INT, also called software interrupt. We can embed assembly code (i.e., execution of instruction INT) in C code through inline assembly

int main() { int r, s = 5; asm("int $0"); return; }
which asks gcc to embed assembly code, int $0, at the specified location in C code when translated into assembly. In Problem 5.1 of lab1 we considered ABI programming where a function coded in assembly is called from a C function. When assembly code is but a few instructions, a more efficient implementation is to use inline assembly which does not incur the overhead associated with function calls. Repeat the test of 3.2 but with main() using inline assembly to generate interrupt number 0. Discuss your finding in lab2ans.pdf.


4. Trapped system call implementation [180 pts]

4.1 Objective

XINU system calls are regular C function calls that do not contain a trap instruction to switch between user mode and kernel mode. We will implement trapped versions of XINU system calls that follow most of the way Linux and Windows traditionally implement system calls on x86. Our implementation does not go all the way as we haven't yet covered scheduling and the mechanics of process context-switching needed for a newly created process to execute in user mode. Our implementation covers the bulk of traditional trapped system call implementation in x86 Linux and Windows where a system call uses software interrupt INT to trap to the lower half of the XINU kernel, changes to a different stack (i.e., kernel stack), and jump to the kernel function in the upper half to carry out the request task. Upon completion, the upper half kernel function returns to the lower half which switches back to user stack and untraps by returning to user code.

4.2 Three software layers

As discussed in class, we consider three software layers when implementing trapped system calls.

System call wrappers. The first layer is the system call API which is a wrapper function (running in user mode in Linux and Windows) that ultimately traps to kernel code in kernel mode via a trap instruction. For example, fork() in Linux is a wrapper function that is part of the C Standard Library (e.g., glibc on our frontend Linux machines). Similarly for CreateProcess() which is part of the Win32 API in Windows operating systems. XINU's getpid() system call is not a trapped system call since it does not execute a trap instruction to jump to kernel code in kernel mode. Similarly for the new system call, syscall childrennum(pid32 pid), that you implemented in 3.1(d) of lab1 that returned the number of child processes of the process specified in the argument. We will implement a wrapper function, syscall xchildrennum(pid32 pid), in system/xchildrennum.c that acts as the API that programmers use to invoke the kernel service requesting the number of children of a process. That is, as with fork() xchildrennum() will be the system call API used to trap to kernel code via trap instruction INT coded using extended inline assembly. The chief difference of extended inline over plain inline assembly that we will utilize is the ability to copy the value of C variables into registers before inline assembly code executes, and vice versa after inline assembly has executed.

We will use interrupt number 46 which legacy XINU does not use as the entry of IDT (interrupt descriptor table) -- the interrupt vector of x86 -- to jump to the system call dispatcher code in XINU's lower half. Interrupt numbers 0-31 are reserved in x86 for backward compatibility, XINU uses 32 to service clock interrupts, 42 is used by TTY, and 43 by Ethernet. Traditionally interrupt number 46 is used by Windows whereas Linux uses 128 to trap to system call dispatchers in their kernel lower halves. XINU's system call wrappers must communicate which system call is being invoked (i.e., system call number) to the system call dispatcher. We will do so by copying the system call number into register EAX before executing, int $46, via extended inline assembly in the system call wrapper function. If system calls have arguments they must be passed to the system call dispatcher as well. For example, the system call API xchildrennum() has one argument of type pid32 (which is typedef int32 whose C type is defined in include/kernel.h). If a system call has one argument as is the case for xchildrennum() we will pass its value from the system call wrapper to system call dispatcher in register EBX using extended inline assembly. For system calls that have two arguments, we will communicate the value of the second argument through ECX. We will not consider system calls with three or more arguments which may be passed through additional registers or pushing the values on the run-time stack.

System call dispatcher. The second software layer is the system call dispatcher in the lower half of the XINU kernel. Entry 46 in XINU's IDT has been configured to point to label _Xint46 in system/intr.S. You will modify the assembly code at _Xint46 so that it performs the tasks of a system call dispatcher which include checking which system call is being called, making a call to an internal kernel function in the upper half to carry out the requested kernel service. As noted above, _Xint46 will assume that EAX contains the system call number, single arguments in system calls are passed through EBX, two arguments in EBX and ECX parsed right to left similar to CDECL (i.e., second argument in EBX and first argument in ECX).

Upon entry the chores of _Xint46 include saving the state of the interrupted user code and disabling interrupts since XINU's IDT has not been configured to automatically disable further interrupts. Another key task before calling an internal kernel function in the upper half is to switch the run-time stack of the process in consideration of the 5th hardware/software support necessary to achieve isolation/protection. When a process is created, we will allocate a second stack per-process to be used as kernel stack. We will do so by modifying create() which calls getstk() a second time and store the address returned in a new process table field, char *prkstack. The content of the second stack when allocated by create() is empty. Fix the size of the second stack to 16 KB.

One of the first chores of _Xint46 is to copy the values of EFLAGS, CS, EIP stored at the top of the (user) run-time stack by x86 to the second (kernel) stack of the process. We will do so by popping the content of the user stack and pushing the popped values onto the process's kernel stack. Note that this will reverse the order in which the three values are stored in the kernel stack, with EFLAGS at the top of the stack pointed to by ESP. All subsequent function calls inside the kernel will be managed using the kernel stack. When copying the stored values of EFLAGS, CS, EIP from user stack to kernel stack, we must remember the address of the top of the user stack so that we can switch back from kernel stack to user stack before the system call dispatcher returns (i.e., untraps) to the system call wrapper by executing iret. We will do so by remembering the address of the top of the user stack after popping EFLAGS, CS, EIP in a new process table field, char *prustack. Note that "pushing" the popped EFLAGS, CS, EIP values onto the kernel stack does not mean that the x86 pushl instruction has to be used. Sometimes using instruction movl can lead to simpler and more efficient code. These implementation choices are up to you.

After switching stacks, _Xint46 is ready to check the system call number contained in EAX and call the internal kernel function in XINU's upper half to carry out the requested service. We will reuse the legacy XINU system call as the internal kernel function of the upper half. For example, xchildrennum() traps to _Xint46 which then calls childrennum(). Since childrennum() is coded in C, _Xtrap46 must follow CDECL when passing the argument contained in EBX to childrennum() by pushing its value onto the kernel stack. Then _Xint46 can invoke chidrennum() by executing the instruction, call childrennum. Upon entry into childrennum() in the upper half of XINU, the kernel stack will contain the saved values of EIP, CS, EFLAGS, EBX, EIP2, with EIP2 at the top of the stack where EIP2 is the return address pushed by x86 when _Xint46 executes, call childrennum.

Upper half internal kernel functions perform actual system call work. The third software layer are internal kernel functions in the upper half that perform the service requested of the kernel by the system call wrapper function. We will reuse XINU's legacy system calls coded in C as internal kernel functions in the upper half. Thus legacy system call, syscall childrennum(pid32 pid), is repurposed as an upper half kernel function that the system call dispatcher _Xint46 calls to carry out the actual service requested by a process.

System calls, by default, have a return value since, at a minimum, possible failure to complete a system call for myriad reasons by returning -1 (i.e., SYSERR) must be supported. Since legacy XINU system calls, including childrennum() that you implemented in lab1, are coded in C, values are returned to the caller through register EAX following CDECL. Since the machine code of childrennum() is generated by gcc obeying CDECL the caller _Xint46 can assume that childrennum()'s return value is stored in EAX. _Xint46, in turn, must communicate the return value of childrennum() to the wrapper function xchildrennum(). _Xint46 will do so using EAX. Hence _Xint46 must not disturb the content of EAX before executing iret to untrap to the system call wrapper function. The wrapper function xchildrennum() can access the value contained in EAX using extended inline assembly and copy it to a local C variable that is then returned to its caller, say main(). However, noting that both xchildrennum() and main() are coded in C whose machine code produced by gcc follow CDECL, it may be possible to omit copying EAX's value into a C variable if the EAX value returned by _Xint46 is left undisturbed by xchildrennum() before it returns to main(). How you choose to forward the return value received by xchildrennum() from _Xint46 to its caller main() is up to you.

Last, but not least, when we inspect clkdisp.S which is the entry code in XINU's lower half for clock interrupts we notice that clkdisp.S saved the 8 general purpose registers which includes EAX upon entry by executing pushal and restores their values by executing popal before executing iret. This prologue and epilogue code of saving and restoring register values is aimed at putting the state of the interrupted process back to its original state before it was interrupted. However, doing so blindly in _Xint46 would disturb the return value in EAX thus leading to a bug. What state of an interrupted process must be saved and restored must be carefully considered by thinking through the problem and what your code does.

4.3 Supported system calls

We will provide trapped system call support for three XINU system calls: childrennum(), chprio(), sleepms() with their respective wrapper functions xchildrennum(), xchprio() in system/xchprio.c, xsleepms() in system/xsleepms.c. chprio() has two arguments that specify the PID of a process whose priority should be set to a specific value. sleepms() has a single argument that specifies in unit of msec the time a process wishes to sleep. Define the system call numbers for the three system calls as 10, 14, 18 using macros SYSCHLN, SYSCHPR, SYSSLP in a new header file include/syscalls.h.

4.4 Testing

Test and verify that your trapped system call implementation works correctly. Discuss your method for assessing correctness in lab2ans.pdf.


Bonus problem [25 pts]

Extend the trapped XINU system calls to include kill() with wrapper function xkill() in system/xkill.c. Assign a suitable system call number. Test and verify that your implementation works correctly.

Note: The bonus problem provides an opportunity to earn extra credits that count toward the lab component of the course. It is purely optional.


Turn-in instructions

General instructions:

When implementing code in the labs, please maintain separate versions/copies of code so that mistakes such as unintentional overwriting or deletion of code is prevented. This is in addition to the efficiency that such organization provides. You may use any number of version control systems such as GIT and RCS. Please make sure that your code is protected from public access. For example, when using GIT, use git that manages code locally instead of its on-line counterpart github. If you prefer not to use version control tools, you may just use manual copy to keep track of different versions required for development and testing. More vigilance and discipline may be required when doing so.

The TAs, when evaluating your code, will use their own test code (principally main()) to drive your XINU code. The code you put inside main() is for your own testing and will, by default, not be considered during evaluation. If your main() is considered during testing, a problem will specify so.

If you are unsure what you need to submit in what format, consult the TA notes link. If it doesn't answer your question, ask during PSOs and office hours which are scheduled M-F.

Specific instructions:

1. Format for submitting written lab answers and kprintf() added for testing and debugging purposes in kernel code:

2. Before submitting your work, make sure to double-check the TA Notes to ensure that any additional requirements and instructions have been followed.

3. Electronic turn-in instructions:

        i) Go to the xinu-spring2023/compile directory and run "make clean".

        ii) Go to the directory where lab2 (containing xinu-spring2023/ and lab2ans.pdf) is a subdirectory.

                For example, if /homes/alice/cs354/lab2/xinu-spring2023 is your directory structure, go to /homes/alice/cs354

        iii) Type the following command

                turnin -c cs354 -p lab2 lab2

You can check/list the submitted files using

turnin -c cs354 -p lab2 -v

Please make sure to disable all debugging output before submitting your code.


Back to the CS 354 web page