diff options
Diffstat (limited to 'labs/syscall.html')
| -rw-r--r-- | labs/syscall.html | 443 |
1 files changed, 0 insertions, 443 deletions
diff --git a/labs/syscall.html b/labs/syscall.html deleted file mode 100644 index 2281f2e..0000000 --- a/labs/syscall.html +++ /dev/null @@ -1,443 +0,0 @@ -<html> -<head> -<title>Lab: Alarm and uthread</title> -<link rel="stylesheet" href="homework.css" type="text/css" /> -</head> -<body> - -<h1>Lab: Alarm and uthread</h1> - -This lab will familiarize you with the implementation of system calls -and switching between threads of execution. In particular, you will -implement new system calls (<tt>sigalarm</tt> and <tt>sigreturn</tt>) -and switching between threads in a user-level thread package. - -<h2>Warmup: RISC-V assembly</h2> - -<p>For this lab it will be important to understand a bit of RISC-V assembly. - -<p>Add a file user/call.c with the following content, modify the - Makefile to add the program to the user programs, and compile (make - fs.img). The Makefile also produces a binary and a readable - assembly a version of the program in the file user/call.asm. -<pre> -#include "kernel/param.h" -#include "kernel/types.h" -#include "kernel/stat.h" -#include "user/user.h" - -int g(int x) { - return x+3; -} - -int f(int x) { - return g(x); -} - -void main(void) { - printf(1, "%d %d\n", f(8)+1, 13); - exit(); -} -</pre> - -<p>Read through user/call.asm and understand it. The instruction manual - for RISC-V is in the doc directory (doc/riscv-spec-v2.2.pdf). Here - are some questions that you should answer for yourself: - - <ul> - <li>Which registers contain arguments to functions? Which - register holds 13 in the call to <tt>printf</tt>? Which register - holds the second argument? Which register holds the third one? Etc. - - <li>Where is the function call to <tt>f</tt> from main? Where - is the call to <tt>g</tt>? - (Hint: the compiler may inline functions.) - - <li>At what address is the function <tt>printf</tt> located? - - <li>What value is in the register <tt>ra</tt> just after the <tt>jalr</tt> - to <tt>printf</tt> in <tt>main</tt>? - </ul> - -<h2>Warmup: system call tracing</h2> - -<p>In this exercise you will modify the xv6 kernel to print out a line -for each system call invocation. It is enough to print the name of the -system call and the return value; you don't need to print the system -call arguments. - -<p> -When you're done, you should see output like this when booting -xv6: - -<pre> -... -fork -> 2 -exec -> 0 -open -> 3 -close -> 0 -$write -> 1 - write -> 1 -</pre> - -<p> -That's init forking and execing sh, sh making sure only two file descriptors are -open, and sh writing the $ prompt. (Note: the output of the shell and the -system call trace are intermixed, because the shell uses the write syscall to -print its output.) - -<p> Hint: modify the syscall() function in kernel/syscall.c. - -<p>Run the xv6 programs you wrote in earlier labs and inspect the system call - trace. Are there many system calls? Which system calls correspond - to code in the applications you wrote? - -<p>Optional: print the system call arguments. - - -<h2>Alarm</h2> - -<p> -In this exercise you'll add a feature to xv6 that periodically alerts -a process as it uses CPU time. This might be useful for compute-bound -processes that want to limit how much CPU time they chew up, or for -processes that want to compute but also want to take some periodic -action. More generally, you'll be implementing a primitive form of -user-level interrupt/fault handlers; you could use something similar -to handle page faults in the application, for example. - -<p> -You should add a new <tt>sigalarm(interval, handler)</tt> system call. -If an application calls <tt>sigalarm(n, fn)</tt>, then after every -<tt>n</tt> "ticks" of CPU time that the program consumes, the kernel -should cause application function -<tt>fn</tt> to be called. When <tt>fn</tt> returns, the application -should resume where it left off. A tick is a fairly arbitrary unit of -time in xv6, determined by how often a hardware timer generates -interrupts. - -<p> -You'll find a file <tt>user/alarmtest.c</tt> in your xv6 -repository. Add it to the Makefile. It won't compile correctly -until you've added <tt>sigalarm</tt> and <tt>sigreturn</tt> -system calls (see below). - -<p> -<tt>alarmtest</tt> calls <tt>sigalarm(2, periodic)</tt> in <tt>test0</tt> to -ask the kernel to force a call to <tt>periodic()</tt> every 2 ticks, -and then spins for a while. -You can see the assembly -code for alarmtest in user/alarmtest.asm, which may be handy -for debugging. -When you've finished the lab, -<tt>alarmtest</tt> should produce output like this: - -<pre> -$ alarmtest -test0 start -......................................alarm! -test0 passed -test1 start -..alarm! -..alarm! -..alarm! -.alarm! -..alarm! -..alarm! -..alarm! -..alarm! -..alarm! -..alarm! -test1 passed -$ -</pre> - -<p>The main challenge will be to arrange that the handler is invoked - when the process's alarm interval expires. You'll need to modify - usertrap() in kernel/trap.c so that when a - process's alarm interval expires, the process executes - the handler. How can you do that? You will need to understand - how system calls work (i.e., the code in kernel/trampoline.S - and kernel/trap.c). Which register contains the address to which - system calls return? - -<p>Your solution will be only a few lines of code, but it may be tricky to - get it right. -We'll test your code with the version of alarmtest.c in the original -repository; if you modify alarmtest.c, make sure your kernel changes -cause the original alarmtest to pass the tests. - -<h3>test0: invoke handler</h3> - -<p>Get started by modifying the kernel to jump to the alarm handler in -user space, which will cause test0 to print "alarm!". Don't worry yet -what happens after the "alarm!" output; it's OK for now if your -program crashes after printing "alarm!". Here are some hints: - -<ul> - -<li>You'll need to modify the Makefile to cause <tt>alarmtest.c</tt> -to be compiled as an xv6 user program. - -<li>The right declarations to put in <tt>user/user.h</tt> are: -<pre> - int sigalarm(int ticks, void (*handler)()); - int sigreturn(void); -</pre> - -<li>Update user/sys.pl (which generates user/usys.S), - kernel/syscall.h, and kernel/syscall.c - to allow <tt>alarmtest</tt> to invoke the sigalarm and - sigreturn system calls. - -<li>For now, your <tt>sys_sigreturn</tt> should just return zero. - -<li>Your <tt>sys_sigalarm()</tt> should store the alarm interval and -the pointer to the handler function in new fields in the <tt>proc</tt> -structure, defined in <tt>kernel/proc.h</tt>. - -<li>You'll need to keep track of how many ticks have passed since the -last call (or are left until the next call) to a process's alarm -handler; you'll need a new field in <tt>struct proc</tt> for this -too. You can initialize <tt>proc</tt> fields in <tt>allocproc()</tt> -in <tt>proc.c</tt>. - -<li>Every tick, the hardware clock forces an interrupt, which is handled -in <tt>usertrap()</tt>; you should add some code here. - -<li>You only want to manipulate a process's alarm ticks if there's a a - timer interrupt; you want something like -<pre> - if(which_dev == 2) ... -</pre> - -<li>Only invoke the alarm function if the process has a - timer outstanding. Note that the address of the user's alarm - function might be 0 (e.g., in alarmtest.asm, <tt>periodic</tt> is at - address 0). - -<li>It will be easier to look at traps with gdb if you tell qemu to -use only one CPU, which you can do by running -<pre> - make CPUS=1 qemu -</pre> - -<li>You've succeeded if alarmtest prints "alarm!". - -</ul> - -<h3>test1(): resume interrupted code</h3> - -Chances are that alarmtest crashes at some point after it prints -"alarm!". Depending on how your solution works, that point may be in -test0, or it may be in test1. Crashes are likely caused -by the alarm handler (<tt>periodic</tt> in alarmtest.c) returning -to the wrong point in the user program. - -<p> -Your job now is to ensure that, when the alarm handler is done, -control returns to -the instruction at which the user program was originally -interrupted by the timer interrupt. You must also ensure that -the register contents are restored to values they held -at the time of the interrupt, so that the user program -can continue undisturbed after the alarm. - -<p>Your solution is likely to require you to save and restore - registers---what registers do you need to save and restore to resume - the interrupted code correctly? (Hint: it will be many). - Several approaches are possible; for this lab you should make - the <tt>sigreturn</tt> system call - restore registers and return to the original - interrupted user instruction. - The user-space alarm handler - calls sigreturn when it is done. - - Some hints: - <ul> - <li>Have <tt>usertrap</tt> save enough state in - <tt>struct proc</tt> when the timer goes off - that <tt>sigreturn</tt> can correctly return to the - interrupted user code. - - <li>Prevent re-entrant calls to the handler----if a handler hasn't - returned yet, the kernel shouldn't call it again. - </ul> - -<p>Once you pass <tt>test0</tt> and <tt>test1</tt>, run usertests to - make sure you didn't break any other parts of the kernel. - -<h2>Uthread: switching between threads</h2> - -<p>Download <a href="uthread.c">uthread.c</a> and <a - href="uthread_switch.S">uthread_switch.S</a> into your xv6 directory. -Make sure <tt>uthread_switch.S</tt> ends with <tt>.S</tt>, not -<tt>.s</tt>. Add the -following rule to the xv6 Makefile after the _forktest rule: - -<pre> -$U/_uthread: $U/uthread.o $U/uthread_switch.o - $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $U/_uthread $U/uthread.o $U/uthread_switch.o $(ULIB) - $(OBJDUMP) -S $U/_uthread > $U/uthread.asm -</pre> -Make sure that the blank space at the start of each line is a tab, -not spaces. - -<p> -Add <tt>_uthread</tt> in the Makefile to the list of user programs defined by UPROGS. - -<p>Run xv6, then run <tt>uthread</tt> from the xv6 shell. The xv6 kernel will print an error message about <tt>uthread</tt> encountering a page fault. - -<p>Your job is to complete <tt>uthread_switch.S</tt>, so that you see output similar to -this (make sure to run with CPUS=1): -<pre> -~/classes/6828/xv6$ make CPUS=1 qemu -... -$ uthread -my thread running -my thread 0x0000000000002A30 -my thread running -my thread 0x0000000000004A40 -my thread 0x0000000000002A30 -my thread 0x0000000000004A40 -my thread 0x0000000000002A30 -my thread 0x0000000000004A40 -my thread 0x0000000000002A30 -my thread 0x0000000000004A40 -my thread 0x0000000000002A30 -... -my thread 0x0000000000002A88 -my thread 0x0000000000004A98 -my thread: exit -my thread: exit -thread_schedule: no runnable threads -$ -</pre> - -<p><tt>uthread</tt> creates two threads and switches back and forth between -them. Each thread prints "my thread ..." and then yields to give the other -thread a chance to run. - -<p>To observe the above output, you need to complete <tt>uthread_switch.S</tt>, but before -jumping into <tt>uthread_switch.S</tt>, first understand how <tt>uthread.c</tt> -uses <tt>uthread_switch</tt>. <tt>uthread.c</tt> has two global variables -<tt>current_thread</tt> and <tt>next_thread</tt>. Each is a pointer to a -<tt>thread</tt> structure. The thread structure has a stack for a thread and a -saved stack pointer (<tt>sp</tt>, which points into the thread's stack). The -job of <tt>uthread_switch</tt> is to save the current thread state into the -structure pointed to by <tt>current_thread</tt>, restore <tt>next_thread</tt>'s -state, and make <tt>current_thread</tt> point to where <tt>next_thread</tt> was -pointing to, so that when <tt>uthread_switch</tt> returns <tt>next_thread</tt> -is running and is the <tt>current_thread</tt>. - -<p>You should study <tt>thread_create</tt>, which sets up the initial stack for -a new thread. It provides hints about what <tt>uthread_switch</tt> should do. -Note that <tt>thread_create</tt> simulates saving all callee-save registers -on a new thread's stack. - -<p>To write the assembly in <tt>thread_switch</tt>, you need to know how the C -compiler lays out <tt>struct thread</tt> in memory, which is as -follows: - -<pre> - -------------------- - | 4 bytes for state| - -------------------- - | stack size bytes | - | for stack | - -------------------- - | 8 bytes for sp | - -------------------- <--- current_thread - ...... - - ...... - -------------------- - | 4 bytes for state| - -------------------- - | stack size bytes | - | for stack | - -------------------- - | 8 bytes for sp | - -------------------- <--- next_thread -</pre> - -The variables <tt>&next_thread</tt> and <tt>¤t_thread</tt> each -contain the address of a pointer to <tt>struct thread</tt>, and are -passed to <tt>thread_switch</tt>. The following fragment of assembly -will be useful: - -<pre> - ld t0, 0(a0) - sd sp, 0(t0) -</pre> - -This saves <tt>sp</tt> in <tt>current_thread->sp</tt>. This works because -<tt>sp</tt> is at -offset 0 in the struct. -You can study the assembly the compiler generates for -<tt>uthread.c</tt> by looking at <tt>uthread.asm</tt>. - -<p>To test your code it might be helpful to single step through your -<tt>uthread_switch</tt> using <tt>riscv64-linux-gnu-gdb</tt>. You can get started in this way: - -<pre> -(gdb) file user/_uthread -Reading symbols from user/_uthread... -(gdb) b *0x230 - -</pre> -0x230 is the address of uthread_switch (see uthread.asm). When you -compile it may be at a different address, so check uthread_asm. -You may also be able to type "b uthread_switch". <b>XXX This doesn't work - for me; why?</b> - -<p>The breakpoint may (or may not) be triggered before you even run -<tt>uthread</tt>. How could that happen? - -<p>Once your xv6 shell runs, type "uthread", and gdb will break at -<tt>thread_switch</tt>. Now you can type commands like the following to inspect -the state of <tt>uthread</tt>: - -<pre> - (gdb) p/x *next_thread - $1 = {sp = 0x4a28, stack = {0x0 (repeats 8088 times), - 0x68, 0x1, 0x0 <repeats 102 times>}, state = 0x1} -</pre> -What address is <tt>0x168</tt>, which sits on the bottom of the stack -of <tt>next_thread</tt>? - -With "x", you can examine the content of a memory location -<pre> - (gdb) x/x next_thread->sp - 0x4a28 <all_thread+16304>: 0x00000168 -</pre> -Why does that print <tt>0x168</tt>? - -<h3>Optional challenges</h3> - -<p>The user-level thread package interacts badly with the operating system in -several ways. For example, if one user-level thread blocks in a system call, -another user-level thread won't run, because the user-level threads scheduler -doesn't know that one of its threads has been descheduled by the xv6 scheduler. As -another example, two user-level threads will not run concurrently on different -cores, because the xv6 scheduler isn't aware that there are multiple -threads that could run in parallel. Note that if two user-level threads were to -run truly in parallel, this implementation won't work because of several races -(e.g., two threads on different processors could call <tt>thread_schedule</tt> -concurrently, select the same runnable thread, and both run it on different -processors.) - -<p>There are several ways of addressing these problems. One is - using <a href="http://en.wikipedia.org/wiki/Scheduler_activations">scheduler - activations</a> and another is to use one kernel thread per - user-level thread (as Linux kernels do). Implement one of these ways - in xv6. This is not easy to get right; for example, you will need to - implement TLB shootdown when updating a page table for a - multithreaded user process. - -<p>Add locks, condition variables, barriers, -etc. to your thread package. - -</body> -</html> - |