pintos_22/doc/userprog.texi

@node Task 2--User Programs
@chapter Task 2: User Programs

Now that you've worked with PintOS and are becoming familiar with its
infrastructure and thread package, it's time to start working on the
parts of the system that allow running user programs.
The base code already supports loading and
running user programs, but no I/O or interactivity
is possible.  In this task, you will enable programs to interact with
the OS via system calls.

You will be working out of the @file{userprog} directory for this
assignment, but you will also be interacting with almost every
other part of PintOS.  We will describe the
relevant parts below.

You can build task 2 on top of your task 1 submission or you can
start fresh.  No code from task 1 is required for this
assignment.  The ``alarm clock'' functionality from task 0 may be useful in
task 3, but it is not strictly required.

You might find it useful to go back and reread how to run the tests
(@pxref{Testing}).

@menu
* Task 2 Background::        
* Task 2 Suggested Order of Implementation::  
* Task 2 Requirements::      
* Task 2 FAQ::               
* 80x86 Calling Convention::    
@end menu

@node Task 2 Background
@section Background

Up to now, all of the code you have run under 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 task deals with the consequences.

We allow more than one process to run at a time.  Each process has one
thread (multithreaded processes are not supported).  User programs are
written under the illusion that they have the entire machine.  This
means that when you load and run multiple processes at a time, you must
manage memory, scheduling, and other state correctly to maintain this
illusion.

In the previous task, we compiled our test code directly into your
kernel, so we had to require certain specific function interfaces within
the kernel.  From now on, we will test your operating system by running
user programs.  This gives you much greater freedom.  You must make sure
that the user program interface meets the specifications described here,
but given that constraint you are free to restructure or rewrite kernel
code however you wish.

@menu
* Task 2 Source Files::      
* Using the File System::       
* How User Programs Work::      
* Virtual Memory Layout::       
* Accessing User Memory::       
@end menu

@node Task 2 Source Files
@subsection Source Files

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
@file{userprog}, you'll find a small number of files, but here is
where the bulk of your work will be:

@table @file
@item process.c
@itemx process.h
Loads ELF binaries and starts processes.

@item pagedir.c
@itemx pagedir.h
A simple manager for 80@var{x}86 hardware page tables.
Although you probably won't want to modify this code for this task,
you may want to call some of its functions.
@xref{Page Tables}, for more information.

@item syscall.c
@itemx syscall.h
Whenever a user process wants to access some kernel functionality, it
invokes 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 task you will add code to do everything
else needed by system calls.

@item exception.c
@itemx exception.h
When a user process performs a privileged or prohibited operation, it
traps into the kernel as an ``exception'' or ``fault.''@footnote{We
will treat these terms as synonyms.  There is no standard
distinction between them, although Intel processor manuals make 
a minor distinction between them on 80@var{x}86.}  These files handle
exceptions.  Currently all exceptions simply print a message and
terminate the process.  Some, but not all, solutions to task 2
require modifying @func{page_fault} in this file.

@item gdt.c
@itemx gdt.h
The 80@var{x}86 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 tasks.  You can read the code if
you're interested in how the GDT works.

@item tss.c
@itemx tss.h
The Task-State Segment (TSS) is used for 80@var{x}86 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 tasks.
You can read the code if you're interested in how the TSS
works.
@end table

@node Using the File System
@subsection Using the File System

You will need to interface to the file system code for this task,
because
user programs are loaded from the file system and many of the
system calls you must implement deal with the file system.  However,
the focus of this task is not the file system, so we have
provided a simple but complete file system in the @file{filesys}
directory.  You
will want to look over the @file{filesys.h} and @file{file.h}
interfaces to understand how to use the file system, and especially
its many limitations.

There is no need to modify the file system code for this task, and so
we recommend that you do not.  Working on the file system is likely to
distract you from this task's focus.

You will have to tolerate the following limitations of the provided
filesystem implementation:

@itemize @bullet
@item
No internal synchronization.  Concurrent accesses will interfere with one
another.  You should use synchronization to ensure that only one process at a
time is executing file system code. No finer-grained synchronisation 
(for eg. per-file locking) is expected.

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

@item
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.

@item
No subdirectories.

@item
File names are limited to 14 characters.

@item
A system crash mid-operation may corrupt the disk in a way
that cannot be repaired automatically.  There is no file system repair
tool anyway.
@end itemize

One important feature is included:

