Project 2: User Programs
************************

Now that you've worked with Pintos and are familiar with its infrastructure and thread package, it's time to start working on the parts of the system that will allow users to run programs on top of your operating system.  The base code already supports loading and running a single user program at a time with little interactivity possible.  You will allow multiple programs to be loaded in at once, and to interact with the OS via system calls.

You will be working out of the userprog directory for this assignment.  However, you will also be interacting with almost every other part of the code for this assignment. We will describe the relevant parts below. If you are confident in your HW1 code, you can build on top of it.  However, if you wish you can start with a fresh copy of the code and re-implement thread_join, which is the only part of project #1 required for this assignment.  Your submission should define THREAD_JOIN_IMPLEMENTED in constants.h (see Conditional Compilation).

Up to now, all of the code you have written for Pintos has been part of the operating system kernel.  This means, for example, that all the test code from the last assignment ran as part of the kernel, with full access to privileged parts of the system.  Once we start running user programs on top of the operating system, this is no longer true. This project deals with consequences of the change.

We allow more than one user program to run at a time.  Because user programs are written and compiled to work under the illusion that they have the entire machine, when you load into memory and run more than one process at a time, you must manage things correctly to maintain this illusion.

Before we delve into the details of the new code that you'll be working with, you should probably undo the test cases from project 1.

Code
====

The easiest way to get an overview of the programming you will be doing is to simply go over each part you'll be working with.  In userprog, you'll find a small number of files, but here is where the bulk of your work will be:

process.c
process.h
     Loads ELF binaries and starts processes.

pagedir.c
pagedir.h
     A simple manager for 80X page directories and page tables. Although you probably won't want to modify this code for this project, you may want to call some of its functions.  In particular, pagedir_get_page may be helpful for accessing user memory.

syscall.c
syscall.h
     Whenever a user process wants to access some kernel functionality, it needs to do so via a system call.  This is a skeleton system call handler.  Currently, it just prints a message and terminates the user process.  In part 2 of this project you will add code to do everything else needed by system calls.

exception.c
exception.h
     When a user process performs a privileged or prohibited operation, it traps into the kernel as an ``exception'' or ``fault.'' (We will treat these terms as synonymous.  There is no standard distinction between them, although the Intel processor manuals define them slightly differently on 80X86.)  These files handle exceptions.  Currently all exceptions simply print a message and terminate the process.  Some, but not all, solutions to project 2 require modifying page_fault in this file.

gdt.c
gdt.c
     The 80X86 is a segmented architecture.  The Global Descriptor Table (GDT) is a table that describes the segments in use.  These files set up the GDT.  You should not need to modify these files for any of the projects.  However, you can read the code if you're interested in how the GDT works.

tss.c
tss.c
     The Task-State Segment (TSS) is used for 80X86 architectural task switching.  Pintos uses the TSS only for switching stacks when a user process enters an interrupt handler, as does Linux.  You should not need to modify these files for any of the projects. However, you can read the code if you're interested in how the TSS works.

Finally, in lib/kernel, you might want to use bitmap.[ch].  A bitmap is basically an array of bits, each of which can be true or false.  Bitmaps are typically used to keep track of the usage of a large array of (identical) resources: if resource N is in use, then bit N of the bitmap is true.  You might find it useful for tracking memory pages, for example.

Using the File System
=====================

