Due by Monday, October 29.
The managing TA for all Xen/Linux track assignments is Hemayet Hossain. All email inquiries about this assignment should be addressed to the TA and cc the instructor. This assignment will be examined through demo with the TA. Please schedule a demo time with the TA by Monday, October 29 or earlier. We expect each demo will take around 30 minutes. Please reserve your time slot with the TA ahead of time.
This is a group assignment.
Disclaimer: This assignment is adapted from a project developed by Dr. Jason Nieh at Columbia University.
In this part of the assignment, you will work on synchronization and threads in userspace. For this part, you do not need the Xen virtual machine. In other words, you DO NOT have to develop the solution inside a Xen domain.
In this problem you will add synchronization functionality to the
implementation of SThreads, a simple threading library. Get
the source files here.
The files provide the source, header, and Makefile for the SThreads
library. The functions and datatypes are declared in the file
sthread.h. The library is used as follows:
sthread_t.
Consider sthread_t to be an opaque data type (i.e., only
functions in sthread.c get to know what it really is).sthread_init() must be called exactly once, as the first
thing in main(). It returns 0 normally, and -1 on error.
int sthread_create(sthread_t *t, sthread_main_t main, void *arg).
sthread_t object is returned.
The second is the function the new thread should run. The third argument
is passed to this function. sthread_create() returns 0
normally and -1 on error.sthread_self(), which returns
the sthread_t associated with the currently running thread,
as well as sthread_suspend(), which puts the currently
running thread to sleep, and sthread_wake(sthread_t t),
which wakes up a thread, given the thread's sthread_t object.
Note that for the SThreads library, first waking up a running thread and
then suspending it leaves the thread in a running state.
You are also provided with the function test_and_set(int *x),
which atomically sets the integer that x points to to 1, and returns
its original value. Using sthread_suspend(),
sthread_wake(), and test_and_set(), you are
to implement the missing locking primitives in the SThreads library.
You may use test_and_set() to implement spinlocks, in
which you repeatedly call test_and_set() and a no-op in
a tight loop, waiting for the test result to be 0. Note that you can
use spinlocks to synchronize access on your locks' shared data
structures, but not to implement the locks themselves. In other
words, if I call sthread_mutex_lock() on an unavailable
mutex, I should suspend rather than spinning until the lock is released.
Now comes the fun part. For this assignment, implement mutex locks in
the SThreads library. Put your function implementations in a single
file, called sync.c, and your structure definitions in
sync.h. Skeleton files are provided, but you may have to
add functions and datatypes to these files. You shouldn't have to
change sthread.c or sthread.h. Unless
otherwise noted, all functions should return 0 on success and -1 on error.
The prototypes for the five functions you must implement are found in
sync.h, and are all named sthread_mutex_*.
You must define struct sthread_mutex_struct.
sthread_mutex_init() and sthread_mutex_destroy()
should be used to initialize and free resources related to this structure.
Either or both may be no-ops if your implementation requires no
initialization and/or cleanup. sthread_mutex_lock()
should obtain the lock, if it is available, or else the current thread
should block until the lock is available.
sthread_mutex_unlock() should make the lock available. It
should be an error for any thread other than the owner of the lock to
call this. sthread_mutex_trylock() should obtain the lock
and return 0, if the lock is available, or else return non-zero
immediately. This function does not cause the caller to block.
Your implementation should be recursive, i.e., if the owner of a lock
tries to get the same lock, it should not deadlock, but just require
another call to sthread_mutex_unlock() to fully unlock the
mutex. Note that this is not how all mutex implementations work --
many will simply deadlock if the holder of a lock attempts to get it
again. The Linux pthread implementation has both standard and recursive
mutexes: see the pthread_mutex_init(1) man page for details.
Your implementation should not allow starvation of any thread waiting for the mutex. That is, if two threads are repeatedly locking and unlocking a mutex, that should not prevent a third thread from eventually getting the lock. (Of course, if one thread never unlocks the mutex, the others will starve, but that's a programming error, i.e., not your problem!)
For this part of the assignment, you will implement a new kernel synchronization primitive. It may be helpful to read some references. One example is the "Sleeping and Waking Up" section in chapter 4 in the Linux Kernel Development book by Robert Love. Note that the kernel calls its semaphore operations down and up instead of P and V, but the operations are the same. Note that unlike the userspace mutexes you implemented for the first part of this assignment, the synchronization primitives in Linux generally do not have owners and are not recursive. No owners means that there's nothing stopping any piece of code from unlocking every lock in the kernel (and bringing the kernel to a fiery screeching halt, probably). Not recursive means that the owner of a lock (even if there was such a thing) can't obtain the lock twice.
You are asked to design and implement a new kernel synchronization primitive that will allow multiple processes to block on an event until some other process signals the event. When a process signals the event, all processes that are blocked on the event are unblocked. If no processes are blocked on an event when it is signaled, then the signal has no effect. Implement the following new system calls in the Linux kernel, respectively. Chapter 5 of the Linux Kernel Development book gives detailed instructions on building a system call. You might also be able to find online help on this as well.
int doeventopen();
Creates a new event, returning event ID on success, -1 on failure.int doeventclose(int eventID);
Destroy the event with the given event ID and signal any processes
waiting on the event to leave the event. Return number of processes
signaled on success and -1 on failure.int doeventwait(int eventID);
Blocks process until the event is signaled. Return 1 on success and
-1 on failure.int doeventsig(int eventID);
Unblocks all waiting processes; ignored if no processes are
blocked. Return number of processes signaled on success and -1 on
failure.
You are designing a completely new facility to add to the kernel. You
will need to create a new implementation file and change the Makefile
so that it compiles your new file. You are also likely to need to
change a few parts of the existing kernel, such as the initialization
code. To do this, you should write a new doevent_init()
function that can be called when the system is booted. You will need
to change the system initialization code to call this new function.
You should begin by thinking carefully about the data structures that
you will need to solve this problem. Your system will need to support
having multiple events open at the same time, so you will probably
need a set of event descriptor data structures, each of which
identifies an event. Those data structures will need to be put in a
list from which your code can find the appropriate event descriptor
corresponding to the event that you need. Space for the event
descriptors should be dynamically allocated, most likely using the
kernel functions kmalloc() and kfree().
You can choose to work at the level of wait queues and the associated
low-level routines such as add_wait_queue(), etc.
Alternatively, you may find it easier to work with kernel functions
such as interruptible_sleep_on(),
sleep_on(), and wake_up(),
wake_up_interruptible(). Be sure to properly synchronize
access to your data structures. You should not make any assumptions
about whether the system is a uniprocessor or multiprocessor system.
You are also asked to write a user-level program to test your new kernel functions. Your test program should show that the kernel functions work for the usual cases, for example, with one process waiting, and also for boundary conditions such as
doeventsig() is called,doeventsig() is called,doeventclose() is called.
A Linux kernel reference book would be very helpful. For instance,
Chapter 5 of the Linux Kernel Development book gives detailed
instructions on building a system call. You might also be able to
find online help on this.
In order to learn about system calls, you may also find it helpful to
search the Linux kernel for other system calls and see how they are
defined. The file kernel/timer.c might give some useful
examples of this. The getpid system call might be a useful
starting point. The system call sys_getpid defined in
kernel/timer.c uses current and provides a good
reference point for defining your system call.
Important Note:
When adding a system call, you need to register it in the system call
table in entry.S for your architecture. For i386, you might
find two such files arch/i386/kernel/entry.S and
arch/xen/i386/kernel/entry.S. Although a regular kernel
(not customized for Xen) only has the former file, in this case you have
to work on the latter. You might also find it is readonly by default.
Go ahead and make it writable.
Make sure the path values for "kernel" and "disk" are properly set in the xen.config file. Usually, the kernel image (kernelU) is built in /home/team?/kernel/kernelU.
Debugging the kernel can be extremely frustrating. It is good to build up some
debugging experience. You can use printk to print
information from inside the kernel. To request the printk messages
be sent to a log file, insert the following line into the
/etc/syslog.conf file:
kern.* /var/log/kern.logThis will cause
printk messages to be written to
/var/log/kern.log after the next reboot.
There are also a few kernel debuggers out there. We haven't had much
luck with any of them. If you manage to get any of them working, please
let us know.
Have fun hacking!!!
The user space portion will constitute 30% of the grade while the kernel portion will constitute 70%.