Assignment 0

This assignment is worth a possible 10 marks of the class mark component of your assessment

No bonuses apply for this assignment.

The assignment is due Monday, 20th of March, at 8:00am (week 4).

Introduction

The aim of Assignment 0 is to have you familiarise yourself with the environment you will be using for the remaining assignments. The assignment consists of two parts, an assessable and a non-assessable component. The non-assessable component consists of a set of directed questions to guide you through the code. The answers to this code reading Q & A component of the assignment will be given and discussed in your tutorial. The assessable part of this assignment consists of you making a very minor change to the existing OS. The change is conceptually trivial, so you can view this assignment as us giving away marks as an incentive for you to get the assignment environment up and running early in the session. This assignment is worth 10% of the class mark component of your final assessment.

Note that while the code reading component is not assessable, we view it as compulsory. You will really struggle with the assignments if you fail to get an understanding of the code base. The code reading component is there to guide you towards acquiring that understanding. Skip it at your own risk.

Also note that this assignment is not indicative of the level of difficulty of the later assignments. The later assignments will be much more challenging.

This assignment will introduce you to the following components of the environment you will use during the semester.

OS/161

OS/161 is an educational operating system. It aims to strike a balance between giving students experience working on a real operating system, and potentially overwhelming students with the complexity that exists in a fully fledged operating system, such as Linux. Compared to most deployed operating systems, OS/161 is quite small (approximately 20,000 lines of code and comments), and therefore it is much easier to develop an understanding of the entire code base, as you will begin to do during this assignment.

The source code distribution contains a full operating system source tree, including the kernel, libraries, various utilities (ls, cat, etc.), and some test programs. The OS/161 boots on the simulated machine in the same manner as a real system might boot on real hardware.

System/161

System/161 simulates a "real" machine to run OS/161 on. The machine features a MIPS R2000/R3000 CPU including an MMU, but no floating point unit or cache. It also features simplified hardware devices hooked up to lamebus. These devices are much simpler than real hardware, and thus make it feasible for you to get your hands dirty, without having to deal with the typical level of complexity of physical hardware.

Using a simulator has several advantages. Unlike software you have written thus far (Windows excluded :-)), buggy software may result in completely locking up the machine, making to difficult to debug and requiring a reboot. A simulator allows debuggers access to the machine below the software architecture level as if debugging was built into the CPU chip. In some senses, the simulator is similar to an in circuit emulator (ICE) that you might find in industry, only it's done in software. The other major advantage is speed of reboot, rebooting real hardware takes minutes, and hence the development cycle can be frustratingly slow on real hardware.

GDB

You should already be familiar the GDB, the GNU debugger. GDB allows you to set breakpoints to stop your program under certain conditions, inspect the state of your program when it stops, modify its state, and continue where it left off. It is a powerful aid to the debugging process that is worth investing the time needed to learn it. GDB allows you to quickly find bugs that are very difficult to find with the typical printf style debugging.

Details beyond the level you need to know can be found at http://www.gnu.org/software/gdb/gdb.html. A brief and focused introduction will be given later in this document.

CVS

CVS (Concurrent Versions System) is a source code management system used to track changes to a piece of software. We make use of CVS in this course to allow you to manage the large code base (compared to most previous assignments you have done), and recover from potential problems. CVS keeps a recoverable copy of specified versions of all your OS/161 files. It allows you to track the changes you have made, and more importantly, rollback to a known state if things get out of hand.

CVS also enables you and your partner to work on the same code repository in a coordinated way. You can even work on versions of your code stored at home and at CSE.

CVS is a large system of which you need to know only a small subset of its functionality. We will give you directions for the parts you need to know. For the curious, you can find detailed docs on CVS at http://www.cvshome.org/docs/. For the adventurous, try out tkcvs. While tkcvs is nice for browsing and diffing, we do not recommend using it directly for manipulating the cvs repository. Please follow the directions given for the command line utilities. If you feel like "knowing better", we'll feel free to say "I told you so".

Getting Started

Setting up your account

You're working in pairs for this assignment. Some of the instructions below need to be done for each group member, some need to be performed only once for the overall group. We will indicate this when appropriate, so pay attention.

Both partners will need to set up various environment variables for you to access the tools needed for the course. If you know what your doing, do the following, or simply run 3231 in each new shell you use when working on the assignment.

Note: You must not have "." (or equivalent) prior to "/bin" in your PATH. The build will fail later if you do. Note: doing this is generally a bad idea for security reasons anyway.

Each partner will need to modify their umask to allow their partner to share the assignment files (if your interested, see man umask for details). Do this by modifying your .profile in your home directory. Change the umask command to be the following. 

umask 007

You will have been informed of your group number for the session. A group account has been created for you in /home/osprj000, where 000 corresponds to your group number (three digits, e.g. 013). For the remainder of the document we will assume you replace references to osprj000 with your own group number (e.g., osprj013).

You will be using cvs to manage the assignments for your group and cvs needs to be told where you will be storing its repository. The easiest way to do this is to set an environment variable in your shell's start up files. Edit your .profile and add the following lines. Remember to adjust the group number. 

