Home

Syllabus

Staff

Lectures

Drill

Exams

Project

Literature

Announcements

Contact

Valid HTML 4.01!

OPERATING SYSTEMS COURSE [SPRING 2006]: PROJECT

The course includes a project of modest size, involving software design and implementation.

TEAMS

The class will be divided into teams of two students each. By default, it is assumed that these will be the same teams as formed for homework assignments. Anyone who wants to change the arrangement, does not currently have a partner, etc., should contact Hananel by email as soon as possible. Please do not forget to put "[OS Course]" in the subject line (including the square brackets). The final team list should be compiled by Thursday, May 4, 2006, and no changes will be possible after Sunday, May 7, 2006.

Choosing a partner and working as a team is an essential part of the project. It is expected that team members will divide the work between them as they see fit, and will back each other up in cases of illness, reserve army duty, etc., to meet the project deadline. Every attempt will be made to form suitable pairs. Working as a team of three will only be permitted if no other reasonable solution is found, e.g., if there is an odd number of students in the course. Working alone will not be permitted under any circumstances.

SUBMISSION DEADLINE

The project submissions are due by midnight, June 20, 2006. This makes the project duration more than 6 weeks. No extensions will be granted.

The submissions will be sent by email to both Oleg and Hananel. This will provide a backup in case one of the mails gets lost or delayed - it is enough that one of us gets the submission, but do send to both of us. Do not forget to put "[OS Course]" in the message subject. The emails must be received by at least one of us before the deadline.

Each submission must include all the deliverables as text/plain attachements, and include at least the ID numbers (and optionally names) of all the team members.

PROJECT DEFENSE

The project defense will be scheduled separately. During the defense the submissions will be tested, there may be a brief design and code review with each team, and a discussion. Each member of each team will be expected to explain the various design and implementation decisions made in the course of the project, answer questions, etc.

GRADES

The project will account for 30 per cent of the final grade, and is mandatory. A passing project grade is necessary to pass the course.

The grades will be based upon the review of the submitted material, testing of its operation, and the discussion during the defense.

PROJECT GOALS

Writing code is only a minor goal of the project. In fact, the amount of code that needs to be written is very small. The emphasis is very much on independent learning, including reading code, and on applying the knowledge gained.

Some of the most important goals of the project are as follows:

  • Independent learning of a few practical aspects of OS design and programming via reading available literature and OS code and actively applying the knowledge.
  • Getting experience in modifying and extending a large existing code base (such as Linux kernel code), as opposed to implementing an independent piece of software. This includes taking care of keeping the original code base intact when the user does not need the new functionality, conforming to the existing coding standards and practices, creating the necessary configuration tools, testing infrastructure, documentation, etc.
  • Simulating (to some extent) a real industry project, including working in a team, independent study, project planning, formulation of requirements, preparation of a suitable development environment, design and implementation of a modification to a large project, documentation, etc.
  • Dealing with some aspects of software project management, such as division of labor between team members, risk management. The team members are expected to back each other up in case of illness, reserve army duty, etc. The technical risks should be assessed and mitigated in a timely fashion. E.g., when do you test that you can bring up a new kernel in your development environment? Is it when you have developed most of the code already, 3 days before submission deadline, or should it be verified during the first week?
  • Getting a little bit of practical experience in OS development via implementing a very simple peripheral device in software and writing a driver for it.
  • The project is intended to become a part of your professional "portfolio" that you can point to in your CV and subsequent job interviews.

PROJECT DESCRIPTION

SUMMARY

Implement a Linux driver for a (simulated) PCI character device that computes word count of input ASCII text. The user sends a text to the device, the device DMAs the input, computes the counts of characters, words, and lines in the input, similarly to the functionality of the UNIX wc(1) program, and DMAs the results back into the memory. The user interface will be a simple device file: the input will be transferred to the device by writing to the file, and the results will be obtain by a subsequent read.

COMPONENTS

1) THE SIMULATED "WC" DEVICE IN QEMU (PROVIDED!)

The WC device is a generic DMA-capable character PCI device. For the necessary material on PCI devicesthe topic see Linux Device Drivers, 3rd edition, also in the Literature web page, especially the chapters on character and PCI drivers), and also the Linux kernel source code and documentation.

