1 - Introduction

The objective of this assignment is to implement a kernel-based first-in-first-out (FIFO) message queue by extending a barebone character device driver. This message queue can be used by multiple producers and consumers to exchange data at the same time so with this assignment you will also get more practice with synchronization primitives. Specifically, you will:

  • Extend a character device driver, implemented as a kernel module, to implement a FIFO message queue that supports multiple producers and consumers.

  • Extend a user space program to interact with the character device driver to test it.

2 - Setup

  1. Boot your Debian virtual machine using your “known good” Linux kernel (most likely the one with a name ending with amd64).

  2. Download the file template-pa5.zip, move it to your shared folder, and unzip this archive file using the command:

    unzip -d "<shared>/<login>-pa5" template-pa5.zip

    Where <shared> is the path to your shared directory, and <login> is your Stevens username (e.g. rtsang1).

  3. In the “scull” character device driver (inside the driver directory) we have prepared one IOCTL command, which you can find in the scull_ioctl function of the scull.c file.

    This command returns the size of a queue element (in other words, the maximum length of any message exchanged between a producer and consumer), although the queue itself is not implemented yet (this will be your job below). The scull.c file also contains two scull_read and scull_write functions which currently do nothing except write an informational message to the kernel log.

    To test the code:

    1. Modify MODULE_AUTHOR in scull.c to indicate your own student login name.

    2. Compile the scull driver code (it is implemented as a kernel module).

    3. Load the module into the kernel. Also check what happens at the same time in the kernel log.

    4. Create the special character device file /dev/scull with the correct major number for the “scull” module (see Programming Assignment 4 if you do not remember how to do this).

    5. By default, the /dev/scull pseudofile is created with root-only access permissions. To enable read and write permissions, execute the following command:

      sudo chmod o+rw /dev/scull

      (o indicates “other users”)

    6. Compile the user-space producer and consumer programs (inside the src directory).

    7. Test the consumer and producer programs to get a feel for what they do. Also check what happens at the same time in the kernel log.

    8. Unload the module.

3 - Part 1: Implementing the Message Queue

Extend the “scull” character device driver (inside the driver directory) by implementing a FIFO message queue that can store up to N messages (N is called scull_fifo_size in the code), each of size ELEMSZ characters (called scull_fifo_elemsz in the code).

The provided code is written in such a way that N and ELEMSZ can be configured at module load time through module parameters (see below). Do not make any assumption in your own code about the values of N and ELEMSZ, except that you can assume that they are always positive integers.

The only limits for N and ELEMSZ should be kernel memory availability, not anything in your implementation.

Do NOT delete existing code and do NOT create new files. Only modify existing files to introduce your functionality.

Your tasks:

  1. Allocate the message queue as a flat array of characters when the module is loaded into the kernel, and correctly free the message queue when the module is unloaded. Do not implement it in any other way. Not as a list; not as an array of structures; not as multiple arrays. Yes I am forcing you to practice pointer arithmetic.

    Information on memory allocation and deallocation in the kernel can be found on kernel.org.

    1. You must check whether your memory allocation succeeds or not; if not, you should return an error.

    2. Because processes can store less than ELEMSZ characters of data in a given message, you will also need to store the number of characters actually written in the element.

      See the Figure 1. where for example the length “len” for the first message is less than ELEMSZ, and so the “len” value needs to always be stored as part of the array, in front of the data for the message proper. The type you use for ‘len“ in your code must match the type used by the scull_read and scull_write functions for the length of a message.

      Figure 1: Memory model for message queue entries

    3. Since you need to use a flat array to implement a FIFO message queue, you will also need two pointers to manage this array as a circular buffer (do not use any integer type or you will lose points):

      • start to indicate the oldest full array element where the next (oldest) message can be read;

      • end to indicate the oldest empty array element where the next (newest) message can be written.

      Make sure these two pointers are properly initialized when the module is loaded! Use the “void *” pointer type for both of these pointers.

  2. Implement the scull_read (consumer) message queue operation in the device driver.

    A placeholder function is already in driver/scull.c that currently does nothing except print a message in the kernel log. Complete this function to perform the following:

    • Consume the first entry in the queue and copy its data to the provided buf parameter, or block if the queue is empty. If count (the size of buf) is less than the available data, only copy count bytes to buf and ignore the rest.
    • Return the number of bytes copied to buf if successful, -EFAULT if copying fails, or -EINVAL if a parameter is invalid.
    • f_pos is unused.
    • Print “scull read” at level KERN_INFO just before the entry data is copied to buf.

    Because the size of the queue elements (ELEMSZ) is not known at compile time, you will need to do pointer arithmetic when updating the start pointer after a read.

    Also make sure that start properly wraps around at the end of the array back to the beginning, as necessary, to correctly implement a circular buffer.

  3. Implement the scull_write (producer) message queue operation in the device driver.

    A placeholder function is already in driver/scull.c that currently does nothing except print a message in the kernel log. Complete this function to perform the following:

    • Produce a message by copying count bytes from buf into the next empty queue entry, or block if the queue is full. If count is greater than ELEMSZ, only copy ELEMSZ bytes and ignore the rest.
    • Return the number of bytes copied if successful, -EFAULT if copying fails, or -EINVAL if a parameter is invalid.
    • f_pos is unused.
    • Print “scull write” at level KERN_INFO just before data is copied from buf to the entry.

    Again, because the size ELEMSZ of the FIFO elements is not known at compile time, you will need to do pointer arithmetic when updating the end pointer after a write.

    Also make sure that end properly wraps around at the end of the array back to the beginning, as necessary, to correctly implement a circular buffer.

  4. Add synchronization code to scull_read and scull_write to ensure safe concurrent access to the message queue, as we saw in class in the concurrency lectures. Use sleeping / waking synchronization functions, not busy-waiting ones.

    You must use only semaphores and mutexes for synchronization (otherwise you will lose points) and use the interruptible variants (both for semaphores and mutexes), so that the functions can be interrupted if you decide to terminate the processes early using a signal (e.g., through Ctrl-c from the keyboard).

    Make sure your code checks and returns an appropriate error on early termination, and does not leave any semaphore or mutex still locked!