CVSROOT="/home/osprj000/cvsroot"
export CVSROOT

Now whenever you log in, you umask and environment variable CVSROOT will be set appropriately. Just on this occasion, run source .profile to avoid having to log out and log back in again.

Obtaining and setting up the distribution in CVS

In this section, you will be setting up the cvs repository that will contain your code. Only one of you needs to do the following. We suggest your partner sit in on this part of the assignment. You have now completed setting up a shared repository for both partners. The following instructions are now for both partners.

The Reading Part of Assignment 0

Note: this part is non-assessable. The answers will be made available in week 4. Feel free to discuss them with fellow students.

This is probably the first time most of you will attempt to understand, and carefully modify, a large body of code that you did not write yourself. It is imperative that you take the time to read through the code to get an understanding of the overall structure of the code, and what each part of the code does.

This non-assessable, code reading component of this assignment aims to guide you through the code base to help you comprehend its contents, identify what functionality is implemented where, and be able to make intelligent decisions on how to modify the code base to achieve the goals of the assignments.

You don't need to understand every line of code, but you should have a rough idea of what some files do.

Invest the time now in gaining an overall understanding of the code base. Now is probably the least busiest part of the semester for you. Don't waste it and struggle later.

The top-level Directory

The asst0-src directory contains the top-level directory of the OS/161. It contains a few files, and subdirectories containing distinct parts of OS/161. The files are: asst0-src contains the following directories: Your focus during this code walk through should be on the kernel sources. You won't need a detailed understanding of the utilities in bin and sbin, however broad understanding of how they work and where things are is useful. Likewise with the lib and include directories.

The Kern Subdirectory

This directory and its subdirectories are where most (if not all) of the action takes place. The only file in this directory is a Makefile. This Makefile only installs various header files. It does not actually build anything.

We will now examine the various subdirectories in detail. Take time to explore the code and answer the questions.

kern/arch
This directory contains architecture-dependent code, which means code that is dependent on the architecture OS/161 runs on. Different machine architectures have their own specific architecture-dependent directory. Currently, there is only one supported architecture, which is mips.
kern/arch/mips/conf

conf.arch: This tells the kernel config script where to find the machine-specific, low-level functions it needs (see mips/mips).

Question 1: What is the vm system called that is configured for assignment 0?

Makefile.mips: Kernel Makefile; it copies this when you "config a kernel".

kern/arch/mips/include
These files are include files for the machine-specific constants and functions.

Question 2. Which register number is used for the stack pointer (sp) in OS/161?
Question 3. What bus/busses does OS/161 support?
Question 4. What is the difference between splhigh and spl0?
Question 5. Why do we use typedefs like u_int32_t instead of simply saying "int"?
Question 6: What must be the first thing in the process control block?

kern/arch/mips/mips
These are the low-level functions the kernel needs that are machine-dependent.

Question 7. What does splx return?
Question 8. What is the highest interrupt level?
Question 9. What function is called when user-level code generates a fatal fault?

kern/asst1
This is the directory that contains framework code for one of the assignments at Harvard. You can safely ignore it.
kern/compile
This is where you build kernels. In the compile directory, you will find one subdirectory for each kernel you want to build. In a real installation, these will often correspond to things like a debug build, a profiling build, etc. In our world, each build directory will correspond to a programming assignment, e.g., ASST1, ASST2, etc. These directories are created when you configure a kernel (described in the next section). This directory and build organisation is typical of UNIX installations and is not necessarily universal across all operating systems.
kern/conf
config is a shell script that takes a config file, like ASST1, and creates the corresponding build directory. Later (not now), in order to build a kernel, you will do the following: 
% cd kern/conf
% ./config ASST0
% cd ../compile/ASST0
% make depend
% make
This will create the ASST0 build directory and then actually build a kernel in it. Note that you should specify the complete pathname ./config when you configure OS/161. If you omit the ./, you may end up running the configuration command for the system on which you are building OS/161, and that is almost guaranteed to produce rather strange results!
kern/include
These are the include files that the kernel needs. The kern subdirectory contains include files that are visible not only to the operating system itself, but also to user-level programs.

Question 10. How frequently are hardclock interrupts generated?
Question 11. What functions comprise the standard interface to a VFS device?
Question 12. How many characters are allowed in a volume name?
Question 13. How many direct blocks does an SFS file have?
Question 14. What is the standard interface to a file system (i.e., what functions must you implement to implement a new file system)?
Question 15. What function puts a thread to sleep?
Question 16. How large are OS/161 pids?
Question 17. What operations can you do on a vnode?
Question 18. What is the maximum path length in OS/161?
Question 19. What is the system call number for a reboot?
Question 20. Where is STDIN_FILENO defined?

kern/main
This is where the kernel is initialised and where the kernel main function is implemented.

Question 21. What does kmain() do?

kern/thread
Threads are the fundamental abstraction on which the kernel is built.

Question 22. Is it OK to initialise the thread system before the scheduler? Why (not)?
Question 23. What is a zombie?
Question 24. How large is the initial run queue?