Do go over the kernel's Documentation tree - there is a lot of very relevant information there. It is a part of the project assignment to identify which of the information is most relevant and helpful.

To implement the device in software one needs to create a set of control registers:

  • registers for source and destination addresses;
  • a register for the size of input (for DMA);
  • a write-only control register for commands to the device;
  • a read-only status register for feedback from the device.

The minimal set of command flags to pass into the control register is:

  • WC_CTRL_ACTIVATE (to activate the device);
  • WC_CTRL_DMA_END_IRQ (to raise IRQ on DMA completion).

The minimal set of status flags to otain from the status register is (the meaning should be obvious):

  • WC_STAT_BUSY;
  • WC_STAT_READY;
  • WC_STAT_READ_ERR;
  • WC_STAT_WRITE_ERR.

The normal way to implement the control protocol is to treat the control and status registers as bitmasks, and check whether the bits corresponding to the particular control and status flag is on.

The endianness of the device is not necessarily the same to the CPU.

The device has been implemented for you inside the QEMU hardware emulator. The emulator can be installed and run as an application on Windows, Linux, or MacOS computer without special privileges (see the relevant documantation). All software (system and applications) running inside QEMU will behave as if it is running on real hardware.

Instructions for installing QEMU with the "WC" device.

  • Download the QEMU source code, suggested version is 0.8.1.
  • Unpack the QEMU source code, e.g., tar zxvf qemu-0.8.1.tar.gz.
  • Apply this patch, e.g., on Linux do cd qemu-0.8.1; patch -p1 < ../qemu-wc.patch (this assumes that the patch exists in the same directory as the top-level directory of the unpacked sources, qemu-0.8.1).
  • Congifure, build, and install QEMU. Follow the instructions in the QEMU documentation.
  • Get a Linux image to run in QEMU. For instance, pick one that suits you from FreeOSZoo. Verify that the image works under QEMU by running it.
  • Get a 2.6 Linux kernel to hack on from kernel.org or one of its mirrors.
  • Unpack the kernel source, e.g., tar jxvf linux-2.6.16.tar.bz.
  • Configure and build the kernel for QEMU, e.g., start with this config file: copy it to the top level kernel souirce directory as .config, and run make oldconfig; make bzImage.
  • Test that your kernel works with QEMU.

QEMU tips and tricks:

  • QEMU does not compile with gcc 4.x. You need gcc 3.2.x. Modern Linux distribultions usually come with both. E.g., the default gcc on Fedora Core 4 is version 4, but there is also gcc32. So use ./configure --cc=gcc32.
  • QEMU will not compile on Windows with MSVC. You can either cross-compile for Windows on Linux, or install MinGW (see QEMU documentation for details). An easy way to install MinGW (and gcc) is Cygwin.
  • This directory contains a prebuilt version of QEMU, including this patch. It has been built on an i386 Fedora Core system, using ./configure --cc=gcc32 --target-list=i386-softmmu. It uses dynamically linked libraries, so it is not guaranteed that it will work on your system, but you may try it. It is recommended that you build your own.
  • You may experience problems mounting the images that are compressed (such as qcow - QEMU Copy-On-Write - format). QEMU understands such formats, but mount may not. You need to convert the image to the "raw" format using qemu-img. For instance, qemu-img info shows what format the image is in, and qemu-img convert may be used to convert to the raw format. See QEMU documentation for details.
  • In the lab, you do not have root permissions to mount the image. Use UML (see below) or Knoppix to run qemu - you will have root access there. If you use a virtual machine (such as VMware) you won't have a problem, either.

At this point you should be ready to develop the driver.

Feel free to have a look at the provided QEMU patch to see how the device is implemented, pay special attention to the register implementation, since this is how your driver will communicate with the device.

2) THE DEVICE DRIVER

The driver needs to register/unregister itself as a PCI driver, enable/disable the device, probe the device, remove the device, etc. Suspend/resume are not mandatory. It is enough to handle only one device of this type.

The driver must implement the device control protocol, handle errors, handle the interrupt, including verifying that the interrupt comes from this device (so that the IRQ can be shared).

