Obtain the ASST1 distribution with git

From ASST1 onwards, we will provide you with your own git project on a CSE-owned gitlab instance running in the cloud.

Fetch the ASST1 sources from the project set up for you to work on:

% cd ~/cs3231
% git clone https://z8888888@nw-syd-gitlab.cseunsw.tech/COMP3231/25T2/z8888888-asst1.git asst1-src

We have had some technical issues with the gitlab instance. If for some reason you can't fetch the sources as above, please let us know on the forum. You can also fetch a copy from www.cse.unsw.edu.au.

% cd ~/cs3231
% git clone https://www.cse.unsw.edu.au/~cs3231/25T2/assignments/asst1-src asst1-src

If you have fetched a copy from the website, you can commit locally but cannot push your commits back to it. Here is a way to move your local commits into a repo based on the gitlab instance.

% cd ~/cs3231
% # move existing repo to backup spot
% mv asst1-src asst1-src-backup
% # clone new version
% git clone https://z8888888@nw-syd-gitlab.../... (see above) asst1-src
% # fetch commits from backup spot
% cd asst1-src
% git fetch ../asst1-src-backup
% git merge FETCH_HEAD

Configure OS/161 for Assignment 1

Configure your new sources as follows.

% cd ~/cs3231/asst1-src
% ./configure && bmake && bmake install

The above steps configure everything and build the userland binaries. We will rebuild some of the userland binaries later in the project.

We also need to configure and build the kernel. The procedure for configuring a kernel is the same as in ASST0, except you will use the ASST1 configuration file:

% cd ~/cs3231/asst1-src/kern/conf
% ./config ASST1

You should now see an ASST1 directory in the kern/compile directory.

Building ASST1

When you built OS/161 for ASST0, you ran bmake in compile/ASST0. In ASST1, you run bmake from (you guessed it) compile/ASST1.

% cd ../compile/ASST1
% bmake depend
% bmake
% bmake install

If you are told that the compile/ASST1 directory does not exist, make sure you ran config for ASST1.

Tip: Once you start modifying the OS/161 kernel, you can quickly rebuild and re-install with the following command sequence. It will install the kernel if the build succeeds. There should be no need to repeat the depend step unless you want to add more source files to the kernel, which we do not recommend.

% bmake && bmake install

Check sys161.conf

The sys161.conf should be already be installed in the ~/cs3231/root directory from assignment 0. If not, follow the instructions below to obtain another copy. A pre-configured sys161 configuration is available here: sys161.conf.

% cd ~/cs3231/root
% wget http://cgi.cse.unsw.edu.au/~cs3231/25T2/assignments/asst1/sys161.conf

Run the kernel

Run the previously built kernel:

% cd ~/cs3231/root
% sys161 kernel
sys161: System/161 release 2.0.8, compiled Feb 25 2019 09:34:40

OS/161 base system version 2.0.3
(with locks&CVs solution)
Copyright (c) 2000, 2001-2005, 2008-2011, 2013, 2014
President and Fellows of Harvard College.  All rights reserved.

Put-your-group-name-here's system version 0 (ASST1 #1)

16220k physical memory available
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lser0 at lamebus0
con0 at lser0

cpu0: MIPS/161 (System/161 2.x) features 0x0
OS/161 kernel [? for menu]:

Kernel menu commands and arguments to OS/161

Your solutions to ASST1 will be tested (and automarked) by running OS/161 with command line arguments that correspond to the menu options in the OS/161 boot menu.

Here are some examples of using command line arguments to select OS/161 menu items:

sys161 kernel "at;bt;q"

This is the same as starting up with sys161 kernel, then running "at" at the menu prompt (invoking the array test), then when that finishes running "bt" (bitmap test), then quitting by typing "q".

sys161 kernel "q"

This is the simplest example. This will start the kernel up, then quit as soon as it's finished booting. Try it yourself with other menu commands. Remember that the commands must be separated by semicolons (";").

Essential to this assignment is the p command, which runs an initial user-level program. You can, for instance, run the add test like this:

sys161 kernel "p testbin/add"

