From 7241838b4cecefb32bad4698e748fc31d008d94d Mon Sep 17 00:00:00 2001 From: Frans Kaashoek Date: Tue, 20 Aug 2019 20:23:18 -0400 Subject: Move labs into 6.828 repo. The lab text isn't dependent on specific xv6 code. Lab submission instructions etc. are likely going to be more MIT 6.828 specific. --- labs/syscall.html | 443 ------------------------------------------------------ 1 file changed, 443 deletions(-) delete mode 100644 labs/syscall.html (limited to 'labs/syscall.html') 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 @@ - - -Lab: Alarm and uthread - - - - -

Lab: Alarm and uthread

- -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 (sigalarm and sigreturn) -and switching between threads in a user-level thread package. - -

Warmup: RISC-V assembly

- -

For this lab it will be important to understand a bit of RISC-V assembly. - -

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. -

-#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();
-}
-

- -

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: - -

Which registers contain arguments to functions? Which - register holds 13 in the call to printf? Which register - holds the second argument? Which register holds the third one? Etc. - -
Where is the function call to f from main? Where - is the call to g? - (Hint: the compiler may inline functions.) - -
At what address is the function printf located? - -
What value is in the register ra just after the jalr - to printf in main? -

- -

Warmup: system call tracing

- -

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. - -

-When you're done, you should see output like this when booting -xv6: - -

-...
-fork -> 2
-exec -> 0
-open -> 3
-close -> 0
-$write -> 1
- write -> 1
-

- -

-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.) - -

Hint: modify the syscall() function in kernel/syscall.c. - -

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? - -

Optional: print the system call arguments. - - -

Alarm

- -

-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. - -

-You should add a new sigalarm(interval, handler) system call. -If an application calls sigalarm(n, fn), then after every -n "ticks" of CPU time that the program consumes, the kernel -should cause application function -fn to be called. When fn 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. - -

-You'll find a file user/alarmtest.c in your xv6 -repository. Add it to the Makefile. It won't compile correctly -until you've added sigalarm and sigreturn -system calls (see below). - -

-alarmtest calls sigalarm(2, periodic) in test0 to -ask the kernel to force a call to periodic() 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, -alarmtest should produce output like this: - -

-$ alarmtest
-test0 start
-......................................alarm!
-test0 passed
-test1 start
-..alarm!
-..alarm!
-..alarm!
-.alarm!
-..alarm!
-..alarm!
-..alarm!
-..alarm!
-..alarm!
-..alarm!
-test1 passed
-$
-

- -

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? - -

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. - -

test0: invoke handler

- -

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: - -

You'll need to modify the Makefile to cause alarmtest.c -to be compiled as an xv6 user program. - -

The right declarations to put in user/user.h are: -

-    int sigalarm(int ticks, void (*handler)());
-    int sigreturn(void);
-

- -

Update user/sys.pl (which generates user/usys.S), - kernel/syscall.h, and kernel/syscall.c - to allow alarmtest to invoke the sigalarm and - sigreturn system calls. - -
For now, your sys_sigreturn should just return zero. - -
Your sys_sigalarm() should store the alarm interval and -the pointer to the handler function in new fields in the proc -structure, defined in kernel/proc.h. - -
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 struct proc for this -too. You can initialize proc fields in allocproc() -in proc.c. - -
Every tick, the hardware clock forces an interrupt, which is handled -in usertrap(); you should add some code here. - -
You only want to manipulate a process's alarm ticks if there's a a - timer interrupt; you want something like -
```
-    if(which_dev == 2) ...
-
```
- -
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, periodic is at - address 0). - -
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 -
```
-    make CPUS=1 qemu
-
```
- -
You've succeeded if alarmtest prints "alarm!". - -

- -

test1(): resume interrupted code

- -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 (periodic in alarmtest.c) returning -to the wrong point in the user program. - -

-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. - -

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 sigreturn 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: -

Have usertrap save enough state in - struct proc when the timer goes off - that sigreturn can correctly return to the - interrupted user code. - -
Prevent re-entrant calls to the handler----if a handler hasn't - returned yet, the kernel shouldn't call it again. -

- -

Once you pass test0 and test1, run usertests to - make sure you didn't break any other parts of the kernel. - -

Uthread: switching between threads

- -

Download uthread.c and uthread_switch.S into your xv6 directory. -Make sure uthread_switch.S ends with .S, not -.s. Add the -following rule to the xv6 Makefile after the _forktest rule: - -

-$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
-

-Make sure that the blank space at the start of each line is a tab, -not spaces. - -

-Add _uthread in the Makefile to the list of user programs defined by UPROGS. - -

Run xv6, then run uthread from the xv6 shell. The xv6 kernel will print an error message about uthread encountering a page fault. - -

Your job is to complete uthread_switch.S, so that you see output similar to -this (make sure to run with CPUS=1): -

-~/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
-$
-

- -

uthread 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. - -

To observe the above output, you need to complete uthread_switch.S, but before -jumping into uthread_switch.S, first understand how uthread.c -uses uthread_switch. uthread.c has two global variables -current_thread and next_thread. Each is a pointer to a -thread structure. The thread structure has a stack for a thread and a -saved stack pointer (sp, which points into the thread's stack). The -job of uthread_switch is to save the current thread state into the -structure pointed to by current_thread, restore next_thread's -state, and make current_thread point to where next_thread was -pointing to, so that when uthread_switch returns next_thread -is running and is the current_thread. - -

You should study thread_create, which sets up the initial stack for -a new thread. It provides hints about what uthread_switch should do. -Note that thread_create simulates saving all callee-save registers -on a new thread's stack. - -

To write the assembly in thread_switch, you need to know how the C -compiler lays out struct thread in memory, which is as -follows: - -

-    --------------------
-    | 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
-

- -The variables &next_thread and ¤t_thread each -contain the address of a pointer to struct thread, and are -passed to thread_switch. The following fragment of assembly -will be useful: - -

-   ld t0, 0(a0)
-   sd sp, 0(t0)
-

- -This saves sp in current_thread->sp. This works because -sp is at -offset 0 in the struct. -You can study the assembly the compiler generates for -uthread.c by looking at uthread.asm. - -

To test your code it might be helpful to single step through your -uthread_switch using riscv64-linux-gnu-gdb. You can get started in this way: - -

-(gdb) file user/_uthread
-Reading symbols from user/_uthread...
-(gdb) b *0x230
-
-

-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". XXX This doesn't work - for me; why? - -

The breakpoint may (or may not) be triggered before you even run -uthread. How could that happen? - -

Once your xv6 shell runs, type "uthread", and gdb will break at -thread_switch. Now you can type commands like the following to inspect -the state of uthread: - -

-  (gdb) p/x *next_thread
-  $1 = {sp = 0x4a28, stack = {0x0 (repeats 8088 times),
-      0x68, 0x1, 0x0 }, state = 0x1}
-

-What address is 0x168, which sits on the bottom of the stack -of next_thread? - -With "x", you can examine the content of a memory location -

-  (gdb) x/x next_thread->sp
-  0x4a28 :      0x00000168
-

-Why does that print 0x168? - -

Optional challenges

- -

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 thread_schedule -concurrently, select the same runnable thread, and both run it on different -processors.) - -

There are several ways of addressing these problems. One is - using scheduler - activations 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. - -

Add locks, condition variables, barriers, -etc. to your thread package. - - - - -- cgit v1.2.3