The driver will implement a regular character device, a device file, input and output DMA buffers, etc. The DMA infrastructure should be minimal, setting up a pair of coherent DMA buffers (for input and output) should be sufficient. Coherent DMA buffers are available to both the CPU and the device all the time (see Linux Device Drivers, Ch. 15).

The user will write and read to the device file. The device will be activated on write, and will output data on read. The read operation will block while the device is working. Read must also reset the device so that the same output is not read over and over again.

Typical user test will look something like 

(cat input_file.txt >&0; cat) <> /dev/wc
where the first cat writes the contents of input_file.txt to /dev/wc, and the second cat reads /dev/wc.

Upon completion of DMA the interrupt raised by the device must be handled, and the waiting process needs to be woken up.

The device must employ proper locking. E.g., all register access and relevant data structures must be protected. For simplicity, it is enough to allow only one user at a time to access the device file.

3) KERNEL CONFIGURATION

The device and the driver should work with a modern 2.6 Linux kernel. The kernel configuration utility should allow the user to choose whether or not to configure the device as a module. If the user chooses not to configure the device, the kernel must not be affected in any way. The configuration part should include the kernel configuration scripts and comprehensive help for the driver.

DELIVERABLES

KERNEL PATCH

A clean patch file (produced by diff -Nur, see the documentation of the diff and patch utilities, e.g., info diff), including:

  • all the device and driver code;
  • the changes to the kernel configuration and build code (makefiles, Kconfig files, etc., see Documentation/kbuild in the kernel code);
  • the necessary documentation, included in the kernel's Documentation tree.
The patch must be complete, but clean, i.e.:
  • it should not contain anything that should not be present in the kernel code - no object files, no files generated during build, no editor autosave files, etc.
  • the kernel built after applying the patch must be installable alongside the unmodified kernel on which the project is based (hint: check the EXTRAVERSION variable in the top-level kernel Makefile)

The documentation should contain a full description of the device functionality. It will be treated as a specification against which the operation of the code will be checked. The specification should conform to the original project description, of course.

The documentation should also contain the instructions for loading and operating the driver, whether or not a load/unload script is provided (see below).

A TEST UTILITY

A simple userspace test utility should be provided. The tester (the TA) will not be confined to this utility - the device and the driver must perform properly (this includes error reporting) under all circumstances. The comprehensiveness of testing will be incorporated into the final assessment of the project.

OPTIONAL: A LOAD SCRIPT

You may provide an optional load script that will load the driver, create the device file (if necessary), etc. Whether or not you do so, the complete instructions for loading the driver must be provided in the documentation. Of course, the documentation may refer to the load script if there is one.

NON-FUNCTIONAL REQUIREMENTS

  • this is a modification/enhancement of a large existing code base, and it must conform to the base in style; read Documentation/CodingStyle very carefully, and notice how the style considerations are applied as a design tool.
  • proper error handling is essential, in particular, "garbage in / garbage out" is not acceptable; the code should deal with unexpected input intelligently.
  • solid design of both code and interface is essential.

BONUS POINTS

Bonus points will be awarded for useful enhancements. Possible examples of such enhancements may include:

  • implementation of a device that computes word and/or character frequencies rather than mere counts, i.e., outputs the number of times each word and/or character was used in the input;
  • allowing multiple identical devices to be present;
  • allowing for multiuser operation, etc.

If you have thought of an interesting enhancement but are not sure whether it is "useful" enough to be considered for a bonus, feel free to discuss it with Oleg.

PRACTICAL ADVICE

A possible plan of attack may look as follows:

  • Implement a "Hello world!" driver to learn how to write kernel modules, compile the kernel, load a driver, etc.
  • Implement a simple character device driver, e.g., following the example of scull driver in Linux Device Drivers, 3rd edition. You will thus learn how users can pass information to the kernel and get responses back.
  • Move on to a PCI driver that can communicate with the "WC" device. Start with reading the relevant chapters from the book. The guest lecture on May 14 will also help with this.

Note that this is only a suggestion, and it will not necessarily work best for all of you. Do feel free to approach the problem the way that suits you best.

ENVIRONMENT: HOW TO RUN LINUX ON YOUR MACHINE

