Assignment 2: System calls and processes

1. Due Dates and Mark Distribution

Due Date: 8am, Fri May 5th

Marks: Worth 30 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.

The advanced assignment is assessable for COMP3891/COMP9283 students. It is worth 5 marks of the 100 class marks available.

COMP3231/COMP9201 students can do the advanced part with the permission of the lecturer, and only if basic assignment is completed a week prior to the deadline. Marks obtained are added to any shortfall in the class mark component up to a maximum of 10 bonus marks overall for all assignments.

A small number of additional bonus marks are available as described in the advanced section.

The familiarisation questions contained herein are the subject of your week 8 tutorial. Please answer the questions and bring them to your tutorial.

User-level programs

Our System/161 simulator can run normal C programs if they are compiled with a cross-compiler, os161-gcc. This runs on a host (e.g., a Linux x86 machine) and produces MIPS executables; it is the same compiler used to compile the OS/161 kernel. Various user-level programs already exist in userland/bin, userland/testbin, and userland/sbin. Note: that only a small subset these programs will execute successfully due to OS/161 only support a small subset of system calls.

To create new user programs (for testing purposes), you need to edit the Makefile in bin, sbin, or testbin (depending on where you put your programs) and then create a directory similar to those that already exist. Use an existing program and its Makefile as a template.

Design

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.

3. Code walk-through

Bring your answers to the code walk-through questions to your week 8 tutorial.

3.1 General system calls

kern/arch/mips/: traps and syscalls

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. 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 syscalls. Understanding at least the C code in this directory is key to being a real operating systems junkie, so we highly recommend reading through it carefully. The code is also covered in the system calls lecture.

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 bonus 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

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

3.2 Moving data between kernel and userland.

 vm/copyinout.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 userlevel programs, so this is a good file to read very carefully. The framework provided is needed to safely implement application buffer handling in the read() and write() system calls. You should also examine the code in lib/uio.c.

Questions

6. What is the difference between UIO_USERISPACE and UIO_USERSPACE? When should one use UIO_SYSSPACE instead?
7. 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 is the destination memory for the read)?
8. In what file are copyin() and copyout() defined? memmove()? Why can't copyin() and copyout() be implemented as simply as memmove()?

3.3 The VFS interface.

kern/include

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

Questions

9. How are vfs_open, vfs_close used? What other vfs_() calls are relevant?
10. What are VOP_READ, VOP_WRITE? How are they used?
11. What does VOP_ISSEEKABLE do?
12. Where is the struct thread defined? What does this structure contain?
13. Where is the struct proc defined? What does this structure contain?

3.4 Loading and running programs.

These questions mostly relate to the advanced assignment, but are worth exploring to understand how a program starts running.

 kern/syscall

This directory contains some syscall implementations, and the files that are responsible for the loading and running of userlevel programs. Currently, the only files in the directory are loadelf.c, runprogram.c, and time_syscalls.c, although you may want to add more of your own during this assignment. Understanding these files is the key to getting started with the assignment, especially the advanced part, the implementation of multiprogramming. Note that to answer some of the questions, you will have to look in files outside this directory.

loadelf.c

This file contains the functions responsible for loading an ELF executable from the filesystem and into virtual memory space. 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.

runprogram.c

This file contains only one function, runprogram(), which is the function that is responsible for running a program from the kernel menu. Once you have designed your file system calls, a program started by runprogram() should have the standard file descriptors (stdout, stderr) available while it's running.

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

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

fork()

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

Questions

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

3.5 The userland side of system calls.

This section is mostly related to the advanced version, but is still generally insightful to understand how system calls transition into the kernel. This was covered in some detail in the system call lecture in week 2.

userland/lib/crt0

The userland C 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 main(). This is the code that your execv() implementation will be interfacing to, so be sure to check what values it expects to appear in what registers and so forth.

userland/lib/libc:

There's obviously a lot of code in the OS/161 C library (and a lot more yet in a real system's C library...) 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 simple standard C functions on the whiteboard. For present purposes you need only look at the code that implements the user-level side of system calls.

errno.c

This is where the global variable errno is defined.

syscalls-mips.S

Questions

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

4. Basic Assignment

Setup

Remember to use a 3231 subshell (or continue using your modified PATH) for this assignment, as outlined in ASST0. Also double-check you have retained your umask from ASST1.

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

Building and Testing Your Assignment

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

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

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

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

You can test your assignment by typing p /testbin/asst2 at the OS/161 menu prompt. As a short cut, you can also specify menu arguments on the command line, example: sys161 kernel "p /testbin/asst2".
Note: If you don't have a sys161.conf file, you can use this one.

Running the program produces output similar to the following prior to starting the assignment.

Unknown syscall 55
Unknown syscall 55
Unknown syscall 55
Unknown syscall 55
     :
     :
Unknown syscall 55
Unknown syscall 55
Unknown syscall 3
Fatal user mode trap 4 sig 10 (Address error on load, epc 0x400814, vaddr 0xeeeee00f) 

 
OS/161 kernel [? for menu]: p /testbin/asst2
Operation took 0.000212160 seconds
OS/161 kernel [? for menu]:
**********
* File Tester
**********
* write() works for stdout
**********
* write() works for stderr
**********
* opening new file "test.file"
* open() got fd 3
* writing test string
* wrote 45 bytes
* writing test string again
* wrote 45 bytes
* closing file
**********
* opening old file "test.file"
* open() got fd 3
* reading entire file into buffer
* attemping read of 500 bytes
* read 90 bytes
* attemping read of 410 bytes
* read 0 bytes
* reading complete
* file content okay
**********
* testing lseek
* reading 10 bytes of file into buffer
* attemping read of 10 bytes
* read 10 bytes
* reading complete
* file lseek  okay
* closing file
Unknown syscall 3
Fatal user mode trap 4 sig 10 (Address error on load, epc 0x400814, vaddr 0xeeeee00f)

