Reading Code

In HW 3, you may have thought of your solutions to the cats-and-mice problem as separate programs, but they were really just functions that were linked into the kernel itself and thus ran inside the kernel, in kernel mode. We used that approach because the kernel wasn't yet able to run meaningful user-space code. In this assignment, you'll be making OS/161 deal with meaningful user-space programs for the first time.

As you start, OS/161's support for user-space programs is limited and incomplete. The only working system call available to user-space code is reboot. Moreover, although the kernel does have a struct proc structure, and even a curproc per-processor variable like curthread that points to the currently active process, there is almost nothing stored in the struct proc structure, and the curproc variable is rarely if ever used. So it's fair to say that the kernel barely knows what a process is.

• Tracking “per-process” information
• Providing system calls that support program I/O (e.g., read, write)
• Providing system calls for managing processes (e.g., fork)

The first step is to read and understand the existing parts of OS/161. At present, OS/161 can run one user-level C program at a time—of course, the only programs that work are reboot, halt, and poweroff, which all (only) use the reboot system call. Understanding how the kernel runs these simple programs should help you in planning what parts of the code you will need to modify.

Loading and Running User-Level Programs; Dealing with User-Space Memory

The directory kern/syscall/ contains the files that are responsible for loading and running user-level programs. Currently, this directory only contains three real source files (described below), although you may want to add more of your own during this assignment. Understanding these files is the key to getting started with your implementation of multiprogramming.

The directories kernel/lib/ and kernel/vm/ also contain code that is relevant to this assignment. In particular, there are files related to copying data between user and kernel space, and to managing the virtual memory of the system. You don't need to understand all of this code in detail yet; there are a few files we'll highlight here that are particularly relevant.

kern/syscall/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 os161-gcc.)

kern/syscall/runprogram.c

This file contains only one function, runprogram, which is responsible for running a program from the kernel menu. It is a good base for writing the execv system call, but only a base—you will need to determine what else is required for execv that runprogram does not need to worry about. Additionally, once you have designed your process system, runprogram should be altered to start processes properly within this framework; for example, a program started by runprogram should have the standard file descriptors available while it's running.

kern/syscall/time_syscalls.c

This file implements a single system call, __time, which returns the current time in seconds and nanoseconds. __time is a simple system call that demonstrates how to pass data from the kernel to user space, and, in particular, that data in memory for user space must never be directly accessed by the kernel. Instead, special functions are provided to correctly copy data between kernel and user space.

kern/syscall/file_syscalls.c and kern/syscall/proc_syscalls.c

These files are essentially empty. You will be adding code to them as you implement the file and process system calls for this assignment.

kern/lib/uio.c

This file contains functions for moving data between kernel and user space. Knowing when and how to cross this boundary is critical to properly implementing user-level programs, so be sure to read this file very carefully.

kern/vm/copyinout.c

This file contains a number of useful functions for copying data between kernel and user space. You will need to use these functions when implementing system calls that involve moving data between kernel and user space when the calls don't specifically involve file I/O.

Virtual File System Support

OS/161 supports multiple kinds of file systems as well as other devices such as the console. To allow all of these systems to be accessed in a uniform way, OS/161 uses a virtual file system (VFS) layer. The VFS layer is responsible for managing the file system and device drivers, and for providing a uniform interface to the rest of the kernel.

kern/include/vfs.h and kern/include/vnode.h

These header files contain the definitions of the structures and functions that are used to interact with the VFS layer.

For this assignment, in vfs.h we care about the “VFS layer high-level operations on pathnames” section, which contains the functions that are used to open and close files, as well as change the current working directory. Notably, vfs_open returns (via a pointer argument) a struct vnode* object, which is the VFS layer's representation of an open file.

In vnode.h, we care about VOP_ macros; in particular, VOP_READ, VOP_WRITE, and VOP_ISSEEKABLE. All these operations are described in the comment “Abstract operations on a vnode.”, although the struct vnode_ops structure will help you determine what the argument and return types are for these functions. VFS and vnode functions that read and write data do so via struct uio objects, which describe a place to put or get data, either in kernel or user space.