You can use the University UNIX Lab that has a significant number of Linux machines and is always available. The machines are accessible from outside of the University (ask the Lab staff), so you can work on them from the comfort of your home.

If you wish to use your own computer, there are several options. The most obvious one is to install Linux as an additional operating system on your computer. You need some spare disk space, and you need to modify your existing disk partition structure, which may be a problem. Do not attempt it unless you are fairly sure you know what you are doing, or that you will be able to recover lost data if things go wrong.

If you decide to do it, use one of the established distributions, such as Red Hat's Fedora, Novell (SuSE), Mandriva, Debian, Kubuntu, or any of a score of others. It does not matter for the purpose of the project which one you choose.

Installation is normally as simple as burning a few CDs, popping the first one into the drive, and booting the computer. You will be presented with some choices, the most important of which is disk partitioning. Once again - this is the dangerous part. Unless you shrink your existing partitions with a tool like PartitionMagic (I don't know if the University has licences for that) to free some space before installation, repartitioning may cause loss of data. You've been warned.

So you decided not to install Linux for fear of losing your critical data on the existing partitions. There are other options.

Emulators. We will study the principles closer to the end of the semester. I suggest checking out QEMU - it runs on Linux, Windows, and Mac and emulates a number of different CPUs. You should be able to emulate a computer system and run Linux in emulation mode, after you have read the documentation.

A virtual machine (another topic we will cover in the course, also closer to the end) is probably a better and easier solution. You can download VMware Player and one of the prepackaged virtual machines. You can pop a CD and install Linux (over the existing contents, though a prepackaged Linux virtual machine may serve your purposes very well) just like on a physical computer. You will end up running two operating systems on your computer simultaneously. A disadvantage of this solution is that it may be too slow on older systems with limited memory. I do not suggest this if you have less than 512MB of RAM.

I am told that Microsoft's Virtual PC is available to the University students. It is another virtual machine option, but I have never tried running Linux in it.

A live CD. Probably the most popular one is knoppix. You can run Linux directly off a CD, without doing any installation. A disadvantage of this solution is that a CD is not writable, and you will have to do some work. You can solve this by either using a (big enough) USB disk-on-key or letting Knoppix access you hard drive and creating a filesystem in a file there.

All of these solutions are available free of charge, including those from commercial companies (Red Hat, Novell, Mandriva, VMware, etc.).

Note also that you can run QEMU in your account on any computer in the Lab: QEMU is a userspace application and does not require special privileges. VMware Player does require root privileges to configure itself.

An additional way to run "your own" Linux in the Lab that does not require root privileges is User Mode Linux (UML). It is available on all the lab machines.

Here are the instructions (as received from the Lab Administrator) on running UML in the Lab:

As a user you need to login into one of the machines and run:

linux con0=fd:0,fd:1 mem=128M ubd0=root_fs_cow,/usr/local/uml/root_fs \ eth0=tuntap,,,192.168.0.2

This will create a layered fs in the user home, it's a diff from the root partition at /usr/local/uml/root_fs.

You will also get a prompt to login, you can login using root (no password). If you need network you can run /etc/init.d/net.eth0 start. The machine is using tun/tap network and the firewall on the real machine masquerades the traffic.

To close it nicely, run shutdown -h, then you should be back in your account.

The students can download the the root_fs, if they want to work at home.

If, for some reason, you get a kernel panic during boot, first, make sure this is not a root_fs corruption issue.

Go through all the messages during linux's bootup process and search for something similar to this 

    F_SETLK failed, file already locked by pid 9108
    Failed to lock 'root_fs', err = 11
Possible solutions:
  • If you have enough disk space left, 
     cp -ia root_fs_cow  
 root_fs_cow.orig
 rm root_fs_cow  
 sleep 2
 mv root_fs_cow.orig root_fs_cow
  • If there are no other users logged into that machine, restart the computer. The lock should be released then.
  • Put the COW filesystem in /tmp but rememeber that directory is not backed up and is local to the computer (not part of the NFS). When there is no one on that machine, reboot it.

Please refer to the Lab staff if you are having problems with the setup.

$Revision: 1.17 $
$Date: 2006/06/06 02:20:13 $