Introduction

1. open an Event
2. wait and signal on Events they have opened
3. close an Event

The semantics of event_wait are that is always blocks the calling process. The semantics of event_signal are that it unblocks all processes waiting on the Event.

You will implement the data structure(s) for representing Events at the kernel-level, and you will add system calls for user-level processes to event_open, event_close, event_wait, and event_signal on Events. In addition, you will need to write user-level programs to test your Event primitives.

An individual process can have multiple Events open at a time (and can wait and signal on any of its open Events). Your Event implementation, however, must make sure that only processes that open an Event can wait, signal, or close the Event.

I strongly encourage you to get an early start on this project; your solution will require a fair amount of thinking time, linux code reading time, and code design and debugging time.

Implementation Details:

To implement support for Event primitives, you need to create kernel data structure(s) to keep track of Events that have been created (i.e. an Event table), to keep track of which processes currently have the Event open, to keep track of which processes are currently blocked on an Event, etc. Typically, the kernel uses fixed-sized data structures to keep track of instances of abstractions that it implements. For example, there is an open file table to keep track of all currently open files in the system. Because these data structures are fixed-sized, there is an upper bound on the number of instances that can currently exist in the system (e.g. there is a maximum number of open files). Implement your Event Table data structure so that it is fixed-sized, and make its size small (~5) so that you can test that you are handling the case when a process requests to open a new Event, but there are already 5 active Events (each has at least one open). When an Event is closed for the last time, it is no longer an active Event, and space for it in the Event Table can be used by a subsequent newly created Event.

Creating an Event Table

#include <linux/init.h>
void __init event_init();   	// this is NOT a system call 

Dynamic Memory Allocation in the Kernel

Memory leaks in the kernel are very, very bad; make sure that if you add a call kmalloc you add a corresponding call to kfree somewhere. Also, it is good programming practice to set a variable's value to NULL after freeing the space to which it points: free(ptr); ptr = 0; .

Event System call

1. long event_open(int *id): if *id==0, then create a new Event, and set the id to the new Event's ID. If *id is positive, open an existing Event with a matching id value. The function returns 0 on success, or an error value on failure. Return different error values to indicate different types of failure (you may use error values already defined in error.h, for example: return -ESRCH;). Remember, that you need to verify that values passed by reference to your system calls refer to readable/writable memory before you read/write to it (see project 2 if you forgot how to do this). A process can only open the same event 1 time.

2. long event_close(int id): closes the corresponding Event. The last close to an Event, destroys the Event (you could re-use its id for a subsequent event_open call that is passed a value of 0). Only processes that have the Event open can close the Event. Also, the last close should fail if there are waiters on the Event. The function returns 0 on success, or an error value on error.

3. long event_wait(int id): blocks the calling process on the Event with a matching id (again the caller must have opened the Event before it can wait or signal or close it). The function returns 0 on success, or an error value on error.

4. long event_signal(int id): wakes up all processes blocked on the event with the matching id. The function returns 0 on success, or an error value on error. Again, only processes that have opened the Event can signal on it.

5. long print_event_table(): a debugging routine to print out the contents of the event table (printk). For open events, include the process ids of every process that has the event open, and print out the pid of all processes waiting on each event. returns 0 on success.

In addition, you may want to implement a print_event_table function that can be called from within your system calls to help with debugging and testing.

Blocking and Unblocking a Process (task)

You will use wait_queue_head_t data structure(s) to block processes that have done a wait on an Event.

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

1. set the process' state (in its task_struct) to TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE (you should use TASK_INTERRUPTIBLE for this assignment, which means that if the process receives a signal (like SIGKILL), it will wake up before event_signal is called on the Event on which it is blocked.
2. add the process to a wait queue associated with the Event
3. call the kernel routine schedule() to de-schedule the process and schedule another process from the READY Q to run.

To wake-up a process on an Event, you need to:

1. remove the process from its waitQ
2. set its state to TASK_RUNNING
3. call schedule() to add it to the readyQ

Wait Queues

Your solution should NOT make calls to the higher level functions interruptible_sleep_on, or sleep_on. Instead, you will implement a solution that explicitly adds a process to a waitqueue and blocks it using the 3 steps listed above. You may, however, use wake_up to wake up all waiters on a wait queue.

The wait queue data structure is a bit tricky to figure out. I suggest looking at existing code the initializes, adds and removes items from a wait queue, and draw some pictures and step through the code for init_waitqueue_head, init_waitqueue_item, add_wait_queue, and remove_wait_queue on your picture.

