From: Ben Pfaff Date: Tue, 28 Sep 2004 07:40:29 +0000 (+0000) Subject: Update docs. X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=c574297b7acbcbf04d128113cf91dbbcc1730f9c Update docs. --- diff --git a/doc/Makefile b/doc/Makefile index b2e8a43..446b2b3 100644 --- a/doc/Makefile +++ b/doc/Makefile @@ -1,6 +1,6 @@ -TEXIS = projects.texi intro.texi threads.texi mlfqs.texi userprog.texi \ -vm.texi filesys.texi references.texi standards.texi doc.texi devel.texi \ -debug.texi +TEXIS = projects.texi intro.texi tour.texi threads.texi mlfqs.texi \ +userprog.texi vm.texi filesys.texi references.texi standards.texi \ +doc.texi devel.texi debug.texi all: projects.html projects.info diff --git a/doc/debug.texi b/doc/debug.texi index 754f5bc..68318fd 100644 --- a/doc/debug.texi +++ b/doc/debug.texi @@ -1,4 +1,4 @@ -@node Debugging Tools, , Project Documentation, Top +@node Debugging Tools, Development Tools, Project Documentation, Top @appendix Debugging Tools Many tools lie at your disposal for debugging Pintos. This appendix @@ -15,23 +15,23 @@ introduces you to a few of them. @end menu @node printf -@section @code{printf()} +@section @func{printf} -Don't underestimate the value of @code{printf()}. The way -@code{printf()} is implemented in Pintos, you can call it from +Don't underestimate the value of @func{printf}. The way +@func{printf} is implemented in Pintos, you can call it from practically anywhere in the kernel, whether it's in a kernel thread or an interrupt handler, almost regardless of what locks are held. -@code{printf()} isn't useful just because it can print data members. +@func{printf} isn't useful just because it can print data members. It can also help figure out when and where something goes wrong, even when the kernel crashes or panics without a useful error message. The -strategy is to sprinkle calls to @code{print()} with different strings +strategy is to sprinkle calls to @func{print} with different strings (e.g.@: @code{"1\n"}, @code{"2\n"}, @dots{}) throughout the pieces of code you suspect are failing. If you don't even see @code{1} printed, then something bad happened before that point, if you see @code{1} but not @code{2}, then something bad happened between those two points, and so on. Based on what you learn, you can then insert more -@code{printf()} calls in the new, smaller region of code you suspect. +@func{printf} calls in the new, smaller region of code you suspect. Eventually you can narrow the problem down to a single statement. @node ASSERT @@ -55,8 +55,8 @@ backtraces below for more information. @section @code{DEBUG} The @code{DEBUG} macro, also defined in @code{}, is a sort of -conditional @code{printf()}. It takes as its arguments the name of a -``message class'' and a @code{printf()}-like format string and +conditional @func{printf}. It takes as its arguments the name of a +``message class'' and a @func{printf}-like format string and arguments. The message class is used to filter the messages that are actually displayed. You select the messages to display on the Pintos command line using the @option{-d} option. This allows you to easily @@ -82,7 +82,7 @@ pintos run -d thread When the kernel panics, it prints a ``backtrace,'' that is, a summary of how your program got where it is, as a list of addresses inside the functions that were running at the time of the panic. You can also -insert a call to @code{debug_backtrace()}, prototyped in +insert a call to @func{debug_backtrace}, prototyped in @file{}, at any point in your code. The addresses in a backtrace are listed as raw hexadecimal numbers, @@ -131,7 +131,7 @@ commands. If you issue the @samp{c} command, the Bochs BIOS will take control, load Pintos, and then Pintos will run in the usual way. You can pause the process at any point with @key{Ctrl+C}. If you want @command{gdb} to stop when Pintos starts running, set a breakpoint on -@code{main()} with the command @code{break main} before @samp{c}. +@func{main} with the command @code{break main} before @samp{c}. You can read the @command{gdb} manual by typing @code{info gdb} at a terminal command prompt, or you can view it in Emacs with the command @@ -203,8 +203,8 @@ put it in your @env{PATH}, and make sure that it is earlier than Of course, to get any good out of this you'll have to actually modify Bochs. Instructions for doing this are firmly out of the scope of this document. However, if you want to debug page faults as suggested -above, a good place to start adding @code{printf()}s is -@code{BX_CPU_C::dtranslate_linear()} in @file{cpu/paging.cc}. +above, a good place to start adding @func{printf}s is +@func{BX_CPU_C::dtranslate_linear} in @file{cpu/paging.cc}. @node Debugging Tips @section Tips @@ -222,4 +222,4 @@ Similarly, the block allocator in @file{threads/malloc.c} clears all the bytes in freed blocks to @t{0xcd}. The two bytes @t{0xcdcd} are a CPU opcode for ``invoke interrupt @t{0xcd},'' so @code{Interrupt 0xcd (unknown)} is a good sign that you tried to execute code in a -block freed with @code{free()}. +block freed with @func{free}. diff --git a/doc/devel.texi b/doc/devel.texi index df5d196..20af12f 100644 --- a/doc/devel.texi +++ b/doc/devel.texi @@ -1,8 +1,14 @@ -@node Development Tools +@node Development Tools, , Debugging Tools, Top @appendix Development Tools Here are some tools that you might find useful while developing code. +@menu +* Tags:: +* CVS:: +* VNC:: +@end menu + @node Tags @section Tags diff --git a/doc/doc.texi b/doc/doc.texi index 55a80f5..f3465fa 100644 --- a/doc/doc.texi +++ b/doc/doc.texi @@ -14,8 +14,8 @@ characters per line, with a hard limit of 80. @menu * README:: -* DESIGNDOC :: -* TESTCASE :: +* DESIGNDOC:: +* TESTCASE:: @end menu @node README @@ -30,7 +30,7 @@ dependencies, and so on. If you added extra credit features to your project, explain them concisely in the @file{README}. Otherwise, we're likely to miss them. -@node DESIGNDOC +@node DESIGNDOC @section @file{DESIGNDOC} This file is our primary tool for assessing your design. Therefore, @@ -65,7 +65,7 @@ Finally, please keep your @file{DESIGNDOC} as short as you can, without sacrificing key design decisions. You should be brief, yet complete. We don't want to read novels. -@node TESTCASE +@node TESTCASE @section @file{TESTCASE} The @file{TESTCASE} file should contain all the information about how @@ -94,13 +94,13 @@ Show us that you tested each part of your assignment. Clearly state in your @file{TESTCASE} file what each test is supposed to test. You should be testing not only the common case, but testing corner cases. Specify what criteria or issue is being tested. For -example, in testing @code{thread_join()} you would have specified that -you test @code{thread_join()} when it is called multiple times on the +example, in testing @func{thread_join} you would have specified that +you test @func{thread_join} when it is called multiple times on the same child thread. @item Make your tests as succinct as possible. Most students in the past -have done a great job with the testing of @code{thread_join()}, +have done a great job with the testing of @func{thread_join}, creating very succinct short tests. We like that. @item diff --git a/doc/filesys.texi b/doc/filesys.texi index d580a0d..da5f1e2 100644 --- a/doc/filesys.texi +++ b/doc/filesys.texi @@ -193,7 +193,7 @@ demonstrate the performance improvement. Note that write-behind makes your filesystem more fragile in the face of crashes. Therefore, you should implement some manner to periodically write all cached blocks to disk. If you have -@code{timer_sleep()} from the first project working, this is an +@func{timer_sleep} from the first project working, this is an excellent application for it. Likewise, read-ahead is only really useful when done asynchronously. @@ -372,7 +372,7 @@ End of directory Yes. Implementing @file{.} and @file{..} is extra credit, though. @item -@b{Should @code{remove()} also be able to remove directories?} +@b{Should @func{remove} also be able to remove directories?} Yes. The @code{remove} system call should handle removal of both regular files and directories. You may assume that directories can @@ -417,7 +417,7 @@ implementation of the buffer cache. Basically, you can't store a to read a @code{struct inode}, you'll have to get it either from the buffer cache or from disk. -If you look at @code{file_read_at()}, it uses the inode directly +If you look at @func{file_read_at}, it uses the inode directly without having first read in that sector from wherever it was in the storage hierarchy. You are no longer allowed to do this. You will need to change @code{file_read_at} (and similar functions) so that it diff --git a/doc/intro.texi b/doc/intro.texi index 94a1bd6..81b54fb 100644 --- a/doc/intro.texi +++ b/doc/intro.texi @@ -1,4 +1,4 @@ -@node Introduction, Project 1--Threads, Top, Top +@node Introduction, Pintos Tour, Top, Top @chapter Introduction Welcome to Pintos. Pintos is a simple operating system framework for diff --git a/doc/projects.texi b/doc/projects.texi index 3437dcc..b5b08f5 100644 --- a/doc/projects.texi +++ b/doc/projects.texi @@ -28,6 +28,14 @@ @end macro @end ifhtml +@macro func{name} +@code{\name\()} +@end macro + +@macro struct{name} +@code{struct \name\} +@end macro + @titlepage @title Pintos Projects @end titlepage @@ -41,6 +49,7 @@ @menu * Introduction:: +* Pintos Tour:: * Project 1--Threads:: * Project 2--User Programs:: * Project 3--Virtual Memory:: @@ -50,9 +59,11 @@ * Coding Standards:: * Project Documentation:: * Debugging Tools:: +* Development Tools:: @end menu @include intro.texi +@include tour.texi @include threads.texi @include userprog.texi @include vm.texi @@ -62,5 +73,6 @@ @include standards.texi @include doc.texi @include debug.texi +@include devel.texi @bye diff --git a/doc/standards.texi b/doc/standards.texi index b95d930..7af266e 100644 --- a/doc/standards.texi +++ b/doc/standards.texi @@ -70,7 +70,7 @@ There are a few exceptions: @itemize @bullet @item -Problem 1-2, @code{thread_join()}. Some other code expects +Problem 1-2, @func{thread_join}. Some other code expects @code{THREAD_JOIN_IMPLEMENTED} to be defined once you've implemented this function. @@ -131,7 +131,7 @@ macro giving its maximum value. @item @file{} is useful on its own, but it provides no way to pass -the types it defines to @code{printf()} and related functions. This +the types it defines to @func{printf} and related functions. This header provides macros to help with that. For every @code{int@var{n}_t} defined by @file{}, it provides macros @code{PRId@var{n}} and @code{PRIi@var{n}} for formatting values of @@ -153,7 +153,7 @@ above, you supply it yourself and follow it by any flags, field widths, etc. @item -The @file{printf()} function has some new type modifiers for printing +The @func{printf} function has some new type modifiers for printing standard types: @table @samp @@ -167,6 +167,9 @@ For @code{size_t} (e.g.@: @samp{%zu}). @item t For @code{ptrdiff_t} (e.g.@: @samp{%td}). @end table + +Pintos @func{printf} also implements a nonstandard @samp{'} flag that +group large numbers with commas to make them easier to read. @end table @node Unsafe String Functions @@ -177,37 +180,37 @@ A few of the string functions declared in the standard The worst offenders are intentionally not included in the Pintos C library: -@table @code -@item strcpy() +@table @func +@item strcpy When used carelessly this function can overflow the buffer reserved -for its output string. Use @code{strlcpy()} instead. Refer to +for its output string. Use @func{strlcpy} instead. Refer to comments in its source code in @code{lib/string.c} for documentation. -@item strncpy() +@item strncpy This function can leave its destination buffer without a null string terminator and it has performance problems besides. Again, use -@code{strlcpy()}. +@func{strlcpy}. -@item strcat() -Same issue as @code{strcpy()}, but substitute @code{strlcat()}. +@item strcat +Same issue as @func{strcpy}, but substitute @func{strlcat}. Again, refer to comments in its source code in @code{lib/string.c} for documentation. -@item strncat() +@item strncat The meaning of its buffer size argument often leads to problems. -Again, use @code{strlcat()}. +Again, use @func{strlcat}. -@item strtok() +@item strtok Uses global data, so it is unsafe in threaded programs such as -kernels. Use @code{strtok_r()} instead, and see its source code in +kernels. Use @func{strtok_r} instead, and see its source code in @code{lib/string.c} for documentation and an example. -@item sprintf() -Same issue as @code{strcpy()}. Use @code{snprintf()} instead. Refer +@item sprintf +Same issue as @func{strcpy}. Use @func{snprintf} instead. Refer to comments in @code{lib/stdio.h} for documentation. -@item vsprintf() -Same issue as @code{strcpy()}. Use @code{vsnprintf()} instead. +@item vsprintf +Same issue as @func{strcpy}. Use @func{vsnprintf} instead. @end table If you try to use any of these functions, you should get a hint from diff --git a/doc/threads.texi b/doc/threads.texi index 62e8a3e..96a9ca2 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -1,4 +1,4 @@ -@node Project 1--Threads, Project 2--User Programs, Introduction, Top +@node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top @chapter Project 1: Threads In this assignment, we give you a minimally functional thread system. @@ -11,6 +11,12 @@ You will be working in primarily in the @file{threads} directory for this assignment, with some work in the @file{devices} directory on the side. Compilation should be done in the @file{threads} directory. +Before you read the description of this project, you should read all +of the following sections: @ref{Introduction}, @ref{Threads Tour}, +@ref{Coding Standards}, @ref{Project Documentation}, @ref{Debugging +Tools}, and @ref{Development Tools}. To complete this project you +will also need to read @ref{Multilevel Feedback Scheduling}. + @menu * Understanding Threads:: * Project 1 Code:: @@ -35,7 +41,7 @@ However, there's a lot of magic going on in some of this code, so if you haven't already compiled and run the base system, as described in the introduction (@pxref{Introduction}), you should do so now. You can read through parts of the source code by hand to see what's going -on. If you like, you can add calls to @code{printf()} almost +on. If you like, you can add calls to @func{printf} 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 @@ -43,12 +49,12 @@ so on. @xref{i386-elf-gdb}, for more information. 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()}. The first time the thread is +argument to @func{thread_create}. The first time the thread is scheduled and runs, it will start from the beginning of that function and execute it in the context. When that function returns, that thread completes. Each thread, therefore, acts like a mini-program running -inside Pintos, with the function passed to @code{thread_create()} -acting like @code{main()}. +inside Pintos, with the function passed to @func{thread_create} +acting like @func{main}. At any given time, Pintos is running exactly one thread, with the others switched out. The scheduler decides which thread to run next @@ -65,16 +71,16 @@ thread we're switching to. Using the @command{gdb} debugger, slowly trace through a context switch to see what happens (@pxref{i386-elf-gdb}). You can set a -breakpoint on the @code{schedule()} function to start out, and then +breakpoint on the @func{schedule} function to start out, and then single-step from there. 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()}, another thread starts running, and the first +@func{switch_threads}, another thread starts running, and the first thing the new thread does is to return from -@code{switch_threads()}. We realize this comment will seem cryptic to +@func{switch_threads}. We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand -why the @code{switch_threads()} that gets called is different from the -@code{switch_threads()} that returns. +why the @func{switch_threads} that gets called is different from the +@func{switch_threads} that returns. @strong{Warning}: In Pintos, each thread is assigned a small, fixed-size execution stack just under @w{4 kB} in size. The kernel @@ -84,7 +90,7 @@ declare large data structures as non-static local variables, e.g. @samp{int buf[1000];}. Alternatives to stack allocation include the page allocator in @file{threads/palloc.c} and the block allocator in @file{threads/malloc.c}. Note that the page allocator doles out -@w{4 kB} chunks and that @code{malloc()} has a @w{2 kB} block size +@w{4 kB} chunks and that @func{malloc} has a @w{2 kB} block size limit. If you need larger chunks, consider using a linked structure instead. @@ -112,12 +118,12 @@ of the kernel image. Again, you should not need to look at this code or modify it, but it's here in case you're curious. @item start.S -Jumps to @code{main()}. +Jumps to @func{main}. @item init.c @itemx init.h -Kernel initialization, including @code{main()}, the kernel's ``main -program.'' You should look over @code{main()} at least to see what +Kernel initialization, including @func{main}, the kernel's ``main +program.'' You should look over @func{main} at least to see what gets initialized. @item thread.c @@ -138,7 +144,7 @@ pages. @item malloc.c @itemx malloc.h -A very simple implementation of @code{malloc()} and @code{free()} for +A very simple implementation of @func{malloc} and @func{free} for the kernel. @item interrupt.c @@ -191,13 +197,13 @@ modify this code in Problem 1-1. @item vga.c @itemx vga.h VGA display driver. Responsible for writing text to the screen. -You should have no need to look at this code. @code{printf()} will +You should have no need to look at this code. @func{printf} will call into the VGA display driver for you, so there's little reason to call this code yourself. @item serial.c @itemx serial.h -Serial port driver. Again, @code{printf()} calls this code for you, +Serial port driver. Again, @func{printf} calls this code for you, so you don't need to do so yourself. Feel free to look through it if you're curious. @@ -271,7 +277,7 @@ Hash table implementation. Likely to come in handy for project 3. @item kernel/console.c @itemx kernel/console.h -Implements @code{printf()} and a few other functions. +Implements @func{printf} and a few other functions. @end table @node Debugging versus Testing @@ -314,8 +320,8 @@ degree of confidence you should test your code with many seed values. There should be no busy-waiting in any of your solutions to this assignment. Furthermore, resist the temptation to directly disable -interrupts in your solution by calling @code{intr_disable()} or -@code{intr_set_level()}, although you may find doing so to be useful +interrupts in your solution by calling @func{intr_disable} or +@func{intr_set_level}, although you may find doing so to be useful while debugging. Instead, use semaphores, locks and condition variables to solve synchronization problems. Hint: read the comments in @file{threads/synch.h} if you're unsure what synchronization @@ -334,7 +340,7 @@ right. We don't give out solutions, so you're stuck with your Join code for the whole quarter. Problem 1-1 (Alarm Clock) could be very handy, but not strictly required in the future. The upshot of all this is that you should focus heavily on making sure that your -implementation of @code{thread_join()} works correctly, since if it's +implementation of @func{thread_join} works correctly, since if it's broken, you will need to fix it for future assignments. The other parts can be turned off in the future if you find you can't make them work quite right. @@ -349,7 +355,7 @@ Problem 1-4. @section Problem 1-1: Alarm Clock Improve the implementation of the timer device defined in -@file{devices/timer.c} by reimplementing @code{timer_sleep()}. +@file{devices/timer.c} by reimplementing @func{timer_sleep}. Threads call @code{timer_sleep(@var{x})} to suspend execution until time has advanced by at least @w{@var{x} timer ticks}. This is useful for threads that operate in real-time, for example, for @@ -365,8 +371,10 @@ advanced far enough. This is undesirable because it wastes time that could potentially be used more profitably by another thread. Your solution should not busy wait. -The argument to @code{timer_sleep()} is expressed in timer ticks, not -in milliseconds or some other unit. +The argument to @func{timer_sleep} is expressed in timer ticks, not +in milliseconds or another unit. There are @code{TIMER_FREQ} timer +ticks per second, where @code{TIMER_FREQ} is a macro defined in +@code{devices/timer.h}. @node Problem 1-2 Join @section Problem 1-2: Join @@ -375,25 +383,25 @@ Implement @code{thread_join(tid_t)} in @file{threads/thread.c}. There is already a prototype for it in @file{threads/thread.h}, which you should not change. This function causes the currently running thread to block until the thread whose thread id is passed as an argument -exits. If A is the running thread and B is the argument, then we say -that ``A joins B'' in this case. +exits. If @var{A} is the running thread and @var{B} is the argument, +then we say that ``@var{A} joins @var{B}.'' Incidentally, we don't use @code{struct thread *} as -@file{thread_join()}'s parameter type because a thread pointer is not +@func{thread_join}'s parameter type because a thread pointer is not unique over time. That is, when a thread dies, its memory may be, whether immediately or much later, reused for another thread. If thread A over time had two children B and C that were stored at the -same address, then @code{thread_join(@r{B})} and -@code{thread_join(@r{C})} would be ambiguous. Introducing a thread id -or @dfn{tid}, represented by type @code{tid_t}, that is intentionally -unique over time solves the problem. The provided code uses an -@code{int} for @code{tid_t}, but you may decide you prefer to use some -other type. - -The model for @code{thread_join()} is the @command{wait} system call +same address, then @code{thread_join(@var{B})} and +@code{thread_join(@var{C})} would be ambiguous. Introducing a thread +id or @dfn{tid}, represented by type @code{tid_t}, that is +intentionally unique over time solves the problem. The provided code +uses an @code{int} for @code{tid_t}, but you may decide you prefer to +use some other type. + +The model for @func{thread_join} is the @command{wait} system call in Unix-like systems. (Try reading the manpages.) That system call can only be used by a parent process to wait for a child's death. You -should implement @code{thread_join()} to have the same restriction. +should implement @func{thread_join} to have the same restriction. That is, a thread may only join its immediate children. A thread need not ever be joined. Your solution should properly free @@ -407,20 +415,21 @@ multiple times is equivalent to joining it once, because T has already exited at the time of the later joins. Thus, joins on T after the first should return immediately. -Calling @code{thread_join()} on an thread that is not the caller's +Calling @func{thread_join} on an thread that is not the caller's child should cause the caller to return immediately. -Consider all the ways a join can occur: nested joins (A joins B when B -is joined on C), multiple joins (A joins B, then A joins C), and so -on. Does your join work if @code{thread_join()} is called on a thread -that has not yet been scheduled for the first time? You should handle -all of these cases. Write test code that demonstrates the cases your -join works for. Don't overdo the output volume, please! +Consider all the ways a join can occur: nested joins (@var{A} joins +@var{B}, then @var{B} joins @var{C}), multiple joins (@var{A} joins +@var{B}, then @var{A} joins @var{C}), and so on. Does your join work +if @func{thread_join} is called on a thread that has not yet been +scheduled for the first time? You should handle all of these cases. +Write test code that demonstrates the cases your join works for. +Don't overdo the output volume, please! Be careful to program this function correctly. You will need its functionality for project 2. -Once you've implemented @code{thread_join()}, define +Once you've implemented @func{thread_join}, define @code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}. @xref{Conditional Compilation}, for more information. @@ -429,15 +438,15 @@ Once you've implemented @code{thread_join()}, define Implement priority scheduling in Pintos. Priority scheduling is a key building block for real-time systems. Implement functions -@code{thread_set_priority()} to set the priority of the running thread -and @code{thread_get_priority()} to get the running thread's priority. +@func{thread_set_priority} to set the priority of the running thread +and @func{thread_get_priority} to get the running thread's priority. (A thread can examine and modify only its own priority.) There are already prototypes for these functions in @file{threads/thread.h}, which you should not change. Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59). The initial thread priority is passed as an argument to -@code{thread_create()}. If there's no reason to choose another +@func{thread_create}. If there's no reason to choose another priority, use @code{PRI_DEFAULT} (29). The @code{PRI_} macros are defined in @file{threads/thread.h}, and you should not change their values. @@ -453,7 +462,7 @@ on a lock, semaphore, or condition variable. One issue with priority scheduling is ``priority inversion'': if a high priority thread needs to wait for a low priority thread (for instance, for a lock held by a low priority thread, or in -@code{thread_join()} for a thread to complete), and a middle priority +@func{thread_join} for a thread to complete), and a middle priority thread is on the ready list, then the high priority thread will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is to have the waiting thread @@ -465,9 +474,10 @@ You will need to account for all different orders that priority donation and inversion can occur. Be sure to handle multiple donations, in which multiple priorities are donated to a thread. You must also handle nested donation: given high, medium, and low priority -threads H, M, and L, respectively, if H is waiting on a lock that M -holds and M is waiting on a lock that L holds, then both M and L -should be boosted to H's priority. +threads @var{H}, @var{M}, and @var{L}, respectively, if @var{H} is +waiting on a lock that @var{M} holds and @var{M} is waiting on a lock +that @var{L} holds, then both @var{M} and @var{L} should be boosted to +@var{H}'s priority. You only need to implement priority donation when a thread is waiting for a lock held by a lower-priority thread. You do not need to @@ -599,22 +609,22 @@ handler?} As you've discovered, you cannot sleep in an external interrupt handler. Since many lock, semaphore, and condition variable functions attempt to sleep, you won't be able to call those in -@code{timer_interrupt()}. You may still use those that never sleep. +@func{timer_interrupt}. You may still use those that never sleep. Having said that, you need to make sure that global data does not get updated by multiple threads simultaneously executing -@code{timer_sleep()}. Here are some pieces of information to think +@func{timer_sleep}. Here are some pieces of information to think about: @enumerate a @item -Interrupts are turned off while @code{timer_interrupt()} runs. This -means that @code{timer_interrupt()} will not be interrupted by a -thread running in @code{timer_sleep()}. +Interrupts are turned off while @func{timer_interrupt} runs. This +means that @func{timer_interrupt} will not be interrupted by a +thread running in @func{timer_sleep}. @item -A thread in @code{timer_sleep()}, however, can be interrupted by a -call to @code{timer_interrupt()}, except when that thread has turned +A thread in @func{timer_sleep}, however, can be interrupted by a +call to @func{timer_interrupt}, except when that thread has turned off interrupts. @item @@ -676,13 +686,13 @@ scheduler should then run the highest priority thread on the ready list. @item -@b{If a thread calls @code{thread_yield()} and then it turns out that +@b{If a thread calls @func{thread_yield} and then it turns out that it has higher priority than any other threads, does the high-priority thread continue running?} Yes. If there is a single highest-priority thread, it continues running until it blocks or finishes, even if it calls -@code{thread_yield()}. +@func{thread_yield}. @item @b{If the highest priority thread is added to the ready to run list it @@ -745,10 +755,10 @@ Thread 1 goes. @end example This happens because context switches are being invoked by the test -when it explicitly calls @code{thread_yield()}. However, the time +when it explicitly calls @func{thread_yield}. However, the time slice timer is still alive and so, every tick (by default), thread 1 -gets switched out (caused by @code{timer_interrupt()} calling -@code{intr_yield_on_return()}) before it gets a chance to run its +gets switched out (caused by @func{timer_interrupt} calling +@func{intr_yield_on_return}) before it gets a chance to run its mainline. It is by coincidence that Thread 1 is the one that gets skipped in our example. If we use a different jitter value, the same behavior is seen where a thread gets started and switched out @@ -766,7 +776,7 @@ The correct behavior is to immediately yield the processor. Your solution must act this way. @item -@b{What should @code{thread_get_priority()} return in a thread while +@b{What should @func{thread_get_priority} return in a thread while its priority has been increased by a donation?} The higher (donated) priority. diff --git a/doc/tour.texi b/doc/tour.texi index abbcb69..41fde25 100644 --- a/doc/tour.texi +++ b/doc/tour.texi @@ -1,4 +1,4 @@ -@node Pintos Tour +@node Pintos Tour, Project 1--Threads, Introduction, Top @chapter A Tour Through Pintos This chapter is a brief tour through the Pintos code. It covers the @@ -6,12 +6,25 @@ 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 corresponding project. +Hint: try using ``tags'' to follow along with references to function +and variable names (@pxref{Tags}). + +@menu +* Pintos Loading:: +* Threads Tour:: +@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 @@ -77,7 +90,7 @@ 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 -@code{main()}, which never returns. +@func{main}, which never returns. There's one more trick to the loader: the Pintos kernel command line is stored in the boot loader. The @command{pintos} program actually @@ -90,18 +103,20 @@ and effective. @node Kernel Initialization @subsection Kernel Initialization -The kernel proper starts with the @code{main()} function. The -@code{main()} function is written in C, as will be most of the code we +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 @code{main()} starts, the system is in a pretty raw state. We're +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 @code{main()} function consists primarily of calls -into other Pintos modules' initialization functions, which are -typically named @code{@var{module}_init()}, where @var{module} is the -module's name. +ready. Thus, the @func{main} function consists primarily of calls +into other Pintos modules' initialization functions. You should +notice that 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 @code{ram_init()}. The first step +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 C, whenever you declare a variable outside a function without providing an @@ -109,12 +124,248 @@ initializer, that variable goes into the BSS.@footnote{This isn't actually required by the ANSI C standard, but it is the case with most implementations of C on most machines.} Because it's all zeros, the BSS isn't stored in the image that the loader brought into memory. We -just use @code{memset()} to zero it out. The other task of -@code{ram_init()} is to read out the machine's memory size from where +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 below, 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{argv_init} to parse the kernel command line. +This entails reading the command line out of the loader and updating +global variables appropriately. + +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. @func{argv_init} might already have done this (if +the user specified @option{-rs} on the @command{pintos} command line) +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, then @func{timer_init} and +@func{kbd_init} prepare us to handle 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. +Interrupt-driven serial port I/O is also possible now, so we use +@func{serial_init_queue} to switch to that mode. + +If the filesystem is compiled in, as it will be in project 2 and +later, we now initialize the disks with @func{disk_init}, then the +filesystem with @func{filesys_init}, and run any operations that were +requested on the kernel command line with @func{fsutil_run}. +Boot is complete, so we print a message. + +For project 1, now we execute @func{test}, which runs whatever test is +currently compiled into the kernel. For later projects, we will +instead run a user program and wait for it to complete. + +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 Tour @section Threads + +@menu +* struct thread:: +@end menu + +@node struct thread +@subsection @struct{thread} + +The main Pintos data structure for threads is @struct{thread}, +declared in @file{threads/thread.h}. @struct{thread} has these +members with the given type: + +@table @code +@item 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. + +@item enum thread_status status; +The thread's state, one of these: + +@table @code +@item THREAD_RUNNING +The thread is running. Exactly one thread is running at a given time. +@func{thread_current} returns the running thread. + +@item 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}. + +@item 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}. + +@item THREAD_DYING +The thread will be destroyed by the scheduler after switching to the +next thread. +@end table + +@item char name[16]; +The thread's name as a string, or at least the first few characters of +it. + +@item 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. + +@item int priority; +A thread priority, ranging from the lowest possible priority +@code{PRI_MIN} (0) to the highest possible priority @code{PRI_MAX} +(59). Pintos as provided ignores thread priorities, but you will +implement priority scheduling in problem 1-3 (@pxref{Problem 1-3 +Priority Scheduling}). + +@item 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 the Pintos doubly linked list ADT. + +@item uint32_t *pagedir; +Only present in project 2 and later. + +@item 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. +See below for more information. +@end table + +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 + 4 kB +---------------------------------+ + | kernel stack | + | | | + | | | + | V | + | grows downward | + | | + | | + | | + | | + | | + | | + | | + | | + +---------------------------------+ + | magic | + | : | + | : | + | name | + | status | + 0 kB +---------------------------------+ +@end example + +The upshot of this is twofold. 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. Our 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. + +This brings us to the purpose of @struct{thread}'s @code{magic} +member. If a thread's stack does overflow, then @code{magic} will be +the first member of @struct{thread} to be overwritten, because it is +closest to the kernel stack. Thus, some of the thread functions +(notably @func{thread_current}) check that @code{magic} has the proper +value. + +@node Thread Functions +@subsection Thread Functions + +@file{threads/thread.c} implements several public functions for +thread support. Let's take a look at some of them: + +@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 sets up the initial +thread's stack at the end of a page. 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 enables the scheduler because +processes are rescheduled in the return path from the timer +interrupt. FIXME +@end deftypefun + +@deftypefun void thread_tick (void) +Called by @func{timer_interrupt} on every timer interrupt. Just +increments counters that keep track of how often various kinds of +threads run. +@end deftypefun + +@deftypefun void thread_print_stats (void) +Prints the statistics kept by @func{thread_ticK] to the console. +Called when Pintos is terminating. +@end deftypefun + +@deftypefun void 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} works by allocating a page for the thread's +@struct{thread} and stack and initializing its members, then setting +up a set of fake stack frames for it (we'll talk more about this +later). The thread was initialized in the blocked state, so the final +action before returning is to unblock it, allowing the new thread to +be scheduled. +@end deftypefun diff --git a/doc/userprog.texi b/doc/userprog.texi index 5c0ee72..72ab256 100644 --- a/doc/userprog.texi +++ b/doc/userprog.texi @@ -14,7 +14,7 @@ assignment. However, you will also be interacting with almost every other part of the code for this assignment. We will describe the relevant parts below. If you are confident in your HW1 code, you can build on top of it. However, if you wish you can start with a fresh -copy of the code and re-implement @code{thread_join()}, which is the +copy of the code and re-implement @func{thread_join}, which is the only part of project #1 required for this assignment. Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h} (@pxref{Conditional Compilation}). @@ -68,7 +68,7 @@ Loads ELF binaries and starts processes. A simple manager for 80@var{x} page directories and page tables. Although you probably won't want to modify this code for this project, you may want to call some of its functions. In particular, -@code{pagedir_get_page()} may be helpful for accessing user memory. +@func{pagedir_get_page} may be helpful for accessing user memory. @item syscall.c @itemx syscall.h @@ -87,7 +87,7 @@ distinction between them, although the Intel processor manuals define them slightly differently on 80@var{x}86.} These files handle exceptions. Currently all exceptions simply print a message and terminate the process. Some, but not all, solutions to project 2 -require modifying @code{page_fault()} in this file. +require modifying @func{page_fault} in this file. @item gdt.c @itemx gdt.c @@ -163,7 +163,7 @@ Also, @option{-ls} lists the files in the file system and @option{-p Pintos can run normal C programs. In fact, it can run any program you want, provided it's compiled into the proper file format, and uses -only the system calls you implement. (For example, @code{malloc()} +only the system calls you implement. (For example, @func{malloc} makes use of functionality that isn't provided by any of the syscalls we require you to support.) The only other limitation is that Pintos can't run programs using floating point operations, since it doesn't @@ -203,7 +203,7 @@ User virtual memory is per-process. Conceptually, each process is free to use the entire space of user virtual memory however it chooses. When the kernel switches from one process to another, it also switches user virtual address spaces by switching the processor's -page directory base register (see @code{pagedir_activate() in +page directory base register (see @func{pagedir_activate in @file{userprog/pagedir.c}}. Kernel virtual memory is global. It is always mapped the same way, @@ -216,7 +216,7 @@ physical memory. User programs can only access user virtual memory. An attempt to access kernel virtual memory will cause a page fault, handled by -@code{page_fault()} in @file{userprog/exception.c}, and the process +@func{page_fault} in @file{userprog/exception.c}, and the process will be terminated. Kernel threads can access both kernel virtual memory and, if a user process is running, the user virtual memory of the running process. However, even in the kernel, an attempt to @@ -243,11 +243,11 @@ first process. @node Problem 2-1 Argument Passing @section Problem 2-1: Argument Passing -Currently, @code{process_execute()} does not support passing arguments +Currently, @func{process_execute} does not support passing arguments to new processes. UNIX and other operating systems do allow passing command line arguments to a program, which accesses them via the argc, argv arguments to main. You must implement this functionality by -extending @code{process_execute()} so that instead of simply taking a +extending @func{process_execute} so that instead of simply taking a program file name, it can take a program name with arguments as a single string. That is, @code{process_execute("grep foo *.c")} should be a legal call. @xref{80x86 Calling Convention}, for information on @@ -371,7 +371,7 @@ is not safe to call into the filesystem code provided in the recommend adding a single lock that controls access to the filesystem code. You should acquire this lock before calling any functions in the @file{filesys} directory, and release it afterward. Don't forget -that @file{process_execute()} also accesses files. @strong{For now, we +that @func{process_execute} also accesses files. @strong{For now, we recommend against modifying code in the @file{filesys} directory.} We have provided you a function for each system call in @@ -394,7 +394,7 @@ exception is a call to the @code{halt} system call. @item @b{Do we need a working project 1 to implement project 2?} -You may find the code for @code{thread_join()} to be useful in +You may find the code for @func{thread_join} to be useful in implementing the join syscall, but besides that, you can use the original code provided for project 1. @@ -427,8 +427,8 @@ You need to modify @file{tests/Makefile}. @b{What's the difference between @code{tid_t} and @code{pid_t}?} A @code{tid_t} identifies a kernel thread, which may have a user -process running in it (if created with @code{process_execute()}) or not -(if created with @code{thread_create()}). It is a data type used only +process running in it (if created with @func{process_execute}) or not +(if created with @func{thread_create}). It is a data type used only in the kernel. A @code{pid_t} identifies a user process. It is used by user @@ -463,7 +463,7 @@ simplest way to handle user memory access. The second method is to ``assume and react'': directly dereference user pointers, after checking that they point below @code{PHYS_BASE}. Invalid user pointers will then cause a ``page fault'' that you can -handle by modifying the code for @code{page_fault()} in +handle by modifying the code for @func{page_fault} in @file{userprog/exception.cc}. This technique is normally faster because it takes advantage of the processor's MMU, so it tends to be used in real kernels (including Linux). @@ -500,7 +500,7 @@ static inline bool put_user (uint8_t *udst, uint8_t byte) @{ Each of these functions assumes that the user address has already been verified to be below @code{PHYS_BASE}. They also assume that you've -modified @code{page_fault()} so that a page fault in the kernel causes +modified @func{page_fault} so that a page fault in the kernel causes @code{eax} to be set to 0 and its former value copied into @code{eip}. @item @@ -557,7 +557,7 @@ defend it in your @file{DESIGNDOC}. @b{How do I parse all these argument strings?} You're welcome to use any technique you please, as long as it works. -If you're lost, look at @code{strtok_r()}, prototyped in +If you're lost, look at @func{strtok_r}, prototyped in @file{lib/string.h} and implemented with thorough comments in @file{lib/string.c}. You can find more about it by looking at the man page (run @code{man strtok_r} at the prompt). @@ -586,10 +586,10 @@ simply via recompilation. @enumerate 1 @item -@b{What should I do with the parameter passed to @code{exit()}?} +@b{What should I do with the parameter passed to @func{exit}?} This value, the exit status of the process, must be returned to the -thread's parent when @code{join()} is called. +thread's parent when @func{join} is called. @item @b{Can I just cast a pointer to a @code{struct file} object to get a @@ -688,20 +688,20 @@ some of your caches. This is why inlining code can be much faster. @end menu @node Argument Passing to main -@subsection Argument Passing to @code{main()} +@subsection Argument Passing to @func{main} -In @code{main()}'s case, there is no caller to prepare the stack +In @func{main}'s case, there is no caller to prepare the stack before it runs. Therefore, the kernel needs to do it. Fortunately, since there's no caller, there are no registers to save, no return address to deal with, etc. The only difficult detail to take care of, -after loading the code, is putting the arguments to @code{main()} on +after loading the code, is putting the arguments to @func{main} on the stack. (The above is a small lie: most compilers will emit code where main isn't strictly speaking the first function. This isn't an important detail. If you want to look into it more, try disassembling a program and looking around a bit. However, you can just act as if -@code{main()} is the very first function called.) +@func{main} is the very first function called.) Pintos is written for the 80@var{x}86 architecture. Therefore, we need to adhere to the 80@var{x}86 calling convention. Basically, you @@ -712,7 +712,7 @@ have a caller, its stack frame must have the same layout as any other function's. The program will assume that the stack has been laid out this way when it begins running. -So, what are the arguments to @code{main()}? Just two: an @samp{int} +So, what are the arguments to @func{main}? Just two: an @samp{int} (@code{argc}) and a @samp{char **} (@code{argv}). @code{argv} is an array of strings, and @code{argc} is the number of strings in that array. However, the hard part isn't these two things. The hard part @@ -762,7 +762,7 @@ Then we push @code{argv} (that is, the address of the first element of the @code{argv} array) onto the stack, along with the length of the argument vector (@code{argc}, 4 in this example). This must also be done in this order, since @code{argc} is the first argument to -@code{main()} and therefore is on first (smaller address) on the +@func{main} and therefore is on first (smaller address) on the stack. Finally, we push a fake ``return address'' and leave the stack pointer to point to its location. @@ -802,7 +802,7 @@ As shown above, your code should start the stack at the very top of the user virtual address space, in the page just below virtual address @code{PHYS_BASE} (defined in @file{threads/mmu.h}). -You may find the non-standard @code{hex_dump()} function, declared in +You may find the non-standard @func{hex_dump} function, declared in @file{}, useful for debugging your argument passing code. Here's what it would show in the above example, given that @code{PHYS_BASE} is @t{0xc0000000}: @@ -838,11 +838,11 @@ interrupt. The normal calling convention pushes function arguments on the stack from right to left and the stack grows downward. Thus, when the -system call handler @code{syscall_handler()} gets control, the system +system call handler @func{syscall_handler} gets control, the system call number is in the 32-bit word at the caller's stack pointer, the first argument is in the 32-bit word at the next higher address, and so on. The caller's stack pointer is accessible to -@code{syscall_handler()} as the @samp{esp} member of the @code{struct +@func{syscall_handler} as the @samp{esp} member of the @code{struct intr_frame} passed to it. Here's an example stack frame for calling a system call numbered 10 diff --git a/doc/vm.texi b/doc/vm.texi index 34109cf..bb87e02 100644 --- a/doc/vm.texi +++ b/doc/vm.texi @@ -77,7 +77,7 @@ table contained all the virtual-to-physical translations for the process. Whenever the processor needed to look up a translation, it consulted the page table. As long as the process only accessed memory that it didn't own, all was well. If the process accessed -memory it didn't own, it ``page faulted'' and @code{page_fault()} +memory it didn't own, it ``page faulted'' and @func{page_fault} terminated the process. When we implement virtual memory, the rules have to change. A page @@ -269,7 +269,7 @@ need this data structure until part 2, but planning ahead is a good idea. @end itemize -The page fault handler, @code{page_fault()} in +The page fault handler, @func{page_fault} in @file{threads/exception.c}, needs to do roughly the following: @enumerate 1 @@ -304,11 +304,11 @@ probably want to leave the code that reads the pages from disk, but use your new page table management code to construct the page tables only as page faults occur for them. -You should use the @code{palloc_get_page()} function to get the page +You should use the @func{palloc_get_page} function to get the page frames that you use for storing user virtual pages. Be sure to pass the @code{PAL_USER} flag to this function when you do so, because that allocates pages from a ``user pool'' separate from the ``kernel pool'' -that other calls to @code{palloc_get_page()} make. +that other calls to @func{palloc_get_page} make. There are many possible ways to implement virtual memory. The above is simply an outline of our suggested implementation. @@ -359,7 +359,7 @@ file itself as backing store for read-only segments, since these segments won't change. There are a few special cases. Look at the loop in -@code{load_segment()} in @file{userprog/process.c}. Each time +@func{load_segment} in @file{userprog/process.c}. Each time around the loop, @code{read_bytes} represents the number of bytes to read from the executable file and @code{zero_bytes} represents the number of bytes to initialize to zero following the bytes read. The two @@ -525,7 +525,7 @@ to any of the TA's office hours for further clarification. for?} In simple cases you won't have any need for the @var{aux} parameters. -In these cases you can just pass a null pointer to @code{hash_init()} +In these cases you can 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 @@ -607,10 +607,10 @@ Make a reasonable decision and document it in your code and in your design document. Please make sure to justify your decision. @item -@b{Why do I need to pass @code{PAL_USER} to @code{palloc_get_page()} +@b{Why do I need to pass @code{PAL_USER} to @func{palloc_get_page} when I allocate physical page frames?} -You can layer some other allocator on top of @code{palloc_get_page()} +You can layer some other allocator on top of @func{palloc_get_page} if you like, but it should be the underlying mechanism, directly or indirectly, for two reasons. First, running out of pages in the user pool just causes user programs to page, but running out of pages in