Principles of Operating Systems

Introduction/Objectives

In this project, you will be creating a virtual device driver in the form of Linux a loadable kernel module. Your loadable kernel modules will implement a virtual character device to perform a specific task. The Linux kernel source code contains the code for several different character device drivers that you may reference in developing your driver for this project, such as those for /dev/rtc, /dev/urandom, etc.

Before you begin, you must create your repository for Project 3 by using the appropriate link on Piazza for your section of the class. As this project will be building what is called an "out-of-tree" Linux device driver, you will not be cloning the full Linux source code into your repository as you did for Project 2.

Initial Setup

You will need to compile the kernel exactly one time to complete this project. If you still have your vanilla-project2 around unmodified from the beginning of Project 2, you may use that to build the one kernel you will need for this assignment. If you do not have an unmodified vanilla-project2 directory still, please re-create it following the instructions in Project 2, but do not change the origin of the repository or copy it to a project2 directory.

Before you get started, reboot your VM and select the Advanced option on the boot menu to pick the default Debian 4.19.0 kernel (use whichever is the newest version of it, but make sure to select the option that doesn't say anything about fallback or recovery). Then, uninstall any still installed project kernels you may have from Project 0 or Project 2 with the following two commands (type these commands very carefully!):

sudo apt-get purge linux-image-5.5.0\*
sudo apt-get purge linux-headers-5.5.0\*

Now, go to your vanilla-project2 directory and follow steps 1-4 of building the kernel that you did for both Project 0 and Project 2. However, instead of running make bindeb-pkg, you must run make deb-pkg to ensure that you get a proper linux-headers package, linux-libc-dev package, and a linux-image package. To clarify, you are only performing the build instructions starting with make mrproper, you have no need to reinstall packages, set up sudo or git configurations, or anything else like that. You are not to change anything about the kernel code itself for this project. You are not to change the version string or any other kernel source code!

Once the build has finished, install the resulting linux-image-5.5.0, linux-headers-5.5.0, and linux-libc-dev packages with sudo dpkg and reboot your VM. You should now be booted into a clean copy of the 5.5.0 kernel by default.

You may now clone your repository for Project 3 by running the following set of commands (putting your GitHub username in where appropriate):

cd /usr/src
git clone git@github.com:umbc-cmsc421-sp2021/project3-YourGitHubUsernameGoesHere project3

Incremental Development

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 in a day — 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 a source control system for incremental development.

You are required 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. If in doubt as to whether a particular approach is feasible, you are encouraged to reach out to your TAs to ask their opinion.

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. Students doing either of these tend to get poor grades on their assignments. To this end, we are requiring you to make at least four non-trivial commits to your GitHub repository for the assignment. These four commits must be made on different dates and at least one must be done before Wednesday, April 7th at 11:59:00 PM EDT. You may make more than four commits during the timeline of the project — four is simply a minimum number 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). However, you may have a single commit count for significant work on your preliminary design document, as specified below.
• 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.
• Commits containing code implementing testing drivers or other such user-space code do count.

Project Design (30% of Project 3 Grade)

As a part of this project, you are required to produce two design documents explaining your choices for designing the code for this project. The first of these design documents is a preliminary one explaining how you intend to tackle the project. This document is expected to be less detailed than your final design document, but still detailed enough as to give the TAs some insight on your intended design for the project. The idea here is that you preliminary design document will be turned in early on during the project so that the TAs can critique it and suggest possible pitfalls in your approach.

Elements that we expect to see in a preliminary design document include the following:

• A basic description of the project itself and what you are expected to produce.
• A brief description of what a character device is in the Linux kernel, how they interact with user-space, and the required functions to implement (you will need to do a little bit of research on your own here).
• Ideas for how to implement the required algorithms that will be used to accomplish your device driver's task.
• Ideas of how to store the data required to accomplish your driver's task.
• A rough estimate of how many lines of code it will take to implement the driver, divided up by various functions you will be required to implement.
• Any references you have cited in preparing the design document.

