CS 45 — Lab 6: A Modular Device Driver

Checkpoint: Friday, April 25/26 (brief demo during lab)

Due: Friday, May 3 @ 11:59 PM

To compile this lab, you’ll need to install the gcc-12 package inside your VM. You should only need to do this once for each VM, and you can install it by running (in a terminal inside the VM):

sudo apt-get install gcc-12

Answer y for yes if it prompts you.

1. Overview

For this lab, you’ll be implementing a device driver for a pseudo-device called a mailbox. Like a pipe, a mailbox has a read end and a write end. Processes can interact with a mailbox using the standard file system interface: open(), read(), write(), and close(). Unlike a pipe, a mailbox and its contents persist even after 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 request on the device it invokes the appropriate driver function to perform the underlying I/O operation. You will implement a character device driver for mailbox pseudo-devices. 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 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 mailbox device driver (yay!). To remove the module, you can unload it with rmmod.

For this lab, you should boot your VM with the kernel that was provided by Ubuntu. That is, boot the one with "generic" in the name. Since you’ll be doing most of your work in the VM, be sure to copy your code to your home directory and/or GitHub when you finish working. Your VM lives on /local, which is NOT backed up!

To interact with a mailbox, user programs will open special files of type device in the /dev directory. You will create eight devices, named /dev/mailbox0 through /dev/mailbox7 to support four mailboxes. Even-numbered device files correspond to the write end of a mailbox and should be write-only, and odd-numbered device files correspond to the read end of a mailbox and should be read-only. For example, /dev/mailbox0 is the write end of the first mailbox, and /dev/mailbox1 is the read end of the same mailbox.

1.1. Goals

Design a Linux device driver that meets an interface specification.
Implement your design as a loadable kernel module.
Register devices with the Linux kernel and interact with device files in /dev.
Practice reading and writing Linux kernel code.

1.2. Handy References

1.3. Lab Recordings

Week 1

Week 2

2. Requirements

A process must open a mailbox device before it can read, write, close, or ioctl it. Only one process at a time can open the read end of a mailbox. Multiple processes can open the write end.
The state of a mailbox device persists past the processes that open it. For example, suppose one process opens the write-end of a mailbox and writes 'ABC' and then closes it. The 'ABC' should stay in the mailbox until a process opens the read-end and reads 3 bytes. In contrast to a pipe, opening or closing one end of a mailbox has no effect on any processes that may have the other end of the mailbox open. The state of the mailboxes should only be erased if the device driver module is unloaded from the kernel, which should not be allowed if any processes have a mailbox open.
The behavior of the mailbox buffer is similar a bounded-buffer version of the producer/consumer problem:

Each mailbox should keep a mailbox data buffer of MAILBOX_BUF_LEN bytes (default 32 bytes) for storing data that is written into the mailbox. Processes will make requests to read or write data from/to this mailbox buffer. Your driver should move one character at a time between the user and mailbox buffer. A process that reads from a mailbox should read the bytes that it can out of the mailbox buffer and then block if there are not enough bytes remaining to satisfy the remainder of the read request. A process that writes to a mailbox should write the bytes that fit into the mailbox buffer and then block if there is not enough space to write the remainder of the data it has requested to write. That is, 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).

For example, suppose the mailbox buffer contains 'ABC' and the user asks to read one byte. You should copy the first character ('A') to them, leaving the other two characters ('BC') in the mailbox buffer, and return back to the user. If the user then asks to read three more bytes, you should copy the next two bytes out of the mailbox buffer (leaving your mailbox empty) and then block the process on a wait queue until a writer adds one additional byte. Once that third byte becomes available, you should copy it from the mailbox buffer to the user and then return, since you can now satisfy the request for three bytes.

Writing should work the same way. If the mailbox buffer has enough free space for 5 characters and the user asks to write 10 characters, you should copy the first five characters that fit into the mailbox buffer and then block the process until more space becomes available. As more space opens up, you should continue to copy one byte at a time into the mailbox buffer until you fill it again or you fully satisfy the write request.
If there are multiple writers with the write end of a mailbox open at the same time, their write requests should be satisfied in the order they arrive. The first request should be fully satisfied before moving on to the next one.