You will need to use some file system code for this project.  First, user programs are loaded from the file system.  Second, many of the system calls you must implement deal with the file system.  However, the focus of this project is not on the file system code, so we have provided a simple file system in the filesys directory.  You will want to look over the filesys.h and file.h interfaces to understand how to use the file system, and especially its many limitations.  You should not modify the file system code for this project.  Proper use of the file system routines now will make life much easier for project 4, when you improve the file system implementation.  Until then, you will have to put up with the following limitations:

  * No synchronization.  Concurrent accesses will interfere with one another, so external synchronization is needed.  See Synchronizing File Access, for more details.

  * File size is fixed at creation time.  Because the root directory is represented as a file, the number of files that may be created is also limited.

  * File data is allocated as a single extent, that is, data in a single file must occupy a contiguous range of sectors on disk.  External fragmentation can therefore become a serious problem as a file system is used over time.

  * No subdirectories.

  * File names are limited to 14 characters.

  * A system crash mid-operation may corrupt the disk in a way that cannot be repaired automatically.  No `fsck' tool is provided in any case.

However one important feature is included:

  * Unix-like semantics for filesys_remove() are implemented. That is, if a file is open when it is removed, its blocks are not deallocated and it may still be accessed by the threads that have it open until the last one closes it.  See Removing an Open File, for more information.

You need to be able to create and format simulated disks.  The pintos program provides this functionality with its make-disk command.  From the userprog/build directory, execute pintos make-disk fs.dsk 2.  This command creates a 2 MB simulated disk named fs.dsk.  (It does not actually start Pintos.)  Then format the disk by passing the -f option to Pintos on the kernel's command line: pintos run -f.

You'll need a way to get files in and out of the simulated file system.  The pintos put and get commands are designed for this.  To copy FILE into the Pintos file system, use the command pintos put FILE.  To copy it to the Pintos file system under the name NEWNAME, add the new name to the end of the command: pintos put FILE NEWNAME.  The commands for copying files out of a VM are similar, but substitute get for get.

Incidentally, these commands work by passing special options -ci and -co on the kernel's command line and copying to and from a special simulated disk named scratch.dsk.  If you're very curious, you can look at the pintos program as well as filesys/fsutil.c to learn the implementation details, but it's really not relevant for this project.

Here's a summary of how you would create and format a disk, copy the echo program into the new disk, and then run echo. It assumes that you've already built the tests in tests/userprog and that the current directory is userprog/build:

     pintos make-disk fs.dsk 2
     pintos run -f
     pintos put ../../tests/userprog/echo echo
     pintos run -ex echo

You can delete a file from the Pintos file system using the -r FILE kernel option, e.g. pintos run -r FILE. Also, -ls lists the files in the file system and -p FILE prints a file's contents to the display.

How User Programs Work
======================

Pintos can run normal C programs.  In fact, it can run any program you want, provided it's compiled into the proper file format, and uses only the system calls you implement.  (For example, malloc makes use of functionality that isn't provided by any of the syscalls we require you to support.)  The only other limitation is that Pintos can't run programs using floating point operations, since it doesn't include the necessary kernel functionality to save and restore the processor's floating-point unit when switching threads.  You can look in tests/userprog directory for some examples.

Pintos loads ELF executables, where ELF is an executable format used by Linux, Solaris, and many other Unix and Unix-like systems. Therefore, you can use any compiler and linker that produce 80X86 ELF executables to produce programs for Pintos.  We recommend using the tools we provide in the tests/userprog directory.  By default, the Makefile in this directory will compile the test programs we provide.  You can edit the Makefile to compile your own test programs as well.

One thing you should realize immediately is that, until you copy a test program to the emulated disk, Pintos will be unable to do very much useful work.  You will also find that you won't be able to do interesting things until you copy a variety of programs to the disk. A useful technique is to create a clean reference disk and copy that over whenever you trash your fs.dsk beyond a useful state, which may happen occasionally while debugging.

Virtual Memory Layout
=====================

Virtual memory in Pintos is divided into two regions: user virtual memory and kernel virtual memory.  User virtual memory ranges from virtual address 0 up to PHYS_BASE, which is defined in threads/mmu.h and defaults to 0xc0000000 (3 GB).  Kernel virtual memory occupies the rest of the virtual address space, from PHYS_BASE up to 4 GB.

User virtual memory is per-process.  Conceptually, each process is free to use the entire space of user virtual memory however it chooses.  When the kernel switches from one process to another, it also switches user virtual address spaces by switching the processor's page directory base register (see pagedir_activate in userprog/pagedir.c.  thread contains a pointer to a process's page directory.

Kernel virtual memory is global.  It is always mapped the same way, regardless of what user process or kernel thread is running.  In Pintos, kernel virtual memory is mapped one-to-one to physical memory.  That is, virtual address PHYS_ADDR accesses physical address 0, virtual address PHYS_ADDR + 0x1234 access physical address 0x1234, and so on up to the size of the machine's physical memory.

User programs can only access user virtual memory.  An attempt to access kernel virtual memory will cause a page fault, handled by page_fault in userprog/exception.c, and the process will be terminated.  Kernel threads can access both kernel virtual memory and, if a user process is running, the user virtual memory of the running process.  However, even in the kernel, an attempt to access memory at a user virtual address that doesn't have a page mapped into it will cause a page fault.

You must handle memory fragmentation gracefully, that is, a process that needs N pages of memory must not require that all N be contiguous.  In fact, it must not require that any of the pages be contiguous.

Global Requirements
===================

For testing and grading purposes, we have some simple overall requirements:

  * The kernel should print out the program's name and exit status whenever a process terminates, whether termination is caused by the exit system call or for another reason.

       - The message must be formatted exactly as if it was printed with printf ("%s: exit(%d)\n", ...); given appropriate arguments.

       - The name printed should be the full name passed to process_execute, except that it is acceptable to truncate it to 15 characters to allow for the limited space in thread.  The name printed need not include arguments.

       - Do not print a message when a kernel thread that is not a process terminates.

       - Do not print messages about process termination for the halt system call.

       - No message need be printed when a process fails to load.

  * Aside from this, the kernel should print out no other messages that Pintos as provided doesn't already print.  You may understand all those debug messages, but we won't, and it just clutters our ability to see the stuff we care about.

  * Additionally, while it may be useful to hard-code which process will run at startup while debugging, before you submit your code you must make sure that it takes the start-up process name and arguments from the -ex argument.  For example, running pintos run -ex "testprogram 1 2 3 4" will spawn testprogram 1 2 3 4 as the first process.

Problem 2-1: Argument Passing
=============================

Currently, process_execute does not support passing arguments to new processes.  UNIX and other operating systems do allow passing command line arguments to a program, which accesses them via the argc, argv arguments to main.  You must implement this functionality by extending process_execute so that instead of simply taking a program file name as its argument, it divides it into words at spaces. The first word is the program name, the second word is the first argument, and so on.  That is, process_execute("grep foo bar") should run grep passing two arguments foo and bar.  A few details:

  * Multiple spaces are considered the same as a single space, so that process_execute("grep foo bar") would be equivalent to our original example.

  * You can impose a reasonable limit on the length of the command line arguments.  For example, you could limit the arguments to those that will fit in a single page (4 kB).

  * You can parse the argument strings any way you like.  If you're lost, look at strtok_r, prototyped in lib/string.h and implemented with thorough comments in lib/string.c.  You can find more about it by looking at the man page (run man strtok_r at the prompt).

  * See 80x86 Calling Convention, for information on exactly how you need to set up the stack.

This functionality is extremely important.  Almost all our test cases rely on being able to pass arguments, so if you don't get this right, a lot of things will not appear to work correctly with our tests.  If the tests fail, so do you.  Fortunately, this part shouldn't be too hard.

Problem 2-2: System Calls
=========================

Implement the system call handler in userprog/syscall.c to properly deal with all the system calls described below.  Currently, it ``handles'' system calls by terminating the process.  You will need to decipher system call arguments and take the appropriate action for each.

You are required to support the following system calls, whose syscall numbers are defined in lib/syscall-nr.h and whose C functions called by user programs are prototyped in lib/user/syscall.h:

SYS_halt
void halt (void)
     Stops Pintos by calling power_off (declared in threads/init.h).  Note that this should be seldom used, since then you lose some information about possible deadlock situations, etc.

SYS_exit
void exit (int STATUS)
     Terminates the current user program, returning STATUS to the kernel.  If the process's parent joins it, this is the status that will be returned.  Conventionally, a STATUS of 0 indicates a successful exit.  Other values may be used to indicate user-defined conditions (usually errors).

SYS_exec
pid_t exec (const char *CMD_LINE)
     Runs the executable whose name is given in CMD_LINE, passing any given arguments, and returns the new process's program id (pid).  If there is an error loading this program, may return pid -1, which otherwise should not be a valid id number.

SYS_join
int join (pid_t PID)
     Joins the process PID, using the join rules from the last assignment, and returns the process's exit status.  If the process was terminated by the kernel (i.e. killed due to an exception), the exit status should be -1.  If the process was not a child of the calling process, the return value is undefined (but kernel operation must not be disrupted).

SYS_create
bool create (const char *FILE, unsigned INITIAL_SIZE)
     Create a new file called FILE initially INITIAL_SIZE bytes in size.  Returns true if successful, false otherwise.

SYS_remove
bool remove (const char *FILE)
     Delete the file called FILE.  Returns true if successful, false otherwise.

SYS_open
int open (const char *FILE)
     Open the file called FILE.  Returns a nonnegative integer handle called a ``file descriptor'' (fd), or -1 if the file could not be opened.  All open files associated with a process should be closed when the process exits or is terminated.

     File descriptors numbered 0 and 1 are reserved for the console: fd 0 is standard input (stdin), fd 1 is standard output (stdout).  These special file descriptors are valid as system call arguments only as explicitly described below.

SYS_filesize
int filesize (int FD)
     Returns the size, in bytes, of the file open as FD.

SYS_read
int read (int FD, void *BUFFER, unsigned SIZE)
     Read SIZE bytes from the file open as FD into BUFFER.  Returns the number of bytes actually read (0 at end of file), or -1 if the file could not be read (due to a condition other than end of file).  Fd 0 reads from the keyboard using kbd_getc.

SYS_write
int write (int FD, const void *BUFFER, unsigned SIZE)
     Write SIZE bytes from BUFFER to the open file FD. Returns the number of bytes actually written, or -1 if the file could not be written.

     Fd 1 writes to the console.  Your code to write to the console should write all of BUFFER in one call to putbuf, at least as long as SIZE is not bigger than a few hundred bytes.  Otherwise, lines of text output by different processes may end up interleaved on the console, confusing both human readers and our grading scripts.

SYS_seek
void seek (int FD, unsigned POSITION)
     Changes the next byte to be read or written in open file FD to POSITION, expressed in bytes from the beginning of the file. (Thus, a POSITION of 0 is the file's start.)

     A seek past the current end of a file is not an error.  A later read obtains 0 bytes, indicating end of file.  A later write extends the file, filling any unwritten gap with zeros.  (However, in Pintos files have a fixed length until project 4 is complete, so writes past end of file will return an error.)  These semantics are implemented in the file system and do not require any special effort in system call implementation.

SYS_tell
unsigned tell (int FD)
     Returns the position of the next byte to be read or written in open file FD, expressed in bytes from the beginning of the file.

SYS_close
void close (int FD)
     Close file descriptor FD.

The file defines other syscalls.  Ignore them for now.  You will implement some of them in project 3 and the rest in project 4, so be sure to design your system with extensibility in mind.

To implement syscalls, you will need to provide a way of copying data from the user's virtual address space into the kernel and vice versa. This can be a bit tricky: what if the user provides an invalid pointer, a pointer into kernel memory, or points to a block that is partially in one of those regions?  You should handle these cases by terminating the user process.  You will need this code before you can even obtain the system call number, because the system call number is on the user's stack in the user's virtual address space.  We recommend writing and testing this code before implementing any other system call functionality.

You must make sure that system calls are properly synchronized so that any number of user processes can make them at once.  In particular, it is not safe to call into the filesystem code provided in the filesys directory from multiple threads at once.  For now, we recommend adding a single lock that controls access to the filesystem code.  You should acquire this lock before calling any functions in the filesys directory, and release it afterward.  Don't forget that process_execute also accesses files.  For now, we recommend against modifying code in the filesys directory.

We have provided you a user-level function for each system call in lib/user/syscall.c.  These provide a way for user processes to invoke each system call from a C program.  Each of them calls an assembly language routine in lib/user/syscall-stub.S, which in turn invokes the system call interrupt and returns.

When you're done with this part, and forevermore, Pintos should be bulletproof.  Nothing that a user program can do should ever cause the OS to crash, halt, assert fail, or otherwise stop running.  It is important to emphasize this point: our tests will try to break your system calls in many, many ways.  You need to think of all the corner cases and handle them.  The sole way a user program should be able to cause the OS to halt is by invoking the halt system call.

If a system call is passed an invalid argument, acceptable options include returning an error value (for those calls that return a value), returning an undefined value, or terminating the process.

See System Calls, for more information on how syscalls work.

FAQ
===

 1. Do we need a working project 1 to implement project 2?

     You may find the code for thread_join to be useful in implementing the join syscall, but besides that, you can use the original code provided for project 1.

 2. pintos put always panics.

     Here are the most common causes:

       * The disk hasn't yet been formatted (with pintos run -f).

       * The file name specified is too long.  The file system limits file names to 14 characters.  If you're using a command like pintos put ../../tests/userprog/echo, that overflows the limit.  Use pintos put ../../tests/userprog/echo echo to put the file under the name echo instead.

       * The file system is full.

       * The file system already contains 10 files.  (There's a 10-file limit for the base Pintos file system.)

       * The file system is so fragmented that there's not enough contiguous space for your file.

 3. All my user programs die with page faults.

     This will generally happen if you haven't implemented problem 2-1 yet.  The reason is that the basic C library for user programs tries to read ARGC and ARGV off the stack.  Because the stack isn't properly set up yet, this causes a page fault.

 4. I implemented 2-1 and now all my user programs die with system call!.

     Every reasonable program tries to make at least one system call (exit) and most programs make more than that.  Notably, printf invokes the write system call.  The default system call handler just prints system call! and terminates the program.  You'll have to implement 2-2 before you see anything more interesting.  Until then, you can use hex_dump to convince yourself that 2-1 is implemented correctly (see Argument Passing to main).

 5. Is there a way I can disassemble user programs?

     The i386-elf-objdump utility can disassemble entire user programs or object files.  Invoke it as i386-elf-objdump -d FILE.  You can also use i386-elf-gdb's disassemble command to disassemble individual functions in object files compiled with debug information.

 6. Why can't I use many C include files in my Pintos programs?

     The C library we provide is very limited.  It does not include many of the features that are expected of a real operating system's C library. The C library must be built specifically for the operating system (and architecture), since it must make system calls for I/O and memory allocation.  (Not all functions do, of course, but usually the library is compiled as a unit.)

 7. Can I use libFOO in my Pintos programs?

     The chances are good that libFOO uses parts of the C library that Pintos doesn't implement.  It will probably take at least some porting effort to make it work under Pintos.  Notably, the Pintos userland C library does not have a malloc implementation.

 8. How do I compile new user programs?

     You need to modify tests/Makefile.

 9. What's the difference between tid_t and pid_t?

     A tid_t identifies a kernel thread, which may have a user process running in it (if created with process_execute) or not (if created with thread_create).  It is a data type used only in the kernel.

     A pid_t identifies a user process.  It is used by user processes and the kernel in the exec and join system calls.

     You can choose whatever suitable types you like for tid_t and pid_t.  By default, they're both int.  You can make them a one-to-one mapping, so that the same values in both identify the same process, or you can use a more complex mapping.  It's up to you.

 10. I can't seem to figure out how to read from and write to user memory. What should I do?

     The kernel must treat user memory delicately.  As part of a system call, the user can pass to the kernel a null pointer, a pointer to unmapped virtual memory, or a pointer to kernel virtual address space (above PHYS_BASE).  All of these types of invalid pointers must be rejected without harm to the kernel or other running processes.  At your option, the kernel may handle invalid pointers by terminating the process or returning from the system call with an error.

     There are at least two reasonable ways to do this correctly.  The first method is to ``verify then access'': (These terms are made up for this document.  They are not standard terminology.) verify the validity of a user-provided pointer, then dereference it.  If you choose this route, you'll want to look at the functions in userprog/pagedir.c and in threads/mmu.h.  This is the simplest way to handle user memory access.

     The second method is to ``assume and react'': directly dereference user pointers, after checking that they point below PHYS_BASE. Invalid user pointers will then cause a ``page fault'' that you can handle by modifying the code for page_fault in userprog/exception.cc.  This technique is normally faster because it takes advantage of the processor's MMU, so it tends to be used in real kernels (including Linux).

     In either case, you need to make sure not to ``leak'' resources.  For example, suppose that your system call has acquired a lock or allocated a page of memory.  If you encounter an invalid user pointer afterward, you must still be sure to release the lock or free the page of memory.  If you choose to ``verify then access,'' then this should be straightforward, but for ``assume and react'' it's more difficult, because there's no way to return an error code from a memory access. Therefore, for those who want to try the latter technique, we'll provide a little bit of helpful code:

     /* Tries to copy a byte from user address USRC to kernel address DST.
        Returns true if successful, false if USRC is invalid. */
     static inline bool get_user (uint8_t *dst, const uint8_t *usrc) {
       int eax;
       asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
            : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
       return eax != 0;
     }

     /* Tries write BYTE to user address UDST.
        Returns true if successful, false if UDST is invalid. */
     static inline bool put_user (uint8_t *udst, uint8_t byte) {
       int eax;
       asm ("movl $1f, %%eax; movb %b2, %0; 1:"
            : "=m" (*udst), "=&a" (eax) : "r" (byte));
       return eax != 0;
     }

     Each of these functions assumes that the user address has already been verified to be below PHYS_BASE.  They also assume that you've modified page_fault so that a page fault in the kernel causes eax to be set to 0 and its former value copied into eip.

 11. I'm also confused about reading from and writing to the stack. Can you help?

       * Only non-char values will have issues when writing them to memory.  If a digit is in a string, it is considered a character. However, the value of argc would be a non-char.

       * You will need to write characters and non-characters into main memory.

       * When you add items to the stack, you will be decrementing the stack pointer.  You'll need to decrement the stack pointer before writing to the location.

       * Each character is 1 byte.

 12. Why doesn't keyboard input work with pintos -v?

     Serial input isn't implemented.  Don't use pintos -v if you want to use the shell or otherwise provide keyboard input.

Problem 2-1: Argument Passing FAQ
---------------------------------

 1. Why is the top of the stack at 0xc0000000?  Isn't that off the top of user virtual memory?  Shouldn't it be 0xbfffffff?

     When the processor pushes data on the stack, it decrements the stack pointer first.  Thus, the first (4-byte) value pushed on the stack will be at address 0xbffffffc.

     Also, the stack should always be aligned to a 4-byte boundary, but 0xbfffffff isn't.

 2. Is PHYS_BASE fixed?

     No.  You should be able to support PHYS_BASE values that are any multiple of 0x10000000 from 0x80000000 to 0xc0000000, simply via recompilation.

Problem 2-2: System Calls FAQ
-----------------------------

 1. Can I just cast a pointer to a file object to get a unique file descriptor?  Can I just cast a struct thread * to a pid_t?  It's so much simpler that way!

     This is a design decision you will have to make for yourself. However, note that most operating systems do distinguish between file descriptors (or pids) and the addresses of their kernel data structures.  You might want to give some thought as to why they do so before committing yourself.

 2. Can I set a maximum number of open files per process?

     From a design standpoint, it would be better not to set an arbitrary maximum.  That said, if your design calls for it, you may impose a limit of 128 open files per process (as the Solaris machines here do).

 3. What happens when two (or more) processes have a file open and one of them removes it?

     You should copy the standard Unix semantics for files.  That is, when a file is removed an process which has a file descriptor for that file may continue to do operations on that descriptor.  This means that they can read and write from the file.  The file will not have a name, and no other processes will be able to open it, but it will continue to exist until all file descriptors referring to the file are closed or the machine shuts down.

 4. I've discovered that some of my user programs need more than one 4 kB page of stack space.  What should I do?

     You may modify the stack setup code to allocate more than one page of stack space for each process.

80X86 Calling Convention
========================

What follows is a quick and dirty discussion of the 80X86 calling convention.  Some of the basics should be familiar from CS 107, and if you've already taken CS 143 or EE 182, then you should have seen even more of it.  I've omitted some of the complexity, since this isn't a class in how function calls work, so don't expect this to be exactly correct in full, gory detail.  If you do want all the details, you can refer to SysV-i386.

Whenever a function call happens, you need to put the arguments on the call stack for that function, before the code for that function executes, so that the callee has access to those values.  The caller has to be responsible for this (be sure you understand why). Therefore, when you compile a program, the assembly code emitted will have in it, before every function call, a bunch of instructions that prepares for the call in whatever manner is conventional for the machine you're working on.  This includes saving registers as needed, putting stuff on the stack, saving the location to return to somewhere (so that when the callee finishes, it knows where the caller code is), and some other bookkeeping stuff.  Then you do the jump to the callee's code, and it goes along, assuming that the stack and registers are prepared in the appropriate manner.  When the callee is done, it looks at the return location as saved earlier, and jumps back to that location.  The caller may then have to do some cleanup: clearing arguments and the return value off the stack, restoring registers that were saved before the call, and so on.

If you think about it, some of these things should remind you of context switching.

As an aside, in general, function calls are not cheap.  You have to do a bunch of memory writes to prepare the stack, you need to save and restore registers before and after a function call, you need to write the stack pointer, you have a couple of jumps which probably wrecks some of your caches.  This is why inlining code can be much faster.

Argument Passing to main()
--------------------------

In main's case, there is no caller to prepare the stack before it runs.  Therefore, the kernel needs to do it.  Fortunately, since there's no caller, there are no registers to save, no return address to deal with, etc.  The only difficult detail to take care of, after loading the code, is putting the arguments to main on the stack.

(The above is a small lie: most compilers will emit code where main isn't strictly speaking the first function.  This isn't an important detail.  If you want to look into it more, try disassembling a program and looking around a bit.  However, you can just act as if main is the very first function called.)

Pintos is written for the 80X86 architecture.  Therefore, we need to adhere to the 80X86 calling convention.  Basically, you put all the arguments on the stack and move the stack pointer appropriately.  You also need to insert space for the function's ``return address'': even though the initial function doesn't really have a caller, its stack frame must have the same layout as any other function's.  The program will assume that the stack has been laid out this way when it begins running.

So, what are the arguments to main? Just two: an int (argc) and a char ** (argv).  argv is an array of strings, and argc is the number of strings in that array.  However, the hard part isn't these two things.  The hard part is getting all the individual strings in the right place.  As we go through the procedure, let us consider the following example command: /bin/ls -l foo bar.

The first thing to do is to break the command line into individual strings: /bin/ls, -l, foo, and bar.  These constitute the arguments of the command, including the program name itself (which belongs in argv[0]).

These individual, null-terminated strings should be placed on the user stack.  They may be placed in any order, as you'll see shortly, without affecting how main works, but for simplicity let's assume they are in reverse order (keeping in mind that the stack grows downward on an 80X86 machine).  As we copy the strings onto the stack, we record their (virtual) stack addresses.  These addresses will become important when we write the argument vector (two paragraphs down).

After we push all of the strings onto the stack, we adjust the stack pointer so that it is word-aligned: that is, we move it down to the next 4-byte boundary.  This is required because we will next be placing several words of data on the stack, and they must be aligned to be read correctly.  In our example, as you'll see below, the strings start at address 0xffed.  One word below that would be at 0xffe9, so we could in theory put the next word on the stack there.  However, since the stack pointer should always be word-aligned, we instead leave the stack pointer at 0xffe8.

Once we align the stack pointer, we then push the elements of the argument vector, that is, a null pointer, then the addresses of the strings /bin/ls, -l, foo, and bar) onto the stack.  This must be done in reverse order, such that argv[0] is at the lowest virtual address, again because the stack is growing downward.  (The null pointer pushed first is because argv[argc] must be a null pointer.)  This is because we are now writing the actual array of strings; if we write them in the wrong order, then the strings will be in the wrong order in the array.  This is also why, strictly speaking, it doesn't matter what order the strings themselves are placed on the stack: as long as the pointers are in the right order, the strings themselves can really be anywhere. After we finish, we note the stack address of the first element of the argument vector, which is argv itself.

Then we push argv (that is, the address of the first element of the argv array) onto the stack, along with the length of the argument vector (argc, 4 in this example).  This must also be done in this order, since argc is the first argument to main and therefore is on first (smaller address) on the stack.  Finally, we push a fake ``return address'' and leave the stack pointer to point to its location.

All this may sound very confusing, so here's a picture which will hopefully clarify what's going on. This represents the state of the stack and the relevant registers right before the beginning of the user program (assuming for this example that the stack bottom is 0xc0000000):

Address   Name   Data
0xbffffffc   *argv[3]   bar\0
0xbffffff8   *argv[2]   foo\0
0xbffffff5   *argv[1]   -l\0
0xbfffffed   *argv[0]   /bin/ls\0
0xbfffffec   word-align   \0
0xbfffffe8   argv[4]   0
0xbfffffe4   argv[3]   0xbffffffc
0xbfffffe0   argv[2]   0xbffffff8
0xbfffffdc   argv[1]   0xbffffff5
0xbfffffd8   argv[0]   0xbfffffed
0xbfffffd4   argv   0xbfffffd8
0xbfffffd0   argc   4
0xbfffffcc   ``return address''   0

In this example, the stack pointer would be initialized to 0xbfffffcc.

As shown above, your code should start the stack at the very top of the user virtual address space, in the page just below virtual address PHYS_BASE (defined in threads/mmu.h).

You may find the non-standard hex_dump function, declared in <stdio.h>, useful for debugging your argument passing code. Here's what it would show in the above example, given that PHYS_BASE is 0xc0000000:

bfffffc0                                      00 00 00 00 |            ....|
bfffffd0  04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
bfffffe0  f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
bffffff0  6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|

System Calls
============

We have already been dealing with one way that the operating system can regain control from a user program: interrupts from timers and I/O devices.  These are ``external'' interrupts, because they are caused by entities outside the CPU.

The operating system is also called to deal with software exceptions, which are events generated in response to the code.  These can be errors such as a page fault or division by zero.  However, exceptions are also the means by which a user program can request services (``system calls'') from the operating system.

In the 80X86 architecture, the int instruction is the most commonly used means for invoking system calls.  This instruction is handled in the same way as other software exceptions.  In Pintos, user programs invoke int $0x30 to make a system call.  The system call number and any additional arguments are expected to be pushed on the stack in the normal fashion before invoking the interrupt.

The normal calling convention pushes function arguments on the stack from right to left and the stack grows downward.  Thus, when the system call handler syscall_handler gets control, the system call number is in the 32-bit word at the caller's stack pointer, the first argument is in the 32-bit word at the next higher address, and so on.  The caller's stack pointer is accessible to syscall_handler as the esp member of the struct intr_frame passed to it.

Here's an example stack frame for calling a system call numbered 10 with three arguments passed as 1, 2, and 3.  The stack addresses are arbitrary:

Address   Value
0xbffffe7c   3
0xbffffe78   2
0xbffffe74   1
0xbffffe70   10

In this example, the caller's stack pointer would be at 0xbffffe70.

The 80X86 convention for function return values is to place them in the EAX register.  System calls that return a value can do so by modifying the eax member of intr_frame.

You should try to avoid writing large amounts of repetitive code for implementing system calls.  Each system call argument, whether an integer or a pointer, takes up 4 bytes on the stack.  You should be able to take advantage of this to avoid writing much near-identical code for retrieving each system call's arguments from the stack.