To implement your event primitive, you need to maintain some data structures in the kernel to track which processes have an event open and which processes are blocked on an event at any given time. To keep such structures from growing unbounded, the Linux kernel typically uses a fixed-size data structure (e.g., the file descriptor table has a maximum size). In a similar fashion, you should implement an event table data structure as a static global variable of a fixed capacity. That is, define a struct that has all the properties you need to track for one event (one row in the table) and then allocate a global, fixed-size array of those structs to represent your table. To make testing (and grading) easier, set your array to be a #defined constant size of 5.

Your table needs to track which events (numbered with indices 0-4) are currently in use. For those that are, it should track which processes have them open and which processes are waiting on them. For tracking which processes have an event open, you should use Linux’s standard linked list implementation to store a list of the processes' PIDs, and for tracking waiting processes, you should use Linux’s wait queue implementation. Both mechanisms are described in more detail below. You’re welcome to maintain extra state variables in each row or other properties about the table too, if that helps (e.g., the number of event rows currently in use).

Because multiple process might be concurrently attempting to make event-related calls, code that accesses your table or other related state variables must be considered a critical section. For this lab, you should use a semaphore to provide mutual exclusion to your table and other state from race conditions. To be clear, the semaphore should only be used to protect your kernel state structures to ensure that only one process may interact with it at a time. For blocking processes that call evnt_wait, use Linux’s wait queue. The interfaces for both are described below.

When the kernel boots, it needs to initialize all of its data structures, so you’ll need to tell it how to initialize your table and state too. For this task, you should implement an init function and then register it to be invoked on start-up, using the pure_initcall macro:

You’ll define five system calls for your event implementation. Please use the system call numbers and error codes described here so that I can grade more easily.

Like the previous lab, you’ll need to write a small application that can invoke your system calls and 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 event system calls to be made in the order you want.

You must submit ALL the files that you modified or added to the Linux kernel sources. Please make sure that all necessary files are present and that they compile without errors.

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:

For this lab, your event implementation should use exactly one semaphore to protect its event table and associated global state from concurrent access races. The semaphore interface is defined in include/linux/semaphore.h. The main items of interest for this lab are:

Each entry in your event table will 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 row in your event table 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 event open. Then, whenever a process opens an event, 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 creating a new event. 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):

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

https://medium.com/@414apache/kernel-data-structures-linkedlist-b13e4f8de4bf

https://algorithmsandme.com/linked-list-implementation-in-linux-kernel/

https://kernelnewbies.org/FAQ/LinkedLists

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:

To block a process on an event, you need to:

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

To unblock a process that is waiting on an event, you can use one of the wake_up family of macros defined in include/linux/wait.h. Given the semantics we’ve defined for events, you probably want wake_up_all.