Note that the final fatal error is expected, and is due to exit() (system call 3) not being implemented by OS/161. If exit()returns to userland (which would not happen in a complete OS implementation), the userland exit library code simply accesses an illegal memory address in order to cause a fault, which subsequently causes the program (and system) to stop. You can distinguish this expected fault from other faults by the address accessed: 0xeeeee00f.

The Assignment Task: File System Calls

Of the full range of system calls that is listed in kern/include/kern/syscall.h, your task is to implement the following file-based system calls: open, read, write, lseek, close, dup2. Note: You are writing the kernel code that implements part of 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 implementation of your system calls should not assume a single process.

It's crucial that your syscalls handle all error conditions gracefully (i.e., without crashing OS/161.) You should consult the OS/161 man pages (also included in the distribution) and understand fully the system calls that you must implement. Your system calls must return the correct value (in case of success) or error code (in case of failure) as specified in the man pages. Some of the auto-marking scripts rely on the return of error codes, however, we are lenient as to which specific code in the case of potential ambiguity as to the most appropriate error code.

The file userland/include/unistd.h contains the user-level interface definition of the system calls that you will be writing for OS/161 (including ones you will implement in later assignments). This interface is different from that of the kernel functions that you will define to implement these calls. You need to design this interface and put it in kern/include/syscall.h. As you discovered (ideally) in Assignment 0, the integer codes for the calls are defined in kern/include/kern/syscall.h. You need to think about a variety of issues associated with implementing system calls. Perhaps, the most obvious one is: can two different user-level processes (or user-level threads, if you choose to implement them) find themselves running a system call at the same time?

Notes on open(), read(), write(), lseek(), close(), and dup2()

For any given process, the first file descriptors (0, 1, and 2) are considered to be standard input (stdin), standard output (stdout), and standard error (stderr) respectively. For this basic assignment, the file descriptors 1 (stdout) and 2 (stderr) must start out attached to the console device ("con:"), 0 (stdin) can be left unattached. You will probably modify runprogram() to achieve this. Your implementation must allow programs to use dup2() to change stdin, stdout, stderr to point elsewhere.

Although these system calls may seem to be tied to the filesystem, in fact, these system calls are really about manipulation of file descriptors, or process-specific filesystem state. A large part of this assignment is designing and implementing a system to track this state. Some of this information (such as the cwd) is specific only to the process, but others (such as offset) is specific to the process and file descriptor. Don't rush this design. Think carefully about the state you need to maintain, how to organise it, and when and how it has to change.

While this assignment requires you to implement file-system-related system calls, you actually have to write virtually no low-level file system code in this assignment. You will use the existing VFS layer to do most of the work. Your job is to construct the subsystem that implements the interface expected by userland programs by invoking the appropriate VFS and vnode operations.

While you are not restricted to only modifying these files, please place most of your implementation in the following files: function prototypes and data types for your file subsystem in kern/include/file.h, and the function implementations and variable instantiations in kern/syscall/file.c.

A note on errors and error handling of system calls

Design Questions

• Section 10.6.3 and "NFS implementation" in Section 10.6.4, Tannenbaum, Modern Operating Systems .
• Section 6.4 and Section 6.5, McKusick et al., The Design and Implementation of the 4.4 BSD Operating System.
• Chapter 8, Vahalia, Unix Internals: the new frontiers.
• The original VFS paper is available here.

Documenting your solution

The document will be used to guide our markers in their evaluation of your solution to the assignment. In the case of a poor results in the functional testing combined with a poor design document, we will base our assessment on these components alone. If you can't describe your own solution clearly, you can't expect us to reverse engineer the code to a poor and complex solution to the assignment.

Place your design document in design.txt (which we have created for you) at the top of the source tree to OS/161 (i.e. in ~/cs3231/asst2-src/design.txt).

When you later commit your changes into your repository, your design doc will be included in the commit, and later in your submission.

Also, please word wrap you design doc if your have not already done so. You can use the unix fmt command to achieve this if your editor cannot.

5. Basic Assignment Submission

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

% svn add filename.c

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

Submitting Your Assignment

% cd ~
% give cs3231 asst2 asst2.diff

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.

We strongly suggest keeping your svn repository intact to allow for recovery of your work if need be.

6. Advanced Assignment

• fork(), getpid()5 marks.
• waitpid(), _exit(), kill_curthread() 2 bonus marks.
• exec() optional for 1 bonus mark.

The advanced assignment is to complete the basic assignment, plus the additional task below. 

Given you're doing the advanced version of the assignment, I'm assuming you're competent with managing your SVN repository and don't need simple directions. You basically need to generate a diff between your final version and the base. There are two ways you can do this: the simpler (but messier) option is to continue developing along your mainline branch and generate the diff in the same way as for the basic assignment. A neater approach is to create a new branch in SVN to work on your advanced solution. Whichever approach you take, make sure you test your diff before you submit it!

User-level Process Management System Calls

Design Questions

  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);

Advanced Assignment Submission

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

% 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

FAQ and Gotchas

See https://wiki.cse.unsw.edu.au/cs3231cgi/2017s1/Asst2 for an up to date list of potential issues you might encounter.