You will demo checkpoints to me during your Monday lab session. You cannot use late days on the checkpoints.

• Checkpoint 1: implement lkm functions for loading and unloading the module and implement open and ioctl on a Mailbox.
• Checkpoint 2: implement close, and non-blocking read and write to a Mailbox (i.e. it is fine if write overwrites unread contents and read re-reads previously read contents).

Contents:

• Problem Introduction
• Starting point code
• Implementation Details
• Tips for Getting Started
• Links
• What to Hand in and Demo

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:

• process Pi opens the write end of a Mailbox device and Pk opens 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 Pk makes a subsequent request to read 4 bytes, Pk will read "CXY" out of the Mailbox, and then will block until at least one more byte has been written to it. Pk does not return the result to the caller until all bytes of the read request have been read out of the Mailbox: a user-level call to read 4 bytes on a Mailbox doesn't return until all 4 bytes of the request have been read from the Mailbox. In other words, at user-level the read request blocks until the full read request can be satisfied, even though at kernel-level the implementation may read a byte and block several times in handling the single user-level read request.

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 2.6.32.44-lab4' ...
    menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab4 (recovery mode)' ...
    menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab3' ...
    menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-lab3 (recovery mode)' ...
    menuentry 'Debian GNU/Linux, with Linux 2.6.32.44-cs45' ...
   

   In the above list, kernel 2.6.32.44-cs45 is the 4th entry (counting from 0), so I'd set default to 4:

    set default="4" 
   

   Then run sync; sync; reboot and the 2.6.32.44-cs45 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 
   hello1.ko   
   

   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 
   

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
   3: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
   

   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

• A Mailbox lkm has 2 parts:
  1. The device driver part that implements functions that are called on opening, closing, reading, writing or ioctling a mailbox device.
  2. The lkm initialization and cleanup parts that are invoked on insmod and rmmod. Initialize global state in the init funciton, and clean-up any necessary state in the cleanup function.
• registering a device driver: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 includes 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.

• As sudo, run insmod to load your lkm, rmmod to unload it, and lsmod to list all kernel modules. In the starting point code insmod will invoke mailbox_init.

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

  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
  

• To ensure that your names do not conflict with existing kernel symbols, declare things static as much as possible, and use a unique prefix (like mailbox_) on 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.

Mailbox Device files

• 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 sudo 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
  

• 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

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.

REMEMBER:

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.

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

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.

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