1. Due Dates and Mark Distribution

Due Date: 8am, Fri May 4th

Marks: Worth 25 marks (of the 100 available for the class mark component of the course)

The 10% bonus for one week early is available for the basic assignment.

2. Introduction

In this assignment you will be implementing a set of file-related system calls. Upon completion, your operating system will be able to run a single application at user-level and perform some basic file I/O.

A substantial part of this assignment is understanding how OS/161 works and determining what code is required to implement the required functionality. Expect to spend at least as long browsing and digesting OS/161 code as actually writing and debugging your own code.

If you attempt the advanced part, you will add process related system calls and the ability to run multiple applications.

Your current OS/161 system has minimal support for running executables, nothing that could be considered a true process. Assignment 2 starts the transformation of OS/161 into something closer to a true operating system. After this assignment, it will be capable of running a process from actual compiled programs stored in your account. The program will be loaded into OS/161 and executed in user mode by System/161; this will occur under the control of your kernel. First, however, you must implement part of the interface between user-mode programs ("userland") and the kernel. As usual, we provide part of the code you will need. Your job is to design and build the missing pieces.

Our code can run one user-level C program at a time as long as it doesn't want to do anything but shut the system down. We have provided sample user programs that do this (reboot, halt, poweroff), as well as others that make use of features you might be adding in this and future assignments. So far, all the code you have written for OS/161 has only been run within, and only been used by, the operating system kernel. 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 give you two system calls: sys_reboot() in startup/main.c and sys_time() in syscall/time_syscalls.c. In GDB, if you put a breakpoint on sys_reboot() and run the "reboot" program, you can use "backtrace" to see how it got there.

For those attempting the advanced version of the assignment, you will also be implementing the subsystem that keeps track of multiple tasks. You must decide what data structures you will need to hold the data pertinent to a "process" (hint: look at kernel include files of your favorite operating system for suggestions, specifically the proc structure.) The first step is to read and understand the parts of the system that we have written for you.

In the beginning, you should tackle this assignment by producing a DESIGN DOCUMENT. The design document should clearly reflect the development of your solution. They should not merely explain what you programmed. If you try to code first and design later, or even if you design hastily and rush into coding, you will most certainly end up in a software "tar pit". Don't do it! Plan everything you will do. Don't even think about coding until you can precisely explain to your partner what problems you need to solve and how the pieces relate to each other. Note that it can often be hard to write (or talk) about new software design, you are facing problems that you have not seen before, and therefore even finding terminology to describe your ideas can be difficult. There is no magic solution to this problem; but it gets easier with practice. The important thing is to go ahead and try. Always try to describe your ideas and designs to someone else. In order to reach an understanding, you may have to invent terminology and notation, this is fine. If you do this, by the time you have completed your design, you will find that you have the ability to efficiently discuss problems that you have never seen before. Why do you think that CS is filled with so much jargon? To help you get started, we have provided the following questions as a guide for reading through the code. We recommend that you answer questions for the different modules and be prepared to discuss them in your Week 8 tutorial. Once you have prepared the answers, you should be ready to develop a strategy for designing your code for this assignment.

loadelf.c

runprogram.c

In the advanced assignment, runprogram() is a good base for writing the execv() system call, but only a base. When writing your design doc, you should determine what more is required for execv() that runprogram() does not need to worry about. Once you have design your process framework, runprogram() should be altered to start processes properly within this framework.

Questions

1. What are the ELF magic numbers?
2. In runprogram(), why is it important to call vfs_close before going to usermode?
3. What function forces the processor to switch into usermode? Is this function machine dependent?

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 userlevel programs, so this is a good file to read very carefully. You should also examine the code in lib/uio.c.

Questions

4. What is the difference between UIO_USERISPACE and UIO_USERSPACE? When should one use UIO_SYSSPACE instead?
5. Why can the struct uio that is used to read in an ELF segment be allocated on the stack in load_segment() (i.e., where does the memory read actually go)?
6. In what file are copyin() and copyout() defined? memmove()? Why can't copyin() and copyout() be implemented as simply as memmove()?

locore/trap.c

mips_trap() is the key function for returning control to the operating system. This is the C function that gets called by the assembly exception handler. kill_curthread() is the function for handling broken user programs; when the processor is in usermode and hits something it can't handle (say, a bad instruction), it raises an exception. There's no way to recover from this, so the OS needs to kill off the process. The advance part of this assignment will include writing a useful version of this function.

