- Introduction
- Startup: Building xv6
- Exercises
Introduction
It is crucial for this class that you have a solid foundation in C programming, as it is the most widely used language for systems programming (though now facing a relatively decent challenge from Rust). Therefore, we have prepared a set of practice problems for you to solve and refresh your memory when it comes to C programming concepts, as well as introduce some minor new concepts like making system calls and parsing command line arguments.
Learning Objectives
At the end of the lab assignment, you should be able to:
- Implement basic pointer manipulation operations in C.
- Implement basic structures and structure creation/manipulation operations.
- Compile and boot the xv6 operating system.
- Implement standard Unix utilities in the xv6 operating system.
The xv6 Operating System
xv6 is a simple operating system, created by MIT faculty and students, to serve as a teaching tool for operating systems classes. xv6 is based on Dennis Ritchie’s and Ken Thompson’s Unix Version 6 (v6), and is implemented in C to run on a multi-core RISC-V (virtual) machine.
One of the main features of xv6 is that its code is very readable for an operating system. The accompanying book is a great resource to understand how a basic operating system functions, handles system calls, interrupts, memory management, etc. In this class, we will use xv6 as a toy operating system to implement several tools and features that we discuss in class.
Startup: Building xv6
Let’s first start by compiling and booting the xv6 operating system. All of the
source code for this lab is part of the csse332-labs
repository, though on a
different branch. Please follow the instructions below carefully to make sure
you are working on the right stuff.
Getting the source code
If you have not done so yet, please make sure that you have set up your class labs repository by following the appropriate instructions.
Now that you are in the right repository, first make sure you are on the main
branch:
(csse332-labs) $ git branch
This will show all your local branches. Make sure that the one that is starred
is called main
.
If you are not on the main branch, then do:
(csse332-labs) $ git checkout main
Switched to branch 'main'
Your branch is up to date with 'origin/main'.
If your branch is not up to date with origin/main
, then use a git pull
to
get the latest updates from your local main
branch.
Switching to clab
The starter code for this lab is found in the upstream/clab
branch of the
class repository. We need to fetch those changes from the upstream, create our
local solution branch, and then we can start working.
First, fetch the updates from upstream using:
(csse332-labs) $ git fetch upstream
Then, make sure that you can see this lab’s branch:
(csse332-labs) $ git branch -a
* main
remotes/origin/HEAD -> origin/main
remotes/origin/main
remotes/upstream/clab
remotes/upstream/main
You might see other branches there, depending on when you do this, but make sure
that remotes/upstream/clab
shows up.
Now, let’s checkout that clab
branch and create a local one to write our
solution to:
(csse332-labs) $ git checkout -b clab_solution upstream/clab
branch 'clab_solution' set up to track 'upstream/clab'.
Switched to a new branch 'clab_solution'
Finally, update your local branch’s push location to your own repository:
(csse332-labs) $ git push --set-upstream origin clab_solution
Total 0 (delta 0), reused 0 (delta 0), pack-reused 0
remote:
remote: Create a pull request for 'clab_solution' on GitHub by visiting:
remote: https://github.com/user/csse332-labs-user/pull/new/clab_solution
remote:
To github.com:user/csse332-labs-noureddi.git
* [new branch] clab_solution -> clab_solution
branch 'clab_solution' set up to track 'origin/clab_solution'.
Now, you are ready to get started on this lab. Happy hacking ❗
Booting xv6
In all of what follows, we assume that you are working off of the xv6-riscv
directory in your csse332-labs-user
repository, i.e., always do:
$ cd xv6-riscv/
Now we are ready to compile xv6 and launch qemu
to boot into a virtual machine
that is running the xv6 operating system. From the root directory of the cloned
source code, compile and launch qemu
using
make qemu
On my machine, I had the following output, your output should match mine and you
should drop into a shell in the qemu
machine.
$ make qemu
>> Lots of compilation outputs, should be no warnings and no errors <<
xv6 kernel is booting
hart 2 starting
hart 1 starting
init: starting sh
$
If you get to this point, you are ready to roll. Try to play around in the xv6
shell and then when you are ready to exit, press <ctrl - a> then x, i.e., hold
the control key, then press a
, then release both keys and press x
.
Troubleshooting
If the compilation fails, make sure to record any error messages your received. Before contacting your instructor, make sure you record the versions of all of the tools that are needed to compile xv6. You can get those version by running the following commands:
- Your kernel version:
$ uname -r
- You
qemu
system version:$ qemu-system-riscv64 --version QEMU emulator version 4.2.1 (Debian 1:4.2-3ubuntu6.18) Copyright (c) 2003-2019 Fabrice Bellard and the QEMU Project developers
- Your RISC-V cross compiler version:
$ riscv64-linux-gnu-gcc --version riscv64-linux-gnu-gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Once you have the above information, make a public post on the Moodle forum and include all the information above plus any error messages that came up during compilation. One of the instructors or TAs will get back to you as soon as possible.
Exercises
There are four sets of exercises in this lab, that range in difficulty from straightforward to medium. Since this is a review lab, there will be no really challenging tasks. Expect those to show in the following labs.
Warmup
The first set of exercises you will solve are warmup exercises that are fairly
easy and straightforward to solve. Checkout the code in user/warmup.c
for
instructions on how to solve these problems. The source code in warmup.c
contains test cases that will help you test your code and debug in the case of a
failed implementation.
To run the warmup code, you can use the following instructions:
- Compile the
xv6
source code using$ make qemu
- In the
xv6
shell, issue thewarmup
command using$ warmup
-
Note that running
warmup
without any arguments will run all of the test cases. To run a specific test case, you can usewarmup <num>
when<num>
is an integer that corresponds to the test case you want to run. Check out themain
function inwarmup.c
for the mapping between numbers and test cases. -
Note that failed assertions in the test cases written will cause your program to fail.
Running the grading script
To double check your work, you can run the grading script (assuming you have
python3
installed) from your Linux shell (not the xv6 shell):
$ ./grade-lab-0.py warmup
ArrayList
The next set of exercises will have you implement an array list data structure
in C in the xv6 operating system. Recall that an array list doubles in size
every time it runs out of space. We have already defined a structure that
contains the elements needed to implement an array list in the arraylist
structure as follows:
struct arraylist {
int size;
int capacity;
int *list;
};
where size
is the current size of the list (i.e., the total number of elements
currently in the array list), capacity
is the maximum size of the array list,
and list
is the actual list in memory that contains the elements.
-
The first function you are to implement is the
al_new
function, which takes no arguments and returns a new array list structure initialized to asize
of 0, acapacity
ofDEF_ARRAY_LIST_CAPACITY
, and an array of sizecapacity
allocated in memory (It is okay if the allocated memory area contains garbage data, you do not need to initialize it).To allocate memory in C, you will find the function
malloc
to be very useful. -
The second function you are to implement is the
al_free
function, which takes a pointer to an array list structure and frees that array list. Note that you must also free the inner list in case it exists.To free memory in C, you will find the function
free
to be very useful. -
The next function to implement is the
al_get_at
function. It takes as input a pointer to an array list structure and a positionpos
. It returns the element in the list at the positionpos
. If such an element does not exists, then the function returns the hex constant0xffffffff
. -
Next, implement the
al_resize
function. It accepts as input a pointer to an array list structure and resizes the inner array to double its size. Note that you do not have access to therealloc
routine, you must implement that yourself.Make sure to have no memory leaks, you will lose points if you do!
-
Finally, implement the
al_append
function that accepts a pointer to an array list structure and a valueval
. It then insertsval
at the end of the list. If the list is full, it then callsal_resize
to make room forval
and then inserts it into the list. -
For your convenience, we have implemented
al_print
to print an array list. Use that to print your list for debugging purposes.
Testing
To test your code, after each step, launch the xv6 machine and then issue the
arraylist
command:
$ arraylist
Note that the numbers between the parenthesis correspond to the line numbers in your code. So if an assertion fails, you can go to that specific line number and check which test has failed.
As you implement more functions, more tests will pass. At the end, you should see something that looks like the following:
$ arraylist
main(174): OK.
main(175): OK.
main(176): OK.
main(181): OK.
main(182): OK.
main(185): OK.
main(186): OK.
main(187): OK.
main(192): OK.
main(193): OK.
main(197): OK.
main(198): OK.
main(201): OK.
main(202): OK.
main(203): OK.
main(204): OK.
main(205): OK.
Running the grading script
To double check your work, run the grading script from your Linux terminal (not your xv6 terminal), using:
$ ./grade-lab-0.py arraylist
make: 'kernel/kernel' is up to date.
== Test arraylist, all == arraylist, all: OK (1.5s)
Implementing sleep
Before getting started, skim through Chapter 1 of the xv6 book; it serves as a good introduction to the operating system and its interface.
The goal of this exercise is to implement the UNIX utility sleep
, which causes
the current terminal to pause for a user-specified number of ticks. In xv6, a
tick is defined as the time between two interrupts from the qemu
timer chip.
For example, if I issue the command sleep 10
from the terminal, the whole
terminal would pause until 10 ticks have passed. You can examine the behavior of
sleep
in your current Linux terminal by typing man sleep
.
All user utilities in xv6 will go into the user/
directory. In there you will
find examples of other utilities, such as ls
, grep
, mkdir
, rm
, etc.
Examining the code behind some of those utilities will prove to be of immense
help in this lab.
Implementation plan
Please note that throughout this lab, you do not have access to the regular C routines defined in libc, such as those defined in
stdio.h
,stdlib.h
, andstring.h
for example. All the routines available to you are defined inuser/user.h
.
Here’s a list of steps and requirements that will help you implement the sleep
utility in xv6:
- We have created a file named
sleep.c
for you in theuser/
directory.- The
sleep.c
file includes the necessary header files and has an emptymain
function for you to fill out.
- The
- In
main(int argc, char **argv)
,argc
is the argument count andargv
is the argument vector. Recall thatargv[0]
is always the name of the program being run, so alwaysargc >= 1
. - If the user forgets to pass an argument, your program should output an error message and instruct the user on proper usage of the utility.
- Command line arguments are passed as strings, you can use
atoi
to convert a string into an integer. Checkoutuser/lib.c
for more information about the availablelibc
routines. - Use the system call
sleep
.- Take a look at
user/user.h
to see the definition ofsleep
that is callable from user-space. - If you want to take a look at the actual system call, then examine
kernel/sysproc.c
and look forsys_sleep
.
- Take a look at
- Make sure that your program calls
exit()
in order to exit your program.
Building and testing
We have already added the sleep binary to the list of targets to compile by the
Makefile
so you do not need to change anything there.
Compile xv6 and launch into the qemu
emulator using
$ make qemu
then run your sleep
program from the xv6 shell:
$ sleep 10
### Nothing happens for 10 ticks ###
$
Running the grading script
To double check your work, you can run the python grading script (assuming you
have python3
installed):
$ ./grade-lab-0.py sleep
Implementing find
The goal of this exercise is to implement the UNIX find
program, which, given
a file name, finds all the files in a certain directory (and its
sub-directories) that match that file name.
For example, consider a directory a/
that contains a file called b
and then
another directory called c/
that contains another file called b
as well.
Then launching the find
command from the a
directory will return both ./b
and ./c/b
as results.
$ cd a/
$ find . b
./b
./c/b
Implementation plan
Since we are exploring directories and sub-directories, expect your solution to
be recursive. Also, recall that we are dealing with C strings, so ==
does
not compare strings, rather it compares their pointers. To compare strings in C,
use the routine strcmp
.
For inspiration to get started, take a look at user/ls.c
to see how to read
files and directories.
Here are a couple of hints and observations:
- You might find the system call
fstat
and the utility routinestat
useful. -
Running
fstat
on a file will fill out astruct stat
structure, which contains a lot of useful information about the file/directory. You can find the definition of thestruct stat
below and inkernel/stat.h
#define T_DIR 1 // Directory #define T_FILE 2 // File #define T_DEVICE 3 // Device struct stat { int dev; // File system's disk device uint ino; // Inode number short type; // Type of file short nlink; // Number of links to file uint64 size; // Size of file in bytes };
- Use recursion to descend into sub-directories, but do not recurse into
.
and..
- A directory is nothing but a file that contains a bunch of directory entries,
or dentries. In xv6, they are represented as
struct dirent
structures. - Remember to
\0
terminate your strings before using thestrlen
routine.
Building and testing
Compile xv6 using make qemu
from your terminal, and then, from the xv6 shell:
$ echo > b
$ mkdir a
$ echo > a/b
$ find . b
./b
./a/b
$
Running the grading script
To double check your work, you can run the python grading script using:
$ ./grade-lab-0.py find
Running the full grading script
Once you are done implementing all the above programs, run the grading script using
$ make grade
from your Linux terminal (not your xv6 terminal window).
Submitting your code
From the Linux terminal, issue the command (make sure you are in the xv6-riscv
directory in your repository):
./create_submission.sh <username>
and replace <username>
with your RHIT username (without the <
and >
). For
example, for me, that would be:
./create_submission.sh noureddi
If you get a message saying that you don’t have permission to run
./create_submission.sh
, then issue the following command first
chmod +x ./create_submission.sh
Here’s the output as it shows up on my end:
Cleaning up xv6 directory...
Process started: writing temporaries to /tmp/a8998c31a141924d06220074fcdc6925.txt
Found the following modified files:
./user/arraylist.c
./user/find.c
./user/sleep.c
./user/warmup.c
Creating the submission zip file.
adding: user/arraylist.c (deflated 64%)
adding: user/find.c (deflated 30%)
adding: user/sleep.c (deflated 19%)
adding: user/warmup.c (deflated 63%)
Done...
################################################################
submission_noureddi.zip has been created.
Please submit THIS FILE AND THIS FILE ONLY to Gradescope.
################################################################
This will generate a single file called submission-username.zip
(for me, it
would be submission-noureddi.zip
). That is all you need to upload to
Gradescope.
Submission Checklist
- My code compiles and generates the right executables.
- I ran
make grade
to double check the test cases for all of my code. - I ran the submission script to generate my
zip
file. - I submitted the
zip
file to Gradescope.
Grading
Check out this assignment’s grading page for more information.
This page was last edited by Mohammad Noureddine on Sat 25 Nov 2023. If you notice any typos or inaccuracies, please open a GitHub issue on this repository.