4 - Part 2: Modifying the User-Space Test Programs

  1. Modify the code of the producer (inside the src directory) to use your own name as the message rather than “Ryan Tsang” (nothing else). Note how the string is written to the message queue without the trailing \0 character.

  2. Modify the code of the consumer so that it reads (and prints) the complete data from a queue element.

    Do not assume that the consumer program knows in advance the size of each queue element. The driver already implements an IOCTL command (SCULL_IOCGETELEMSZ) to return the size of a queue element (ELEMSZ) to user-space processes and this is what your code must use to learn the maximum size allowed for a message. Use this IOCTL command in the consumer code to dynamically allocate a user-space buffer of the right size before reading a queue element.

    Make sure that a \0 exists at the end of the data in the buffer before printing the data.

    Also make sure the user-space buffer is properly deallocated when it is not needed anymore.

5 - Part 3: Testing the Message Queue

  1. Load the module with a large scull_fifo_size and a small scull_fifo_elemsz. Start 2 producers and then 2 consumers. For example:

    $ sudo insmod ../driver/scull.ko scull_fifo_size=10 scull_fifo_elemsz=3 
    $ ./producer p 2 
    Device (/dev/scull) opened 
    write: Ryan Tsang
    write: Ryan Tsang
    Device (/dev/scull) closed 
    $ ./consumer p 2 
    Device (/dev/scull) opened 
    read: Rya 
    read: Rya 
    Device (/dev/scull) closed

    You must provide a single screenshot that shows a Debian terminal window that shows output similar to what is shown above (including the insmod command used), followed by the output of the id command.

  2. Reload the module with a large scull_fifo_size and a large scull_fifo_elemsz. Start 2 producers and then 2 consumers. For example:

    $ sudo insmod ../driver/scull.ko scull_fifo_size=10 scull_fifo_elemsz=30 
    $ ./producer p 2 
    Device (/dev/scull) opened 
    write: Ryan Tsang
    write: Ryan Tsang
    Device (/dev/scull) closed 
    $ ./consumer p 2 
    Device (/dev/scull) opened 
    read: Ryan Tsang
    read: Ryan Tsang
    Device (/dev/scull) closed

    You must provide a single screenshot that shows a Debian terminal window that shows output similar to what is shown above (including the insmod command used), followed by the output of the id command.

  3. Open 3 terminal windows, one for showing the kernel log, one for reloading the module and starting the producers, and one for starting the consumers.

    1. Reload the module with scull_fifo_size=2 and scull_fifo_elemsz=30.

    2. Start 5 producers and show that some of them block waiting for consumers in kernel log. Use Ctrl-C to kill the remaining producers.

    3. Then start 5 consumers and wait until they block. Use Ctrl-C to kill the remaining consumers.

    Show in the kernel log that some of them print messages while the remaining consumers block waiting for producers. For example:

    Figure 2: Screenshot of blocked, then killed producers and consumers.

    You must provide a single screenshot that shows a Debian terminal window that shows output similar to what is shown above (including the insmod command used), followed by the output of the id command.

  4. Clear the terminal windows for the producer and consumer processes.

    1. Reload the module with the same values for scull_fifo_size and scull_fifo_elemsz as in the previous test.

    2. Start 5 producers in the first terminal. When they block, do not kill the process.

    3. Then start 5 consumers in the second terminal and allow the processes to complete.

    Show that all blocked producers and all consumers then terminate, and that the reads and writes are interleaved in the kernel log. For example:

    Figure 3: Screenshot of producers and consumers with interleaved reads and writes

    You must provide a single screenshot that shows both Debian terminal windows that show output similar to what is shown above (including the insmod command used), followed by the output of the id command (in either of the two terminal windows).

  5. You should also check that the same thing works fine if you start the 5 consumers before starting the 5 producers (no need to provide any screenshot for this).

6 - Deliverables

Once both your kernel module and your user-space test program work, execute make clean in both the ~/<login>-pa5/driver/ and ~/<login>-pa5/src/ directories to delete any extraneous files there (replace <login> with your student login name, of course).

In the top level of the same ~/<login>-pa5 submission directory, create a PDF file named screenshots.pdf that contains:

  1. Your full name.

  2. The Stevens Honor pledge.

  3. The four screenshots you created above: one for each of Listing 1, Listing 2, Figure 2, Figure 3. Make sure the screenshots are clearly readable.

  4. Also add a short explanation before each screenshot so the Course Assistants know what you are trying to show in those screenshots.

At this point the ~/<login>-pa5 directory must contain all the files you were given in the original zip file (with some of them modified by you, of course), plus your PDF file containing the screenshots, nothing more, nothing less.

For example:

rtsang1-pa5
├── Makefile
├── screenshots.pdf
├── driver
│   ├── Makefile
│   ├── scull.c
│   └── scull.h
└── src
    ├── Makefile
    ├── producer.c
    └── consumer.c

Create your submission zip file by running make zip at the top level of the directory.

Once you have correctly created the file <login>-pa5.zip, copy it to the host OS using your shared folder, double-check its content to make sure it contains everything, then submit it on Gradescope.

7 - Rubric

60% Code for Section 3
20% Code for Section 4
20% Screenshots for Section 5

You do not get points for screenshots unless the corresponding code is submitted too.

Screenshots alone will not get you any points at all. So make sure you double check everything before you submit on Gradescope.