We are not specifying any specific template for the preliminary design document beyond these requirements for what it must contain. You may use whatever widely accepted citation style that you would like (APA, MLA, etc). We do however expect your document to be of a sufficient length to explain the requirements we have outlined above. To this end, we require that your document be at least 2 full double-spaced pages with a standard 12 point font (Helvetica, Times, Arial, or Times New Roman are the only acceptable font choices without approval from the TAs ahead of time), with no larger than 1 inch margins on normal letter (8.5 inch x 11 inch) sized pages. You may include diagrams as needed (hand-drawn or computer-generated), but these do not count toward your required page count). Additionally, title pages, tables of contents, etc do not count toward the required page count. Please see the top of the project for the due date of the preliminary design document! Your preliminary design document must be placed in the root of your GitHub repository and MUST be a PDF file named preliminary.pdf.

Your final design document will essentially be a more fully specified version of the preliminary design document. You are expected to complete your final design document as you are completing or after you have completed the code, so it should be reflective of the actual state of what you turn in for the assignment. In addition to the requirements outlined above for the preliminary design document, you should include a section explaining how your final design changed from the preliminary design and why you made those changes. Also, your final design document should explain any places where you ran into issues developing your project and any shortcomings it might have. Finally, if you have completed any of the extra credit on the project, you must document it in your final design document, or no credit will be given for it. Be sure to explain the implementation details of your extra credit if you attempt any of it!

As your final design will be more detailed, we expect it to be of a more significant length as well. Your final design document must be at least 4 full double-spaced pages, following all of the other formatting requirements outlined above for the preliminary design. Your final design document must be placed in the root of your GitHub repository and MUST be a PDF file named design.pdf.

Reversi Kernel Module (70% of Project 3 Grade)

In this assignment, you will be implementing a kernel module that can be used to play against the CPU in a game of Reversi (aka Othello). This module will implement a virtual character device (with a corresponding entry in /dev that the user can open a file descriptor to), which will be interacted with by the user using normal file read and write operations. The module will work on the principle that the user opens a file descriptor to the module's /dev entry (which shall be named /dev/reversi), writes commands to that file descriptor with the write() system call, and reads the responses to those commands with the read() system call. To this end, the module must keep track of the state of the game board, implement logic to read and parse commands, check the validity of any commands, and check if the game is over (either in the case that one player wins or there is a draw). Your module must be named reversi.ko once it is compiled.

A minimal solution to this project does not have to implement any sort of AI to determine what move to make when it is the computer's turn. It may simply choose a random valid move. However, the CPU and user player must be required to always make valid moves (or pass their turn if no valid move exists).

The set of commands that your module must support the user executing from user-space, as well as the expected responses are described below. Each command consists of a two-digit command code followed by any arguments that are required for the command, and ends with a newline ('\n') character. Please note that you should always check the data sent in by the user for validity!

Your code may make the assumption that no more than one command is ever present in one write to your module and that if a write does not end in a newline character that it is invalid. Additionally, if multiple writes to your device occur without an intervening read, you shall return only the most recent response when a read does come in. Note that in the base requirements, no distinction is made between open file descriptors referring to your device.

• 00 X/O — Begin a new game. Resets the game board to the initial state. Takes one argument specifying whether the user wishes to play as "X" (who places dark colored discs and goes first) or "O" (who places light colored discs and goes second). This command will set the game board to the standard opening for a game of Othello. Responds with "OK\n" on success.


• 01 — Returns the current state of the game board. Takes no arguments. Responds with the current state of the game board as a string of sixty-six characters followed by a newline. Each of the first sixty-four characters represents one square of the game board and shall contain an 'X', 'O', or a '-' character ('X' for a space occupied by a dark colored disc, 'O' for a space occupied by a light colored disc, and '-' for an unoccupied space). Spaces shall be listed starting with the top row (starting from the left), continuing to the right end of the top row, then continuing on to the next row and so on until the entire board has been written out. The remaining two characters shall be a horizontal tab ('\t') character followed by either an 'X' or an 'O' which represents the player who has the next move.


