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

Edit: depending on when you fetched the sources, it is possible the bmake step will fail, saying that kernel_encode_call and encode_system_setup are missing. These features were added in a follow-up release of the assignment. You can see their types in kern/include/encode_sys.h. We recommend you add dummy versions of these functions (that don't do anything) to kern/syscall/encode.c. Once that is done, the kernel build with bmake should succeed. It will become clear what these functions are for in Part 5.

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.

Handling new system calls

You need to attach some new system call handling code to deal with a SYS_encode system call, etc. We recommend you have a look at how the example system call SYS___time/sys___time is handled. There is space set up for you to write new system call functionality in kern/syscall/encode.c.

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.

Pseudo-code

Updated in v2 of the spec, here is pseudo-code of an implementation of the central function of the encode system call.

function sys_encode (op_num, arg, box_id1, box_id2)

  device = get_encode_device ()
  if no device, return an error

  mode = device.is_op_supported (op_num)
  if not supported, return an error

  if mode requires no boxes:
    if box_id1 is not -1 or box_id2 is not -1, return an error

    result = device.encode_op (op_num, arg, null)

  else:
    check box_id1 is in [0 ..< num_enc_boxes], otherwise return an error
    check box_id2 is in [0 ..< num_enc_boxes], otherwise return an error

    boxes = allocate()
    if allocate failed, return an error
    boxes.id1 = box_id1
    boxes.id2 = box_id2

    result = device.encode_op (op_num, arg, boxes)
    free(boxes)

  return success and result

What does "return an error" mean? More on that in the FAQ question about return values.

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.

Pseudo-code

Updated in v2 of the spec, here is pseudo-code of an implementation of the central function of the checksum system call.

function sys_checksum (op_num, arg)

  device = get_encode_device ()
  if no device, return an error

  result = device.checksum_op (op_num, arg)

  if result is error:
    failed_checksum()

  return result

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.
  • You can pick this number by hand, it's OK if it's the same in each run.
• Encode the number 8 times using ENCODE_BOX_OP_1 and a cycle of boxes.
  • The first pair of boxes is 0 and 1.
  • Note that argument order matters with these lockboxes, using boxes 1 and 0 would have a different meaning.
  • The next pair of boxes is 1 and 2, then 2 and 3, etc.
  • The last pair of boxes is 7 and 0, completing the cycle.
• The output of each encode step should be the input to the next one.

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 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. There are some surviving comments in that header that suggest you could implement these functions, but you don't have to. In the Harvard course that OS/161 was borrowed from there were many more assignments, including one to implement these mechanisms.

We have provided some test cases in an extension to the provided code. These will help you check your implementation. Concurrent testing requires forking kernel-only threads in OS/161 as multi-threaded user-level execution is not yet present. To fetch the additional code, pull from our website:

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

Make sure that your current work is all committed. You can now merge with our changes by:

% git merge cs3231-website/main

The merge should succeed, unless you have modified encoder161.c, encoder161.h or menu.c. Remember to commit the merge as soon as it is done!

You should now see the new header kern/include/encode_sys.h. It defines prototypes for two functions, encode_system_setup and kernel_encode_call. You need to add these to the system call layer you added in Part 1.

The kernel_encode_call function simply performs the same operation as an encode system call, but it is started from within the kernel. Your implementation can just call on your encode implementation from Part 1; we can't make such a function call as we don't know exactly the type or name of your encode system call handler. The kernel_encode_call function is used by our multi-threaded tester. The encode_system_setup function will be called prior to any calls to kernel_encode_call or system calls. You can use it to safely do any initialisation you need to in a non-concurrent context.

You can run the new test by using the "part5" menu command to sys161:

% sys161 kernel "part5 inc"
% sys161 kernel "part5 flip"

These tests exercise the new ENCODE_BOX_INC operation and the ENCODE_BOX_OP_2 (aka flip) operation using the kernel_encode_call interface with 16 client threads.

Important note: you need to implement encode_system_setup and kernel_encode_call to get the marks for this part of the assignment. The test code we provide here will also be used as part of our marking auto-tests.

Clarification: this part is concerned with concurrent access to this in-kernel interface. Note that we haven't included a mechanism that allows the kernel to call for a checksum operation, so that's not your job, and you can ignore possible concurrency situations that involve it. Our tests might still make use of a checksum feature, but if they do, they will themselves use synchronisation primitives to ensure there is no race with a call to kernel_encode_call.

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.

The tests from Part 5 can be used to check that your approach prevents problematic races. We don't provide you with any test that shows that your approach allows concurrent operations. It's up to you to convince yourself that you've really solved this part (as opposed to writing a complicated solution to Part 5), or to take the risk of submitting your work untested.

The final job for Part A-1 is to edit the file part_a1.txt to include a short description of your implementation.

Advanced Part 2: The Mystery Machine Test

Marks: Equivalent to 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. This should be a short message, a few lines long, written in English.

There is a default message shipped with the assignment sources. To make this (very slightly) more interesting, fetch your custom message from this URL:

https://cgi.cse.unsw.edu.au/~cs3231/cgi-bin/mystery/get_msg.py

To complete Part A-2, edit the file part_a2.txt to include the decoded message itself and a short description of the steps that you took to extract it.

% cd ~
% give cs3231 asst1 asst1.bundle

Submitting the Advanced Part

The advanced component is also submitted using the give system following a very similar procedure. It is a separate submission with its own assignment name, asst1_adv. In addition, the test process expects a branch called asst1_adv rather than main.

To create a bundle containing the asst1_adv branch (and not other branches):

% git bundle create asst1_adv.bundle asst1_adv

If you did your work on some other branch named other_branch (or even main), you can copy it to asst1_adv prior to bundling:

% git branch asst1_adv other_branch
% # check what is on the new branch
% git log asst1_adv

Once you have a bundle, submit it using give as for the main part:

% cd ~
% give cs3231 asst1_adv asst1_adv.bundle

Number of Lockboxes

Q: Is there some kind of constant I need to be using to get the maximum number of lockboxes?

A: You should only use the number of lockboxes provided by a particular instance of an Encoder161 device, which you can get from the num_enc_boxes field of the encode_device struct.

The "System Call Layer"

Q: What is meant by the Part 5 spec when it says that encode_system_setup and kernel_encode_call should be added to the system call layer from Part 1?

A: When you implemented your solution for Part 1, you likely created a function that has the same or a similar function signature to kernel_encode_call (probably named something like sys_encode). To do Part 5, we want you add a function body to kernel_encode_call that wraps/calls your original function. E.g. if your function was called sys_encode:

int kernel_encode_call(args...) {
    return sys_encode(args...);
}

We then want you to modify your Part 1 function (e.g. sys_encode) to make it thread-safe.

If you find that you need to set something up (which you probably do) you can add the setup code to an encode_system_setup function, and assume that this function will be run before any system calls or kernel_encode_calls in your kernel.

syscall.S

Q: Where is this auto-generated syscall.S mentioned in Part 2?

A: It is generated in the build/ directory. You may have issues searching for it via VS Code because its search function, by default, ignores files that match the .gitignore. Disabling this option should allow you to find the file.

Encoding 4294967295

Q: Why would the "boxes" test or the "mystery" test be trying to encode 4294967295?

A: That number is two to the power of 32 minus one, or, it is what the signed value -1 will become when cast to an unsigned 32-bit value.

We saw in lectures that the system call wrapper at user-level replaces return values with -1 if an error is raised.

If something in your system call handler returns an error code (e.g. EINVAL) when it shouldn't, this might lead to a test like "boxes" or "mystery" getting the result -1, and trying to encode it again. You probably need to use GDB or kprintf to go through the steps of your system call handling code.

Return values and error codes

In Part 1, you need to write a function that handles user encode calls. This function might need to produce result information (the result of the encoding) and might need to produce error information (if something goes wrong). The pseudo-code in Part 1 describes this vaguely by suggesting the function might "return an error" or "return success and a value".

It is not possible for this function to return a single value of type int and for its caller to inspect that int and know if it is an error code or an encoded value. This function needs to return more information to its caller. There are multiple ways this could be done in C, including returning a struct value, or receiving a pointer to a variable to be written.

It's OK for your function to have a different type signature to the sys_encode function in the pseudo-code.

There are plenty of other functions in OS/161 which need to report both error codes and other values to their callers. It's very common for a function in OS code to need to have a way to detect a failure case, undo any memory allocations it has performed, and report that failure to its caller.

The type of kernel_encode_call in Part 5 use one particular approach to returning error codes.