@itemize @bullet
@item
Unix-like semantics for @func{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 any
threads that have it open, until the last one closes it.  @xref{Removing
an Open File}, for more information.
@end itemize

You need to be able to create a simulated disk with a file system
partition.  The @command{pintos-mkdisk} program provides this
functionality.  From the @file{userprog/build} directory, execute
@code{pintos-mkdisk filesys.dsk --filesys-size=2}.  This command
creates a simulated disk named @file{filesys.dsk} that contains a @w{2
MB} PintOS file system partition.  Then format the file system
partition by passing @option{-f -q} on the kernel's command line:
@code{pintos -f -q}.  The @option{-f} option causes the file system to
be formatted, and @option{-q} causes PintOS to exit as soon as the
format is done.

You'll need a way to copy files in and out of the simulated file system.
The @code{pintos} @option{-p} (``put'') and @option{-g} (``get'')
options do this.  To copy @file{@var{file}} into the
PintOS file system, use the command @file{pintos -p @var{file} -- -q}.
(The @samp{--} is needed because @option{-p} is for the @command{pintos}
script, not for the simulated kernel.)  To copy it to the PintOS file
system under the name @file{@var{newname}}, add @option{-a
@var{newname}}: @file{pintos -p @var{file} -a @var{newname} -- -q}.  The
commands for copying files out of a VM are similar, but substitute
@option{-g} for @option{-p}.

Incidentally, these commands work by passing special commands
@command{extract} and @command{append} on the kernel's command line and copying
to and from a special simulated ``scratch'' partition.  If you're very
curious, you can look at the @command{pintos} script as well as
@file{filesys/fsutil.c} to learn the implementation details.

Here's a summary of how to create a disk with a file system partition,
format the file system, copy the @command{echo} program into the new
disk, and then run @command{echo}, passing argument @code{x}.
(Argument passing won't work until you implemented it.)  It assumes
that you've already built the examples in @file{examples} and that the
current directory is @file{userprog/build}:

@example
pintos-mkdisk filesys.dsk --filesys-size=2
pintos -f -q
pintos -p ../../examples/echo -a echo -- -q
pintos -q run 'echo x'
@end example

The three final steps can actually be combined into a single command:

@example
pintos-mkdisk filesys.dsk --filesys-size=2
pintos -p ../../examples/echo -a echo -- -f -q run 'echo x'
@end example

If you don't want to keep the file system disk around for later use or
inspection, you can even combine all four steps into a single command.
The @code{--filesys-size=@var{n}} option creates a temporary file
system partition
approximately @var{n} megabytes in size just for the duration of the
@command{pintos} run.  The PintOS automatic test suite makes extensive
use of this syntax:

@example
pintos --filesys-size=2 -p ../../examples/echo -a echo -- -f -q run 'echo x'
@end example

You can delete a file from the PintOS file system using the @code{rm
@var{file}} kernel action, e.g.@: @code{pintos -q rm @var{file}}.  Also,
@command{ls} lists the files in the file system and @code{cat
@var{file}} prints a file's contents to the display.

@node How User Programs Work
@subsection How User Programs Work

PintOS can run normal C programs, as long as they fit into memory and use
only the system calls you implement.  Notably, @func{malloc} cannot be
implemented because none of the system calls required for this task
allow for memory allocation.  PintOS also can't run programs that use
floating point operations, since the kernel doesn't save and restore the
processor's floating-point unit when switching threads.

The @file{src/examples} directory contains a few sample user
programs.  The @file{Makefile} in this directory
compiles the provided examples, and you can edit it
compile your own programs as well.  Some of the example programs will
only work once task 3 has been implemented.

PintOS can load @dfn{ELF} executables with the loader provided for you
in @file{userprog/process.c}.  ELF is a file format used by Linux,
Solaris, and many other operating systems for object files,
shared libraries, and executables.  You can actually use any compiler
and linker that output 80@var{x}86 ELF executables to produce programs
for PintOS.  (We've provided compilers and linkers that should do just
fine.)

You should realize immediately that, until you copy a
test program to the simulated file system, PintOS will be unable to do
useful work.  You won't be able to do
interesting things until you copy a variety of programs to the file system.
You might want to create a clean reference file system disk and copy that
over whenever you trash your @file{filesys.dsk} beyond a useful state,
which may happen occasionally while debugging.

@node Virtual Memory Layout
@subsection 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 @code{PHYS_BASE}, which is defined in
@file{threads/vaddr.h} and defaults to @t{0xc0000000} (3 GB).  Kernel
virtual memory occupies the rest of the virtual address space, from
@code{PHYS_BASE} up to 4 GB.

User virtual memory is per-process.
When the kernel switches from one process to another, it
also switches user virtual address spaces by changing the processor's
page directory base register (see @func{pagedir_activate} in
@file{userprog/pagedir.c}).  @struct{thread} contains a pointer to a
process's page table.

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, starting at @code{PHYS_BASE}.  That is, virtual address
@code{PHYS_BASE} accesses physical
address 0, virtual address @code{PHYS_BASE} + @t{0x1234} accesses
physical address @t{0x1234}, and so on up to the size of the machine's
physical memory.

A user program can only access its own user virtual memory.  An attempt to
access kernel virtual memory causes a page fault, handled by
@func{page_fault} in @file{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 an unmapped user virtual address
will cause a page fault.

@page
@menu
* Typical Memory Layout::       
@end menu

@node Typical Memory Layout
@subsubsection Typical Memory Layout

Conceptually, each process is
free to lay out its own user virtual memory however it
chooses.  In practice, user virtual memory is laid out like this:

@html
<CENTER>
@end html
@example
@group
   PHYS_BASE +----------------------------------+
             |            user stack            |
             |                 |                |
             |                 |                |
             |                 V                |
             |          grows downward          |
             |                                  |
             |                                  |
             |                                  |
             |                                  |
             |           grows upward           |
             |                 ^                |
             |                 |                |
             |                 |                |
             +----------------------------------+
             | uninitialized data segment (BSS) |
             +----------------------------------+
             |     initialized data segment     |
             +----------------------------------+
             |           code segment           |
  0x08048000 +----------------------------------+
             |                                  |
             |                                  |
             |                                  |
             |                                  |
             |                                  |
           0 +----------------------------------+
@end group
@end example
@html
</CENTER>
@end html

In this task, the user stack is fixed in size, but in task 3 it
will be allowed to grow.  Traditionally, the size of the uninitialized
data segment can be adjusted with a system call, but you will not have
to implement this.

The code segment in PintOS starts at user virtual address
@t{0x08084000}, approximately 128 MB from the bottom of the address
space.  This value is specified in @bibref{SysV-i386} and has no deep
significance.

The linker sets the layout of a user program in memory, as directed by a
``linker script'' that tells it the names and locations of the various
program segments.  You can learn more about linker scripts by reading
the ``Scripts'' chapter in the linker manual, accessible via @samp{info
ld}.

To view the layout of a particular executable, run @command{objdump}
(80@var{x}86) with the @option{-p}
option.

@node Accessing User Memory
@subsection Accessing User Memory

As part of a system
call, the kernel must often access memory through pointers provided by a user
program.  The kernel must be very careful about doing so, because
the user can pass a null pointer, a pointer to
unmapped virtual memory, or a pointer to kernel virtual address space
(above @code{PHYS_BASE}).  All of these types of invalid pointers must
be rejected without harm to the kernel or other running processes, by
terminating the offending process and freeing its resources.

There are at least two reasonable ways to do this correctly.  The
first method is to 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
@file{userprog/pagedir.c} and in @file{threads/vaddr.h}, specifically 
@func{pagedir_get_page} and @func{is_user_vaddr}.  This is the
simplest way to handle user memory access.

The second method is to check only that a user
pointer points below @code{PHYS_BASE}, then dereference it.
An invalid user pointer will cause a ``page fault'' that you can
handle by modifying the code for @func{page_fault} in
@file{userprog/exception.c}.  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 memory with @func{malloc}.  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 user pointers before dereferencing
them, this should be straightforward.  It's more difficult to handle
if an invalid pointer causes a page fault,
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:

@verbatim
/* Reads a byte at user virtual address UADDR.
   UADDR must be below PHYS_BASE.
   Returns the byte value if successful, -1 if a segfault
   occurred. */
static int
get_user (const uint8_t *uaddr)
{
  int result;
  asm ("movl $1f, %0; movzbl %1, %0; 1:"
       : "=&a" (result) : "m" (*uaddr));
  return result;
}
 
/* Writes BYTE to user address UDST.
   UDST must be below PHYS_BASE.
   Returns true if successful, false if a segfault occurred. */
static bool
put_user (uint8_t *udst, uint8_t byte)
{
  int error_code;
  asm ("movl $1f, %0; movb %b2, %1; 1:"
       : "=&a" (error_code), "=m" (*udst) : "q" (byte));
  return error_code != -1;
}
@end verbatim

Each of these functions assumes that the user address has already been
verified to be below @code{PHYS_BASE}.  They also assume that you've
modified @func{page_fault} so that a page fault in the kernel merely
sets the interupt frame @code{eax} to @t{0xffffffff} and copies the old value
into @code{eip}.

@page
@node Task 2 Suggested Order of Implementation
@section Suggested Order of Implementation

We suggest first implementing the following, which can happen in parallel:

@itemize
@item
Argument passing (@pxref{Argument Passing}).@* 
Every user program will page fault immediately until argument passing is implemented.

For now, you may simply wish to change
@example
*esp = PHYS_BASE;
@end example
@noindent to
@example
*esp = PHYS_BASE - 12;
@end example
in @func{setup_stack} to fake the set-up for a minimaml stack.

This will work for any example program that doesn't examine its arguments (e.g. @code{halt.c}), 
although the program's name will be printed as @code{(null)}.

Note that all of the Task 2 tests access the program arguments, so these will still page-fault and die. 
Thus, you will still fail all of the Task 2 tests at this point.

Until you implement argument passing fully, you should only run programs without passing command-line arguments.  
Currently, attempting to pass @strong{any} arguments to a program will cause the kernel to search for a program whose 
name includes those arguments. This will obviously fail and cause the kernel to abort running the program.

@item
User memory access (@pxref{Accessing User Memory}).  All system calls
need to read user memory.  Few system calls need to write to user
memory.

@item
System call infrastructure (@pxref{System Calls}).  Implement enough
code to read the system call number from the user stack and dispatch to
a handler based on it.

@item
The @code{exit} system call.  Every user program that finishes in the
normal way calls @code{exit}.  Even a program that returns from
@func{main} calls @code{exit} indirectly (see @func{_start} in
@file{lib/user/entry.c}).

@item
The @code{write} system call for writing to fd 1, the system console.
All of our test programs write to the console (the user process version
of @func{printf} is implemented this way), so they will all malfunction
until @code{write} is available.

@item
For now, change @func{process_wait} to an infinite loop (one that waits
forever). The purpose of @func{process_wait} is described in more detail 
above it's function stub in @file{src/userprog/process.c}, and more 
information can be found in the description of the @code{wait} system call 
later in this document.
The provided implementation returns immediately, so PintOS
will power off before any processes actually get to run.  You will
eventually need to provide a correct implementation.
@end itemize

After the above are implemented, user processes should work minimally,
although you will still fail all of the Task 2 tests 
(as these all print the program name @code{argv[0]} in their output).
However, you should at least be able to write to the console and exit correctly.
You can then refine your implementation so that some of the tests start
to pass (your first step should be to complete @func{process_wait} so 
that user programs return correctly). In order to minimise the amount of 
time you spend on this exercise, it is vital that you implement the 
@code{write}, @code{exit} and @code{wait} system calls before beginning the 
others.

@node Task 2 Requirements
@section Requirements

@menu
* Task 2 Design Document::   
* Process Termination Messages::  
* Argument Passing::            
* System Calls::                
* Denying Writes to Executables::  
@end menu

@node Task 2 Design Document
@subsection Design Document

When you submit your work for task 2, you must also submit a completed copy of
@uref{userprog.tmpl, , the task 2 design document template}. 
You can find a template design document for this task in @file{pintos/doc/userprog.tmpl} and also on CATe.
You are free to submit your design document as either a @file{.txt} or @file{.pdf} file.
We recommend that you read the design document template before you start working on the task.  
@xref{Task Documentation}, for a sample design document that goes along with a fictitious task.

@node Process Termination Messages
@subsection Process Termination Messages

Whenever a user process terminates, because it called @code{exit}
or for any other reason, print the process's name
and exit code, formatted as if printed by @code{printf ("%s:
exit(%d)\n", @dots{});}.  The name printed should be the full name
passed to @func{process_execute}, omitting command-line arguments.
Do not print these messages when a kernel thread that is not a user
process terminates, or
when the @code{halt} system call is invoked.  The message is optional
when a process fails to load.

Aside from this, don't print any other
messages that PintOS as provided doesn't already print.  You may find
extra messages useful during debugging, but they will confuse the
grading scripts and thus lower your score.

@node Argument Passing
@subsection Argument Passing

Currently, @func{process_execute}, found in @file{src/userprog/process.c}, does not support passing arguments to new processes.
Instead, the entire command line will be treated as the program name, resulting in the kernel failing to load the correct program file into memory.
You will need to fix this.

Implement argument passing by extending @func{process_execute} so that rather than simply taking a program file name to be the whole command line, 
it instead divides the command line into words at spaces. 
The first word is the program name, the second word is the first argument, and so on.  
That is, @code{process_execute("grep foo bar")} should run @command{grep} passing two arguments @code{foo} and @code{bar}.

Within a command line, multiple spaces are equivalent to a single space, 
so that @code{process_execute("grep @w{ }foo @w{ }@w{ }bar")} is 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).  
(There is an @strong{unrelated} limit of 128 bytes on command-line arguments that the @command{pintos} utility can pass to the kernel.)

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

Virtually all the code you will write relating to argument passing will be in @func{process_execute} and @func{start_process}. 
@func{process_execute} creates a new thread, calling @func{start_process} to load the actual process into the thread and set up the stack and other related structures.
You must ensure that the correct executable file is loaded within @func{start_process}.

@xref{Program Startup Details}, for information on exactly how you
need to set up the stack.

@node System Calls
@subsection System Calls

Implement the system call handler in @file{userprog/syscall.c}.  The
skeleton implementation we provide ``handles'' system calls by
terminating the process.  It will need to retrieve the system call
number, then any system call arguments, and carry out appropriate actions.

Implement the following system calls.  The prototypes listed are those
seen by a user program that includes @file{lib/user/syscall.h}.  (This
header, and all others in @file{lib/user}, are for use by user
programs only.)  System call numbers for each system call are defined in
@file{lib/syscall-nr.h}:

@deftypefn {System Call} void halt (void)
Terminates PintOS by calling @func{shutdown_power_off} (declared in
@file{devices/shutdown.h}).  This should be seldom used, because you lose
some information about possible deadlock situations, etc.
@var{*Warning*: The original PintOS documentation on the Stanford website
is outdated and incorrectly places the shutdown function in the wrong 
location. It's advisable that you don't use it as a reference
in completing any of the tasks.}
@end deftypefn

@deftypefn {System Call} void exit (int @var{status})
Terminates the current user program, sending its exit @var{status} to the
kernel.  If the process's parent @code{wait}s for it (see below), this
is the status
that will be returned.  Conventionally, a @var{status} of 0 indicates
success and nonzero values indicate errors.
@end deftypefn

@deftypefn {System Call} pid_t exec (const char *@var{cmd_line})
Runs the executable whose name is given in @var{cmd_line}, passing any
given arguments, and returns the new process's program id (pid).  Must
return pid -1, which otherwise should not be a valid pid, if
the program cannot load or run for any reason.
Thus, the parent process cannot return from the @code{exec} until it
knows whether the child process successfully loaded its executable.
You must use appropriate synchronization to ensure this.
@end deftypefn

@deftypefn {System Call} int wait (pid_t @var{pid})
Waits for a child process @var{pid} and retrieves the child's exit status.

If @var{pid} is still alive, waits until it terminates.
Then, returns the status that @var{pid} passed to @code{exit}. 
If @var{pid} did not call @code{exit()}, but was terminated by the kernel (e.g.@: killed due to an exception), 
@code{wait(pid)} must return -1. 
It is perfectly legal for a parent process to wait for child processes that have already terminated by the time the parent calls @code{wait}, 
but the kernel must still allow the parent to retrieve its child's exit status, or learn that the child was terminated by the kernel.

@code{wait} must fail and return -1 immediately if any of the following conditions are true:
@itemize @bullet
@item
@var{pid} does not refer to a direct child of the calling process.
@var{pid} is a direct child of the calling process if and only if the calling process received @var{pid} 
as a return value from a successful call to @code{exec}.

Note that children are not inherited: 
if @var{A} spawns child @var{B} and @var{B} spawns child process @var{C}, then @var{A} cannot wait for @var{C}, even if @var{B} is dead. 
A call to @code{wait(C)} by process @var{A} must fail. 
Similarly, orphaned processes are not assigned to a new parent if their parent process exits before they do.

@item
The process that calls @code{wait} has already called @code{wait} on @var{pid}. 
That is, a process may wait for any given child at most once.
@end itemize

Processes may spawn any number of children, wait for them in any order, 
and may even exit without having waited for some or all of their children.
Your design should consider all the ways in which waits can occur.
All of a process's resources, including its @struct{thread}, must be freed whether its parent ever waits for it or not, 
and regardless of whether the child exits before or after its parent.

As a special case, you must ensure that PintOS does not terminate until the initial process exits. 
The supplied PintOS code tries to do this by calling @func{process_wait} (in @file{userprog/process.c}) 
from @func{main} (in @file{threads/init.c}).

We strongly suggest that you implement @func{process_wait} according to the comment at the top of the function 
and then implement the @code{wait} system call in terms of @func{process_wait}.

Be aware that implementing this system call requires considerably more work than any of the others.
@end deftypefn

@deftypefn {System Call} bool create (const char *@var{file}, unsigned @var{initial_size})
Creates a new file called @var{file} initially @var{initial_size} bytes
in size.  Returns true if successful, false otherwise.
Creating a new file does not open it: opening the new file is a
separate operation which would require a @code{open} system call.
@end deftypefn

@deftypefn {System Call} bool remove (const char *@var{file})
Deletes the file called @var{file}.  Returns true if successful, false
otherwise.
A file may be removed regardless of whether it is open or closed, and
removing an open file does not close it.  @xref{Removing an Open
File}, for details.
@end deftypefn

@deftypefn {System Call} int open (const char *@var{file})
Opens the file called @var{file}.  Returns a nonnegative integer handle
called a ``file descriptor'' (fd), or -1 if the file could not be
opened.  

File descriptors numbered 0 and 1 are reserved for the console: fd 0
(@code{STDIN_FILENO}) is standard input, fd 1 (@code{STDOUT_FILENO}) is
standard output.  The @code{open} system call will never return either
of these file descriptors, which are valid as system call arguments only
as explicitly described below.

Each process has an independent set of file descriptors.  File
descriptors are not inherited by child processes.

When a single file is opened more than once, whether by a single
process or different processes, each @code{open} returns a new file
descriptor.  Different file descriptors for a single file are closed
independently in separate calls to @code{close} and they do not share
a file position.
@end deftypefn

@deftypefn {System Call} int filesize (int @var{fd})
Returns the size, in bytes, of the file open as @var{fd}.
@end deftypefn

@deftypefn {System Call} int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
Reads @var{size} bytes from the file open as @var{fd} into
@var{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
@func{input_getc}, which can be found in @file{src/devices/input.h}.
@end deftypefn

@deftypefn {System Call} int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
Writes @var{size} bytes from @var{buffer} to the open file @var{fd}.
Returns the number of bytes actually written, which may be less than
@var{size} if some bytes could not be written.

Writing past end-of-file would normally extend the file, but file growth
is not implemented by the basic file system.  The expected behaviour is
to write as many bytes as possible up to end-of-file and return the
actual number written, or 0 if no bytes could be written at all.

Fd 1 writes to the console.  Your code to write to the console should
write all of @var{buffer} in one call to @func{putbuf}, at least as
long as @var{size} is not bigger than a few hundred bytes.  (It is
reasonable to break up larger buffers.)  Otherwise,
lines of text output by different processes may end up interleaved on
the console, confusing both human readers and our grading scripts.
@end deftypefn

@deftypefn {System Call} void seek (int @var{fd}, unsigned @var{position})
Changes the next byte to be read or written in open file @var{fd} to
@var{position}, expressed in bytes from the beginning of the file.
(Thus, a @var{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.  
Normally, a later write would extend the file, filling any unwritten gap with zeros.  
However, in PintOS files have a fixed length, 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.
@end deftypefn

@deftypefn {System Call} unsigned tell (int @var{fd})
Returns the position of the next byte to be read or written in open
file @var{fd}, expressed in bytes from the beginning of the file.
@end deftypefn

@deftypefn {System Call} void close (int @var{fd})
Closes file descriptor @var{fd}.  
Exiting or terminating a process implicitly closes all its open file
descriptors, as if by calling this function for each one.
@end deftypefn

The system call handler defines other syscalls.  Ignore them for now.  You will
implement the rest in task 3, so be
sure to design your system with extensibility in mind.

To implement syscalls, you need to provide ways to read and write data
in user virtual address space.
You need this ability 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.
This can be a bit tricky: what if the user provides an invalid
pointer, a pointer into kernel memory, or a block
partially in one of those regions?  You should handle these cases by
terminating the user process.  We recommend
writing and testing this code before implementing any other system
call functionality.  @xref{Accessing User Memory}, for more information.

You must synchronize system calls so that
any number of user processes can make them at once.  In particular, it
is not safe to call into the file system code provided in the
@file{filesys} directory from multiple threads at once.  Your system
call implementation must treat the file system code as a critical
section.  Don't forget
that @func{process_execute} also accesses files.  For now, we
recommend against modifying code in the @file{filesys} directory.

We have provided you a user-level function for each system call in
@file{lib/user/syscall.c}.  These provide a way for user processes to
invoke each system call from a C program.  Each uses a little inline
assembly code to invoke the system call and (if appropriate) returns the
system call's return value.

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, panic, fail an assertion, or otherwise malfunction.  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 @code{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.

@xref{System Call Details}, for details on how system calls work.

@node Denying Writes to Executables
@subsection Denying Writes to Executables

Add code to deny writes to files in use as executables.  Many OSes do
this because of the unpredictable results if a process tried to run code
that was in the midst of being changed on disk.  This is especially
important once virtual memory is implemented in task 3, but it can't
hurt even now.

You can use @func{file_deny_write} to prevent writes to an open file.
Calling @func{file_allow_write} on the file will re-enable them (unless
the file is denied writes by another opener).  Closing a file will also
re-enable writes.  Thus, to deny writes to a process's executable, you
must keep it open as long as the process is still running.

@node Task 2 FAQ
@section FAQ

@table @b
@item How much code will I need to write?

Here's a summary of our reference solution, produced by the
@command{diffstat} program.  The final row gives total lines inserted
and deleted; a changed line counts as both an insertion and a deletion.

@verbatim
 threads/thread.c     |   13 
 threads/thread.h     |   26 +
 userprog/exception.c |    8 
 userprog/process.c   |  247 ++++++++++++++--
 userprog/syscall.c   |  468 ++++++++++++++++++++++++++++++-
 userprog/syscall.h   |    1 
 6 files changed, 725 insertions(+), 38 deletions(-)
@end verbatim

The reference solution represents just one possible solution.  Many
other solutions are also possible and many of those differ greatly from
the reference solution.  Some excellent solutions may not modify all the
files modified by the reference solution, and some may modify files not
modified by the reference solution.

@item Do we need a working Task 1 to implement Task 2?

No.

@item The kernel always panics when I run @code{pintos -p @var{file} -- -q}.

Did you format the file system (with @samp{pintos -f})?

Is your file name too long?  The file system limits file names to 14
characters.  A command like @samp{pintos -p ../../examples/echo -- -q}
will exceed the limit.  Use @samp{pintos -p ../../examples/echo -a echo
-- -q} to put the file under the name @file{echo} instead.

Is the file system full?

Does the file system already contain 16 files?  The base PintOS file
system has a 16-file limit.

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

@item When I run @code{pintos -p ../file --}, @file{file} isn't copied.

Files are written under the name you refer to them, by default, so in
this case the file copied in would be named @file{../file}.  You
probably want to run @code{pintos -p ../file -a file --} instead.

You can list the files in your file system with @code{pintos -q ls}.

@item All my user programs die with page faults.

This will happen if you haven't implemented argument passing
(or haven't done so correctly).  The basic C library for user programs tries
to read @var{argc} and @var{argv} off the stack.  If the stack
isn't properly set up, this causes a page fault.

@item All my user programs die with @code{system call!}

You'll have to implement system calls before you see anything else.
Every reasonable program tries to make at least one system call
(@func{exit}) and most programs make more than that.  Notably,
@func{printf} invokes the @code{write} system call.  The default system
call handler just prints @samp{system call!} and terminates the program.
Until then, you can use @func{hex_dump} to convince yourself that
argument passing is implemented correctly (@pxref{Program Startup Details}).

@item How can I disassemble user programs?

The @command{objdump} (80@var{x}86) utility can disassemble entire user
programs or object files.  Invoke it as @code{objdump -d
@var{file}}.  You can use GDB's
@code{disassemble} command to disassemble individual functions
(@pxref{GDB}).

@item Why do many C include files not work in PintOS programs?
@itemx Can I use lib@var{foo} 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.)

The chances are good that the library you want 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
user program C library does not have a @func{malloc} implementation.

@item How do I compile new user programs?

Modify @file{src/examples/Makefile}, then run @command{make}.

@item Can I run user programs under a debugger?

Yes, with some limitations.  @xref{GDB}.

@item What's the difference between @code{tid_t} and @code{pid_t}?

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

A @code{pid_t} identifies a user process.  It is used by user
processes and the kernel in the @code{exec} and @code{wait} system
calls.

You can choose whatever suitable types you like for @code{tid_t} and
@code{pid_t}.  By default, they're both @code{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.

@item What should I expect from the Task 2 code-review?

The code-review for this task will be conducted with each group in-person.
Our Task 2 code-review will cover @strong{four} main areas: 
functional correctness, efficiency, design quality and general coding style.

@itemize @bullet
@item For @strong{functional correctness}, we will be looking to see if your argument passing code can avoid stack-overflow for all possible input command lines.
We will also be checking if your data structures for storing file descriptors, your file-system accesses and your implementation of the @func{wait} and @func{exit} system calls are all free of any race conditions.

@item For @strong{efficiency}, we will be looking at how you are storing the process parent/child relationships, how you are storing child load status and ensuring that your code does not leak memory in any situation.

@item For @strong{design quality}, we will be looking at how you have abstracted your argument passing code from the underlying stack updates (pushing arguments and their pointers onto the stack) and your system call handler to avoid repetitive code for each syscall case.
We will also be looking at the level of fidelity in your use of synchronisation for the @func{exec}, @func{wait} and @func{exit} system calls.

@item For @strong{general coding style}, we will be paying attention to all of the usual elements of good style 
that you should be used to from last year (e.g. consistent code layout, appropriate use of comments, avoiding magic numbers, etc.)
as well as your use of git (e.g. commit frequency and commit message quality).
In this task, we will be paying particular attention to magic numbers in your system call handler, as well as your use of global variables anywhere in your solution.
@end itemize
@end table

@menu
* Argument Passing FAQ::        
* System Calls FAQ::            
@end menu

@node Argument Passing FAQ
@subsection Argument Passing FAQ

@table @b
@item Isn't the top of stack in kernel virtual memory?

The top of stack is at @code{PHYS_BASE}, typically @t{0xc0000000}, which
is also where kernel virtual memory starts.
But before the processor pushes data on the stack, it decrements the stack
pointer.  Thus, the first (4-byte) value pushed on the stack
will be at address @t{0xbffffffc}.

@item Is @code{PHYS_BASE} fixed?

No.  You should be able to support @code{PHYS_BASE} values that are
any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xf0000000},
simply via recompilation.
@end table

@node System Calls FAQ
@subsection System Calls FAQ

@table @b
@item Can I just cast a @code{struct file *} to get a file descriptor?
@itemx Can I just cast a @code{struct thread *} to a @code{pid_t}?

You will have to make these design decisions yourself.
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.

@item Can I set a maximum number of open files per process?

It is better not to set an arbitrary limit.  You may impose a limit of
128 open files per process, if necessary.

@item What happens when an open file is removed?
@anchor{Removing an Open File}

You should implement the standard Unix semantics for files.  That is, when
a file is removed any process which has a file descriptor for that file
may continue to use 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.

@item How can I run user programs that need more than 4 kB stack space?

You may modify the stack setup code to allocate more than one page of
stack space for each process.  In the next task, you will implement a
better solution.

@item What should happen if an @code{exec} fails midway through loading?

@code{exec} should return -1 if the child process fails to load for
any reason.  This includes the case where the load fails part of the
way through the process (e.g.@: where it runs out of memory in the
@code{multi-oom} test).  Therefore, the parent process cannot return
from the @code{exec} system call until it is established whether the
load was successful or not.  The child must communicate this
information to its parent using appropriate synchronization, such as a
semaphore (@pxref{Semaphores}), to ensure that the information is
communicated without race conditions.
@end table

@node 80x86 Calling Convention
@section 80@var{x}86 Calling Convention

This section summarizes important points of the convention used for
normal function calls on 32-bit 80@var{x}86 implementations of Unix.
Some details are omitted for brevity.  If you do want all the details,
refer to @bibref{SysV-i386}.

The calling convention works like this:

@enumerate 1
@item
The caller pushes each of the function's arguments on the stack one by
one, normally using the @code{PUSH} assembly language instruction.
Arguments are pushed in right-to-left order.

The stack grows downward: each push decrements the stack pointer, then
stores into the location it now points to, like the C expression
@samp{*--sp = @var{value}}.

@item
The caller pushes the address of its next instruction (the @dfn{return
address}) on the stack and jumps to the first instruction of the callee.
A single 80@var{x}86 instruction, @code{CALL}, does both.

@item
The callee executes.  When it takes control, the stack pointer points to
the return address, the first argument is just above it, the second
argument is just above the first argument, and so on.

@item
If the callee has a return value, it stores it into register @code{EAX}.

@item
The callee returns by popping the return address from the stack and
jumping to the location it specifies, using the 80@var{x}86 @code{RET}
instruction.

@item
The caller pops the arguments off the stack.
@end enumerate

Consider a function @func{f} that takes three @code{int} arguments.
This diagram shows a sample stack frame as seen by the callee at the
beginning of step 3 above, supposing that @func{f} is invoked as
@code{f(1, 2, 3)}.  The initial stack address is arbitrary:

@html
<CENTER>
@end html
@example
                             +----------------+
                  0xbffffe7c |        3       |
                  0xbffffe78 |        2       |
                  0xbffffe74 |        1       |
stack pointer --> 0xbffffe70 | return address |
                             +----------------+
@end example
@html
</CENTER>
@end html

@menu
* Program Startup Details::     
* System Call Details::         
@end menu

@node Program Startup Details
@subsection Program Startup Details

The PintOS C library for user programs designates @func{_start}, in
@file{lib/user/entry.c}, as the entry point for user programs.  This
function is a wrapper around @func{main} that calls @func{exit} if
@func{main} returns:

@example
void
_start (int argc, char *argv[]) 
@{
  exit (main (argc, argv));
@}
@end example

The kernel must put the arguments for the initial function on the stack
before it allows the user program to begin executing.  The arguments are
passed in the same way as the normal calling convention (@pxref{80x86
Calling Convention}).

Consider how to handle arguments for the following example command:
@samp{/bin/ls -l foo bar}.
First, break the command into words: @samp{/bin/ls},
@samp{-l}, @samp{foo}, @samp{bar}.  Place the words at the top of the
stack.  Order doesn't matter, because they will be referenced through
pointers.

Then, push the address of each string plus a null pointer sentinel, on
the stack, in right-to-left order.  These are the elements of
@code{argv}.  The null pointer sentinel ensures that @code{argv[argc]}
is a null pointer, as required by the C standard.  The order ensures
that @code{argv[0]} is at the lowest virtual address.  Word-aligned
accesses are faster than unaligned accesses, so for best performance
round the stack pointer down to a multiple of 4 before the first push.

Then, push @code{argv} (the address of @code{argv[0]}) and @code{argc},
in that order.  Finally, push a fake ``return address'': although the
entry function will never return, its stack frame must have the same
structure as any other.

The table below shows the state of the stack and the relevant registers
right before the beginning of the user program, assuming
@code{PHYS_BASE} is @t{0xc0000000}:

@html
<CENTER>
@end html
@multitable {@t{0xbfffffff}} {return address} {@t{/bin/ls\0}} {@code{void (*) ()}}
@item Address @tab Name @tab Data @tab Type
@item @t{0xbffffffc} @tab @code{argv[3][@dots{}]} @tab @samp{bar\0} @tab @code{char[4]}
@item @t{0xbffffff8} @tab @code{argv[2][@dots{}]} @tab @samp{foo\0} @tab @code{char[4]}
@item @t{0xbffffff5} @tab @code{argv[1][@dots{}]} @tab @samp{-l\0} @tab @code{char[3]}
@item @t{0xbfffffed} @tab @code{argv[0][@dots{}]} @tab @samp{/bin/ls\0} @tab @code{char[8]}
@item @t{0xbfffffec} @tab word-align @tab 0 @tab @code{uint8_t}
@item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0} @tab @code{char *}
@item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc} @tab @code{char *}
@item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8} @tab @code{char *}
@item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5} @tab @code{char *}
@item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed} @tab @code{char *}
@item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8} @tab @code{char **}
@item @t{0xbfffffd0} @tab @code{argc} @tab 4 @tab @code{int}
@item @t{0xbfffffcc} @tab return address @tab 0 @tab @code{void (*) ()}
@end multitable
@html
</CENTER>
@end html

In this example, the stack pointer would be initialized to
@t{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
@code{PHYS_BASE} (defined in @file{threads/vaddr.h}).

You may find the non-standard @func{hex_dump} function, declared in
@file{<stdio.h>}, useful for debugging your argument passing code.
Here's what it would show in the above example:

@verbatim
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.|
@end verbatim

@node System Call Details
@subsection System Call Details

The first task already dealt 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 (@pxref{External Interrupt Handling}).

The operating system also deals with software exceptions, which are
events that occur in program code (@pxref{Internal Interrupt
Handling}).  These can be errors such as a page fault or division by
zero.  Exceptions are also the means by which a user program
can request services (``system calls'') from the operating system.

In the 80@var{x}86 architecture, the @samp{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 @samp{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 (@pxref{80x86 Calling Convention}).

Thus, when the system call handler @func{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
@func{syscall_handler} as the @samp{esp} member of the
@struct{intr_frame} passed to it.  (@struct{intr_frame} is on the kernel
stack.)

The 80@var{x}86 convention for function return values is to place them
in the @code{EAX} register.  System calls that return a value can do
so by modifying the @samp{eax} member of @struct{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.