• 02 C R — Specifies a move for the player. C and R shall be numbers between 0 and 7 representing the column and row that the player wishes to choose for their turn. Responds with "OK\n" if the move specified by the player is valid (and the user has not won), "WIN\n" if the move specified by the player is valid and the player has won by making that move, "TIE\n" if the move specified by the player is valid and the game has ended in a draw, "LOSE\n" if the move specified by the player is valid and the game has ended with the CPU player winnning, "ILLMOVE\n" if the move specified by the player is not valid (for instance if there is already a mark in the specified square or an invalid coordinate is specified), "OOT\n" if the user is attempting to move outside of their turn, or "NOGAME\n" if the game has not been started or is otherwise over. If you believe that there are other error cases that we have not described above, please document them in your README file for the project and the design document (error codes shall be textual strings that end with a newline character and contain no more than 8 characters before the newline). In the case of any error condition, the state of the game should not be changed in any way. It shall still be the user's turn if it was their turn and no marks on the board shall change.


• 03 — Asks the computer to make a move. Responds with one of the responses documented above for the 02 command, as appropriate (however, the "ILLMOVE\n" error shall never be returned from this command — the computer shall never attempt to make an illegal move). This command takes no arguments. Responses such as "WIN\n" and "LOSE\n" still refer to the human player from this command, not to the CPU.


• 04 — Pass the user's turn because no valid moves exist. If a valid move exists for the player, responds with "ILLMOVE\n" and does not modify the game's state. Otherwise responds as does the 02 command above for the state of the game after the move.

Any illegal commands shall respond with "UNKCMD\n". Improperly formatted commands shall respond with "INVFMT\n". If you wish to add additional error codes not covered here, document them in your README and your design document. All error codes must end with a newline character and be no more than 8 characters long (not counting the newline).

Commands must match the input and output described above exactly to be considered valid. It is not valid to change the output of the 01 command to return the data in a pictorial representation, for instance — this would be something that should be handled in a user-space program that interacts with your character device. If the input to your character device does not match exactly the format described above, then you shall return an invalid format error.

If you wish to add any additional commands to this list (for debugging purposes, for instance), the command code used must be two digits long and must start with a number greater than or equal to 7. Please document any extra commands you add in your README and your design document. Note: You must not make any additional commands required to be called in a normal playthrough of the game — our testcases will not call any such extra commands.

The board shall be oriented such that coordinate (0, 0) corresponds to the upper left corner of the board and such that coordinate (7, 7) corresponds to the lower right corner of the board, as shown in this diagram (which matches the description given for the 01 command):

 (0, 0) | (1, 0) |  ...  | (7, 0)
----------------------------------
 (0, 1) | (1, 1) |  ...  | (7, 1)
----------------------------------
                ...
----------------------------------
 (0, 7) | (1, 7) |  ...  | (7, 7)

As an example of how this works, please refer to the following example. Lines that start with > are written to the device with write(), whereas lines that start with < are read from the device with read(). Each line below ends with a single newline character (and the greater/less than signs are not included as a part of the data — they are only there for illustrative purposes).

>00 X
<OK
>01
<---------------------------OX------XO---------------------------    X
>02 3 2
<OK
>02 0 0
<OOT
>01
<-------------------X-------XX------XO---------------------------    O
>03
<OK
>01
<-------------------X-------XX-----OOO---------------------------    X
>02 0 0
<ILLMOVE
>03
<OOT
>02 3 5 7
<INVFMT
>02 3 5
<OK
>02 3 5
<OOT
>03
>OK

Required Documentation

You must include a README file in the root of your repository for this assignment, documenting anything that you feel would be useful to tell us as a part of grading the assignment, as well as any references outside of the course materials that you may have used in the development of this assignment. This is not meant to be a rehash of your design documents, and only should include details relevant to grading.

Program to interact with the module

In order to qualify for any extra credit, you must make a reasonable attempt to complete all of the required portions of the assignment (including the required design documentation). If you do not complete any portion of the assignment, including required documentation, you will not qualify for any extra credit you attempt! Extra credit on this assignment is not designed to help you make up for not attempting parts of the assignment that may be more difficult.

Any extra credit earned on this project will be applied toward the grade you receive on the assignment. That is to say, it is possible to earn more than a 100% on this assignment.

As this is extra credit, the TAs and instructors will not answer any technical questions about it. Clarification questions are fine, but we will not help you implement the extra credit in any way. Do not ask.

Each of the extra credit options below are independent from one another (with one minor exception). You may implement as many or as few of these options as you wish to implement for extra credit. Just remember to document in your design document and your README file any extra credit you attempt or you will not receive credit for it!

