Finish that thought.
[pintos-anon] / doc / tour.texi
1 @node Pintos Tour, Project 1--Threads, Introduction, Top
2 @chapter A Tour Through Pintos
3
4 This chapter is a brief tour through 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 corresponding project.
8
9 Hint: try using ``tags'' to follow along with references to function
10 and variable names (@pxref{Tags}).
11
12 @menu
13 * Pintos Loading::              
14 * Threads Tour::                
15 @end menu
16
17 @node Pintos Loading
18 @section Loading
19
20 This section covers the Pintos loader and basic kernel
21 initialization.
22
23 @menu
24 * Pintos Loader::               
25 * Kernel Initialization::       
26 @end menu
27
28 @node Pintos Loader
29 @subsection The Loader
30
31 The first part of Pintos that runs is the loader, in
32 @file{threads/loader.S}.  The PC BIOS loads the loader into memory.
33 The loader, in turn, is responsible for initializing the CPU, loading
34 the rest of Pintos into memory, and then jumping to its start.  It's
35 not important to understand exactly what the loader does, but if
36 you're interested, read on.  You should probably read along with the
37 loader's source.  You should also understand the basics of the
38 80@var{x}86 architecture as described by chapter 3 of
39 @bibref{IA32-v1}.
40
41 Because the PC BIOS loads the loader, the loader has to play by the
42 BIOS's rules.  In particular, the BIOS only loads 512 bytes (one disk
43 sector) into memory.  This is a severe restriction and it means that,
44 practically speaking, the loader has to be written in assembly
45 language.
46
47 Pintos' loader first initializes the CPU.  The first important part of
48 this is to enable the A20 line, that is, the CPU's address line
49 numbered 20.  For historical reasons, PCs start out with this address
50 line fixed at 0, which means that attempts to access memory beyond the
51 first 1 MB (2 raised to the 20th power) will fail.  Pintos wants to
52 access more memory than this, so we have to enable it.
53
54 Next, the loader asks the BIOS for the PC's memory size.  Again for
55 historical reasons, the function that we call in the BIOS to do this
56 can only detect up to 64 MB of RAM, so that's the practical limit that
57 Pintos can support.  The memory size is stashed away in a location in
58 the loader that the kernel can read after it boots.
59
60 Third, the loader creates a basic page table.  This page table maps
61 the 64 MB at the base of virtual memory (starting at virtual address
62 0) directly to the identical physical addresses.  It also maps the
63 same physical memory starting at virtual address
64 @code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB).  The
65 Pintos kernel only wants the latter mapping, but there's a
66 chicken-and-egg problem if we don't include the former: our current
67 virtual address is roughly @t{0x7c00}, the location where the BIOS
68 loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
69 page table, but if we turn on the page table without jumping there,
70 then we've just pulled the rug out from under ourselves.  At any rate,
71 it's necessary.
72
73 After the page table is initialized, we load the CPU's control
74 registers to turn on protected mode and paging, and then we set up the
75 segment registers.  We aren't equipped to handle interrupts in
76 protected mode yet, so we disable interrupts.
77
78 Finally it's time to load the kernel from disk.  We choose a simple,
79 although inflexible, method to do this: we program the IDE disk
80 controller directly.  We assume that the kernel is stored starting
81 from the second sector of the first IDE disk (the first sector
82 contains the boot loader itself).  We also assume that the BIOS has
83 already set up the IDE controller for us.  We read
84 @code{KERNEL_LOAD_PAGES} 4 kB pages of data from the disk directly
85 into virtual memory starting @code{LOADER_KERN_BASE} bytes past
86 @code{LOADER_PHYS_BASE}, which by default means that we load the
87 kernel starting 1 MB into physical memory.
88
89 Then we jump to the start of the compiled kernel image.  Using the
90 ``linker script'' in @file{threads/kernel.lds.S}, the kernel has
91 arranged that it begins with the assembly module
92 @file{threads/start.S}.  This assembly module just calls
93 @func{main}, which never returns.
94
95 There's one more trick to the loader: the Pintos kernel command line
96 is stored in the boot loader.  The @command{pintos} program actually
97 modifies the boot loader on disk each time it runs the kernel, putting
98 in whatever command line arguments the user supplies to the kernel,
99 and then the kernel at boot time reads those arguments out of the boot
100 loader in memory.  This is something of a nasty hack, but it is simple
101 and effective.
102
103 @node Kernel Initialization
104 @subsection Kernel Initialization
105
106 The kernel proper starts with the @func{main} function.  The
107 @func{main} function is written in C, as will be most of the code we
108 encounter in Pintos from here on out.
109
110 When @func{main} starts, the system is in a pretty raw state.  We're
111 in protected mode with paging enabled, but hardly anything else is
112 ready.  Thus, the @func{main} function consists primarily of calls
113 into other Pintos modules' initialization functions.  You should
114 notice that these are usually named @func{@var{module}_init}, where
115 @var{module} is the module's name, @file{@var{module}.c} is the
116 module's source code, and @file{@var{module}.h} is the module's
117 header.
118
119 First we initialize kernel RAM in @func{ram_init}.  The first step
120 is to clear out the kernel's so-called ``BSS'' segment.  The BSS is a
121 segment that should be initialized to all zeros.  In C, whenever you
122 declare a variable outside a function without providing an
123 initializer, that variable goes into the BSS.@footnote{This isn't
124 actually required by the ANSI C standard, but it is the case with most
125 implementations of C on most machines.}  Because it's all zeros, the
126 BSS isn't stored in the image that the loader brought into memory.  We
127 just use @func{memset} to zero it out.  The other task of
128 @func{ram_init} is to read out the machine's memory size from where
129 the loader stored it and put it into the @code{ram_pages} variable for
130 later use.
131
132 Next, @func{thread_init} initializes the thread system.  We will defer
133 full discussion to our discussion of Pintos threads below.  It is
134 called so early in initialization because the console, initialized
135 just below, tries to use locks and locks in turn require there to be a
136 running thread.
137
138 Then we initialize the console so that we can use @func{printf}.
139 @func{main} calls @func{vga_init}, which initializes the VGA text
140 display and clears the screen.  It also calls @func{serial_init_poll}
141 to initialize the first serial port in ``polling mode,'' that is,
142 where the kernel busy-waits for the port to be ready for each
143 character to be output.  (We use polling mode until we're ready to set
144 up interrupts later.)  Finally we initialize the console device and
145 print a startup message to the console.
146
147 @func{main} calls @func{argv_init} to parse the kernel command line.
148 This entails reading the command line out of the loader and updating
149 global variables appropriately.
150
151 The next block of functions we call initialize 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.  @func{malloc_init} sets
154 up the allocator that handles odd-sized allocations.
155 @func{paging_init} sets up a page table for the kernel.
156
157 In projects 2 and later, @func{main} also calls @func{tss_init} and
158 @func{gdt_init}, but we'll talk about those later.
159
160 @func{main} calls @func{random_init} to initialize the kernel random
161 number generator.  @func{argv_init} might already have done this (if
162 the user specified @option{-rs} on the @command{pintos} command line)
163 but calling it a second time is harmless and has no effect.
164
165 We initialize the interrupt system in the next set of calls.
166 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
167 (IDT) to ready it for interrupt handling, then @func{timer_init} and
168 @func{kbd_init} prepare us to handle timer interrupts and keyboard
169 interrupts, respectively.  In projects 2 and later, we also prepare to
170 handle interrupts caused by user programs using @func{exception_init}
171 and @func{syscall_init}.
172
173 Now that interrupts are set up, we can start preemptively scheduling
174 threads with @func{thread_start}, which also enables interrupts.
175 Interrupt-driven serial port I/O is also possible now, so we use
176 @func{serial_init_queue} to switch to that mode.
177
178 If the filesystem is compiled in, as it will be in project 2 and
179 later, we now initialize the disks with @func{disk_init}, then the
180 filesystem with @func{filesys_init}, and run any operations that were
181 requested on the kernel command line with @func{fsutil_run}.
182
183 Boot is complete, so we print a message.
184
185 For project 1, now we execute @func{test}, which runs whatever test is
186 currently compiled into the kernel.  For later projects, we will
187 instead run a user program and wait for it to complete.
188
189 Finally, if @option{-q} was specified on the kernel command line, we
190 call @func{power_off} to terminate the machine simulator.  Otherwise,
191 @func{main} calls @func{thread_exit}, which allows any other running
192 threads to continue running.
193
194 @node Threads Tour
195 @section Threads
196
197 @menu
198 * struct thread::               
199 * Thread Functions::            
200 * Thread Switching::            
201 * Synchronization::             
202 * Interrupt Handling::          
203 * Memory Allocation::           
204 @end menu
205
206 @node struct thread
207 @subsection @code{struct thread}
208
209 The main Pintos data structure for threads is @struct{thread},
210 declared in @file{threads/thread.h}.  @struct{thread} has these
211 members with the given type:
212
213 @table @code
214 @item tid_t tid;
215 The thread's thread identifier or @dfn{tid}.  Every thread must have a
216 tid that is unique over the entire lifetime of the kernel.  By
217 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
218 thread receives the numerically next higher tid, starting from 1 for
219 the initial process.  You can change the type and the numbering scheme
220 if you like.
221
222 @item enum thread_status status;
223 The thread's state, one of these:
224
225 @table @code
226 @item THREAD_RUNNING
227 The thread is running.  Exactly one thread is running at a given time.
228 @func{thread_current} returns the running thread.
229
230 @item THREAD_READY
231 The thread is ready to run, but it's not running right now.  The
232 thread could be selected to run the next time the scheduler is
233 invoked.  Ready threads are kept in a doubly linked list called
234 @code{ready_list}.
235
236 @item THREAD_BLOCKED
237 The thread is waiting for something, e.g.@: a lock to become
238 available, an interrupt to be invoked.  The thread won't be scheduled
239 again until it transitions to the @code{THREAD_READY} state with a
240 call to @func{thread_unblock}.
241
242 @item THREAD_DYING
243 The thread will be destroyed by the scheduler after switching to the
244 next thread.
245 @end table
246
247 @item char name[16];
248 The thread's name as a string, or at least the first few characters of
249 it.
250
251 @item uint8_t *stack;
252 Every thread has its own stack to keep track of its state.  When the
253 thread is running, the CPU's stack pointer register tracks the top of
254 the stack and this member is unused.  But when the CPU switches to
255 another thread, this member saves the thread's stack pointer.  No
256 other members are needed to save the thread's registers, because the
257 other registers that must be saved are saved on the stack.
258
259 @item int priority;
260 A thread priority, ranging from the lowest possible priority
261 @code{PRI_MIN} (0) to the highest possible priority @code{PRI_MAX}
262 (59).  Pintos as provided ignores thread priorities, but you will
263 implement priority scheduling in problem 1-3 (@pxref{Problem 1-3
264 Priority Scheduling}).
265
266 @item list_elem elem;
267 A ``list element'' used to put the thread into doubly linked lists,
268 either the list of threads ready to run or a list of threads waiting
269 on a semaphore.  Take a look at @file{lib/kernel/list.h} for
270 information on how to use the Pintos doubly linked list ADT.
271
272 @item uint32_t *pagedir;
273 Only present in project 2 and later.
274
275 @item unsigned magic;
276 Always set to @code{THREAD_MAGIC}, which is just a random number
277 defined in @file{threads/thread.c}, and used to detect stack overflow.
278 See below for more information.
279 @end table
280
281 Every @struct{thread} occupies the beginning of its own page of
282 memory.  The rest of the page is used for the thread's stack, which
283 grows downward from the end of the page.  It looks like this:
284
285 @example
286 @group
287         4 kB +---------------------------------+
288              |          kernel stack           |
289              |                |                |
290              |                |                |
291              |                V                |
292              |         grows downward          |
293              |                                 |
294              |                                 |
295              |                                 |
296              |                                 |
297              |                                 |
298              |                                 |
299              |                                 |
300              |                                 |
301              +---------------------------------+
302              |              magic              |
303              |                :                |
304              |                :                |
305              |               name              |
306              |              status             |
307         0 kB +---------------------------------+
308 @end group
309 @end example
310
311 The upshot of this is twofold.  First, @struct{thread} must not be
312 allowed to grow too big.  If it does, then there will not be enough
313 room for the kernel stack.  Our base @struct{thread} is only a few
314 bytes in size.  It probably should stay well under 1 kB.
315
316 Second, kernel stacks must not be allowed to grow too large.  If a
317 stack overflows, it will corrupt the thread state.  Thus, kernel
318 functions should not allocate large structures or arrays as non-static
319 local variables.  Use dynamic allocation with @func{malloc} or
320 @func{palloc_get_page} instead.
321
322 This brings us to the purpose of @struct{thread}'s @code{magic}
323 member.  If a thread's stack does overflow, then @code{magic} will be
324 the first member of @struct{thread} to be overwritten, because it is
325 closest to the kernel stack.  Thus, some of the thread functions
326 (notably @func{thread_current}) check that @code{magic} has the proper
327 value.
328
329 @node Thread Functions
330 @subsection Thread Functions
331
332 @file{threads/thread.c} implements several public functions for thread
333 support.  Let's take a look at the most useful:
334
335 @deftypefun void thread_init (void)
336 Called by @func{main} to initialize the thread system.  Its main
337 purpose is to create a @struct{thread} for Pintos's initial thread.
338 This is possible because the Pintos loader sets up the initial
339 thread's stack at the end of a page.  Before @func{thread_init} runs,
340 @func{thread_current} will fail because the running thread's
341 @code{magic} value is incorrect.  Lots of functions call
342 @func{thread_current} directly or indirectly, including
343 @func{lock_acquire} for locking a lock, so @func{thread_init} is
344 called early in Pintos initialization.
345 @end deftypefun
346
347 @deftypefun void thread_start (void)
348 Called by @func{main} to start the scheduler.  Creates the idle
349 thread, that is, the thread that is scheduled when no other thread is
350 ready.  Then enables interrupts, which enables the scheduler because
351 processes are rescheduled on return from the timer interrupt, using
352 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
353 @end deftypefun
354
355 @deftypefun void thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
356 Creates and starts a new thread named @var{name} with the given
357 @var{priority}, returning the new thread's tid.  The thread executes
358 @var{func}, passing @var{aux} as the function's single argument.
359
360 @func{thread_create} works by allocating a page for the thread's
361 @struct{thread} and stack and initializing its members, then setting
362 up a set of fake stack frames for it (we'll talk more about this
363 later).  The thread was initialized in the blocked state, so the final
364 action before returning is to unblock it, allowing the new thread to
365 be scheduled.
366 @end deftypefun
367
368 @deftypefun void thread_block (void)
369 Transitions the running thread from the running state to the blocked
370 state.  This thread will not run again until @func{thread_unblock} is
371 called on it, so you'd better have some way arranged for that to
372 happen.
373 @end deftypefun
374
375 @deftypefun void thread_unblock (struct thread *@var{thread})
376 Transitions @var{thread}, which must be in the blocked state, to the
377 ready state, allowing it to continue to run.  This is called when the
378 event that the thread is waiting for happens, such as the lock that
379 the thread is waiting on becoming available.
380 @end deftypefun
381
382 @deftypefun struct thread *thread_current (void)
383 Returns the running thread.
384 @end deftypefun
385
386 @deftypefun void thread_exit (void) NO_RETURN
387 Causes the current thread to exit.  Never returns (hence
388 @code{NO_RETURN}: @pxref{UNUSED NO_RETURN NO_INLINE PRINTF_FORMAT}).
389 @end deftypefun
390
391 @deftypefun void thread_yield (void)
392 Yields the CPU to the scheduler, which picks a new thread to run.  The
393 new thread might be the current thread, so you can't depend on this
394 function to keep this thread from running for any particular length of
395 time.
396 @end deftypefun
397
398 @node Thread Switching
399 @subsection Thread Switching
400
401 @func{schedule} is the function responsible for switching threads.  It
402 is internal to @file{threads/thread.c} and called only by the three
403 public thread functions that need to switch threads:
404 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
405 Before these functions call @func{schedule}, they all disable
406 interrupts (or ensure that they are already disabled) and then change
407 the running thread's state to something other than running.
408
409 The actual @func{schedule} implementation is simple.  It records the
410 current thread in local variable @var{cur}, determines the next thread
411 to run as local variable @var{next} (by calling
412 @func{next_thread_to_run}, and then calls @func{switch_threads} to do
413 the actual thread switch.  The thread we switched to was also running
414 inside @func{switch_threads}, as are all the threads not currently
415 running in Pintos, so the new thread now returns out of
416 @func{switch_threads}, returning the previously running thread.
417
418 @func{switch_threads} is an assembly language routine in
419 @file{threads/switch.S}.  It saves registers on the stack, stores the
420 CPU's current stack pointer into the current @struct{thread}'s @code{stack}
421 member, restores the new thread's @code{stack} into the CPU's stack
422 pointer, restores registers from the stack, and returns.
423
424 The rest of the scheduler is implemented as @func{schedule_tail}.  It
425 marks the new thread as running.  If the thread we just switched from
426 is in the dying state, then it also frees the page that contained the
427 dying thread's @struct{thread} and stack, which couldn't be freed
428 before the thread switch because the switch needed to use it.
429
430 Running a thread for the first time is a special case.  When
431 @func{thread_create} creates a new thread, it goes through a fair
432 amount of trouble to get it started properly.  In particular, a new
433 thread hasn't started running yet, so there's no way for it to be
434 running inside @func{switch_threads} as the scheduler expects.  To
435 solve the problem, @func{thread_create} creates some fake stack frames
436 in the new thread's stack:
437
438 @itemize @bullet
439 @item
440 The topmost fake stack frame is for @func{switch_threads}, represented
441 by @struct{switch_threads_frame}.  The important part of this frame is
442 its @code{eip} member, the return address.  We point @code{eip} to
443 @func{switch_entry}.
444
445 @item
446 The next fake stack frame is for @func{switch_entry}, an assembly
447 language routine in @file{threads/switch.S} that adjusts the stack
448 pointer,@footnote{This is because @func{switch_threads} takes
449 arguments on the stack and the 80@var{x}86 SVR4 calling convention
450 requires the caller, not the called function, to remove them when the
451 call is complete.  See @bibref{SysV-i386} chapter 3 for details.}
452 calls @func{schedule_tail} (this special case is why
453 @func{schedule_tail} is separate from @func{schedule}), and returns.
454 We fill in its stack frame so that it returns into
455 @func{kernel_thread}, a function in @file{threads/thread.c}.
456
457 @item
458 The final stack frame is for @func{kernel_thread}, which enables
459 interrupts and calls the thread's function (the function passed to
460 @func{thread_create}).  If the thread's function returns, it calls
461 @func{thread_exit} to terminate the thread.
462 @end itemize
463
464 @node Synchronization
465 @subsection Synchronization
466
467 Situations often arise in threaded programs in which threads want to
468 share resources.  If resource sharing is not handled in a careful,
469 controlled fashion, then threads can end up making a big mess.
470 This is especially the case in operating system kernels, where
471 faulty sharing can crash the entire machine.  Pintos provides several
472 synchronization primitives to help out.
473
474 @menu
475 * Disabling Interrupts::        
476 * Semaphores::                  
477 * Locks::                       
478 * Condition Variables::         
479 @end menu
480
481 @node Disabling Interrupts
482 @subsubsection Disabling Interrupts
483
484 The crudest way to do synchronization is to disable interrupts, that
485 is, to temporarily prevent the CPU from responding to interrupts.  If
486 interrupts are off, no other thread will preempt the running thread,
487 because thread preemption is driven by the timer interrupt.  If
488 interrupts are on, as they normally are, then the running thread may
489 be preempted by another at any time, whether between two C statements
490 or even within the execution of one.
491
492 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
493 is, kernel threads can be preempted at any time.  Traditional Unix
494 systems are ``nonpreemptible,'' that is, kernel threads can only be
495 preempted at points where they explicitly call into the scheduler.
496 User programs can be preempted at any time in both models.  As you
497 might imagine, preemptible kernels require more use of
498 synchronization.
499
500 You should have little need to set the interrupt state directly.  Most
501 of the time you should use the other synchronization primitives
502 described in the following sections.
503
504 Types and functions for disabling and enabling interrupts are in
505 @file{threads/interrupt.h}.
506
507 @deftp Type {enum intr_level}
508 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
509 disabled or enabled, respectively.
510 @end deftp
511
512 @deftypefun {enum intr_level} intr_get_level (void)
513 Returns the current interrupt state.
514 @end deftypefun
515
516 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
517 Turns interrupts on or off according to @var{level} and returns the
518 previous interrupt state.
519 @end deftypefun
520
521 @deftypefun {enum intr_level} intr_enable (void)
522 Turns interrupts on and returns the previous interrupt state.
523 @end deftypefun
524
525 @deftypefun {enum intr_level} intr_disable (void)
526 Turns interrupts off and returns the previous interrupt state.
527 @end deftypefun
528
529 @node Semaphores
530 @subsubsection Semaphores
531
532 A semaphore is a nonnegative integer along with two atomic operators
533 for manipulating it, which are:
534
535 @itemize @bullet
536 @item
537 ``Down'' or ``P'': wait for the value to become positive, then
538 decrement it.
539
540 @item
541 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
542 if any).
543 @end itemize
544
545 A semaphore initialized to 1 is typically used for controlling access
546 to a resource.  Before a block of code starts using the resource, it
547 ``downs'' the semaphore, then after it is done with the resource it
548 ``ups'' the resource.  In such a case a lock, described below, may be
549 more appropriate.
550
551 A semaphore initialized to 0 can be useful for waiting for an event
552 that will happen exactly once.  For example, suppose thread @var{A}
553 starts another thread @var{B} and wants to wait for @var{B} to signal
554 that some activity is complete.  @var{A} can create a semaphore
555 initialized to 0, pass it to @var{B}, and then ``down'' the semaphore.
556 When @var{B} finishes its activity, it ``ups'' the semaphore.
557
558 Pintos declared its semaphore type and operations on them in
559 @file{threads/synch.h}.
560
561 @deftp {Type} {struct semaphore}
562 Represents a semaphore.
563 @end deftp
564
565 @deftypefun void sema_init (struct semaphore *sema, unsigned value, const char *name)
566 Initializes @var{sema} as a new semaphore with the given initial
567 @var{value}.  Gives @var{sema} the specified @var{name} for use in
568 debugging.
569 @end deftypefun
570
571 @deftypefun void sema_down (struct semaphore *@var{sema})
572 Executes the ``down'' or ``P'' operation on the semaphore, waiting for
573 its value to become positive and then decrementing it by one.
574 @end deftypefun
575
576 @deftypefun void sema_up (struct semaphore *@var{sema})
577 Increments @var{sema}'s value.  If any threads are waiting on
578 @var{sema}, wakes one of them up.
579 @end deftypefun
580
581 Semaphores are internally built out of interrupt disabling
582 (@pxref{Disabling Interrupts}), thread blocking and unblocking
583 (@func{thread_block} and @func{thread_unblock}).  Semaphores maintain
584 a doubly linked list of waiting threads using the linked list
585 implementation in @file{lib/kernel/list.c}.
586
587 @node Locks
588 @subsubsection Locks
589
590 A lock is a specialization of a semaphore (@pxref{Semaphores}) with an
591 initial value of 1.  The difference between a lock and such a
592 semaphore is twofold.  First, a semaphore can have a value greater
593 than 1, but a lock can only be owned by a single thread at a time.
594 Second, a semaphore does not have an owner, meaning that one thread
595 can ``down'' the semaphore and then another one ``up'' it, but with a
596 lock the same thread must both acquire and release it.  When these
597 restrictions prove onerous, it's a good sign that a semaphore should
598 be used, instead of a lock.
599
600 Locks in Pintos are not ``recursive,'' that is, it is an error for the
601 thread currently holding a lock to try to acquire that lock.
602
603 Lock types and functions are declared in @file{threads/synch.h}.
604
605 @deftp {Type} {struct lock}
606 Represents a lock.
607 @end deftp
608
609 @deftypefun void lock_init (struct lock *@var{lock}, const char *@var{name})
610 Initializes @var{lock} as a new lock and gives it the specified
611 @var{name} for use in debugging.
612 @end deftypefun
613
614 @deftypefun void lock_acquire (struct lock *@var{lock})
615 Acquires @var{lock} for use by the current thread, first waiting for
616 any current owner to release it if necessary.
617 @end deftypefun
618
619 @deftypefun void lock_release (struct lock *@var{lock})
620 Releases @var{lock}, which the current thread must own.
621 @end deftypefun
622
623 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
624 Returns true if the running thread owns @var{lock},
625 false otherwise.
626 @end deftypefun
627
628 @node Condition Variables
629 @subsubsection Condition Variables
630
631 A condition variable allows one piece of code to signal a condition
632 and cooperating code to receive the signal and act upon it.  Each
633 condition variable is associated with a lock.  A given condition
634 variable is associated with only a single lock, but one lock may be
635 associated with any number of condition variables.  A lock along with
636 all of its condition variables is known as a ``monitor.''
637
638 A thread that owns the monitor lock is said to be ``in the monitor.''
639 The thread in the monitor has control over all the data protected with
640 the lock.  It may freely examine or modify this data.  If it discovers
641 that it needs to wait for some condition to become true, then it
642 ``waits'' on the associated condition, which releases the lock and
643 waits for the condition to be signaled.  If it, on the other hand, has
644 caused one of these conditions to become true, it ``signals'' the
645 condition to wake up one waiter, or ``broadcasts'' the condition to
646 wake all of them.
647
648 The classical example of a monitor is handling a buffer into which one
649 ``producer'' thread writes characters and out of which a second
650 ``consumer'' thread reads characters.  To implement this case we need,
651 besides the monitor lock, two condition variables which we will call
652 @var{not_full} and @var{not_empty}:
653
654 @example
655 char buf[BUF_SIZE];     /* @r{Buffer.} */
656 size_t n = 0;           /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
657 size_t head = 0;        /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
658 size_t tail = 0;        /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
659 struct lock lock;       /* @r{Monitor lock.} */
660 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
661 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
662
663 @dots{}@r{initialize the locks and condition variables}@dots{}
664
665 void put (char ch) @{
666   lock_acquire (&lock);
667   while (n == BUF_SIZE)         /* @r{Can't add to @var{buf} as long as it's full.} */
668     cond_wait (&not_full);
669   buf[head++ % BUF_SIZE] = ch;  /* @r{Add @var{ch} to @var{buf}.} */
670   n++;
671   cond_signal (&not_empty);     /* @r{@var{buf} can't be empty anymore.} */
672   lock_release (&lock);
673 @}
674
675 char get (void) @{
676   char ch;
677   lock_acquire (&lock);
678   while (n == 0)                /* @r{Can't read from @var{buf} as long as it's empty.} */
679     cond_wait (&not_empty);
680   ch = buf[tail++ % BUF_SIZE];  /* @r{Get @var{ch} from @var{buf}.} */
681   n--;
682   cond_signal (&not_full);      /* @r{@var{buf} can't be full anymore.} */
683   lock_release (&lock);
684 @}
685 @end example
686
687 As the code above illustrates, Pintos monitors are ``Mesa'' style, not
688 ``Hoare'' style, that is, sending and receiving a signal are not an
689 atomic operation.  Thus, typically the caller must recheck the
690 condition after the wait completes and, if necessary, wait again.
691
692 Condition variable types and functions are declared in
693 @file{threads/synch.h}.
694
695 @deftp {Type} {struct condition}
696 Represents a condition variable.
697 @end deftp
698
699 @deftypefun void cond_init (struct condition *@var{cond}, const char *@var{name})
700 Initializes @var{cond} as a new condition variable and gives it the
701 specified @var{name} for use in debugging.
702 @end deftypefun
703
704 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{name})
705 Atomically releases @var{lock} (the monitor lock) and waits for
706 @var{cond} to be signaled by some other piece of code.  After
707 @var{cond} is signaled, @var{lock} is reacquired before returning.
708 @var{lock} must be held before calling this function.
709 @end deftypefun
710
711 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
712 If any threads are waiting on @var{cond} (protected by monitor lock
713 @var{lock}), then this function signals one of them to wake up from
714 its wait.  @var{lock} must be held before calling this function.
715 @end deftypefun
716
717 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
718 Wakes up all threads, if any, waiting on @var{cond} (protected by
719 monitor lock @var{lock}).  @var{lock} must be held before calling this
720 function.
721 @end deftypefun
722
723 @node Interrupt Handling
724 @subsection Interrupt Handling
725
726 An @dfn{interrupt} notifies the CPU of some event.  Much of the work
727 of an operating system relates to interrupts in one way or another.
728 For our purposes, we classify interrupts into two broad categories:
729
730 @itemize @bullet
731 @item
732 @dfn{External interrupts}, that is, interrupts originating outside the
733 CPU.  These interrupts come from hardware devices such as the system
734 timer, keyboard, serial ports, and disks.  External interrupts are
735 @dfn{asynchronous}, meaning that they don't occur in a fashion
736 synchronized with anything going on in the CPU.  External interrupts
737 are what @func{intr_disable} and related functions can arrange to
738 temporarily ignore (@pxref{Disabling Interrupts}).
739
740 @item
741 @dfn{Internal interrupts}, that is, interrupts caused by something
742 executing on the CPU.  These interrupts are caused by something
743 unusual happening during instruction execution: accessing invalid
744 memory (a @dfn{page fault}), executing invalid instructions, and
745 various other disallowed activities.  Because they are caused by CPU
746 instructions, internal interrupts are @dfn{synchronous} or
747 synchronized with CPU instructions.  @func{intr_disable} does not
748 disable internal interrupts.
749 @end itemize
750
751 Because the CPU treats all interrupts largely the same way, regardless
752 of source, Pintos uses the same infrastructure for both internal and
753 external interrupts, up to a point.  The next section describes this
754 common infrastructure.  But external and internal interrupts are
755 actually quite different, so we also follow up that section with one
756 specific to each category.
757
758 If you haven't already read chapter 3 in @bibref{IA32-v1}, it is
759 recommended that you do so now.  You might also want to skim chapter 5
760 in @bibref{IA32-v3}.
761
762 @menu
763 * Interrupt Infrastructure::    
764 * Internal Interrupt Handling::  
765 * External Interrupt Handling::  
766 @end menu
767
768 @node Interrupt Infrastructure
769 @subsubsection Interrupt Infrastructure
770
771 When an interrupt occurs while the kernel is running, the CPU saves
772 its most essential state on the stack and jumps to an interrupt
773 handler routine.  The 80@var{x}86 architecture allows for 256 possible
774 interrupts, each of which can have its own handler. The handler for
775 each interrupt is defined in an array called the @dfn{interrupt
776 descriptor table} or IDT.
777
778 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
779 IDT so that each entry points to a unique entry point in
780 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
781 @var{NN} is the interrupt number in
782 hexadecimal.@footnote{@file{threads/intr-stubs.S} is so repetitive
783 that it is actually generated by a Perl script,
784 @file{threads/intr-stubs.pl}.  Thus, you will actually find
785 @file{threads/intr-stubs.S} in your @file{threads/build/threads}
786 directory, not in plain @file{threads}.}  Because the CPU doesn't give
787 us any other way to find out the interrupt number, this entry point
788 pushes the interrupt number on the stack.  Then it jumps to
789 @func{intr_entry}, which pushes all the registers that the processor
790 didn't save for us, and then calls @func{intr_handler}, which
791 brings us back into C in @file{threads/interrupt.c}.
792
793 The main job of @func{intr_handler} is to call any function that has
794 been registered for handling the particular interrupt.  (If there's no
795 function registered, it dumps some information to the console and
796 panics the kernel.)  It does some extra processing for external
797 interrupts that we'll discuss later.
798
799 When @func{intr_handler} returns, the assembly code in
800 @file{threads/intr-stubs.S} restores all the CPU registers saved
801 earlier and directs the CPU to return from the interrupt.
802
803 A few types and functions apply to both internal and external
804 interrupts.
805
806 @deftypefun void intr_register (uint8_t @var{vec}, int @var{dpl}, enum intr_level @var{level}, intr_handler_func *@var{func}, const char *@var{name})
807 Registers @var{func} to be called when the interrupt numbered
808 @var{vec} is triggered.  Names the interrupt @var{name} for debugging
809 purposes.
810
811 If @var{level} is @code{INTR_OFF} then handling of further interrupts
812 will be disabled while the interrupt is being processed.  If @var{vec}
813 denotes an external interrupt, then @var{level} must be
814 @code{INTR_OFF}.  Otherwise, interrupts should normally be turned on
815 during the handling of an internal interrupt.
816
817 For internal interrupts, @var{dpl} determines how the interrupt can be
818 invoked.  If @var{dpl} is 0, then the interrupt can be invoked only by
819 kernel threads.  Otherwise @var{dpl} should be 3, which allows user
820 processes to invoke the interrupt as well (this is useful only
821 starting with project 2).  @var{dpl} has no effect on external
822 interrupts
823 @end deftypefun
824
825 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
826 This is the type of an interrupt handler function.  Its @var{frame}
827 argument (see below) allows it to determine the cause of the interrupt
828 and the state of the thread that was interrupted.
829 @end deftp
830
831 @deftp {Type} {struct intr_frame}
832 The stack frame of an interrupt handler.  Its most interesting members
833 are as follows:
834 @table @code
835 @item uint32_t edi;
836 @item uint32_t esi;
837 @item uint32_t ebp;
838 @item uint32_t esp_dummy;
839 @item uint32_t ebx;
840 @item uint32_t edx;
841 @item uint32_t ecx;
842 @item uint32_t eax;
843 @item uint16_t es;
844 @item uint16_t ds;
845 Register values in the interrupted thread saved by @func{intr_entry}.
846 The @code{esp_dummy} value isn't actually used (refer to the
847 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
848
849 @item uint32_t vec_no;
850 The interrupt vector number, ranging from 0 to 255.
851
852 @item uint32_t error_code;
853 The ``error code'' pushed on the stack by the CPU for some internal
854 interrupts.
855
856 @item void (*eip) (void);
857 The address of the next instruction to be executed by the interrupted
858 thread. 
859
860 @item void *esp;
861 The interrupted thread's stack pointer.
862 @end table
863 @end deftp
864
865 @deftypefun {const char *} intr_name (uint8_t @var{vec})
866 Returns the registered name of the interrupt numbered @var{vec}, or
867 @code{"unknown"} if the interrupt's name is not known.
868 @end deftypefun
869
870 @node Internal Interrupt Handling
871 @subsubsection Internal Interrupt Handling
872
873 When an internal interrupt occurs, it is because the running kernel
874 thread (or, starting from project 2, the running user process) has
875 caused it.  Thus, because it is related to a thread (or process), an
876 internal interrupt is said to happen in a ``process context.''
877
878 In an internal interrupt, it can make sense to examine the
879 @struct{intr_frame} passed to the interrupt handler.  In cases where
880 the interrupted thread intentionally caused the interrupt, it can even
881 make sense to modify it.  When the interrupt returns, modified members
882 in @struct{intr_frame} become changes to the thread's registers.
883 We'll use this in project 2 to return values from system call
884 handlers.
885
886 There are no special restrictions on what an internal interrupt
887 handler can or can't do.  Generally they should run with interrupts
888 enabled, just like other code, and so they can be preempted by other
889 kernel threads.  Thus, they do need to synchronize with other threads
890 on shared data and other resources (@pxref{Synchronization}).
891
892 @node External Interrupt Handling
893 @subsubsection External Interrupt Handling
894
895 Whereas an internal interrupt runs in the context of the thread that
896 caused it, external interrupts do not have any predictable context.
897 They are asynchronous, so it can be invoked at any time that
898 interrupts have not been enabled.  We say that an external interrupt
899 runs in an ``interrupt context.''
900
901 In an external interrupt, the @struct{intr_frame} passed to the
902 handler is not very meaningful.  It describes the state of the thread
903 or process that was interrupted, but there is no way to predict which
904 one that is.  It is possible, though rarely useful, to examine it, but
905 modifying it is a recipe for disaster.
906
907 The activities of an external interrupt handler are severely
908 restricted.  First, only one external interrupt may be processed at a
909 time, that is, nested external interrupt handling is not supported.
910 This means that external interrupts must be processed with interrupts
911 disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
912 enabled at any point during their execution.
913
914 Second, an interrupt handler must not call any function that can
915 sleep, which includes @func{thread_yield}, @func{lock_acquire}, and
916 many others.  This is because external interrupts use space on the
917 stack of the kernel thread that was running at the time the interrupt
918 occurred.  If the interrupt handler tried to sleep and that thread
919 resumed, then the two uses of the single stack would interfere, which
920 cannot be allowed.
921
922 Because an external interrupt runs with interrupts disabled, it
923 effectively monopolizes the machine and delays all other activities.
924 Therefore, external interrupt handlers should complete as quickly as
925 they can.  Any activities that require much CPU time should instead
926 run in a kernel thread, possibly a thread whose activity is triggered
927 by the interrupt using some synchronization primitive.
928
929 External interrupts are also special because they are controlled by a
930 device external to the CPU called a @dfn{programmable interrupt
931 controller} or @dfn{PIC} for short.  When @func{intr_init} sets up the
932 CPU's IDT, it also initializes the PIC for interrupt handling.  The
933 PIC also has to be ``acknowledged'' at the end of processing for each
934 external interrupt.  @func{intr_handler} takes care of that by calling
935 @func{pic_end_of_interrupt}, which sends the proper signals to the
936 PIC.
937
938 The following additional interrupts functions are related to external
939 interrupts.
940
941 @deftypefun bool intr_context (void)
942 Returns true if we are running in an interrupt context and false
943 otherwise.  Mainly used at the beginning of functions that might sleep
944 or that otherwise should not be, in this form:
945 @example
946 ASSERT (!intr_context ());
947 @end example
948 @end deftypefun
949
950 @deftypefun intr_yield_on_return (void)
951 When called in an interrupt context, causes @func{thread_yield} to be
952 called just before the interrupt returns.  This is used, for example,
953 in the timer interrupt handler to cause a new thread to be scheduled
954 on every timer tick.
955 @end deftypefun
956
957 @node Memory Allocation
958 @subsection Memory Allocation
959
960 Pintos contains two memory allocators, one that allocates memory in
961 units of a page, and one that can allocate blocks of any size.
962
963 @menu
964 * Page Allocation::             
965 * Block Allocator::             
966 @end menu
967
968 @node Page Allocation
969 @subsubsection Page Allocation
970
971 The page allocator declared in @file{threads/palloc.h} allocates
972 memory in units of a page.  It is most often used to allocate memory
973 one page at a time, but it can also allocate multiple contiguous pages
974 at once.
975
976 The page allocator divides the memory it allocates into two pools,
977 called the kernel and user pools.  By default, each pool gets half of
978 system memory, but this can be changed with a kernel command line
979 option (@pxref{Why PAL_USER?}).  An allocation request draws from one
980 pool or the other.  If one pool becomes empty, the other may still
981 have free pages.  The user pool should be used for allocating memory
982 for user processes and the kernel pool for all other allocations.
983 This will only become important starting with project 3.  Until then,
984 all allocations should be made from the kernel pool.
985
986 Each pools is managed with a bitmap of used pages, one bit per page in
987 the pool.  An allocation request for @var{n} pages scans the bitmap,
988 starting from the beginning, for @var{n} consecutive bits set to
989 false, indicating that those pages are free, and then sets those bits
990 to true to mark them as now used.  This is a ``first fit'' allocation
991 strategy.
992
993 The page allocator is subject to fragmentation.  That is, it may not
994 be possible to allocate @var{n} contiguous pages even though @var{n}
995 or more pages are free, because the free pages are separated by used
996 pages.  In fact, in pathological cases it may be impossible to
997 allocate 2 contiguous pages even though @var{n} / 2 pages are free!
998 However, single-page requests can't fail due to fragmentation.  Thus,
999 it is best to limit the need to allocate more than one contiguous page
1000 as much as possible.
1001
1002 The interesting page allocator types and functions are described
1003 below.
1004
1005 @deftp {Type} {enum palloc_flags}
1006 A set of flags that describe how to allocate pages.  These flags may
1007 be combined in any combination:
1008
1009 @table @code
1010 @item PAL_ASSERT
1011 If the pages cannot be allocated, panic the kernel.  This is only
1012 appropriate during kernel initialization, because user processes
1013 should never be permitted to panic the kernel.
1014
1015 @item PAL_ZERO
1016 Clear the pages to all zeros before returning them.  If not set,
1017 newly allocated pages' contents are unpredictable.
1018
1019 @item PAL_USER
1020 Obtain the pages from the user pool.  If not set, pages are allocated
1021 from the kernel pool.
1022 @end table
1023 @end deftp
1024
1025 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1026 Obtains a single free page, allocating it in the manner specified by
1027 @var{flags}, and returns it.  Returns a null pointer if no pages are
1028 free.
1029 @end deftypefun
1030
1031 @deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1032 Obtains @var{page_cnt} contiguous free pages, allocating them in the
1033 manner specified by @var{flags}, and returns them.  Returns a null
1034 pointer if no pages are free.
1035 @end deftypefun
1036
1037 @deftypefun void palloc_free_page (void *@var{page})
1038 Frees @var{page}, which must have been obtained using
1039 @func{palloc_get_page} or @func{palloc_get_multiple}.
1040 @end deftypefun
1041
1042 @deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1043 Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
1044 All of the pages must have been obtained using @func{palloc_get_page}
1045 or @func{palloc_get_multiple}.
1046 @end deftypefun
1047
1048 @node Block Allocator
1049 @subsubsection Block Allocator
1050
1051 The block allocator, declared in @file{threads/malloc.h}, can allocate
1052 blocks of any size.  It is layered on top of the page allocator
1053 described in the previous section.  Blocks returned by the block
1054 allocator are obtained from the kernel pool.
1055
1056 The block allocator uses two different strategies for allocating
1057 memory.  The first of these applies to blocks no larger than 1 kB (one
1058 fourth of the the page size).  These allocations are rounded up to the
1059 nearest power of 2, or 16 bytes, whichever is larger.  Then they are
1060 grouped into a page used only for allocations of that power of 2
1061 size.
1062
1063 A different strategy applies to allocating blocks larger than 1 kB.
1064 These allocations (plus a small amount of overhead) are rounded up to
1065 the nearest page in size, and then the block allocator requests that
1066 number of contiguous pages from the page allocator.  
1067
1068 In either case, the difference between the allocation requested size
1069 and the actual block size is wasted.  A real operating system would
1070 carefully tune its allocator to minimize this waste, but this is
1071 unimportant in an instructional system like Pintos.
1072
1073 As long as a page can be obtained from the page allocator, small
1074 allocations always succeed.  Most small allocations will not require a
1075 new page from the page allocator at all.  However, large allocations
1076 always require calling into the page allocator, and any allocation
1077 that needs more than one contiguous page can fail due to fragmentation,
1078 as already discussed in the previous section.  Thus, you should
1079 minimize the number of large allocations in your code, especially
1080 those over approximately 4 kB each.
1081
1082 The interface to the block allocator is through the standard C library
1083 functions @func{malloc}, @func{calloc}, and @func{free}.