Lab 4: Implementing a Device Driver in Linux
Due: Wednesday Dec 7 before 1am (late Tuesday night)

I will not accept late assignments after Friday Dec. 9 before 1am (this will count as 1 day late)

Problem Introduction
Lab 4 Set-up and Starting point code
Implementation Details
Links to on-line documentation
What to Hand in and Demo

Introduction

For this lab you will implement a device driver for a psuedo mailbox device, and write test programs to demonstrate that your driver works. A mailbox is is like a persistent pipe. It has a read end and a write end. Processes can open either end, then read or write to it, then they close it when they are done. Unlike a pipe, a mailbox and its contents do not go away when one or both ends of it are closed.

A device driver implements an interface 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 will invoke 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.

You will write the character device driver for a mailbox pseudo-device (do not implement it as block device driver), and you will use blocking rather than a polling interface for reads and writes to your mailbox devices.

The mailbox device driver code will be written as a loadable kernel module (lkm) that is written and compiled into a .ko file that is then loaded into the kernel at runtime by calling insmod; you do not need to modify, rebuild or reboot the kernel to implement, load, or run your device driver.

To use your pseudo-device, user-level programs will open, read, write, and close special files in /dev corresponding to your mailbox devices. You will create 8 special files in /dev. Odd numbered devices 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 of your mailbox will have a buffer of 32 bytes. A Writer process can write up to 32 bytes before it blocks waiting for the 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 mailbox.

An Example: in the figure below, process Pi has opened the write end of a mailbox device and Pk has opened the read end of the same mailbox device. Pi writes "ABC" to the mailbox and closes its end. Pj then opens the write end and writes "XY". If Pk reads two bytes from the mailbox, it will read "AB", and only three bytes will remain in the mailbox "CXY". If Pj makes a subsequent request to read 4 bytes, Pj will read "CXY" out of the mailbox, and then will block until at least one more byte has been written to the mailbox. Pk does not return the result to the caller until all bytes of the read request have been read out of the mailbox (a call to read 4 bytes on a mailbox blocks until all 4 bytes have been read, even though the kernel-level implementation may read a byte and block several times).

Set-up and Starting point code:

Set-up for Lab 5: do this one time only
1. You want to use the cs45start version of the kernel for this project. Either grab a new copy of the /scratch/vm/qemu/cs45f11_debian.img and use it for this lab, or change the grub.cfg file on your current image to set it to boot cs45start by default. To do this, change the value of 'default' in /boot/grub/grub.cfg from 0 to the number of the kernel to boot. Here is what your list of kernel images might look like:
```
 
% vi /boot/grub/grub.cfg

set default="0"
...

### BEGIN /etc/grub.d/10_linux ###
menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab3' --class debian --class gnu-linux --class gnu --class os {
...

menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab3 (recovery mode)' --class debian --class gnu-linux --class gnu --class os {
...

menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab2' --class debian --class gnu-linux --class gnu --class os {
...
menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab2 (recovery mode)' --class debian --class gnu-linux --class gnu --class os {
...
menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-cs45start' --class debian --class gnu-linux --class gnu --class os {
...
	
```
  In the above list, since the kernel 2.6.32.44-cs45start is the 4th entry (counting from 0), I'll set default to 4:
```
set default="4"
	
```
  Then run sync; sync; reboot and the 2.6.32.44-cs45start 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
2. As some user (not root) scp over the starting point code onto your qemu machine (it is in ~newhall/public/cs45/lab4). Here is an example doing the scp from the qemu machine:
```
  scp -r  user_name@172.20.0.1:/home/newhall/public/cs45/lab4 . 
	
```
Try out a kernel module
To build an lkm, you must compile it on the qemu machine (not on the CS machines).
As a regular user on your qemu machine, build the hello1 module you copied over in the modules subdirectory (you can do this as root, but it is always good practice to avoid doing anything as root that you can do as a regular user...it will save you from doing really bad things like accidentally deleting system files):
```
	$ cp Makefile_hello1 Makefile
	$ make 
	$ ls
	  hello1.ko   

	
```
As root, try inserting and removing the hello kernel module:
```
	$ su
	$ insmod hello1.ko    # insert the hello module, has printk output
	$ lsmod               # list all loaded kernel modules 
	$ rmmod hello         # remove the hello module, has printk output
	
```

Implementation Details:

note: you will be doing most of your development for this lab on your qemu machine. Make sure to frequently scp your code to a private subdirectoy of your home directory of your CS account 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.

For this lab you will implement your device driver as an lkm. Grab the starting point code for lab 5 that contains an example of how to register a character device driver with the kernel. You need to implement read, write, open, and release (close) routines as well as complete the mailbox_init and mailbox_cleanup routines 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.

I suggest implementing this assignment incrementally. For example, first, try loading and unloading a simple lkm. Next, try to implement just the open and close parts of your mailbox devices, once you get those to work, then add read and write without blocking, then add in blocking.

Semantics of read, write, open close, and ioctl

A process must open a mailbox device before it can read or write to it.
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.
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.
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.
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).
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).
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 the contents of the 4 mailboxes, the read and write offsets for each, and information about which processes have mailbox endpoints open. And, you can add any additional output you want, but keep it fairly consise and easy to read. For example, list the mailbox contents something like this:
```
Mailbox Contents:
0: abcdexxxxxxxxxxAAAAAAAAAAAAAAAAA
1: ssssssssssssssssssssrrrrrrrrrrrr
2: aa345679aaaaaaaaaaaaaaaaaaaaaaaa
3: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
```
And remember these are just buffers 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.