Two Player Reversi — 2% of final project grade

To complete this option, you must allow for two human players to participate in one game of Reversi against each other. The CPU will not be involved in a two human player game of Reversi. To do this, you will be adding a few new commands to support a second player, as detailed below:

• 05 — Begin a new two-player game. Resets the game board to the initial state. This command replaces the 00 command for a two player game (00 will still be used to start a single-player game). This command will set the game board to the standard opening for a game of Othello. Responds with "OK\n" on success.
• 06 C R — Specify a move for player 2, who plays with the light colored pieces. The semantics of this command are the same as for the 02 command, but for the second player.
• 07 — Pass the second player's turn because no valid moves exist for the player. The semantics of this command are the same as for the 04 command, but for the second player.

Allow multiple games at once — 3% of final project grade

To complete this portion of the extra credit, you must allow for multiple open file descriptors to the /dev/reversi file to each represent their own game. That is to say if there are five different programs on your VM each opening a file descriptor to /dev/reversi then there will be five different game sessions in progress. Moves from one game should not affect any other games.

Allow saving/resuming of games of Reversi — 5% of final project grade

To complete this portion of the extra credit, you must implement an additional command to serialize the entire playthrough of a game as well as one to deserialize it. This means that the command will open a file and write out to that file the exact commands that have been used (successfully) to mutate the game board to the state it is in when the request is made. As the normal 03 command does not capture the moves made by the AI player, the 06 command from the first part of this extra credit must be used to represent any AI moves (this is the exception mentioned above). To implement this portion of the extra credit, you must store every move made in every game and keep track of the ordering of those moves. Your save files will consist of only the following commands: 00, 02, 04, 05, 06, and 07 (games that are completed may also be saved). Each line of the file should be terminated by a newline character. To implement this functionality, you must add the following new commands to your program to serialize and deserialize game state:

• 08 filename — saves the game state to the specified filename on the filesystem. The file should be created if it does not exist and shall be overwritten in its entirety if it does exist. If the file is created, it shall be owned by the same user id as the calling process and must be at least readable/writable by that user. Responds with "OK\n" on success or "FILEERR\n" on any errors in creating/writing to the file. Does not change the state of the game in any way — you must allow this command to be called and then for the game to continue on afterwards. The filename given shall be an absolute path (you may return an appropriate error if the filename given does not begin with a / character).
• 09 filename — loads the game state from the specified filename on the filesystem. Responds with "OK\n" on success, "FILEERR\n" on any errors in opening/reading the file, or "PARSEERR\n" on any errors in parsing the file. You may leave the system in an indeterminate state if any errors occur while parsing the file. The filename given shall be an absolute path (you may return an appropriate error if the filename given does not begin with a / character).

Reversi AI — up to 10% of final project grade

To complete this portion of the extra credit, you must implement an AI that applies some form of computation to determine moves and document what the strategy you implemented does. The more complex the strategy employed (and stronger the AI that you produce is at Reversi), the more points you can earn here. This part of the extra credit is fairly open-ended in what you can do and how many points that can be earned. Let your imagination (and perhaps experience in other classes) go wild here! Just make sure to fully explain your implementation in your design document.

Submission Instructions

The submission of this project follows the same procedures that you have used on previous projects of adding, committing, and pushing your git repository for the assignment.

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

References

Below is a list of references that you may find useful in your quest to complete this project:

Online Research vs. Plagiarism

Students are allowed to research operating system concepts online and use the knowledge to write their own code. Any sources must be cited in the README file and the relevant design document(s).

• It is not okay to copy code.
• It is not okay to copy code and minimally change it in ways such as renaming variables or functions.
• It is not okay to use an online source and not cite it properly.

There are many ways to use different syntax or different logic to achieve the same semantics. Students must create their own code. Any submissions that contain similar code between two or more students or similar code to an online source will be considered plagiarism.

Any suspected cases of plagiarism will be referred to the office of academic integrity.

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.

• Requiring that changes be made to the kernel sources.
• Extraneous files are included.
• Files are missing that needed to be included.
• Failure to follow the requirements in the "Incremental Development" section of the assignment.
• Any form of cheating or plagiarism.

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