The above test is expected to mostly fail, and nearly all the others, will fail, reporting that we haven't implemented some system calls. In assignment 2, we will add some standard system calls to OS/161, so that many of these tests pass. For now, we're interested in three special-purpose tests, named rot13, boxes and mystery. More on that below.

Part 1: Despatching the encode and checksum System Calls

Marks: 40% of this assignment

The first task is to implement the encode and checksum system calls.

To do this, you need to add new system call numbers for them to the syscall.h file we looked at above. You can choose the system call numbers, but they should be different from all existing system calls. You should use the standard naming convention, e.g. SYS_encode.

Note: This is unusual. In the remaining assignments, you will be adding implementations of standard UNIX system calls, which are already enumerated and prototyped at user-level, and documented in the usual manual pages. In this assignment, you are adding a non-standard system call for this feature. Their specification is below.

The provided encoder device actually implements the encoder and decoder operations. The job of your code is to map the system call arguments to the device arguments, and handle various possible error conditions.

Specification of encode

The encode system call takes four arguments, op_id, argument, box_id1 and box_id2. These are four of the registers saved in the trap-frame. Each argument will be passed to the underlying encoder device operation.

The return value is the resulting encoded value, if the operation is successful. Like many other system calls, encode can fail and return an error code, which the user will receive via the errno mechanism.

The Encoder161 device provides a small number of on-device registers called "lockboxes" which can be used to store the intermediate results of larger encoding calculations. The box-ID arguments box_id1 and box_id2 are used to identify lockboxes to be used. If lockboxes are not required, both of these arguments should be set to -1. Note that the device interface uses slightly different types to manage box IDs, and also that not all operations support the use of lockboxes. Your OS code should not attempt to pass box-ID values to the device when the operation would not support it. Instead such cases should be reported to the user code by returning an error value.

The error codes used by the kernel and returned to the user are listed in kern/include/kern/errno.h.

Specification of checksum

The checksum system call takes two arguments, op_id and argument. These are passed directly to the device.

The device checksum code returns 0 for success and other error codes for failure, like many kernel functions. However, these errors are not reported to user code. Failed checksums indicate a possible security error. To ensure security, tasks that fail a checksum are suspended, to prevent them from decoding values by repeated guess and check. The failed_checksum function is provided to you to suspend tasks as necessary.

Re-building the kernel

Once you have implemented encode and checksum, you should be able to build and install your modified kernel via bmake && bmake install in the compile/ASST1 directory. To test it, we'll need to add some custom user-level programs in the remaining parts.

Part 2: The User-Level System Calls

Marks: 10% of this assignment

Recall that we can rebuild the user-level programs with bmake && bmake install in the top-level asst1-src directory.

This rebuild will automatically create the bodies of the encode and checksum system calls. The system call number file (kern/syscall.h) is used to auto-generate an assembly file called syscalls.S. Find that file and check that there are mentions of encode and checksum. You don't have to understand how the macros in this file actually work.

To call these functions, we'll have to add C prototypes for them to a C header file. An appropriate place is the userland/include/encoder.h header file.

Once those function prototypes are defined, you should be able to un-comment the calls to encode and checksum in the mystery test code in userland/testbin/mystery/mystery.c, and rebuild user-land.

Part 3: Testing the ROT-13 Feature

Marks: 15% of this assignment

It's time to write a test!

The goal of the rot13 test-binary is to exercise the ROT-13 feature of the Encoder161 device. This is not a very secure form of cryptographic encoding. You can read more about ROT-13 by searching for it on the internet.

Once you implement the rot13 test, you can rebuild it by rebuilding all of user-land, as you have above. You don't need to write much code to implement this test, and it is best to use no C features other than the system calls we have just written. User-level OS/161 programs cannot yet produce output by calling printf or writing to a file; we will fix that in assignment 2. User-level OS/161 programs also run in a small window of memory which will run out quickly if they attempt to malloc; we will fix that in assignment 3.

To complete this test, you need to apply the encode operation to every character in the test string "The quick brown fox jumps over the lazy dog.", including the final full stop.

The characters of a string have type char in C, but they can safely be cast to unsigned int to be encoded. The ROT-13 encoder will always map characters in the printable character range (0-127) to other characters in the same range, so they can be cast back to values of type char without loss of information.

