1 files changed, 1734 insertions, 0 deletions
diff --git a/doc/pintos_2.html b/doc/pintos_2.html
new file mode 100644
index 0000000..ae51974
--- /dev/null
+++ b/doc/pintos_2.html
@@ -0,0 +1,1734 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
+                      "http://www.w3.org/TR/html40/loose.dtd">
+<HTML>
+<!-- Created on March, 6 2012 by texi2html 1.66 -->
+<!--
+Written by: Lionel Cons <Lionel.Cons@cern.ch> (original author)
+            Karl Berry  <karl@freefriends.org>
+            Olaf Bachmann <obachman@mathematik.uni-kl.de>
+            and many others.
+Maintained by: Many creative people <dev@texi2html.cvshome.org>
+Send bugs and suggestions to <users@texi2html.cvshome.org>
+-->
+<HEAD>
+<TITLE>Pintos Projects: Project 0--Introducing Pintos</TITLE>
+<META NAME="description" CONTENT="Pintos Projects: Project 0--Introducing Pintos">
+<META NAME="keywords" CONTENT="Pintos Projects: Project 0--Introducing Pintos">
+<META NAME="resource-type" CONTENT="document">
+<META NAME="distribution" CONTENT="global">
+<META NAME="Generator" CONTENT="texi2html 1.66">
+<LINK REL="stylesheet" HREF="pintos.css">
+</HEAD>
+<BODY >
+<A NAME="SEC15"></A>
+<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
+<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_1.html#SEC1"> &lt;&lt; </A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_3.html#SEC41"> &gt;&gt; </A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
+</TR></TABLE>
+<HR SIZE=2>
+<H1> 2. Project 0: Introducing Pintos </H1>
+<!--docid::SEC15::-->
+<P>
+In this assignment, you will learn about the existing functionality
+in Pintos, and add two small features to the system: a more efficient
+implementation of <Q><SAMP>sleep</SAMP></Q>, and the ability to pass command line
+arguments to user programs.
+</P>
+<P>
+You will be working in the <Q><TT>threads</TT></Q> directory for the first part
+of this assignment (with some work in the <Q><TT>devices</TT></Q> directory on
+the side), and modify the file <Q><TT>userprog/process.c</TT></Q> in the second part.
+</P>
+<P>
+The tests for Project 0 are executed by changing the working directory
+to <Q><TT>intro</TT></Q> and running <Q><SAMP>make</SAMP></Q> followed by <Q><SAMP>make check</SAMP></Q>.
+</P>
+<P>
+Before you read the description of this project, you should read all of
+the following sections: <A HREF="pintos_1.html#SEC1">1. Introduction</A>, <A HREF="pintos_6.html#SEC89">B. Coding Standards</A>,
+<A HREF="pintos_8.html#SEC96">D. Debugging Tools</A>, and <A HREF="pintos_9.html#SEC109">E. Development Tools</A>.  You should at least
+skim the material from <A HREF="pintos_5.html#SEC49">A.1 Loading</A> through <A HREF="pintos_5.html#SEC69">A.5 Memory Allocation</A>, especially <A HREF="pintos_5.html#SEC58">A.3 Synchronization</A>.
+</P>
+<P>
+<A NAME="Understanding Threads"></A>
+<HR SIZE="6">
+<A NAME="SEC16"></A>
+<H2> 2.1 Understanding Threads </H2>
+<!--docid::SEC16::-->
+<P>
+The first step is to read and understand the code for the initial thread
+system.
+Pintos already implements thread creation and thread completion,
+a simple scheduler to switch between threads, and synchronization
+primitives (semaphores, locks, condition variables, and optimization
+barriers).
+</P>
+<P>
+Some of this code might seem slightly mysterious.  If
+you haven't already compiled and run the base system, as described in
+the introduction (see section <A HREF="pintos_1.html#SEC1">1. Introduction</A>), you should do so now.  You
+can read through parts of the source code to see what's going
+on.  If you like, you can add calls to <CODE>printf()</CODE> almost
+anywhere, then recompile and run to see what happens and in what
+order.  You can also run the kernel in a debugger and set breakpoints
+at interesting spots, single-step through code and examine data, and
+so on.
+</P>
+<P>
+When a thread is created, you are creating a new context to be
+scheduled.  You provide a function to be run in this context as an
+argument to <CODE>thread_create()</CODE>.  The first time the thread is
+scheduled and runs, it starts from the beginning of that function
+and executes in that context.  When the function returns, the thread
+terminates.  Each thread, therefore, acts like a mini-program running
+inside Pintos, with the function passed to <CODE>thread_create()</CODE>
+acting like <CODE>main()</CODE>.
+</P>
+<P>
+At any given time, exactly one thread runs and the rest, if any,
+become inactive.  The scheduler decides which thread to
+run next.  (If no thread is ready to run
+at any given time, then the special &quot;idle&quot; thread, implemented in
+<CODE>idle()</CODE>, runs.)
+Synchronization primitives can force context switches when one
+thread needs to wait for another thread to do something.
+</P>
+<P>
+The mechanics of a context switch are
+in <Q><TT>threads/switch.S</TT></Q>, which is 80<VAR>x</VAR>86
+assembly code.  (You don't have to understand it.)  It saves the
+state of the currently running thread and restores the state of the
+thread we're switching to.
+</P>
+<P>
+Using the GDB debugger, slowly trace through a context
+switch to see what happens (see section <A HREF="pintos_8.html#SEC102">D.5 GDB</A>).  You can set a
+breakpoint on <CODE>schedule()</CODE> to start out, and then
+single-step from there.<A NAME="DOCF1" HREF="pintos_fot.html#FOOT1">(1)</A>  Be sure
+to keep track of each thread's address
+and state, and what procedures are on the call stack for each thread.
+You will notice that when one thread calls <CODE>switch_threads()</CODE>,
+another thread starts running, and the first thing the new thread does
+is to return from <CODE>switch_threads()</CODE>.  You will understand the thread
+system once you understand why and how the <CODE>switch_threads()</CODE> that
+gets called is different from the <CODE>switch_threads()</CODE> that returns.
+See section <A HREF="pintos_5.html#SEC57">A.2.3 Thread Switching</A>, for more information.
+</P>
+<P>
+<STRONG>Warning</STRONG>: In Pintos, each thread is assigned a small,
+fixed-size execution stack just under 4 kB in size.  The kernel
+tries to detect stack overflow, but it cannot do so perfectly.  You
+may cause bizarre problems, such as mysterious kernel panics, if you
+declare large data structures as non-static local variables,
+e.g. <Q><SAMP>int buf[1000];</SAMP></Q>.  Alternatives to stack allocation include
+the page allocator and the block allocator (see section <A HREF="pintos_5.html#SEC69">A.5 Memory Allocation</A>).
+</P>
+<P>
+<A NAME="Project 1 Source Files"></A>
+<HR SIZE="6">
+<A NAME="SEC17"></A>
+<H3> 2.1.1 Source Files </H3>
+<!--docid::SEC17::-->
+<P>
+Here is a brief overview of the files in the <Q><TT>threads</TT></Q>
+directory.  You will not need to modify most of this code, but the
+hope is that presenting this overview will give you a start on what
+code to look at.
+</P>
+<P>
+</P>
+<DL COMPACT>
+<DT><Q><TT>loader.S</TT></Q>
+<DD><DT><Q><TT>loader.h</TT></Q>
+<DD>The kernel loader.  Assembles to 512 bytes of code and data that the
+PC BIOS loads into memory and which in turn finds the kernel on disk,
+loads it into memory, and jumps to <CODE>start()</CODE> in <Q><TT>start.S</TT></Q>.
+See section <A HREF="pintos_5.html#SEC50">A.1.1 The Loader</A>, for details.  You should not need to look at
+this code or modify it.
+<P>
+</P>
+<DT><Q><TT>start.S</TT></Q>
+<DD>Does basic setup needed for memory protection and 32-bit
+operation on 80<VAR>x</VAR>86 CPUs.  Unlike the loader, this code is
+actually part of the kernel.  See section <A HREF="pintos_5.html#SEC51">A.1.2 Low-Level Kernel Initialization</A>,
+for details.
+<P>
+</P>
+<DT><Q><TT>kernel.lds.S</TT></Q>
+<DD>The linker script used to link the kernel.  Sets the load address of
+the kernel and arranges for <Q><TT>start.S</TT></Q> to be near the beginning
+of the kernel image.  See section <A HREF="pintos_5.html#SEC50">A.1.1 The Loader</A>, for details. Again, you
+should not need to look at this code
+or modify it, but it's here in case you're curious.
+<P>
+</P>
+<DT><Q><TT>init.c</TT></Q>
+<DD><DT><Q><TT>init.h</TT></Q>
+<DD>Kernel initialization, including <CODE>main()</CODE>, the kernel's &quot;main
+program.&quot;  You should look over <CODE>main()</CODE> at least to see what
+gets initialized.  You might want to add your own initialization code
+here.  See section <A HREF="pintos_5.html#SEC52">A.1.3 High-Level Kernel Initialization</A>, for details.
+<P>
+</P>
+<DT><Q><TT>thread.c</TT></Q>
+<DD><DT><Q><TT>thread.h</TT></Q>
+<DD>Basic thread support.  Much of your work will take place in these files.
+<Q><TT>thread.h</TT></Q> defines <CODE>struct thread</CODE>, which you are likely to modify
+in all three projects.  See <A HREF="pintos_5.html#SEC55">A.2.1 <CODE>struct thread</CODE></A> and <A HREF="pintos_5.html#SEC54">A.2 Threads</A> for
+more information.
+<P>
+</P>
+<DT><Q><TT>switch.S</TT></Q>
+<DD><DT><Q><TT>switch.h</TT></Q>
+<DD>Assembly language routine for switching threads.  Already discussed
+above.  See section <A HREF="pintos_5.html#SEC56">A.2.2 Thread Functions</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>palloc.c</TT></Q>
+<DD><DT><Q><TT>palloc.h</TT></Q>
+<DD>Page allocator, which hands out system memory in multiples of 4 kB
+pages.  See section <A HREF="pintos_5.html#SEC70">A.5.1 Page Allocator</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>malloc.c</TT></Q>
+<DD><DT><Q><TT>malloc.h</TT></Q>
+<DD>A simple implementation of <CODE>malloc()</CODE> and <CODE>free()</CODE> for
+the kernel.  See section <A HREF="pintos_5.html#SEC71">A.5.2 Block Allocator</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>interrupt.c</TT></Q>
+<DD><DT><Q><TT>interrupt.h</TT></Q>
+<DD>Basic interrupt handling and functions for turning interrupts on and
+off.  See section <A HREF="pintos_5.html#SEC65">A.4 Interrupt Handling</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>intr-stubs.S</TT></Q>
+<DD><DT><Q><TT>intr-stubs.h</TT></Q>
+<DD>Assembly code for low-level interrupt handling.  See section <A HREF="pintos_5.html#SEC66">A.4.1 Interrupt Infrastructure</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>synch.c</TT></Q>
+<DD><DT><Q><TT>synch.h</TT></Q>
+<DD>Basic synchronization primitives: semaphores, locks, condition
+variables, and optimization barriers.  You will need to use these for
+synchronization in all
+four projects.  See section <A HREF="pintos_5.html#SEC58">A.3 Synchronization</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>io.h</TT></Q>
+<DD>Functions for I/O port access.  This is mostly used by source code in
+the <Q><TT>devices</TT></Q> directory that you won't have to touch.
+<P>
+</P>
+<DT><Q><TT>vaddr.h</TT></Q>
+<DD><DT><Q><TT>pte.h</TT></Q>
+<DD>Functions and macros for working with virtual addresses and page table
+entries.  These will be more important to you in project 2.  For now,
+you can ignore them.
+<P>
+</P>
+<DT><Q><TT>flags.h</TT></Q>
+<DD>Macros that define a few bits in the 80<VAR>x</VAR>86 &quot;flags&quot; register.
+Probably of no interest.  See [ <A HREF="pintos_10.html#IA32-v1">IA32-v1</A>], section 3.4.3, &quot;EFLAGS
+Register,&quot; for more information.
+</DL>
+<P>
+<A NAME="devices code"></A>
+<HR SIZE="6">
+<A NAME="SEC18"></A>
+<H4> 2.1.1.1 <Q><TT>devices</TT></Q> code </H4>
+<!--docid::SEC18::-->
+<P>
+The basic threaded kernel also includes these files in the
+<Q><TT>devices</TT></Q> directory:
+</P>
+<P>
+</P>
+<DL COMPACT>
+<DT><Q><TT>timer.c</TT></Q>
+<DD><DT><Q><TT>timer.h</TT></Q>
+<DD>System timer that ticks, by default, 100 times per second.  You will
+modify this code in this project.
+<P>
+</P>
+<DT><Q><TT>vga.c</TT></Q>
+<DD><DT><Q><TT>vga.h</TT></Q>
+<DD>VGA display driver.  Responsible for writing text to the screen.
+You should have no need to look at this code.  <CODE>printf()</CODE>
+calls into the VGA display driver for you, so there's little reason to
+call this code yourself.
+<P>
+</P>
+<DT><Q><TT>serial.c</TT></Q>
+<DD><DT><Q><TT>serial.h</TT></Q>
+<DD>Serial port driver.  Again, <CODE>printf()</CODE> calls this code for you,
+so you don't need to do so yourself.
+It handles serial input by passing it to the input layer (see below).
+<P>
+</P>
+<DT><Q><TT>block.c</TT></Q>
+<DD><DT><Q><TT>block.h</TT></Q>
+<DD>An abstraction layer for <EM>block devices</EM>, that is, random-access,
+disk-like devices that are organized as arrays of fixed-size blocks.
+Out of the box, Pintos supports two types of block devices: IDE disks
+and partitions.
+<P>
+</P>
+<DT><Q><TT>ide.c</TT></Q>
+<DD><DT><Q><TT>ide.h</TT></Q>
+<DD>Supports reading and writing sectors on up to 4 IDE disks.
+<P>
+</P>
+<DT><Q><TT>partition.c</TT></Q>
+<DD><DT><Q><TT>partition.h</TT></Q>
+<DD>Understands the structure of partitions on disks, allowing a single
+disk to be carved up into multiple regions (partitions) for
+independent use.
+<P>
+</P>
+<DT><Q><TT>kbd.c</TT></Q>
+<DD><DT><Q><TT>kbd.h</TT></Q>
+<DD>Keyboard driver.  Handles keystrokes passing them to the input layer
+(see below).
+<P>
+</P>
+<DT><Q><TT>input.c</TT></Q>
+<DD><DT><Q><TT>input.h</TT></Q>
+<DD>Input layer.  Queues input characters passed along by the keyboard or
+serial drivers.
+<P>
+</P>
+<DT><Q><TT>intq.c</TT></Q>
+<DD><DT><Q><TT>intq.h</TT></Q>
+<DD>Interrupt queue, for managing a circular queue that both kernel
+threads and interrupt handlers want to access.  Used by the keyboard
+and serial drivers.
+<P>
+</P>
+<DT><Q><TT>rtc.c</TT></Q>
+<DD><DT><Q><TT>rtc.h</TT></Q>
+<DD>Real-time clock driver, to enable the kernel to determine the current
+date and time.  By default, this is only used by <Q><TT>thread/init.c</TT></Q>
+to choose an initial seed for the random number generator.
+<P>
+</P>
+<DT><Q><TT>speaker.c</TT></Q>
+<DD><DT><Q><TT>speaker.h</TT></Q>
+<DD>Driver that can produce tones on the PC speaker.
+<P>
+</P>
+<DT><Q><TT>pit.c</TT></Q>
+<DD><DT><Q><TT>pit.h</TT></Q>
+<DD>Code to configure the 8254 Programmable Interrupt Timer.  This code is
+used by both <Q><TT>devices/timer.c</TT></Q> and <Q><TT>devices/speaker.c</TT></Q>
+because each device uses one of the PIT's output channel.
+</DL>
+<P>
+<A NAME="lib files"></A>
+<HR SIZE="6">
+<A NAME="SEC19"></A>
+<H4> 2.1.1.2 <Q><TT>lib</TT></Q> files </H4>
+<!--docid::SEC19::-->
+<P>
+Finally, <Q><TT>lib</TT></Q> and <Q><TT>lib/kernel</TT></Q> contain useful library
+routines.  (<Q><TT>lib/user</TT></Q> will be used by user programs, starting in
+project 2, but it is not part of the kernel.)  Here's a few more
+details:
+</P>
+<P>
+</P>
+<DL COMPACT>
+<DT><Q><TT>ctype.h</TT></Q>
+<DD><DT><Q><TT>inttypes.h</TT></Q>
+<DD><DT><Q><TT>limits.h</TT></Q>
+<DD><DT><Q><TT>stdarg.h</TT></Q>
+<DD><DT><Q><TT>stdbool.h</TT></Q>
+<DD><DT><Q><TT>stddef.h</TT></Q>
+<DD><DT><Q><TT>stdint.h</TT></Q>
+<DD><DT><Q><TT>stdio.c</TT></Q>
+<DD><DT><Q><TT>stdio.h</TT></Q>
+<DD><DT><Q><TT>stdlib.c</TT></Q>
+<DD><DT><Q><TT>stdlib.h</TT></Q>
+<DD><DT><Q><TT>string.c</TT></Q>
+<DD><DT><Q><TT>string.h</TT></Q>
+<DD>A subset of the standard C library.  See section <A HREF="pintos_6.html#SEC91">B.2 C99</A>, for
+information
+on a few recently introduced pieces of the C library that you might
+not have encountered before.  See section <A HREF="pintos_6.html#SEC92">B.3 Unsafe String Functions</A>, for
+information on what's been intentionally left out for safety.
+<P>
+</P>
+<DT><Q><TT>debug.c</TT></Q>
+<DD><DT><Q><TT>debug.h</TT></Q>
+<DD>Functions and macros to aid debugging.  See section <A HREF="pintos_8.html#SEC96">D. Debugging Tools</A>, for
+more information.
+<P>
+</P>
+<DT><Q><TT>random.c</TT></Q>
+<DD><DT><Q><TT>random.h</TT></Q>
+<DD>Pseudo-random number generator.  The actual sequence of random values
+will not vary from one Pintos run to another, unless you do one of
+three things: specify a new random seed value on the <Q><SAMP>-rs</SAMP></Q>
+kernel command-line option on each run, or use a simulator other than
+Bochs, or specify the <Q><SAMP>-r</SAMP></Q> option to <CODE>pintos</CODE>.
+<P>
+</P>
+<DT><Q><TT>round.h</TT></Q>
+<DD>Macros for rounding.
+<P>
+</P>
+<DT><Q><TT>syscall-nr.h</TT></Q>
+<DD>System call numbers.  Not used until project 2.
+<P>
+</P>
+<DT><Q><TT>kernel/list.c</TT></Q>
+<DD><DT><Q><TT>kernel/list.h</TT></Q>
+<DD>Doubly linked list implementation.  Used all over the Pintos code, and
+you'll probably want to use it a few places yourself.
+<P>
+</P>
+<DT><Q><TT>kernel/bitmap.c</TT></Q>
+<DD><DT><Q><TT>kernel/bitmap.h</TT></Q>
+<DD>Bitmap implementation.  You can use this in your code if you like, but
+you probably won't have any need for it in project 0 and project 1.
+<P>
+</P>
+<DT><Q><TT>kernel/hash.c</TT></Q>
+<DD><DT><Q><TT>kernel/hash.h</TT></Q>
+<DD>Hash table implementation.
+<P>
+</P>
+<DT><Q><TT>kernel/console.c</TT></Q>
+<DD><DT><Q><TT>kernel/console.h</TT></Q>
+<DD><DT><Q><TT>kernel/stdio.h</TT></Q>
+<DD>Implements <CODE>printf()</CODE> and a few other functions.
+</DL>
+<P>
+<A NAME="Project 1 Synchronization"></A>
+<HR SIZE="6">
+<A NAME="SEC20"></A>
+<H3> 2.1.2 Synchronization </H3>
+<!--docid::SEC20::-->
+<P>
+Proper synchronization is an important part of the solutions to these
+problems.  Any synchronization problem can be easily solved by turning
+interrupts off: while interrupts are off, there is no concurrency, so
+there's no possibility for race conditions.  Therefore, it's tempting to
+solve all synchronization problems this way, but <STRONG>don't</STRONG>.
+Instead, use semaphores, locks, and condition variables to solve the
+bulk of your synchronization problems.  Read the tour section on
+synchronization (see section <A HREF="pintos_5.html#SEC58">A.3 Synchronization</A>) or the comments in
+<Q><TT>threads/synch.c</TT></Q> if you're unsure what synchronization primitives
+may be used in what situations.
+</P>
+<P>
+In the Pintos projects, the only class of problem best solved by
+disabling interrupts is coordinating data shared between a kernel thread
+and an interrupt handler.  Because interrupt handlers can't sleep, they
+can't acquire locks.  This means that data shared between kernel threads
+and an interrupt handler must be protected within a kernel thread by
+turning off interrupts.
+</P>
+<P>
+This project only requires accessing a little bit of thread state from
+interrupt handlers.  For the alarm clock, the timer interrupt needs to
+wake up sleeping threads.  In the advanced scheduler, the timer
+interrupt needs to access a few global and per-thread variables.  When
+you access these variables from kernel threads, you will need to disable
+interrupts to prevent the timer interrupt from interfering.
+</P>
+<P>
+When you do turn off interrupts, take care to do so for the least amount
+of code possible, or you can end up losing important things such as
+timer ticks or input events.  Turning off interrupts also increases the
+interrupt handling latency, which can make a machine feel sluggish if
+taken too far.
+</P>
+<P>
+The synchronization primitives themselves in <Q><TT>synch.c</TT></Q> are
+implemented by disabling interrupts.  You may need to increase the
+amount of code that runs with interrupts disabled here, but you should
+still try to keep it to a minimum.
+</P>
+<P>
+Disabling interrupts can be useful for debugging, if you want to make
+sure that a section of code is not interrupted.  You should remove
+debugging code before turning in your project.  (Don't just comment it
+out, because that can make the code difficult to read.)
+</P>
+<P>
+There should be no busy waiting in your submission.  A tight loop that
+calls <CODE>thread_yield()</CODE> is one form of busy waiting.
+</P>
+<P>
+<A NAME="Development Suggestions"></A>
+<HR SIZE="6">
+<A NAME="SEC21"></A>
+<H3> 2.1.3 Development Suggestions </H3>
+<!--docid::SEC21::-->
+<P>
+In the past, many groups divided the assignment into pieces, then each
+group member worked on his or her piece until just before the
+deadline, at which time the group reconvened to combine their code and
+submit.  <STRONG>This is a bad idea.  We do not recommend this
+approach.</STRONG>  Groups that do this often find that two changes conflict
+with each other, requiring lots of last-minute debugging.  Some groups
+who have done this have turned in code that did not even compile or
+boot, much less pass any tests.
+</P>
+<P>
+Instead, we recommend integrating your team's changes early and often,
+using the source code control system git.
+This is less likely to produce surprises, because everyone can see
+everyone else's code as it is written, instead of just when it is
+finished.  These systems also make it possible to review changes and,
+when a change introduces a bug, drop back to working versions of code.
+</P>
+<P>
+You should expect to run into bugs that you simply don't understand
+while working on this and subsequent projects.  When you do,
+reread the appendix on debugging tools, which is filled with
+useful debugging tips that should help you to get back up to speed
+(see section <A HREF="pintos_8.html#SEC96">D. Debugging Tools</A>).  Be sure to read the section on backtraces
+(see section <A HREF="pintos_8.html#SEC100">D.4 Backtraces</A>), which will help you to get the most out of every
+kernel panic or assertion failure.
+</P>
+<P>
+<A NAME="Understanding User Programs"></A>
+<HR SIZE="6">
+<A NAME="SEC22"></A>
+<H2> 2.2 Understanding User Programs </H2>
+<!--docid::SEC22::-->
+<P>
+The tests for both the alarm clock assignment in Project 0, and the
+priority scheduler in Project 1, run as part of the operating system
+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.
+</P>
+<P>
+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.
+</P>
+<P>
+In Project 2, 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.
+</P>
+<P>
+<A NAME="User Program Source Files"></A>
+<HR SIZE="6">
+<A NAME="SEC23"></A>
+<H3> 2.2.1 Source Files </H3>
+<!--docid::SEC23::-->
+<P>
+</P>
+<DL COMPACT>
+<DT><Q><TT>process.c</TT></Q>
+<DD><DT><Q><TT>process.h</TT></Q>
+<DD>Loads ELF binaries and starts processes.
+<P>
+</P>
+<DT><Q><TT>pagedir.c</TT></Q>
+<DD><DT><Q><TT>pagedir.h</TT></Q>
+<DD>A simple manager for 80<VAR>x</VAR>86 hardware page tables.
+Although you probably won't want to modify this code for this project,
+you may want to call some of its functions.
+See  <A HREF="pintos_4.html#Page Tables">Page Tables</A>, for more information.
+<P>
+</P>
+<DT><Q><TT>syscall.c</TT></Q>
+<DD><DT><Q><TT>syscall.h</TT></Q>
+<DD>Whenever a user process wants to access some kernel functionality, it
+invokes a system call.
+<P>
+</P>
+<DT><Q><TT>exception.c</TT></Q>
+<DD><DT><Q><TT>exception.h</TT></Q>
+<DD>When a user process performs a privileged or prohibited operation, it
+traps into the kernel as an &quot;exception&quot; or &quot;fault.&quot;<A NAME="DOCF2" HREF="pintos_fot.html#FOOT2">(2)</A>  These files handle
+exceptions. In project 2, you will need to modify the page fault
+handler to support lazy page loading and stack growth.
+<P>
+</P>
+<DT><Q><TT>gdt.c</TT></Q>
+<DD><DT><Q><TT>gdt.h</TT></Q>
+<DD>The 80<VAR>x</VAR>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 projects.  You can read the code if
+you're interested in how the GDT works.
+<P>
+</P>
+<DT><Q><TT>tss.c</TT></Q>
+<DD><DT><Q><TT>tss.h</TT></Q>
+<DD>The Task-State Segment (TSS) is used for 80<VAR>x</VAR>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 projects.
+You can read the code if you're interested in how the TSS
+works.
+</DL>
+<P>
+<A NAME="Using the File System"></A>
+<HR SIZE="6">
+<A NAME="SEC24"></A>
+<H3> 2.2.2 Using the File System </H3>
+<!--docid::SEC24::-->
+<P>
+You will need to interface to the file system code, because
+user programs are loaded from the file system and most of the
+system calls you must implement deal with the file system. 
+You will want to look over the <Q><TT>filesys.h</TT></Q> and <Q><TT>file.h</TT></Q>
+interfaces to understand how to use the file system, and especially
+its many limitations.
+</P>
+<P>
+There is no need to modify the file system code in this course, and so
+we recommend that you do not.  Working on the file system is likely to
+distract you from the project's foci.
+</P>
+<P>
+You will have to tolerate the following limitations, however:
+</P>
+<P>
+<UL>
+<LI>
+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.
+<P>
+</P>
+<LI>
+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.
+<P>
+</P>
+<LI>
+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.
+<P>
+</P>
+<LI>
+No subdirectories.
+<P>
+</P>
+<LI>
+File names are limited to 14 characters.
+<P>
+</P>
+<LI>
+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.
+</UL>
+<P>
+One important feature is included:
+</P>
+<P>
+<UL>
+<LI>
+Unix-like semantics for <CODE>filesys_remove()</CODE> 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.  See  <A HREF="pintos_2.html#Removing an Open File">Removing an Open File</A>, for more information.
+</UL>
+<P>
+You need to be able to create a simulated disk with a file system
+partition.  The <CODE>pintos-mkdisk</CODE> program provides this
+functionality.  From the <Q><TT>userprog/build</TT></Q> directory, execute
+<CODE>pintos-mkdisk filesys.dsk --filesys-size=2</CODE>.  This command
+creates a simulated disk named <Q><TT>filesys.dsk</TT></Q> that contains a 2
+MB Pintos file system partition.  Then format the file system
+partition by passing <Q><SAMP>-f -q</SAMP></Q> on the kernel's command line:
+<CODE>pintos -f -q</CODE>.  The <Q><SAMP>-f</SAMP></Q> option causes the file system to
+be formatted, and <Q><SAMP>-q</SAMP></Q> causes Pintos to exit as soon as the
+format is done.
+</P>
+<P>
+You'll need a way to copy files in and out of the simulated file system.
+The <CODE>pintos</CODE> <Q><SAMP>-p</SAMP></Q> (&quot;put&quot;) and <Q><SAMP>-g</SAMP></Q> (&quot;get&quot;)
+options do this.  To copy <Q><TT><VAR>file</VAR></TT></Q> into the
+Pintos file system, use the command <Q><TT>pintos -p <VAR>file</VAR> -- -q</TT></Q>.
+(The <Q><SAMP>--</SAMP></Q> is needed because <Q><SAMP>-p</SAMP></Q> is for the <CODE>pintos</CODE>
+script, not for the simulated kernel.)  To copy it to the Pintos file
+system under the name <Q><TT><VAR>newname</VAR></TT></Q>, add <Q><SAMP>-a
+<VAR>newname</VAR></SAMP></Q>: <Q><TT>pintos -p <VAR>file</VAR> -a <VAR>newname</VAR> -- -q</TT></Q>.  The
+commands for copying files out of a VM are similar, but substitute
+<Q><SAMP>-g</SAMP></Q> for <Q><SAMP>-p</SAMP></Q>.
+</P>
+<P>
+Incidentally, these commands work by passing special commands
+<CODE>extract</CODE> and <CODE>append</CODE> on the kernel's command line and copying
+to and from a special simulated &quot;scratch&quot; partition.  If you're very
+curious, you can look at the <CODE>pintos</CODE> script as well as
+<Q><TT>filesys/fsutil.c</TT></Q> to learn the implementation details.
+</P>
+<P>
+Here's a summary of how to create a disk with a file system partition,
+format the file system, copy the <CODE>echo</CODE> program into the new
+disk, and then run <CODE>echo</CODE>, passing argument <CODE>x</CODE>.
+(Argument passing won't work until you implemented it.)  It assumes
+that you've already built the examples in <Q><TT>examples</TT></Q> and that the
+current directory is <Q><TT>userprog/build</TT></Q>:
+</P>
+<P>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>pintos-mkdisk filesys.dsk --filesys-size=2
+pintos -f -q
+pintos -p ../../examples/echo -a echo -- -q
+pintos -q run 'echo x'
+</pre></td></tr></table><P>
+The three final steps can actually be combined into a single command:
+</P>
+<P>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>pintos-mkdisk filesys.dsk --filesys-size=2
+pintos -p ../../examples/echo -a echo -- -f -q run 'echo x'
+</pre></td></tr></table><P>
+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</VAR></CODE> option creates a temporary file
+system partition
+approximately <VAR>n</VAR> megabytes in size just for the duration of the
+<CODE>pintos</CODE> run.  The Pintos automatic test suite makes extensive
+use of this syntax:
+</P>
+<P>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>pintos --filesys-size=2 -p ../../examples/echo -a echo -- -f -q run 'echo x'
+</pre></td></tr></table><P>
+You can delete a file from the Pintos file system using the <CODE>rm
+<VAR>file</VAR></CODE> kernel action, e.g. <CODE>pintos -q rm <VAR>file</VAR></CODE>.  Also,
+<CODE>ls</CODE> lists the files in the file system and <CODE>cat
+<VAR>file</VAR></CODE> prints a file's contents to the display.
+</P>
+<P>
+<A NAME="How User Programs Work"></A>
+<HR SIZE="6">
+<A NAME="SEC25"></A>
+<H3> 2.2.3 How User Programs Work </H3>
+<!--docid::SEC25::-->
+<P>
+Pintos can run normal C programs, as long as they fit into memory and use
+only the system calls you implement.  Notably, <CODE>malloc()</CODE> cannot be
+implemented because none of the system calls required for this project
+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.
+</P>
+<P>
+The <Q><TT>src/examples</TT></Q> directory contains a few sample user
+programs.  The <Q><TT>Makefile</TT></Q> in this directory
+compiles the provided examples, and you can edit it
+compile your own programs as well.  Some of the example programs will
+not work with the current implementation of Pintos.
+</P>
+<P>
+Pintos can load <EM>ELF</EM> executables with the loader provided for you
+in <Q><TT>userprog/process.c</TT></Q>.  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</VAR>86 ELF executables to produce programs
+for Pintos.  (We've provided compilers and linkers that should do just
+fine.)
+</P>
+<P>
+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 <Q><TT>filesys.dsk</TT></Q> beyond a useful state,
+which may happen occasionally while debugging.
+</P>
+<P>
+<A NAME="Virtual Memory Layout"></A>
+<HR SIZE="6">
+<A NAME="SEC26"></A>
+<H3> 2.2.4 Virtual Memory Layout </H3>
+<!--docid::SEC26::-->
+<P>
+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</CODE>, which is defined in
+<Q><TT>threads/vaddr.h</TT></Q> and defaults to <TT>0xc0000000</TT> (3 GB).  Kernel
+virtual memory occupies the rest of the virtual address space, from
+<CODE>PHYS_BASE</CODE> up to 4 GB.
+</P>
+<P>
+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 <CODE>pagedir_activate()</CODE> in
+<Q><TT>userprog/pagedir.c</TT></Q>).  <CODE>struct thread</CODE> contains a pointer to a
+process's page table.
+</P>
+<P>
+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</CODE>.  That is, virtual address
+<CODE>PHYS_BASE</CODE> accesses physical
+address 0, virtual address <CODE>PHYS_BASE</CODE> + <TT>0x1234</TT> accesses
+physical address <TT>0x1234</TT>, and so on up to the size of the machine's
+physical memory.
+</P>
+<P>
+A user program can only access its own user virtual memory.  An attempt to
+access kernel virtual memory causes a page fault, handled by
+<CODE>page_fault()</CODE> in <Q><TT>userprog/exception.c</TT></Q>, 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.
+</P>
+<P>
+<A NAME="Typical Memory Layout"></A>
+<HR SIZE="6">
+<A NAME="SEC27"></A>
+<H4> 2.2.4.1 Typical Memory Layout </H4>
+<!--docid::SEC27::-->
+<P>
+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:
+</P>
+<P>
+<CENTER>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>   PHYS_BASE +----------------------------------+
+             |            user stack            |
+             |                 |                |
+             |                 |                |
+             |                 V                |
+             |          grows downward          |
+             |                                  |
+             |                                  |
+             |                                  |
+             |                                  |
+             |           grows upward           |
+             |                 ^                |
+             |                 |                |
+             |                 |                |
+             +----------------------------------+
+             | uninitialized data segment (BSS) |
+             +----------------------------------+
+             |     initialized data segment     |
+             +----------------------------------+
+             |           code segment           |
+  0x08048000 +----------------------------------+
+             |                                  |
+             |                                  |
+             |                                  |
+             |                                  |
+             |                                  |
+           0 +----------------------------------+
+</pre></td></tr></table></CENTER>
+<P>
+In this project, the user stack is fixed in size, but in project 2 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.
+</P>
+<P>
+The code segment in Pintos starts at user virtual address
+<TT>0x08084000</TT>, approximately 128 MB from the bottom of the address
+space.  This value is specified in [ <A HREF="pintos_10.html#SysV-i386">SysV-i386</A>] and has no deep
+significance.
+</P>
+<P>
+The linker sets the layout of a user program in memory, as directed by a
+&quot;linker script&quot; that tells it the names and locations of the various
+program segments.  You can learn more about linker scripts by reading
+the &quot;Scripts&quot; chapter in the linker manual, accessible via <Q><SAMP>info
+ld</SAMP></Q>.
+</P>
+<P>
+To view the layout of a particular executable, run <CODE>objdump</CODE>
+(80<VAR>x</VAR>86) or <CODE>i386-elf-objdump</CODE> (SPARC) with the <Q><SAMP>-p</SAMP></Q>
+option.
+</P>
+<P>
+<A NAME="Accessing User Memory"></A>
+<HR SIZE="6">
+<A NAME="SEC28"></A>
+<H3> 2.2.5 Accessing User Memory </H3>
+<!--docid::SEC28::-->
+<P>
+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</CODE>).  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.
+</P>
+<P>
+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. 
+The second method is to check only that a user
+pointer points below <CODE>PHYS_BASE</CODE>, then dereference it.
+An invalid user pointer will cause a &quot;page fault&quot; that you can
+handle by modifying the code for <CODE>page_fault()</CODE> in
+<Q><TT>userprog/exception.c</TT></Q>.  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). It is also the way
+access to user pointers is implemented in the Pintos version provided.
+</P>
+<P>
+In either case, one needs to make sure not to &quot;leak&quot; resources.  For
+example, suppose that your system call has acquired a lock or
+allocated memory with <CODE>malloc()</CODE>.  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.
+</P>
+<P>
+<A NAME="Project 0 Requirements"></A>
+<HR SIZE="6">
+<A NAME="SEC29"></A>
+<H2> 2.3 Requirements </H2>
+<!--docid::SEC29::-->
+<P>
+<A NAME="Project 0 Design Document"></A>
+<HR SIZE="6">
+<A NAME="SEC30"></A>
+<H3> 2.3.1 Design Document </H3>
+<!--docid::SEC30::-->
+<P>
+Before you turn in your project, you must copy <A HREF="start.tmpl">the
+project 0 design document template</A> into your source tree under the name
+<Q><TT>pintos/src/intro/DESIGNDOC</TT></Q> and fill it in.  We recommend that
+you read the design document template before you start working on the
+project.  See section <A HREF="pintos_7.html#SEC93">C. Project Documentation</A>, for a sample design document
+that goes along with a fictitious project.
+</P>
+<P>
+<A NAME="Alarm Clock"></A>
+<HR SIZE="6">
+<A NAME="SEC31"></A>
+<H3> 2.3.2 Alarm Clock </H3>
+<!--docid::SEC31::-->
+<P>
+Reimplement <CODE>timer_sleep()</CODE>, defined in <Q><TT>devices/timer.c</TT></Q>.
+Although a working implementation is provided, it &quot;busy waits,&quot; that
+is, it spins in a loop checking the current time and calling
+<CODE>thread_yield()</CODE> until enough time has gone by.  Reimplement it to
+avoid busy waiting.
+</P>
+<P>
+<A NAME="IDX1"></A>
+</P>
+<DL>
+<DT><U>Function:</U> void <B>timer_sleep</B> (int64_t <VAR>ticks</VAR>)
+<DD>Suspends execution of the calling thread until time has advanced by at
+least <VAR>x</VAR> timer ticks.  Unless the system is otherwise idle, the
+thread need not wake up after exactly <VAR>x</VAR> ticks.  Just put it on
+the ready queue after they have waited for the right amount of time.
+<P>
+<CODE>timer_sleep()</CODE> is useful for threads that operate in real-time,
+e.g. for blinking the cursor once per second.
+</P>
+<P>
+The argument to <CODE>timer_sleep()</CODE> is expressed in timer ticks, not in
+milliseconds or any another unit.  There are <CODE>TIMER_FREQ</CODE> timer
+ticks per second, where <CODE>TIMER_FREQ</CODE> is a macro defined in
+<CODE>devices/timer.h</CODE>.  The default value is 100.  We don't recommend
+changing this value, because any change is likely to cause many of
+the tests to fail.
+</P>
+</DL>
+<P>
+Separate functions <CODE>timer_msleep()</CODE>, <CODE>timer_usleep()</CODE>, and
+<CODE>timer_nsleep()</CODE> do exist for sleeping a specific number of
+milliseconds, microseconds, or nanoseconds, respectively, but these will
+call <CODE>timer_sleep()</CODE> automatically when necessary.  You do not need
+to modify them.
+</P>
+<P>
+If your delays seem too short or too long, reread the explanation of the
+<Q><SAMP>-r</SAMP></Q> option to <CODE>pintos</CODE> (see section <A HREF="pintos_1.html#SEC6">1.1.4 Debugging versus Testing</A>).
+</P>
+<P>
+The tests for the <A HREF="pintos_2.html#SEC31">2.3.2 Alarm Clock</A> assignment are executed by changing the
+working directory <Q><TT>intro</TT></Q>. The run <Q><SAMP>make</SAMP></Q> to build the
+Pintos kernel. Finally run <Q><SAMP>make check</SAMP></Q> to run the tests,
+followed by <Q><SAMP>make grade</SAMP></Q> to obtain your score.
+</P>
+<P>
+The alarm clock implementation is not needed for later projects.
+</P>
+<P>
+<A NAME="Argument Passing"></A>
+<HR SIZE="6">
+<A NAME="SEC32"></A>
+<H3> 2.3.3 Argument Passing </H3>
+<!--docid::SEC32::-->
+<P>
+Currently, <CODE>process_execute()</CODE> does not support passing arguments to
+new processes.  Implement this functionality, by extending
+<CODE>process_execute()</CODE> 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, <CODE>process_execute(&quot;grep foo bar&quot;)</CODE> should run
+<CODE>grep</CODE> passing two arguments <CODE>foo</CODE> and <CODE>bar</CODE>.
+</P>
+<P>
+Within a command line, multiple spaces are equivalent to a single
+space, so that <CODE>process_execute(&quot;grep  foo   bar&quot;)</CODE>
+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 unrelated limit of 128 bytes on command-line
+arguments that the <CODE>pintos</CODE> utility can pass to the kernel.)
+</P>
+<P>
+You can parse argument strings any way you like.  If you're lost,
+look at <CODE>strtok_r()</CODE>, prototyped in <Q><TT>lib/string.h</TT></Q> and
+implemented with thorough comments in <Q><TT>lib/string.c</TT></Q>.  You can
+find more about it by looking at the man page (run <CODE>man strtok_r</CODE>
+at the prompt).
+</P>
+<P>
+See section <A HREF="pintos_2.html#SEC39">2.5.1 Program Startup Details</A>, for information on exactly how you
+need to set up the stack.
+</P>
+<P>
+<A NAME="Project 0 FAQ"></A>
+<HR SIZE="6">
+<A NAME="SEC33"></A>
+<H2> 2.4 FAQ </H2>
+<!--docid::SEC33::-->
+<P>
+</P>
+<DL COMPACT>
+<DT><B>How much code will I need to write?</B>
+<DD><P>
+Here's a summary of our reference solution, produced by the
+<CODE>diffstat</CODE> program.  The final row gives total lines inserted
+and deleted; a changed line counts as both an insertion and a deletion.
+</P>
+<P>
+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.
+</P>
+<P>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre> devices/timer.c    |   40 +++++++++++-
+ threads/thread.h   |    3 +
+ userprog/process.c |  148 ++++++++++++++++++++++++++++++-----------
+ 3 files changed, 150 insertions(+), 41 deletions(-)
+</pre></td></tr></table></DL>
+<P>
+<A NAME="Threads FAQ"></A>
+<HR SIZE="6">
+<A NAME="SEC34"></A>
+<H3> 2.4.1 Threads FAQ </H3>
+<!--docid::SEC34::-->
+<P>
+</P>
+<DL COMPACT>
+<DT><B>How do I update the <Q><TT>Makefile</TT></Q>s when I add a new source file?</B>
+<DD><P>
+<A NAME="Adding Source Files"></A>
+To add a <Q><TT>.c</TT></Q> file, edit the top-level <Q><TT>Makefile.build</TT></Q>.
+Add the new file to variable <Q><SAMP><VAR>dir</VAR>_SRC</SAMP></Q>, where
+<VAR>dir</VAR> is the directory where you added the file.  For this
+project, that means you should add it to <CODE>threads_SRC</CODE> or
+<CODE>devices_SRC</CODE>.  Then run <CODE>make</CODE>.  If your new file
+doesn't get
+compiled, run <CODE>make clean</CODE> and then try again.
+</P>
+<P>
+When you modify the top-level <Q><TT>Makefile.build</TT></Q> and re-run
+<CODE>make</CODE>, the modified
+version should be automatically copied to
+<Q><TT>threads/build/Makefile</TT></Q>.  The converse is
+not true, so any changes will be lost the next time you run <CODE>make
+clean</CODE> from the <Q><TT>threads</TT></Q> directory.  Unless your changes are
+truly temporary, you should prefer to edit <Q><TT>Makefile.build</TT></Q>.
+</P>
+<P>
+A new <Q><TT>.h</TT></Q> file does not require editing the <Q><TT>Makefile</TT></Q>s.
+</P>
+<P>
+</P>
+<DT><B>What does <CODE>warning: no previous prototype for `<VAR>func</VAR>'</CODE> mean?</B>
+<DD><P>
+It means that you defined a non-<CODE>static</CODE> function without
+preceding it by a prototype.  Because non-<CODE>static</CODE> functions are
+intended for use by other <Q><TT>.c</TT></Q> files, for safety they should be
+prototyped in a header file included before their definition.  To fix
+the problem, add a prototype in a header file that you include, or, if
+the function isn't actually used by other <Q><TT>.c</TT></Q> files, make it
+<CODE>static</CODE>.
+</P>
+<P>
+</P>
+<DT><B>What is the interval between timer interrupts?</B>
+<DD><P>
+Timer interrupts occur <CODE>TIMER_FREQ</CODE> times per second.  You can
+adjust this value by editing <Q><TT>devices/timer.h</TT></Q>.  The default is
+100 Hz.
+</P>
+<P>
+We don't recommend changing this value, because any changes are likely
+to cause many of the tests to fail.
+</P>
+<P>
+</P>
+<DT><B>How long is a time slice?</B>
+<DD><P>
+There are <CODE>TIME_SLICE</CODE> ticks per time slice.  This macro is
+declared in <Q><TT>threads/thread.c</TT></Q>.  The default is 4 ticks.
+</P>
+<P>
+We don't recommend changing this value, because any changes are likely
+to cause many of the tests to fail.
+</P>
+<P>
+</P>
+<DT><B>How do I run the tests?</B>
+<DD><P>
+See section <A HREF="pintos_1.html#SEC8">1.2.1 Testing</A>.
+</P>
+<P>
+See section <A HREF="pintos_8.html#SEC100">D.4 Backtraces</A>, for more information.
+</DL>
+<P>
+<A NAME="Alarm Clock FAQ"></A>
+<HR SIZE="6">
+<A NAME="SEC35"></A>
+<H3> 2.4.2 Alarm Clock FAQ </H3>
+<!--docid::SEC35::-->
+<P>
+</P>
+<DL COMPACT>
+<DT><B>Do I need to account for timer values overflowing?</B>
+<DD><P>
+Don't worry about the possibility of timer values overflowing.  Timer
+values are expressed as signed 64-bit numbers, which at 100 ticks per
+second should be good for almost 2,924,712,087 years.  By then, we
+expect Pintos to have been phased out of the curriculum.
+</DL>
+<P>
+<A NAME="Userprog FAQ"></A>
+<HR SIZE="6">
+<A NAME="SEC36"></A>
+<H3> 2.4.3 Userprog FAQ </H3>
+<!--docid::SEC36::-->
+<P>
+</P>
+<DL COMPACT>
+<DT><B>The kernel always panics when I run <CODE>pintos -p <VAR>file</VAR> -- -q</CODE>.</B>
+<DD><P>
+Did you format the file system (with <Q><SAMP>pintos -f</SAMP></Q>)?
+</P>
+<P>
+Is your file name too long?  The file system limits file names to 14
+characters.  A command like <Q><SAMP>pintos -p ../../examples/echo -- -q</SAMP></Q>
+will exceed the limit.  Use <Q><SAMP>pintos -p ../../examples/echo -a echo
+-- -q</SAMP></Q> to put the file under the name <Q><TT>echo</TT></Q> instead.
+</P>
+<P>
+Is the file system full?
+</P>
+<P>
+Does the file system already contain 16 files?  The base Pintos file
+system has a 16-file limit.
+</P>
+<P>
+The file system may be so fragmented that there's not enough contiguous
+space for your file.
+</P>
+<P>
+</P>
+<DT><B>When I run <CODE>pintos -p ../file --</CODE>, <Q><TT>file</TT></Q> isn't copied.</B>
+<DD><P>
+Files are written under the name you refer to them, by default, so in
+this case the file copied in would be named <Q><TT>../file</TT></Q>.  You
+probably want to run <CODE>pintos -p ../file -a file --</CODE> instead.
+</P>
+<P>
+You can list the files in your file system with <CODE>pintos -q ls</CODE>.
+</P>
+<P>
+</P>
+<DT><B>All my user programs die with page faults.</B>
+<DD><P>
+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</VAR> and <VAR>argv</VAR> off the stack.  If the stack
+isn't properly set up, this causes a page fault.
+</P>
+<P>
+</P>
+<DT><B>How can I disassemble user programs?</B>
+<DD><P>
+The <CODE>objdump</CODE> (80<VAR>x</VAR>86) or <CODE>i386-elf-objdump</CODE>
+(SPARC) utility can disassemble entire user
+programs or object files.  Invoke it as <CODE>objdump -d
+<VAR>file</VAR></CODE>.  You can use GDB's
+<CODE>disassemble</CODE> command to disassemble individual functions
+(see section <A HREF="pintos_8.html#SEC102">D.5 GDB</A>).
+</P>
+<P>
+</P>
+<DT><B>Why do many C include files not work in Pintos programs?</B>
+<DD><DT><B>Can I use lib<VAR>foo</VAR> in my Pintos programs?</B>
+<DD><P>
+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.)
+</P>
+<P>
+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 <CODE>malloc()</CODE> implementation.
+</P>
+<P>
+</P>
+<DT><B>How do I compile new user programs?</B>
+<DD><P>
+Modify <Q><TT>src/examples/Makefile</TT></Q>, then run <CODE>make</CODE>.
+</P>
+<P>
+</P>
+<DT><B>Can I run user programs under a debugger?</B>
+<DD><P>
+Yes, with some limitations.  See section <A HREF="pintos_8.html#SEC102">D.5 GDB</A>.
+</P>
+<P>
+</P>
+<DT><B>How can I run user programs that need more than 4 kB stack space?</B>
+<DD><P>
+You may modify the stack setup code to allocate more than one page of
+stack space for each process.  In project 2, you will implement a better
+solution.
+</P>
+<P>
+</P>
+<DT><B>What happens when an open file is removed?</B>
+<DD><A NAME="Removing an Open File"></A>
+<P>
+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.
+</P>
+<P>
+</DL>
+<P>
+<A NAME="Argument Passing FAQ"></A>
+<HR SIZE="6">
+<A NAME="SEC37"></A>
+<H3> 2.4.4 Argument Passing FAQ </H3>
+<!--docid::SEC37::-->
+<P>
+</P>
+<DL COMPACT>
+<DT><B>Isn't the top of stack in kernel virtual memory?</B>
+<DD><P>
+The top of stack is at <CODE>PHYS_BASE</CODE>, typically <TT>0xc0000000</TT>, 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 <TT>0xbffffffc</TT>.
+</P>
+<P>
+</P>
+<DT><B>Is <CODE>PHYS_BASE</CODE> fixed?</B>
+<DD><P>
+No.  You should be able to support <CODE>PHYS_BASE</CODE> values that are
+any multiple of <TT>0x10000000</TT> from <TT>0x80000000</TT> to <TT>0xf0000000</TT>,
+simply via recompilation.
+</DL>
+<P>
+<A NAME="80x86 Calling Convention"></A>
+<HR SIZE="6">
+<A NAME="SEC38"></A>
+<H2> 2.5 80<VAR>x</VAR>86 Calling Convention </H2>
+<!--docid::SEC38::-->
+<P>
+This section summarizes important points of the convention used for
+normal function calls on 32-bit 80<VAR>x</VAR>86 implementations of Unix.
+Some details are omitted for brevity.  If you do want all the details,
+refer to [ <A HREF="pintos_10.html#SysV-i386">SysV-i386</A>].
+</P>
+<P>
+The calling convention works like this:
+</P>
+<P>
+<OL>
+<LI>
+The caller pushes each of the function's arguments on the stack one by
+one, normally using the <CODE>PUSH</CODE> assembly language instruction.
+Arguments are pushed in right-to-left order.
+<P>
+The stack grows downward: each push decrements the stack pointer, then
+stores into the location it now points to, like the C expression
+<Q><SAMP>*--sp = <VAR>value</VAR></SAMP></Q>.
+</P>
+<P>
+</P>
+<LI>
+The caller pushes the address of its next instruction (the <EM>return
+address</EM>) on the stack and jumps to the first instruction of the callee.
+A single 80<VAR>x</VAR>86 instruction, <CODE>CALL</CODE>, does both.
+<P>
+</P>
+<LI>
+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.
+<P>
+</P>
+<LI>
+If the callee has a return value, it stores it into register <CODE>EAX</CODE>.
+<P>
+</P>
+<LI>
+The callee returns by popping the return address from the stack and
+jumping to the location it specifies, using the 80<VAR>x</VAR>86 <CODE>RET</CODE>
+instruction.
+<P>
+</P>
+<LI>
+The caller pops the arguments off the stack.
+</OL>
+<P>
+Consider a function <CODE>f()</CODE> that takes three <CODE>int</CODE> arguments.
+This diagram shows a sample stack frame as seen by the callee at the
+beginning of step 3 above, supposing that <CODE>f()</CODE> is invoked as
+<CODE>f(1, 2, 3)</CODE>.  The initial stack address is arbitrary:
+</P>
+<P>
+<CENTER>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>                             +----------------+
+                  0xbffffe7c |        3       |
+                  0xbffffe78 |        2       |
+                  0xbffffe74 |        1       |
+stack pointer --&gt; 0xbffffe70 | return address |
+                             +----------------+
+</pre></td></tr></table></CENTER>
+<P>
+<A NAME="Program Startup Details"></A>
+<HR SIZE="6">
+<A NAME="SEC39"></A>
+<H3> 2.5.1 Program Startup Details </H3>
+<!--docid::SEC39::-->
+<P>
+The Pintos C library for user programs designates <CODE>_start()</CODE>, in
+<Q><TT>lib/user/entry.c</TT></Q>, as the entry point for user programs.  This
+function is a wrapper around <CODE>main()</CODE> that calls <CODE>exit()</CODE> if
+<CODE>main()</CODE> returns:
+</P>
+<P>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>void
+_start (int argc, char *argv[])
+{
+  exit (main (argc, argv));
+}
+</pre></td></tr></table><P>
+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 (see section <A HREF="pintos_2.html#SEC38">2.5 80<VAR>x</VAR>86 Calling Convention</A>).
+</P>
+<P>
+Consider how to handle arguments for the following example command:
+<Q><SAMP>/bin/ls -l foo bar</SAMP></Q>.
+First, break the command into words: <Q><SAMP>/bin/ls</SAMP></Q>,
+<Q><SAMP>-l</SAMP></Q>, <Q><SAMP>foo</SAMP></Q>, <Q><SAMP>bar</SAMP></Q>.  Place the words at the top of the
+stack.  Order doesn't matter, because they will be referenced through
+pointers.
+</P>
+<P>
+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</CODE>.  The null pointer sentinel ensures that <CODE>argv[argc]</CODE>
+is a null pointer, as required by the C standard.  The order ensures
+that <CODE>argv[0]</CODE> 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.
+</P>
+<P>
+Then, push <CODE>argv</CODE> (the address of <CODE>argv[0]</CODE>) and <CODE>argc</CODE>,
+in that order.  Finally, push a fake &quot;return address&quot;: although the
+entry function will never return, its stack frame must have the same
+structure as any other.
+</P>
+<P>
+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</CODE> is <TT>0xc0000000</TT>:
+</P>
+<P>
+<CENTER>
+</P>
+<TABLE>
+<TR><TD>Address </TD><TD> Name </TD><TD> Data </TD><TD> Type</TD>
+</TR>
+<TR><TD><TT>0xbffffffc</TT> </TD><TD> <CODE>argv[3][<small>...</small>]</CODE> </TD><TD> <Q><SAMP>bar\0</SAMP></Q> </TD><TD> <CODE>char[4]</CODE></TD>
+</TR>
+<TR><TD><TT>0xbffffff8</TT> </TD><TD> <CODE>argv[2][<small>...</small>]</CODE> </TD><TD> <Q><SAMP>foo\0</SAMP></Q> </TD><TD> <CODE>char[4]</CODE></TD>
+</TR>
+<TR><TD><TT>0xbffffff5</TT> </TD><TD> <CODE>argv[1][<small>...</small>]</CODE> </TD><TD> <Q><SAMP>-l\0</SAMP></Q> </TD><TD> <CODE>char[3]</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffed</TT> </TD><TD> <CODE>argv[0][<small>...</small>]</CODE> </TD><TD> <Q><SAMP>/bin/ls\0</SAMP></Q> </TD><TD> <CODE>char[8]</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffec</TT> </TD><TD> word-align </TD><TD> 0 </TD><TD> <CODE>uint8_t</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffe8</TT> </TD><TD> <CODE>argv[4]</CODE> </TD><TD> <TT>0</TT> </TD><TD> <CODE>char *</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffe4</TT> </TD><TD> <CODE>argv[3]</CODE> </TD><TD> <TT>0xbffffffc</TT> </TD><TD> <CODE>char *</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffe0</TT> </TD><TD> <CODE>argv[2]</CODE> </TD><TD> <TT>0xbffffff8</TT> </TD><TD> <CODE>char *</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffdc</TT> </TD><TD> <CODE>argv[1]</CODE> </TD><TD> <TT>0xbffffff5</TT> </TD><TD> <CODE>char *</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffd8</TT> </TD><TD> <CODE>argv[0]</CODE> </TD><TD> <TT>0xbfffffed</TT> </TD><TD> <CODE>char *</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffd4</TT> </TD><TD> <CODE>argv</CODE> </TD><TD> <TT>0xbfffffd8</TT> </TD><TD> <CODE>char **</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffd0</TT> </TD><TD> <CODE>argc</CODE> </TD><TD> 4 </TD><TD> <CODE>int</CODE></TD>
+</TR>
+<TR><TD><TT>0xbfffffcc</TT> </TD><TD> return address </TD><TD> 0 </TD><TD> <CODE>void (*) ()</CODE></TD>
+</TR></TABLE>
+</CENTER>
+<P>
+In this example, the stack pointer would be initialized to
+<TT>0xbfffffcc</TT>.
+</P>
+<P>
+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</CODE> (defined in <Q><TT>threads/vaddr.h</TT></Q>).
+</P>
+<P>
+You may find the non-standard <CODE>hex_dump()</CODE> function, declared in
+<Q><TT>&lt;stdio.h&gt;</TT></Q>, useful for debugging your argument passing code.
+Here's what it would show in the above example:
+</P>
+<P>
+<TABLE><tr><td>&nbsp;</td><td class=example><pre>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.|
+</pre></td></tr></table><P>
+<A NAME="System Call Details"></A>
+<HR SIZE="6">
+<A NAME="SEC40"></A>
+<H3> 2.5.2 System Call Details </H3>
+<!--docid::SEC40::-->
+<P>
+We already know one way that the operating system
+can regain control from a user program: interrupts from timers and I/O
+devices.  These are &quot;external&quot; interrupts, because they are caused
+by entities outside the CPU (see section <A HREF="pintos_5.html#SEC68">A.4.3 External Interrupt Handling</A>).
+</P>
+<P>
+The operating system also deals with software exceptions, which are
+events that occur in program code (see section <A HREF="pintos_5.html#SEC67">A.4.2 Internal Interrupt Handling</A>).  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 (&quot;system calls&quot;) from the operating system.
+</P>
+<P>
+In the 80<VAR>x</VAR>86 architecture, the <Q><SAMP>int</SAMP></Q> 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 <Q><SAMP>int $0x30</SAMP></Q> 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 (see section <A HREF="pintos_2.html#SEC38">2.5 80<VAR>x</VAR>86 Calling Convention</A>).
+</P>
+<P>
+Thus, when the system call handler <CODE>syscall_handler()</CODE> 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
+<CODE>syscall_handler()</CODE> as the <Q><SAMP>esp</SAMP></Q> member of the
+<CODE>struct intr_frame</CODE> passed to it.  (<CODE>struct intr_frame</CODE> is on the kernel
+stack.)
+</P>
+<P>
+The 80<VAR>x</VAR>86 convention for function return values is to place them
+in the <CODE>EAX</CODE> register.  System calls that return a value can do
+so by modifying the <Q><SAMP>eax</SAMP></Q> member of <CODE>struct intr_frame</CODE>.
+</P>
+<P>
+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.
+<A NAME="Project 1--Threads"></A>
+<HR SIZE="6">
+<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
+<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_2.html#SEC15"> &lt;&lt; </A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_3.html#SEC41"> &gt;&gt; </A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
+<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
+</TR></TABLE>
+<BR>
+<FONT SIZE="-1">
+This document was generated
+by on <I>March, 6 2012</I>
+using <A HREF="http://texi2html.cvshome.org"><I>texi2html</I></A>
+</FONT>
+</BODY>
+</HTML>