Due by 11:59PM EDT on Wednesday, April 5, 2017
Tuesday, March 14 — Initial version
Tuesday, March 14 — Fixed links
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 access control mechanisms to ensure the proper functionality of the message system as an IPC tool.
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 project1 for project0 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 UMBC username where appropriate).
One of the nice things about using GitHub for submitting assignments is that it lends itself nicely to an incremental development process. As they say, Rome wasn't built overnight — nor is most software. Part of our goal in using GitHub for assignment submission is to give all of the students in the class experience with using an source control system for incremental development.
You are encouraged in this project to plan out an incremental development process for yourself — one that works for you. There is no one-size-fits-all approach here. One suggested option is to break the assignment down into steps and implement things as you go. For instance, the locking/thread safety portions of the assignment can be easily added after the main functionality is implemented, in most cases. You are also encouraged to seek out the review of your TAs to determine whether an approach might be feasible.
You should not attempt to complete this entire project in one sitting. Also, we don't want you all waiting until the last minute to even start on the assignment. Doing either of these will usually lead to students getting poor grades on the assignment. To this end, we are requiring you to make at least 3 non-trivial commits to your GitHub repository for the assignment. These three commits must be made on different dates and at least one must be done during the first week that the assignment is assigned.
A non-trivial commit is defined for this assignment as one that meets all of these requirements:
Failure to adhere to these requirments will result in a significant deduction in your score for the assignment. This deduction will be applied after the rest of your score is calculated, much like a deduction for turning in the assigment with a late penalty.
Only the root user may call the creation and deletion system calls below. All other system calls may be called by any process that would be allowed and in any user context. If a regular user account attempts to call either of the prohibited system calls, then they should be given an error indicating that they have been denied that permission such as -EPERM.
Your IPC mechanism will implement a very simple encryption algorithm which each mailbox will support optionally. By optionally, I mean that on mailbox creation it will be specified whether encryption is used or not — you must implement the encryption algorithm if it is requested on mailbox creation it is not an optional part of this assignment to implement the encryption scheme. 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).
If the mailbox is specified to use encryption, each message in the mailbox 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
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 boxes 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. Upon creation, the user will specify how messages are to be stored.
Each mailbox will store its messages in either FIFO or LIFO order. That is to say that each mailbox should be seen as either a queue or a stack. Which one of these options is used shall be specified by the user at mailbox creation time.
Please keep in mind that these functions may well be called from multiple different processes simultaneously. You must provide for appropriate locking to ensure concurrent access to these functions works properly.
As this code will be part of the kernel itself, correctness and efficiency should be of primary concern to you in the implementation. Particularly inefficient (memory-wise, algorithmic, or poor locking choices) solutions to the problem at hand may be penalized in grading. In regard to correctness, you will probably find that the majority of your code for this assignment will be spent in ensuring that arguments and other such information passed in from user-space is valid. If in doubt, assume that the data passed in is invalid. Users tend to do a lot of really stupid things, after all. Crashing the kernel because a NULL pointer is passed in will result in a significant deduction of points.
Finally, you are to implement this system on your own. The IPC systems within the kernel already will not be helpful to you in implementing this assignment.
The signature and semantics for your system calls must be:
Each system call returns an appropriate non-negative integer on success, and a negative integer on failure which indicative of the error that occurred. See the <errno.h> header file for a list of error codes.
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 and instructions on how to run them in a README file within this directory. Your README for the test programs should also describe your general strategy for testing the system calls. Remember that testing is one of the primary jobs of a developer in the real world!
It is strongly suggested that you additionally build a separate program for each system call to be implemented to simply call that system call with user-provided arguments. For the data to be sent as a message, you might consider allowing the user to specify a file of data to send or a string on the command line. These programs will likely prove to be invaluable in debugging.
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 must include a Makefile that can build your test program(s) in this directory as well. You should not attempt to add your test directory to the main kernel Makefile. Also, include a README file in this directory describing your approach to testing this project. Tell us what your testcases actually test, and why you chose to test those things. If your testcases are supposed to fail at any point, make sure to tell us that in the README (after all, you should not only test your code with good inputs, but with bad ones too — we'll do just that in our testcases).
You must also include a README.proj1 file in the root directory of the kernel source code that describes anything you might want us to know when we're grading your assignment. This can include an outline of how you implemented the requirements of the project, for instance. This is also where you should cite any references you have used for the assignment other than those given in this assignment description.
You should also verify that your changes are reflected in the GitHub repository by viewing your repository in your web browser.
Below is a list of references that you may find useful in your quest to complete this project:
If in doubt, the Kernel API and Linux Cross Reference should be your ultimate guides.
Any of the following will cause a significant point loss on this project. Items marked with a * will result in a 0.
Please do not make us take off points for any of these things!
Last modified Tuesday, 01-Sep-2020 18:43:36 EDT