CS45 Lab 5:
Implementing a Device Driver

Checkpoint 1: Due Monday April 14 in lab
Checkpoint 2: Due Monday April 21 in lab
Full Solution: Due Sunday April 27 before 11:59pm
You will demo checkpoints to me during your Monday lab session. You cannot use late days on the checkpoints.


Problem Introduction
For this lab you will implement a device driver for a pseudo device, and write test programs to demonstrate that your driver works. The pseudo device you will implement is called a Mailbox. A Mailbox has a read end and a write end, like a pipe. Processes can open either end. Once open, they can read or write to it over and over, closing it when they are done. Unlike a pipe, a Mailbox and its contents persist when one or both ends of it are closed, and multiple processes can take turns opening, reading, writing and closing the Mailbox to modify its contents.

A device driver implements functions for managing a (typically) physical device. Every device driver is written to conform to the kernel's device driver interface. When the kernel receives an I/O requests on the device it invokes the appropriate driver function to perform the I/O operation. Device driver functions are registered with the kernel when the driver is loaded into the kernel via insmod.

You will implement a character device driver for Mailbox pseudo-devices (do not implement it as a block device). Your implementation should use blocking (rather than polling) for reads and writes that cannot be satisfied immediately.

Your Mailbox device driver will be implemented as a loadable kernel module (lkm) that can be loated into the the kernel at runtime by calling insmod; you do not need to modify, rebuild or reboot the kernel to implement, load, or run your Mailbox device driver.

User-level programs open, read, write, and close special files in /dev to perform operations on Mailboxes. You will create 8 special files in /dev corresponding to 4 Mailboxes. Odd numbered device files will be read-only, the other 4 will be write-only; with the 8 you will implement 4 Mailbox pseudo-devices (e.g. 0 is the write end and 1 is the read end of the same Mailbox). Devices have a major number and a minor number. All devices with the same major number use the same device driver code; driver code is associated with /dev special files by creating /dev special files with the same major device number that is used to register its device driver code.

Each Mailbox should have a buffer of 32 bytes. A Writer process can write up to 32 bytes before it blocks waiting for a reader process to read data from the mailbox. Reader processes will block if there is not enough data in the mailbox to satisfy the read request. You need to use wait queues to block and unblock processes on a Mailbox.

As an example, shown in the figure below:

