Lab 2

Quick links: Useful kernel functions / Getting kernel source

In Lab 2, you'll get your hands dirty inside the Linux kernel!

You will write a kernel module -- code that can be dynamically downloaded into the kernel -- that implements a ramdisk: an in-memory block device. (A block device is basically a device that acts like a disk.)

Your ramdisk will support the usual read and write operations. You can read and write the ramdisk by reading and writing a file, for instance one named /dev/osprda. (In fact, you could also initialize your ramdisk to contain a Linux file system!) After one process writes to the disk, another process can read out the results. Your ramdisk will also support a special locking feature, where a process can gain exclusive access to the ramdisk. This, of course, leads to some interesting synchronization issues! The locking feature is implemented using ioctl system calls, which are eventually processed by your ramdisk block device code.

Like most device drivers, your module can support several of these devices simultaneously; in particular, it supports four simultaneous ramdisks.

This lab has a handful of purposes, including:

• To introduce you to kernel programming.
• To give you experience in writing a device driver for a real operating system. (Although you don't have to implement any interaction with real hardware controllers.)
• To give you some interesting synchronization problems to handle.

This lab requires that you use a Linux machine; additionally, you must have the necessary permission to load kernel modules on that machine. The Linux lab machines in 4405 Boelter have been set up for this, but you can also use your own machine.

The skeleton code you will get for this lab consists of:

• a Makefile
• two module source files (osprd.c and osprd.h)
• the source code for a utility to execute a command with a locked ramdisk (osprdlock.c)
• two scripts for issuing reads and writes to your device (sector_read and sector_write)
• a header file implementing the instrumented locking code described below (spinlock.h)
• a script (create_devs) which will come in handy for creating the special files in /dev used to access your devices

We have already created the special files for your devices on the lab machines, so you will only need create_devs if you are using your own machine. When you extract lab2.tar.gz you will get a directory lab2 which contains these files. Since you will be using Linux for this lab, the command tar xvzf lab2.tar.gz will suffice to extract the archive.

Writing kernel code is actually not as scary as it sounds. The Linux kernel is a very large piece of software, but you only have to use a subset for your module. Remember that the kernel is providing the abstractions we usually take for granted in userspace, so often it cannot take advantage of them itself (sort of a chicken-and-egg thing). We will try to list a few of the most important things for this lab here.

Each process in Linux has its own kernel stack, which means that while the kernel is executing on behalf of that process, it uses a stack which is specific to that process. This is convenient, because we can do things like invoke the scheduler from this stack, and the scheduler will "return" to the same place on that process' kernel stack next time the process is scheduled. Additionally, many recent Linux kernels are preemptible which means that just like threaded user code, code in the kernel has to worry about race conditions. Therefore, it is very important in the kernel to use proper synchronization mechanisms like locks to avoid unpredictable behavior and deadlocks. It's not just one process that might get stuck as the result of a bug -- the whole system can crash!

While the lab machines in 4405 Boelter do not have preemptible kernels, kernel modules still need to handle these synchronization issues so that they will work correctly when used with a preemptible kernel. In the lab skeleton code, we have instrumented the kernel's locks to help you detect incorrect lock usage even on non-preemptible kernels where ordinarily incorrect use of the locks does not cause problems. This may be easier than testing using a preemptible kernel, where incorrect locking often deadlocks the kernel (making the whole machine lock up). However, you won't be able to detect missing locks (though that's hard even with a preemptible kernel), so you'll have to think carefully about where they will be necessary.

Memory protection is also not the same as it is in userspace. In userspace, if you follow a bad pointer, your program may be killed, but that's about it. In the kernel, the kernel itself will likely crash. This is obviously a bad thing. Even worse, userspace programs can pass invalid pointers into the kernel through system calls. If the kernel dereferences such a pointer, the machine is in trouble! To help the kernel protect itself against such abuses, there are special kernel functions for dealing with userspace-supplied pointers in a safe way. You won't need to worry about these functions for this lab, but they will become important in Lab 3. You will find them, and other useful kernel functions, documented here.

Another important thing to keep in mind is that you can't call system calls like open, read, or write from inside the kernel. You are implementing these functions for your block device, so calling them would likely cause an infinite loop (and also the kernel just won't let you). Similarly, you can't call internal kernel functions like send_sig from userspace.

To complete the lab you need to complete all EXERCISE sections in osprd.c. This section of the lab manual gives an overview of the exercises and related background knowledge.

Your ramdisk will be a block device, meaning it will implement the Linux block device interface. A block device is, basically, a device that acts like a disk. Concretely:

• Block devices store data. They support read and write operations.
• That data is stored in fixed-size units, called sectors, which the system can access in any order.

Even though the ramdisk could be more flexible, it conforms to the block device interface so that it can be used everywhere a physical block device can be used. The Linux block device interface also includes an ioctl function to perform special per-device operations. You will use the ioctl interface to implement the locking features of your block device.

We suggest you first implement read and write support in your block device. This is the osprd_process_request function. When you're done, you'll be able to read and write data from each ramdisk by reading and writing the /dev/osprdX files! To make this easier, we've provided read and write shell scripts that write sectors on your block device and then read back the data you wrote. (You can also use dd, the program the shell scripts use, directly; look into the seek and skip arguments in the manual page for dd.)

Next, you will implement support for the locking function, where a user can obtain exclusive access to a ramdisk. We've designed the interface as follows:

• To lock a ramdisk, a process calls ioctl(fd, OSPRDIOCLOCK);, where fd is a ramdisk file. (ioctl is a system call for specialized file functions that don't fit any other category.)
  • The ioctl function should block until there are no other open files to that ramdisk. Then it should claim the ramdisk lock. (However, if the process gets a signal while it is blocked, then ioctl should return -EINTR, which indicates that the system call was interrupted by a signal.)
  • Once it has the ramdisk lock, then any other attempt to open the ramdisk file should block until the ramdisk is unlocked. (Again, if the process gets a signal while it is blocked, then open should return -EINTR.)
• To unlock a ramdisk, a process calls ioctl(fd, OSPRDIOCUNLOCK);. Closing a locked ramdisk file should transparently unlock the ramdisk as well.
  • All ramdisk-blocked processes should wake up when a ramdisk is unlocked.

To implement these semantics, you will need to maintain a wait queue per ramdisk, and also keep track of how many files are open for a given ramdisk.

We have written a helper program that you can use to check out locking semantics. Its name is osprdlock. It opens a ramdisk file, locks it, then runs a command with that ramdisk file as standard input. When the command is done, osprdlock unlocks the ramdisk file. Here are some examples of desired behavior.

 % ./sector_read
 1+0 records in
 1+0 records out
 512 bytes (512 B) copied, 0.000105 seconds, 4.9 MB/s
 00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 *
 00000200
 % ./sector_write osprd.c
 1+0 records in
 1+0 records out
 512 bytes (512 B) copied, 0.000214 seconds, 2.4 MB/s
 % ./sector_read
 .......
 00000000  23 69 6e 63 6c 75 64 65  20 3c 6c 69 6e 75 78 2f  |#include <linux/|
 00000010  76 65 72 73 69 6f 6e 2e  68 3e 0a 23 69 6e 63 6c  |version.h>.#incl|
 .......

    # Now, we lock the ramdisk for 5 seconds, but after 1sec, attempt to read it.
    # The read should be blocked until the lock is complete.
    # Note the use of "&", for backgrounding, to run 2 commands in parallel.
 % ./osprdlock "sleep 5" & ( sleep 1 ; ./sector_read )
 [3] ..process number..
 [[[[ 5 SECOND PAUSE ]]]]
 .......
 00000000  23 69 6e 63 6c 75 64 65  20 3c 6c 69 6e 75 78 2f  |#include <linux/|
 00000010  76 65 72 73 69 6f 6e 2e  68 3e 0a 23 69 6e 63 6c  |version.h>.#incl|
 .......

    # This time we keep an unlocked ramdisk open for 5 seconds, but after 1sec,
    # attempt to lock it.  (The "-n" argument says don't try to lock the ramdisk.)
 % ./osprdlock -n "sleep 5" & ( sleep 1 ; ./osprdlock "echo Got lock" )
 [3] ..process number..
 [[[[ 5 SECOND PAUSE ]]]]
 Got lock

    # Print the first line in the ramdisk
 % head -1 /dev/osprda
 #include <linux/version.h>

    # Doesn't work when it's locked, since that would cause deadlock!  (opening
    # the ramdisk again)
 % ./osprdlock "head -1 /dev/osprda"
 head: cannot open `/dev/osprda' for reading: Resource deadlock avoided

    # But can use the version of /dev/osprda on standard input, since that has
    # already been opened.  (Similarly, "./sector_read -" would work.)
 % ./osprdlock "head -1 -"
 #include <linux/version.h>

First, keep track of each ramdisk's number of open files, using the ramdisk info structure (osprd_info_t) nopen member. Change the osprd_open and osprd_release functions to do this.

Make sure you protect any access to shared state with the osprd_info_t's mutex member. This is a spin lock, or polling mutex. Remember that it is illegal in Linux for a process to lock a spin lock, and then block! (This is because another thread could then attempt to lock the spin lock, and spin forever.) You will have to arrange your code in later steps so that you always release the spin lock before blocking and re-acquire it afterwards.

Next, implement the OSPRDIOCLOCK ioctl call to lock the ramdisk. Instructions are included in the skeleton code.

Signals are a tricky aspect of this ioctl interface. Remember that signals are a way to send a running process asynchronous events, or to kill a running process. If the process is blocked in the kernel -- for instance, if it is blocked in osprd_ioctl -- then the kernel must wake up so the process can process the signal. Since we want to kill blocked processes, they had better be able to handle signals. This means:

• When blocked, you should put processes into an interruptible wait. This means that signal delivery takes place as usual. (In an uninterruptable wait, you would not be able to kill a waiting processes except by causing the event it was waiting for -- and this would, in turn, prevent your module from being unloaded because it is currently blocked by code in your module. You'd have to reboot a lot!) Putting a process into interruptible wait is a two-step process: you prepare to wait (prepare_to_wait), then you schedule (schedule). The schedule function blocks the current process, which will not run again until much later, when the process wakes up.
• When your process receives a signal, it will wake up (the schedule function will return). You should use the signal_pending function to check whether a signal has occurred. If so, osprd_ioctl should immediately return to its caller. (See the comments to tell which return value.)

Notice that at this point, signals will be the only way to wake up waiting processes, because no code exists that will actually let them know when there have been writes to the block device yet.

Next, implement code in osprd_ioctl to unlock the lock, on the OSPRDIOCUNLOCK ioctl.

At this point, you should be able to test the following case, in which one locking process is blocked on the other:

 % ./osprdlock "sleep 5" & (sleep 1 ; ./osprdlock "echo a")
 [[[[ AFTER 5 SECONDS ]]]]
 a

Then, implement code for blocking and for unlocking in osprd_open and osprd_release, and test your code using test cases like those above (AND OTHERS you come up with yourself).

So far, so good! But there's a problem in store: There are at least three cases where a file operation might cause a known deadlock. That is, a process would be effectively waiting for itself -- and thus would never wake up. Your job is to detect these deadlocks. Instead of blocking forever (or until a signal), your code should return -EDEADLK, a special error code that indicates a deadlock was avoided.

We aren't going to describe these deadlock conditions precisely, although there are a couple hints scattered in the lab manual and the code -- including these:

• You may find the for_all_files helper function useful (definition here). This function calls a little callback function you supply, once for each open file in a given process.
• We added 2 members to the osprd_info_t type in our solution.

On the lab machines in 4405 Boelter, we have already installed the Linux kernel source code necessary for building kernel modules for the revision of the kernel they are running. Therefore, all you have to do to compile your code into a loadable kernel module (a .ko file) is run make. However, if you are using your own machine, you may need to get the kernel source code first. Try compiling the skeleton module; if it does not work, go here for instructions on how to download and install the kernel source code.

Ordinarily, loading or unloading Linux kernel modules requires that you be the administrator (the root user). If you are using your own machine, you can just change to the root user with su. On the lab machines, you are not allowed to do this, so we have set up a special mechanism for you to execute the commands needed to load and unload modules.

After changing to the root user, you can use the insmod program to load .ko files: just run insmod with the name of the .ko file to load as an argument. The name of the module is the part before the .ko, thus, for this lab, the module will be named osprd and the module file will be osprd.ko. To unload a module, use the rmmod command with the name of the module as an argument. Note that when you try to load a module, if there is already a module by the same name loaded, it will fail -- so you will have to unload it first.

To do this on the lab machines, there is a program called sudo which allows you to run specific programs as root (as specified by the system administrator). We have set up sudo to let you run insmod and rmmod, though because sudo is a little paranoid you have to specify the full path to the commands. Here are the commands you should use:

$ sudo /root/fixMachine
[[You only need to do this command once per session, and you may not
need to do it at all -- but if you see a funny error, try this.]]

$ sudo /sbin/insmod osprd.ko
$ sudo /sbin/rmmod osprd

For security reasons, sudo will ask you to type your password before it will execute the commands. However, for convenience, if you have used sudo within the last 10 minutes, it will not bother to ask you for your password again. The first time you run sudo, it will display a short message about talking to the administrator about local security policies.

Once your module is loaded, it becomes a part of the currently executing kernel. Your code executes as part of the kernel, and can easily crash the machine if you dereference bad pointers or do other things that would only kill your process in userspace. Save your files and run sync before you load your module to avoid losing your work! Even after unloading your module, there may be residual effects of its having been loaded if there were serious bugs in it, so you should save your work frequently.

Messages you print with printk or eprintk from your module may not be shown on the screen by default, which can make debugging a little difficult. If you find that this is the case, you can get a list of the messages by running the dmesg program. On the lab machines, you may need to run it via sudo as described above for insmod and rmmod; if so, you may also need to specify its full path: /bin/dmesg. We found that eprintk messages were actually sent to all open terminals on the lab machines, so you may want to use printk and dmesg instead.

On the lab machines, and on any other machines with non-preemptible kernels, you will see some lock debugging information by using dmesg as well. On machines running preemptible kernels, the system will probably lock up instead of giving any debugging information. This is because the locks aren't really necessary on non-preemptible kernels, so we've replaced them with special debugging versions that detect deadlocks for you (but don't actually lock, which is why the machine doesn't lock up). On a preemptible kernel, the locks are actually needed, so we can't replace them like this. (But don't think the synchronization exercises aren't necessary - even on a non-preemptible kernel, there is still a real race condition that you will need to fix during the lab.)

After loading your module, you'll probably want to try using it. To do this, you will have to access the block special files in /dev which represent the devices it controls. If you are using your own machine, these files may not exist yet (depending on a variety of things). Look in /dev to see if you have files named osprda, osprdb, osprdc, and osprdd. If so, you're all set. If not, run the create_devs script as root to create them.

These files are not like other files in your filesystem. They do not actually contain any data; they just "represent" the devices your driver controls. The only reason they are there is so programs can call open on them to get file descriptors which the kernel knows are connected to particular devices. However, this property means that many programs can use them just as if they were normal files. This is part of the UNIX design philosophy that "everything is a file."

So, to use your devices and thus your module, you just need a program which will open the block special files and read from or write to them. We have included scripts for this, but you can also use the dd utility or write your own program to do it. If you write your own program, you may want to look into the read (man 2 read) and write (man 2 write) system calls.

The locking semantics we use are not fair to lockers: if a process tries to lock the block device, and a continuous stream of other processes open and close the device, then the locker will wait forever since there will always be some other process with the device open. We say that this lock favors the processes opening the block device. We could also have made the lock favor the lockers, so that a continuous stream of lockers would cause processes trying to open the block device to wait forever. Change the semantics of your lock to not favor either openers or lockers, so that in effect, processes obey a "first come, first served" ordering (except that an entire group of processes trying to open the device can open it at once, until a process tries to lock the device).

This challenge problem has been removed, because it turns out that the problem it proposed was not actually possible. Sorry about that. You are welcome to propose your own challenge problems, if you don't like the two listed here. Challenge problems are due with the rest of the lab, unless you use late days. (Also remember that if you propose your own challenge problem, it must be approved by a TA!)

A process may have to wait a long time before it can lock an OSP block device, if there are many other processes with the device already open. In some situations, the process trying to lock the device may decide after a while that it is no longer necessary to lock the device. For instance, a process started by a web server to serve a client request may want to report an error to the client if the device can't be locked within 10 seconds. Add a parameter to the ioctl to lock the device that allows a timeout to be specified, and return -ETIME if the timeout expires before the device can be locked.

When you are finished, edit the file named LAB and follow the instructions at the top of the file to fill in your name(s), student ID(s), email address(es), short descriptions of any extra credit or challenge problems you did, any known limitations of your code (including known bugs), and any other information you'd like us to have.

Then run "make tarball" which will generate a file lab2-yourusername.tar.gz inside the lab2 directory. Upload this file to CourseWeb using a web browser to turn in the project. Remember to upload it only once if you are working in a team - the LAB file will allow us to give both team members credit.

Good luck!