Loadable Kernel Modules (lkm)

The good news with this lab is that you do not need to modify existing kernel code to implement your solution. As a result, you do not need to re-build and re-install the kernel to test each change. Instead you are using the kernel's support for loadable kernel modules to implement your mailbox device driver. Loadable kernel modules are code that can be loaded/unloaded into the kernel as it runs. The bad news is that this is still kernel-level code, so debugging is tricky and your code can still cause a kernel panic.

As root, run insmod to load your lkm, rmmod to unload it, and lsmod to list all kernel modules. The function insmod invokes your mailbox_init function and rmmod invokes your mailbox_cleanup function.

note: rmmod is a bit flaky, so if it fails you will need to reboot the kernel to remove your lkm.

You will likely need to included the following headers in your lkm:

 linux/kernel.h	
 linux/module.h	  # lkm types/function prototypes 
 linux/init.h     # some useful macros
 linux/fs.h       # file_operations type for device driver
 linux/wait.h     # wait queue types/function prototypes
 linux/list.h     # list types/function prototypes
 asm/uaccess.h    # useful functions 
 linux/cdev.h     # character device interface functions
 asm/current.h    
 linux/sched.h

Details

The lkm is divided into 2 parts: the device driver part and the lkm initialization and cleanup parts which are invoked on insmod and rmmod. The mailbox_init function in the starting point shows an example of how to register a device driver on one of the 8 device files you need to create. Part of registering a device driver is defining a set of functions that are registered with the Virtual File System (VFS); each VFS inode has a set of file operations for the file system object to which it points. These functions are called when a user-level program makes an I/O system call (ex. read or write) on one of your /dev/mailbox devices.

To ensure that your names do not conflict with existing kernel symbols, use the mailbox_ prefix on all your functions and global variables. You can also search the Linux cross reference for names to see if there are any names in the kernel that could conflict with any you add.
To use a mailbox device, a user level process will open, read, write, and close special files in /dev. You will create 8 special files in /dev/. Odd numbered device files will be the read end of a mailbox, and even numbered device files will be the write end of a mailbox. With the 8 device files you will implement 4 mailbox pseudo-devices; if the write end of a mailbox is i, then the corresponding read end of the mailbox is i+1. Name your devices "mailboxi" where "i" is one of {0, 7}. Use 166 as the major device number and {0,7} as the minor device numbers. A list of in-use device numbers is in /proc/devices. 166 should be free, but if for some reason it is not, pick a different number.
With the starting point code is a script, mkdevs, that will create all the device files in /dev. Run this script as root after each reboot. Here is what the script looks like:
```
mknod  --mode=666 /dev/mailbox0 c 166 0
mknod  --mode=666 /dev/mailbox1 c 166 1
mknod  --mode=666 /dev/mailbox2 c 166 2
mknod  --mode=666 /dev/mailbox3 c 166 3
mknod  --mode=666 /dev/mailbox4 c 166 4
mknod  --mode=666 /dev/mailbox5 c 166 5
mknod  --mode=666 /dev/mailbox6 c 166 6
mknod  --mode=666 /dev/mailbox7 c 166 7
ls -l /dev/mail*
```
The script creates device files in /dev/. At reboot, these files are removed. You can add to the file /etc/rc.local the 8 mknod commands above, and then on re-boot the mailbox device files will be re-created "automatically".
If you do ls -l on these files, you will see information for the device:
```
#    file_permission  device_file_name          char_dev   major# minor#
mknod --mode=666     /dev/mailbox7                   c      166       7
```
You need to ensure that each of your mailbox devices can be opened by at most one process at a time.
The rmmod command invokes mailbox_cleanup that unloads your device driver code from the kernel and unregisters the drivers from the mailbox devices by calling cdev_del.
rmmod should not succeeded unless all mailbox devices are closed.
With each of your 4 mailbox pseudo-devices should be a buffer of size 32. 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 data in the buffer to satisfy the read request (it needs to wait 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.

To print the device major and minor number from the file's inode:

    printk("Device %d:%d\n",inode->i_rdev >> 8, inode->i_rdev & 0xff);

User-level test program

Use the system calls open, close, read, write, ioctl, for interacting with your /dev/mailboxi files. Don't use fopen, etc.

Tips for getting started

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.
Next, create the mailbox device files and try loading and unloading the staring point lkm.
Next, implement simple open and close on a mailbox device (it doesn't need to be a complete implementation of either function). Add to your user-level test program a call to open one of your files in /dev and see what happens.
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").
Next, add support for a non-blocking write to a mailbox; the write may overwrite bytes not yet read by the reader process.
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.
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.
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?

Useful Documentation Links

Linux Kernel Module Programming Guide by Salzman, Burian, Pomerantz. Keep in mind that there are some differences between the version of the kernel we are using and the older version described here.
Linux Device Drivers, Third Edition, by Corbet, Rubini, and Kroah-Hartman. Chapter 3 is likely most useful for this assignment.
Also, refer to struct defs and function prototypes in version 2.6.32.44 of the linux, as some types may differ from the version of linux used in this documentation.

Hand in

Create a single tar file with the following and submit it using cs45handin:

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

Demo

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. You will want to run a version with debugging output that prints out the state of your mailbox devices after open, close, read and write operations so that you can more easily demonstrate that your code works.

Lab 4: Implementing a Device Driver in Linux Due: Wednesday Dec 7 before 1am (late Tuesday night)