To iterate through the elements on a wait queue, you can use the list_for_each_safe macros, and the list_entry macro to get a pointer to the next wait_queue_t element in the list. Here are some example code fragments using wait_queues:

  // declare and init a wait Q
  static DECLARE_WAIT_QUEUE_HEAD(my_wait_Q);  

  // declare and initialize a wait_queue_t element named "wait_entry"
  struct task_struct *curtask = get_current();
  DECLARE_WAITQUEUE(wait_entry, curtask);   

  // there are functions to add and remove elements from a wait Q:
  add_wait_queue(&my_wait_Q, &wait_entry);
  remove_wait_queue(&my_wait_Q, &wait_entry);

  // you can traverse the elements of a wait queue using the underlying
  // list implementation used by the wait queue (see wait.h and list.h )
  struct list_head *tmp, *next;	
  list_for_each_safe(tmp, next, &(my_wait_Q.task_list)) {
      wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
      ...
  }

Synchronization Primitives in the kernel

 
    static DECLARE_MUTEX(event_mutex); // declare a MUTEX semaphore initialized to 1
    static DECLARE_MUTEX_LOCKED(event_mutex); // declare a MUTEX semaphore initialized to 0 

    if(down_interruptible(&event_mutex)) {
          // process woke up due to signal...semaphore was NOT acquired	
    }  
    // Critical Section Code (i.e. access shared data structures)
	  // make sure this process doesn't block while it holds the semaphore
    up(&event_mutex)) {

Other requirements

Your system calls should return error values as they did in the previous assignment (for example, return -ESRCH). It is fine to use existing error values defined in error.h that are close to but perhaps not exactly what you want for your errors. You may add new error codes if you'd like (using existing ones is fine though). User level programs should call perror to print an error message when an error value that is returned by your system calls.

Getting Started

As you design your solution, think about what a process is (or can be) doing while another process is modifying shared state associated with an Event. For example: is it possible for process i to do a wait on Event j, process k to do a signal on Event j, and process i to do another wait on Event j before it has been removed from Event j's wait queue (add itself to the wait Q more than one time)? can a process exit while it is on an Event wait queue? when does a process' call to schedule() return (what is true about the process at this point)?

I suggest incrementally implementing and testing functionality. Start with event_init, then event_open and test that a process can successfully open several Events, and that you are correctly detecting error conditions. You will likely want to add a fair amount of debugging code as you implement and test. The output from printk statements are also written to files: /var/log/messages and /var/log/kern.log.

Use good modular design...remember you can have regular kernel-level functions that your system calls call.

You should build a new kernel package for your lab3 kernel image (use a new --append-to-version flag for this project). You could start with your lab 2 kernel and add in lab 3 functionality or start with a new copy of the kernel source and add lab 3 functionality to that.

Testing:

• Multiple processes open an event
• One process waiting when event_signal is called
• No processes waiting when event_signal is called
• Multiple processes waiting when event_signal is called
• More than max number of new Event opens are attempted
• One process closes an Event which has multiple opens
• The last process closes an Event
• Trying to open/close/signal/wait on an invalid Event number

When you call system calls from your test program, get and check the return value. If the return value is -1, you should call perror to print out an error specific message.

Again, use information in /proc to help you debug your program's correctness.

Hand in

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. A brief (1 paragraph) description of how you implemented the Event synchronization primitive. Include information about any design choices you made and why you made them.
   5. A list of the source file that you modified or added (and are submitting) please list these as full path names. For example:

       
             Files I added
             -------------
             /usr/src/linux/kernel/mynewfile.c  # implementation of my new sys calls
             ...	
      
             Files I modified
             ----------------
             /usr/src/linux/kernel/existingkernelfile.c # added a call to mynewfunc in function blah
             ...
      

   6. Describe how I can find your changes to code in kernel source files you submitted (i.e. what do I search for in these files to find your changes?). Put some comments before and after your changes:

             /*************** START my changes for project 3 ***************/
                your code
             /*************** END my changes for project 3 ***************/
        

2. Copies of the test program(s) you wrote including Makefile(s). These should be well commented including descriptions the functionality that you are testing at different points in your program, and including a description of how to run your test program. You may additionally submit an output script of your test program annotated with comments describing what you are testing at each part (it is not necessary that you submit this, and only do so if you think that it helps to explain how your test program works).

3. Copies of all source and header files you added to the kernel and copies of all kernel source and header files you modified (like unistd.h). Please do not submit the entire kernel directory containing your solution, and please do not submit .o files or other binaries.

Demo

You should write an interactive test program that provides a menu of options, the user selects the next option, and then you can show the results of that action. This as opposed to writing a test program that contains all the calls you want to demo and just streams through them. The idea is to be able to stop after each system call and show me what happened as a result of that call and demonstrate that the call did what it is supposed to do.

Additionally, you may want to run a version of your kernel with debugging output that prints out the state of your Event data structures and prints out process state as wait, signal, open and close operations are executed on Events. This may help you to demonstrate that your solution is really blocking processes when it should be and really waking them up when it should be.