Starting point code
Together in lab we will do the following:
Note: if you copied over the starting point code in lab on Monday (step 1), grab a new copy of the starting point code (mailbox.c had a bug that has since been fixed).
  1. Start by setting up a git repo for your lab 5 work (remember to add three users: you, partner, and your shared cs45X user). Then, copy over my starting point files and add them to your repo:

    cp ~newhall/public/cs45/lab05/* .
    1. hello1.c: a simple loadable kernel module (lkm).
    2. Makefile_hello1: the Makefile for building the hello1.ko lkm.
    3. testmailbox.c: starting point of a user-level test program for testing your Mailbox devices.
    4. Makefile_testmailbox: a Makefile for the user-level test program
    5. mailbox.c: starting point for your mailbox implementation
    6. Makefile_mailbox: the Makefile for building the mailbox.ko lkm.
    7. mkdevs: a script to create eight mailbox device files in /dev

  2. You will use the cs45 version of the kernel for this lab. You can set this as the default kernel to boot on your VM by editing the grub.cfg file:
    $ vi /boot/grub/grub.cfg
     set default="0"
     # later in file is the boot menu list of kernels:
     menuentry 'Debian GNU/Linux, with Linux' ...
     menuentry 'Debian GNU/Linux, with Linux (recovery mode)' ...
     menuentry 'Debian GNU/Linux, with Linux' ...
     menuentry 'Debian GNU/Linux, with Linux (recovery mode)' ...
     menuentry 'Debian GNU/Linux, with Linux' ...
    In the above list, kernel is the 4th entry (counting from 0), so I'd set default to 4:
     set default="4" 
    Then run sync; sync; reboot and the kernel should be the default (and don't run update-grub or default will be set back to 0.)

    Run uname -a to see that the right version of the kernel booted, and if not, edit grub.cfg and try again

  3. scp over the starting point code onto your VM.
    $ scp -P 10022 -r  /local/me_n_pa/lab5 swatcs@yourmachine:.  
  4. Try out a kernel module

    To build an lkm, you must compile it on your virtual box VM (not on the CS machines). As a regular user on your VM, build the hello1 module you copied over in the modules subdirectory:
    $ cp Makefile_hello1 Makefile
    $ make 
    $ ls 
    As sudo, try inserting and removing the hello kernel module:
    $ sudo insmod hello1.ko    # insert the hello1 module, has printk output
    $ lsmod                    # list all loaded kernel modules 
    $ sudo rmmod hello1        # remove the hello1 module, has printk output 

Implementation Details
For this lab you will implement your device driver as an lkm. You need to implement read, write, open, ioctl, and release (close) routines, as well as complete the mailbox_init and mailbox_cleanup functions that are called when your modules is loaded/unloaded in the kernel. User-level processes will trigger your device driver code by opening, reading, writing, and closing "mailboxi" device files in /dev. See Tips for Getting Started below for some implementation hints and suggestions.

Semantics of read, write, open close, and ioctl

  1. A process must open a mailbox device before it can read or write to it.

  2. Only one process at a time can have an end of a mailbox device open; there can be at most a single process with the read end open and a single process with the write-end open.

  3. The state of mailbox devices lives past the processes who open them. For example, if one process opens the write-end writes 'ABC' then closes the write-end, 'ABC' stay in the mailbox until a process opens the read-end and reads 3 bytes. A third process can come along and open the wite-end and write 'XYZ' that could be read by the process with the read-end open.

  4. With each of your 4 mailbox pseudo-devices is a buffer of 32 bytes. A process that writes to one of these devices will block if there is not enough space to write the data (it needs to wait for a reader to read some bytes). A process that reads from the device will block if there are not enough bytes of for the writer to write some more bytes).
    You should use wait queues to block readers/writers that are waiting for bytes to read/write, and you can call wake_up to unblock a reader/writer when there is something to read/write from the mailbox.

  5. Reading from an empty mailbox will block the calling process until there is something written to the mailbox; a write on the corresponding write mailbox device, will unblock the waiting reader.

  6. A close to the write-end of a mailbox when a process is waiting on the read-end of the mailbox results in the reader continuing to wait (this is different from what would happen on a pipe if the writer process closed its end of the pipe); the reader will wait until another process comes along and opens the write end of the mailbox and starts writing data (this is like producer-consumer semantics for close). Similarly, a close to a read mailbox when there is a waiting writing process results in the waiter continuing to block (it will wait for the next reader to open the read mailbox and start reading).

  7. A call by a user-level program to read/write X bytes from/to a mailbox should not return until all X bytes have been read from/written to the mailbox (unless an error occurs).

  8. Your ioctl function should print mailbox information using printk. You can use this to debug and to demo your solution. Some things you should print out:
    1. the buffer contents of the 4 mailboxes
    2. the read and write offsets for each mailbox
    3. the number of bytes currently stored in each mailbox
    4. information about which process has mailbox endpoints open
    You can add any additional output you want, but keep it fairly concise and easy to read. For example, you could print out each Mailbox's contents like this:
    Mailbox Contents:                      
    0: abcdexxxxxxxxxxAAAAAAAAAAAAAAAAA    
    1: ssssssssssssssssssssrrrrrrrrrrrr      
    2: aa345679aaaaaaaaaaaaaaaaaaaaaaaa
    Remember that the mailbox buffers are just arrays of char values, so you cannot print out the contents as a string (there is no terminating '\0'), instead you have to print out each char one at a time.

    Also, remember that you cannot call ioctl without a valid file descriptor...your process has to have at least one mailbox open and use its file descriptor to pass to ioctl to get it to print out mailbox information.

Loadable Kernel Modules and Character Device Drivers

Mailbox Device files

User-level test program

Implement a simple menu-driven program for testing your Mailboxes (similar to what you did in lab 3).

User-level test code should use the system calls open, close, read, write, and ioctl on /dev/mailboxX files for manipulating Mailboxes.

Do not use FILE *, fopen, fread, etc.

Tips for getting started
  • You will be doing most of your code development on the virtualbox VM. Be sure to periodically scp your code back to the git repo on a CS machine and commit and push it so that you don't lose your work.
  • Also, you need to re-run the mkdevs script after each reboot to recreate the 8 /dev mailbox files.
  1. After reading through on-line lkm and device driver documentation, start by loading and unloading the hello lkm, to get an idea of what insmod, lsmod, and rmmod does.
  2. Next, create the mailbox device files and try loading and unloading the staring point lkm.
  3. Next, implement open, iotcl and close on a mailbox device Add to your user-level test program a call to open one of your files in /dev and see what happens.
  4. Next add support for non-blocking read to a mailbox device. Just initialize the mailbox with 32 bytes of some string and have the reader read bytes from this "static" 32 byte string (i.e. if read is for 40 bytes and the static mailbox string is "abcd...z123456", then have the read return "abcd...z123456abcdef").
  5. Next, add support for a non-blocking write to a mailbox; the write may overwrite bytes not yet read by the reader process.
  6. At this point, it would be good to add support for all error conditions that do not have to do with processes blocking, and test that your error handling code.
  7. Next add support for blocking reader and writer processes. A writer process will block when the mailbox buffer fills and the write cannot complete until a reader reads some bytes out of the buffer (the writer must wait until the reader has read bytes rather than just writing over them). A reader process blocks when it tries to read more bytes from the mailbox than there are bytes to read (the reader must wait for the writer process to write more). Your solution should allow readers and writers to make read and write requests that are much larger than the mailbox buffer size. In this case a reader or writer process may block and unblock multiple times before the single read or write request is complete (i.e. a user level call to read 2000 bytes on a mailbox doesn't return until all 2000 bytes have been read even though in your kernel-level implementation of read, the process will block and unblock many times while reading this many bytes). You may want to first implement and test blocking readers then implement and test blocking writers.
  8. Finally, make sure that your code is robust. Think about error conditions that you will need to test (this is not a complete list): what happens when a process tries to read, write, open a mailbox device opened by another process? what happens if a process tries to write to the read end of a mailbox or tries to open the read end for writing? what happens if a reader processes is blocked on a mailbox and the writer process closes it or exits?

There are some on-line references for device drivers and lkms. Keep in mind that these interfaces change a fair amount, so some of the details may differ in the kernel version we are using.


You will submit a single tar file containing your lab 5 solution and submit it via cs45handin Only one of you or your partner should submit your tar file via cs45handin. If you accidentally both submit it, send me email right away letting me know which of the two solutions I should keep and which I should discard. You can run cs45handin as many times as you like, and only the most recent submission will be recorded.

Your lab5 tar file should include the following (see Unix Tools for more information on script, dos2unix, make, and tar):

  1. README file containing the following information:
    1. Your name and your partner's name
    2. The number of late days you used on this assignment
    3. The number of late days you have used so far
    4. Information telling me how to build, load, and run your device driver code and your test program(s).

  2. Copies of the test program(s) you wrote including Makefile(s). Your test program(s) should be well commented and include descriptions the functionality that you are testing at different points in your program, and include descriptions of how to run your test program.

  3. Copies of all source files, header files and makefiles that I need to compile, load, run and test your mailbox device driver. Again, this should be well commented code.


After submitting your lab, you and your partner will sign-up for a 30 minute demo slot. You should demonstrate that your device driver is correct and robust. I will definitely want to see how you handle reader and writer blocking. Make sure that your ioctl function prints out enough information about mailboxes for your to "show me" the effects after open, close, read and write operations. If it doesn't, then add some more output to your ioctl or some debug printks to functions so that you can more easily demonstrate that your code works.