1 @node Pintos Tour, Project 1--Threads, Introduction, Top
2 @chapter A Tour Through Pintos
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
9 (Actually, the tour is currently incomplete. It fully covers only the
12 We recommend using ``tags'' to follow along with references to function
13 and variable names (@pxref{Tags}).
18 * User Programs Tour::
19 * Virtual Memory Tour::
26 This section covers the Pintos loader and basic kernel
31 * Kernel Initialization::
35 @subsection The Loader
37 The first part of Pintos that runs is the loader, in
38 @file{threads/loader.S}. The PC BIOS loads the loader into memory.
39 The loader, in turn, is responsible for initializing the CPU, loading
40 the rest of Pintos into memory, and then jumping to its start. It's
41 not important to understand exactly what the loader does, but if
42 you're interested, read on. You should probably read along with the
43 loader's source. You should also understand the basics of the
44 80@var{x}86 architecture as described by chapter 3, ``Basic Execution
45 Environment,'' of @bibref{IA32-v1}.
47 Because the PC BIOS loads the loader, the loader has to play by the
48 BIOS's rules. In particular, the BIOS only loads 512 bytes (one disk
49 sector) into memory. This is a severe restriction and it means that,
50 practically speaking, the loader has to be written in assembly
53 Pintos' loader first initializes the CPU. The first important part of
54 this is to enable the A20 line, that is, the CPU's address line
55 numbered 20. For historical reasons, PCs start out with this address
56 line fixed at 0, which means that attempts to access memory beyond the
57 first 1 MB (2 raised to the 20th power) will fail. Pintos wants to
58 access more memory than this, so we have to enable it.
60 Next, the loader asks the BIOS for the PC's memory size. Again for
61 historical reasons, the function that we call in the BIOS to do this
62 can only detect up to 64 MB of RAM, so that's the practical limit that
63 Pintos can support. The memory size is stashed away in a location in
64 the loader that the kernel can read after it boots.
66 Third, the loader creates a basic page table. This page table maps
67 the 64 MB at the base of virtual memory (starting at virtual address
68 0) directly to the identical physical addresses. It also maps the
69 same physical memory starting at virtual address
70 @code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB). The
71 Pintos kernel only wants the latter mapping, but there's a
72 chicken-and-egg problem if we don't include the former: our current
73 virtual address is roughly @t{0x7c00}, the location where the BIOS
74 loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
75 page table, but if we turn on the page table without jumping there,
76 then we've just pulled the rug out from under ourselves.
78 After the page table is initialized, we load the CPU's control
79 registers to turn on protected mode and paging, and then we set up the
80 segment registers. We aren't equipped to handle interrupts in
81 protected mode yet, so we disable interrupts.
83 Finally it's time to load the kernel from disk. We use a simple but
84 inflexible method to do this: we program the IDE disk
85 controller directly. We assume that the kernel is stored starting
86 from the second sector of the first IDE disk (the first sector normally
87 contains the boot loader). We also assume that the BIOS has
88 already set up the IDE controller for us. We read
89 @code{KERNEL_LOAD_PAGES} pages of data (4 kB per page) from the disk directly
90 into virtual memory, starting @code{LOADER_KERN_BASE} bytes past
91 @code{LOADER_PHYS_BASE}, which by default means that we load the
92 kernel starting 1 MB into physical memory.
94 Then we jump to the start of the compiled kernel image. Using the
95 ``linker script'' in @file{threads/kernel.lds.S}, the kernel has
96 arranged that it begins with the assembly module
97 @file{threads/start.S}. This assembly module just calls
98 @func{main}, which never returns.
100 There's one more trick: the Pintos kernel command line
101 is stored in the boot loader. The @command{pintos} program actually
102 modifies the boot loader on disk each time it runs the kernel, putting
103 in whatever command line arguments the user supplies to the kernel,
104 and then the kernel at boot time reads those arguments out of the boot
105 loader in memory. This is something of a nasty hack, but it is simple
108 @node Kernel Initialization
109 @subsection Kernel Initialization
111 The kernel proper starts with the @func{main} function. The
112 @func{main} function is written in C, as will be most of the code we
113 encounter in Pintos from here on out.
115 When @func{main} starts, the system is in a pretty raw state. We're
116 in protected mode with paging enabled, but hardly anything else is
117 ready. Thus, the @func{main} function consists primarily of calls
118 into other Pintos modules' initialization functions.
119 These are usually named @func{@var{module}_init}, where
120 @var{module} is the module's name, @file{@var{module}.c} is the
121 module's source code, and @file{@var{module}.h} is the module's
124 First we initialize kernel RAM in @func{ram_init}. The first step
125 is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
126 segment that should be initialized to all zeros. In most C
127 implementations, whenever you
128 declare a variable outside a function without providing an
129 initializer, that variable goes into the BSS. Because it's all zeros, the
130 BSS isn't stored in the image that the loader brought into memory. We
131 just use @func{memset} to zero it out. The other task of
132 @func{ram_init} is to read out the machine's memory size from where
133 the loader stored it and put it into the @code{ram_pages} variable for
136 Next, @func{thread_init} initializes the thread system. We will defer
137 full discussion to our discussion of Pintos threads below. It is
138 called so early in initialization because the console, initialized
139 just afterward, tries to use locks, and locks in turn require there to be a
142 Then we initialize the console so that we can use @func{printf}.
143 @func{main} calls @func{vga_init}, which initializes the VGA text
144 display and clears the screen. It also calls @func{serial_init_poll}
145 to initialize the first serial port in ``polling mode,'' that is,
146 where the kernel busy-waits for the port to be ready for each
147 character to be output. (We use polling mode until we're ready to set
148 up interrupts later.) Finally we initialize the console device and
149 print a startup message to the console.
151 @func{main} calls @func{read_command_line} to break the kernel command
152 line into arguments, then @func{parse_options} to read any options at
153 the beginning of the command line. (Executing actions specified on the
154 command line happens later.)
156 The next block of functions we call initialize the kernel's memory
157 system. @func{palloc_init} sets up the kernel page allocator, which
158 doles out memory one or more pages at a time. @func{malloc_init} sets
159 up the allocator that handles odd-sized allocations.
160 @func{paging_init} sets up a page table for the kernel.
162 In projects 2 and later, @func{main} also calls @func{tss_init} and
163 @func{gdt_init}, but we'll talk about those later.
165 @func{main} calls @func{random_init} to initialize the kernel random
166 number generator. If the user specified @option{-rs} on the
167 @command{pintos} command line, @func{parse_options} has already done
168 this, but calling it a second time is harmless and has no effect.
170 We initialize the interrupt system in the next set of calls.
171 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
172 (IDT) to ready it for interrupt handling (@pxref{Interrupt
173 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
174 handling timer interrupts and keyboard interrupts, respectively. In
175 projects 2 and later, we also prepare to handle interrupts caused by
176 user programs using @func{exception_init} and @func{syscall_init}.
178 Now that interrupts are set up, we can start preemptively scheduling
179 threads with @func{thread_start}, which also enables interrupts.
180 With interrupts enabled, interrupt-driven serial port I/O becomes
182 @func{serial_init_queue} to switch to that mode. Finally,
183 @func{timer_calibrate} calibrates the timer for accurate short delays.
185 If the file system is compiled in, as it will starting in project 2, we
186 now initialize the disks with @func{disk_init}, then the
187 file system with @func{filesys_init}.
189 Boot is complete, so we print a message.
191 Function @func{run_actions} now parses and executes actions specified on
192 the kernel command line, such as @command{run} to run a test (in project
193 1) or a user program (in later projects).
195 Finally, if @option{-q} was specified on the kernel command line, we
196 call @func{power_off} to terminate the machine simulator. Otherwise,
197 @func{main} calls @func{thread_exit}, which allows any other running
198 threads to continue running.
201 @section Threads Project
206 * Interrupt Handling::
207 * Memory Allocation::
211 @subsection Thread Support
220 @subsubsection @code{struct thread}
222 The main Pintos data structure for threads is @struct{thread},
223 declared in @file{threads/thread.h}.
225 @deftp {Structure} {@struct{thread}}
226 Represents a thread or a user process. In the projects, you will have
227 to add your own members to @struct{thread}. You may also change or
228 delete the definitions of existing members.
230 Every @struct{thread} occupies the beginning of its own page of
231 memory. The rest of the page is used for the thread's stack, which
232 grows downward from the end of the page. It looks like this:
236 4 kB +---------------------------------+
250 +---------------------------------+
256 0 kB +---------------------------------+
260 This has two consequences. First, @struct{thread} must not be allowed
261 to grow too big. If it does, then there will not be enough room for the
262 kernel stack. The base @struct{thread} is only a few bytes in size. It
263 probably should stay well under 1 kB.
265 Second, kernel stacks must not be allowed to grow too large. If a stack
266 overflows, it will corrupt the thread state. Thus, kernel functions
267 should not allocate large structures or arrays as non-static local
268 variables. Use dynamic allocation with @func{malloc} or
269 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
272 @deftypecv {Member} {@struct{thread}} {tid_t} tid
273 The thread's thread identifier or @dfn{tid}. Every thread must have a
274 tid that is unique over the entire lifetime of the kernel. By
275 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
276 thread receives the numerically next higher tid, starting from 1 for
277 the initial process. You can change the type and the numbering scheme
281 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
282 The thread's state, one of the following:
284 @defvr {Thread State} @code{THREAD_RUNNING}
285 The thread is running. Exactly one thread is running at a given time.
286 @func{thread_current} returns the running thread.
289 @defvr {Thread State} @code{THREAD_READY}
290 The thread is ready to run, but it's not running right now. The
291 thread could be selected to run the next time the scheduler is
292 invoked. Ready threads are kept in a doubly linked list called
296 @defvr {Thread State} @code{THREAD_BLOCKED}
297 The thread is waiting for something, e.g.@: a lock to become
298 available, an interrupt to be invoked. The thread won't be scheduled
299 again until it transitions to the @code{THREAD_READY} state with a
300 call to @func{thread_unblock}.
303 @defvr {Thread State} @code{THREAD_DYING}
304 The thread will be destroyed by the scheduler after switching to the
309 @deftypecv {Member} {@struct{thread}} {char} name[16]
310 The thread's name as a string, or at least the first few characters of
314 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
315 Every thread has its own stack to keep track of its state. When the
316 thread is running, the CPU's stack pointer register tracks the top of
317 the stack and this member is unused. But when the CPU switches to
318 another thread, this member saves the thread's stack pointer. No
319 other members are needed to save the thread's registers, because the
320 other registers that must be saved are saved on the stack.
322 When an interrupt occurs, whether in the kernel or a user program, an
323 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
324 in a user program, the @struct{intr_frame} is always at the very top of
325 the page. @xref{Interrupt Handling}, for more information.
328 @deftypecv {Member} {@struct{thread}} {int} priority
329 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
330 (63). Lower numbers correspond to @emph{higher} priorities, so that
331 priority 0 is the highest priority and priority 63 is the lowest.
332 Pintos as provided ignores thread priorities, but you will implement
333 priority scheduling in project 1 (@pxref{Priority Scheduling}).
336 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
337 A ``list element'' used to put the thread into doubly linked lists,
338 either the list of threads ready to run or a list of threads waiting
339 on a semaphore. Take a look at @file{lib/kernel/list.h} for
340 information on how to use Pintos doubly linked lists.
343 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
344 Only present in project 2 and later.
347 @deftypecv {Member} {@struct{thread}} {unsigned} magic
348 Always set to @code{THREAD_MAGIC}, which is just a random 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 will normally change this value, triggering the assertion. For greatest
353 benefit, as you add members to @struct{thread}, leave @code{magic} as
357 @node Thread Functions
358 @subsubsection Thread Functions
360 @file{threads/thread.c} implements several public functions for thread
361 support. Let's take a look at the most useful:
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
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.
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}).
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.
391 @deftypefun void thread_print_stats (void)
392 Called during Pintos shutdown to print thread statistics.
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.
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 (more about this
403 later). The thread is initialized in the blocked state, so the final
404 action before returning is to unblock it, which allows the new thread to
408 @deftp {Type} {void thread_func (void *@var{aux})}
409 This is the type of a thread function. Its @var{aux} argument is the
410 value passed to @func{thread_create}.
413 @deftypefun void thread_block (void)
414 Transitions the running thread from the running state to the blocked
415 state. The thread will not run again until @func{thread_unblock} is
416 called on it, so you'd better have some way arranged for that to happen.
417 Because @func{thread_block} is so low-level, you should prefer to use
418 one of the synchronization primitives instead (@pxref{Synchronization}).
421 @deftypefun void thread_unblock (struct thread *@var{thread})
422 Transitions @var{thread}, which must be in the blocked state, to the
423 ready state, allowing it to resume running. This is called when the
424 event that the thread is waiting for occurs, e.g.@: when the lock that
425 the thread is waiting on becomes available.
428 @deftypefun {struct thread *} thread_current (void)
429 Returns the running thread.
432 @deftypefun {tid_t} thread_tid (void)
433 Returns the running thread's thread id. Equivalent to
434 @code{thread_current ()->tid}.
437 @deftypefun {const char *} thread_name (void)
438 Returns the running thread's name. Equivalent to @code{thread_current
442 @deftypefun void thread_exit (void) @code{NO_RETURN}
443 Causes the current thread to exit. Never returns, hence
444 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
447 @deftypefun void thread_yield (void)
448 Yields the CPU to the scheduler, which picks a new thread to run. The
449 new thread might be the current thread, so you can't depend on this
450 function to keep this thread from running for any particular length of
454 @deftypefun int thread_get_priority (void)
455 @deftypefunx void thread_set_priority (int @var{new_priority})
456 Skeleton to set and get thread priority. @xref{Priority Scheduling}.
459 @deftypefun int thread_get_nice (void)
460 @deftypefunx void thread_set_nice (int @var{new_nice})
461 @deftypefunx int thread_get_recent_cpu (void)
462 @deftypefunx int thread_get_load_avg (void)
463 Skeletons for the advanced scheduler. @xref{4.4BSD Scheduler}.
466 @node Thread Switching
467 @subsubsection Thread Switching
469 @func{schedule} is the function responsible for switching threads. It
470 is internal to @file{threads/thread.c} and called only by the three
471 public thread functions that need to switch threads:
472 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
473 Before any of these functions call @func{schedule}, they disable
474 interrupts (or ensure that they are already disabled) and then change
475 the running thread's state to something other than running.
477 @func{schedule} is simple but tricky. It records the
478 current thread in local variable @var{cur}, determines the next thread
479 to run as local variable @var{next} (by calling
480 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
481 the actual thread switch. The thread we switched to was also running
482 inside @func{switch_threads}, as are all the threads not currently
483 running, so the new thread now returns out of
484 @func{switch_threads}, returning the previously running thread.
486 @func{switch_threads} is an assembly language routine in
487 @file{threads/switch.S}. It saves registers on the stack, saves the
488 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
489 member, restores the new thread's @code{stack} into the CPU's stack
490 pointer, restores registers from the stack, and returns.
492 The rest of the scheduler is implemented as @func{schedule_tail}. It
493 marks the new thread as running. If the thread we just switched from
494 is in the dying state, then it also frees the page that contained the
495 dying thread's @struct{thread} and stack. These couldn't be freed
496 prior to the thread switch because the switch needed to use it.
498 Running a thread for the first time is a special case. When
499 @func{thread_create} creates a new thread, it goes through a fair
500 amount of trouble to get it started properly. In particular, a new
501 thread hasn't started running yet, so there's no way for it to be
502 running inside @func{switch_threads} as the scheduler expects. To
503 solve the problem, @func{thread_create} creates some fake stack frames
504 in the new thread's stack:
508 The topmost fake stack frame is for @func{switch_threads}, represented
509 by @struct{switch_threads_frame}. The important part of this frame is
510 its @code{eip} member, the return address. We point @code{eip} to
511 @func{switch_entry}, indicating it to be the function that called
515 The next fake stack frame is for @func{switch_entry}, an assembly
516 language routine in @file{threads/switch.S} that adjusts the stack
517 pointer,@footnote{This is because @func{switch_threads} takes
518 arguments on the stack and the 80@var{x}86 SVR4 calling convention
519 requires the caller, not the called function, to remove them when the
520 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
521 calls @func{schedule_tail} (this special case is why
522 @func{schedule_tail} is separate from @func{schedule}), and returns.
523 We fill in its stack frame so that it returns into
524 @func{kernel_thread}, a function in @file{threads/thread.c}.
527 The final stack frame is for @func{kernel_thread}, which enables
528 interrupts and calls the thread's function (the function passed to
529 @func{thread_create}). If the thread's function returns, it calls
530 @func{thread_exit} to terminate the thread.
533 @node Synchronization
534 @subsection Synchronization
536 If sharing of resources between threads is not handled in a careful,
537 controlled fashion, then the result is usually a big mess.
538 This is especially the case in operating system kernels, where
539 faulty sharing can crash the entire machine. Pintos provides several
540 synchronization primitives to help out.
543 * Disabling Interrupts::
546 * Condition Variables::
550 @node Disabling Interrupts
551 @subsubsection Disabling Interrupts
553 The crudest way to do synchronization is to disable interrupts, that
554 is, to temporarily prevent the CPU from responding to interrupts. If
555 interrupts are off, no other thread will preempt the running thread,
556 because thread preemption is driven by the timer interrupt. If
557 interrupts are on, as they normally are, then the running thread may
558 be preempted by another at any time, whether between two C statements
559 or even within the execution of one.
561 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
562 is, kernel threads can be preempted at any time. Traditional Unix
563 systems are ``nonpreemptible,'' that is, kernel threads can only be
564 preempted at points where they explicitly call into the scheduler.
565 (User programs can be preempted at any time in both models.) As you
566 might imagine, preemptible kernels require more explicit
569 You should have little need to set the interrupt state directly. Most
570 of the time you should use the other synchronization primitives
571 described in the following sections. The main reason to disable
572 interrupts is to synchronize kernel threads with external interrupt
573 handlers, which cannot sleep and thus cannot use most other forms of
574 synchronization (@pxref{External Interrupt Handling}).
576 Types and functions for disabling and enabling interrupts are in
577 @file{threads/interrupt.h}.
579 @deftp Type {enum intr_level}
580 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
581 disabled or enabled, respectively.
584 @deftypefun {enum intr_level} intr_get_level (void)
585 Returns the current interrupt state.
588 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
589 Turns interrupts on or off according to @var{level}. Returns the
590 previous interrupt state.
593 @deftypefun {enum intr_level} intr_enable (void)
594 Turns interrupts on. Returns the previous interrupt state.
597 @deftypefun {enum intr_level} intr_disable (void)
598 Turns interrupts off. Returns the previous interrupt state.
602 @subsubsection Semaphores
604 Pintos' semaphore type and operations are declared in
605 @file{threads/synch.h}.
607 @deftp {Type} {struct semaphore}
608 Represents a @dfn{semaphore}, a nonnegative integer together with two
609 operators that manipulate it atomically, which are:
613 ``Down'' or ``P'': wait for the value to become positive, then
617 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
621 A semaphore initialized to 0 may be used to wait for an event
622 that will happen exactly once. For example, suppose thread @var{A}
623 starts another thread @var{B} and wants to wait for @var{B} to signal
624 that some activity is complete. @var{A} can create a semaphore
625 initialized to 0, pass it to @var{B} as it starts it, and then
626 ``down'' the semaphore. When @var{B} finishes its activity, it
627 ``ups'' the semaphore. This works regardless of whether @var{A}
628 ``downs'' the semaphore or @var{B} ``ups'' it first.
630 A semaphore initialized to 1 is typically used for controlling access
631 to a resource. Before a block of code starts using the resource, it
632 ``downs'' the semaphore, then after it is done with the resource it
633 ``ups'' the resource. In such a case a lock, described below, may be
636 Semaphores can also be initialized to values larger than 1. These are
640 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
641 Initializes @var{sema} as a new semaphore with the given initial
645 @deftypefun void sema_down (struct semaphore *@var{sema})
646 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
647 its value to become positive and then decrementing it by one.
650 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
651 Tries to execute the ``down'' or ``P'' operation on @var{sema},
652 without waiting. Returns true if @var{sema} had a positive value
653 that was successfully decremented, or false if it was already
654 zero and thus could not be decremented. Calling this function in a
655 tight loop wastes CPU time (use @func{sema_down} instead, or find a
659 @deftypefun void sema_up (struct semaphore *@var{sema})
660 Executes the ``up'' or ``V'' operation on @var{sema},
661 incrementing its value. If any threads are waiting on
662 @var{sema}, wakes one of them up.
665 Semaphores are internally built out of disabling interrupt
666 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
667 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
668 a list of waiting threads, using the linked list
669 implementation in @file{lib/kernel/list.c}.
674 Lock types and functions are declared in @file{threads/synch.h}.
676 @deftp {Type} {struct lock}
677 Represents a @dfn{lock}, a specialized semaphore with an initial value
678 of 1 (@pxref{Semaphores}). The difference between a lock and such a
679 semaphore is twofold. First, a semaphore does not have an owner,
680 meaning that one thread can ``down'' the semaphore and then another one
681 ``up'' it, but a single thread must both acquire and release a lock.
682 Second, a semaphore can have a value greater than 1, but a lock can only
683 be owned by a single thread at a time. If these restrictions prove
684 onerous, it's a good sign that a semaphore should be used, instead of a
687 Locks in Pintos are not ``recursive,'' that is, it is an error for the
688 thread currently holding a lock to try to acquire that lock.
691 @deftypefun void lock_init (struct lock *@var{lock})
692 Initializes @var{lock} as a new lock.
695 @deftypefun void lock_acquire (struct lock *@var{lock})
696 Acquires @var{lock} for use by the current thread, first waiting for
697 any current owner to release it if necessary.
700 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
701 Tries to acquire @var{lock} for use by the current thread, without
702 waiting. Returns true if successful, false if the lock is already
703 owned. Calling this function in a tight loop is a bad idea because it
704 wastes CPU time (use @func{lock_acquire} instead).
707 @deftypefun void lock_release (struct lock *@var{lock})
708 Releases @var{lock}, which the current thread must own.
711 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
712 Returns true if the running thread owns @var{lock},
716 @node Condition Variables
717 @subsubsection Condition Variables
719 Condition variable types and functions are declared in
720 @file{threads/synch.h}.
722 @deftp {Type} {struct condition}
723 Represents a condition variable, which allows one piece of code to
725 and cooperating code to receive the signal and act upon it. Each
726 condition variable is associated with a lock. A given condition
727 variable is associated with only a single lock, but one lock may be
728 associated with any number of condition variables. A set of condition
729 variables taken together with their lock is called a ``monitor.''
731 A thread that owns the monitor lock is said to be ``in the monitor.''
732 The thread in the monitor has control over all the data protected by
733 the lock. It may freely examine or modify this data. If it discovers
734 that it needs to wait for some condition to become true, then it
735 ``waits'' on the associated condition, which releases the lock and
736 waits for the condition to be signaled. If, on the other hand, it has
737 caused one of these conditions to become true, it ``signals'' the
738 condition to wake up one waiter, or ``broadcasts'' the condition to
741 Pintos monitors are ``Mesa'' style, not
742 ``Hoare'' style. That is, sending and receiving a signal are not an
743 atomic operation. Thus, typically the caller must recheck the
744 condition after the wait completes and, if necessary, wait again.
747 @deftypefun void cond_init (struct condition *@var{cond})
748 Initializes @var{cond} as a new condition variable.
751 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
752 Atomically releases @var{lock} (the monitor lock) and waits for
753 @var{cond} to be signaled by some other piece of code. After
754 @var{cond} is signaled, reacquires @var{lock} before returning.
755 @var{lock} must be held before calling this function.
758 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
759 If any threads are waiting on @var{cond} (protected by monitor lock
760 @var{lock}), then this function wakes up one of them. If no threads are
761 waiting, returns without performing any action.
762 @var{lock} must be held before calling this function.
765 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
766 Wakes up all threads, if any, waiting on @var{cond} (protected by
767 monitor lock @var{lock}). @var{lock} must be held before calling this
771 @subsubheading Monitor Example
773 The classical example of a monitor is handling a buffer into which one
774 ``producer'' thread writes characters and out of which a second
775 ``consumer'' thread reads characters. To implement this case we need,
776 besides the monitor lock, two condition variables which we will call
777 @var{not_full} and @var{not_empty}:
780 char buf[BUF_SIZE]; /* @r{Buffer.} */
781 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
782 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
783 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
784 struct lock lock; /* @r{Monitor lock.} */
785 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
786 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
788 @dots{}@r{initialize the locks and condition variables}@dots{}
790 void put (char ch) @{
791 lock_acquire (&lock);
792 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
793 cond_wait (¬_full, &lock);
794 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
796 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
797 lock_release (&lock);
802 lock_acquire (&lock);
803 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
804 cond_wait (¬_empty, &lock);
805 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
807 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
808 lock_release (&lock);
812 @node Memory Barriers
813 @subsubsection Memory Barriers
815 Suppose we add a ``feature'' that, whenever a timer interrupt
816 occurs, the character in global variable @code{timer_put_char} is
817 printed on the console, but only if global Boolean variable
818 @code{timer_do_put} is true.
820 If interrupts are enabled, this code for setting up @samp{x} to be
821 printed is clearly incorrect, because the timer interrupt could intervene
822 between the two assignments:
825 timer_do_put = true; /* INCORRECT CODE */
826 timer_put_char = 'x';
829 It might not be as obvious that the following code is just as
833 timer_put_char = 'x'; /* INCORRECT CODE */
837 The reason this second example might be a problem is that the compiler
838 is, in general, free to reorder operations when it doesn't have a
839 visible reason to keep them in the same order. In this case, the
840 compiler doesn't know that the order of assignments is important, so its
841 optimization pass is permitted to exchange their order.
842 There's no telling whether it will actually do this, and it is possible
843 that passing the compiler different optimization flags or changing
844 compiler versions will produce different behavior.
846 The following is @emph{not} a solution, because locks neither prevent
847 interrupts nor prevent the compiler from reordering the code within the
848 region where the lock is held:
851 lock_acquire (&timer_lock); /* INCORRECT CODE */
852 timer_put_char = 'x';
854 lock_release (&timer_lock);
857 Fortunately, real solutions do exist. One possibility is to
858 disable interrupts around the assignments. This does not prevent
859 reordering, but it makes the assignments atomic as observed by the
860 interrupt handler. It also has the extra runtime cost of disabling and
861 re-enabling interrupts:
864 enum intr_level old_level = intr_disable ();
865 timer_put_char = 'x';
867 intr_set_level (old_level);
870 A second possibility is to mark the declarations of
871 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
872 keyword tells the compiler that the variables are externally observable
873 and allows it less latitude for optimization. However, the semantics of
874 @samp{volatile} are not well-defined, so it is not a good general
877 Usually, the best solution is to use a compiler feature called a
878 @dfn{memory barrier}, a special statement that prevents the compiler
879 from reordering memory operations across the barrier. In Pintos,
880 @file{threads/synch.h} defines the @code{barrier()} macro as a memory
881 barrier. Here's how we would use a memory barrier to fix this code:
884 timer_put_char = 'x';
889 The compiler also treats invocation of any function defined externally,
890 that is, in another source file, as a limited form of a memory barrier.
891 Specifically, the compiler assumes that any externally defined function
892 may access any statically or dynamically allocated data and any local
893 variable whose address is taken. This often means that explicit
894 barriers can be omitted, and, indeed, this is why the base Pintos code
895 does not need any barriers.
897 A function defined in the same source file, or in a header included by
898 the source file, cannot be relied upon as a memory barrier.
899 This applies even to invocation of a function before its
900 definition, because the compiler may read and parse the entire source
901 file before performing optimization.
903 @node Interrupt Handling
904 @subsection Interrupt Handling
906 An @dfn{interrupt} notifies the CPU of some event. Much of the work
907 of an operating system relates to interrupts in one way or another.
908 For our purposes, we classify interrupts into two broad categories:
912 @dfn{External interrupts}, that is, interrupts originating outside the
913 CPU. These interrupts come from hardware devices such as the system
914 timer, keyboard, serial ports, and disks. External interrupts are
915 @dfn{asynchronous}, meaning that their delivery is not
916 synchronized with normal CPU activities. External interrupts
917 are what @func{intr_disable} and related functions
918 postpone (@pxref{Disabling Interrupts}).
921 @dfn{Internal interrupts}, that is, interrupts caused by something
922 executing on the CPU. These interrupts are caused by something
923 unusual happening during instruction execution: accessing invalid
924 memory (a @dfn{page fault}), executing invalid instructions, and
925 various other disallowed activities. Because they are caused by CPU
926 instructions, internal interrupts are @dfn{synchronous} or
927 synchronized with CPU instructions. @func{intr_disable} does not
928 disable internal interrupts.
931 Because the CPU treats all interrupts largely the same way, regardless
932 of source, Pintos uses the same infrastructure for both internal and
933 external interrupts, to a point. The following section describes this
934 common infrastructure, and sections after that give the specifics of
935 external and internal interrupts.
937 If you haven't already read chapter 3, ``Basic Execution Environment,''
938 in @bibref{IA32-v1}, it is recommended that you do so now. You might
939 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
943 * Interrupt Infrastructure::
944 * Internal Interrupt Handling::
945 * External Interrupt Handling::
948 @node Interrupt Infrastructure
949 @subsubsection Interrupt Infrastructure
951 When an interrupt occurs while the kernel is running, the CPU saves
952 its most essential state on the stack and jumps to an interrupt
953 handler routine. The 80@var{x}86 architecture allows for 256 possible
954 interrupts, each of which can have its own handler. The handler for
955 each interrupt is defined in an array called the @dfn{interrupt
956 descriptor table} or IDT.
958 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
959 IDT so that each entry points to a unique entry point in
960 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
961 @var{NN} is the interrupt number in
962 hexadecimal. Because the CPU doesn't give
963 us any other way to find out the interrupt number, this entry point
964 pushes the interrupt number on the stack. Then it jumps to
965 @func{intr_entry}, which pushes all the registers that the processor
966 didn't already save for us, and then calls @func{intr_handler}, which
967 brings us back into C in @file{threads/interrupt.c}.
969 The main job of @func{intr_handler} is to call any function that has
970 been registered for handling the particular interrupt. (If no
971 function is registered, it dumps some information to the console and
972 panics.) It does some extra processing for external
973 interrupts that we'll discuss later.
975 When @func{intr_handler} returns, the assembly code in
976 @file{threads/intr-stubs.S} restores all the CPU registers saved
977 earlier and directs the CPU to return from the interrupt.
979 A few types and functions apply to both internal and external
982 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
983 This is how an interrupt handler function must be declared. Its @var{frame}
984 argument (see below) allows it to determine the cause of the interrupt
985 and the state of the thread that was interrupted.
988 @deftp {Type} {struct intr_frame}
989 The stack frame of an interrupt handler, as saved by CPU, the interrupt
990 stubs, and @func{intr_entry}. Its most interesting members are described
994 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
995 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
996 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
997 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
998 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
999 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1000 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1001 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1002 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1003 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1004 Register values in the interrupted thread saved by @func{intr_entry}.
1005 The @code{esp_dummy} value isn't actually used (refer to the
1006 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1009 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1010 The interrupt vector number, ranging from 0 to 255.
1013 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1014 The ``error code'' pushed on the stack by the CPU for some internal
1018 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1019 The address of the next instruction to be executed by the interrupted
1023 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1024 The interrupted thread's stack pointer.
1027 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1028 Returns the name of the interrupt numbered @var{vec}, or
1029 @code{"unknown"} if the interrupt has no registered name.
1032 @node Internal Interrupt Handling
1033 @subsubsection Internal Interrupt Handling
1035 When an internal interrupt occurs, it is because the running kernel
1036 thread (or, starting from project 2, the running user process) has
1037 caused it. Thus, because it is related to a thread (or process), an
1038 internal interrupt is said to happen in a ``process context.''
1040 In an internal interrupt, it can make sense to examine the
1041 @struct{intr_frame} passed to the interrupt handler, or even to modify
1042 it. When the interrupt returns, modified members
1043 in @struct{intr_frame} become changes to the thread's registers.
1044 We'll use this in project 2 to return values from system call
1047 There are no special restrictions on what an internal interrupt
1048 handler can or can't do. Generally they should run with interrupts
1049 enabled, just like other code, and so they can be preempted by other
1050 kernel threads. Thus, they do need to synchronize with other threads
1051 on shared data and other resources (@pxref{Synchronization}).
1053 @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})
1054 Registers @var{handler} to be called when internal interrupt numbered
1055 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1058 If @var{level} is @code{INTR_OFF} then handling of further interrupts
1059 will be disabled while the interrupt is being processed. Interrupts
1060 should normally be turned on during the handling of an internal
1063 @var{dpl} determines how the interrupt can be
1064 invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
1065 kernel threads. Otherwise @var{dpl} should be 3, which allows user
1066 processes to invoke the interrupt as well (this is useful only
1067 starting with project 2).
1070 @node External Interrupt Handling
1071 @subsubsection External Interrupt Handling
1073 Whereas an internal interrupt runs in the context of the thread that
1074 caused it, external interrupts do not have any predictable context.
1075 They are asynchronous, so they can be invoked at any time that
1076 interrupts have not been disabled. We say that an external interrupt
1077 runs in an ``interrupt context.''
1079 In an external interrupt, the @struct{intr_frame} passed to the
1080 handler is not very meaningful. It describes the state of the thread
1081 or process that was interrupted, but there is no way to predict which
1082 one that is. It is possible, although rarely useful, to examine it, but
1083 modifying it is a recipe for disaster.
1085 The activities of an external interrupt handler are severely
1086 restricted. First, only one external interrupt may be processed at a
1087 time, that is, nested external interrupt handling is not supported.
1088 This means that external interrupts must be processed with interrupts
1089 disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
1090 enabled at any point during their execution.
1092 Second, an interrupt handler must not call any function that can
1093 sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
1094 many others. This is because external interrupts use space on the
1095 stack of the kernel thread that was running at the time the interrupt
1096 occurred. If the interrupt handler tried to sleep and that thread
1097 resumed, then the two uses of the single stack would interfere, which
1100 Because an external interrupt runs with interrupts disabled, it
1101 effectively monopolizes the machine and delays all other activities.
1102 Therefore, external interrupt handlers should complete as quickly as
1103 they can. Any activities that require much CPU time should instead
1104 run in a kernel thread, possibly a thread whose activity is triggered
1105 by the interrupt using some synchronization primitive.
1107 External interrupts are also special because they are controlled by a
1108 pair of devices outside the CPU called @dfn{programmable interrupt
1109 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1110 CPU's IDT, it also initializes the PICs for interrupt handling. The
1111 PICs also must be ``acknowledged'' at the end of processing for each
1112 external interrupt. @func{intr_handler} takes care of that by calling
1113 @func{pic_end_of_interrupt}, which sends the proper signals to the
1116 The following additional functions are related to external
1119 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1120 Registers @var{handler} to be called when external interrupt numbered
1121 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1122 purposes. The handler will run with interrupts disabled.
1125 @deftypefun bool intr_context (void)
1126 Returns true if we are running in an interrupt context, otherwise
1127 false. Mainly used at the beginning of functions that might sleep
1128 or that otherwise should not be called from interrupt context, in this
1131 ASSERT (!intr_context ());
1135 @deftypefun void intr_yield_on_return (void)
1136 When called in an interrupt context, causes @func{thread_yield} to be
1137 called just before the interrupt returns. This is used, for example,
1138 in the timer interrupt handler to cause a new thread to be scheduled
1139 when a thread's time slice expires.
1142 @node Memory Allocation
1143 @subsection Memory Allocation
1145 Pintos contains two memory allocators, one that allocates memory in
1146 units of a page, and one that can allocate blocks of any size.
1153 @node Page Allocator
1154 @subsubsection Page Allocator
1156 The page allocator declared in @file{threads/palloc.h} allocates
1157 memory in units of a page. It is most often used to allocate memory
1158 one page at a time, but it can also allocate multiple contiguous pages
1161 The page allocator divides the memory it allocates into two pools,
1162 called the kernel and user pools. By default, each pool gets half of
1163 system memory, but this can be changed with a kernel command line
1164 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1165 pool or the other. If one pool becomes empty, the other may still
1166 have free pages. The user pool should be used for allocating memory
1167 for user processes and the kernel pool for all other allocations.
1168 This will only become important starting with project 3. Until then,
1169 all allocations should be made from the kernel pool.
1171 Each pool's usage is tracked with a bitmap, one bit per page in
1172 the pool. A request to allocate @var{n} pages scans the bitmap
1173 for @var{n} consecutive bits set to
1174 false, indicating that those pages are free, and then sets those bits
1175 to true to mark them as used. This is a ``first fit'' allocation
1178 The page allocator is subject to fragmentation. That is, it may not
1179 be possible to allocate @var{n} contiguous pages even though @var{n}
1180 or more pages are free, because the free pages are separated by used
1181 pages. In fact, in pathological cases it may be impossible to
1182 allocate 2 contiguous pages even though @var{n} / 2 pages are free!
1183 Single-page requests can't fail due to fragmentation, so
1184 it is best to limit, as much as possible, the need for multiple
1187 Pages may not be allocated from interrupt context, but they may be
1190 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1191 a debugging aid (@pxref{Debugging Tips}).
1193 Page allocator types and functions are described below.
1195 @deftp {Type} {enum palloc_flags}
1196 A set of flags that describe how to allocate pages. These flags may
1197 be combined in any combination.
1200 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1201 If the pages cannot be allocated, panic the kernel. This is only
1202 appropriate during kernel initialization. User processes
1203 should never be permitted to panic the kernel.
1206 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1207 Zero all the bytes in the allocated pages before returning them. If not
1208 set, the contents of newly allocated pages are unpredictable.
1211 @defvr {Page Allocator Flag} @code{PAL_USER}
1212 Obtain the pages from the user pool. If not set, pages are allocated
1213 from the kernel pool.
1216 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1217 Obtains and returns a single page, allocating it in the manner specified by
1218 @var{flags}. Returns a null pointer if no pages are
1222 @deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1223 Obtains @var{page_cnt} contiguous free pages, allocating them in the
1224 manner specified by @var{flags}, and returns them. Returns a null
1225 pointer if no pages are free.
1228 @deftypefun void palloc_free_page (void *@var{page})
1229 Frees @var{page}, which must have been obtained using
1230 @func{palloc_get_page} or @func{palloc_get_multiple}.
1233 @deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1234 Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
1235 All of the pages must have been obtained using @func{palloc_get_page}
1236 or @func{palloc_get_multiple}.
1239 @node Block Allocator
1240 @subsubsection Block Allocator
1242 The block allocator, declared in @file{threads/malloc.h}, can allocate
1243 blocks of any size. It is layered on top of the page allocator
1244 described in the previous section. Blocks returned by the block
1245 allocator are obtained from the kernel pool.
1247 The block allocator uses two different strategies for allocating
1248 memory. The first of these applies to ``small'' blocks, those 1 kB or
1250 fourth of the the page size). These allocations are rounded up to the
1251 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1252 grouped into a page used only for allocations of the smae
1255 The second strategy applies to allocating ``large'' blocks, those larger
1257 These allocations (plus a small amount of overhead) are rounded up to
1258 the nearest page in size, and then the block allocator requests that
1259 number of contiguous pages from the page allocator.
1261 In either case, the difference between the allocation requested size
1262 and the actual block size is wasted. A real operating system would
1263 carefully tune its allocator to minimize this waste, but this is
1264 unimportant in an instructional system like Pintos.
1266 As long as a page can be obtained from the page allocator, small
1267 allocations always succeed. Most small allocations will not require a
1268 new page from the page allocator at all. However, large allocations
1269 always require calling into the page allocator, and any allocation
1270 that needs more than one contiguous page can fail due to fragmentation,
1271 as already discussed in the previous section. Thus, you should
1272 minimize the number of large allocations in your code, especially
1273 those over approximately 4 kB each.
1275 The interface to the block allocator is through the standard C library
1276 functions @func{malloc}, @func{calloc}, and @func{free}.
1278 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1279 a debugging aid (@pxref{Debugging Tips}).
1281 The block allocator may not be called from interrupt context.
1283 @node User Programs Tour
1284 @section User Programs Project
1286 No tour for this project is available.
1288 @node Virtual Memory Tour
1289 @section Virtual Memory Project
1291 Only some parts of the tour for this project are available.
1298 @subsection Hash Table
1300 Most implementations of the virtual memory project use a hash table to
1301 translate virtual page frames to physical page frames. It is possible
1302 to do this translation without adding a new data structure, by modifying
1303 the code in @file{userprog/pagedir.c}. However, if you do that you'll
1304 need to carefully study and understand section 3.7, ``Page Translation
1305 Using 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}, and in practice
1306 it is probably easier to add a new data structure. You may find other
1307 uses for hash tables as well.
1309 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1310 To use it you will need to manually include its header file,
1311 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}. Intentionally,
1312 no code provided with Pintos uses the hash table, which means that you
1313 are free to use it as is, modify its implementation for your own
1314 purposes, or ignore it, as you wish.
1318 * Basic Hash Functions::
1319 * Hash Search Functions::
1320 * Hash Iteration Functions::
1321 * Hash Table Example::
1322 * Hash Auxiliary Data::
1323 * Hash Synchronization::
1326 @node Hash Data Types
1327 @subsubsection Data Types
1329 A hash table is represented by @struct{hash}.
1331 @deftp {Type} {@struct{hash}}
1332 Represents an entire hash table. The actual members of @struct{hash}
1333 are ``opaque.'' That is, code that uses a hash table should not access
1334 @struct{hash} members directly, nor should it need to. Instead, use
1335 hash table functions and macros.
1338 The hash table operates on elements of type @struct{hash_elem}.
1340 @deftp {Type} {@struct{hash_elem}}
1341 Embed a @struct{hash_elem} member in the structure you want to include
1342 in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
1343 All functions for operating on hash table elements actually take and
1344 return pointers to @struct{hash_elem}, not pointers to your hash table's
1348 You will often need to obtain a @struct{hash_elem}
1349 given a real element of the hash table, and vice versa. Given
1350 a real element of the hash table, obtaining a pointer to its
1351 @struct{hash_elem} is trivial: take the address of the
1352 @struct{hash_elem} member. Use the @code{hash_entry()} macro to go the
1355 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1356 Returns a pointer to the structure that @var{elem}, a pointer to a
1357 @struct{hash_elem}, is embedded within. You must provide @var{type},
1358 the name of the structure that @var{elem} is inside, and @var{member},
1359 the name of the member in @var{type} that @var{elem} points to.
1361 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1362 that points to a @struct{thread} member (of type @struct{hash_elem})
1363 named @code{h_elem}. Then, @code{hash_entry (h, struct thread, h_elem)}
1364 yields the address of the @struct{thread} that @code{h} points within.
1367 Each hash table element must contain a key, that is, data that
1368 identifies and distinguishes elements in the hash table. Every element
1369 in a hash table at a given time must have a unique key. (Elements may
1370 also contain non-key data that need not be unique.) While an element is
1371 in a hash table, its key data must not be changed. For each hash table,
1372 you must write two functions that act on keys: a hash function and a
1373 comparison function. These functions must match the following
1376 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1377 Returns a hash of @var{element}'s data, as a value anywhere in the range
1378 of @code{unsigned int}. The hash of an element should be a
1379 pseudo-random function of the element's key. It must not depend on
1380 non-key data in the element or on any non-constant data other than the
1381 key. Pintos provides the following functions as a suitable basis for
1384 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1385 Returns a hash of the @var{size} bytes starting at @var{buf}. The
1386 implementation is the general-purpose
1387 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1388 hash} for 32-bit words.
1391 @deftypefun unsigned hash_string (const char *@var{s})
1392 Returns a hash of null-terminated string @var{s}.
1395 @deftypefun unsigned hash_int (int @var{i})
1396 Returns a hash of integer @var{i}.
1399 If your key is a single piece of data of an appropriate type, it is
1400 sensible for your hash function to directly return the output of one of
1401 these functions. For multiple pieces of data, you may wish to combine
1402 the output of more than one call to them using, e.g., the @samp{^}
1404 operator. Finally, you may entirely ignore these functions and write
1405 your own hash function from scratch, but remember that your goal is to
1406 build an operating system kernel, not to design a hash function.
1408 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1411 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1412 Compares the keys stored in elements @var{a} and @var{b}. Returns
1413 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1414 or equal to @var{b}.
1416 If two elements compare equal, then they must hash to equal values.
1418 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1421 A few functions that act on hashes accept a pointer to a third kind of
1422 function as an argument:
1424 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1425 Performs some kind of action, chosen by the caller, on @var{element}.
1427 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1430 @node Basic Hash Functions
1431 @subsubsection Basic Functions
1433 These functions create and destroy hash tables and obtain basic
1434 information about their contents.
1436 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
1437 Initializes @var{hash} as a hash table using @var{hash_func} as hash
1438 function, @var{less_func} as comparison function, and @var{aux} as
1440 Returns true if successful, false on failure. @func{hash_init} calls
1441 @func{malloc} and fails if memory cannot be allocated.
1443 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
1444 most often a null pointer.
1447 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
1448 Removes all the elements from @var{hash}, which must have been
1449 previously initialized with @func{hash_init}.
1451 If @var{action} is non-null, then it is called once for each element in
1452 the hash table, which gives the caller an opportunity to deallocate any
1453 memory or other resources used by the element. For example, if the hash
1454 table elements are dynamically allocated using @func{malloc}, then
1455 @var{action} could @func{free} the element. This is safe because
1456 @func{hash_clear} will not access the memory in a given hash element
1457 after calling @var{action} on it. However, @var{action} must not call
1458 any function that may modify the hash table, such as @func{hash_insert}
1459 or @func{hash_delete}.
1462 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
1463 If @var{action} is non-null, calls it for each element in the hash, with
1464 the same semantics as a call to @func{hash_clear}. Then, frees the
1465 memory held by @var{hash}. Afterward, @var{hash} must not be passed to
1466 any hash table function, absent an intervening call to @func{hash_init}.
1469 @deftypefun size_t hash_size (struct hash *@var{hash})
1470 Returns the number of elements currently stored in @var{hash}.
1473 @deftypefun bool hash_empty (struct hash *@var{hash})
1474 Returns true if @var{hash} currently contains no elements,
1475 false if @var{hash} contains at least one element.
1478 @node Hash Search Functions
1479 @subsubsection Search Functions
1481 Each of these functions searches a hash table for an element that
1482 compares equal to one provided. Based on the success of the search,
1483 they perform some action, such as inserting a new element into the hash
1484 table, or simply return the result of the search.
1486 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
1487 Searches @var{hash} for an element equal to @var{element}. If none is
1488 found, inserts @var{element} into @var{hash} and returns a null pointer.
1489 If the table already contains an element equal to @var{element}, returns
1490 the existing element without modifying @var{hash}.
1493 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
1494 Inserts @var{element} into @var{hash}. Any element equal to
1495 @var{element} already in @var{hash} is removed. Returns the element
1496 removed, or a null pointer if @var{hash} did not contain an element
1497 equal to @var{element}.
1499 The caller is responsible for deallocating any resources associated with
1500 the element returned, as appropriate. For example, if the hash table
1501 elements are dynamically allocated using @func{malloc}, then the caller
1502 must @func{free} the element after it is no longer needed.
1505 The element passed to the following functions is only used for hashing
1506 and comparison purposes. It is never actually inserted into the hash
1507 table. Thus, only the key data in the element need be initialized, and
1508 other data in the element will not be used. It often makes sense to
1509 declare an instance of the element type as a local variable, initialize
1510 the key data, and then pass the address of its @struct{hash_elem} to
1511 @func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
1512 an example. (Large structures should not be
1513 allocated as local variables. @xref{struct thread}, for more
1516 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
1517 Searches @var{hash} for an element equal to @var{element}. Returns the
1518 element found, if any, or a null pointer otherwise.
1521 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
1522 Searches @var{hash} for an element equal to @var{element}. If one is
1523 found, it is removed from @var{hash} and returned. Otherwise, a null
1524 pointer is returned and @var{hash} is unchanged.
1526 The caller is responsible for deallocating any resources associated with
1527 the element returned, as appropriate. For example, if the hash table
1528 elements are dynamically allocated using @func{malloc}, then the caller
1529 must @func{free} the element after it is no longer needed.
1532 @node Hash Iteration Functions
1533 @subsubsection Iteration Functions
1535 These functions allow iterating through the elements in a hash table.
1536 Two interfaces are supplied. The first requires writing and supplying a
1537 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
1539 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
1540 Calls @var{action} once for each element in @var{hash}, in arbitrary
1541 order. @var{action} must not call any function that may modify the hash
1542 table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
1543 must not modify key data in elements, although it may modify any other
1547 The second interface is based on an ``iterator'' data type.
1548 Idiomatically, iterators are used as follows:
1551 struct hash_iterator i;
1554 while (hash_next (&i))
1556 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
1557 @r{@dots{}do something with @i{f}@dots{}}
1561 @deftp {Type} {@struct{hash_iterator}}
1562 Represents a position within a hash table. Calling any function that
1563 may modify a hash table, such as @func{hash_insert} or
1564 @func{hash_delete}, invalidates all iterators within that hash table.
1566 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
1569 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
1570 Initializes @var{iterator} to just before the first element in
1574 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
1575 Advances @var{iterator} to the next element in @var{hash}, and returns
1576 that element. Returns a null pointer if no elements remain. After
1577 @func{hash_next} returns null for @var{iterator}, calling it again
1578 yields undefined behavior.
1581 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
1582 Returns the value most recently returned by @func{hash_next} for
1583 @var{iterator}. Yields undefined behavior after @func{hash_first} has
1584 been called on @var{iterator} but before @func{hash_next} has been
1585 called for the first time.
1588 @node Hash Table Example
1589 @subsubsection Hash Table Example
1591 Suppose you have a structure, called @struct{page}, that you
1592 want to put into a hash table. First, define @struct{page} to include a
1593 @struct{hash_elem} member:
1598 struct hash_elem hash_elem; /* @r{Hash table element.} */
1599 void *addr; /* @r{Virtual address.} */
1600 /* @r{@dots{}other members@dots{}} */
1604 We write a hash function and a comparison function using @var{addr} as
1605 the key. A pointer can be hashed based on its bytes, and the @samp{<}
1606 operator works fine for comparing pointers:
1609 /* @r{Returns a hash value for page @var{p}.} */
1611 page_hash (const struct hash_elem *p_, void *aux UNUSED)
1613 const struct page *p = hash_entry (p_, struct page, hash_elem);
1614 return hash_bytes (&p->addr, sizeof p->addr);
1617 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
1619 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
1622 const struct page *a = hash_entry (a_, struct page, hash_elem);
1623 const struct page *b = hash_entry (b_, struct page, hash_elem);
1625 return a->addr < b->addr;
1630 (The use of @code{UNUSED} in these functions' prototypes suppresses a
1631 warning that @var{aux} is unused. @xref{Function and Parameter
1632 Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
1633 Data}, for an explanation of @var{aux}.)
1635 Then, we can create a hash table like this:
1640 hash_init (&pages, page_hash, page_less, NULL);
1643 Now we can manipulate the hash table we've created. If @code{@var{p}}
1644 is a pointer to a @struct{page}, we can insert it into the hash table
1648 hash_insert (&pages, &p->hash_elem);
1651 @noindent If there's a chance that @var{pages} might already contain a
1652 page with the same @var{addr}, then we should check @func{hash_insert}'s
1655 To search for an element in the hash table, use @func{hash_find}. This
1656 takes a little setup, because @func{hash_find} takes an element to
1657 compare against. Here's a function that will find and return a page
1658 based on a virtual address, assuming that @var{pages} is defined at file
1662 /* @r{Returns the page containing the given virtual @var{address},
1663 or a null pointer if no such page exists.} */
1665 page_lookup (const void *address)
1668 struct hash_elem *e;
1671 e = hash_find (&pages, &p.hash_elem);
1672 return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
1677 @struct{page} is allocated as a local variable here on the assumption
1678 that it is fairly small. Large structures should not be allocated as
1679 local variables. @xref{struct thread}, for more information.
1681 A similar function could delete a page by address using
1684 @node Hash Auxiliary Data
1685 @subsubsection Auxiliary Data
1687 In simple cases like the example above, there's no need for the
1688 @var{aux} parameters. In these cases, just pass a null pointer to
1689 @func{hash_init} for @var{aux} and ignore the values passed to the hash
1690 function and comparison functions. (You'll get a compiler warning if
1691 you don't use the @var{aux} parameter, but you can turn that off with
1692 the @code{UNUSED} macro, as shown in the example, or you can just ignore
1695 @var{aux} is useful when you have some property of the data in the
1696 hash table that's both constant and needed for hashing or comparisons,
1697 but which is not stored in the data items themselves. For example, if
1698 the items in a hash table contain fixed-length strings, but the items
1699 themselves don't indicate what that fixed length is, you could pass
1700 the length as an @var{aux} parameter.
1702 @node Hash Synchronization
1703 @subsubsection Synchronization
1705 The hash table does not do any internal synchronization. It is the
1706 caller's responsibility to synchronize calls to hash table functions.
1707 In general, any number of functions that examine but do not modify the
1708 hash table, such as @func{hash_find} or @func{hash_next}, may execute
1709 simultaneously. However, these function cannot safely execute at the
1710 same time as any function that may modify a given hash table, such as
1711 @func{hash_insert} or @func{hash_delete}, nor may more than one function
1712 that can modify a given hash table execute safely at once.
1714 It is also the caller's responsibility to synchronize access to data in
1715 hash table elements. How to synchronize access to this data depends on
1716 how it is designed and organized, as with any other data structure.
1718 @node File Systems Tour
1719 @section File Systems Project
1721 No tour for this project is available.