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.18.6-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 4 non-trivial commits to your GitHub repository for the assignment. These four commits must be made on different dates and at least two must be completed by Wednesday, March 6th. You may make more than four commits during the timeline of the project — four is only the minimum that will be required for full credit.
A non-trivial commit is defined for this assignment as one that meets all of these requirements:
- Does not contain only documentation (i.e, just committing a README file does not count).
- Does not contain only Makefile modifications or creation.
- Modifies/creates at least 10 lines of code in a combination of existing or newly created .c or .h files. That is to say, creating a new file with 10 lines of code counts, but creating a new file with a 10 line comment does not.
- Code modifications/creation must be relevant to the project. Creating a bunch of useless files/functions that are unrelated or otherwise superfluous to the assignment does not count. It is ok to reorganize your code after you have started and remove pieces of code, of course, but if you are obviously only adding code to the repository early on that you completely delete later (or that has nothing to do with the assignment), then that commit will not count toward the requirements herein.
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 as well as those modifying access control lists for mailboxes. If a regular user account attempts to call any of the prohibited system calls, then they must be given an error indicating that they have been denied that permission such as -EPERM.
Mailboxes will start with no access control lists. Process IDs may be added to a mailbox’s ACL only by the root user. Attempts to add process IDs to the ACL for a mailbox are not gated by the ACL — that is to say that as long as the process is running as root, it can modify the ACL of any mailbox. Any attempt to modify the ACL of a mailbox by any process running as any user other than root must return an error indicating that they have been denied that permission such as -EPERM.
If an ACL has not been set up on a mailbox, then any process can access that mailbox. That means that any process can send/receive messages from that mailbox, count the messages in that mailbox, get the length of the first message in the mailbox, and see it in any mailbox lists.
As soon as a process has been added successfully to an ACL for a mailbox, operations on that mailbox are gated by the ACL. No processes other than those on the ACL shall be allowed to send/receive messages, get lengths/counts of messages, or even see the mailbox ID in a list of mailboxes, unless that process is owned by root — processes running as root have access to all mailboxes at all times. If the ACL for a mailbox has been emptied after setting it up, that mailbox still is controlled by its empty ACL — that is to say that no processes that running as any non-root user shall be able to access that mailbox until another process ID is added to the ACL.
Your IPC mechanism will optionally use an encryption algorithm known as the Extended Tiny Encryption Algorithm (XTEA) in order to encrypt data for storage in the mailbox. By optionally, we mean that on mailbox creation it will be specified if encryption is used or not — you must use the specified encryption algorithm if it is requested on mailbox creation it is not an optional part of this assignment to implement this encryption scheme.
The Extended Tiny Encryption Algorithm is a simple encryption algorithm that has a key length of 128 bits and operates on blocks of data that are 64 bits in size. As messages can be of arbitrary size in your mailbox system, you will have to apply the XTEA algorithm in a loop in order to process messages larger than 64 bits (8 bytes) in size. To deal with messages that are of a size not divisible evenly by 8 bytes, you should pad the end of the message with zero bytes (you should store the original length with your messages so as not to ever reveal this padding to programs using your system calls).
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. You must not store this key along with the message in your IPC system’s data structures in the kernel. The key will be passed in as an array of 4 32-bit integers and will have to be read from the user space buffer before use.
You may use the code included below in order to implement the XTEA algorithm in your assignment (which is adapted from the public domain source code presented in the Wikipedia article and the original XTEA reference code). These functions will need to be called for every 64-bits of your message data (so, you will have to call them in a loop).
You must make sure that all encryption and decryption steps take place completely within the kernel’s memory space. That is to say that you should never attempt to encrypt or decrypt from or to a user-space buffer directly, nor should you attempt to use the key from user-space without copying it into the kernel’s memory first. Doing any of these things would be a serious lapse in security!
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 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. Messages are binary data and should not be treated as text strings — this means that messages may have zero bytes (also known as NUL terminators) embedded within them. To this end, you should not be using any string related functions on them (such as strlen() or strcpy()).
Each mailbox will store its messages in FIFO order. That is to say that each mailbox should be seen as a queue.
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 or otherwise invalid 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. Also, kfifo will not be useful to you at all — seriously, don’t confuse yourself by even looking at kfifo.
The signature and semantics for your system calls must be:
- long create_mbox_421(unsigned long id, int enable_crypt): creates a new empty mailbox with ID id, if it does not already exist, and returns 0. The queue shall be flagged for encryption if the enable_crypt option is set to anything other than 0. If enable_crypt is set to zero, then the key parameter in any functions including it shall be ignored (they may be NULL).
- long remove_mbox_421(unsigned long id): removes mailbox with ID id, if it is empty, and returns 0. If the mailbox is not empty, this system call shall return an appropriate error and not remove the mailbox.
- long mbox_add_acl_421(unsigned long id, int proc_id): adds the process with PID proc_id to the access control list for the mailbox with ID id and returns 0. If the process is already in the ACL for the specified mailbox, this system call shall return an appropriate error.
- long mbox_del_acl_421(unsigned long id, int proc_id): removes the process with PID proc_id from the access control list for the mailbox with ID id and returns 0. If the process is not in the ACL for the specified mailbox, this system call shall return an appropriate error.
- long count_mbox_421(void): returns the number of existing mailboxes.
- long list_mbox_421(unsigned long __user *mbxes, long k): returns a list of up to k mailbox IDs that the calling process can access in the user-space variable mbxes. It returns the number of IDs written successfully to mbxes on success and an appropriate error code on failure.
- long send_msg_421(unsigned long id, unsigned char __user *msg, long n, uint32_t __user *key): encrypts the message msg (if appropriate), adding it to the already existing mailbox identified. Returns the number of bytes stored (which shall be equal to the message length n) on success, and an appropriate error code on failure. Messages with negative lengthsshall be rejected as invalid and cause an appropriate error to be returned, however messages with a length of zero shall be accepted as valid.
- long recv_msg_421(unsigned long id, unsigned char __user *msg, long n, uint32_t __user *key): copies up to n characters from the next message in the mailbox id to the user-space buffer msg, decrypting with the specified key (if appropriate), and removes the entire message from the mailbox (even if only part of the message is copied out). Returns the number of bytes successfully copied (which shall be the minimum of the length of the message that is stored and n) on success or an appropriate error code on failure.
- long peek_msg_421(unsigned long id, unsigned char __user *msg, long n, uint32_t __user *key): performs the same operation as recv_msg_421() without removing the message from the mailbox.
- long count_msg_421(unsigned long id): returns the number of messages in the mailbox id on success or an appropriate error code on failure.
- long len_msg_421(unsigned long id): returns the length of the next message that would be returned by calling recv_msg_421() with the same id value (that is the number of bytes in the next message in the mailbox). If there are no messages in the mailbox, this shall return an appropriate error value.
See the <linux/syscalls.h> file for more information about these macros.
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. Suggested error codes for several error conditions are listed below (this does not necessarily cover all error cases you might encounter):
- -EPERM: Permission denied
- -ENOMEM: Out of memory during an allocation
- -EFAULT: Supplied an invalid pointer or one that cannot be read/written for the entire requested length
- -ENOENT: Invalid mailbox id specified
- -EEXIST: Mailbox already exists on creation
- -ENOTEMPTY: Mailbox not empty on deletion
The kernel must be very careful with memory access. Remember that users often don’t properly error check their code very well and that malicious users do also exist. You should be very careful in your code to ensure that any pointers that come in from user-space (all marked with __user above are checked sufficiently. Also, you should ensure to not leak private information outside the kernel, such as encrypted messages. All of your encryption and decryption MUST occur in memory within the kernel’s memory space — not in any user-space memory. Also, it is up to the user to provide the key for both encryption and decryption. You MUST NOT store the key with the messages in the kernel. If the user specifies a different encryption key for encryption and decryption, the user should expect to get a scrambled message back. Finally, 0 is a perfectly valid encryption key — mathematically it just won’t change the message at all.
USER-SPACE DRIVER PROGRAM(S)
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:
- The Linux Kernel API — documentation of the internal API for programming in the Linux kernel (Especially useful is the chapter on user-space memory access and the chapter on linked lists within the kernel)
- The Linux Cross-Reference (for version 4.18.6 of the kernel) — a cross-referenced copy of the Linux kernel source code for relatively easy searching
- The Open Group Base Specifications Issue 7/IEEE Std. 1003.1 – 2008, 2018 Edition/POSIX.1-2008
- The Unreliable Guide to Locking [in the Linux Kernel]
- Kernel Korner: System Calls — old and outdated, but still demonstrates the concepts used for system calls
If in doubt, the Kernel API and Linux Cross Reference should be your ultimate guides.
WHAT TO DO IF YOU WANT TO LOSE POINTS ON THIS PROJECT
Any of the following will cause a significant point loss on this project.
- 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.
- Failure to follow the requirements in the “Incremental Development” section of the assignment.
Please do not make us take off points for any of these things!
HERE ARE THE NEEDED FILES “
Last Updated on March 26, 2019 by EssayPro