Operating systems

Portail informatique

System calls

The goal of this lab is to make you familiar with xv6, a kernel developed at MIT to learn operating systems. The second goal of this lab is that you understand how a system call works. To do this, you will implement a new synchronization mechanism in the kernel and explore the basic structures of structures of xv6.

Installation (∼ 20mn)

First, let's clone the xv6 repository:
git clone https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-tsp.git

Then, create a local branch named tp-syscall for your lab:
git checkout -b tp-syscall

Then, compile the kernel:
make
In this course, it is only possible to compile and run xv6 on a Linux machine. If you don't have a Linux, install one, or connect with ssh to a Linux machine.

Start xv6 with the following command:
make qemu

This command starts xv6 in the qemu emulator. When xv6 starts, it launches a simple shell allowing to execute some basic commands. The code of shell is located in the sh.c file.

If you look at the source code, you can find the classic architecture of a system: the kernel library is called xv6 and consists of the files indicated in the variable OBJS that you will find in the Makefile. Each of the basic commands corresponds to a source file (cat.c, sh.c etc.). You can find the list of these commands, each prefixed with a _ in the variable UPROGS (user commands) of the Makefile.

For WSL users, make qemu tries to open a window, which may not work on your system. You can run qemu without a window by running:
make qemu-nox
To exit qemu, type Ctrl-A C then quit.
With WSL, XV6 may fail to start with the error message "No bootable hard drive". The problem comes from WSL bad handling of carriage return characters in Perl script. You can fix this by running:
sed -i -e 's/\r/\n/g' *.pl

It is also possible to run xv6 in debug mode for directly seeing the low-level kernel operation. To do this, run
make qemu-gdb
(make qemu-nox-gdb for WSL). This command launches a window to run xv6 in qemu. The start is interrupted just before the virtual machine starts and allows gdb to connect to it.

In another terminal, navigate to the sources of xv6, then run gdb. If you see an error message similar to this one :