syscall/syscall.c

syscall() is the function that delegates the actual work of a system call off to the kernel function that implements it. Notice that reboot and time are the only cases currently handled.

Questions

7. What is the numerical value of the exception code for a MIPS system call?
8. How many bytes is an instruction in MIPS? (Answer this by reading syscall() carefully, not by looking somewhere else.)
9. What is the contents of the struct trapframe? Where is the struct trapframe that is passed into syscall() stored?
10. What would be required to implement a system call that took more than 4 arguments?
11. What is the purpose of userptr_t?

errno.c

syscalls-mips.S

Questions

12. What is the purpose of the SYSCALL macro?
13. What is the MIPS instruction that actually triggers a system call? (Answer this by reading the source in this directory, not looking somewhere else.)

The files vfs.h and vnode.h in this directory contain function declarations and comments that are directly relevant to this assignment.

Questions

14. How are vfs_open, vfs_close used? What other vfs_() calls are relevant?
15. What are VOP_READ, VOP_WRITE? How are they used?
16. What does VOP_TRYSEEK do?
17. Where is the struct thread defined? What does this structure contain?

3.7. fork()

Answer these questions by reading the fork() man page and the sections dealing with fork() in the textbook.

Questions

18. What is the purpose of the fork() system call?
19. What process state is shared between the parent and child?
20. What process state is copied between the parent and child?

SVN setup

Only one of you needs to do the following. In this section, you will be setting up the svn repository that will contain your code. We suggest your partner sit in on this part of the assignment.

Import the OS/161 sources into your repository as follows:

% cd /home/cs3231/assigns
% svn import asst2/src file:///home/osprjXXX/repo/asst2/trunk -m "Initial import"

Make an immediate branch of this import for easy reference when you generate your diff:

% svn copy -m "Tag initial import" file:///home/osprjXXX/repo/asst2/trunk file:///home/osprjXXX/repo/asst2/initial

Checkout

The following instructions are now for both partners. You have now completed setting up a shared repository for both partners. We'll assume your cs3231 directory is intact from the previous assignment. Change to your directory:

% cd ~/cs3231

Now checkout a copy of the os161 sources to work on from your shared repository:

% svn checkout file:///home/osprjXXX/repo/asst2/trunk asst2-src

Configure OS/161 for Assignment 2

Before proceeding further, configure your new sources.

% cd ~/cs3231/asst2-src
% ./configure

Unlike previous the previous assignment, you will need to build and install the user-level programs that will be run by your kernel in this assignment.

% cd ~/cs3231/asst2-src
% bmake
% bmake install

For your kernel development, again we have provided you with a framework for you to run your solutions for ASST2.

You have to reconfigure your kernel before you can use this framework. The procedure for configuring a kernel is the same as in ASST0 and ASST1, except you will use the ASST2 configuration file:

% cd ~/cs3231/asst2-src/kern/conf
% ./config ASST2

Building for ASST2

% cd ../compile/ASST2
% bmake depend
% bmake
% bmake install

If you are told that the compile/ASST2 directory does not exist, make sure you ran config for ASST2.

Command Line Arguments to OS/161

IMPORTANT: Please DO NOT change these menu option strings!

Running "asst2"

Implement the following file-based system calls. The full range of system calls that is listed in kern/include/kern/syscall.h. For this assignment you should implement: open, read, write, lseek, close, dup2. Note: You are implementing the kernel code that implements the system call functionality within the kernel. The C stubs that user-level applications call to invoke the system calls are already automatically generated when you build OS/161.

