+@node Reference Guide
+@appendix Reference Guide
+
+This chapter is a reference for the Pintos code. It covers the
+entire code base, but you'll only be using Pintos one part at a time,
+so you may find that you want to read each part as you work on the
+project where it becomes important.
+
+(Actually, the reference guide is currently incomplete.)
+
+We recommend using ``tags'' to follow along with references to function
+and variable names (@pxref{Tags}).
+
+@menu
+* Pintos Loading::
+* Threads::
+* Synchronization::
+* Interrupt Handling::
+* Memory Allocation::
+* Virtual Addresses::
+* Page Table::
+* Hash Table::
+@end menu
+
+@node Pintos Loading
+@section Loading
+
+This section covers the Pintos loader and basic kernel
+initialization.
+
+@menu
+* Pintos Loader::
+* Kernel Initialization::
+@end menu
+
+@node Pintos Loader
+@subsection The Loader
+
+The first part of Pintos that runs is the loader, in
+@file{threads/loader.S}. The PC BIOS loads the loader into memory.
+The loader, in turn, is responsible for initializing the CPU, loading
+the rest of Pintos into memory, and then jumping to its start. It's
+not important to understand exactly what the loader does, but if
+you're interested, read on. You should probably read along with the
+loader's source. You should also understand the basics of the
+80@var{x}86 architecture as described by chapter 3, ``Basic Execution
+Environment,'' of @bibref{IA32-v1}.
+
+Because the PC BIOS loads the loader, the loader has to play by the
+BIOS's rules. In particular, the BIOS only loads 512 bytes (one disk
+sector) into memory. This is a severe restriction and it means that,
+practically speaking, the loader has to be written in assembly
+language.
+
+Pintos' loader first initializes the CPU. The first important part of
+this is to enable the A20 line, that is, the CPU's address line
+numbered 20. For historical reasons, PCs start out with this address
+line fixed at 0, which means that attempts to access memory beyond the
+first 1 MB (2 raised to the 20th power) will fail. Pintos wants to
+access more memory than this, so we have to enable it.
+
+Next, the loader asks the BIOS for the PC's memory size. Again for
+historical reasons, the function that we call in the BIOS to do this
+can only detect up to 64 MB of RAM, so that's the practical limit that
+Pintos can support. The memory size is stashed away in a location in
+the loader that the kernel can read after it boots.
+
+Third, the loader creates a basic page table. This page table maps
+the 64 MB at the base of virtual memory (starting at virtual address
+0) directly to the identical physical addresses. It also maps the
+same physical memory starting at virtual address
+@code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB). The
+Pintos kernel only wants the latter mapping, but there's a
+chicken-and-egg problem if we don't include the former: our current
+virtual address is roughly @t{0x7c00}, the location where the BIOS
+loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
+page table, but if we turn on the page table without jumping there,
+then we've just pulled the rug out from under ourselves.
+
+After the page table is initialized, we load the CPU's control
+registers to turn on protected mode and paging, and then we set up the
+segment registers. We aren't equipped to handle interrupts in
+protected mode yet, so we disable interrupts.
+
+Finally it's time to load the kernel from disk. We use a simple but
+inflexible method to do this: we program the IDE disk
+controller directly. We assume that the kernel is stored starting
+from the second sector of the first IDE disk (the first sector normally
+contains the boot loader). We also assume that the BIOS has
+already set up the IDE controller for us. We read
+@code{KERNEL_LOAD_PAGES} pages of data (4 kB per page) from the disk directly
+into virtual memory, starting @code{LOADER_KERN_BASE} bytes past
+@code{LOADER_PHYS_BASE}, which by default means that we load the
+kernel starting 1 MB into physical memory.
+
+Then we jump to the start of the compiled kernel image. Using the
+``linker script'' in @file{threads/kernel.lds.S}, the kernel has
+arranged that it begins with the assembly module
+@file{threads/start.S}. This assembly module just calls
+@func{main}, which never returns.
+
+There's one more trick: the Pintos kernel command line
+is stored in the boot loader. The @command{pintos} program actually
+modifies the boot loader on disk each time it runs the kernel, putting
+in whatever command line arguments the user supplies to the kernel,
+and then the kernel at boot time reads those arguments out of the boot
+loader in memory. This is something of a nasty hack, but it is simple
+and effective.
+
+@node Kernel Initialization
+@subsection Kernel Initialization
+
+The kernel proper starts with the @func{main} function. The
+@func{main} function is written in C, as will be most of the code we
+encounter in Pintos from here on out.
+
+When @func{main} starts, the system is in a pretty raw state. We're
+in protected mode with paging enabled, but hardly anything else is
+ready. Thus, the @func{main} function consists primarily of calls
+into other Pintos modules' initialization functions.
+These are usually named @func{@var{module}_init}, where
+@var{module} is the module's name, @file{@var{module}.c} is the
+module's source code, and @file{@var{module}.h} is the module's
+header.
+
+First we initialize kernel RAM in @func{ram_init}. The first step
+is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
+segment that should be initialized to all zeros. In most C
+implementations, whenever you
+declare a variable outside a function without providing an
+initializer, that variable goes into the BSS. Because it's all zeros, the
+BSS isn't stored in the image that the loader brought into memory. We
+just use @func{memset} to zero it out. The other task of
+@func{ram_init} is to read out the machine's memory size from where
+the loader stored it and put it into the @code{ram_pages} variable for
+later use.
+
+Next, @func{thread_init} initializes the thread system. We will defer
+full discussion to our discussion of Pintos threads below. It is
+called so early in initialization because the console, initialized
+just afterward, tries to use locks, and locks in turn require there to be a
+running thread.
+
+Then we initialize the console so that we can use @func{printf}.
+@func{main} calls @func{vga_init}, which initializes the VGA text
+display and clears the screen. It also calls @func{serial_init_poll}
+to initialize the first serial port in ``polling mode,'' that is,
+where the kernel busy-waits for the port to be ready for each
+character to be output. (We use polling mode until we're ready to set
+up interrupts later.) Finally we initialize the console device and
+print a startup message to the console.
+
+@func{main} calls @func{read_command_line} to break the kernel command
+line into arguments, then @func{parse_options} to read any options at
+the beginning of the command line. (Executing actions specified on the
+command line happens later.)
+
+The next block of functions we call initialize the kernel's memory
+system. @func{palloc_init} sets up the kernel page allocator, which
+doles out memory one or more pages at a time. @func{malloc_init} sets
+up the allocator that handles odd-sized allocations.
+@func{paging_init} sets up a page table for the kernel.
+
+In projects 2 and later, @func{main} also calls @func{tss_init} and
+@func{gdt_init}, but we'll talk about those later.
+
+@func{main} calls @func{random_init} to initialize the kernel random
+number generator. If the user specified @option{-rs} on the
+@command{pintos} command line, @func{parse_options} has already done
+this, but calling it a second time is harmless and has no effect.
+
+We initialize the interrupt system in the next set of calls.
+@func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
+(IDT) to ready it for interrupt handling (@pxref{Interrupt
+Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
+handling timer interrupts and keyboard interrupts, respectively. In
+projects 2 and later, we also prepare to handle interrupts caused by
+user programs using @func{exception_init} and @func{syscall_init}.
+
+Now that interrupts are set up, we can start preemptively scheduling
+threads with @func{thread_start}, which also enables interrupts.
+With interrupts enabled, interrupt-driven serial port I/O becomes
+possible, so we use
+@func{serial_init_queue} to switch to that mode. Finally,
+@func{timer_calibrate} calibrates the timer for accurate short delays.
+
+If the file system is compiled in, as it will starting in project 2, we
+now initialize the disks with @func{disk_init}, then the
+file system with @func{filesys_init}.
+
+Boot is complete, so we print a message.
+
+Function @func{run_actions} now parses and executes actions specified on
+the kernel command line, such as @command{run} to run a test (in project
+1) or a user program (in later projects).
+
+Finally, if @option{-q} was specified on the kernel command line, we
+call @func{power_off} to terminate the machine simulator. Otherwise,
+@func{main} calls @func{thread_exit}, which allows any other running
+threads to continue running.
+
+@node Threads
+@section Threads
+
+@menu
+* struct thread::
+* Thread Functions::
+* Thread Switching::
+@end menu
+
+@node struct thread
+@subsection @code{struct thread}
+
+The main Pintos data structure for threads is @struct{thread},
+declared in @file{threads/thread.h}.
+
+@deftp {Structure} {struct thread}
+Represents a thread or a user process. In the projects, you will have
+to add your own members to @struct{thread}. You may also change or
+delete the definitions of existing members.
+
+Every @struct{thread} occupies the beginning of its own page of
+memory. The rest of the page is used for the thread's stack, which
+grows downward from the end of the page. It looks like this:
+
+@example
+@group
+ 4 kB +---------------------------------+
+ | kernel stack |
+ | | |
+ | | |
+ | V |
+ | grows downward |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ +---------------------------------+
+ | magic |
+ | : |
+ | : |
+ | status |
+ | tid |
+ 0 kB +---------------------------------+
+@end group
+@end example
+
+This has two consequences. First, @struct{thread} must not be allowed
+to grow too big. If it does, then there will not be enough room for the
+kernel stack. The base @struct{thread} is only a few bytes in size. It
+probably should stay well under 1 kB.
+
+Second, kernel stacks must not be allowed to grow too large. If a stack
+overflows, it will corrupt the thread state. Thus, kernel functions
+should not allocate large structures or arrays as non-static local
+variables. Use dynamic allocation with @func{malloc} or
+@func{palloc_get_page} instead (@pxref{Memory Allocation}).
+@end deftp
+
+@deftypecv {Member} {@struct{thread}} {tid_t} tid
+The thread's thread identifier or @dfn{tid}. Every thread must have a
+tid that is unique over the entire lifetime of the kernel. By
+default, @code{tid_t} is a @code{typedef} for @code{int} and each new
+thread receives the numerically next higher tid, starting from 1 for
+the initial process. You can change the type and the numbering scheme
+if you like.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {enum thread_status} status
+The thread's state, one of the following:
+
+@defvr {Thread State} @code{THREAD_RUNNING}
+The thread is running. Exactly one thread is running at a given time.
+@func{thread_current} returns the running thread.
+@end defvr
+
+@defvr {Thread State} @code{THREAD_READY}
+The thread is ready to run, but it's not running right now. The
+thread could be selected to run the next time the scheduler is
+invoked. Ready threads are kept in a doubly linked list called
+@code{ready_list}.
+@end defvr
+
+@defvr {Thread State} @code{THREAD_BLOCKED}
+The thread is waiting for something, e.g.@: a lock to become
+available, an interrupt to be invoked. The thread won't be scheduled
+again until it transitions to the @code{THREAD_READY} state with a
+call to @func{thread_unblock}.
+@end defvr
+
+@defvr {Thread State} @code{THREAD_DYING}
+The thread will be destroyed by the scheduler after switching to the
+next thread.
+@end defvr
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {char} name[16]
+The thread's name as a string, or at least the first few characters of
+it.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {uint8_t *} stack
+Every thread has its own stack to keep track of its state. When the
+thread is running, the CPU's stack pointer register tracks the top of
+the stack and this member is unused. But when the CPU switches to
+another thread, this member saves the thread's stack pointer. No
+other members are needed to save the thread's registers, because the
+other registers that must be saved are saved on the stack.
+
+When an interrupt occurs, whether in the kernel or a user program, an
+@struct{intr_frame} is pushed onto the stack. When the interrupt occurs
+in a user program, the @struct{intr_frame} is always at the very top of
+the page. @xref{Interrupt Handling}, for more information.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {int} priority
+A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
+(63). Lower numbers correspond to lower priorities, so that
+priority 0 is the lowest priority and priority 63 is the highest.
+Pintos as provided ignores thread priorities, but you will implement
+priority scheduling in project 1 (@pxref{Priority Scheduling}).
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
+A ``list element'' used to put the thread into doubly linked lists,
+either the list of threads ready to run or a list of threads waiting
+on a semaphore. Take a look at @file{lib/kernel/list.h} for
+information on how to use Pintos doubly linked lists.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
+Only present in project 2 and later.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {unsigned} magic
+Always set to @code{THREAD_MAGIC}, which is just a random number defined
+in @file{threads/thread.c}, and used to detect stack overflow.
+@func{thread_current} checks that the @code{magic} member of the running
+thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
+will normally change this value, triggering the assertion. For greatest
+benefit, as you add members to @struct{thread}, leave @code{magic} as
+the final member.
+@end deftypecv
+
+@node Thread Functions
+@subsection Thread Functions
+
+@file{threads/thread.c} implements several public functions for thread
+support. Let's take a look at the most useful:
+
+@deftypefun void thread_init (void)
+Called by @func{main} to initialize the thread system. Its main
+purpose is to create a @struct{thread} for Pintos's initial thread.
+This is possible because the Pintos loader puts the initial
+thread's stack at the top of a page, in the same position as any other
+Pintos thread.
+
+Before @func{thread_init} runs,
+@func{thread_current} will fail because the running thread's
+@code{magic} value is incorrect. Lots of functions call
+@func{thread_current} directly or indirectly, including
+@func{lock_acquire} for locking a lock, so @func{thread_init} is
+called early in Pintos initialization.
+@end deftypefun
+
+@deftypefun void thread_start (void)
+Called by @func{main} to start the scheduler. Creates the idle
+thread, that is, the thread that is scheduled when no other thread is
+ready. Then enables interrupts, which as a side effect enables the
+scheduler because the scheduler runs on return from the timer interrupt, using
+@func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
+@end deftypefun
+
+@deftypefun void thread_tick (void)
+Called by the timer interrupt at each timer tick. It keeps track of
+thread statistics and triggers the scheduler when a time slice expires.
+@end deftypefun
+
+@deftypefun void thread_print_stats (void)
+Called during Pintos shutdown to print thread statistics.
+@end deftypefun
+
+@deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
+Creates and starts a new thread named @var{name} with the given
+@var{priority}, returning the new thread's tid. The thread executes
+@var{func}, passing @var{aux} as the function's single argument.
+
+@func{thread_create} allocates a page for the thread's
+@struct{thread} and stack and initializes its members, then it sets
+up a set of fake stack frames for it (more about this
+later). The thread is initialized in the blocked state, so the final
+action before returning is to unblock it, which allows the new thread to
+be scheduled.
+@end deftypefun
+
+@deftp {Type} {void thread_func (void *@var{aux})}
+This is the type of a thread function. Its @var{aux} argument is the
+value passed to @func{thread_create}.
+@end deftp
+
+@deftypefun void thread_block (void)
+Transitions the running thread from the running state to the blocked
+state. The thread will not run again until @func{thread_unblock} is
+called on it, so you'd better have some way arranged for that to happen.
+Because @func{thread_block} is so low-level, you should prefer to use
+one of the synchronization primitives instead (@pxref{Synchronization}).
+@end deftypefun
+
+@deftypefun void thread_unblock (struct thread *@var{thread})
+Transitions @var{thread}, which must be in the blocked state, to the
+ready state, allowing it to resume running. This is called when the
+event that the thread is waiting for occurs, e.g.@: when the lock that
+the thread is waiting on becomes available.
+@end deftypefun
+
+@deftypefun {struct thread *} thread_current (void)
+Returns the running thread.
+@end deftypefun
+
+@deftypefun {tid_t} thread_tid (void)
+Returns the running thread's thread id. Equivalent to
+@code{thread_current ()->tid}.
+@end deftypefun
+
+@deftypefun {const char *} thread_name (void)
+Returns the running thread's name. Equivalent to @code{thread_current
+()->name}.
+@end deftypefun
+
+@deftypefun void thread_exit (void) @code{NO_RETURN}
+Causes the current thread to exit. Never returns, hence
+@code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
+@end deftypefun
+
+@deftypefun void thread_yield (void)
+Yields the CPU to the scheduler, which picks a new thread to run. The
+new thread might be the current thread, so you can't depend on this
+function to keep this thread from running for any particular length of
+time.
+@end deftypefun
+
+@deftypefun int thread_get_priority (void)
+@deftypefunx void thread_set_priority (int @var{new_priority})
+Skeleton to set and get thread priority. @xref{Priority Scheduling}.
+@end deftypefun
+
+@deftypefun int thread_get_nice (void)
+@deftypefunx void thread_set_nice (int @var{new_nice})
+@deftypefunx int thread_get_recent_cpu (void)
+@deftypefunx int thread_get_load_avg (void)
+Skeletons for the advanced scheduler. @xref{4.4BSD Scheduler}.
+@end deftypefun
+
+@node Thread Switching
+@subsection Thread Switching
+
+@func{schedule} is the function responsible for switching threads. It
+is internal to @file{threads/thread.c} and called only by the three
+public thread functions that need to switch threads:
+@func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
+Before any of these functions call @func{schedule}, they disable
+interrupts (or ensure that they are already disabled) and then change
+the running thread's state to something other than running.
+
+@func{schedule} is simple but tricky. It records the
+current thread in local variable @var{cur}, determines the next thread
+to run as local variable @var{next} (by calling
+@func{next_thread_to_run}), and then calls @func{switch_threads} to do
+the actual thread switch. The thread we switched to was also running
+inside @func{switch_threads}, as are all the threads not currently
+running, so the new thread now returns out of
+@func{switch_threads}, returning the previously running thread.
+
+@func{switch_threads} is an assembly language routine in
+@file{threads/switch.S}. It saves registers on the stack, saves the
+CPU's current stack pointer in the current @struct{thread}'s @code{stack}
+member, restores the new thread's @code{stack} into the CPU's stack
+pointer, restores registers from the stack, and returns.
+
+The rest of the scheduler is implemented as @func{schedule_tail}. It
+marks the new thread as running. If the thread we just switched from
+is in the dying state, then it also frees the page that contained the
+dying thread's @struct{thread} and stack. These couldn't be freed
+prior to the thread switch because the switch needed to use it.
+
+Running a thread for the first time is a special case. When
+@func{thread_create} creates a new thread, it goes through a fair
+amount of trouble to get it started properly. In particular, a new
+thread hasn't started running yet, so there's no way for it to be
+running inside @func{switch_threads} as the scheduler expects. To
+solve the problem, @func{thread_create} creates some fake stack frames
+in the new thread's stack:
+
+@itemize @bullet
+@item
+The topmost fake stack frame is for @func{switch_threads}, represented
+by @struct{switch_threads_frame}. The important part of this frame is
+its @code{eip} member, the return address. We point @code{eip} to
+@func{switch_entry}, indicating it to be the function that called
+@func{switch_entry}.
+
+@item
+The next fake stack frame is for @func{switch_entry}, an assembly
+language routine in @file{threads/switch.S} that adjusts the stack
+pointer,@footnote{This is because @func{switch_threads} takes
+arguments on the stack and the 80@var{x}86 SVR4 calling convention
+requires the caller, not the called function, to remove them when the
+call is complete. See @bibref{SysV-i386} chapter 3 for details.}
+calls @func{schedule_tail} (this special case is why
+@func{schedule_tail} is separate from @func{schedule}), and returns.
+We fill in its stack frame so that it returns into
+@func{kernel_thread}, a function in @file{threads/thread.c}.
+
+@item
+The final stack frame is for @func{kernel_thread}, which enables
+interrupts and calls the thread's function (the function passed to
+@func{thread_create}). If the thread's function returns, it calls
+@func{thread_exit} to terminate the thread.
+@end itemize
+
+@node Synchronization
+@section Synchronization
+
+If sharing of resources between threads is not handled in a careful,
+controlled fashion, then the result is usually a big mess.
+This is especially the case in operating system kernels, where
+faulty sharing can crash the entire machine. Pintos provides several
+synchronization primitives to help out.
+
+@menu
+* Disabling Interrupts::
+* Semaphores::
+* Locks::
+* Condition Variables::
+* Memory Barriers::
+@end menu
+
+@node Disabling Interrupts
+@subsection Disabling Interrupts
+
+The crudest way to do synchronization is to disable interrupts, that
+is, to temporarily prevent the CPU from responding to interrupts. If
+interrupts are off, no other thread will preempt the running thread,
+because thread preemption is driven by the timer interrupt. If
+interrupts are on, as they normally are, then the running thread may
+be preempted by another at any time, whether between two C statements
+or even within the execution of one.
+
+Incidentally, this means that Pintos is a ``preemptible kernel,'' that
+is, kernel threads can be preempted at any time. Traditional Unix
+systems are ``nonpreemptible,'' that is, kernel threads can only be
+preempted at points where they explicitly call into the scheduler.
+(User programs can be preempted at any time in both models.) As you
+might imagine, preemptible kernels require more explicit
+synchronization.
+
+You should have little need to set the interrupt state directly. Most
+of the time you should use the other synchronization primitives
+described in the following sections. The main reason to disable
+interrupts is to synchronize kernel threads with external interrupt
+handlers, which cannot sleep and thus cannot use most other forms of
+synchronization (@pxref{External Interrupt Handling}).
+
+Types and functions for disabling and enabling interrupts are in
+@file{threads/interrupt.h}.
+
+@deftp Type {enum intr_level}
+One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
+disabled or enabled, respectively.
+@end deftp
+
+@deftypefun {enum intr_level} intr_get_level (void)
+Returns the current interrupt state.
+@end deftypefun
+
+@deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
+Turns interrupts on or off according to @var{level}. Returns the
+previous interrupt state.
+@end deftypefun
+
+@deftypefun {enum intr_level} intr_enable (void)
+Turns interrupts on. Returns the previous interrupt state.
+@end deftypefun
+
+@deftypefun {enum intr_level} intr_disable (void)
+Turns interrupts off. Returns the previous interrupt state.
+@end deftypefun
+
+@node Semaphores
+@subsection Semaphores
+
+Pintos' semaphore type and operations are declared in
+@file{threads/synch.h}.
+
+@deftp {Type} {struct semaphore}
+Represents a @dfn{semaphore}, a nonnegative integer together with two
+operators that manipulate it atomically, which are:
+
+@itemize @bullet
+@item
+``Down'' or ``P'': wait for the value to become positive, then
+decrement it.
+
+@item
+``Up'' or ``V'': increment the value (and wake up one waiting thread,
+if any).
+@end itemize
+
+A semaphore initialized to 0 may be used to wait for an event
+that will happen exactly once. For example, suppose thread @var{A}
+starts another thread @var{B} and wants to wait for @var{B} to signal
+that some activity is complete. @var{A} can create a semaphore
+initialized to 0, pass it to @var{B} as it starts it, and then
+``down'' the semaphore. When @var{B} finishes its activity, it
+``ups'' the semaphore. This works regardless of whether @var{A}
+``downs'' the semaphore or @var{B} ``ups'' it first.
+
+A semaphore initialized to 1 is typically used for controlling access
+to a resource. Before a block of code starts using the resource, it
+``downs'' the semaphore, then after it is done with the resource it
+``ups'' the resource. In such a case a lock, described below, may be
+more appropriate.
+
+Semaphores can also be initialized to values larger than 1. These are
+rarely used.
+@end deftp
+
+@deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
+Initializes @var{sema} as a new semaphore with the given initial
+@var{value}.
+@end deftypefun
+
+@deftypefun void sema_down (struct semaphore *@var{sema})
+Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
+its value to become positive and then decrementing it by one.
+@end deftypefun
+
+@deftypefun bool sema_try_down (struct semaphore *@var{sema})
+Tries to execute the ``down'' or ``P'' operation on @var{sema},
+without waiting. Returns true if @var{sema} had a positive value
+that was successfully decremented, or false if it was already
+zero and thus could not be decremented. Calling this function in a
+tight loop wastes CPU time (use @func{sema_down} instead, or find a
+different approach).
+@end deftypefun
+
+@deftypefun void sema_up (struct semaphore *@var{sema})
+Executes the ``up'' or ``V'' operation on @var{sema},
+incrementing its value. If any threads are waiting on
+@var{sema}, wakes one of them up.
+@end deftypefun
+
+Semaphores are internally built out of disabling interrupt
+(@pxref{Disabling Interrupts}) and thread blocking and unblocking
+(@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
+a list of waiting threads, using the linked list
+implementation in @file{lib/kernel/list.c}.
+
+@node Locks
+@subsection Locks
+
+Lock types and functions are declared in @file{threads/synch.h}.
+
+@deftp {Type} {struct lock}
+Represents a @dfn{lock}, a specialized semaphore with an initial value
+of 1 (@pxref{Semaphores}). The difference between a lock and such a
+semaphore is twofold. First, a semaphore does not have an owner,
+meaning that one thread can ``down'' the semaphore and then another one
+``up'' it, but a single thread must both acquire and release a lock.
+Second, a semaphore can have a value greater than 1, but a lock can only
+be owned by a single thread at a time. If these restrictions prove
+onerous, it's a good sign that a semaphore should be used, instead of a
+lock.
+
+Locks in Pintos are not ``recursive,'' that is, it is an error for the
+thread currently holding a lock to try to acquire that lock.
+@end deftp
+
+@deftypefun void lock_init (struct lock *@var{lock})
+Initializes @var{lock} as a new lock.
+@end deftypefun
+
+@deftypefun void lock_acquire (struct lock *@var{lock})
+Acquires @var{lock} for use by the current thread, first waiting for
+any current owner to release it if necessary.
+@end deftypefun
+
+@deftypefun bool lock_try_acquire (struct lock *@var{lock})
+Tries to acquire @var{lock} for use by the current thread, without
+waiting. Returns true if successful, false if the lock is already
+owned. Calling this function in a tight loop is a bad idea because it
+wastes CPU time (use @func{lock_acquire} instead).
+@end deftypefun
+
+@deftypefun void lock_release (struct lock *@var{lock})
+Releases @var{lock}, which the current thread must own.
+@end deftypefun
+
+@deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
+Returns true if the running thread owns @var{lock},
+false otherwise.
+@end deftypefun
+
+@node Condition Variables
+@subsection Condition Variables
+
+Condition variable types and functions are declared in
+@file{threads/synch.h}.
+
+@deftp {Type} {struct condition}
+Represents a condition variable, which allows one piece of code to
+signal a condition
+and cooperating code to receive the signal and act upon it. Each
+condition variable is associated with a lock. A given condition
+variable is associated with only a single lock, but one lock may be
+associated with any number of condition variables. A set of condition
+variables taken together with their lock is called a ``monitor.''
+
+A thread that owns the monitor lock is said to be ``in the monitor.''
+The thread in the monitor has control over all the data protected by
+the lock. It may freely examine or modify this data. If it discovers
+that it needs to wait for some condition to become true, then it
+``waits'' on the associated condition, which releases the lock and
+waits for the condition to be signaled. If, on the other hand, it has
+caused one of these conditions to become true, it ``signals'' the
+condition to wake up one waiter, or ``broadcasts'' the condition to
+wake all of them.
+
+Pintos monitors are ``Mesa'' style, not
+``Hoare'' style. That is, sending and receiving a signal are not an
+atomic operation. Thus, typically the caller must recheck the
+condition after the wait completes and, if necessary, wait again.
+@end deftp
+
+@deftypefun void cond_init (struct condition *@var{cond})
+Initializes @var{cond} as a new condition variable.
+@end deftypefun
+
+@deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
+Atomically releases @var{lock} (the monitor lock) and waits for
+@var{cond} to be signaled by some other piece of code. After
+@var{cond} is signaled, reacquires @var{lock} before returning.
+@var{lock} must be held before calling this function.
+@end deftypefun
+
+@deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
+If any threads are waiting on @var{cond} (protected by monitor lock
+@var{lock}), then this function wakes up one of them. If no threads are
+waiting, returns without performing any action.
+@var{lock} must be held before calling this function.
+@end deftypefun
+
+@deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
+Wakes up all threads, if any, waiting on @var{cond} (protected by
+monitor lock @var{lock}). @var{lock} must be held before calling this
+function.
+@end deftypefun
+
+@subsubsection Monitor Example
+
+The classical example of a monitor is handling a buffer into which one
+``producer'' thread writes characters and out of which a second
+``consumer'' thread reads characters. To implement this case we need,
+besides the monitor lock, two condition variables which we will call
+@var{not_full} and @var{not_empty}:
+
+@example
+char buf[BUF_SIZE]; /* @r{Buffer.} */
+size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
+size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
+size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
+struct lock lock; /* @r{Monitor lock.} */
+struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
+struct condition not_full; /* @r{Signaled when the buffer is not full.} */
+
+@dots{}@r{initialize the locks and condition variables}@dots{}
+
+void put (char ch) @{
+ lock_acquire (&lock);
+ while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
+ cond_wait (¬_full, &lock);
+ buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
+ n++;
+ cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
+ lock_release (&lock);
+@}
+
+char get (void) @{
+ char ch;
+ lock_acquire (&lock);
+ while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
+ cond_wait (¬_empty, &lock);
+ ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
+ n--;
+ cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
+ lock_release (&lock);
+@}
+@end example
+
+@node Memory Barriers
+@subsection Memory Barriers
+
+Suppose we add a ``feature'' that, whenever a timer interrupt
+occurs, the character in global variable @code{timer_put_char} is
+printed on the console, but only if global Boolean variable
+@code{timer_do_put} is true.
+
+If interrupts are enabled, this code for setting up @samp{x} to be
+printed is clearly incorrect, because the timer interrupt could intervene
+between the two assignments:
+
+@example
+timer_do_put = true; /* INCORRECT CODE */
+timer_put_char = 'x';
+@end example
+
+It might not be as obvious that the following code is just as
+incorrect:
+
+@example
+timer_put_char = 'x'; /* INCORRECT CODE */
+timer_do_put = true;
+@end example
+
+The reason this second example might be a problem is that the compiler
+is, in general, free to reorder operations when it doesn't have a
+visible reason to keep them in the same order. In this case, the
+compiler doesn't know that the order of assignments is important, so its
+optimization pass is permitted to exchange their order.
+There's no telling whether it will actually do this, and it is possible
+that passing the compiler different optimization flags or changing
+compiler versions will produce different behavior.
+
+The following is @emph{not} a solution, because locks neither prevent
+interrupts nor prevent the compiler from reordering the code within the
+region where the lock is held:
+
+@example
+lock_acquire (&timer_lock); /* INCORRECT CODE */
+timer_put_char = 'x';
+timer_do_put = true;
+lock_release (&timer_lock);
+@end example
+
+Fortunately, real solutions do exist. One possibility is to
+disable interrupts around the assignments. This does not prevent
+reordering, but it makes the assignments atomic as observed by the
+interrupt handler. It also has the extra runtime cost of disabling and
+re-enabling interrupts:
+
+@example
+enum intr_level old_level = intr_disable ();
+timer_put_char = 'x';
+timer_do_put = true;
+intr_set_level (old_level);
+@end example
+
+A second possibility is to mark the declarations of
+@code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
+keyword tells the compiler that the variables are externally observable
+and restricts its latitude for optimization. However, the semantics of
+@samp{volatile} are not well-defined, so it is not a good general
+solution.
+
+Usually, the best solution is to use a compiler feature called a
+@dfn{memory barrier}, a special statement that prevents the compiler
+from reordering memory operations across the barrier. In Pintos,
+@file{threads/synch.h} defines the @code{barrier()} macro as a memory
+barrier. Here's how we would use a memory barrier to fix this code:
+
+@example
+timer_put_char = 'x';
+barrier ();
+timer_do_put = true;
+@end example
+
+The compiler also treats invocation of any function defined externally,
+that is, in another source file, as a limited form of a memory barrier.
+Specifically, the compiler assumes that any externally defined function
+may access any statically or dynamically allocated data and any local
+variable whose address is taken. This often means that explicit
+barriers can be omitted, and, indeed, this is why the base Pintos code
+does not need any barriers.
+
+A function defined in the same source file, or in a header included by
+the source file, cannot be relied upon as a memory barrier.
+This applies even to invocation of a function before its
+definition, because the compiler may read and parse the entire source
+file before performing optimization.
+
+@node Interrupt Handling
+@section Interrupt Handling
+
+An @dfn{interrupt} notifies the CPU of some event. Much of the work
+of an operating system relates to interrupts in one way or another.
+For our purposes, we classify interrupts into two broad categories:
+
+@itemize @bullet
+@item
+@dfn{External interrupts}, that is, interrupts originating outside the
+CPU. These interrupts come from hardware devices such as the system
+timer, keyboard, serial ports, and disks. External interrupts are
+@dfn{asynchronous}, meaning that their delivery is not
+synchronized with normal CPU activities. External interrupts
+are what @func{intr_disable} and related functions
+postpone (@pxref{Disabling Interrupts}).
+
+@item
+@dfn{Internal interrupts}, that is, interrupts caused by something
+executing on the CPU. These interrupts are caused by something
+unusual happening during instruction execution: accessing invalid
+memory (a @dfn{page fault}), executing invalid instructions, and
+various other disallowed activities. Because they are caused by CPU
+instructions, internal interrupts are @dfn{synchronous} or
+synchronized with CPU instructions. @func{intr_disable} does not
+disable internal interrupts.
+@end itemize
+
+Because the CPU treats all interrupts largely the same way, regardless
+of source, Pintos uses the same infrastructure for both internal and
+external interrupts, to a point. The following section describes this
+common infrastructure, and sections after that give the specifics of
+external and internal interrupts.
+
+If you haven't already read chapter 3, ``Basic Execution Environment,''
+in @bibref{IA32-v1}, it is recommended that you do so now. You might
+also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
+@bibref{IA32-v3a}.
+
+@menu
+* Interrupt Infrastructure::
+* Internal Interrupt Handling::
+* External Interrupt Handling::
+@end menu
+
+@node Interrupt Infrastructure
+@subsection Interrupt Infrastructure
+
+When an interrupt occurs while the kernel is running, the CPU saves
+its most essential state on the stack and jumps to an interrupt
+handler routine. The 80@var{x}86 architecture allows for 256 possible
+interrupts, each of which can have its own handler. The handler for
+each interrupt is defined in an array called the @dfn{interrupt
+descriptor table} or IDT.
+
+In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
+IDT so that each entry points to a unique entry point in
+@file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
+@var{NN} is the interrupt number in
+hexadecimal. Because the CPU doesn't give
+us any other way to find out the interrupt number, this entry point
+pushes the interrupt number on the stack. Then it jumps to
+@func{intr_entry}, which pushes all the registers that the processor
+didn't already save for us, and then calls @func{intr_handler}, which
+brings us back into C in @file{threads/interrupt.c}.
+
+The main job of @func{intr_handler} is to call any function that has
+been registered for handling the particular interrupt. (If no
+function is registered, it dumps some information to the console and
+panics.) It does some extra processing for external
+interrupts that we'll discuss later.
+
+When @func{intr_handler} returns, the assembly code in
+@file{threads/intr-stubs.S} restores all the CPU registers saved
+earlier and directs the CPU to return from the interrupt.
+
+A few types and functions apply to both internal and external
+interrupts.
+
+@deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
+This is how an interrupt handler function must be declared. Its @var{frame}
+argument (see below) allows it to determine the cause of the interrupt
+and the state of the thread that was interrupted.
+@end deftp
+
+@deftp {Type} {struct intr_frame}
+The stack frame of an interrupt handler, as saved by CPU, the interrupt
+stubs, and @func{intr_entry}. Its most interesting members are described
+below.
+@end deftp
+
+@deftypecv {Member} {@struct{intr_frame}} uint32_t edi
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
+@deftypecvx {Member} {@struct{intr_frame}} uint16_t es
+@deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
+Register values in the interrupted thread saved by @func{intr_entry}.
+The @code{esp_dummy} value isn't actually used (refer to the
+description of @code{PUSHA} in @bibref{IA32-v2b} for details).
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
+The interrupt vector number, ranging from 0 to 255.
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
+The ``error code'' pushed on the stack by the CPU for some internal
+interrupts.
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
+The address of the next instruction to be executed by the interrupted
+thread.
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} {void *} esp
+The interrupted thread's stack pointer.
+@end deftypecv
+
+@deftypefun {const char *} intr_name (uint8_t @var{vec})
+Returns the name of the interrupt numbered @var{vec}, or
+@code{"unknown"} if the interrupt has no registered name.
+@end deftypefun
+
+@node Internal Interrupt Handling
+@subsection Internal Interrupt Handling
+
+When an internal interrupt occurs, it is because the running kernel
+thread (or, starting from project 2, the running user process) has
+caused it. Thus, because it is related to a thread (or process), an
+internal interrupt is said to happen in a ``process context.''
+
+In an internal interrupt, it can make sense to examine the
+@struct{intr_frame} passed to the interrupt handler, or even to modify
+it. When the interrupt returns, modified members
+in @struct{intr_frame} become changes to the thread's registers.
+We'll use this in project 2 to return values from system call
+handlers.
+
+There are no special restrictions on what an internal interrupt
+handler can or can't do. Generally they should run with interrupts
+enabled, just like other code, and so they can be preempted by other
+kernel threads. Thus, they do need to synchronize with other threads
+on shared data and other resources (@pxref{Synchronization}).
+
+@deftypefun void intr_register_int (uint8_t @var{vec}, int @var{dpl}, enum intr_level @var{level}, intr_handler_func *@var{handler}, const char *@var{name})
+Registers @var{handler} to be called when internal interrupt numbered
+@var{vec} is triggered. Names the interrupt @var{name} for debugging
+purposes.
+
+If @var{level} is @code{INTR_OFF} then handling of further interrupts
+will be disabled while the interrupt is being processed. Interrupts
+should normally be turned on during the handling of an internal
+interrupt.
+
+@var{dpl} determines how the interrupt can be
+invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
+kernel threads. Otherwise @var{dpl} should be 3, which allows user
+processes to invoke the interrupt as well (this is useful only
+starting with project 2).
+@end deftypefun
+
+@node External Interrupt Handling
+@subsection External Interrupt Handling
+
+Whereas an internal interrupt runs in the context of the thread that
+caused it, external interrupts do not have any predictable context.
+They are asynchronous, so they can be invoked at any time that
+interrupts have not been disabled. We say that an external interrupt
+runs in an ``interrupt context.''
+
+In an external interrupt, the @struct{intr_frame} passed to the
+handler is not very meaningful. It describes the state of the thread
+or process that was interrupted, but there is no way to predict which
+one that is. It is possible, although rarely useful, to examine it, but
+modifying it is a recipe for disaster.
+
+The activities of an external interrupt handler are severely
+restricted. First, only one external interrupt may be processed at a
+time, that is, nested external interrupt handling is not supported.
+This means that external interrupts must be processed with interrupts
+disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
+enabled at any point during their execution.
+
+Second, an interrupt handler must not call any function that can
+sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
+many others. This is because external interrupts use space on the
+stack of the kernel thread that was running at the time the interrupt
+occurred. If the interrupt handler slept, it would effectively put that
+thread to sleep too until the interrupt handler resumed control and
+returned.
+
+Because an external interrupt runs with interrupts disabled, it
+effectively monopolizes the machine and delays all other activities.
+Therefore, external interrupt handlers should complete as quickly as
+they can. Any activities that require much CPU time should instead
+run in a kernel thread, possibly a thread whose activity is triggered
+by the interrupt using some synchronization primitive.
+
+External interrupts are also special because they are controlled by a
+pair of devices outside the CPU called @dfn{programmable interrupt
+controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
+CPU's IDT, it also initializes the PICs for interrupt handling. The
+PICs also must be ``acknowledged'' at the end of processing for each
+external interrupt. @func{intr_handler} takes care of that by calling
+@func{pic_end_of_interrupt}, which sends the proper signals to the
+right PIC.
+
+The following additional functions are related to external
+interrupts.
+
+@deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
+Registers @var{handler} to be called when external interrupt numbered
+@var{vec} is triggered. Names the interrupt @var{name} for debugging
+purposes. The handler will run with interrupts disabled.
+@end deftypefun
+
+@deftypefun bool intr_context (void)
+Returns true if we are running in an interrupt context, otherwise
+false. Mainly used at the beginning of functions that might sleep
+or that otherwise should not be called from interrupt context, in this
+form:
+@example
+ASSERT (!intr_context ());
+@end example
+@end deftypefun
+
+@deftypefun void intr_yield_on_return (void)
+When called in an interrupt context, causes @func{thread_yield} to be
+called just before the interrupt returns. This is used, for example,
+in the timer interrupt handler to cause a new thread to be scheduled
+when a thread's time slice expires.
+@end deftypefun
+
+@node Memory Allocation
+@section Memory Allocation
+
+Pintos contains two memory allocators, one that allocates memory in
+units of a page, and one that can allocate blocks of any size.
+
+@menu
+* Page Allocator::
+* Block Allocator::
+@end menu
+
+@node Page Allocator
+@subsection Page Allocator
+
+The page allocator declared in @file{threads/palloc.h} allocates
+memory in units of a page. It is most often used to allocate memory
+one page at a time, but it can also allocate multiple contiguous pages
+at once.
+
+The page allocator divides the memory it allocates into two pools,
+called the kernel and user pools. By default, each pool gets half of
+system memory, but this can be changed with a kernel command line
+option (@pxref{Why PAL_USER?}). An allocation request draws from one
+pool or the other. If one pool becomes empty, the other may still
+have free pages. The user pool should be used for allocating memory
+for user processes and the kernel pool for all other allocations.
+This will only become important starting with project 3. Until then,
+all allocations should be made from the kernel pool.
+
+Each pool's usage is tracked with a bitmap, one bit per page in
+the pool. A request to allocate @var{n} pages scans the bitmap
+for @var{n} consecutive bits set to
+false, indicating that those pages are free, and then sets those bits
+to true to mark them as used. This is a ``first fit'' allocation
+strategy.
+
+The page allocator is subject to fragmentation. That is, it may not
+be possible to allocate @var{n} contiguous pages even though @var{n}
+or more pages are free, because the free pages are separated by used
+pages. In fact, in pathological cases it may be impossible to
+allocate 2 contiguous pages even though @var{n} / 2 pages are free!
+Single-page requests can't fail due to fragmentation, so
+it is best to limit, as much as possible, the need for multiple
+contiguous pages.
+
+Pages may not be allocated from interrupt context, but they may be
+freed.
+
+When a page is freed, all of its bytes are cleared to @t{0xcc}, as
+a debugging aid (@pxref{Debugging Tips}).
+
+Page allocator types and functions are described below.
+
+@deftp {Type} {enum palloc_flags}
+A set of flags that describe how to allocate pages. These flags may
+be combined in any combination.
+@end deftp
+
+@defvr {Page Allocator Flag} @code{PAL_ASSERT}
+If the pages cannot be allocated, panic the kernel. This is only
+appropriate during kernel initialization. User processes
+should never be permitted to panic the kernel.
+@end defvr
+
+@defvr {Page Allocator Flag} @code{PAL_ZERO}
+Zero all the bytes in the allocated pages before returning them. If not
+set, the contents of newly allocated pages are unpredictable.
+@end defvr
+
+@defvr {Page Allocator Flag} @code{PAL_USER}
+Obtain the pages from the user pool. If not set, pages are allocated
+from the kernel pool.
+@end defvr
+
+@deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
+Obtains and returns a single page, allocating it in the manner specified by
+@var{flags}. Returns a null pointer if no pages are
+free.
+@end deftypefun
+
+@deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
+Obtains @var{page_cnt} contiguous free pages, allocating them in the
+manner specified by @var{flags}, and returns them. Returns a null
+pointer if no pages are free.
+@end deftypefun
+
+@deftypefun void palloc_free_page (void *@var{page})
+Frees @var{page}, which must have been obtained using
+@func{palloc_get_page} or @func{palloc_get_multiple}.
+@end deftypefun
+
+@deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
+Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
+All of the pages must have been obtained using @func{palloc_get_page}
+or @func{palloc_get_multiple}.
+@end deftypefun
+
+@node Block Allocator
+@subsection Block Allocator
+
+The block allocator, declared in @file{threads/malloc.h}, can allocate
+blocks of any size. It is layered on top of the page allocator
+described in the previous section. Blocks returned by the block
+allocator are obtained from the kernel pool.
+
+The block allocator uses two different strategies for allocating
+memory. The first of these applies to ``small'' blocks, those 1 kB or
+smaller (one
+fourth of the page size). These allocations are rounded up to the
+nearest power of 2, or 16 bytes, whichever is larger. Then they are
+grouped into a page used only for allocations of the smae
+size.
+
+The second strategy applies to allocating ``large'' blocks, those larger
+than 1 kB.
+These allocations (plus a small amount of overhead) are rounded up to
+the nearest page in size, and then the block allocator requests that
+number of contiguous pages from the page allocator.
+
+In either case, the difference between the allocation requested size
+and the actual block size is wasted. A real operating system would
+carefully tune its allocator to minimize this waste, but this is
+unimportant in an instructional system like Pintos.
+
+As long as a page can be obtained from the page allocator, small
+allocations always succeed. Most small allocations will not require a
+new page from the page allocator at all. However, large allocations
+always require calling into the page allocator, and any allocation
+that needs more than one contiguous page can fail due to fragmentation,
+as already discussed in the previous section. Thus, you should
+minimize the number of large allocations in your code, especially
+those over approximately 4 kB each.
+
+The interface to the block allocator is through the standard C library
+functions @func{malloc}, @func{calloc}, and @func{free}.
+
+When a block is freed, all of its bytes are cleared to @t{0xcc}, as
+a debugging aid (@pxref{Debugging Tips}).
+
+The block allocator may not be called from interrupt context.
+
+@node Virtual Addresses
+@section Virtual Addresses
+
+A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
+and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
+
+@example
+@group
+ 31 12 11 0
+ +-------------------+-----------+
+ | Page Number | Offset |
+ +-------------------+-----------+
+ Virtual Address
+@end group
+@end example
+
+Header @file{threads/vaddr.h} defines these functions and macros for
+working with virtual addresses:
+
+@defmac PGSHIFT
+@defmacx PGBITS
+The bit index (0) and number of bits (12) in the offset part of a
+virtual address, respectively.
+@end defmac
+
+@defmac PGMASK
+A bit mask with value @t{0xfff}, so that the bits in the page offset are
+set to 1 and other bits set to 0.
+@end defmac
+
+@defmac PGSIZE
+The page size in bytes (4096).
+@end defmac
+
+@deftypefun unsigned pg_ofs (const void *@var{va})
+Extracts and returns the page offset in virtual address @var{va}.
+@end deftypefun
+
+@deftypefun uintptr_t pg_no (const void *@var{va})
+Extracts and returns the page number in virtual address @var{va}.
+@end deftypefun
+
+@deftypefun {void *} pg_round_down (const void *@var{va})
+Returns the start of the virtual page that @var{va} points within, that
+is, @var{va} with the page offset set to 0.
+@end deftypefun
+
+@deftypefun {void *} pg_round_up (const void *@var{va})
+Returns @var{va} rounded up to the nearest page boundary.
+@end deftypefun
+
+Virtual memory in Pintos is divided into two regions: user virtual
+memory and kernel virtual memory. The boundary between them is
+@code{PHYS_BASE}:
+
+@defmac PHYS_BASE
+Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
+GB), but it may be changed to any multiple of @t{0x10000000} from
+@t{0x80000000} to @t{0xf0000000}.
+
+User virtual memory ranges from virtual address 0 up to
+@code{PHYS_BASE}. Kernel virtual memory occupies the rest of the
+virtual address space, from @code{PHYS_BASE} up to 4 GB.
+@end defmac
+
+@deftypefun {bool} is_user_vaddr (const void *@var{va})
+@deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
+Returns true if @var{va} is a user or kernel virtual address,
+respectively, false otherwise.
+@end deftypefun
+
+The 80@var{x}86 doesn't provide any way to directly access memory given
+a physical address. This ability is often necessary in an operating
+system kernel, so Pintos works around it by mapping kernel virtual
+memory one-to-one to physical memory. 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. Thus, adding
+@code{PHYS_BASE} to a physical address obtains a kernel virtual address
+that accesses that address; conversely, subtracting @code{PHYS_BASE}
+from a kernel virtual address obtains the corresponding physical
+address. Header @file{threads/vaddr.h} provides a pair of functions to
+do these translations:
+
+@deftypefun {void *} ptov (uintptr_t @var{pa})
+Returns the kernel virtual address corresponding to physical address
+@var{pa}, which should be between 0 and the number of bytes of physical
+memory.
+@end deftypefun
+
+@deftypefun {uintptr_t} vtop (void *@var{va})
+Returns the physical address corresponding to @var{va}, which must be a
+kernel virtual address.
+@end deftypefun
+
+@node Page Table
+@section Page Table
+
+The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
+hardware page table, also called a ``page directory'' by Intel processor
+documentation. The page table interface uses a @code{uint32_t *} to
+represent a page table because this is convenient for accessing their
+internal structure.
+
+The sections below describe the page table interface and internals.
+
+@menu
+* Page Table Creation Destruction Activation::
+* Page Tables Inspection and Updates::
+* Page Table Accessed and Dirty Bits::
+* Page Table Details::
+@end menu
+
+@node Page Table Creation Destruction Activation
+@subsection Creation, Destruction, and Activation
+
+These functions create, destroy, and activate page tables. The base
+Pintos code already calls these functions where necessary, so it should
+not be necessary to call them yourself.
+
+@deftypefun {uint32_t *} pagedir_create (void)
+Creates and returns a new page table. The new page table contains
+Pintos's normal kernel virtual page mappings, but no user virtual
+mappings.
+
+Returns a null pointer if memory cannot be obtained.
+@end deftypefun
+
+@deftypefun void pagedir_destroy (uint32_t *@var{pd})
+Frees all of the resources held by @var{pd}, including the page table
+itself and the frames that it maps.
+@end deftypefun
+
+@deftypefun void pagedir_activate (uint32_t *@var{pd})
+Activates @var{pd}. The active page table is the one used by the CPU to
+translate memory references.
+@end deftypefun
+
+@node Page Tables Inspection and Updates
+@subsection Inspection and Updates
+
+These functions examine or update the mappings from pages to frames
+encapsulated by a page table. They work on both active and inactive
+page tables (that is, those for running and suspended processes),
+flushing the TLB as necessary.
+
+User page parameters (@var{upage})to these functions should be user
+virtual addresses. Kernel page parameters (@var{kpage}) should be
+kernel virtual addresses and should have been obtained from the user
+pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why PAL_USER?}).
+
+@deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
+Adds to @var{pd} a mapping from page @var{upage} to the frame identified
+by kernel virtual address @var{kpage}. If @var{writable} is true, the
+page is mapped read/write; otherwise, it is mapped read-only.
+
+Page @var{upage} must not already be mapped. If it is, the kernel
+panics.
+
+Returns true if successful, false on failure. Failure will occur if
+additional memory required for the page table cannot be obtained.
+@end deftypefun
+
+@deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
+Looks up the frame mapped to @var{upage} in @var{pd}. Returns the
+kernel virtual address for that frame, if @var{upage} is mapped, or a
+null pointer if it is not.
+@end deftypefun
+
+@deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{upage})
+Marks page @var{upage} ``not present'' in @var{pd}. Later accesses to
+the page will fault.
+
+Other bits in the page table for @var{upage} are preserved, permitting
+the accessed and dirty bits (see the next section) to be checked.
+
+If @var{upage} is not mapped, this function has no effect.
+@end deftypefun
+
+@node Page Table Accessed and Dirty Bits
+@subsection Accessed and Dirty Bits
+
+80@var{x}86 hardware provides some assistance for implementing page
+replacement algorithms, through a pair of bits in the page table entry
+(PTE) for each page. On any read or write to a page, the CPU sets the
+@dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
+sets the @dfn{dirty bit} to 1. The CPU never resets these bits to 0,
+but the OS may do so.
+
+Proper interpretation of these bits requires understanding of
+@dfn{aliases}, that is, two (or more) pages that refer to the same
+frame. When an aliased frame is accessed, the accessed and dirty bits
+are updated in only one page table entry (the one for the page used for
+access). The accessed and dirty bits for the other aliases are not
+updated.
+
+@xref{Accessed and Dirty Bits}, on applying these bits in implementing
+page replacement algorithms.
+
+@deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
+@deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
+Returns true if page directory @var{pd} contains a page table entry for
+@var{page} that is marked dirty (or accessed). Otherwise,
+returns false.
+@end deftypefun
+
+@deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
+@deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
+If page directory @var{pd} has a page table entry for @var{page}, then
+its dirty (or accessed) bit is set to @var{value}.
+@end deftypefun
+
+@node Page Table Details
+@subsection Page Table Details
+
+The functions provided with Pintos are sufficient to implement the
+projects. However, you may still find it worthwhile to understand the
+hardware page table format, so we'll go into a little detail in this
+section.
+
+@menu
+* Page Table Structure::
+* Page Table Entry Format::
+* Page Directory Entry Format::
+@end menu
+
+@node Page Table Structure
+@subsubsection Structure
+
+The top-level paging data structure is a page called the ``page
+directory'' (PD) arranged as an array of 1,024 32-bit page directory
+entries (PDEs), each of which represents 4 MB of virtual memory. Each
+PDE may point to the physical address of another page called a
+``page table'' (PT) arranged, similarly, as an array of 1,024
+32-bit page table entries (PTEs), each of which translates a single 4
+kB virtual page to a physical page.
+
+Translation of a virtual address into a physical address follows
+the three-step process illustrated in the diagram
+below:@footnote{Actually, virtual to physical translation on the
+80@var{x}86 architecture occurs via an intermediate ``linear
+address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
+so that linear and virtual addresses are one and the same. Thus, you
+can effectively ignore this CPU feature.}
+
+@enumerate 1
+@item
+The most-significant 10 bits of the virtual address (bits 22@dots{}31)
+index the page directory. If the PDE is marked ``present,'' the
+physical address of a page table is read from the PDE thus obtained.
+If the PDE is marked ``not present'' then a page fault occurs.
+
+@item
+The next 10 bits of the virtual address (bits 12@dots{}21) index
+the page table. If the PTE is marked ``present,'' the physical
+address of a data page is read from the PTE thus obtained. If the PTE
+is marked ``not present'' then a page fault occurs.
+
+@item
+The least-significant 12 bits of the virtual address (bits 0@dots{}11)
+are added to the data page's physical base address, yielding the final
+physical address.
+@end enumerate
+
+@example
+@group
+ 31 22 21 12 11 0
++----------------------+----------------------+----------------------+
+| Page Directory Index | Page Table Index | Page Offset |
++----------------------+----------------------+----------------------+
+ | | |
+ _______/ _______/ _____/
+ / / /
+ / Page Directory / Page Table / Data Page
+ / .____________. / .____________. / .____________.
+ |1,023|____________| |1,023|____________| | |____________|
+ |1,022|____________| |1,022|____________| | |____________|
+ |1,021|____________| |1,021|____________| \__\|____________|
+ |1,020|____________| |1,020|____________| /|____________|
+ | | | | | | | |
+ | | | \____\| |_ | |
+ | | . | /| . | \ | . |
+ \____\| . |_ | . | | | . |
+ /| . | \ | . | | | . |
+ | . | | | . | | | . |
+ | | | | | | | |
+ |____________| | |____________| | |____________|
+ 4|____________| | 4|____________| | |____________|
+ 3|____________| | 3|____________| | |____________|
+ 2|____________| | 2|____________| | |____________|
+ 1|____________| | 1|____________| | |____________|
+ 0|____________| \__\0|____________| \____\|____________|
+ / /
+@end group
+@end example
+
+Pintos provides some macros and functions that are useful for working
+with raw page tables:
+
+@defmac PTSHIFT
+@defmacx PTBITS
+The bit index (12) and number of bits (10), respectively, in a page table
+index within a virtual address.
+@end defmac
+
+@defmac PTMASK
+A bit mask with the bits in the page table index set to 1 and other bits
+set to 0.
+@end defmac
+
+@defmac PTSPAN
+The number of bytes of virtual address space that a single page table
+page covers (4,194,304 bytes, or 4 MB).
+@end defmac
+
+@defmac PDSHIFT
+@defmacx PDBITS
+The bit index (22) and number of bits (10), respectively, in a page
+directory index within a virtual address.
+@end defmac
+
+@defmac PDMASK
+A bit mask with the bits in the page directory index set to 1 and other
+bits set to 0.
+@end defmac
+
+@deftypefun uintptr_t pd_no (const void *@var{va})
+@deftypefunx uintptr_t pt_no (const void *@var{va})
+Returns the page directory index or page table index, respectively, for
+virtual address @var{va}. These functions are defined in
+@file{threads/pte.h}.
+@end deftypefun
+
+@deftypefun unsigned pg_ofs (const void *@var{va})
+Returns the page offset for virtual address @var{va}. This function is
+defined in @file{threads/vaddr.h}.
+@end deftypefun
+
+@node Page Table Entry Format
+@subsubsection Page Table Entry Format
+
+You do not need to understand the PTE format to do the Pintos
+projects, unless you wish to incorporate the page table into your
+segment table (@pxref{Managing the Segment Table}).
+
+The actual format of a page table entry is summarized below. For
+complete information, refer to section 3.7, ``Page Translation Using
+32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
+
+@example
+@group
+ 31 12 11 9 6 5 2 1 0
++---------------------------------------+----+----+-+-+---+-+-+-+
+| Physical Address | AVL| |D|A| |U|W|P|
++---------------------------------------+----+----+-+-+---+-+-+-+
+@end group
+@end example
+
+Some more information on each bit is given below. The names are
+@file{threads/pte.h} macros that represent the bits' values:
+
+@defmac PTE_P
+Bit 0, the ``present'' bit. When this bit is 1, the
+other bits are interpreted as described below. When this bit is 0, any
+attempt to access the page will page fault. The remaining bits are then
+not used by the CPU and may be used by the OS for any purpose.
+@end defmac
+
+@defmac PTE_W
+Bit 1, the ``read/write'' bit. When it is 1, the page
+is writable. When it is 0, write attempts will page fault.
+@end defmac
+
+@defmac PTE_U
+Bit 2, the ``user/supervisor'' bit. When it is 1, user
+processes may access the page. When it is 0, only the kernel may access
+the page (user accesses will page fault).
+
+Pintos clears this bit in PTEs for kernel virtual memory, to prevent
+user processes from accessing them.
+@end defmac
+
+@defmac PTE_A
+Bit 5, the ``accessed'' bit. @xref{Page Table Accessed
+and Dirty Bits}.
+@end defmac
+
+@defmac PTE_D
+Bit 6, the ``dirty'' bit. @xref{Page Table Accessed and
+Dirty Bits}.
+@end defmac
+
+@defmac PTE_AVL
+Bits 9@dots{}11, available for operating system use.
+Pintos, as provided, does not use them and sets them to 0.
+@end defmac
+
+@defmac PTE_ADDR
+Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
+The low 12 bits of the frame's address are always 0.
+@end defmac
+
+Other bits are either reserved or uninteresting in a Pintos context and
+should be set to@tie{}0.
+
+Header @file{threads/pte.h} defines three functions for working with
+page table entries:
+
+@deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
+Returns a page table entry that points to @var{page}, which should be a
+kernel virtual address. The PTE's present bit will be set. It will be
+marked for kernel-only access. If @var{writable} is true, the PTE will
+also be marked read/write; otherwise, it will be read-only.
+@end deftypefun
+
+@deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
+Returns a page table entry that points to @var{page}, which should be
+the kernel virtual address of a frame in the user pool (@pxref{Why
+PAL_USER?}). The PTE's present bit will be set and it will be marked to
+allow user-mode access. If @var{writable} is true, the PTE will also be
+marked read/write; otherwise, it will be read-only.
+@end deftypefun
+
+@deftypefun {void *} pte_get_page (uint32_t @var{pte})
+Returns the kernel virtual address for the frame that @var{pte} points
+to. The @var{pte} may be present or not-present; if it is not-present
+then the pointer return is only meaningful if the proper bits in the PTE
+actually represent a physical address.
+@end deftypefun
+
+@node Page Directory Entry Format
+@subsubsection Page Directory Entry Format
+
+Page directory entries have the same format as PTEs, except that the
+physical address points to a page table page instead of a frame. Header
+@file{threads/pte.h} defines two functions for working with page
+directory entries:
+
+@deftypefun uint32_t pde_create (uint32_t *@var{pt})
+Returns a page directory that points to @var{page}, which should be the
+kernel virtual address of a page table page. The PDE's present bit will
+be set, it will be marked to allow user-mode access, and it will be
+marked read/write.
+@end deftypefun
+
+@deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
+Returns the kernel virtual address for the page table page that
+@var{pde} points to. The @var{pde} must be marked present.
+@end deftypefun
+
+@node Hash Table
+@section Hash Table
+
+Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
+To use it you will need to manually include its header file,
+@file{lib/kernel/hash.h}, with @code{#include <hash.h>}. Intentionally,
+no code provided with Pintos uses the hash table, which means that you
+are free to use it as is, modify its implementation for your own
+purposes, or ignore it, as you wish.
+
+Most implementations of the virtual memory project use a hash table to
+translate pages to frames. You may find other uses for hash tables as
+well.
+
+@menu
+* Hash Data Types::
+* Basic Hash Functions::
+* Hash Search Functions::
+* Hash Iteration Functions::
+* Hash Table Example::
+* Hash Auxiliary Data::
+* Hash Synchronization::
+@end menu
+
+@node Hash Data Types
+@subsection Data Types
+
+A hash table is represented by @struct{hash}.
+
+@deftp {Type} {struct hash}
+Represents an entire hash table. The actual members of @struct{hash}
+are ``opaque.'' That is, code that uses a hash table should not access
+@struct{hash} members directly, nor should it need to. Instead, use
+hash table functions and macros.
+@end deftp
+
+The hash table operates on elements of type @struct{hash_elem}.
+
+@deftp {Type} {struct hash_elem}
+Embed a @struct{hash_elem} member in the structure you want to include
+in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
+All functions for operating on hash table elements actually take and
+return pointers to @struct{hash_elem}, not pointers to your hash table's
+real element type.
+@end deftp
+
+You will often need to obtain a @struct{hash_elem}
+given a real element of the hash table, and vice versa. Given
+a real element of the hash table, obtaining a pointer to its
+@struct{hash_elem} is trivial: take the address of the
+@struct{hash_elem} member. Use the @code{hash_entry()} macro to go the
+other direction.
+
+@deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
+Returns a pointer to the structure that @var{elem}, a pointer to a
+@struct{hash_elem}, is embedded within. You must provide @var{type},
+the name of the structure that @var{elem} is inside, and @var{member},
+the name of the member in @var{type} that @var{elem} points to.
+
+For example, suppose @code{h} is a @code{struct hash_elem *} variable
+that points to a @struct{thread} member (of type @struct{hash_elem})
+named @code{h_elem}. Then, @code{hash_entry (h, struct thread, h_elem)}
+yields the address of the @struct{thread} that @code{h} points within.
+@end deftypefn
+
+Each hash table element must contain a key, that is, data that
+identifies and distinguishes elements in the hash table. Every element
+in a hash table at a given time must have a unique key. (Elements may
+also contain non-key data that need not be unique.) While an element is
+in a hash table, its key data must not be changed. For each hash table,
+you must write two functions that act on keys: a hash function and a
+comparison function. These functions must match the following
+prototypes:
+
+@deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
+Returns a hash of @var{element}'s data, as a value anywhere in the range
+of @code{unsigned int}. The hash of an element should be a
+pseudo-random function of the element's key. It must not depend on
+non-key data in the element or on any non-constant data other than the
+key. Pintos provides the following functions as a suitable basis for
+hash functions.
+
+@deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
+Returns a hash of the @var{size} bytes starting at @var{buf}. The
+implementation is the general-purpose
+@uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
+hash} for 32-bit words.
+@end deftypefun
+
+@deftypefun unsigned hash_string (const char *@var{s})
+Returns a hash of null-terminated string @var{s}.
+@end deftypefun
+
+@deftypefun unsigned hash_int (int @var{i})
+Returns a hash of integer @var{i}.
+@end deftypefun
+
+If your key is a single piece of data of an appropriate type, it is
+sensible for your hash function to directly return the output of one of
+these functions. For multiple pieces of data, you may wish to combine
+the output of more than one call to them using, e.g., the @samp{^}
+(exclusive or)
+operator. Finally, you may entirely ignore these functions and write
+your own hash function from scratch, but remember that your goal is to
+build an operating system kernel, not to design a hash function.
+
+@xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
+@end deftp
+
+@deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
+Compares the keys stored in elements @var{a} and @var{b}. Returns
+true if @var{a} is less than @var{b}, false if @var{a} is greater than
+or equal to @var{b}.
+
+If two elements compare equal, then they must hash to equal values.
+
+@xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
+@end deftp
+
+A few functions that act on hashes accept a pointer to a third kind of
+function as an argument:
+
+@deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
+Performs some kind of action, chosen by the caller, on @var{element}.
+
+@xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
+@end deftp
+
+@node Basic Hash Functions
+@subsection Basic Functions
+
+These functions create and destroy hash tables and obtain basic
+information about their contents.
+
+@deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
+Initializes @var{hash} as a hash table using @var{hash_func} as hash
+function, @var{less_func} as comparison function, and @var{aux} as
+auxiliary data.
+Returns true if successful, false on failure. @func{hash_init} calls
+@func{malloc} and fails if memory cannot be allocated.
+
+@xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
+most often a null pointer.
+@end deftypefun
+
+@deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
+Removes all the elements from @var{hash}, which must have been
+previously initialized with @func{hash_init}.
+
+If @var{action} is non-null, then it is called once for each element in
+the hash table, which gives the caller an opportunity to deallocate any
+memory or other resources used by the element. For example, if the hash
+table elements are dynamically allocated using @func{malloc}, then
+@var{action} could @func{free} the element. This is safe because
+@func{hash_clear} will not access the memory in a given hash element
+after calling @var{action} on it. However, @var{action} must not call
+any function that may modify the hash table, such as @func{hash_insert}
+or @func{hash_delete}.
+@end deftypefun
+
+@deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
+If @var{action} is non-null, calls it for each element in the hash, with
+the same semantics as a call to @func{hash_clear}. Then, frees the
+memory held by @var{hash}. Afterward, @var{hash} must not be passed to
+any hash table function, absent an intervening call to @func{hash_init}.
+@end deftypefun
+
+@deftypefun size_t hash_size (struct hash *@var{hash})
+Returns the number of elements currently stored in @var{hash}.
+@end deftypefun
+
+@deftypefun bool hash_empty (struct hash *@var{hash})
+Returns true if @var{hash} currently contains no elements,
+false if @var{hash} contains at least one element.
+@end deftypefun
+
+@node Hash Search Functions
+@subsection Search Functions
+
+Each of these functions searches a hash table for an element that
+compares equal to one provided. Based on the success of the search,
+they perform some action, such as inserting a new element into the hash
+table, or simply return the result of the search.
+
+@deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
+Searches @var{hash} for an element equal to @var{element}. If none is
+found, inserts @var{element} into @var{hash} and returns a null pointer.
+If the table already contains an element equal to @var{element}, returns
+the existing element without modifying @var{hash}.
+@end deftypefun
+
+@deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
+Inserts @var{element} into @var{hash}. Any element equal to
+@var{element} already in @var{hash} is removed. Returns the element
+removed, or a null pointer if @var{hash} did not contain an element
+equal to @var{element}.
+
+The caller is responsible for deallocating any resources associated with
+the element returned, as appropriate. For example, if the hash table
+elements are dynamically allocated using @func{malloc}, then the caller
+must @func{free} the element after it is no longer needed.
+@end deftypefun
+
+The element passed to the following functions is only used for hashing
+and comparison purposes. It is never actually inserted into the hash
+table. Thus, only the key data in the element need be initialized, and
+other data in the element will not be used. It often makes sense to
+declare an instance of the element type as a local variable, initialize
+the key data, and then pass the address of its @struct{hash_elem} to
+@func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
+an example. (Large structures should not be
+allocated as local variables. @xref{struct thread}, for more
+information.)
+
+@deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
+Searches @var{hash} for an element equal to @var{element}. Returns the
+element found, if any, or a null pointer otherwise.
+@end deftypefun
+
+@deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
+Searches @var{hash} for an element equal to @var{element}. If one is
+found, it is removed from @var{hash} and returned. Otherwise, a null
+pointer is returned and @var{hash} is unchanged.
+
+The caller is responsible for deallocating any resources associated with
+the element returned, as appropriate. For example, if the hash table
+elements are dynamically allocated using @func{malloc}, then the caller
+must @func{free} the element after it is no longer needed.
+@end deftypefun
+
+@node Hash Iteration Functions
+@subsection Iteration Functions
+
+These functions allow iterating through the elements in a hash table.
+Two interfaces are supplied. The first requires writing and supplying a
+@var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
+
+@deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
+Calls @var{action} once for each element in @var{hash}, in arbitrary
+order. @var{action} must not call any function that may modify the hash
+table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
+must not modify key data in elements, although it may modify any other
+data.
+@end deftypefun
+
+The second interface is based on an ``iterator'' data type.
+Idiomatically, iterators are used as follows:
+
+@example
+struct hash_iterator i;
+
+hash_first (&i, h);
+while (hash_next (&i))
+ @{
+ struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
+ @r{@dots{}do something with @i{f}@dots{}}
+ @}
+@end example
+
+@deftp {Type} {struct hash_iterator}
+Represents a position within a hash table. Calling any function that
+may modify a hash table, such as @func{hash_insert} or
+@func{hash_delete}, invalidates all iterators within that hash table.
+
+Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
+@end deftp
+
+@deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
+Initializes @var{iterator} to just before the first element in
+@var{hash}.
+@end deftypefun
+
+@deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
+Advances @var{iterator} to the next element in @var{hash}, and returns
+that element. Returns a null pointer if no elements remain. After
+@func{hash_next} returns null for @var{iterator}, calling it again
+yields undefined behavior.
+@end deftypefun
+
+@deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
+Returns the value most recently returned by @func{hash_next} for
+@var{iterator}. Yields undefined behavior after @func{hash_first} has
+been called on @var{iterator} but before @func{hash_next} has been
+called for the first time.
+@end deftypefun
+
+@node Hash Table Example
+@subsection Hash Table Example
+
+Suppose you have a structure, called @struct{page}, that you
+want to put into a hash table. First, define @struct{page} to include a
+@struct{hash_elem} member:
+
+@example
+struct page
+ @{
+ struct hash_elem hash_elem; /* @r{Hash table element.} */
+ void *addr; /* @r{Virtual address.} */
+ /* @r{@dots{}other members@dots{}} */
+ @};
+@end example
+
+We write a hash function and a comparison function using @var{addr} as
+the key. A pointer can be hashed based on its bytes, and the @samp{<}
+operator works fine for comparing pointers:
+
+@example
+/* @r{Returns a hash value for page @var{p}.} */
+unsigned
+page_hash (const struct hash_elem *p_, void *aux UNUSED)
+@{
+ const struct page *p = hash_entry (p_, struct page, hash_elem);
+ return hash_bytes (&p->addr, sizeof p->addr);
+@}
+
+/* @r{Returns true if page @var{a} precedes page @var{b}.} */
+bool
+page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+ void *aux UNUSED)
+@{
+ const struct page *a = hash_entry (a_, struct page, hash_elem);
+ const struct page *b = hash_entry (b_, struct page, hash_elem);
+
+ return a->addr < b->addr;
+@}
+@end example
+
+@noindent
+(The use of @code{UNUSED} in these functions' prototypes suppresses a
+warning that @var{aux} is unused. @xref{Function and Parameter
+Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
+Data}, for an explanation of @var{aux}.)
+
+Then, we can create a hash table like this:
+
+@example
+struct hash pages;
+
+hash_init (&pages, page_hash, page_less, NULL);
+@end example
+
+Now we can manipulate the hash table we've created. If @code{@var{p}}
+is a pointer to a @struct{page}, we can insert it into the hash table
+with:
+
+@example
+hash_insert (&pages, &p->hash_elem);
+@end example
+
+@noindent If there's a chance that @var{pages} might already contain a
+page with the same @var{addr}, then we should check @func{hash_insert}'s
+return value.
+
+To search for an element in the hash table, use @func{hash_find}. This
+takes a little setup, because @func{hash_find} takes an element to
+compare against. Here's a function that will find and return a page
+based on a virtual address, assuming that @var{pages} is defined at file
+scope:
+
+@example
+/* @r{Returns the page containing the given virtual @var{address},
+ or a null pointer if no such page exists.} */
+struct page *
+page_lookup (const void *address)
+@{
+ struct page p;
+ struct hash_elem *e;
+
+ p.addr = address;
+ e = hash_find (&pages, &p.hash_elem);
+ return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
+@}
+@end example
+
+@noindent
+@struct{page} is allocated as a local variable here on the assumption
+that it is fairly small. Large structures should not be allocated as
+local variables. @xref{struct thread}, for more information.
+
+A similar function could delete a page by address using
+@func{hash_delete}.
+
+@node Hash Auxiliary Data
+@subsection Auxiliary Data
+
+In simple cases like the example above, there's no need for the
+@var{aux} parameters. In these cases, just pass a null pointer to
+@func{hash_init} for @var{aux} and ignore the values passed to the hash
+function and comparison functions. (You'll get a compiler warning if
+you don't use the @var{aux} parameter, but you can turn that off with
+the @code{UNUSED} macro, as shown in the example, or you can just ignore
+it.)
+
+@var{aux} is useful when you have some property of the data in the
+hash table that's both constant and needed for hashing or comparisons,
+but which is not stored in the data items themselves. For example, if
+the items in a hash table contain fixed-length strings, but the items
+themselves don't indicate what that fixed length is, you could pass
+the length as an @var{aux} parameter.
+
+@node Hash Synchronization
+@subsection Synchronization
+
+The hash table does not do any internal synchronization. It is the
+caller's responsibility to synchronize calls to hash table functions.
+In general, any number of functions that examine but do not modify the
+hash table, such as @func{hash_find} or @func{hash_next}, may execute
+simultaneously. However, these function cannot safely execute at the
+same time as any function that may modify a given hash table, such as
+@func{hash_insert} or @func{hash_delete}, nor may more than one function
+that can modify a given hash table execute safely at once.
+
+It is also the caller's responsibility to synchronize access to data in
+hash table elements. How to synchronize access to this data depends on
+how it is designed and organized, as with any other data structure.
+