For example, if one writer arrives first with a request to write 'ABCDE', and then another shows up with a request to write 'FGHIJ', all of the first writer’s data ('ABCDE') should be copied to the mailbox buffer before any of the second’s data ('FGHIJ') is copied. If the first request blocks, the second request will also need to block. Rather than putting both writers on a wait queue, I would suggest using a semaphore to enforce mutual exclusion over "who is currently allowed to write". If the first process blocks on a wait queue while holding the semaphore, that’s fine - the other writer will block on the semaphore itself, which it won’t be able to acquire until the first writer fully completes its request.
Your device driver should detect and report errors by returning the appropriate error code. Like labs 2 and 3, you should report errors by returning -EWHATEVER. The expected error conditions and their corresponding codes are listed as comments above each function in the starter code. Don’t forget to use access_ok and copy_to_user / copy_from_user when dealing with userspace pointers!
If a user process calls ioctl() on one of your open mailboxes, you should print some debugging information using printk, much like evnt_print did in lab 3. It doesn’t matter whether they call it on a read or write end, it should print the details of all mailboxes. For each mailbox, you should print: the contents of the mailbox buffer, the read and write offsets into the mailbox, and the PIDs of any processes that have the mailbox open. NOTE: the mailbox buffers are just an array of characters that is NOT null-terminated. Rather than printing it as a string, you should print one character at a time. Here’s an example of my output:
```
Mailbox #0:
  Contents: abcdefghijklmnopqrstuvwxyz
  Read offset: 0
  Write offset: 26
  Reader PID: 2503
  Writer PIDs: 17906 15170
Mailbox #1:
  Contents:
  Read offset: 0
  Write offset: 0
  Reader PID: closed
  Writer PIDs:
Mailbox #2:
  Contents:
  Read offset: 0
  Write offset: 0
  Reader PID: closed
  Writer PIDs:
Mailbox #3:
  Contents:
  Read offset: 0
  Write offset: 0
  Reader PID: closed
  Writer PIDs:
```
Your driver module should track how many times it’s "in use" so that the kernel can refuse to unload it while processes are still using it. To increase the "in use" count, use try_module_get(THIS_MODULE). It returns true on success and false (0) on failure. To decrease the "in use" count, use module_put(THIS_MODULE).

You should increase the count when a process successfully opens a mailbox and decrease the count when a mailbox is successfully closed. You can check the count with lsmod (see the section about module loading).
Like previous kernel labs, you’ll need to write a small application that can invoke your device driver’s functions to test their behavior. I would strongly suggest that your test program be interactive (i.e., like your shell, it accepts commands as input and then invokes the corresponding system call). That way, you don’t have to worry about orchestrating multiple processes and their timing when you test. You can simply fire up multiple copies of your interactive tester and purposefully cause any combination of driver function calls to be made in the order you want.

Because your device is exported through the file system, you have more flexibility in testing than you had when making system calls. If you’d like to use Python (or any other language) for your test program, that’s fine! Just make sure that your file system calls are unbuffered. If you’re using C, use the low-level open(), read(), and write() rather than fopen(), fread(), and fwrite(). For Python, use the os module’s os.open(), os.read(), and os.write(). For ioctl in Python, use fcntl.ioctl().

3. Checkpoint

For the checkpoint, you should be able to demonstrate that:

The kernel initializes your driver module’s state variables when it’s loaded.
User processes can open and close mailbox devices.
Your driver can print the status information for mailboxes when ioctl is invoked. For the checkpoint, the important thing to print for each mailbox is the PID of processes that have it open for reading and writing.
Your module properly tracks whether or not mailboxes are open using try_module_get and module_put.
The driver module can be unloaded when no mailboxes are open.

4. Mailbox Device Files

Your mailbox devices will appear in the file system as special device files that live in the /dev directory. Each driver’s devices needs a major device number, which for this lab will be 166. Each device using that driver also needs a minor number, to differentiate which device it is (in case there are multiple devices sharing the same driver, as there will be in this lab). To create a device file, you can use the mknod command. To make setting up all the device files easier, I’ve provided you with a script named mkdevs.sh. You’ll need to execute this script once each time you start your VM (sudo ./mkdevs.sh) to produce the /dev/mailbox files:

