Rename schedule_tail() to thread_schedule_tail().
[pintos-anon] / doc / reference.texi
1 @node Reference Guide
2 @appendix Reference Guide
3
4 This chapter is a reference for the Pintos code.  It covers the
5 entire code base, but you'll only be using Pintos one part at a time,
6 so you may find that you want to read each part as you work on the
7 project where it becomes important.
8
9 (Actually, the reference guide is currently incomplete.)
10
11 We recommend using ``tags'' to follow along with references to function
12 and variable names (@pxref{Tags}).
13
14 @menu
15 * Pintos Loading::              
16 * Threads::                     
17 * Synchronization::             
18 * Interrupt Handling::          
19 * Memory Allocation::           
20 * Virtual Addresses::           
21 * Page Table::                  
22 * Hash Table::                  
23 @end menu
24
25 @node Pintos Loading
26 @section Loading
27
28 This section covers the Pintos loader and basic kernel
29 initialization.
30
31 @menu
32 * Pintos Loader::               
33 * Kernel Initialization::       
34 @end menu
35
36 @node Pintos Loader
37 @subsection The Loader
38
39 The first part of Pintos that runs is the loader, in
40 @file{threads/loader.S}.  The PC BIOS loads the loader into memory.
41 The loader, in turn, is responsible for initializing the CPU, loading
42 the rest of Pintos into memory, and then jumping to its start.  It's
43 not important to understand exactly what the loader does, but if
44 you're interested, read on.  You should probably read along with the
45 loader's source.  You should also understand the basics of the
46 80@var{x}86 architecture as described by chapter 3, ``Basic Execution
47 Environment,'' of @bibref{IA32-v1}.
48
49 Because the PC BIOS loads the loader, the loader has to play by the
50 BIOS's rules.  In particular, the BIOS only loads 512 bytes (one disk
51 sector) into memory.  This is a severe restriction and it means that,
52 practically speaking, the loader has to be written in assembly
53 language.
54
55 The Pintos loader first initializes the CPU.  The first important part of
56 this is to enable the A20 line, that is, the CPU's address line
57 numbered 20.  For historical reasons, PCs boot with this address
58 line fixed at 0, which means that attempts to access memory beyond the
59 first 1 MB (2 raised to the 20th power) will fail.  Pintos wants to
60 access more memory than this, so we have to enable it.
61
62 Next, the loader asks the BIOS for the PC's memory size.  Again for
63 historical reasons, the function that we call in the BIOS to do this
64 can only detect up to 64 MB of RAM, so that's the practical limit that
65 Pintos can support.  The memory size is stashed away in a location in
66 the loader that the kernel can read after it boots.
67
68 Third, the loader creates a basic page table.  This page table maps
69 the 64 MB at the base of virtual memory (starting at virtual address
70 0) directly to the identical physical addresses.  It also maps the
71 same physical memory starting at virtual address
72 @code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB).  The
73 Pintos kernel only wants the latter mapping, but there's a
74 chicken-and-egg problem if we don't include the former: our current
75 virtual address is roughly @t{0x7c00}, the location where the BIOS
76 loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
77 page table, but if we turn on the page table without jumping there,
78 then we've just pulled the rug out from under ourselves.
79
80 After the page table is initialized, we load the CPU's control
81 registers to turn on protected mode and paging, and then we set up the
82 segment registers.  We aren't yet equipped to handle interrupts in
83 protected mode, so we disable interrupts.
84
85 Finally it's time to load the kernel from disk.  We use a simple but
86 inflexible method to do this: we program the IDE disk
87 controller directly.  We assume that the kernel is stored starting
88 from the second sector of the first IDE disk (the first sector normally
89 contains the boot loader).  We also assume that the BIOS has
90 already set up the IDE controller for us.  We read
91 @code{KERNEL_LOAD_PAGES} pages of data (4 kB per page) from the disk directly
92 into virtual memory, starting @code{LOADER_KERN_BASE} bytes past
93 @code{LOADER_PHYS_BASE}, which by default means that we load the
94 kernel starting 1 MB into physical memory.
95
96 Then we jump to the start of the compiled kernel image.  Using the
97 ``linker script'' in @file{threads/kernel.lds.S}, the kernel has
98 arranged to begin with the assembly module
99 @file{threads/start.S}.  This assembly module just calls
100 @func{main}, which never returns.
101
102 There's one more trick: the Pintos kernel command line
103 is stored in the boot loader.  The @command{pintos} program actually
104 modifies a copy of the boot loader on disk each time it runs the kernel,
105 putting
106 in whatever command line arguments the user supplies to the kernel,
107 and then the kernel at boot time reads those arguments out of the boot
108 loader in memory.  This is not an elegant solution, but it is simple
109 and effective.
110
111 @node Kernel Initialization
112 @subsection Kernel Initialization
113
114 The kernel proper starts with the @func{main} function.  The
115 @func{main} function is written in C, as will be most of the code we
116 encounter in Pintos from here on out.
117
118 When @func{main} starts, the system is in a pretty raw state.  We're
119 in 32-bit protected mode with paging enabled, but hardly anything else is
120 ready.  Thus, the @func{main} function consists primarily of calls
121 into other Pintos modules' initialization functions.
122 These are usually named @func{@var{module}_init}, where
123 @var{module} is the module's name, @file{@var{module}.c} is the
124 module's source code, and @file{@var{module}.h} is the module's
125 header.
126
127 First we initialize kernel RAM in @func{ram_init}.  The first step
128 is to clear out the kernel's so-called ``BSS'' segment.  The BSS is a
129 segment that should be initialized to all zeros.  In most C
130 implementations, whenever you
131 declare a variable outside a function without providing an
132 initializer, that variable goes into the BSS.  Because it's all zeros, the
133 BSS isn't stored in the image that the loader brought into memory.  We
134 just use @func{memset} to zero it out.  The other task of
135 @func{ram_init} is to read out the machine's memory size from where
136 the loader stored it and put it into the @code{ram_pages} variable for
137 later use.
138
139 Next, @func{main} calls @func{read_command_line} to break the kernel command
140 line into arguments, then @func{parse_options} to read any options at
141 the beginning of the command line.  (Actions specified on the
142 command line execute later.)
143
144 @func{thread_init} initializes the thread system.  We will defer full
145 discussion to our discussion of Pintos threads below.  It is called so
146 early in initialization because a valid thread structure is a
147 prerequisite for acquiring a lock, and lock acquisition in turn is
148 important to other Pintos subsystems.  Then we initialize the console
149 and print a startup message to the console.
150
151 The next block of functions we call initializes the kernel's memory
152 system.  @func{palloc_init} sets up the kernel page allocator, which
153 doles out memory one or more pages at a time (@pxref{Page Allocator}).
154 @func{malloc_init} sets
155 up the allocator that handles allocations of arbitrary-size blocks of
156 memory (@pxref{Block Allocator}).
157 @func{paging_init} sets up a page table for the kernel (@pxref{Page
158 Table}).
159
160 In projects 2 and later, @func{main} also calls @func{tss_init} and
161 @func{gdt_init}.
162
163 The next set of calls initializes the interrupt system.
164 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
165 (IDT) to ready it for interrupt handling (@pxref{Interrupt
166 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
167 handling timer interrupts and keyboard interrupts, respectively. 
168 @func{input_init} sets up to merge serial and keyboard input into one
169 stream.  In
170 projects 2 and later, we also prepare to handle interrupts caused by
171 user programs using @func{exception_init} and @func{syscall_init}.
172
173 Now that interrupts are set up, we can start the scheduler
174 with @func{thread_start}, which creates the idle thread and enables
175 interrupts.
176 With interrupts enabled, interrupt-driven serial port I/O becomes
177 possible, so we use
178 @func{serial_init_queue} to switch to that mode.  Finally,
179 @func{timer_calibrate} calibrates the timer for accurate short delays.
180
181 If the file system is compiled in, as it will starting in project 2, we
182 initialize the disks with @func{disk_init}, then the
183 file system with @func{filesys_init}.
184
185 Boot is complete, so we print a message.
186
187 Function @func{run_actions} now parses and executes actions specified on
188 the kernel command line, such as @command{run} to run a test (in project
189 1) or a user program (in later projects).
190
191 Finally, if @option{-q} was specified on the kernel command line, we
192 call @func{power_off} to terminate the machine simulator.  Otherwise,
193 @func{main} calls @func{thread_exit}, which allows any other running
194 threads to continue running.
195
196 @node Threads
197 @section Threads
198
199 @menu
200 * struct thread::               
201 * Thread Functions::            
202 * Thread Switching::            
203 @end menu
204
205 @node struct thread
206 @subsection @code{struct thread}
207
208 The main Pintos data structure for threads is @struct{thread},
209 declared in @file{threads/thread.h}.
210
211 @deftp {Structure} {struct thread}
212 Represents a thread or a user process.  In the projects, you will have
213 to add your own members to @struct{thread}.  You may also change or
214 delete the definitions of existing members.
215
216 Every @struct{thread} occupies the beginning of its own page of
217 memory.  The rest of the page is used for the thread's stack, which
218 grows downward from the end of the page.  It looks like this:
219
220 @example
221 @group
222                   4 kB +---------------------------------+
223                        |          kernel stack           |
224                        |                |                |
225                        |                |                |
226                        |                V                |
227                        |         grows downward          |
228                        |                                 |
229                        |                                 |
230                        |                                 |
231                        |                                 |
232                        |                                 |
233                        |                                 |
234                        |                                 |
235                        |                                 |
236 sizeof (struct thread) +---------------------------------+
237                        |              magic              |
238                        |                :                |
239                        |                :                |
240                        |              status             |
241                        |               tid               |
242                   0 kB +---------------------------------+
243 @end group
244 @end example
245
246 This has two consequences.  First, @struct{thread} must not be allowed
247 to grow too big.  If it does, then there will not be enough room for the
248 kernel stack.  The base @struct{thread} is only a few bytes in size.  It
249 probably should stay well under 1 kB.
250
251 Second, kernel stacks must not be allowed to grow too large.  If a stack
252 overflows, it will corrupt the thread state.  Thus, kernel functions
253 should not allocate large structures or arrays as non-static local
254 variables.  Use dynamic allocation with @func{malloc} or
255 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
256 @end deftp
257
258 @deftypecv {Member} {@struct{thread}} {tid_t} tid
259 The thread's thread identifier or @dfn{tid}.  Every thread must have a
260 tid that is unique over the entire lifetime of the kernel.  By
261 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
262 thread receives the numerically next higher tid, starting from 1 for
263 the initial process.  You can change the type and the numbering scheme
264 if you like.
265 @end deftypecv
266
267 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
268 @anchor{Thread States}
269 The thread's state, one of the following:
270
271 @defvr {Thread State} @code{THREAD_RUNNING}
272 The thread is running.  Exactly one thread is running at a given time.
273 @func{thread_current} returns the running thread.
274 @end defvr
275
276 @defvr {Thread State} @code{THREAD_READY}
277 The thread is ready to run, but it's not running right now.  The
278 thread could be selected to run the next time the scheduler is
279 invoked.  Ready threads are kept in a doubly linked list called
280 @code{ready_list}.
281 @end defvr
282
283 @defvr {Thread State} @code{THREAD_BLOCKED}
284 The thread is waiting for something, e.g.@: a lock to become
285 available, an interrupt to be invoked.  The thread won't be scheduled
286 again until it transitions to the @code{THREAD_READY} state with a
287 call to @func{thread_unblock}.  This is most conveniently done
288 indirectly, using one of the Pintos synchronization primitives that
289 block and unblock threads automatically (@pxref{Synchronization}).
290
291 There is no @i{a priori} way to tell what a blocked thread is waiting
292 for, but a backtrace can help (@pxref{Backtraces}).
293 @end defvr
294
295 @defvr {Thread State} @code{THREAD_DYING}
296 The thread will be destroyed by the scheduler after switching to the
297 next thread.
298 @end defvr
299 @end deftypecv
300
301 @deftypecv {Member} {@struct{thread}} {char} name[16]
302 The thread's name as a string, or at least the first few characters of
303 it.
304 @end deftypecv
305
306 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
307 Every thread has its own stack to keep track of its state.  When the
308 thread is running, the CPU's stack pointer register tracks the top of
309 the stack and this member is unused.  But when the CPU switches to
310 another thread, this member saves the thread's stack pointer.  No
311 other members are needed to save the thread's registers, because the
312 other registers that must be saved are saved on the stack.
313
314 When an interrupt occurs, whether in the kernel or a user program, an
315 @struct{intr_frame} is pushed onto the stack.  When the interrupt occurs
316 in a user program, the @struct{intr_frame} is always at the very top of
317 the page.  @xref{Interrupt Handling}, for more information.
318 @end deftypecv
319
320 @deftypecv {Member} {@struct{thread}} {int} priority
321 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
322 (63).  Lower numbers correspond to lower priorities, so that
323 priority 0 is the lowest priority and priority 63 is the highest.
324 Pintos as provided ignores thread priorities, but you will implement
325 priority scheduling in project 1 (@pxref{Priority Scheduling}).
326 @end deftypecv
327
328 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} allelem
329 This ``list element'' is used to link the thread into the list of all
330 threads.  Each thread is inserted into this list when it is created
331 and removed when it exits.  The @func{thread_foreach} function should 
332 be used to iterate over all threads.
333 @end deftypecv
334
335 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
336 A ``list element'' used to put the thread into doubly linked lists,
337 either @code{ready_list} (the list of threads ready to run) or a list of
338 threads waiting on a semaphore in @func{sema_down}.  It can do double
339 duty because a thread waiting on a semaphore is not ready, and vice
340 versa.
341 @end deftypecv
342
343 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
344 Only present in project 2 and later.  @xref{Page Tables}.
345 @end deftypecv
346
347 @deftypecv {Member} {@struct{thread}} {unsigned} magic
348 Always set to @code{THREAD_MAGIC}, which is just an arbitrary number defined
349 in @file{threads/thread.c}, and used to detect stack overflow.
350 @func{thread_current} checks that the @code{magic} member of the running
351 thread's @struct{thread} is set to @code{THREAD_MAGIC}.  Stack overflow
352 tends to change this value, triggering the assertion.  For greatest
353 benefit, as you add members to @struct{thread}, leave @code{magic} at
354 the end.
355 @end deftypecv
356
357 @node Thread Functions
358 @subsection Thread Functions
359
360 @file{threads/thread.c} implements several public functions for thread
361 support.  Let's take a look at the most useful:
362
363 @deftypefun void thread_init (void)
364 Called by @func{main} to initialize the thread system.  Its main
365 purpose is to create a @struct{thread} for Pintos's initial thread.
366 This is possible because the Pintos loader puts the initial
367 thread's stack at the top of a page, in the same position as any other
368 Pintos thread.
369
370 Before @func{thread_init} runs,
371 @func{thread_current} will fail because the running thread's
372 @code{magic} value is incorrect.  Lots of functions call
373 @func{thread_current} directly or indirectly, including
374 @func{lock_acquire} for locking a lock, so @func{thread_init} is
375 called early in Pintos initialization.
376 @end deftypefun
377
378 @deftypefun void thread_start (void)
379 Called by @func{main} to start the scheduler.  Creates the idle
380 thread, that is, the thread that is scheduled when no other thread is
381 ready.  Then enables interrupts, which as a side effect enables the
382 scheduler because the scheduler runs on return from the timer interrupt, using
383 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
384 @end deftypefun
385
386 @deftypefun void thread_tick (void)
387 Called by the timer interrupt at each timer tick.  It keeps track of
388 thread statistics and triggers the scheduler when a time slice expires.
389 @end deftypefun
390
391 @deftypefun void thread_print_stats (void)
392 Called during Pintos shutdown to print thread statistics.
393 @end deftypefun
394
395 @deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
396 Creates and starts a new thread named @var{name} with the given
397 @var{priority}, returning the new thread's tid.  The thread executes
398 @var{func}, passing @var{aux} as the function's single argument.
399
400 @func{thread_create} allocates a page for the thread's
401 @struct{thread} and stack and initializes its members, then it sets
402 up a set of fake stack frames for it (@pxref{Thread Switching}).  The
403 thread is initialized in the blocked state, then unblocked just before
404 returning, which allows the new thread to
405 be scheduled (@pxref{Thread States}).
406
407 @deftp {Type} {void thread_func (void *@var{aux})}
408 This is the type of the function passed to @func{thread_create}, whose
409 @var{aux} argument is passed along as the function's argument.
410 @end deftp
411 @end deftypefun
412
413 @deftypefun void thread_block (void)
414 Transitions the running thread from the running state to the blocked
415 state (@pxref{Thread States}).  The thread will not run again until
416 @func{thread_unblock} is
417 called on it, so you'd better have some way arranged for that to happen.
418 Because @func{thread_block} is so low-level, you should prefer to use
419 one of the synchronization primitives instead (@pxref{Synchronization}).
420 @end deftypefun
421
422 @deftypefun void thread_unblock (struct thread *@var{thread})
423 Transitions @var{thread}, which must be in the blocked state, to the
424 ready state, allowing it to resume running (@pxref{Thread States}).
425 This is called when the event that the thread is waiting for occurs,
426 e.g.@: when the lock that 
427 the thread is waiting on becomes available.
428 @end deftypefun
429
430 @deftypefun {struct thread *} thread_current (void)
431 Returns the running thread.
432 @end deftypefun
433
434 @deftypefun {tid_t} thread_tid (void)
435 Returns the running thread's thread id.  Equivalent to
436 @code{thread_current ()->tid}.
437 @end deftypefun
438
439 @deftypefun {const char *} thread_name (void)
440 Returns the running thread's name.  Equivalent to @code{thread_current
441 ()->name}.
442 @end deftypefun
443
444 @deftypefun void thread_exit (void) @code{NO_RETURN}
445 Causes the current thread to exit.  Never returns, hence
446 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
447 @end deftypefun
448
449 @deftypefun void thread_yield (void)
450 Yields the CPU to the scheduler, which picks a new thread to run.  The
451 new thread might be the current thread, so you can't depend on this
452 function to keep this thread from running for any particular length of
453 time.
454 @end deftypefun
455
456 @deftypefun void thread_foreach (thread_action_func *@var{action}, void *@var{aux})
457 Iterates over all threads @var{t} and invokes @code{action(t, aux)} on each.
458 @var{action} must refer to a function that matches the signature 
459 given by @func{thread_action_func}:
460
461 @deftp {Type} {void thread_action_func (struct thread *@var{thread}, void *@var{aux})}
462 Performs some action on a thread, given @var{aux}.
463 @end deftp
464 @end deftypefun
465
466 @deftypefun int thread_get_priority (void)
467 @deftypefunx void thread_set_priority (int @var{new_priority})
468 Stub to set and get thread priority.  @xref{Priority Scheduling}.
469 @end deftypefun
470
471 @deftypefun int thread_get_nice (void)
472 @deftypefunx void thread_set_nice (int @var{new_nice})
473 @deftypefunx int thread_get_recent_cpu (void)
474 @deftypefunx int thread_get_load_avg (void)
475 Stubs for the advanced scheduler.  @xref{4.4BSD Scheduler}.
476 @end deftypefun
477
478 @node Thread Switching
479 @subsection Thread Switching
480
481 @func{schedule} is responsible for switching threads.  It
482 is internal to @file{threads/thread.c} and called only by the three
483 public thread functions that need to switch threads:
484 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
485 Before any of these functions call @func{schedule}, they disable
486 interrupts (or ensure that they are already disabled) and then change
487 the running thread's state to something other than running.
488
489 @func{schedule} is short but tricky.  It records the
490 current thread in local variable @var{cur}, determines the next thread
491 to run as local variable @var{next} (by calling
492 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
493 the actual thread switch.  The thread we switched to was also running
494 inside @func{switch_threads}, as are all the threads not currently
495 running, so the new thread now returns out of
496 @func{switch_threads}, returning the previously running thread.
497
498 @func{switch_threads} is an assembly language routine in
499 @file{threads/switch.S}.  It saves registers on the stack, saves the
500 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
501 member, restores the new thread's @code{stack} into the CPU's stack
502 pointer, restores registers from the stack, and returns.
503
504 The rest of the scheduler is implemented in @func{thread_schedule_tail}.  It
505 marks the new thread as running.  If the thread we just switched from
506 is in the dying state, then it also frees the page that contained the
507 dying thread's @struct{thread} and stack.  These couldn't be freed
508 prior to the thread switch because the switch needed to use it.
509
510 Running a thread for the first time is a special case.  When
511 @func{thread_create} creates a new thread, it goes through a fair
512 amount of trouble to get it started properly.  In particular, the new
513 thread hasn't started running yet, so there's no way for it to be
514 running inside @func{switch_threads} as the scheduler expects.  To
515 solve the problem, @func{thread_create} creates some fake stack frames
516 in the new thread's stack:
517
518 @itemize @bullet
519 @item
520 The topmost fake stack frame is for @func{switch_threads}, represented
521 by @struct{switch_threads_frame}.  The important part of this frame is
522 its @code{eip} member, the return address.  We point @code{eip} to
523 @func{switch_entry}, indicating it to be the function that called
524 @func{switch_entry}.
525
526 @item
527 The next fake stack frame is for @func{switch_entry}, an assembly
528 language routine in @file{threads/switch.S} that adjusts the stack
529 pointer,@footnote{This is because @func{switch_threads} takes
530 arguments on the stack and the 80@var{x}86 SVR4 calling convention
531 requires the caller, not the called function, to remove them when the
532 call is complete.  See @bibref{SysV-i386} chapter 3 for details.}
533 calls @func{thread_schedule_tail} (this special case is why
534 @func{thread_schedule_tail} is separate from @func{schedule}), and returns.
535 We fill in its stack frame so that it returns into
536 @func{kernel_thread}, a function in @file{threads/thread.c}.
537
538 @item
539 The final stack frame is for @func{kernel_thread}, which enables
540 interrupts and calls the thread's function (the function passed to
541 @func{thread_create}).  If the thread's function returns, it calls
542 @func{thread_exit} to terminate the thread.
543 @end itemize
544
545 @node Synchronization
546 @section Synchronization
547
548 If sharing of resources between threads is not handled in a careful,
549 controlled fashion, the result is usually a big mess.
550 This is especially the case in operating system kernels, where
551 faulty sharing can crash the entire machine.  Pintos provides several
552 synchronization primitives to help out.
553
554 @menu
555 * Disabling Interrupts::        
556 * Semaphores::                  
557 * Locks::                       
558 * Monitors::                    
559 * Optimization Barriers::             
560 @end menu
561
562 @node Disabling Interrupts
563 @subsection Disabling Interrupts
564
565 The crudest way to do synchronization is to disable interrupts, that
566 is, to temporarily prevent the CPU from responding to interrupts.  If
567 interrupts are off, no other thread will preempt the running thread,
568 because thread preemption is driven by the timer interrupt.  If
569 interrupts are on, as they normally are, then the running thread may
570 be preempted by another at any time, whether between two C statements
571 or even within the execution of one.
572
573 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
574 is, kernel threads can be preempted at any time.  Traditional Unix
575 systems are ``nonpreemptible,'' that is, kernel threads can only be
576 preempted at points where they explicitly call into the scheduler.
577 (User programs can be preempted at any time in both models.)  As you
578 might imagine, preemptible kernels require more explicit
579 synchronization.
580
581 You should have little need to set the interrupt state directly.  Most
582 of the time you should use the other synchronization primitives
583 described in the following sections.  The main reason to disable
584 interrupts is to synchronize kernel threads with external interrupt
585 handlers, which cannot sleep and thus cannot use most other forms of
586 synchronization (@pxref{External Interrupt Handling}).
587
588 Some external interrupts cannot be postponed, even by disabling
589 interrupts.  These interrupts, called @dfn{non-maskable interrupts}
590 (NMIs), are supposed to be used only in emergencies, e.g.@: when the
591 computer is on fire.  Pintos does not handle non-maskable interrupts.
592
593 Types and functions for disabling and enabling interrupts are in
594 @file{threads/interrupt.h}.
595
596 @deftp Type {enum intr_level}
597 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
598 disabled or enabled, respectively.
599 @end deftp
600
601 @deftypefun {enum intr_level} intr_get_level (void)
602 Returns the current interrupt state.
603 @end deftypefun
604
605 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
606 Turns interrupts on or off according to @var{level}.  Returns the
607 previous interrupt state.
608 @end deftypefun
609
610 @deftypefun {enum intr_level} intr_enable (void)
611 Turns interrupts on.  Returns the previous interrupt state.
612 @end deftypefun
613
614 @deftypefun {enum intr_level} intr_disable (void)
615 Turns interrupts off.  Returns the previous interrupt state.
616 @end deftypefun
617
618 @node Semaphores
619 @subsection Semaphores
620
621 A @dfn{semaphore} is a nonnegative integer together with two operators
622 that manipulate it atomically, which are:
623
624 @itemize @bullet
625 @item
626 ``Down'' or ``P'': wait for the value to become positive, then
627 decrement it.
628
629 @item
630 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
631 if any).
632 @end itemize
633
634 A semaphore initialized to 0 may be used to wait for an event
635 that will happen exactly once.  For example, suppose thread @var{A}
636 starts another thread @var{B} and wants to wait for @var{B} to signal
637 that some activity is complete.  @var{A} can create a semaphore
638 initialized to 0, pass it to @var{B} as it starts it, and then
639 ``down'' the semaphore.  When @var{B} finishes its activity, it
640 ``ups'' the semaphore.  This works regardless of whether @var{A}
641 ``downs'' the semaphore or @var{B} ``ups'' it first.
642
643 A semaphore initialized to 1 is typically used for controlling access
644 to a resource.  Before a block of code starts using the resource, it
645 ``downs'' the semaphore, then after it is done with the resource it
646 ``ups'' the resource.  In such a case a lock, described below, may be
647 more appropriate.
648
649 Semaphores can also be initialized to values larger than 1.  These are
650 rarely used.
651
652 Semaphores were invented by Edsger Dijkstra and first used in the THE
653 operating system (@bibref{Dijkstra}).
654
655 Pintos' semaphore type and operations are declared in
656 @file{threads/synch.h}.  
657
658 @deftp {Type} {struct semaphore}
659 Represents a semaphore.
660 @end deftp
661
662 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
663 Initializes @var{sema} as a new semaphore with the given initial
664 @var{value}.
665 @end deftypefun
666
667 @deftypefun void sema_down (struct semaphore *@var{sema})
668 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
669 its value to become positive and then decrementing it by one.
670 @end deftypefun
671
672 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
673 Tries to execute the ``down'' or ``P'' operation on @var{sema},
674 without waiting.  Returns true if @var{sema}
675 was successfully decremented, or false if it was already
676 zero and thus could not be decremented without waiting.  Calling this
677 function in a
678 tight loop wastes CPU time, so use @func{sema_down} or find a
679 different approach instead.
680 @end deftypefun
681
682 @deftypefun void sema_up (struct semaphore *@var{sema})
683 Executes the ``up'' or ``V'' operation on @var{sema},
684 incrementing its value.  If any threads are waiting on
685 @var{sema}, wakes one of them up.
686
687 Unlike most synchronization primitives, @func{sema_up} may be called
688 inside an external interrupt handler (@pxref{External Interrupt
689 Handling}).
690 @end deftypefun
691
692 Semaphores are internally built out of disabling interrupt
693 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
694 (@func{thread_block} and @func{thread_unblock}).  Each semaphore maintains
695 a list of waiting threads, using the linked list
696 implementation in @file{lib/kernel/list.c}.
697
698 @node Locks
699 @subsection Locks
700
701 A @dfn{lock} is like a semaphore with an initial value of 1
702 (@pxref{Semaphores}).  A lock's equivalent of ``up'' is called
703 ``release'', and the ``down'' operation is called ``acquire''.
704
705 Compared to a semaphore, a lock has one added restriction: only the
706 thread that acquires a lock, called the lock's ``owner'', is allowed to
707 release it.  If this restriction is a problem, it's a good sign that a
708 semaphore should be used, instead of a lock.
709
710 Locks in Pintos are not ``recursive,'' that is, it is an error for the
711 thread currently holding a lock to try to acquire that lock.
712
713 Lock types and functions are declared in @file{threads/synch.h}.
714
715 @deftp {Type} {struct lock}
716 Represents a lock.
717 @end deftp
718
719 @deftypefun void lock_init (struct lock *@var{lock})
720 Initializes @var{lock} as a new lock.
721 The lock is not initially owned by any thread.
722 @end deftypefun
723
724 @deftypefun void lock_acquire (struct lock *@var{lock})
725 Acquires @var{lock} for the current thread, first waiting for
726 any current owner to release it if necessary.
727 @end deftypefun
728
729 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
730 Tries to acquire @var{lock} for use by the current thread, without
731 waiting.  Returns true if successful, false if the lock is already
732 owned.  Calling this function in a tight loop is a bad idea because it
733 wastes CPU time, so use @func{lock_acquire} instead.
734 @end deftypefun
735
736 @deftypefun void lock_release (struct lock *@var{lock})
737 Releases @var{lock}, which the current thread must own.
738 @end deftypefun
739
740 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
741 Returns true if the running thread owns @var{lock},
742 false otherwise.
743 There is no function to test whether an arbitrary thread owns a lock,
744 because the answer could change before the caller could act on it.
745 @end deftypefun
746
747 @node Monitors
748 @subsection Monitors
749
750 A @dfn{monitor} is a higher-level form of synchronization than a
751 semaphore or a lock.  A monitor consists of data being synchronized,
752 plus a lock, called the @dfn{monitor lock}, and one or more
753 @dfn{condition variables}.  Before it accesses the protected data, a
754 thread first acquires the monitor lock.  It is then said to be ``in the
755 monitor''.  While in the monitor, the thread has control over all the
756 protected data, which it may freely examine or modify.  When access to
757 the protected data is complete, it releases the monitor lock.
758
759 Condition variables allow code in the monitor to wait for a condition to
760 become true.  Each condition variable is associated with an abstract
761 condition, e.g.@: ``some data has arrived for processing'' or ``over 10
762 seconds has passed since the user's last keystroke''.  When code in the
763 monitor needs to wait for a condition to become true, it ``waits'' on
764 the associated condition variable, which releases the lock and waits for
765 the condition to be signaled.  If, on the other hand, it has caused one
766 of these conditions to become true, it ``signals'' the condition to wake
767 up one waiter, or ``broadcasts'' the condition to wake all of them.
768
769 The theoretical framework for monitors was laid out by C.@: A.@: R.@:
770 Hoare (@bibref{Hoare}).  Their practical usage was later elaborated in a
771 paper on the Mesa operating system (@bibref{Lampson}).
772
773 Condition variable types and functions are declared in
774 @file{threads/synch.h}.
775
776 @deftp {Type} {struct condition}
777 Represents a condition variable.
778 @end deftp
779
780 @deftypefun void cond_init (struct condition *@var{cond})
781 Initializes @var{cond} as a new condition variable.
782 @end deftypefun
783
784 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
785 Atomically releases @var{lock} (the monitor lock) and waits for
786 @var{cond} to be signaled by some other piece of code.  After
787 @var{cond} is signaled, reacquires @var{lock} before returning.
788 @var{lock} must be held before calling this function.
789
790 Sending a signal and waking up from a wait are not an atomic operation.
791 Thus, typically @func{cond_wait}'s caller must recheck the condition
792 after the wait completes and, if necessary, wait again.  See the next
793 section for an example.
794 @end deftypefun
795
796 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
797 If any threads are waiting on @var{cond} (protected by monitor lock
798 @var{lock}), then this function wakes up one of them.  If no threads are
799 waiting, returns without performing any action.
800 @var{lock} must be held before calling this function.
801 @end deftypefun
802
803 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
804 Wakes up all threads, if any, waiting on @var{cond} (protected by
805 monitor lock @var{lock}).  @var{lock} must be held before calling this
806 function.
807 @end deftypefun
808
809 @subsubsection Monitor Example
810
811 The classical example of a monitor is handling a buffer into which one
812 or more
813 ``producer'' threads write characters and out of which one or more
814 ``consumer'' threads read characters.  To implement this we need,
815 besides the monitor lock, two condition variables which we will call
816 @var{not_full} and @var{not_empty}:
817
818 @example
819 char buf[BUF_SIZE];     /* @r{Buffer.} */
820 size_t n = 0;           /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
821 size_t head = 0;        /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
822 size_t tail = 0;        /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
823 struct lock lock;       /* @r{Monitor lock.} */
824 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
825 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
826
827 @dots{}@r{initialize the locks and condition variables}@dots{}
828
829 void put (char ch) @{
830   lock_acquire (&lock);
831   while (n == BUF_SIZE)            /* @r{Can't add to @var{buf} as long as it's full.} */
832     cond_wait (&not_full, &lock);
833   buf[head++ % BUF_SIZE] = ch;     /* @r{Add @var{ch} to @var{buf}.} */
834   n++;
835   cond_signal (&not_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
836   lock_release (&lock);
837 @}
838
839 char get (void) @{
840   char ch;
841   lock_acquire (&lock);
842   while (n == 0)                  /* @r{Can't read @var{buf} as long as it's empty.} */
843     cond_wait (&not_empty, &lock);
844   ch = buf[tail++ % BUF_SIZE];    /* @r{Get @var{ch} from @var{buf}.} */
845   n--;
846   cond_signal (&not_full, &lock); /* @r{@var{buf} can't be full anymore.} */
847   lock_release (&lock);
848 @}
849 @end example
850
851 Note that @code{BUF_SIZE} must divide evenly into @code{SIZE_MAX + 1}
852 for the above code to be completely correct.  Otherwise, it will fail
853 the first time @code{head} wraps around to 0.  In practice,
854 @code{BUF_SIZE} would ordinarily be a power of 2.
855
856 @node Optimization Barriers
857 @subsection Optimization Barriers
858
859 @c We should try to come up with a better example.
860 @c Perhaps something with a linked list?
861
862 An @dfn{optimization barrier} is a special statement that prevents the
863 compiler from making assumptions about the state of memory across the
864 barrier.  The compiler will not reorder reads or writes of variables
865 across the barrier or assume that a variable's value is unmodified
866 across the barrier, except for local variables whose address is never
867 taken.  In Pintos, @file{threads/synch.h} defines the @code{barrier()}
868 macro as an optimization barrier.
869
870 One reason to use an optimization barrier is when data can change
871 asynchronously, without the compiler's knowledge, e.g.@: by another
872 thread or an interrupt handler.  The @func{too_many_loops} function in
873 @file{devices/timer.c} is an example.  This function starts out by
874 busy-waiting in a loop until a timer tick occurs:
875
876 @example
877 /* Wait for a timer tick. */
878 int64_t start = ticks;
879 while (ticks == start)
880   barrier ();
881 @end example
882
883 @noindent
884 Without an optimization barrier in the loop, the compiler could
885 conclude that the loop would never terminate, because @code{start} and
886 @code{ticks} start out equal and the loop itself never changes them.
887 It could then ``optimize'' the function into an infinite loop, which
888 would definitely be undesirable.
889
890 Optimization barriers can be used to avoid other compiler
891 optimizations.  The @func{busy_wait} function, also in
892 @file{devices/timer.c}, is an example.  It contains this loop:
893
894 @example
895 while (loops-- > 0)
896   barrier ();
897 @end example
898
899 @noindent
900 The goal of this loop is to busy-wait by counting @code{loops} down
901 from its original value to 0.  Without the barrier, the compiler could
902 delete the loop entirely, because it produces no useful output and has
903 no side effects.  The barrier forces the compiler to pretend that the
904 loop body has an important effect.
905
906 Finally, optimization barriers can be used to force the ordering of
907 memory reads or writes.  For example, suppose we add a ``feature''
908 that, whenever a timer interrupt occurs, the character in global
909 variable @code{timer_put_char} is printed on the console, but only if
910 global Boolean variable @code{timer_do_put} is true.  The best way to
911 set up @samp{x} to be printed is then to use an optimization barrier,
912 like this:
913
914 @example
915 timer_put_char = 'x';
916 barrier ();
917 timer_do_put = true;
918 @end example
919
920 Without the barrier, the code is buggy because the compiler is free to
921 reorder operations when it doesn't see a reason to keep them in the
922 same order.  In this case, the compiler doesn't know that the order of
923 assignments is important, so its optimizer is permitted to exchange
924 their order.  There's no telling whether it will actually do this, and
925 it is possible that passing the compiler different optimization flags
926 or using a different version of the compiler will produce different
927 behavior.
928
929 Another solution is to disable interrupts around the assignments.
930 This does not prevent reordering, but it prevents the interrupt
931 handler from intervening between the assignments.  It also has the
932 extra runtime cost of disabling and re-enabling interrupts:
933
934 @example
935 enum intr_level old_level = intr_disable ();
936 timer_put_char = 'x';
937 timer_do_put = true;
938 intr_set_level (old_level);
939 @end example
940
941 A second solution is to mark the declarations of
942 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}.  This
943 keyword tells the compiler that the variables are externally observable
944 and restricts its latitude for optimization.  However, the semantics of
945 @samp{volatile} are not well-defined, so it is not a good general
946 solution.  The base Pintos code does not use @samp{volatile} at all.
947
948 The following is @emph{not} a solution, because locks neither prevent
949 interrupts nor prevent the compiler from reordering the code within the
950 region where the lock is held:
951
952 @example
953 lock_acquire (&timer_lock);     /* INCORRECT CODE */
954 timer_put_char = 'x';
955 timer_do_put = true;
956 lock_release (&timer_lock);
957 @end example
958
959 The compiler treats invocation of any function defined externally,
960 that is, in another source file, as a limited form of optimization
961 barrier.  Specifically, the compiler assumes that any externally
962 defined function may access any statically or dynamically allocated
963 data and any local variable whose address is taken.  This often means
964 that explicit barriers can be omitted.  It is one reason that Pintos
965 contains few explicit barriers.
966
967 A function defined in the same source file, or in a header included by
968 the source file, cannot be relied upon as a optimization barrier.
969 This applies even to invocation of a function before its
970 definition, because the compiler may read and parse the entire source
971 file before performing optimization.
972
973 @node Interrupt Handling
974 @section Interrupt Handling
975
976 An @dfn{interrupt} notifies the CPU of some event.  Much of the work
977 of an operating system relates to interrupts in one way or another.
978 For our purposes, we classify interrupts into two broad categories:
979
980 @itemize @bullet
981 @item
982 @dfn{Internal interrupts}, that is, interrupts caused directly by CPU
983 instructions.  System calls, attempts at invalid memory access
984 (@dfn{page faults}), and attempts to divide by zero are some activities
985 that cause internal interrupts.  Because they are caused by CPU
986 instructions, internal interrupts are @dfn{synchronous} or synchronized
987 with CPU instructions.  @func{intr_disable} does not disable internal
988 interrupts.
989
990 @item
991 @dfn{External interrupts}, that is, interrupts originating outside the
992 CPU.  These interrupts come from hardware devices such as the system
993 timer, keyboard, serial ports, and disks.  External interrupts are
994 @dfn{asynchronous}, meaning that their delivery is not
995 synchronized with instruction execution.  Handling of external interrupts
996 can be postponed with @func{intr_disable} and related functions
997 (@pxref{Disabling Interrupts}).
998 @end itemize
999
1000 The CPU treats both classes of interrupts largely the same way,
1001 so Pintos has common infrastructure to handle both classes.
1002 The following section describes this
1003 common infrastructure.  The sections after that give the specifics of
1004 external and internal interrupts.
1005
1006 If you haven't already read chapter 3, ``Basic Execution Environment,''
1007 in @bibref{IA32-v1}, it is recommended that you do so now.  You might
1008 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
1009 @bibref{IA32-v3a}.
1010
1011 @menu
1012 * Interrupt Infrastructure::    
1013 * Internal Interrupt Handling::  
1014 * External Interrupt Handling::  
1015 @end menu
1016
1017 @node Interrupt Infrastructure
1018 @subsection Interrupt Infrastructure
1019
1020 When an interrupt occurs, the CPU saves
1021 its most essential state on a stack and jumps to an interrupt
1022 handler routine.  The 80@var{x}86 architecture supports 256
1023 interrupts, numbered 0 through 255, each with an independent
1024 handler defined in an array called the @dfn{interrupt
1025 descriptor table} or IDT.
1026
1027 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
1028 IDT so that each entry points to a unique entry point in
1029 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
1030 @var{NN} is the interrupt number in
1031 hexadecimal.  Because the CPU doesn't give
1032 us any other way to find out the interrupt number, this entry point
1033 pushes the interrupt number on the stack.  Then it jumps to
1034 @func{intr_entry}, which pushes all the registers that the processor
1035 didn't already push for us, and then calls @func{intr_handler}, which
1036 brings us back into C in @file{threads/interrupt.c}.
1037
1038 The main job of @func{intr_handler} is to call the function
1039 registered for handling the particular interrupt.  (If no
1040 function is registered, it dumps some information to the console and
1041 panics.)  It also does some extra processing for external
1042 interrupts (@pxref{External Interrupt Handling}).
1043
1044 When @func{intr_handler} returns, the assembly code in
1045 @file{threads/intr-stubs.S} restores all the CPU registers saved
1046 earlier and directs the CPU to return from the interrupt.
1047
1048 The following types and functions are common to all
1049 interrupts.
1050
1051 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
1052 This is how an interrupt handler function must be declared.  Its @var{frame}
1053 argument (see below) allows it to determine the cause of the interrupt
1054 and the state of the thread that was interrupted.
1055 @end deftp
1056
1057 @deftp {Type} {struct intr_frame}
1058 The stack frame of an interrupt handler, as saved by the CPU, the interrupt
1059 stubs, and @func{intr_entry}.  Its most interesting members are described
1060 below.
1061 @end deftp
1062
1063 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
1064 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
1065 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
1066 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
1067 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
1068 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1069 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1070 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1071 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1072 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1073 Register values in the interrupted thread, pushed by @func{intr_entry}.
1074 The @code{esp_dummy} value isn't actually used (refer to the
1075 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1076 @end deftypecv
1077
1078 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1079 The interrupt vector number, ranging from 0 to 255.
1080 @end deftypecv
1081
1082 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1083 The ``error code'' pushed on the stack by the CPU for some internal
1084 interrupts.
1085 @end deftypecv
1086
1087 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1088 The address of the next instruction to be executed by the interrupted
1089 thread.
1090 @end deftypecv
1091
1092 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1093 The interrupted thread's stack pointer.
1094 @end deftypecv
1095
1096 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1097 Returns the name of the interrupt numbered @var{vec}, or
1098 @code{"unknown"} if the interrupt has no registered name.
1099 @end deftypefun
1100
1101 @node Internal Interrupt Handling
1102 @subsection Internal Interrupt Handling
1103
1104 Internal interrupts are caused directly by CPU instructions executed by
1105 the running kernel thread or user process (from project 2 onward).  An
1106 internal interrupt is therefore said to arise in a ``process context.''
1107
1108 In an internal interrupt's handler, it can make sense to examine the
1109 @struct{intr_frame} passed to the interrupt handler, or even to modify
1110 it.  When the interrupt returns, modifications in @struct{intr_frame}
1111 become changes to the calling thread or process's state.  For example,
1112 the Pintos system call handler returns a value to the user program by
1113 modifying the saved EAX register (@pxref{System Call Details}).
1114
1115 There are no special restrictions on what an internal interrupt
1116 handler can or can't do.  Generally they should run with interrupts
1117 enabled, just like other code, and so they can be preempted by other
1118 kernel threads.  Thus, they do need to synchronize with other threads
1119 on shared data and other resources (@pxref{Synchronization}).
1120
1121 Internal interrupt handlers can be invoked recursively.  For example,
1122 the system call handler might cause a page fault while attempting to
1123 read user memory.  Deep recursion would risk overflowing the limited
1124 kernel stack (@pxref{struct thread}), but should be unnecessary.
1125
1126 @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})
1127 Registers @var{handler} to be called when internal interrupt numbered
1128 @var{vec} is triggered.  Names the interrupt @var{name} for debugging
1129 purposes.
1130
1131 If @var{level} is @code{INTR_ON}, external interrupts will be processed
1132 normally during the interrupt handler's execution, which is normally
1133 desirable.  Specifying @code{INTR_OFF} will cause the CPU to disable
1134 external interrupts when it invokes the interrupt handler.  The effect
1135 is slightly different from calling @func{intr_disable} inside the
1136 handler, because that leaves a window of one or more CPU instructions in
1137 which external interrupts are still enabled.  This is important for the
1138 page fault handler; refer to the comments in @file{userprog/exception.c}
1139 for details.
1140
1141 @var{dpl} determines how the interrupt can be invoked.  If @var{dpl} is
1142 0, then the interrupt can be invoked only by kernel threads.  Otherwise
1143 @var{dpl} should be 3, which allows user processes to invoke the
1144 interrupt with an explicit INT instruction.  The value of @var{dpl}
1145 doesn't affect user processes' ability to invoke the interrupt
1146 indirectly, e.g.@: an invalid memory reference will cause a page fault
1147 regardless of @var{dpl}.
1148 @end deftypefun
1149
1150 @node External Interrupt Handling
1151 @subsection External Interrupt Handling
1152
1153 External interrupts are caused by events outside the CPU.
1154 They are asynchronous, so they can be invoked at any time that
1155 interrupts have not been disabled.  We say that an external interrupt
1156 runs in an ``interrupt context.''
1157
1158 In an external interrupt, the @struct{intr_frame} passed to the
1159 handler is not very meaningful.  It describes the state of the thread
1160 or process that was interrupted, but there is no way to predict which
1161 one that is.  It is possible, although rarely useful, to examine it, but
1162 modifying it is a recipe for disaster.
1163
1164 Only one external interrupt may be processed at a time.  Neither
1165 internal nor external interrupt may nest within an external interrupt
1166 handler.  Thus, an external interrupt's handler must run with interrupts
1167 disabled (@pxref{Disabling Interrupts}).
1168
1169 An external interrupt handler must not sleep or yield, which rules out
1170 calling @func{lock_acquire}, @func{thread_yield}, and many other
1171 functions.  Sleeping in interrupt context would effectively put the
1172 interrupted thread to sleep, too, until the interrupt handler was again
1173 scheduled and returned.  This would be unfair to the unlucky thread, and
1174 it would deadlock if the handler were waiting for the sleeping thread
1175 to, e.g., release a lock.
1176
1177 An external interrupt handler
1178 effectively monopolizes the machine and delays all other activities.
1179 Therefore, external interrupt handlers should complete as quickly as
1180 they can.  Anything that require much CPU time should instead run in a
1181 kernel thread, possibly one that the interrupt triggers using a
1182 synchronization primitive.
1183
1184 External interrupts are controlled by a
1185 pair of devices outside the CPU called @dfn{programmable interrupt
1186 controllers}, @dfn{PICs} for short.  When @func{intr_init} sets up the
1187 CPU's IDT, it also initializes the PICs for interrupt handling.  The
1188 PICs also must be ``acknowledged'' at the end of processing for each
1189 external interrupt.  @func{intr_handler} takes care of that by calling
1190 @func{pic_end_of_interrupt}, which properly signals the PICs.
1191
1192 The following functions relate to external
1193 interrupts.
1194
1195 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1196 Registers @var{handler} to be called when external interrupt numbered
1197 @var{vec} is triggered.  Names the interrupt @var{name} for debugging
1198 purposes.  The handler will run with interrupts disabled.
1199 @end deftypefun
1200
1201 @deftypefun bool intr_context (void)
1202 Returns true if we are running in an interrupt context, otherwise
1203 false.  Mainly used in functions that might sleep
1204 or that otherwise should not be called from interrupt context, in this
1205 form:
1206 @example
1207 ASSERT (!intr_context ());
1208 @end example
1209 @end deftypefun
1210
1211 @deftypefun void intr_yield_on_return (void)
1212 When called in an interrupt context, causes @func{thread_yield} to be
1213 called just before the interrupt returns.  Used
1214 in the timer interrupt handler when a thread's time slice expires, to
1215 cause a new thread to be scheduled.
1216 @end deftypefun
1217
1218 @node Memory Allocation
1219 @section Memory Allocation
1220
1221 Pintos contains two memory allocators, one that allocates memory in
1222 units of a page, and one that can allocate blocks of any size.
1223
1224 @menu
1225 * Page Allocator::              
1226 * Block Allocator::             
1227 @end menu
1228
1229 @node Page Allocator
1230 @subsection Page Allocator
1231
1232 The page allocator declared in @file{threads/palloc.h} allocates
1233 memory in units of a page.  It is most often used to allocate memory
1234 one page at a time, but it can also allocate multiple contiguous pages
1235 at once.
1236
1237 The page allocator divides the memory it allocates into two pools,
1238 called the kernel and user pools.  By default, each pool gets half of
1239 system memory, but this can be changed with the @option{-ul} kernel
1240 command line
1241 option (@pxref{Why PAL_USER?}).  An allocation request draws from one
1242 pool or the other.  If one pool becomes empty, the other may still
1243 have free pages.  The user pool should be used for allocating memory
1244 for user processes and the kernel pool for all other allocations.
1245 This will only become important starting with project 3.  Until then,
1246 all allocations should be made from the kernel pool.
1247
1248 Each pool's usage is tracked with a bitmap, one bit per page in
1249 the pool.  A request to allocate @var{n} pages scans the bitmap
1250 for @var{n} consecutive bits set to
1251 false, indicating that those pages are free, and then sets those bits
1252 to true to mark them as used.  This is a ``first fit'' allocation
1253 strategy (@pxref{Wilson}).
1254
1255 The page allocator is subject to fragmentation.  That is, it may not
1256 be possible to allocate @var{n} contiguous pages even though @var{n}
1257 or more pages are free, because the free pages are separated by used
1258 pages.  In fact, in pathological cases it may be impossible to
1259 allocate 2 contiguous pages even though half of the pool's pages are free.
1260 Single-page requests can't fail due to fragmentation, so
1261 requests for multiple contiguous pages should be limited as much as
1262 possible.
1263
1264 Pages may not be allocated from interrupt context, but they may be
1265 freed.
1266
1267 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1268 a debugging aid (@pxref{Debugging Tips}).
1269
1270 Page allocator types and functions are described below.
1271
1272 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1273 @deftypefunx {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1274 Obtains and returns one page, or @var{page_cnt} contiguous pages,
1275 respectively.  Returns a null pointer if the pages cannot be allocated.
1276
1277 The @var{flags} argument may be any combination of the following flags:
1278
1279 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1280 If the pages cannot be allocated, panic the kernel.  This is only
1281 appropriate during kernel initialization.  User processes
1282 should never be permitted to panic the kernel.
1283 @end defvr
1284
1285 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1286 Zero all the bytes in the allocated pages before returning them.  If not
1287 set, the contents of newly allocated pages are unpredictable.
1288 @end defvr
1289
1290 @defvr {Page Allocator Flag} @code{PAL_USER}
1291 Obtain the pages from the user pool.  If not set, pages are allocated
1292 from the kernel pool.
1293 @end defvr
1294 @end deftypefun
1295
1296 @deftypefun void palloc_free_page (void *@var{page})
1297 @deftypefunx void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1298 Frees one page, or @var{page_cnt} contiguous pages, respectively,
1299 starting at @var{pages}.  All of the pages must have been obtained using
1300 @func{palloc_get_page} or @func{palloc_get_multiple}.
1301 @end deftypefun
1302
1303 @node Block Allocator
1304 @subsection Block Allocator
1305
1306 The block allocator, declared in @file{threads/malloc.h}, can allocate
1307 blocks of any size.  It is layered on top of the page allocator
1308 described in the previous section.  Blocks returned by the block
1309 allocator are obtained from the kernel pool.
1310
1311 The block allocator uses two different strategies for allocating memory.
1312 The first strategy applies to blocks that are 1 kB or smaller
1313 (one-fourth of the page size).  These allocations are rounded up to the
1314 nearest power of 2, or 16 bytes, whichever is larger.  Then they are
1315 grouped into a page used only for allocations of that size.
1316
1317 The second strategy applies to blocks larger than 1 kB.
1318 These allocations (plus a small amount of overhead) are rounded up to
1319 the nearest page in size, and then the block allocator requests that
1320 number of contiguous pages from the page allocator.
1321
1322 In either case, the difference between the allocation requested size
1323 and the actual block size is wasted.  A real operating system would
1324 carefully tune its allocator to minimize this waste, but this is
1325 unimportant in an instructional system like Pintos.
1326
1327 As long as a page can be obtained from the page allocator, small
1328 allocations always succeed.  Most small allocations do not require a
1329 new page from the page allocator at all, because they are satisfied
1330 using part of a page already allocated.  However, large allocations
1331 always require calling into the page allocator, and any allocation
1332 that needs more than one contiguous page can fail due to fragmentation,
1333 as already discussed in the previous section.  Thus, you should
1334 minimize the number of large allocations in your code, especially
1335 those over approximately 4 kB each.
1336
1337 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1338 a debugging aid (@pxref{Debugging Tips}).
1339
1340 The block allocator may not be called from interrupt context.
1341
1342 The block allocator functions are described below.  Their interfaces are
1343 the same as the standard C library functions of the same names.
1344
1345 @deftypefun {void *} malloc (size_t @var{size})
1346 Obtains and returns a new block, from the kernel pool, at least
1347 @var{size} bytes long.  Returns a null pointer if @var{size} is zero or
1348 if memory is not available.
1349 @end deftypefun
1350
1351 @deftypefun {void *} calloc (size_t @var{a}, size_t @var{b})
1352 Obtains a returns a new block, from the kernel pool, at least
1353 @code{@var{a} * @var{b}} bytes long.  The block's contents will be
1354 cleared to zeros.  Returns a null pointer if @var{a} or @var{b} is zero
1355 or if insufficient memory is available.
1356 @end deftypefun
1357
1358 @deftypefun {void *} realloc (void *@var{block}, size_t @var{new_size})
1359 Attempts to resize @var{block} to @var{new_size} bytes, possibly moving
1360 it in the process.  If successful, returns the new block, in which case
1361 the old block must no longer be accessed.  On failure, returns a null
1362 pointer, and the old block remains valid.
1363
1364 A call with @var{block} null is equivalent to @func{malloc}.  A call
1365 with @var{new_size} zero is equivalent to @func{free}.
1366 @end deftypefun
1367
1368 @deftypefun void free (void *@var{block})
1369 Frees @var{block}, which must have been previously returned by
1370 @func{malloc}, @func{calloc}, or @func{realloc} (and not yet freed).
1371 @end deftypefun
1372
1373 @node Virtual Addresses
1374 @section Virtual Addresses
1375
1376 A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
1377 and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
1378
1379 @example
1380 @group
1381                31               12 11        0
1382               +-------------------+-----------+
1383               |    Page Number    |   Offset  |
1384               +-------------------+-----------+
1385                        Virtual Address
1386 @end group
1387 @end example
1388
1389 Header @file{threads/vaddr.h} defines these functions and macros for
1390 working with virtual addresses:
1391
1392 @defmac PGSHIFT
1393 @defmacx PGBITS
1394 The bit index (0) and number of bits (12) of the offset part of a
1395 virtual address, respectively.
1396 @end defmac
1397
1398 @defmac PGMASK
1399 A bit mask with the bits in the page offset set to 1, the rest set to 0
1400 (@t{0xfff}).
1401 @end defmac
1402
1403 @defmac PGSIZE
1404 The page size in bytes (4,096).
1405 @end defmac
1406
1407 @deftypefun unsigned pg_ofs (const void *@var{va})
1408 Extracts and returns the page offset in virtual address @var{va}.
1409 @end deftypefun
1410
1411 @deftypefun uintptr_t pg_no (const void *@var{va})
1412 Extracts and returns the page number in virtual address @var{va}.
1413 @end deftypefun
1414
1415 @deftypefun {void *} pg_round_down (const void *@var{va})
1416 Returns the start of the virtual page that @var{va} points within, that
1417 is, @var{va} with the page offset set to 0.
1418 @end deftypefun
1419
1420 @deftypefun {void *} pg_round_up (const void *@var{va})
1421 Returns @var{va} rounded up to the nearest page boundary.
1422 @end deftypefun
1423
1424 Virtual memory in Pintos is divided into two regions: user virtual
1425 memory and kernel virtual memory (@pxref{Virtual Memory Layout}).  The
1426 boundary between them is @code{PHYS_BASE}:
1427
1428 @defmac PHYS_BASE
1429 Base address of kernel virtual memory.  It defaults to @t{0xc0000000} (3
1430 GB), but it may be changed to any multiple of @t{0x10000000} from
1431 @t{0x80000000} to @t{0xf0000000}.
1432
1433 User virtual memory ranges from virtual address 0 up to
1434 @code{PHYS_BASE}.  Kernel virtual memory occupies the rest of the
1435 virtual address space, from @code{PHYS_BASE} up to 4 GB.
1436 @end defmac
1437
1438 @deftypefun {bool} is_user_vaddr (const void *@var{va})
1439 @deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
1440 Returns true if @var{va} is a user or kernel virtual address,
1441 respectively, false otherwise.
1442 @end deftypefun
1443
1444 The 80@var{x}86 doesn't provide any way to directly access memory given
1445 a physical address.  This ability is often necessary in an operating
1446 system kernel, so Pintos works around it by mapping kernel virtual
1447 memory one-to-one to physical memory.  That is, virtual address
1448 @code{PHYS_BASE} accesses physical address 0, virtual address
1449 @code{PHYS_BASE} + @t{0x1234} accesses physical address @t{0x1234}, and
1450 so on up to the size of the machine's physical memory.  Thus, adding
1451 @code{PHYS_BASE} to a physical address obtains a kernel virtual address
1452 that accesses that address; conversely, subtracting @code{PHYS_BASE}
1453 from a kernel virtual address obtains the corresponding physical
1454 address.  Header @file{threads/vaddr.h} provides a pair of functions to
1455 do these translations:
1456
1457 @deftypefun {void *} ptov (uintptr_t @var{pa})
1458 Returns the kernel virtual address corresponding to physical address
1459 @var{pa}, which should be between 0 and the number of bytes of physical
1460 memory.
1461 @end deftypefun
1462
1463 @deftypefun {uintptr_t} vtop (void *@var{va})
1464 Returns the physical address corresponding to @var{va}, which must be a
1465 kernel virtual address.
1466 @end deftypefun
1467
1468 @node Page Table
1469 @section Page Table
1470
1471 The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
1472 hardware page table, also called a ``page directory'' by Intel processor
1473 documentation.  The page table interface uses a @code{uint32_t *} to
1474 represent a page table because this is convenient for accessing their
1475 internal structure.
1476
1477 The sections below describe the page table interface and internals.
1478
1479 @menu
1480 * Page Table Creation Destruction Activation::  
1481 * Page Tables Inspection and Updates::  
1482 * Page Table Accessed and Dirty Bits::  
1483 * Page Table Details::          
1484 @end menu
1485
1486 @node Page Table Creation Destruction Activation
1487 @subsection Creation, Destruction, and Activation
1488
1489 These functions create, destroy, and activate page tables.  The base
1490 Pintos code already calls these functions where necessary, so it should
1491 not be necessary to call them yourself.
1492
1493 @deftypefun {uint32_t *} pagedir_create (void)
1494 Creates and returns a new page table.  The new page table contains
1495 Pintos's normal kernel virtual page mappings, but no user virtual
1496 mappings.
1497
1498 Returns a null pointer if memory cannot be obtained.
1499 @end deftypefun
1500
1501 @deftypefun void pagedir_destroy (uint32_t *@var{pd})
1502 Frees all of the resources held by @var{pd}, including the page table
1503 itself and the frames that it maps.
1504 @end deftypefun
1505
1506 @deftypefun void pagedir_activate (uint32_t *@var{pd})
1507 Activates @var{pd}.  The active page table is the one used by the CPU to
1508 translate memory references.
1509 @end deftypefun
1510
1511 @node Page Tables Inspection and Updates
1512 @subsection Inspection and Updates
1513
1514 These functions examine or update the mappings from pages to frames
1515 encapsulated by a page table.  They work on both active and inactive
1516 page tables (that is, those for running and suspended processes),
1517 flushing the TLB as necessary.
1518
1519 @deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
1520 Adds to @var{pd} a mapping from user page @var{upage} to the frame identified
1521 by kernel virtual address @var{kpage}.  If @var{writable} is true, the
1522 page is mapped read/write; otherwise, it is mapped read-only.
1523
1524 User page @var{upage} must not already be mapped in @var{pd}.
1525
1526 Kernel page @var{kpage} should be a kernel virtual address obtained from
1527 the user pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why
1528 PAL_USER?}).
1529
1530 Returns true if successful, false on failure.  Failure will occur if
1531 additional memory required for the page table cannot be obtained.
1532 @end deftypefun
1533
1534 @deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
1535 Looks up the frame mapped to @var{uaddr} in @var{pd}.  Returns the
1536 kernel virtual address for that frame, if @var{uaddr} is mapped, or a
1537 null pointer if it is not.
1538 @end deftypefun
1539
1540 @deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{page})
1541 Marks @var{page} ``not present'' in @var{pd}.  Later accesses to
1542 the page will fault.
1543
1544 Other bits in the page table for @var{page} are preserved, permitting
1545 the accessed and dirty bits (see the next section) to be checked.
1546
1547 This function has no effect if @var{page} is not mapped.
1548 @end deftypefun
1549
1550 @node Page Table Accessed and Dirty Bits
1551 @subsection Accessed and Dirty Bits
1552
1553 80@var{x}86 hardware provides some assistance for implementing page
1554 replacement algorithms, through a pair of bits in the page table entry
1555 (PTE) for each page.  On any read or write to a page, the CPU sets the
1556 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
1557 sets the @dfn{dirty bit} to 1.  The CPU never resets these bits to 0,
1558 but the OS may do so.
1559
1560 Proper interpretation of these bits requires understanding of
1561 @dfn{aliases}, that is, two (or more) pages that refer to the same
1562 frame.  When an aliased frame is accessed, the accessed and dirty bits
1563 are updated in only one page table entry (the one for the page used for
1564 access).  The accessed and dirty bits for the other aliases are not
1565 updated.
1566
1567 @xref{Accessed and Dirty Bits}, on applying these bits in implementing
1568 page replacement algorithms.
1569
1570 @deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
1571 @deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
1572 Returns true if page directory @var{pd} contains a page table entry for
1573 @var{page} that is marked dirty (or accessed).  Otherwise,
1574 returns false.
1575 @end deftypefun
1576
1577 @deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1578 @deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1579 If page directory @var{pd} has a page table entry for @var{page}, then
1580 its dirty (or accessed) bit is set to @var{value}.
1581 @end deftypefun
1582
1583 @node Page Table Details
1584 @subsection Page Table Details
1585
1586 The functions provided with Pintos are sufficient to implement the
1587 projects.  However, you may still find it worthwhile to understand the
1588 hardware page table format, so we'll go into a little detail in this
1589 section.
1590
1591 @menu
1592 * Page Table Structure::        
1593 * Page Table Entry Format::     
1594 * Page Directory Entry Format::  
1595 @end menu
1596
1597 @node Page Table Structure
1598 @subsubsection Structure
1599
1600 The top-level paging data structure is a page called the ``page
1601 directory'' (PD) arranged as an array of 1,024 32-bit page directory
1602 entries (PDEs), each of which represents 4 MB of virtual memory.  Each
1603 PDE may point to the physical address of another page called a
1604 ``page table'' (PT) arranged, similarly, as an array of 1,024
1605 32-bit page table entries (PTEs), each of which translates a single 4
1606 kB virtual page to a physical page.
1607
1608 Translation of a virtual address into a physical address follows
1609 the three-step process illustrated in the diagram
1610 below:@footnote{Actually, virtual to physical translation on the
1611 80@var{x}86 architecture occurs via an intermediate ``linear
1612 address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
1613 so that linear and virtual addresses are one and the same.  Thus, you
1614 can effectively ignore this CPU feature.}
1615
1616 @enumerate 1
1617 @item
1618 The most-significant 10 bits of the virtual address (bits 22@dots{}31)
1619 index the page directory.  If the PDE is marked ``present,'' the
1620 physical address of a page table is read from the PDE thus obtained.
1621 If the PDE is marked ``not present'' then a page fault occurs.
1622
1623 @item
1624 The next 10 bits of the virtual address (bits 12@dots{}21) index
1625 the page table.  If the PTE is marked ``present,'' the physical
1626 address of a data page is read from the PTE thus obtained.  If the PTE
1627 is marked ``not present'' then a page fault occurs.
1628
1629 @item
1630 The least-significant 12 bits of the virtual address (bits 0@dots{}11)
1631 are added to the data page's physical base address, yielding the final
1632 physical address.
1633 @end enumerate
1634
1635 @example
1636 @group
1637  31                  22 21                  12 11                   0
1638 +----------------------+----------------------+----------------------+
1639 | Page Directory Index |   Page Table Index   |    Page Offset       |
1640 +----------------------+----------------------+----------------------+
1641              |                    |                     |
1642      _______/             _______/                _____/
1643     /                    /                       /
1644    /    Page Directory  /      Page Table       /    Data Page
1645   /     .____________. /     .____________.    /   .____________.
1646   |1,023|____________| |1,023|____________|    |   |____________|
1647   |1,022|____________| |1,022|____________|    |   |____________|
1648   |1,021|____________| |1,021|____________|    \__\|____________|
1649   |1,020|____________| |1,020|____________|       /|____________|
1650   |     |            | |     |            |        |            |
1651   |     |            | \____\|            |_       |            |
1652   |     |      .     |      /|      .     | \      |      .     |
1653   \____\|      .     |_      |      .     |  |     |      .     |
1654        /|      .     | \     |      .     |  |     |      .     |
1655         |      .     |  |    |      .     |  |     |      .     |
1656         |            |  |    |            |  |     |            |
1657         |____________|  |    |____________|  |     |____________|
1658        4|____________|  |   4|____________|  |     |____________|
1659        3|____________|  |   3|____________|  |     |____________|
1660        2|____________|  |   2|____________|  |     |____________|
1661        1|____________|  |   1|____________|  |     |____________|
1662        0|____________|  \__\0|____________|  \____\|____________|
1663                            /                      /
1664 @end group
1665 @end example
1666
1667 Pintos provides some macros and functions that are useful for working
1668 with raw page tables:
1669
1670 @defmac PTSHIFT
1671 @defmacx PTBITS
1672 The starting bit index (12) and number of bits (10), respectively, in a
1673 page table index.
1674 @end defmac
1675
1676 @defmac PTMASK
1677 A bit mask with the bits in the page table index set to 1 and the rest
1678 set to 0 (@t{0x3ff000}).
1679 @end defmac
1680
1681 @defmac PTSPAN
1682 The number of bytes of virtual address space that a single page table
1683 page covers (4,194,304 bytes, or 4 MB).
1684 @end defmac
1685
1686 @defmac PDSHIFT
1687 @defmacx PDBITS
1688 The starting bit index (22) and number of bits (10), respectively, in a
1689 page directory index.
1690 @end defmac
1691
1692 @defmac PDMASK
1693 A bit mask with the bits in the page directory index set to 1 and other
1694 bits set to 0 (@t{0xffc00000}).
1695 @end defmac
1696
1697 @deftypefun uintptr_t pd_no (const void *@var{va})
1698 @deftypefunx uintptr_t pt_no (const void *@var{va})
1699 Returns the page directory index or page table index, respectively, for
1700 virtual address @var{va}.  These functions are defined in
1701 @file{threads/pte.h}.
1702 @end deftypefun
1703
1704 @deftypefun unsigned pg_ofs (const void *@var{va})
1705 Returns the page offset for virtual address @var{va}.  This function is
1706 defined in @file{threads/vaddr.h}.
1707 @end deftypefun
1708
1709 @node Page Table Entry Format
1710 @subsubsection Page Table Entry Format
1711
1712 You do not need to understand the PTE format to do the Pintos
1713 projects, unless you wish to incorporate the page table into your
1714 supplemental page table (@pxref{Managing the Supplemental Page Table}).
1715
1716 The actual format of a page table entry is summarized below.  For
1717 complete information, refer to section 3.7, ``Page Translation Using
1718 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
1719
1720 @example
1721 @group
1722  31                                   12 11 9      6 5     2 1 0
1723 +---------------------------------------+----+----+-+-+---+-+-+-+
1724 |           Physical Address            | AVL|    |D|A|   |U|W|P|
1725 +---------------------------------------+----+----+-+-+---+-+-+-+
1726 @end group
1727 @end example
1728
1729 Some more information on each bit is given below.  The names are
1730 @file{threads/pte.h} macros that represent the bits' values:
1731
1732 @defmac PTE_P
1733 Bit 0, the ``present'' bit.  When this bit is 1, the
1734 other bits are interpreted as described below.  When this bit is 0, any
1735 attempt to access the page will page fault.  The remaining bits are then
1736 not used by the CPU and may be used by the OS for any purpose.
1737 @end defmac
1738
1739 @defmac PTE_W
1740 Bit 1, the ``read/write'' bit.  When it is 1, the page
1741 is writable.  When it is 0, write attempts will page fault.
1742 @end defmac
1743
1744 @defmac PTE_U
1745 Bit 2, the ``user/supervisor'' bit.  When it is 1, user
1746 processes may access the page.  When it is 0, only the kernel may access
1747 the page (user accesses will page fault).
1748
1749 Pintos clears this bit in PTEs for kernel virtual memory, to prevent
1750 user processes from accessing them.
1751 @end defmac
1752  
1753 @defmac PTE_A
1754 Bit 5, the ``accessed'' bit.  @xref{Page Table Accessed
1755 and Dirty Bits}.
1756 @end defmac
1757
1758 @defmac PTE_D
1759 Bit 6, the ``dirty'' bit.  @xref{Page Table Accessed and
1760 Dirty Bits}.
1761 @end defmac
1762
1763 @defmac PTE_AVL
1764 Bits 9@dots{}11, available for operating system use.
1765 Pintos, as provided, does not use them and sets them to 0.
1766 @end defmac
1767
1768 @defmac PTE_ADDR
1769 Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
1770 The low 12 bits of the frame's address are always 0.
1771 @end defmac
1772
1773 Other bits are either reserved or uninteresting in a Pintos context and
1774 should be set to@tie{}0.
1775
1776 Header @file{threads/pte.h} defines three functions for working with
1777 page table entries:
1778
1779 @deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
1780 Returns a page table entry that points to @var{page}, which should be a
1781 kernel virtual address.  The PTE's present bit will be set.  It will be
1782 marked for kernel-only access.  If @var{writable} is true, the PTE will
1783 also be marked read/write; otherwise, it will be read-only.
1784 @end deftypefun
1785
1786 @deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
1787 Returns a page table entry that points to @var{page}, which should be
1788 the kernel virtual address of a frame in the user pool (@pxref{Why
1789 PAL_USER?}).  The PTE's present bit will be set and it will be marked to
1790 allow user-mode access.  If @var{writable} is true, the PTE will also be
1791 marked read/write; otherwise, it will be read-only.
1792 @end deftypefun
1793
1794 @deftypefun {void *} pte_get_page (uint32_t @var{pte})
1795 Returns the kernel virtual address for the frame that @var{pte} points
1796 to.  The @var{pte} may be present or not-present; if it is not-present
1797 then the pointer returned is only meaningful if the address bits in the PTE
1798 actually represent a physical address.
1799 @end deftypefun
1800
1801 @node Page Directory Entry Format
1802 @subsubsection Page Directory Entry Format
1803
1804 Page directory entries have the same format as PTEs, except that the
1805 physical address points to a page table page instead of a frame.  Header
1806 @file{threads/pte.h} defines two functions for working with page
1807 directory entries:
1808
1809 @deftypefun uint32_t pde_create (uint32_t *@var{pt})
1810 Returns a page directory that points to @var{page}, which should be the
1811 kernel virtual address of a page table page.  The PDE's present bit will
1812 be set, it will be marked to allow user-mode access, and it will be
1813 marked read/write.
1814 @end deftypefun
1815
1816 @deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
1817 Returns the kernel virtual address for the page table page that
1818 @var{pde}, which must be marked present, points to.
1819 @end deftypefun
1820
1821 @node Hash Table
1822 @section Hash Table
1823
1824 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1825 To use it you will need to include its header file,
1826 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}.
1827 No code provided with Pintos uses the hash table, which means that you
1828 are free to use it as is, modify its implementation for your own
1829 purposes, or ignore it, as you wish.
1830
1831 Most implementations of the virtual memory project use a hash table to
1832 translate pages to frames.  You may find other uses for hash tables as
1833 well.
1834
1835 @menu
1836 * Hash Data Types::             
1837 * Basic Hash Functions::        
1838 * Hash Search Functions::       
1839 * Hash Iteration Functions::    
1840 * Hash Table Example::          
1841 * Hash Auxiliary Data::         
1842 * Hash Synchronization::        
1843 @end menu
1844
1845 @node Hash Data Types
1846 @subsection Data Types
1847
1848 A hash table is represented by @struct{hash}.
1849
1850 @deftp {Type} {struct hash}
1851 Represents an entire hash table.  The actual members of @struct{hash}
1852 are ``opaque.''  That is, code that uses a hash table should not access
1853 @struct{hash} members directly, nor should it need to.  Instead, use
1854 hash table functions and macros.
1855 @end deftp
1856
1857 The hash table operates on elements of type @struct{hash_elem}.
1858
1859 @deftp {Type} {struct hash_elem}
1860 Embed a @struct{hash_elem} member in the structure you want to include
1861 in a hash table.  Like @struct{hash}, @struct{hash_elem} is opaque.
1862 All functions for operating on hash table elements actually take and
1863 return pointers to @struct{hash_elem}, not pointers to your hash table's
1864 real element type.
1865 @end deftp
1866
1867 You will often need to obtain a @struct{hash_elem} given a real element
1868 of the hash table, and vice versa.  Given a real element of the hash
1869 table, you may use the @samp{&} operator to obtain a pointer to its
1870 @struct{hash_elem}.  Use the @code{hash_entry()} macro to go the other
1871 direction.
1872
1873 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1874 Returns a pointer to the structure that @var{elem}, a pointer to a
1875 @struct{hash_elem}, is embedded within.  You must provide @var{type},
1876 the name of the structure that @var{elem} is inside, and @var{member},
1877 the name of the member in @var{type} that @var{elem} points to.
1878
1879 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1880 that points to a @struct{thread} member (of type @struct{hash_elem})
1881 named @code{h_elem}.  Then, @code{hash_entry@tie{}(h, struct thread, h_elem)}
1882 yields the address of the @struct{thread} that @code{h} points within.
1883 @end deftypefn
1884
1885 @xref{Hash Table Example}, for an example.
1886
1887 Each hash table element must contain a key, that is, data that
1888 identifies and distinguishes elements, which must be unique
1889 among elements in the hash table.  (Elements may
1890 also contain non-key data that need not be unique.)  While an element is
1891 in a hash table, its key data must not be changed.  Instead, if need be,
1892 remove the element from the hash table, modify its key, then reinsert
1893 the element.
1894
1895 For each hash table, you must write two functions that act on keys: a
1896 hash function and a comparison function.  These functions must match the
1897 following prototypes:
1898
1899 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1900 Returns a hash of @var{element}'s data, as a value anywhere in the range
1901 of @code{unsigned int}.  The hash of an element should be a
1902 pseudo-random function of the element's key.  It must not depend on
1903 non-key data in the element or on any non-constant data other than the
1904 key.  Pintos provides the following functions as a suitable basis for
1905 hash functions.
1906
1907 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1908 Returns a hash of the @var{size} bytes starting at @var{buf}.  The
1909 implementation is the general-purpose
1910 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1911 hash} for 32-bit words.
1912 @end deftypefun
1913
1914 @deftypefun unsigned hash_string (const char *@var{s})
1915 Returns a hash of null-terminated string @var{s}.
1916 @end deftypefun
1917
1918 @deftypefun unsigned hash_int (int @var{i})
1919 Returns a hash of integer @var{i}.
1920 @end deftypefun
1921
1922 If your key is a single piece of data of an appropriate type, it is
1923 sensible for your hash function to directly return the output of one of
1924 these functions.  For multiple pieces of data, you may wish to combine
1925 the output of more than one call to them using, e.g., the @samp{^}
1926 (exclusive or)
1927 operator.  Finally, you may entirely ignore these functions and write
1928 your own hash function from scratch, but remember that your goal is to
1929 build an operating system kernel, not to design a hash function.
1930
1931 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1932 @end deftp
1933
1934 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1935 Compares the keys stored in elements @var{a} and @var{b}.  Returns
1936 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1937 or equal to @var{b}.
1938
1939 If two elements compare equal, then they must hash to equal values.
1940
1941 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1942 @end deftp
1943
1944 @xref{Hash Table Example}, for hash and comparison function examples.
1945
1946 A few functions accept a pointer to a third kind of
1947 function as an argument:
1948
1949 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1950 Performs some kind of action, chosen by the caller, on @var{element}.
1951
1952 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1953 @end deftp
1954
1955 @node Basic Hash Functions
1956 @subsection Basic Functions
1957
1958 These functions create, destroy, and inspect hash tables.
1959
1960 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
1961 Initializes @var{hash} as a hash table with @var{hash_func} as hash
1962 function, @var{less_func} as comparison function, and @var{aux} as
1963 auxiliary data.
1964 Returns true if successful, false on failure.  @func{hash_init} calls
1965 @func{malloc} and fails if memory cannot be allocated.
1966
1967 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
1968 most often a null pointer.
1969 @end deftypefun
1970
1971 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
1972 Removes all the elements from @var{hash}, which must have been
1973 previously initialized with @func{hash_init}.
1974
1975 If @var{action} is non-null, then it is called once for each element in
1976 the hash table, which gives the caller an opportunity to deallocate any
1977 memory or other resources used by the element.  For example, if the hash
1978 table elements are dynamically allocated using @func{malloc}, then
1979 @var{action} could @func{free} the element.  This is safe because
1980 @func{hash_clear} will not access the memory in a given hash element
1981 after calling @var{action} on it.  However, @var{action} must not call
1982 any function that may modify the hash table, such as @func{hash_insert}
1983 or @func{hash_delete}.
1984 @end deftypefun
1985
1986 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
1987 If @var{action} is non-null, calls it for each element in the hash, with
1988 the same semantics as a call to @func{hash_clear}.  Then, frees the
1989 memory held by @var{hash}.  Afterward, @var{hash} must not be passed to
1990 any hash table function, absent an intervening call to @func{hash_init}.
1991 @end deftypefun
1992
1993 @deftypefun size_t hash_size (struct hash *@var{hash})
1994 Returns the number of elements currently stored in @var{hash}.
1995 @end deftypefun
1996
1997 @deftypefun bool hash_empty (struct hash *@var{hash})
1998 Returns true if @var{hash} currently contains no elements,
1999 false if @var{hash} contains at least one element.
2000 @end deftypefun
2001
2002 @node Hash Search Functions
2003 @subsection Search Functions
2004
2005 Each of these functions searches a hash table for an element that
2006 compares equal to one provided.  Based on the success of the search,
2007 they perform some action, such as inserting a new element into the hash
2008 table, or simply return the result of the search.
2009
2010 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
2011 Searches @var{hash} for an element equal to @var{element}.  If none is
2012 found, inserts @var{element} into @var{hash} and returns a null pointer.
2013 If the table already contains an element equal to @var{element}, it is
2014 returned without modifying @var{hash}.
2015 @end deftypefun
2016
2017 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
2018 Inserts @var{element} into @var{hash}.  Any element equal to
2019 @var{element} already in @var{hash} is removed.  Returns the element
2020 removed, or a null pointer if @var{hash} did not contain an element
2021 equal to @var{element}.
2022
2023 The caller is responsible for deallocating any resources associated with
2024 the returned element, as appropriate.  For example, if the hash table
2025 elements are dynamically allocated using @func{malloc}, then the caller
2026 must @func{free} the element after it is no longer needed.
2027 @end deftypefun
2028
2029 The element passed to the following functions is only used for hashing
2030 and comparison purposes.  It is never actually inserted into the hash
2031 table.  Thus, only key data in the element needs to be initialized, and
2032 other data in the element will not be used.  It often makes sense to
2033 declare an instance of the element type as a local variable, initialize
2034 the key data, and then pass the address of its @struct{hash_elem} to
2035 @func{hash_find} or @func{hash_delete}.  @xref{Hash Table Example}, for
2036 an example.  (Large structures should not be
2037 allocated as local variables.  @xref{struct thread}, for more
2038 information.)
2039
2040 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
2041 Searches @var{hash} for an element equal to @var{element}.  Returns the
2042 element found, if any, or a null pointer otherwise.
2043 @end deftypefun
2044
2045 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
2046 Searches @var{hash} for an element equal to @var{element}.  If one is
2047 found, it is removed from @var{hash} and returned.  Otherwise, a null
2048 pointer is returned and @var{hash} is unchanged.
2049
2050 The caller is responsible for deallocating any resources associated with
2051 the returned element, as appropriate.  For example, if the hash table
2052 elements are dynamically allocated using @func{malloc}, then the caller
2053 must @func{free} the element after it is no longer needed.
2054 @end deftypefun
2055
2056 @node Hash Iteration Functions
2057 @subsection Iteration Functions
2058
2059 These functions allow iterating through the elements in a hash table.
2060 Two interfaces are supplied.  The first requires writing and supplying a
2061 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
2062
2063 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
2064 Calls @var{action} once for each element in @var{hash}, in arbitrary
2065 order.  @var{action} must not call any function that may modify the hash
2066 table, such as @func{hash_insert} or @func{hash_delete}.  @var{action}
2067 must not modify key data in elements, although it may modify any other
2068 data.
2069 @end deftypefun
2070
2071 The second interface is based on an ``iterator'' data type.
2072 Idiomatically, iterators are used as follows:
2073
2074 @example
2075 struct hash_iterator i;
2076
2077 hash_first (&i, h);
2078 while (hash_next (&i))
2079   @{
2080     struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
2081     @r{@dots{}do something with @i{f}@dots{}}
2082   @}
2083 @end example
2084
2085 @deftp {Type} {struct hash_iterator}
2086 Represents a position within a hash table.  Calling any function that
2087 may modify a hash table, such as @func{hash_insert} or
2088 @func{hash_delete}, invalidates all iterators within that hash table.
2089
2090 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
2091 @end deftp
2092
2093 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
2094 Initializes @var{iterator} to just before the first element in
2095 @var{hash}.
2096 @end deftypefun
2097
2098 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
2099 Advances @var{iterator} to the next element in @var{hash}, and returns
2100 that element.  Returns a null pointer if no elements remain.  After
2101 @func{hash_next} returns null for @var{iterator}, calling it again
2102 yields undefined behavior.
2103 @end deftypefun
2104
2105 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
2106 Returns the value most recently returned by @func{hash_next} for
2107 @var{iterator}.  Yields undefined behavior after @func{hash_first} has
2108 been called on @var{iterator} but before @func{hash_next} has been
2109 called for the first time.
2110 @end deftypefun
2111
2112 @node Hash Table Example
2113 @subsection Hash Table Example
2114
2115 Suppose you have a structure, called @struct{page}, that you
2116 want to put into a hash table.  First, define @struct{page} to include a
2117 @struct{hash_elem} member:
2118
2119 @example
2120 struct page
2121   @{
2122     struct hash_elem hash_elem; /* @r{Hash table element.} */
2123     void *addr;                 /* @r{Virtual address.} */
2124     /* @r{@dots{}other members@dots{}} */
2125   @};
2126 @end example
2127
2128 We write a hash function and a comparison function using @var{addr} as
2129 the key.  A pointer can be hashed based on its bytes, and the @samp{<}
2130 operator works fine for comparing pointers:
2131
2132 @example
2133 /* @r{Returns a hash value for page @var{p}.} */
2134 unsigned
2135 page_hash (const struct hash_elem *p_, void *aux UNUSED)
2136 @{
2137   const struct page *p = hash_entry (p_, struct page, hash_elem);
2138   return hash_bytes (&p->addr, sizeof p->addr);
2139 @}
2140
2141 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
2142 bool
2143 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2144            void *aux UNUSED)
2145 @{
2146   const struct page *a = hash_entry (a_, struct page, hash_elem);
2147   const struct page *b = hash_entry (b_, struct page, hash_elem);
2148
2149   return a->addr < b->addr;
2150 @}
2151 @end example
2152
2153 @noindent
2154 (The use of @code{UNUSED} in these functions' prototypes suppresses a
2155 warning that @var{aux} is unused.  @xref{Function and Parameter
2156 Attributes}, for information about @code{UNUSED}.  @xref{Hash Auxiliary
2157 Data}, for an explanation of @var{aux}.)
2158
2159 Then, we can create a hash table like this:
2160
2161 @example
2162 struct hash pages;
2163
2164 hash_init (&pages, page_hash, page_less, NULL);
2165 @end example
2166
2167 Now we can manipulate the hash table we've created.  If @code{@var{p}}
2168 is a pointer to a @struct{page}, we can insert it into the hash table
2169 with:
2170
2171 @example
2172 hash_insert (&pages, &p->hash_elem);
2173 @end example
2174
2175 @noindent If there's a chance that @var{pages} might already contain a
2176 page with the same @var{addr}, then we should check @func{hash_insert}'s
2177 return value.
2178
2179 To search for an element in the hash table, use @func{hash_find}.  This
2180 takes a little setup, because @func{hash_find} takes an element to
2181 compare against.  Here's a function that will find and return a page
2182 based on a virtual address, assuming that @var{pages} is defined at file
2183 scope:
2184
2185 @example
2186 /* @r{Returns the page containing the given virtual @var{address},}
2187    @r{or a null pointer if no such page exists.} */
2188 struct page *
2189 page_lookup (const void *address)
2190 @{
2191   struct page p;
2192   struct hash_elem *e;
2193
2194   p.addr = address;
2195   e = hash_find (&pages, &p.hash_elem);
2196   return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
2197 @}
2198 @end example
2199
2200 @noindent
2201 @struct{page} is allocated as a local variable here on the assumption
2202 that it is fairly small.  Large structures should not be allocated as
2203 local variables.  @xref{struct thread}, for more information.
2204
2205 A similar function could delete a page by address using
2206 @func{hash_delete}.
2207
2208 @node Hash Auxiliary Data
2209 @subsection Auxiliary Data
2210
2211 In simple cases like the example above, there's no need for the
2212 @var{aux} parameters.  In these cases, just pass a null pointer to
2213 @func{hash_init} for @var{aux} and ignore the values passed to the hash
2214 function and comparison functions.  (You'll get a compiler warning if
2215 you don't use the @var{aux} parameter, but you can turn that off with
2216 the @code{UNUSED} macro, as shown in the example, or you can just ignore
2217 it.)
2218
2219 @var{aux} is useful when you have some property of the data in the
2220 hash table is both constant and needed for hashing or comparison,
2221 but not stored in the data items themselves.  For example, if
2222 the items in a hash table are fixed-length strings, but the items
2223 themselves don't indicate what that fixed length is, you could pass
2224 the length as an @var{aux} parameter.
2225
2226 @node Hash Synchronization
2227 @subsection Synchronization
2228
2229 The hash table does not do any internal synchronization.  It is the
2230 caller's responsibility to synchronize calls to hash table functions.
2231 In general, any number of functions that examine but do not modify the
2232 hash table, such as @func{hash_find} or @func{hash_next}, may execute
2233 simultaneously.  However, these function cannot safely execute at the
2234 same time as any function that may modify a given hash table, such as
2235 @func{hash_insert} or @func{hash_delete}, nor may more than one function
2236 that can modify a given hash table execute safely at once.
2237
2238 It is also the caller's responsibility to synchronize access to data in
2239 hash table elements.  How to synchronize access to this data depends on
2240 how it is designed and organized, as with any other data structure.
2241