warning: File "/home/gael/xv6/.gdbinit" auto-loading has been declined by your `auto-load safe-path' set to "$debugdir:$datadir/auto-load"

So, copy and paste the line displayed just after the line "To enable execution of this file add" in your gdb configuration file (~/.gdbinit) in order to allow the use of the .gdbinit script by gdb.

Once gdb starts correctly, type b main (break main) to interrupt the execution of xv6 when it reaches the main function then resume the execution of xv6 with the command c (continue). If all goes well, xv6 stops at the start of the main function.

Display the code of the main function with list. You can examine the code that initializes the system (the source code of this function can be found in main.c. Technically, this code is called from a trampoline in assembler which is located in entry.S and which takes care of installing the minimum vital allowing to switch to C. Technically, when grub loads the kernel, it jumps directly to the entry label, the assembler part correctly initializes the processor (we will explain how later) then jump on in the main function.

Welcome to an operating system kernel!

First system call (∼ 1h10)

The goal of this exercise is to add new system call to xv6. The system call we create is relatively artificial, but reproduces in a fairly realistic way the operation of the Linux futexes that you have studied in previous labs.

To start, we create a new command named ftest allowing us to test our new system call. This command, like any command, is executed in userland and therefore, ultimately, interacts with the kernel. For the moment, our command simply performs a simple display. To do this, start by creating a ftest.c file in which you define a function main which:
  • uses printf to display "starting". Attention, the printf function of xv6 takes a first parameter corresponding to the stream (stdin, stderr, stdout) you want to write on. As we want to write to the standard output, this parameter is 1 (remember of your CSC3102 courses).
  • calls exit() to exit the command. Without exit(), the program does not stop naturally like in Linux at the end of main and therefore runs random code that usually leads to an error.
The printf and exit functions are defined in the user.h header file, and this file requires to include types.h beforehand.

Now that we have our first command, we can compile and test it. To do this, modify the UPROGS variable the Makefile so that the ftest command is added to the list of commands. Then run xv6 (make qemu) and verify that your command works by running ftest in the shell.
Congratulations, you know how to create new commands in xv6!

Now that our command is functional, we can add our two system calls. These are the calls:
  • int fwake(int slot, int val) : this function considers that the kernel has internal variables, called slots, that are numbered from 0 to 5. The fwake function assigns the value val to the slot th slot, then wakes up the processes that are waiting for the variable slot to change value (see next function);
  • int fwait(int slot, int val) : this function pause the process as long as the slot number slot is not val.

A typical usage of fwake/fwait is given here:

#include "types.h" #include "user.h" int main() { if(fork() == 0) { printf(1, "%d - wait...\n", getpid()); fwait(1, 42); printf(1, "go go go!\n"); } else { sleep(500); printf(1, "%d - notify...\n", getpid()); fwake(1, 42); } exit(); }

This program starts by creating a child process that waits until slot 1 is set to 42 (initially, a slot is set to 0). The father process sleeps for 500 ticks (around 5s, time is managed in a very approximate in xv6) then sets slot 1 to 42, which wakes up the child process.

Start by copying and pasting this code into your ftest.c file.

We now add the fwait and fwake functions in user.h. These functions simply call the appropriate functions in the kernel by making a system call. For that:
  • give a syscall number to our system calls by adding SYS_fwait (number 22) and SYS_fwake (number 23) in syscall.h;
  • then, rather than writing the code that calls kernel functions 22 and 23 using assembly code, you are asked to add SYSCALL(fwait) and SYSCALL(fwake) at the end of usys.S. This macro then creates the fwait and fwake functions which call the system functions 22 and 23 for us. Technically, for fwait, this macro creates a fwait function which places the syscall number (22) in the registry %eax (remember that registers are internal variables of a processor) then executes the instruction int 0x40 which corresponds to the trap instruction in xv6;
  • then add the definition of these functions to the user.h file. This file contains the C signatures of assembler functions found in usys.S . The signatures of these functions are given to the previous question: int fwait (int slot, int val) and int fwake (int slot, int val) .

The test part in userland allowing to test the new system calls is now ready. Since you have not yet associated any code with these system calls in the kernel, calls must fail miserably with "unknown sys call 22" and "unknown sys call 23 " messages. Check that this is the case by compiling, by running xv6 (make qemu) and running your ftest command.

This question aims to understand step by step the sequence of events generated by calling fwait(1, 42) in your ftest command. Don't hesitate to ask your teachers when there are steps you can't get through to understand.

First, we take a look at what's going on in userland. To do this, open the file ftest.asm. This file contains the assembly code of your command ftest:

  • in that file, find the code corresponding to fwait(1, 42). You should see the setting up of arguments (push $0x2a knowing that 0x2a is equal to 42, and push $1) followed by a call to fwait (call 371). 371 is the address where the fwait function was generated. (Note: it is quite possible that you have an address other than 371 in your generated code).
  • we can then follow the flow of execution by looking for this 371 in the file. You should see the assembly code for the fwait function generated from usys.S. This assembly code consists of two instructions:
    • mov $0x16, %eax : sets %eax to 22, this is the number that corresponds to the fwait system call,
    • int $0x40 : trap instruction which switches to system mode.

From this point, the processor switches to system mode and continues its execution in the vector64 function (note that $0x40 = 64) which was associated with the trap when starting xv6. We can therefore follow the flow of execution as follows:

  • the vector64 function is located in the file vector.S. Technically, during an int 0x40, the processor switches to system mode and performs this function;
  • the assembler function vector64 sets arguments which, in fine, will be received by the C trap function located in the trap.c file. These are the values ​​64 and 0;
  • the code continues in alltraps located in the file trapasm.S. This function fills a struct trapframe (defined in x86.h) by saving the registers (the continuation of pushl followed by pushal), then set up a trampoline before jumping in the C trap function located in trap.c;
  • To understand how the struct trapframe is constructed, draw the contents of the stack after all these pushes and compare with the structure.
  • the trap function receives a tf argument. tf->trapno is equal to 64 because vector64 executed push $64. This value being equal to T_SYSCALL, the trap function calls syscall located in syscall.c;
  • the syscall function finds argument 22 corresponding to the system call by consulting tf->eax (remember the mov $0x16, %eax in userland ). As this entry does not yet exist in the kernel, syscall displays that the system call is unknown;
  • as the system call was unsuccessful, syscall logs the value -1 in tf->eax. This value is the return value of the system call. The execution continues in the opposite direction until we come back to the call site at fwait(1, 42) in the main of ftest.c.

To navigate more easily in the sources of xv6, we invite you to use the ctags tool (sudo apt-get install exuberant-ctags) which allows you to index source code and perform research.

  • To generate an index, run the command make tags which invokes etags *.S *.c (you can also modify the Makefile to also index *.h files).
Then, the use of the index depends on your publisher:
  • With emacs:
    • To find the definition of a function (or of a type), position the cursor on the type, then do M-. ("META dot", so the Esc key then the . key)
    • To go back, type M-,
  • With VIM:
    • To find the definition of a function or a type, position the cursor on the function, then type C-] (Ctrl and ])
    • To go back, type C-t

Now that our userland test infrastructure is in place, we can write the fwait and fwake system calls in the kernel. You're about to write your first lines of kernel code!

In the syscall.c file, modify the syscalls table to match respectively the system call SYS_fwait to sys_fwait and the SYS_fwake system call to sys_fwake. Add the signatures of these functions just before the definition of the syscalls structure, as it is done for sys_uptime.

In proc.c, which takes care of managing the processes and who therefore owns the list of processes, add the functions sys_fwait and sys_fwake. Each of these functions must display a message using the function kernel cprintf then return 0. The cprintf function behaves much like the printf function that you know (but does not require an additional argument like printf in userland since cprintf can only do a display on the console).

Check that the messages are displayed when you run the command ftest .

Congratulations, you now know how to create system calls in xv6 and you are able to test them!

Implementing system calls (∼ 1h)

We first take care of the sys_fwait function. First, let's get the arguments of the system call. To do this, use the argint function. You will find an example of its usage in sysproc.c. Print the values ​​of the first two parameters of sys_fwait and verify that they are 1 and 42.

We now create the slots. In proc.c, add a variable int slots [] that you initialize with an array of 5 elements at 0.

As the xv6 kernel can run in parallel on multiple cores, you must acquire a lock before accessing slots. Indeed, it is quite possible that another core executes fwake while fwait is being executed. In sys_wait, acquire the lock ptable.lock after extracting the arguments and then release it. This lock is the one used by the xv6 scheduler. We use it here because we modify the state of our process to put it to sleep, and the acquisition the ptable.lock lock therefore also protects us while we modify the state of the process.

In order to wake up the processes that are waiting on a slot, we add an integer wait_slot field in the structure of a process. When this field is 1, the process is waiting for a slot to change value. Add this field to the proc structure in the file proc.h.

In sys_wait, you must be able to find the structure proc corresponding to the current process. For this you can call myproc(). Next, as long as slots[slot] is not equal to val (where slot and val are the arguments of sys_wait), it should :
  • set the wait_slot field of the current process to 1,
  • set the state of the current process to SLEEPING, which makes the process ineligible.
  • call sched() so that xv6 runs another process (xv6 chooses a process in RUNNABLE state and therefore ignore our process),
  • reset wait_slot to 0.
If you look at the code of sched(), you will see that this function considers that the current process must hold table.lock. Magically enough, the sched() function never lets go of the lock! Technically, this function elects a new process, and it is this new process who owns the lock since it is this process that runs and who acquired it before falling asleep.

Test your program and verify that the child never runs again. It's normal since the father never wakes him up.

Implement the sys_fwakefunction. For this you must:
  • acquire the lock table.lock,
  • extract the slot and arg arguments,
  • assign the value val to slots [slot],
  • browse process table (from ptable.proc [0] to ptable.proc[NPROC]) and for each of them, return it in the RUNNABLE state if it is in the SLEEPING state and if its wait_slot variable istrue.
  • release the lock table.lock.
Check that your program now runs as expected.
The solution can be found in the futex branch (git checkout futex). To display all the modifications made to the source code, just display the differences between the current version and previous commits with:
git diff HEAD^^
.

very important question for the future

Compare the code of your functions sys_fwait / sys_fwake with the code of the sleep and wakeup functions found in the same file.

You should notice that these functions generalize the principle of waiting. sleep pause a process while waiting for an event on chan, and wakeup wakes up processes that are waiting for an event on chan. We could therefore have implemented our functions as follows:

struct spinlock my_lock; int sys_wait() { ... acquire(&my_lock); while(slots[slot] != var) sleep(&slots[slot], &my_lock); // waits for a wakeup on &slots[slot] release(&my_lock); } int sys_fwake() { ... wakeup(&slots[slot]); // wake up processes waiting on &slots[slot] }

In order to see the code of the solution, execute the following sequence of instructions in a terminal:

git remote add futex-soluce https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-soluces/xv6-soluce-futex.git git fetch futex-soluce git checkout -b futex-soluce -t futex-soluce/master

And to see only the added code:

git diff origin/master