About this Guide
The first big challenge you'll encounter in this course is getting a handle on the existing OS/161 code. Working with a large body of code written by others is extremely challenging. To familiarize yourself with a code base, you must sit down and read some code. There is no substitute. This may seem tedious, but if you understand how the system fits together now, you will have much less difficulty completing future assignments.
You don't need to read every line from beginning to end. Instead, your reading should be directed and guided by what you need to accomplish. For example, you don't need to understand most of the assembly code in the codebase; it is not important for this course. Similarly, you don't yet need to understand the file system code, though you should know that it exists, so that you can find it for later in the course. For now, what you need is a solid vision of the overall organization of the code base. The goal is to become familiar enough with the code that you can find the code you need and make intelligent design decisions in the assignments in this course. This page gets you started by describing the overall structure of OS/161 source tree and then explaining how the operating system works with the underlying "hardware" (System/161).
The OS/161 Source Tree
Top Level
The top level directory of many software packages is called src or source. The top of the OS/161 source tree is also called src. The OS/161 source tree contains both user-level code (C library and test programs) that are intended to run on top of OS/161 and the OS/161 kernel code itself. There are also the Makefiles and other scripts needed to build the code distribution.
In the top-level src directory, you will find the following relevant files:
- Makefile: The top-level makefile; builds the OS/161 distribution, including all the provided utilities, but does not build the operating system kernel.
- configure: This is an autoconf-like script. It sets up things like `How to run the compiler.' You should only need to run configure once.
- sys161.conf: A configuration file for the emulator. Copy this file into your root OS/161 directory.
You will also find the following directories:
- user: A directory containing source code for user-level utilities and test files.
- kern: Here is where the kernel source code lives. All other directories with code in the src directory contain user-level code. (To be honest, the kernel and user-level code share the same C library code, but it has been hacked to support this).
- man and design: The OS/161 manual ("man pages") appear here. The man pages document (or specify) every program, every function in the C library, and every system call. You will use the system call man pages for reference for several assignments. The man pages are HTML and can be read with any browser. The latter directory contains programmer documentation.
- mk: This directory contains pieces of makefile that are used for building the system. You don't need to worry about these for this course, although in the long run we do recommend that anyone working on large software systems learn to use make effectively.
You don't need to understand every line in every executable in bin and sbin, but it is worth the time to peruse a couple to see how they work. Eventually, you may want to modify these and/or write your own utilities and these are good models. Similarly, you need not read and understand everything in lib and include, but you should know enough about what's there to be able to get around the source tree easily.
The user Subdirectory
The user-level applications provided with the operating system are organized into several categories.
- bin: Source code for all the utilities that are typically found in /bin, e.g., cat, cp, ls, etc. live here. The things in bin are considered "fundamental" utilities that the system needs to run. Again, these are run as user-level programs.
- include: These are the include files that you would typically find in /usr/include (in our case, a subset of them). These are user level include files; not kernel include files.
- sbin: This is the source code for the utilities typically found in /sbin on a typical UNIX installation. In our case, there are some utilities that let you halt the machine, power it off and reboot it, among other things. As with the /bin utilities, these programs are run as user-level code.
- testbin: These are pieces of user-level test code for testing system call implementations. Most of these will not work until later in the course, once you have added new functionality to the operating system.
- lib: Library code lives here. We have only two libraries: libc, the C standard library, and hostcompat, which is for recompiling OS/161 programs for the host UNIX system. There is also a crt0 directory, which contains the startup code for user programs.
The kern Subdirectory
Once again, there is a Makefile. This Makefile installs header files but does not build anything. In addition, you will find multiple subdirectories -- one for each component of the kernel as well as some utility directories.
-
kern/arch: Architecture-specific code goes here.
Architecture-specific code differs depending on the hardware
platform on which you're running. Only the mips
subdirectory is relevant to this course.
- kern/arch/mips/conf: Configuration files for this architecture.
- kern/arch/mips/include: Include files for machine-specific constants and functions.
- kern/arch/mips/*: The source files containing the machine-dependent code that the kernel needs to run. Most of this code is quite low-level. The syscall subdirectory will be especially important as you extend the OS.
- kern/compile: You will build kernels here. 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 organization is typical of UNIX installations and is not universal across all operating systems.
- kern/conf: Configuration information for the various builds is stored in this directory. If you configure a build, a directory is created in the kern/compile directory.
- kern/dev: All the low level device management code is stored here. You can safely ignore most of this directory.
- kern/include: 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. (Think about why it's named "kern" and where the files end up when installed.)
- kern/lib: These are library routines used throughout the kernel, e.g., managing sleep queues, run queues, kernel malloc, etc.
- kern/startup: Code to initialize the kernel lives here. The main function is here, too.
- kern/thread: Threads are the fundamental abstraction on which the kernel is built.
- kern/syscall: Eventually, you will add add code to this subdirectory to create and manage user level processes. Currently, OS/161 supports only a single user-level process at a time, which must be started from the command menu.
- kern/vm: This directory is fairly empty. The key file is copyinout.c, which you need to use to move data from user level to kernel memory and back. Later, you'll implement virtual memory and most of your code will go in here.
- kern/fs: The file system implementation has two subdirectories. The vfs subdirectory contains the file-system independent layer (the "Virtual File System"). It establishes a framework (an interface) into which you can place new file systems. The sfs subdirectory contains the the "Simple File System" that OS/161 uses by default.
- kern/test: A collection of programs for testing kernel-level code. These tests can be invoked from the OS/161 menu. You can add additional kernel tests here, along with menu options to execute them.
Understanding System Calls
One of the first things you will need to do in this course is to implement your own system calls. In this section, we walk through the functions and steps that are involved in (a) starting a user-level program, (b) handling system calls in the OS, and (c) invoking system calls at the user-level. This is an example of the kind of code reading that you should do as you familiarize yourself with a codebase. For maximum benefit, you should run OS/161 under the control of the debugger and browse the source code while working through this section.
User-level Programs
The System/161 simulator can run normal programs compiled from C, and you can create your own programs. (In particular, you will later want to create new user-level test programs that use the system calls you create.) To build programs that can be run by OS/161, they need to be compiled with a cross-compiler, cs161-gcc. This compiler runs on the host machine and produces MIPS executables; it is the same compiler used to compile the OS/161 kernel. To create new user programs, edit the Makefile in bin, sbin, or testbin (depending on where you put your programs) to include your new program and then create a directory similar to those that already exist. Use an existing program and its Makefile as a template.
A Sample System Call
In a real operating system, the kernel's main function is to provide support for user-level programs. Most such support is accessed via "system calls." We have given you one system call, reboot(), which is implemented in the function sys_reboot() in src/kern/startup/main.c. In GDB, if you put a breakpoint on sys_reboot and run the "reboot" program (by typing "p sbin/reboot" at the OS/161 menu prompt), you can use "backtrace" to see how it got there. In the next few sections, we'll investigate how this system call was invoked, and we'll begin by looking a the function calls in the stack trace you just saw.
Starting a User-level Program: menu.c
Examine kern/startup/menu.c to see how the "p" menu command is handled. This command allows us to load and execute a single user-level program. We will describe it in great detail, most of which is not of immediate critical importance. You will need to understand this eventually, however, and the sooner the better.
The menu() function loops forever printing the menu prompt, getting a string from the console, and calling menu_execute to handle the input. Looking at menu_execute, we see that it separates the input into individual commands (indicated by a semi-colon) and then calls cmd_dispatch for each command. In cmd_dispatch, the name of the command is separated from its arguments, and the name is looked up in the cmdtable data structure. This table stores the string name of each menu command and a function pointer to the function that should handle that command.
Looking at the cmdtable declaration, we find that the "p" command is handled by calling the cmd_prog function. This function simply strips off the "p" part and passes the rest of the input to the common_prog function. Looking at common_prog we see that it calls thread_fork, creating a new thread to run the specified user-level program. Following this call to thread_fork, our system has 2 threads - the initial boot thread that runs the menu() loop, and this new thread that runs the requested user-level program. You can look at kern/thread/thread.c to see what thread_fork() does, but the important thing right now is that the fourth argument to thread_fork specifies the function that the new thread should start executing (in this case, cmd_progthread), and the second and third arguments to thread_fork are the arguments to pass to that function (in this case, the name of the program to load). The cmd_progthread function calls runprogram, passing it the name of the program to load and execute. Note that if runprogram is successful, the thread will continue with the execution of the user-level program and will never return to cmd_progthread. Now let's consider how runprogram operates.
Starting a User-level Program: kern/syscall
The kern/syscall directory contains the files that are responsible for the loading and running of user-level programs. Currently, the only files in the directory are loadelf.c, runprogram.c, and time_syscalls.c. Understanding these files will be very important if you implement fork, but for the time being, a basic understanding of how a user program is loaded and executed is sufficient.
runprogram.c contains only one function, runprogram(), which is responsible for running a program from the kernel menu. It uses the virtual file system operations to open the file containing the program we want to load, creates an address space for the thread, and loads the program into that address space, using the load_elf function. If loading the program is successful, runprogram then sets up the user stack area in the address space, and calls md_usermode to switch to user mode and start running the user program. (You will be learning more about how md_usermode works later this term. Essentially, it does some setup so that a "return from exception" takes control to the entry point of the user program, even though we did not enter the kernel through an exception.)
loadelf.c contains the functions responsible for loading an ELF executable from the filesystem and into virtual memory space. (ELF is the name of the executable format produced by cs161-gcc.) Of course, at this point this virtual memory space does not provide what is normally meant by virtual memory -- although there is translation between the addresses that executables "believe" they are using and physical addresses, there is no mechanism for providing more memory than exists physically. Don't worry about this until you need to work on virtual memory.
In addition to these two files, you'll need a file from the kern/lib directory. uio.c contains functions for moving data between kernel and user space. Knowing when and how to cross this boundary is critical to properly implementing userlevel programs, so read this file very carefully. You should also examine the code in vm/copyinout.c. For example, you should be using copyinstr to get strings from the user address space.
Getting to System Mode: Traps and Syscalls: kern/arch/mips
Once a user program is running, it requests service from the OS using system calls. To get there, it must generate an exception. Exceptions are the key to operating systems; they are the mechanism that enables the OS to regain control of execution and therefore do its job. You can think of exceptions as the interface between the processor and the operating system. When the OS boots, it installs an "exception handler" (carefully crafted assembly code) at a specific address in memory. When the processor raises an exception, it invokes this, which sets up a "trap frame" and calls into the operating system. The business of initializing the trap frame and returning from an exception is all done in assembly code, and can be found in kern/arch/mips/locore/exception-mips1.S.
You don't need to be able to read MIPS assembly code -- the comments in this file are reasonably good. You can see how all the registers are saved ("sw" == "store word"), followed by a call to the mips_trap function ("jal" == "jump and link" == function call). On return from mips_trap, all of the saved state is restored ("lw" == "load word") and execution resumes at the point where the exception occurred. The mips_trap function (in kern/arch/mips/locore/trap.c) is the key. This is the C function that gets called by the assembly language exception handler. It includes code to determine what type of exception occurred, and to dispatch an appropriate handler. If the exception code is EX_SYS, then syscall is called to handle the system call, passing it the trapframe.
Note: The mips_trap code is special, in that it does not really belong to either the operating system or the user. It's a special piece of code that is invoked directly by the hardware -- or, in our case, System/161. It's trusted code that makes sure that no user can take control of the system and that the operating system is called whenever administrative tasks are needed.
Now, continuing from syscall's use of a trapframe, look at the definition of struct trapframe in kern/arch/mips/include. We can see that a trap frame includes space to save all the processor registers that the user program might have been using, as well as some additional state that identifies the cause of the exception (the "tf_cause" field), and the instruction that was being executed when the exception occurred (the "tf_epc" field -- note that epc == "Exception PC" == contents of the program counter register when the exception occurred).
Note: Since "exception" is such an overloaded term in computer science, operating system lingo for an exception is a "trap" -- when the OS traps execution. Interrupts are exceptions, and more significantly for this assignment, so are system calls. Specifically, syscall.c handles traps that happen to be system calls.
Handling the System Call: kern/arch/mips/mips/syscall.c
mips_syscall() in kern/arch/mips/syscall/syscall.c is the function that delegates the actual work of a system call to the kernel function that implements it. Read the comments at the top of this file carefully! In syscall, we begin by extracting the system call number from the trapframe's tf_v0 field. This means that the system call number was stored in register v0 prior to executing the syscall instruction. Then we simply switch on the system call number, with a separate "case" to handle each possible system call. Notice that reboot() and a timing call are the only cases currently handled. These system call numbers are all defined in kern/include/kern/callno.h. You should add new entries to this file for any system calls that you need to create.
Following the switch statement, we prepare to return from the system call. The user-level side of the system call expects to find the result of the system call in register v0, with register a3 indicating whether or not an error occurred. We accomplish this by setting the appropriate fields in the trapframe, which will be loaded into the machine registers before returning control to the user program. Finally, we have to advance the program counter to the next instruction, so that the syscall instruction will not be repeated. This is done by incrementing the tf_epc field of the trapframe.
The User-level Side of a System Call
Now that we understand the system side, let's look at the user-level interface to system calls. Most of this will be encapsulated in C library functions.
user/lib/libc/: This is the user-level C library. There's obviously a lot of code in the subdirectories here. We don't expect you to read it all, although it may be instructive in the long run to do so. Job interviewers have an uncanny habit of asking people to implement standard C library functions on the whiteboard. For present purposes you need only look at the code that implements the user-level side of system calls, which we detail below.
user/lib/unix/errno.c: This is where the global variable errno is defined. Note that this variable is a global within a user-level C program. You cannot set errno for a user-level program by setting a variable named "errno" in the kernel.
user/lib/arch/mips/syscalls-mips.S: This file contains the machine-dependent code necessary for implementing the user-level side of MIPS system calls. It consists of a C pre-processor "define" that declares the body of each system call. The body of each system call is identical, except that a different system call number "num" is used. This body simply loads the system call number (as defined in kern/include/kern/syscall.h) into register v0 and then jumps to the code common to all system calls at the __syscall label. (Compare this with the OS side where the system call number is extracted from the "tf_v0" field of the trapframe).
You may notice that it looks like the code jumps to the __syscall label before setting the system call number. This is just a peculiarity of the MIPS architecture -- the instruction immediately following a branch is called a "delay slot" which means that an instruction can be scheduled and executed during a branch. Such instructions appear immediately after the branch instruction itself. Thus, the "addiu v0, $0, SYS_##sym" happens before we get to the common syscall code at the label __syscall. It's odd -- but try not to be too disturbed. Hardware developers hack in little bits of performance whenever they can.
Now, look at the assembly code at the __syscall label. The common system call code begins with the syscall instruction, which causes a "system call exception" (handled by System/161) and transfers control to the OS as outlined above. The "tf_epc" field in the trapframe on the OS side points to this instruction, and we finish our system call handler by setting "tf_epc" to the next instruction, so on return from the system call we execute the "beq" instruction. This instruction tests if the system call failed or succeeded (recall the system side sets "tf_a3" to 1 on error, and 0 on success). If an error occurred, we take the error code from the v0 register and store it into the global variable errno, and set the return value of the system call (the v0 register) to "-1". If no error occurred, then the OS put the result of the system call into "tf_v0" and we can just return.
build/user/lib/libc/syscalls.S: This file is created from syscalls-mips.S at compile time and is the actual file assembled into the C library. The actual names of the system calls are placed in this file using a script called gensyscalls.sh that reads them from the kernel's header files. This avoids having to make a second list of the system calls. In a real system, typically each system call stub is placed in its own source file, to allow selectively linking them in. OS/161 puts them all together to simplify the makefiles. Adding new entries to kern/include/kern/syscall.h automatically causes new user-level system call procedures to be defined when you re-build the user-level code. Each "SYSCALL(name,num)" macro statement in this file is expanded by the C pre-processor into a declaration of the appropriate system call function.
src/user/include/unistd.h: unistd.h contains the user-level interface definition of the system calls for OS/161 (including ones you will implement in later assignments). The only thing you need to do to complete the user-level system call interface is declare prototypes for your new system calls in unistd.h. Everything else (on the user side) happens automatically when you re-build after updating callno.h.
Note that the user-level interface defined in unistd.h is different from that of the kernel functions that you will define to implement these calls. You need to declare the kernel functions in kern/include/syscall.h.