Note that the basic assignment does not involve implementing fork() (that's part of the advanced assignment). However, the design and implentation of your system calls should nonetheless not assume a single process.

What primitive operations exist to support the transfer of data to and from kernel space? Do you want to implement more on top of these?

You will need to "bullet-proof" the OS/161 kernel from user program errors. There should be nothing a user program can do to crash the operating system when invoking the file system calls. It is okay in the basic assignment for the kernel to panic for an unimplemented system call (e.g. execv()), or a user-level program error.

Decide which functions you need to change and which structures you may need to create to implement the system calls.

How you will keep track of open files? For which system calls is this useful?

For additional background, consult one or more of the following texts for details how similar existing operating systems structure their file system management:

You should first commit your changes back to the repository using the following command. Note: You will have to supply a comment on your changes. You also need to coordinate with your partner that the changes you have (or potentially both have) made are committed consistently by you and your partner, such that the repository contains the work you want from both partners.

% cd ~/cs3231/asst2-src
% svn commit

If the above fails, you may need to run svn update to bring your source tree up to date with commits made by your partner. If you do this, you should double check and test your assignment prior to submission.

Beware! If you have created new files for this assignment, they will not be included in your submission unless you add them, using svn add:

% svn add filename.c

Now generate a file containing the diff.

% cd ~
% svn diff file:///home/osprjXXX/repo/asst2/initial file:///home/osprjXXX/repo/asst2/trunk >~/asst2.diff

Testing Your Submission

fork()

Implement a simplified form of the fork() system call. Your implementation of fork should be the same as that described in the man page, except that it should return 1 to the parent (rather than the child's PID).

The amount of code to implement fork is quite small; the main challenge is to understand what needs to be done. We strongly encourage you to implement the file-related system calls first, with fork in mind.

Some hints:

• Read the comments above mips_usermode() in kern/arch/mips/mips/trap.c
• Read the comments in kern/include/addrspace.h, particularly as_copy().
• You will need to copy the trapframe from the parent to the child. You should be careful how you do this, as there is a possible race condition (where?/why?).
• You may wish to base your implementation on the thread_fork() function in kern/thread/thread.c.

getpid()

A pid, or process ID, is a unique number that identifies a process. The implementation of getpid() is not terribly challenging, but pid allocation and reclamation are the important concepts that you must implement. It is not OK for your system to crash because over the lifetime of its execution you've used up all the pids. Design your pid system; implement all the tasks associated with pid maintenance, and only then implement getpid(). When your pid system is working correctly, change your fork() implementation to return the child's pid to the parent, rather than 1.

execv(), waitpid(), _exit()

Although it may seem simple at first, waitpid() requires a fair bit of design. Read the specification carefully to understand the semantics, and consider these semantics from the ground up in your design. You may also wish to consult the UNIX man page, though keep in mind that you are not required to implement all the things UNIX waitpid() supports, nor is the UNIX parent/child model of waiting the only valid or viable possibility. The implementation of _exit() is intimately connected to the implementation of waitpid(). They are essentially two halves of the same mechanism. Most of the time, the code for _exit() will be simple and the code for waitpid() relatively complicated, but it's perfectly viable to design it the other way around as well. If you find both are becoming extremely complicated, it may be a sign that you should rethink your design.

kill_curthread()

  char *filename = "/bin/cp";
  char *args[4];
  pid_t pid;
  args[0] = "cp";
  args[1] = "file1";
  args[2] = "file2";
  args[3] = NULL;
  pid = fork();
  if (pid == 0)
    execv(filename, argv);

You can test your implementation using OS/161's shell, /bin/sh.

Some questions to think about:

• Passing arguments from one user program, through the kernel, into another user program, is a bit of a chore. What form does this take in C? This is rather tricky, and there are many ways to be led astray. You will probably find that very detailed pictures and several walk-throughs will be most helpful.
• How will you determine: (a) the stack pointer initial value; (b) the initial register contents; (c) the return value; (d) whether you can exec the program at all?
• What new data structures will you need to manage multiple processes?
• What relationships do these new structures have with the rest of the system?
• How will you manage file accesses? When invoke the cat command, and it starts to read file1, what will happen if the shell also tries to read file1? What would you like to happen?
• How you will keep track of running processes. For which system calls is this useful?
• How you will implement the execv system call. How is the argument passing in this function different from that of other system calls?

Submission for the advanced assignment is similar to the basic assignment, except the advance component is given to a distinguished assignment name: asst2_adv Again, you need to generate a diff based on the original source tree.

% cd ~/cs3231/asst2-src
% svn commit

Now generate a file containing the diff. (NOTE: How this works depends on how you have set up branches in svn.)

% cd ~
% svn diff file:///home/osprjXXX/repo/asst2/initial file:///home/osprjXXX/repo/asst2/adv >~/asst2_adv.diff

% cd ~
% give cs3231 asst2_adv asst2_adv.diff