$ cat mkdevs.sh
#!/bin/sh

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/mailbox*

Executing the script will produce /dev/mailbox0 through /dev/mailbox7. Odd-numbered device files represent the read end of a mailbox, and even-numbered device files represent the write end of a mailbox, for a total of four mailbox pseudo-devices. If the write end of a mailbox is N, then the corresponding read end of the mailbox is N+1.

5. Loading and Unloading Kernel Modules

When you run make to build your driver module, the end result will be a file named mailbox.ko. You can load that module by executing:

sudo insmod mailbox.ko

Once it’s loaded, you should be able to see it listed when you run lsmod, which lists the modules loaded on the system:

lsmod | grep mailbox

The number at the right tells you if the module is in use (non-zero) or unused (zero). If the value is zero, you can unload the module using rmmod:

# Note: Don't add the .ko suffix when unloading the module.
sudo rmmod mailbox

6. Relevant Linux Kernel Interfaces

This lab will require you to interact with a few of Linux’s mechanisms for storing/retrieving information and interacting with process states.

(Note: this section contains mostly the same content as lab 3 — none of this should be new to lab 6.)

6.1. Getting the Calling Process

In several cases, you’ll need to get information about the process that is calling one of your system calls. Since that’s a common operation, there’s a helpful function, get_current, that will return a pointer to the task_struct of the current process:

struct task_struct *this_process = get_current();

6.2. Semaphores

For this lab, your driver should use semaphores to protect its global state from race conditions. The semaphore interface is defined in include/linux/semaphore.h. The main items of interest for this lab are:

For this lab (unlike lab 3), you probably want to declare semaphores as fields of a struct. The macro you used in lab 3 doesn’t work for struct fields, so instead, you can declare semaphore variables as struct fields of type struct semaphore. The rest of the ways in which you interact with semaphore should be the same as they were in lab 3.
You can initialize the semaphore with a call to sema_init. Since you’ll be using the semaphore to enforce mutual exclusion, you should give it an initial value of 1. Your sema_init call should be happening once in your init function.
To make a process wait on a semaphore (acquire the lock), the Linux kernel has a few functions with slightly different behaviors, but we’ll only be using one in this lab: down_killable. Assuming you initialized your semaphore’s value to 1, this variant will allow only one process to acquire the semaphore. Any process that attempts to call down_killable while the semaphore is already in use will be blocked in such a way that it cannot be interrupted by anything other than a signal that will terminate the waiting process. This variant is what we want, since we don’t typically want someone who is waiting on your driver to be interrupted, but we do still want test programs to terminate if you hit CTRL-C.
To signal a semaphore (release the lock), use the up function.

6.3. Linked Lists

Since multiple processes can open the same mailbox for writing, you’ll need to keep track of a variable number of processes that have it open. Rather than implementing your own linked lists, you should use the Linux kernel’s built-in doubly linked list implementation, which is defined in include/linux/list.h.

The kernel’s linked list interface is a little different from the lists you’re probably used to seeing, but it really is implementing the same doubly linked list structure you’re familiar with, I promise! Instead of defining a list node as a struct with a data field and pointers to the next/prev structs, the expectation in Linux is that you embed a struct list_head inside of the struct that you’d like to store a list of. That list head keeps track of the links to the struct list_head in the other structs in the list.

For your implementation, each writer should contain a struct list_head to track the processes that have it open. You’ll also need to define a struct, containing just a pid_t and a struct list_head to represent a record of one process having an mailbox open. Then, whenever a process opens a mailbox for writing, you should: kmalloc one of those structs, fill in the current process’s PID, and then add the struct to the list. When closing, you should do the opposite: remove from the list and then kfree.

