Principles of Operating Systems

CMSC 421-04 - Spring 2016

Project 1

Due by 11:59PM EDT on Tuesday March 29, 2016

Changelog:

Wednesday, March 9 @ 6:30PM EST — added XOR cipher reference

Tuesday, March 22 @ 1:09PM EDT — fixed a typo in the XOR section

Sunday, March 27 @ 1:00AM EDT — updated submission instructions

Introduction/Objectives

In this project, you will create a new version of the Linux kernel that adds various system calls that relate to interprocess communication. While the kernel does already provide IPC-related calls, we wish to have a bit more control over the process. To that end, you will be implementing a relatively simple message passing interface that can be queried asychronously by multiple processes. In addition, this message passing interface will support some basic encryption to keep messages from those who shouldn't see them.

Before you begin, be sure to create your new GitHub repository for Project 1 by using the link posted on the course Piazza page. Then, follow the same steps you did in Project 0 to clone this new repository (obviously, substitute project-1 for project-0 from the earlier instructions). Also, you may remove the /usr/src/vanilla-project0 directory and create a new /usr/src/vanilla-project1 directory with the newly checked out code.

As a first step, change the version string of the new kernel to reflect that it is for Project 1. That is, make the version string read 4.4.1-cmsc421project1-USERNAME (substituting your username where appropriate).

Please refer to the various resources on the course website that have been added since Project 0. Specifically, the Kernel API documentation, Unreliable Guide to Locking, Linux Cross Reference, and the Kernel Corner reference should be helpful. You should note that some of this documentation is fairly old, but the concepts are still good. If in doubt, the Kernel API and Linux Cross Reference should be your ultimate guides. The section on User space memory access in the API documentation is especially useful.

Encryption

The encryption algorithm that you will be implementing is exceedingly simple. What you will be implementing is a very simple XOR cipher. Your cipher will process data in 32-bit blocks -- that is to say that the key you will be encrypting and decrypting with is 32-bits in size. Messages should be padded (virtually) to 32-bit increments when encrypting. You are not required to (nor should you) store any encrypted padding bytes — truncate messages back to the original message size before storing them. See here for another description of how an XOR cipher works (which is geared directly to your project).

Each message in the system will have a separate key that is passed in to the kernel when the message is input into the system. In order for the data to come out in the clear, the same key must be passed in when retrieving the message.

As a brief example of how this cipher works, please refer to the following:

Data Passed in (6 bytes): 0xDE 0xAD 0xBE 0xEF 0x12 0x34
Key: 0x1BADC0DE
Data stored: 0xC5 0x00 0x7E 0x31 0x09 0x99

New System Calls

You will add a few new system calls for managing mailboxes of IPC messages. The mailboxes and their contents all exist only in the Kernel address space. You will develop the system calls specified below in order to access the mailboxes and their contents by user processes. Each mailbox should be identified by an unsigned long value, which is passed in at creation time. Each mailbox can store an "unlimited" number of messages, each of which can be of "unlimited" length. Messages should be stored and retrieved in FIFO order. The signature and semantics for your system calls must be:

long create_mbox_421(unsigned long id): creates a new empty mailbox with ID id, if it does not already exist, and returns 0.
long remove_mbox_421(unsigned long id): removes mailbox with ID id, if it is empty, and returns 0.
long count_mbox_421(void): returns the number of existing mailboxes.
long list_mbox_421(unsigned long *mbxes, unsigned long k): returns a list of up to k mailbox IDs in the user-space variable mbxes. It returns the number of IDs in mbxes.
long send_msg_421(unsigned long id, unsigned char *msg, unsigned long n, unsigned long key): encrypts the message msg, appending it to the already existing mailbox identified. Returns the number of bytes stored (which should be equal to the message length n)
long recv_msg_421(unsigned long id, unsigned char *msg, unsigned long n, unsigned long key): copies up to n characters from the first message in the mailbox id to the user-space buffer msg, decrypting with the specified key, and removes the message from the mailbox. Returns the number of characters successfully copied (which should be the minimum of the length of the message that is stored and n).
long count_msg_421(unsigned long id): returns the number of messages in the mailbox id.

Each system call returns an appropriate non-negative integer on success, and a negative integer on failure which indicative of the error that occurred.

User-space driver program

You must adequately test your kernel changes to ensure that they work under all sorts of situations (including in error cases). You should build one or more testing drivers and include them in your sources submitted. Create a new directory in the Linux kernel tree called proj1tests to include your test case program(s). Be sure to include a Makefile to build them.

Submission Instructions

You should follow the same basic set of instructions for submitting Project 1 that you did for Project 0. That is to say, you should do a git status to ensure that any files you modified are detected as such, then do a git add and a git commit to add each modified/newly created file or directory to the local git repository. Then do a git push origin master to push the changes up to your GitHub account.

Be sure to include not only your modified kernel files, but also your driver program files. The driver should go in a proj1tests directory, in the root of the kernel source tree.

You should also verify that your changes are reflected in the GitHub repository by viewing your repository in your web browser.

What to do if you want to get a 0 on this project

Any of the following will cause a significant point loss on this project. Items marked with a * will result in a 0.

Not pushing changes to your GitHub repository by the project due date. *
Excessive unnecessary changes made to the kernel sources.
Extraneous files are included.
Files are missing that needed to be modified.
Hello World system call included, or the system calls required are otherwise out of the order specified

Please do not make us take off points for any of these things!

Last modified