You'll have seen these functions and macros used in the code you reviewed above for loading the ELF executable. You can also see more examples in kern/test/ftest.c, which performs various stress tests on the file system.

Traps & System Calls

As you saw in Homework 1, 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 exception handler, which sets up a “trap frame” and calls into the operating system. Since “exception” is such an overloaded term in computer science, operating system lingo for an exception is a “trap”. Interrupts are exceptions, and, more significantly for this assignment, so are system calls.

The code in the directory kern/arch/mips is responsible for handling traps and system calls.

kern/arch/mips/locore/trap.c

mips_trap is the key function for returning control to the operating system. It is the C function that gets called by the assembly exception handler. md_usermode is the key function for returning control to user programs. kill_curthread is the function for handling broken user programs—when the processor is in user mode and hits something it can't handle (say, a bad instruction), it raises an exception. There's no way to recover from this problem, so the OS needs to kill off the process. Part of this assignment will be to write a useful version of this function.

kern/arch/mips/syscall/syscall.c

syscall() is the function that delegates the actual work of a system call to the kernel function that implements it. Notice that only two system calls are currently handled: reboot and __time, but these two should give you a good idea of what you'll have to add when you implement additional system calls.

You will also find a function, enter_forked_process, which is a half-written stub where you will place your code to implement the fork system call. Your code for sys_fork should eventually end up calling this function (from a newly created thread and process) to start a new process running.

Process Support

The directory kern/proc contains the files that are responsible for managing processes. Currently, this directory only contains a few real source files (described below), although you may want to add more of your own during this assignment. Understanding these files is the key to getting started with the implementation of multiprogramming.

kern/include/limits.h and kern/include/kern/limits.h

There are various constants for fixed limits in OS/161, such as the maximum number of open files per process, the maximum number of processes, and so on. Knowing what these constants are will help when you're designing your process system.

kern/proc/proc.c and kern/include/proc.h

These files contain the struct proc structure and the functions that manipulate it. The struct proc structure is the kernel's representation of a process. Currently, it keeps track of the process's address space and current directory. You will need to add fields to this structure to keep track of the process's file descriptors, process id, and other information you deem necessary.

Other (Stub) Files in kern/proc/

We've also provided essentially empty files in kern/proc/ for you to fill in as you implement the process system calls for this assignment:

• kern/proc/pid.c and kern/include/pid.h, which will contain the code for managing process IDs.
• kern/proc/filetable.c and kern/include/filetable.h, which will contain the code for managing file descriptors.
• kern/proc/openfile.c and kern/include/openfile.h, which will contain the code for managing open-file objects (what file descriptors refer to).

You are not required to use these files, but they reflect a reasonable way to organize your code, and will help others understand your final patch for OS/161. If you choose not to use them, delete them from your GitHub repository and remove them from config/conf.kern so they are not compiled.

Userland

Although you'll mostly be working with kernel code in this assignment, the programs you'll eventually be able to run on OS/161 (and the user-level support code for those programs) found in the userland/ directory are also important to know about.

userland/lib/crt0/

This is the user program startup code. There's only one file in here, mips-crt0.S, which contains the MIPS assembly code that receives control first when a user-level program is started. It calls the user program's main function. Your execv implementation will be interfacing to this code, so be sure to check what values it expects to appear in what registers and so forth.

userland/lib/libc/

The user-level C library. There's obviously a lot of code 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.

userland/lib/libc/unix/errno.c

Defines the global variable errno.

userland/lib/libc/arch/mips/syscalls-mips.S

Contains the machine-dependent code necessary for implementing the user-level side of MIPS system calls.

build/userland/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 true names of the system calls are placed in this file using a script called userland/lib/libc/syscalls/gensyscalls.sh that pulls them from the kernel's header files and generates the appropriate assembly code. This approach avoids our having to make (and maintain) a second list of the system calls.

(When logged in, completion status appears here.)

Go to Parent Page Next Page