kern/lib
These are library routines used throughout the kernel, e.g., managing sleep queues, run queues, kernel malloc, etc.
kern/userprog
This is where to add code to create and manage user level processes. As it stands now, OS/161 runs only kernel threads; there is no support for user level code.
kern/vm
This directory is also fairly vacant. Virtual memory would be mostly implemented in here.
kern/fs
The file system implementation has two subdirectories. We'll talk about each in turn.
kern/fs/vfs
This is the file-system independent layer (vfs stands for "Virtual File System"). It establishes a framework into which you can add new file systems easily. You will want to review vfs.h and vnode.h before looking at this directory.

Question 25. What does a device name in OS/161 look like?
Question 26. What does a raw device name in OS/161 look like?
Question 27. What lock protects the vnode reference count?
Question 28. What device types are currently supported?

kern/fs/sfs
This is the simple file system that OS/161 contains by default. You may augment this file system as part of a future assignment, so we'll ask you questions about it then.
kern/dev
This is where all the low level device management code is stored. You can safely ignore most of this directory.

This concludes the non-assessable reading component of the assignment. Feel free to discuss your answers with fellow students, your tutor, and lab demonstrator. Basically, anybody who will listen :-)

Building a Kernel

Now to the business end of this assignment. You will now build and install a kernel.

Running your Kernel

If you have made it this far, your have built and installed the entire OS. Now it is time to run it.

Using GDB

I cannot stress strongly enough to you the need to learn to use GDB. You can find directions and a short tutorial on using GDB with os161 here. Note: the version of gdb used for these assignments is cs161-gdb.

Modifying your Kernel

We will now go through the steps required to modify and rebuild your kernel. We will add a new file to the sources. The file contains a function we will call from existing code. We need to add the file to the kernel configuration, re-config the kernel, and the rebuild again. Note: If you simply modify a file in an already configed source tree, you can simply run make again to rebuild, followed by make install. You only need to reconfig if you add or remove a file from the config, and you only need to make depend if you add (or modify) a #include directive.

Some practice with CVS

Now we will perform some operations with CVS. Check to see if your kernel builds again.

Note: Your partner and you share the same cvs repository. When you run cvs update your checked out copy will be updated to the most recent version committed to the repository by you or your partner. Later you can use this feature to work on the same assignment separately.

The Assessable part of Assignment 0

This assignment is worth a possible 10 marks of the class mark component of your assessment

The task

Follow the above instructions to add the given file to the operating system. Once you have found (using GDB) and fixed the bugs, you have completed the assignment. Make sure you see the Hello World!!! output just prior to the menu prompt. 
sys161: System/161 release 1.1, compiled Feb 24 2003 21:57:51

OS/161 base system version 1.10
Copyright (c) 2000, 2001, 2002, 2003
   President and Fellows of Harvard College.  All rights reserved.

Put-your-group-name-here's system version 0 (ASST0 #3)

Cpu is MIPS r2000/r3000
344k physical memory available
Device probe...
lamebus0 (system main bus)
emu0 at lamebus0
ltrace0 at lamebus0
ltimer0 at lamebus0
hardclock on ltimer0 (100 hz)
beep0 at ltimer0
rtclock0 at ltimer0
lrandom0 at lamebus0
random0 at lrandom0
lser0 at lamebus0
con0 at lser0
pseudorand0 (virtual)

Hello World!!!
OS/161 kernel [? for menu]:
Check your assignment works with the menu choice supplied on the command line as follows. 
% sys161 kernel q
This is generally the way we test your submission.

Once your assignment works, you should check it back into your repository. Only one member of the group needs to submit. I suggest you do the following together for this assignment. 

% cd ~/cs3231/asst0-src
% cvs commit
You should now tag your repository so you can always return to the point in the future. You can choose any tag name you like. You can only use a tag name once, choose a different tag name if you choose to resubmit later.. We chose asst0-final in the instructions below. 
 
% cd ~/cs3231/asst0-src 
% cvs tag asst0-final
To see what changes you made to do this assignment, type 
% cd ~/cs3231/src
% cvs -q rdiff -r asst0-base -r asst0-final -c asst0-src
The arguments to rdiff are as follows

Generating your submission

You will be submitting a diff of your changes to the original tree. So generate a file containing this diff. 
% cvs -q rdiff -r asst0-base -r asst0-final -u asst0-src > ~/asst0.diff

Testing Your Submission

During week 3, we will provide an "oracle" that you can use to check the correctness of assignment submission. Stay tuned.

Until then, look here for information on testing and resubmitting your assignment.

Submitting Your Assignment

Now submit the diff as your assignment. 
% cd ~
% give cs3231 asst0 asst0.diff
You're now done.

Even though the generated diff output should represent all the changes you have made to the supplied code, occasionally students do something "ingenious" and generate non-representative diff output.

Always keep your cvs repository so that we may recover your assignment should something go wrong.

Note: If for some reason you need to change and re-submit your assignment after you have tagged it asst0-final, you will need to either delete the asst0-final tag, commit the new changes, re-tag, and re-diff your assignment, or choose a different final tag name and commit the new changes, tag with the new tag, and re-diff with the new tag. To delete a cvs tag, use 

% cvs rtag -d asst0-final asst0-src