Call the encode system call with the ENCODE_ROT13 setting for every character in the test string, and save the resulting characters to another character array.

Now, for each character in the new character array, call the checksum system call with the CHECKSUM_ROT13 setting. This will check that the expected encoded characters have been created.

It should now be possible to call checksum with the CHECKSUM_FINISHED operation number. In this case the argument to CHECKSUM_FINISHED does not matter. This will test that the checksum process has completed and checked the entire test string.

The simulated device should print a message saying that the checksum finalisation process succeeded. Once you see that message, you have completed this part of the assignment.

Part 4: Testing the Lockbox Feature

Marks: 15% of this assignment

The Encoder161 provides a small number of on-device registers called "lockboxes" which can be used to store the intermediate results of larger encoding calculations.

In this test, you will exercise the ENCODE_BOX_OP_1 feature, using 8 of the device's lockboxes. We have little surviving documentation of this feature. What we have tells us that it works a little bit like one of those "magic" tricks where the number you have at the end is the same as the one you thought of at the start.

The test protocol we want to perform is:

• Pick a number more than 1 and less than 1 million.
• Encode the number using ENCODE_BOX_OP_1 and boxes 0 and 1. ** Note that order matters with these lockboxes.
• Re-encode the partly-encoded number using boxes 1 and 2.
• Repeat 6 more times. In the final step, encode using boxes 7 and 0.

The finally encoded value should be the same one you started with. Amazing!

We can now go through a check cycle. Call the checksum operation with CHECKSUM_BOXES 8 times, using the final encoded value. This will check that each lockbox is in the correct state.

Once again, you can finish the process with checksum and the CHECKSUM_FINISHED operation number. The argument to CHECKSUM_FINISHED does not matter. This will print a message indicating that the lockbox test is done.

Part 5: Handling Some Concurrency

Marks: 20% of this assignment

In this advanced component, we address the concurrency issues that have been ignored by the specification so far.

The task is simply to prevent dangerous concurrent access to any of the lockboxes of the Encoder161 device.

Consider a scenario where multiple kernel threads exist, and can call your encode system call handler. You should ensure that this does not result in overlapping accesses to the underlying device encode operation using the same lockbox.

The OS/161 implementation provides semaphores, locks and condition variables that you may use in your solution. We recommend you scan the prototypes of these functions in kern/include/synch.h.

Minor caveat: You can get started on this part right away. It is probably not clear how to go about testing your solution. We will release an assignment spec 2.0 at least a week before the deadline which provides some test code.

Advanced Part 1: Handling More Concurrency

Marks: Equivalent to 20% of this assignment

This is the first "advanced" assignment component. Assignments 2 and 3 will contain quite a few more. The "bonus marks" accrued in this component can offset lost marks in this assignment or in other assignments. This makes these advanced components worth some marks, but not a lot of marks. Students should attempt these components mostly for interest.

Students in the Extended OS course codes (COMP3891/COMP9283) are required to attempt at least 3 of these advanced components by the end of the course. Like everything else, we strongly recommend you start early. This assignment has 2 possible advanced components, and assignments 2 and 3 will each have at least 4.

The task is the same as regular part 5, with one additional constraint. Your solution should not prevent concurrent access to different device lockboxes. If one thread attempts an encode operation using lockboxes 2 and 3, and another using 4 and 5, the operations should both be able to commence before either finished. To clarify, we mean that the device operations should be able to overlap. It is possible that you need to synchronise access to other data used in your system call layer, but this should not prevent overlapping calls to the device.

Minor caveat: As with Part 5, you can get started right away. It will be easier to test your solution thoroughly once our concurrent tester code is released.

Advanced Part 2: The Mystery Machine Test

Marks: 20% of this assignment

The mystery machine test is provided to you in userland/testbin/mystery.

It should already build and pass its test, but what it is doing is (somewhat) mysterious. Your job is to extract the mystery message it is decoding.

Minor caveat: As with Part 5, you can start thinking about how to do this right away. The spec 2.0 will provide some more specific instructions about how to set up the mystery machine to receive a specific message, and how to report the message you have extracted in your submission.