The functions you’ll probably want to use are: list_add and list_del to add and remove items from a list. You can also initialize a list with the INIT_LIST_HEAD macro, which you’ll need when initializing your driver. Finally, the list interface has convenience macros for iterating over the contents of a list: list_for_each and list_entry. To use it, you’ll need to give it a pointer to a struct list_head for tracking the iteration position and a pointer to the type you expect to find in the list. Here’s an example (not a suggestion that you should indiscriminately copy/paste):

/* Suppose this is the data type you're keeping a list of. */
struct element {
    int data1;
    int data2;
    struct list_head element_list;  // This tracks the links to other elements.
}

struct list_head *iter;
struct element *e;

list_for_each(iter, ...) {
    e = list_entry(iter, struct element, element_list);
    /* e now refers to one element in the list. */
}

/* The missing ... parameter should be the address of the `struct list_head` that starts off your list.
 * In your case, that will be the `struct list_head` stored in a writer device struct. */

For more information about linked lists in the Linux kernel, try these resources:

https://kernelnewbies.org/FAQ/LinkedLists

https://notes.shichao.io/lkd/ch6/

6.4. Wait Queues

Wait queues track a list of task_structs that are blocked on a condition. They’re built from Linux linked lists, but the structure is already developed for you, since making processes block is a common kernel responsibility that appears all over the place. The associated functions are defined in include/linux/wait.h.

To declare the start of a wait queue (e.g., in each row of your table), you can declare a variable of type struct wait_queue_head, which can be later initialized with init_waitqueue_head. With the start of a queue declared and initialized, you can create a node containing a task_struct using the DECLARE_WAITQUEUE macro. You can then add the node to a queue / remove it from a queue with add_wait_queue and remove_wait_queue.

The struct wait_queue_head type has two fields: a lock (ignore the lock) and a struct list_head named head. You can iterate over it like you iterate over your other linked lists (e.g., with list_for_each). The elements in the list are of type struct wait_queue_entry and they have a field named private which stores a pointer to a task_struct. It’s stored as a void *, but you can cast it to be a struct task_struct * and then access the pid:

// 'proc' is a struct wait_queue_entry
struct task_struct *t = (struct task_struct *) proc->private;

6.5. Blocking and Unblocking a Process

To block a process, you need to:

Add the process to a wait queue.
Set the process’s state (in its task_struct) to one that indicates blocking using set_current_state. Like the semaphore wait functions, there are a few variants. For the same reason described above, you’ll want to set them to the TASK_KILLABLE state.
Call schedule() to cause a context switch.

Later, when the process is resumed, be sure to remove it from the wait queue!

To unblock a process that is waiting on a queue, you can use one of the wake_up family of macros defined in include/linux/wait.h. For this lab, you probably want wake_up.

7. Tips & FAQ

I strongly suggest that you sketch out a logical design of what you want to have happen first, before doing any coding. In other words, map out what should happen in each system call in English text first and then implement it in code later. That way, you decouple the high-level tasks like reasoning about driver function behavior and concurrency from the lower-level task of expressing it in kernel speak.
When the user attempts to open one of your mailbox devices, you can inspect the f_mode field of the file pointer struct to determine how they’re opening the file: for reading, writing, or both.

The f_mode field is a bitwise-ANDed collection of bits, with the relevant values you care about being FMODE_READ and FMODE_WRITE. For example, if you to want test if the file is being opened for reading, you can do:
```
if (fp->f_mode & FMODE_READ) {
    // File is being opened for reading
}
```
Rather than typing dmesg repeatedly to see your debugging output from ioctl(), you can "watch" the log output in real time by executing: watch "dmesg | tail -n 30"
You may find it simpler to divide up each of open() and close() into two helper functions: one for reading and one for writing.
You can extract a mailbox’s device number (0-7) by looking at the inode’s i_rdev field.

For functions that get an inode directly (open and close), you can do:
```
int device_minor_num = MINOR(in->i_rdev);
```
For functions that only get a file pointer:
```
int device_minor_num = MINOR(fp->f_inode->i_rdev);
```

8. Submitting

Please remove any excessive debugging output prior to submitting.

To submit your code, commit your changes locally using git add and git commit. Then run git push while in your lab directory.

Please submit your test program in the userspace directory.