2 @appendix Reference Guide
4 This chapter is a reference for the Pintos code. The reference guide
5 does not cover all of the code in Pintos, but it does cover those
6 pieces that students most often find troublesome. You may find that
7 you want to read each part of the reference guide as you work on the
8 project where it becomes important.
10 We recommend using ``tags'' to follow along with references to function
11 and variable names (@pxref{Tags}).
17 * Interrupt Handling::
27 This section covers the Pintos loader and basic kernel
32 * Low-Level Kernel Initialization::
33 * High-Level Kernel Initialization::
34 * Physical Memory Map::
38 @subsection The Loader
40 The first part of Pintos that runs is the loader, in
41 @file{threads/loader.S}. The PC BIOS loads the loader into memory.
42 The loader, in turn, is responsible for finding the kernel on disk,
43 loading it into memory, and then jumping to its start. It's
44 not important to understand exactly how the loader works, but if
45 you're interested, read on. You should probably read along with the
46 loader's source. You should also understand the basics of the
47 80@var{x}86 architecture as described by chapter 3, ``Basic Execution
48 Environment,'' of @bibref{IA32-v1}.
50 The PC BIOS loads the loader from the first sector of the first hard
51 disk, called the @dfn{master boot record} (MBR). PC conventions
52 reserve 64 bytes of the MBR for the partition table, and Pintos uses
53 about 128 additional bytes for kernel command-line arguments. This
54 leaves a little over 300 bytes for the loader's own code. This is a
55 severe restriction that means, practically speaking, the loader must
56 be written in assembly language.
58 The Pintos loader and kernel don't have to be on the same disk, nor
59 does is the kernel required to be in any particular location on a
60 given disk. The loader's first job, then, is to find the kernel by
61 reading the partition table on each hard disk, looking for a bootable
62 partition of the type used for a Pintos kernel.
64 When the loader finds a bootable kernel partition, it reads the
65 partition's contents into memory at physical address @w{128 kB}. The
66 kernel is at the beginning of the partition, which might be larger
67 than necessary due to partition boundary alignment conventions, so the
68 loader reads no more than @w{512 kB} (and the Pintos build process
69 will refuse to produce kernels larger than that). Reading more data
70 than this would cross into the region from @w{640 kB} to @w{1 MB} that
71 the PC architecture reserves for hardware and the BIOS, and a standard
72 PC BIOS does not provide any means to load the kernel above @w{1 MB}.
74 The loader's final job is to extract the entry point from the loaded
75 kernel image and transfer control to it. The entry point is not at a
76 predictable location, but the kernel's ELF header contains a pointer
77 to it. The loader extracts the pointer and jumps to the location it
80 The Pintos kernel command line
81 is stored in the boot loader. The @command{pintos} program actually
82 modifies a copy of the boot loader on disk each time it runs the kernel,
83 inserting whatever command-line arguments the user supplies to the kernel,
84 and then the kernel at boot time reads those arguments out of the boot
85 loader in memory. This is not an elegant solution, but it is simple
88 @node Low-Level Kernel Initialization
89 @subsection Low-Level Kernel Initialization
91 The loader's last action is to transfer control to the kernel's entry
92 point, which is @func{start} in @file{threads/start.S}. The job of
93 this code is to switch the CPU from legacy 16-bit ``real mode'' into
94 the 32-bit ``protected mode'' used by all modern 80@var{x}86 operating
97 The startup code's first task is actually to obtain the machine's
98 memory size, by asking the BIOS for the PC's memory size. The
99 simplest BIOS function to do this can only detect up to 64 MB of RAM,
100 so that's the practical limit that Pintos can support. The function
101 stores the memory size, in pages, in global variable
102 @code{init_ram_pages}.
104 The first part of CPU initialization is to enable the A20 line, that
105 is, the CPU's address line numbered 20. For historical reasons, PCs
106 boot with this address line fixed at 0, which means that attempts to
107 access memory beyond the first 1 MB (2 raised to the 20th power) will
108 fail. Pintos wants to access more memory than this, so we have to
111 Next, the loader creates a basic page table. This page table maps
112 the 64 MB at the base of virtual memory (starting at virtual address
113 0) directly to the identical physical addresses. It also maps the
114 same physical memory starting at virtual address
115 @code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB). The
116 Pintos kernel only wants the latter mapping, but there's a
117 chicken-and-egg problem if we don't include the former: our current
118 virtual address is roughly @t{0x20000}, the location where the loader
119 put us, and we can't jump to @t{0xc0020000} until we turn on the
120 page table, but if we turn on the page table without jumping there,
121 then we've just pulled the rug out from under ourselves.
123 After the page table is initialized, we load the CPU's control
124 registers to turn on protected mode and paging, and set up the segment
125 registers. We aren't yet equipped to handle interrupts in protected
126 mode, so we disable interrupts. The final step is to call @func{main}.
128 @node High-Level Kernel Initialization
129 @subsection High-Level Kernel Initialization
131 The kernel proper starts with the @func{main} function. The
132 @func{main} function is written in C, as will be most of the code we
133 encounter in Pintos from here on out.
135 When @func{main} starts, the system is in a pretty raw state. We're
136 in 32-bit protected mode with paging enabled, but hardly anything else is
137 ready. Thus, the @func{main} function consists primarily of calls
138 into other Pintos modules' initialization functions.
139 These are usually named @func{@var{module}_init}, where
140 @var{module} is the module's name, @file{@var{module}.c} is the
141 module's source code, and @file{@var{module}.h} is the module's
144 The first step in @func{main} is to call @func{bss_init}, which clears
145 out the kernel's ``BSS'', which is the traditional name for a
146 segment that should be initialized to all zeros. In most C
147 implementations, whenever you
148 declare a variable outside a function without providing an
149 initializer, that variable goes into the BSS. Because it's all zeros, the
150 BSS isn't stored in the image that the loader brought into memory. We
151 just use @func{memset} to zero it out.
153 Next, @func{main} calls @func{read_command_line} to break the kernel command
154 line into arguments, then @func{parse_options} to read any options at
155 the beginning of the command line. (Actions specified on the
156 command line execute later.)
158 @func{thread_init} initializes the thread system. We will defer full
159 discussion to our discussion of Pintos threads below. It is called so
160 early in initialization because a valid thread structure is a
161 prerequisite for acquiring a lock, and lock acquisition in turn is
162 important to other Pintos subsystems. Then we initialize the console
163 and print a startup message to the console.
165 The next block of functions we call initializes the kernel's memory
166 system. @func{palloc_init} sets up the kernel page allocator, which
167 doles out memory one or more pages at a time (@pxref{Page Allocator}).
168 @func{malloc_init} sets
169 up the allocator that handles allocations of arbitrary-size blocks of
170 memory (@pxref{Block Allocator}).
171 @func{paging_init} sets up a page table for the kernel (@pxref{Page
174 In projects 2 and later, @func{main} also calls @func{tss_init} and
177 The next set of calls initializes the interrupt system.
178 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
179 (IDT) to ready it for interrupt handling (@pxref{Interrupt
180 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
181 handling timer interrupts and keyboard interrupts, respectively.
182 @func{input_init} sets up to merge serial and keyboard input into one
184 projects 2 and later, we also prepare to handle interrupts caused by
185 user programs using @func{exception_init} and @func{syscall_init}.
187 Now that interrupts are set up, we can start the scheduler
188 with @func{thread_start}, which creates the idle thread and enables
190 With interrupts enabled, interrupt-driven serial port I/O becomes
192 @func{serial_init_queue} to switch to that mode. Finally,
193 @func{timer_calibrate} calibrates the timer for accurate short delays.
195 If the file system is compiled in, as it will starting in project 2, we
196 initialize the IDE disks with @func{ide_init}, then the
197 file system with @func{filesys_init}.
199 Boot is complete, so we print a message.
201 Function @func{run_actions} now parses and executes actions specified on
202 the kernel command line, such as @command{run} to run a test (in project
203 1) or a user program (in later projects).
205 Finally, if @option{-q} was specified on the kernel command line, we
206 call @func{shutdown_power_off} to terminate the machine simulator. Otherwise,
207 @func{main} calls @func{thread_exit}, which allows any other running
208 threads to continue running.
210 @node Physical Memory Map
211 @subsection Physical Memory Map
213 @multitable {@t{00000000}--@t{00000000}} {Hardware} {Some much longer explanatory text}
214 @headitem Memory Range
218 @item @t{00000000}--@t{000003ff} @tab CPU @tab Real mode interrupt table.
219 @item @t{00000400}--@t{000005ff} @tab BIOS @tab Miscellaneous data area.
220 @item @t{00000600}--@t{00007bff} @tab --- @tab ---
221 @item @t{00007c00}--@t{00007dff} @tab Pintos @tab Loader.
222 @item @t{0000e000}--@t{0000efff} @tab Pintos
223 @tab Stack for loader; kernel stack and @struct{thread} for initial
225 @item @t{0000f000}--@t{0000ffff} @tab Pintos
226 @tab Page directory for startup code.
227 @item @t{00010000}--@t{00020000} @tab Pintos
228 @tab Page tables for startup code.
229 @item @t{00020000}--@t{0009ffff} @tab Pintos
230 @tab Kernel code, data, and uninitialized data segments.
231 @item @t{000a0000}--@t{000bffff} @tab Video @tab VGA display memory.
232 @item @t{000c0000}--@t{000effff} @tab Hardware
233 @tab Reserved for expansion card RAM and ROM.
234 @item @t{000f0000}--@t{000fffff} @tab BIOS @tab ROM BIOS.
235 @item @t{00100000}--@t{03ffffff} @tab Pintos @tab Dynamic memory allocation.
248 @subsection @code{struct thread}
250 The main Pintos data structure for threads is @struct{thread},
251 declared in @file{threads/thread.h}.
253 @deftp {Structure} {struct thread}
254 Represents a thread or a user process. In the projects, you will have
255 to add your own members to @struct{thread}. You may also change or
256 delete the definitions of existing members.
258 Every @struct{thread} occupies the beginning of its own page of
259 memory. The rest of the page is used for the thread's stack, which
260 grows downward from the end of the page. It looks like this:
264 4 kB +---------------------------------+
278 sizeof (struct thread) +---------------------------------+
284 0 kB +---------------------------------+
288 This has two consequences. First, @struct{thread} must not be allowed
289 to grow too big. If it does, then there will not be enough room for the
290 kernel stack. The base @struct{thread} is only a few bytes in size. It
291 probably should stay well under 1 kB.
293 Second, kernel stacks must not be allowed to grow too large. If a stack
294 overflows, it will corrupt the thread state. Thus, kernel functions
295 should not allocate large structures or arrays as non-static local
296 variables. Use dynamic allocation with @func{malloc} or
297 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
300 @deftypecv {Member} {@struct{thread}} {tid_t} tid
301 The thread's thread identifier or @dfn{tid}. Every thread must have a
302 tid that is unique over the entire lifetime of the kernel. By
303 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
304 thread receives the numerically next higher tid, starting from 1 for
305 the initial process. You can change the type and the numbering scheme
309 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
310 @anchor{Thread States}
311 The thread's state, one of the following:
313 @defvr {Thread State} @code{THREAD_RUNNING}
314 The thread is running. Exactly one thread is running at a given time.
315 @func{thread_current} returns the running thread.
318 @defvr {Thread State} @code{THREAD_READY}
319 The thread is ready to run, but it's not running right now. The
320 thread could be selected to run the next time the scheduler is
321 invoked. Ready threads are kept in a doubly linked list called
325 @defvr {Thread State} @code{THREAD_BLOCKED}
326 The thread is waiting for something, e.g.@: a lock to become
327 available, an interrupt to be invoked. The thread won't be scheduled
328 again until it transitions to the @code{THREAD_READY} state with a
329 call to @func{thread_unblock}. This is most conveniently done
330 indirectly, using one of the Pintos synchronization primitives that
331 block and unblock threads automatically (@pxref{Synchronization}).
333 There is no @i{a priori} way to tell what a blocked thread is waiting
334 for, but a backtrace can help (@pxref{Backtraces}).
337 @defvr {Thread State} @code{THREAD_DYING}
338 The thread will be destroyed by the scheduler after switching to the
343 @deftypecv {Member} {@struct{thread}} {char} name[16]
344 The thread's name as a string, or at least the first few characters of
348 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
349 Every thread has its own stack to keep track of its state. When the
350 thread is running, the CPU's stack pointer register tracks the top of
351 the stack and this member is unused. But when the CPU switches to
352 another thread, this member saves the thread's stack pointer. No
353 other members are needed to save the thread's registers, because the
354 other registers that must be saved are saved on the stack.
356 When an interrupt occurs, whether in the kernel or a user program, an
357 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
358 in a user program, the @struct{intr_frame} is always at the very top of
359 the page. @xref{Interrupt Handling}, for more information.
362 @deftypecv {Member} {@struct{thread}} {int} priority
363 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
364 (63). Lower numbers correspond to lower priorities, so that
365 priority 0 is the lowest priority and priority 63 is the highest.
366 Pintos as provided ignores thread priorities, but you will implement
367 priority scheduling in project 1 (@pxref{Priority Scheduling}).
370 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} allelem
371 This ``list element'' is used to link the thread into the list of all
372 threads. Each thread is inserted into this list when it is created
373 and removed when it exits. The @func{thread_foreach} function should
374 be used to iterate over all threads.
377 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
378 A ``list element'' used to put the thread into doubly linked lists,
379 either @code{ready_list} (the list of threads ready to run) or a list of
380 threads waiting on a semaphore in @func{sema_down}. It can do double
381 duty because a thread waiting on a semaphore is not ready, and vice
385 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
386 Only present in project 2 and later. @xref{Page Tables}.
389 @deftypecv {Member} {@struct{thread}} {unsigned} magic
390 Always set to @code{THREAD_MAGIC}, which is just an arbitrary number defined
391 in @file{threads/thread.c}, and used to detect stack overflow.
392 @func{thread_current} checks that the @code{magic} member of the running
393 thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
394 tends to change this value, triggering the assertion. For greatest
395 benefit, as you add members to @struct{thread}, leave @code{magic} at
399 @node Thread Functions
400 @subsection Thread Functions
402 @file{threads/thread.c} implements several public functions for thread
403 support. Let's take a look at the most useful:
405 @deftypefun void thread_init (void)
406 Called by @func{main} to initialize the thread system. Its main
407 purpose is to create a @struct{thread} for Pintos's initial thread.
408 This is possible because the Pintos loader puts the initial
409 thread's stack at the top of a page, in the same position as any other
412 Before @func{thread_init} runs,
413 @func{thread_current} will fail because the running thread's
414 @code{magic} value is incorrect. Lots of functions call
415 @func{thread_current} directly or indirectly, including
416 @func{lock_acquire} for locking a lock, so @func{thread_init} is
417 called early in Pintos initialization.
420 @deftypefun void thread_start (void)
421 Called by @func{main} to start the scheduler. Creates the idle
422 thread, that is, the thread that is scheduled when no other thread is
423 ready. Then enables interrupts, which as a side effect enables the
424 scheduler because the scheduler runs on return from the timer interrupt, using
425 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
428 @deftypefun void thread_tick (void)
429 Called by the timer interrupt at each timer tick. It keeps track of
430 thread statistics and triggers the scheduler when a time slice expires.
433 @deftypefun void thread_print_stats (void)
434 Called during Pintos shutdown to print thread statistics.
437 @deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
438 Creates and starts a new thread named @var{name} with the given
439 @var{priority}, returning the new thread's tid. The thread executes
440 @var{func}, passing @var{aux} as the function's single argument.
442 @func{thread_create} allocates a page for the thread's
443 @struct{thread} and stack and initializes its members, then it sets
444 up a set of fake stack frames for it (@pxref{Thread Switching}). The
445 thread is initialized in the blocked state, then unblocked just before
446 returning, which allows the new thread to
447 be scheduled (@pxref{Thread States}).
449 @deftp {Type} {void thread_func (void *@var{aux})}
450 This is the type of the function passed to @func{thread_create}, whose
451 @var{aux} argument is passed along as the function's argument.
455 @deftypefun void thread_block (void)
456 Transitions the running thread from the running state to the blocked
457 state (@pxref{Thread States}). The thread will not run again until
458 @func{thread_unblock} is
459 called on it, so you'd better have some way arranged for that to happen.
460 Because @func{thread_block} is so low-level, you should prefer to use
461 one of the synchronization primitives instead (@pxref{Synchronization}).
464 @deftypefun void thread_unblock (struct thread *@var{thread})
465 Transitions @var{thread}, which must be in the blocked state, to the
466 ready state, allowing it to resume running (@pxref{Thread States}).
467 This is called when the event that the thread is waiting for occurs,
468 e.g.@: when the lock that
469 the thread is waiting on becomes available.
472 @deftypefun {struct thread *} thread_current (void)
473 Returns the running thread.
476 @deftypefun {tid_t} thread_tid (void)
477 Returns the running thread's thread id. Equivalent to
478 @code{thread_current ()->tid}.
481 @deftypefun {const char *} thread_name (void)
482 Returns the running thread's name. Equivalent to @code{thread_current
486 @deftypefun void thread_exit (void) @code{NO_RETURN}
487 Causes the current thread to exit. Never returns, hence
488 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
491 @deftypefun void thread_yield (void)
492 Yields the CPU to the scheduler, which picks a new thread to run. The
493 new thread might be the current thread, so you can't depend on this
494 function to keep this thread from running for any particular length of
498 @deftypefun void thread_foreach (thread_action_func *@var{action}, void *@var{aux})
499 Iterates over all threads @var{t} and invokes @code{action(t, aux)} on each.
500 @var{action} must refer to a function that matches the signature
501 given by @func{thread_action_func}:
503 @deftp {Type} {void thread_action_func (struct thread *@var{thread}, void *@var{aux})}
504 Performs some action on a thread, given @var{aux}.
508 @deftypefun int thread_get_priority (void)
509 @deftypefunx void thread_set_priority (int @var{new_priority})
510 Stub to set and get thread priority. @xref{Priority Scheduling}.
513 @deftypefun int thread_get_nice (void)
514 @deftypefunx void thread_set_nice (int @var{new_nice})
515 @deftypefunx int thread_get_recent_cpu (void)
516 @deftypefunx int thread_get_load_avg (void)
517 Stubs for the advanced scheduler. @xref{4.4BSD Scheduler}.
520 @node Thread Switching
521 @subsection Thread Switching
523 @func{schedule} is responsible for switching threads. It
524 is internal to @file{threads/thread.c} and called only by the three
525 public thread functions that need to switch threads:
526 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
527 Before any of these functions call @func{schedule}, they disable
528 interrupts (or ensure that they are already disabled) and then change
529 the running thread's state to something other than running.
531 @func{schedule} is short but tricky. It records the
532 current thread in local variable @var{cur}, determines the next thread
533 to run as local variable @var{next} (by calling
534 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
535 the actual thread switch. The thread we switched to was also running
536 inside @func{switch_threads}, as are all the threads not currently
537 running, so the new thread now returns out of
538 @func{switch_threads}, returning the previously running thread.
540 @func{switch_threads} is an assembly language routine in
541 @file{threads/switch.S}. It saves registers on the stack, saves the
542 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
543 member, restores the new thread's @code{stack} into the CPU's stack
544 pointer, restores registers from the stack, and returns.
546 The rest of the scheduler is implemented in @func{thread_schedule_tail}. It
547 marks the new thread as running. If the thread we just switched from
548 is in the dying state, then it also frees the page that contained the
549 dying thread's @struct{thread} and stack. These couldn't be freed
550 prior to the thread switch because the switch needed to use it.
552 Running a thread for the first time is a special case. When
553 @func{thread_create} creates a new thread, it goes through a fair
554 amount of trouble to get it started properly. In particular, the new
555 thread hasn't started running yet, so there's no way for it to be
556 running inside @func{switch_threads} as the scheduler expects. To
557 solve the problem, @func{thread_create} creates some fake stack frames
558 in the new thread's stack:
562 The topmost fake stack frame is for @func{switch_threads}, represented
563 by @struct{switch_threads_frame}. The important part of this frame is
564 its @code{eip} member, the return address. We point @code{eip} to
565 @func{switch_entry}, indicating it to be the function that called
569 The next fake stack frame is for @func{switch_entry}, an assembly
570 language routine in @file{threads/switch.S} that adjusts the stack
571 pointer,@footnote{This is because @func{switch_threads} takes
572 arguments on the stack and the 80@var{x}86 SVR4 calling convention
573 requires the caller, not the called function, to remove them when the
574 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
575 calls @func{thread_schedule_tail} (this special case is why
576 @func{thread_schedule_tail} is separate from @func{schedule}), and returns.
577 We fill in its stack frame so that it returns into
578 @func{kernel_thread}, a function in @file{threads/thread.c}.
581 The final stack frame is for @func{kernel_thread}, which enables
582 interrupts and calls the thread's function (the function passed to
583 @func{thread_create}). If the thread's function returns, it calls
584 @func{thread_exit} to terminate the thread.
587 @node Synchronization
588 @section Synchronization
590 If sharing of resources between threads is not handled in a careful,
591 controlled fashion, the result is usually a big mess.
592 This is especially the case in operating system kernels, where
593 faulty sharing can crash the entire machine. Pintos provides several
594 synchronization primitives to help out.
597 * Disabling Interrupts::
601 * Optimization Barriers::
604 @node Disabling Interrupts
605 @subsection Disabling Interrupts
607 The crudest way to do synchronization is to disable interrupts, that
608 is, to temporarily prevent the CPU from responding to interrupts. If
609 interrupts are off, no other thread will preempt the running thread,
610 because thread preemption is driven by the timer interrupt. If
611 interrupts are on, as they normally are, then the running thread may
612 be preempted by another at any time, whether between two C statements
613 or even within the execution of one.
615 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
616 is, kernel threads can be preempted at any time. Traditional Unix
617 systems are ``nonpreemptible,'' that is, kernel threads can only be
618 preempted at points where they explicitly call into the scheduler.
619 (User programs can be preempted at any time in both models.) As you
620 might imagine, preemptible kernels require more explicit
623 You should have little need to set the interrupt state directly. Most
624 of the time you should use the other synchronization primitives
625 described in the following sections. The main reason to disable
626 interrupts is to synchronize kernel threads with external interrupt
627 handlers, which cannot sleep and thus cannot use most other forms of
628 synchronization (@pxref{External Interrupt Handling}).
630 Some external interrupts cannot be postponed, even by disabling
631 interrupts. These interrupts, called @dfn{non-maskable interrupts}
632 (NMIs), are supposed to be used only in emergencies, e.g.@: when the
633 computer is on fire. Pintos does not handle non-maskable interrupts.
635 Types and functions for disabling and enabling interrupts are in
636 @file{threads/interrupt.h}.
638 @deftp Type {enum intr_level}
639 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
640 disabled or enabled, respectively.
643 @deftypefun {enum intr_level} intr_get_level (void)
644 Returns the current interrupt state.
647 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
648 Turns interrupts on or off according to @var{level}. Returns the
649 previous interrupt state.
652 @deftypefun {enum intr_level} intr_enable (void)
653 Turns interrupts on. Returns the previous interrupt state.
656 @deftypefun {enum intr_level} intr_disable (void)
657 Turns interrupts off. Returns the previous interrupt state.
661 @subsection Semaphores
663 A @dfn{semaphore} is a nonnegative integer together with two operators
664 that manipulate it atomically, which are:
668 ``Down'' or ``P'': wait for the value to become positive, then
672 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
676 A semaphore initialized to 0 may be used to wait for an event
677 that will happen exactly once. For example, suppose thread @var{A}
678 starts another thread @var{B} and wants to wait for @var{B} to signal
679 that some activity is complete. @var{A} can create a semaphore
680 initialized to 0, pass it to @var{B} as it starts it, and then
681 ``down'' the semaphore. When @var{B} finishes its activity, it
682 ``ups'' the semaphore. This works regardless of whether @var{A}
683 ``downs'' the semaphore or @var{B} ``ups'' it first.
685 A semaphore initialized to 1 is typically used for controlling access
686 to a resource. Before a block of code starts using the resource, it
687 ``downs'' the semaphore, then after it is done with the resource it
688 ``ups'' the resource. In such a case a lock, described below, may be
691 Semaphores can also be initialized to values larger than 1. These are
694 Semaphores were invented by Edsger Dijkstra and first used in the THE
695 operating system (@bibref{Dijkstra}).
697 Pintos' semaphore type and operations are declared in
698 @file{threads/synch.h}.
700 @deftp {Type} {struct semaphore}
701 Represents a semaphore.
704 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
705 Initializes @var{sema} as a new semaphore with the given initial
709 @deftypefun void sema_down (struct semaphore *@var{sema})
710 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
711 its value to become positive and then decrementing it by one.
714 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
715 Tries to execute the ``down'' or ``P'' operation on @var{sema},
716 without waiting. Returns true if @var{sema}
717 was successfully decremented, or false if it was already
718 zero and thus could not be decremented without waiting. Calling this
720 tight loop wastes CPU time, so use @func{sema_down} or find a
721 different approach instead.
724 @deftypefun void sema_up (struct semaphore *@var{sema})
725 Executes the ``up'' or ``V'' operation on @var{sema},
726 incrementing its value. If any threads are waiting on
727 @var{sema}, wakes one of them up.
729 Unlike most synchronization primitives, @func{sema_up} may be called
730 inside an external interrupt handler (@pxref{External Interrupt
734 Semaphores are internally built out of disabling interrupt
735 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
736 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
737 a list of waiting threads, using the linked list
738 implementation in @file{lib/kernel/list.c}.
743 A @dfn{lock} is like a semaphore with an initial value of 1
744 (@pxref{Semaphores}). A lock's equivalent of ``up'' is called
745 ``release'', and the ``down'' operation is called ``acquire''.
747 Compared to a semaphore, a lock has one added restriction: only the
748 thread that acquires a lock, called the lock's ``owner'', is allowed to
749 release it. If this restriction is a problem, it's a good sign that a
750 semaphore should be used, instead of a lock.
752 Locks in Pintos are not ``recursive,'' that is, it is an error for the
753 thread currently holding a lock to try to acquire that lock.
755 Lock types and functions are declared in @file{threads/synch.h}.
757 @deftp {Type} {struct lock}
761 @deftypefun void lock_init (struct lock *@var{lock})
762 Initializes @var{lock} as a new lock.
763 The lock is not initially owned by any thread.
766 @deftypefun void lock_acquire (struct lock *@var{lock})
767 Acquires @var{lock} for the current thread, first waiting for
768 any current owner to release it if necessary.
771 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
772 Tries to acquire @var{lock} for use by the current thread, without
773 waiting. Returns true if successful, false if the lock is already
774 owned. Calling this function in a tight loop is a bad idea because it
775 wastes CPU time, so use @func{lock_acquire} instead.
778 @deftypefun void lock_release (struct lock *@var{lock})
779 Releases @var{lock}, which the current thread must own.
782 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
783 Returns true if the running thread owns @var{lock},
785 There is no function to test whether an arbitrary thread owns a lock,
786 because the answer could change before the caller could act on it.
792 A @dfn{monitor} is a higher-level form of synchronization than a
793 semaphore or a lock. A monitor consists of data being synchronized,
794 plus a lock, called the @dfn{monitor lock}, and one or more
795 @dfn{condition variables}. Before it accesses the protected data, a
796 thread first acquires the monitor lock. It is then said to be ``in the
797 monitor''. While in the monitor, the thread has control over all the
798 protected data, which it may freely examine or modify. When access to
799 the protected data is complete, it releases the monitor lock.
801 Condition variables allow code in the monitor to wait for a condition to
802 become true. Each condition variable is associated with an abstract
803 condition, e.g.@: ``some data has arrived for processing'' or ``over 10
804 seconds has passed since the user's last keystroke''. When code in the
805 monitor needs to wait for a condition to become true, it ``waits'' on
806 the associated condition variable, which releases the lock and waits for
807 the condition to be signaled. If, on the other hand, it has caused one
808 of these conditions to become true, it ``signals'' the condition to wake
809 up one waiter, or ``broadcasts'' the condition to wake all of them.
811 The theoretical framework for monitors was laid out by C.@: A.@: R.@:
812 Hoare (@bibref{Hoare}). Their practical usage was later elaborated in a
813 paper on the Mesa operating system (@bibref{Lampson}).
815 Condition variable types and functions are declared in
816 @file{threads/synch.h}.
818 @deftp {Type} {struct condition}
819 Represents a condition variable.
822 @deftypefun void cond_init (struct condition *@var{cond})
823 Initializes @var{cond} as a new condition variable.
826 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
827 Atomically releases @var{lock} (the monitor lock) and waits for
828 @var{cond} to be signaled by some other piece of code. After
829 @var{cond} is signaled, reacquires @var{lock} before returning.
830 @var{lock} must be held before calling this function.
832 Sending a signal and waking up from a wait are not an atomic operation.
833 Thus, typically @func{cond_wait}'s caller must recheck the condition
834 after the wait completes and, if necessary, wait again. See the next
835 section for an example.
838 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
839 If any threads are waiting on @var{cond} (protected by monitor lock
840 @var{lock}), then this function wakes up one of them. If no threads are
841 waiting, returns without performing any action.
842 @var{lock} must be held before calling this function.
845 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
846 Wakes up all threads, if any, waiting on @var{cond} (protected by
847 monitor lock @var{lock}). @var{lock} must be held before calling this
851 @subsubsection Monitor Example
853 The classical example of a monitor is handling a buffer into which one
855 ``producer'' threads write characters and out of which one or more
856 ``consumer'' threads read characters. To implement this we need,
857 besides the monitor lock, two condition variables which we will call
858 @var{not_full} and @var{not_empty}:
861 char buf[BUF_SIZE]; /* @r{Buffer.} */
862 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
863 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
864 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
865 struct lock lock; /* @r{Monitor lock.} */
866 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
867 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
869 @dots{}@r{initialize the locks and condition variables}@dots{}
871 void put (char ch) @{
872 lock_acquire (&lock);
873 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
874 cond_wait (¬_full, &lock);
875 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
877 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
878 lock_release (&lock);
883 lock_acquire (&lock);
884 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
885 cond_wait (¬_empty, &lock);
886 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
888 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
889 lock_release (&lock);
893 Note that @code{BUF_SIZE} must divide evenly into @code{SIZE_MAX + 1}
894 for the above code to be completely correct. Otherwise, it will fail
895 the first time @code{head} wraps around to 0. In practice,
896 @code{BUF_SIZE} would ordinarily be a power of 2.
898 @node Optimization Barriers
899 @subsection Optimization Barriers
901 @c We should try to come up with a better example.
902 @c Perhaps something with a linked list?
904 An @dfn{optimization barrier} is a special statement that prevents the
905 compiler from making assumptions about the state of memory across the
906 barrier. The compiler will not reorder reads or writes of variables
907 across the barrier or assume that a variable's value is unmodified
908 across the barrier, except for local variables whose address is never
909 taken. In Pintos, @file{threads/synch.h} defines the @code{barrier()}
910 macro as an optimization barrier.
912 One reason to use an optimization barrier is when data can change
913 asynchronously, without the compiler's knowledge, e.g.@: by another
914 thread or an interrupt handler. The @func{too_many_loops} function in
915 @file{devices/timer.c} is an example. This function starts out by
916 busy-waiting in a loop until a timer tick occurs:
919 /* Wait for a timer tick. */
920 int64_t start = ticks;
921 while (ticks == start)
926 Without an optimization barrier in the loop, the compiler could
927 conclude that the loop would never terminate, because @code{start} and
928 @code{ticks} start out equal and the loop itself never changes them.
929 It could then ``optimize'' the function into an infinite loop, which
930 would definitely be undesirable.
932 Optimization barriers can be used to avoid other compiler
933 optimizations. The @func{busy_wait} function, also in
934 @file{devices/timer.c}, is an example. It contains this loop:
942 The goal of this loop is to busy-wait by counting @code{loops} down
943 from its original value to 0. Without the barrier, the compiler could
944 delete the loop entirely, because it produces no useful output and has
945 no side effects. The barrier forces the compiler to pretend that the
946 loop body has an important effect.
948 Finally, optimization barriers can be used to force the ordering of
949 memory reads or writes. For example, suppose we add a ``feature''
950 that, whenever a timer interrupt occurs, the character in global
951 variable @code{timer_put_char} is printed on the console, but only if
952 global Boolean variable @code{timer_do_put} is true. The best way to
953 set up @samp{x} to be printed is then to use an optimization barrier,
957 timer_put_char = 'x';
962 Without the barrier, the code is buggy because the compiler is free to
963 reorder operations when it doesn't see a reason to keep them in the
964 same order. In this case, the compiler doesn't know that the order of
965 assignments is important, so its optimizer is permitted to exchange
966 their order. There's no telling whether it will actually do this, and
967 it is possible that passing the compiler different optimization flags
968 or using a different version of the compiler will produce different
971 Another solution is to disable interrupts around the assignments.
972 This does not prevent reordering, but it prevents the interrupt
973 handler from intervening between the assignments. It also has the
974 extra runtime cost of disabling and re-enabling interrupts:
977 enum intr_level old_level = intr_disable ();
978 timer_put_char = 'x';
980 intr_set_level (old_level);
983 A second solution is to mark the declarations of
984 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
985 keyword tells the compiler that the variables are externally observable
986 and restricts its latitude for optimization. However, the semantics of
987 @samp{volatile} are not well-defined, so it is not a good general
988 solution. The base Pintos code does not use @samp{volatile} at all.
990 The following is @emph{not} a solution, because locks neither prevent
991 interrupts nor prevent the compiler from reordering the code within the
992 region where the lock is held:
995 lock_acquire (&timer_lock); /* INCORRECT CODE */
996 timer_put_char = 'x';
998 lock_release (&timer_lock);
1001 The compiler treats invocation of any function defined externally,
1002 that is, in another source file, as a limited form of optimization
1003 barrier. Specifically, the compiler assumes that any externally
1004 defined function may access any statically or dynamically allocated
1005 data and any local variable whose address is taken. This often means
1006 that explicit barriers can be omitted. It is one reason that Pintos
1007 contains few explicit barriers.
1009 A function defined in the same source file, or in a header included by
1010 the source file, cannot be relied upon as a optimization barrier.
1011 This applies even to invocation of a function before its
1012 definition, because the compiler may read and parse the entire source
1013 file before performing optimization.
1015 @node Interrupt Handling
1016 @section Interrupt Handling
1018 An @dfn{interrupt} notifies the CPU of some event. Much of the work
1019 of an operating system relates to interrupts in one way or another.
1020 For our purposes, we classify interrupts into two broad categories:
1024 @dfn{Internal interrupts}, that is, interrupts caused directly by CPU
1025 instructions. System calls, attempts at invalid memory access
1026 (@dfn{page faults}), and attempts to divide by zero are some activities
1027 that cause internal interrupts. Because they are caused by CPU
1028 instructions, internal interrupts are @dfn{synchronous} or synchronized
1029 with CPU instructions. @func{intr_disable} does not disable internal
1033 @dfn{External interrupts}, that is, interrupts originating outside the
1034 CPU. These interrupts come from hardware devices such as the system
1035 timer, keyboard, serial ports, and disks. External interrupts are
1036 @dfn{asynchronous}, meaning that their delivery is not
1037 synchronized with instruction execution. Handling of external interrupts
1038 can be postponed with @func{intr_disable} and related functions
1039 (@pxref{Disabling Interrupts}).
1042 The CPU treats both classes of interrupts largely the same way,
1043 so Pintos has common infrastructure to handle both classes.
1044 The following section describes this
1045 common infrastructure. The sections after that give the specifics of
1046 external and internal interrupts.
1048 If you haven't already read chapter 3, ``Basic Execution Environment,''
1049 in @bibref{IA32-v1}, it is recommended that you do so now. You might
1050 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
1054 * Interrupt Infrastructure::
1055 * Internal Interrupt Handling::
1056 * External Interrupt Handling::
1059 @node Interrupt Infrastructure
1060 @subsection Interrupt Infrastructure
1062 When an interrupt occurs, the CPU saves
1063 its most essential state on a stack and jumps to an interrupt
1064 handler routine. The 80@var{x}86 architecture supports 256
1065 interrupts, numbered 0 through 255, each with an independent
1066 handler defined in an array called the @dfn{interrupt
1067 descriptor table} or IDT.
1069 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
1070 IDT so that each entry points to a unique entry point in
1071 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
1072 @var{NN} is the interrupt number in
1073 hexadecimal. Because the CPU doesn't give
1074 us any other way to find out the interrupt number, this entry point
1075 pushes the interrupt number on the stack. Then it jumps to
1076 @func{intr_entry}, which pushes all the registers that the processor
1077 didn't already push for us, and then calls @func{intr_handler}, which
1078 brings us back into C in @file{threads/interrupt.c}.
1080 The main job of @func{intr_handler} is to call the function
1081 registered for handling the particular interrupt. (If no
1082 function is registered, it dumps some information to the console and
1083 panics.) It also does some extra processing for external
1084 interrupts (@pxref{External Interrupt Handling}).
1086 When @func{intr_handler} returns, the assembly code in
1087 @file{threads/intr-stubs.S} restores all the CPU registers saved
1088 earlier and directs the CPU to return from the interrupt.
1090 The following types and functions are common to all
1093 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
1094 This is how an interrupt handler function must be declared. Its @var{frame}
1095 argument (see below) allows it to determine the cause of the interrupt
1096 and the state of the thread that was interrupted.
1099 @deftp {Type} {struct intr_frame}
1100 The stack frame of an interrupt handler, as saved by the CPU, the interrupt
1101 stubs, and @func{intr_entry}. Its most interesting members are described
1105 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
1106 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
1107 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
1108 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
1109 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
1110 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1111 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1112 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1113 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1114 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1115 Register values in the interrupted thread, pushed by @func{intr_entry}.
1116 The @code{esp_dummy} value isn't actually used (refer to the
1117 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1120 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1121 The interrupt vector number, ranging from 0 to 255.
1124 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1125 The ``error code'' pushed on the stack by the CPU for some internal
1129 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1130 The address of the next instruction to be executed by the interrupted
1134 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1135 The interrupted thread's stack pointer.
1138 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1139 Returns the name of the interrupt numbered @var{vec}, or
1140 @code{"unknown"} if the interrupt has no registered name.
1143 @node Internal Interrupt Handling
1144 @subsection Internal Interrupt Handling
1146 Internal interrupts are caused directly by CPU instructions executed by
1147 the running kernel thread or user process (from project 2 onward). An
1148 internal interrupt is therefore said to arise in a ``process context.''
1150 In an internal interrupt's handler, it can make sense to examine the
1151 @struct{intr_frame} passed to the interrupt handler, or even to modify
1152 it. When the interrupt returns, modifications in @struct{intr_frame}
1153 become changes to the calling thread or process's state. For example,
1154 the Pintos system call handler returns a value to the user program by
1155 modifying the saved EAX register (@pxref{System Call Details}).
1157 There are no special restrictions on what an internal interrupt
1158 handler can or can't do. Generally they should run with interrupts
1159 enabled, just like other code, and so they can be preempted by other
1160 kernel threads. Thus, they do need to synchronize with other threads
1161 on shared data and other resources (@pxref{Synchronization}).
1163 Internal interrupt handlers can be invoked recursively. For example,
1164 the system call handler might cause a page fault while attempting to
1165 read user memory. Deep recursion would risk overflowing the limited
1166 kernel stack (@pxref{struct thread}), but should be unnecessary.
1168 @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})
1169 Registers @var{handler} to be called when internal interrupt numbered
1170 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1173 If @var{level} is @code{INTR_ON}, external interrupts will be processed
1174 normally during the interrupt handler's execution, which is normally
1175 desirable. Specifying @code{INTR_OFF} will cause the CPU to disable
1176 external interrupts when it invokes the interrupt handler. The effect
1177 is slightly different from calling @func{intr_disable} inside the
1178 handler, because that leaves a window of one or more CPU instructions in
1179 which external interrupts are still enabled. This is important for the
1180 page fault handler; refer to the comments in @file{userprog/exception.c}
1183 @var{dpl} determines how the interrupt can be invoked. If @var{dpl} is
1184 0, then the interrupt can be invoked only by kernel threads. Otherwise
1185 @var{dpl} should be 3, which allows user processes to invoke the
1186 interrupt with an explicit INT instruction. The value of @var{dpl}
1187 doesn't affect user processes' ability to invoke the interrupt
1188 indirectly, e.g.@: an invalid memory reference will cause a page fault
1189 regardless of @var{dpl}.
1192 @node External Interrupt Handling
1193 @subsection External Interrupt Handling
1195 External interrupts are caused by events outside the CPU.
1196 They are asynchronous, so they can be invoked at any time that
1197 interrupts have not been disabled. We say that an external interrupt
1198 runs in an ``interrupt context.''
1200 In an external interrupt, the @struct{intr_frame} passed to the
1201 handler is not very meaningful. It describes the state of the thread
1202 or process that was interrupted, but there is no way to predict which
1203 one that is. It is possible, although rarely useful, to examine it, but
1204 modifying it is a recipe for disaster.
1206 Only one external interrupt may be processed at a time. Neither
1207 internal nor external interrupt may nest within an external interrupt
1208 handler. Thus, an external interrupt's handler must run with interrupts
1209 disabled (@pxref{Disabling Interrupts}).
1211 An external interrupt handler must not sleep or yield, which rules out
1212 calling @func{lock_acquire}, @func{thread_yield}, and many other
1213 functions. Sleeping in interrupt context would effectively put the
1214 interrupted thread to sleep, too, until the interrupt handler was again
1215 scheduled and returned. This would be unfair to the unlucky thread, and
1216 it would deadlock if the handler were waiting for the sleeping thread
1217 to, e.g., release a lock.
1219 An external interrupt handler
1220 effectively monopolizes the machine and delays all other activities.
1221 Therefore, external interrupt handlers should complete as quickly as
1222 they can. Anything that require much CPU time should instead run in a
1223 kernel thread, possibly one that the interrupt triggers using a
1224 synchronization primitive.
1226 External interrupts are controlled by a
1227 pair of devices outside the CPU called @dfn{programmable interrupt
1228 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1229 CPU's IDT, it also initializes the PICs for interrupt handling. The
1230 PICs also must be ``acknowledged'' at the end of processing for each
1231 external interrupt. @func{intr_handler} takes care of that by calling
1232 @func{pic_end_of_interrupt}, which properly signals the PICs.
1234 The following functions relate to external
1237 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1238 Registers @var{handler} to be called when external interrupt numbered
1239 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1240 purposes. The handler will run with interrupts disabled.
1243 @deftypefun bool intr_context (void)
1244 Returns true if we are running in an interrupt context, otherwise
1245 false. Mainly used in functions that might sleep
1246 or that otherwise should not be called from interrupt context, in this
1249 ASSERT (!intr_context ());
1253 @deftypefun void intr_yield_on_return (void)
1254 When called in an interrupt context, causes @func{thread_yield} to be
1255 called just before the interrupt returns. Used
1256 in the timer interrupt handler when a thread's time slice expires, to
1257 cause a new thread to be scheduled.
1260 @node Memory Allocation
1261 @section Memory Allocation
1263 Pintos contains two memory allocators, one that allocates memory in
1264 units of a page, and one that can allocate blocks of any size.
1271 @node Page Allocator
1272 @subsection Page Allocator
1274 The page allocator declared in @file{threads/palloc.h} allocates
1275 memory in units of a page. It is most often used to allocate memory
1276 one page at a time, but it can also allocate multiple contiguous pages
1279 The page allocator divides the memory it allocates into two pools,
1280 called the kernel and user pools. By default, each pool gets half of
1281 system memory above @w{1 MB}, but the division can be changed with the
1284 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1285 pool or the other. If one pool becomes empty, the other may still
1286 have free pages. The user pool should be used for allocating memory
1287 for user processes and the kernel pool for all other allocations.
1288 This will only become important starting with project 3. Until then,
1289 all allocations should be made from the kernel pool.
1291 Each pool's usage is tracked with a bitmap, one bit per page in
1292 the pool. A request to allocate @var{n} pages scans the bitmap
1293 for @var{n} consecutive bits set to
1294 false, indicating that those pages are free, and then sets those bits
1295 to true to mark them as used. This is a ``first fit'' allocation
1296 strategy (@pxref{Wilson}).
1298 The page allocator is subject to fragmentation. That is, it may not
1299 be possible to allocate @var{n} contiguous pages even though @var{n}
1300 or more pages are free, because the free pages are separated by used
1301 pages. In fact, in pathological cases it may be impossible to
1302 allocate 2 contiguous pages even though half of the pool's pages are free.
1303 Single-page requests can't fail due to fragmentation, so
1304 requests for multiple contiguous pages should be limited as much as
1307 Pages may not be allocated from interrupt context, but they may be
1310 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1311 a debugging aid (@pxref{Debugging Tips}).
1313 Page allocator types and functions are described below.
1315 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1316 @deftypefunx {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1317 Obtains and returns one page, or @var{page_cnt} contiguous pages,
1318 respectively. Returns a null pointer if the pages cannot be allocated.
1320 The @var{flags} argument may be any combination of the following flags:
1322 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1323 If the pages cannot be allocated, panic the kernel. This is only
1324 appropriate during kernel initialization. User processes
1325 should never be permitted to panic the kernel.
1328 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1329 Zero all the bytes in the allocated pages before returning them. If not
1330 set, the contents of newly allocated pages are unpredictable.
1333 @defvr {Page Allocator Flag} @code{PAL_USER}
1334 Obtain the pages from the user pool. If not set, pages are allocated
1335 from the kernel pool.
1339 @deftypefun void palloc_free_page (void *@var{page})
1340 @deftypefunx void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1341 Frees one page, or @var{page_cnt} contiguous pages, respectively,
1342 starting at @var{pages}. All of the pages must have been obtained using
1343 @func{palloc_get_page} or @func{palloc_get_multiple}.
1346 @node Block Allocator
1347 @subsection Block Allocator
1349 The block allocator, declared in @file{threads/malloc.h}, can allocate
1350 blocks of any size. It is layered on top of the page allocator
1351 described in the previous section. Blocks returned by the block
1352 allocator are obtained from the kernel pool.
1354 The block allocator uses two different strategies for allocating memory.
1355 The first strategy applies to blocks that are 1 kB or smaller
1356 (one-fourth of the page size). These allocations are rounded up to the
1357 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1358 grouped into a page used only for allocations of that size.
1360 The second strategy applies to blocks larger than 1 kB.
1361 These allocations (plus a small amount of overhead) are rounded up to
1362 the nearest page in size, and then the block allocator requests that
1363 number of contiguous pages from the page allocator.
1365 In either case, the difference between the allocation requested size
1366 and the actual block size is wasted. A real operating system would
1367 carefully tune its allocator to minimize this waste, but this is
1368 unimportant in an instructional system like Pintos.
1370 As long as a page can be obtained from the page allocator, small
1371 allocations always succeed. Most small allocations do not require a
1372 new page from the page allocator at all, because they are satisfied
1373 using part of a page already allocated. However, large allocations
1374 always require calling into the page allocator, and any allocation
1375 that needs more than one contiguous page can fail due to fragmentation,
1376 as already discussed in the previous section. Thus, you should
1377 minimize the number of large allocations in your code, especially
1378 those over approximately 4 kB each.
1380 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1381 a debugging aid (@pxref{Debugging Tips}).
1383 The block allocator may not be called from interrupt context.
1385 The block allocator functions are described below. Their interfaces are
1386 the same as the standard C library functions of the same names.
1388 @deftypefun {void *} malloc (size_t @var{size})
1389 Obtains and returns a new block, from the kernel pool, at least
1390 @var{size} bytes long. Returns a null pointer if @var{size} is zero or
1391 if memory is not available.
1394 @deftypefun {void *} calloc (size_t @var{a}, size_t @var{b})
1395 Obtains a returns a new block, from the kernel pool, at least
1396 @code{@var{a} * @var{b}} bytes long. The block's contents will be
1397 cleared to zeros. Returns a null pointer if @var{a} or @var{b} is zero
1398 or if insufficient memory is available.
1401 @deftypefun {void *} realloc (void *@var{block}, size_t @var{new_size})
1402 Attempts to resize @var{block} to @var{new_size} bytes, possibly moving
1403 it in the process. If successful, returns the new block, in which case
1404 the old block must no longer be accessed. On failure, returns a null
1405 pointer, and the old block remains valid.
1407 A call with @var{block} null is equivalent to @func{malloc}. A call
1408 with @var{new_size} zero is equivalent to @func{free}.
1411 @deftypefun void free (void *@var{block})
1412 Frees @var{block}, which must have been previously returned by
1413 @func{malloc}, @func{calloc}, or @func{realloc} (and not yet freed).
1416 @node Virtual Addresses
1417 @section Virtual Addresses
1419 A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
1420 and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
1425 +-------------------+-----------+
1426 | Page Number | Offset |
1427 +-------------------+-----------+
1432 Header @file{threads/vaddr.h} defines these functions and macros for
1433 working with virtual addresses:
1437 The bit index (0) and number of bits (12) of the offset part of a
1438 virtual address, respectively.
1442 A bit mask with the bits in the page offset set to 1, the rest set to 0
1447 The page size in bytes (4,096).
1450 @deftypefun unsigned pg_ofs (const void *@var{va})
1451 Extracts and returns the page offset in virtual address @var{va}.
1454 @deftypefun uintptr_t pg_no (const void *@var{va})
1455 Extracts and returns the page number in virtual address @var{va}.
1458 @deftypefun {void *} pg_round_down (const void *@var{va})
1459 Returns the start of the virtual page that @var{va} points within, that
1460 is, @var{va} with the page offset set to 0.
1463 @deftypefun {void *} pg_round_up (const void *@var{va})
1464 Returns @var{va} rounded up to the nearest page boundary.
1467 Virtual memory in Pintos is divided into two regions: user virtual
1468 memory and kernel virtual memory (@pxref{Virtual Memory Layout}). The
1469 boundary between them is @code{PHYS_BASE}:
1472 Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
1473 GB), but it may be changed to any multiple of @t{0x10000000} from
1474 @t{0x80000000} to @t{0xf0000000}.
1476 User virtual memory ranges from virtual address 0 up to
1477 @code{PHYS_BASE}. Kernel virtual memory occupies the rest of the
1478 virtual address space, from @code{PHYS_BASE} up to 4 GB.
1481 @deftypefun {bool} is_user_vaddr (const void *@var{va})
1482 @deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
1483 Returns true if @var{va} is a user or kernel virtual address,
1484 respectively, false otherwise.
1487 The 80@var{x}86 doesn't provide any way to directly access memory given
1488 a physical address. This ability is often necessary in an operating
1489 system kernel, so Pintos works around it by mapping kernel virtual
1490 memory one-to-one to physical memory. That is, virtual address
1491 @code{PHYS_BASE} accesses physical address 0, virtual address
1492 @code{PHYS_BASE} + @t{0x1234} accesses physical address @t{0x1234}, and
1493 so on up to the size of the machine's physical memory. Thus, adding
1494 @code{PHYS_BASE} to a physical address obtains a kernel virtual address
1495 that accesses that address; conversely, subtracting @code{PHYS_BASE}
1496 from a kernel virtual address obtains the corresponding physical
1497 address. Header @file{threads/vaddr.h} provides a pair of functions to
1498 do these translations:
1500 @deftypefun {void *} ptov (uintptr_t @var{pa})
1501 Returns the kernel virtual address corresponding to physical address
1502 @var{pa}, which should be between 0 and the number of bytes of physical
1506 @deftypefun {uintptr_t} vtop (void *@var{va})
1507 Returns the physical address corresponding to @var{va}, which must be a
1508 kernel virtual address.
1514 The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
1515 hardware page table, also called a ``page directory'' by Intel processor
1516 documentation. The page table interface uses a @code{uint32_t *} to
1517 represent a page table because this is convenient for accessing their
1520 The sections below describe the page table interface and internals.
1523 * Page Table Creation Destruction Activation::
1524 * Page Tables Inspection and Updates::
1525 * Page Table Accessed and Dirty Bits::
1526 * Page Table Details::
1529 @node Page Table Creation Destruction Activation
1530 @subsection Creation, Destruction, and Activation
1532 These functions create, destroy, and activate page tables. The base
1533 Pintos code already calls these functions where necessary, so it should
1534 not be necessary to call them yourself.
1536 @deftypefun {uint32_t *} pagedir_create (void)
1537 Creates and returns a new page table. The new page table contains
1538 Pintos's normal kernel virtual page mappings, but no user virtual
1541 Returns a null pointer if memory cannot be obtained.
1544 @deftypefun void pagedir_destroy (uint32_t *@var{pd})
1545 Frees all of the resources held by @var{pd}, including the page table
1546 itself and the frames that it maps.
1549 @deftypefun void pagedir_activate (uint32_t *@var{pd})
1550 Activates @var{pd}. The active page table is the one used by the CPU to
1551 translate memory references.
1554 @node Page Tables Inspection and Updates
1555 @subsection Inspection and Updates
1557 These functions examine or update the mappings from pages to frames
1558 encapsulated by a page table. They work on both active and inactive
1559 page tables (that is, those for running and suspended processes),
1560 flushing the TLB as necessary.
1562 @deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
1563 Adds to @var{pd} a mapping from user page @var{upage} to the frame identified
1564 by kernel virtual address @var{kpage}. If @var{writable} is true, the
1565 page is mapped read/write; otherwise, it is mapped read-only.
1567 User page @var{upage} must not already be mapped in @var{pd}.
1569 Kernel page @var{kpage} should be a kernel virtual address obtained from
1570 the user pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why
1573 Returns true if successful, false on failure. Failure will occur if
1574 additional memory required for the page table cannot be obtained.
1577 @deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
1578 Looks up the frame mapped to @var{uaddr} in @var{pd}. Returns the
1579 kernel virtual address for that frame, if @var{uaddr} is mapped, or a
1580 null pointer if it is not.
1583 @deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{page})
1584 Marks @var{page} ``not present'' in @var{pd}. Later accesses to
1585 the page will fault.
1587 Other bits in the page table for @var{page} are preserved, permitting
1588 the accessed and dirty bits (see the next section) to be checked.
1590 This function has no effect if @var{page} is not mapped.
1593 @node Page Table Accessed and Dirty Bits
1594 @subsection Accessed and Dirty Bits
1596 80@var{x}86 hardware provides some assistance for implementing page
1597 replacement algorithms, through a pair of bits in the page table entry
1598 (PTE) for each page. On any read or write to a page, the CPU sets the
1599 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
1600 sets the @dfn{dirty bit} to 1. The CPU never resets these bits to 0,
1601 but the OS may do so.
1603 Proper interpretation of these bits requires understanding of
1604 @dfn{aliases}, that is, two (or more) pages that refer to the same
1605 frame. When an aliased frame is accessed, the accessed and dirty bits
1606 are updated in only one page table entry (the one for the page used for
1607 access). The accessed and dirty bits for the other aliases are not
1610 @xref{Accessed and Dirty Bits}, on applying these bits in implementing
1611 page replacement algorithms.
1613 @deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
1614 @deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
1615 Returns true if page directory @var{pd} contains a page table entry for
1616 @var{page} that is marked dirty (or accessed). Otherwise,
1620 @deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1621 @deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1622 If page directory @var{pd} has a page table entry for @var{page}, then
1623 its dirty (or accessed) bit is set to @var{value}.
1626 @node Page Table Details
1627 @subsection Page Table Details
1629 The functions provided with Pintos are sufficient to implement the
1630 projects. However, you may still find it worthwhile to understand the
1631 hardware page table format, so we'll go into a little detail in this
1635 * Page Table Structure::
1636 * Page Table Entry Format::
1637 * Page Directory Entry Format::
1640 @node Page Table Structure
1641 @subsubsection Structure
1643 The top-level paging data structure is a page called the ``page
1644 directory'' (PD) arranged as an array of 1,024 32-bit page directory
1645 entries (PDEs), each of which represents 4 MB of virtual memory. Each
1646 PDE may point to the physical address of another page called a
1647 ``page table'' (PT) arranged, similarly, as an array of 1,024
1648 32-bit page table entries (PTEs), each of which translates a single 4
1649 kB virtual page to a physical page.
1651 Translation of a virtual address into a physical address follows
1652 the three-step process illustrated in the diagram
1653 below:@footnote{Actually, virtual to physical translation on the
1654 80@var{x}86 architecture occurs via an intermediate ``linear
1655 address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
1656 so that linear and virtual addresses are one and the same. Thus, you
1657 can effectively ignore this CPU feature.}
1661 The most-significant 10 bits of the virtual address (bits 22@dots{}31)
1662 index the page directory. If the PDE is marked ``present,'' the
1663 physical address of a page table is read from the PDE thus obtained.
1664 If the PDE is marked ``not present'' then a page fault occurs.
1667 The next 10 bits of the virtual address (bits 12@dots{}21) index
1668 the page table. If the PTE is marked ``present,'' the physical
1669 address of a data page is read from the PTE thus obtained. If the PTE
1670 is marked ``not present'' then a page fault occurs.
1673 The least-significant 12 bits of the virtual address (bits 0@dots{}11)
1674 are added to the data page's physical base address, yielding the final
1681 +----------------------+----------------------+----------------------+
1682 | Page Directory Index | Page Table Index | Page Offset |
1683 +----------------------+----------------------+----------------------+
1685 _______/ _______/ _____/
1687 / Page Directory / Page Table / Data Page
1688 / .____________. / .____________. / .____________.
1689 |1,023|____________| |1,023|____________| | |____________|
1690 |1,022|____________| |1,022|____________| | |____________|
1691 |1,021|____________| |1,021|____________| \__\|____________|
1692 |1,020|____________| |1,020|____________| /|____________|
1694 | | | \____\| |_ | |
1695 | | . | /| . | \ | . |
1696 \____\| . |_ | . | | | . |
1697 /| . | \ | . | | | . |
1698 | . | | | . | | | . |
1700 |____________| | |____________| | |____________|
1701 4|____________| | 4|____________| | |____________|
1702 3|____________| | 3|____________| | |____________|
1703 2|____________| | 2|____________| | |____________|
1704 1|____________| | 1|____________| | |____________|
1705 0|____________| \__\0|____________| \____\|____________|
1710 Pintos provides some macros and functions that are useful for working
1711 with raw page tables:
1715 The starting bit index (12) and number of bits (10), respectively, in a
1720 A bit mask with the bits in the page table index set to 1 and the rest
1721 set to 0 (@t{0x3ff000}).
1725 The number of bytes of virtual address space that a single page table
1726 page covers (4,194,304 bytes, or 4 MB).
1731 The starting bit index (22) and number of bits (10), respectively, in a
1732 page directory index.
1736 A bit mask with the bits in the page directory index set to 1 and other
1737 bits set to 0 (@t{0xffc00000}).
1740 @deftypefun uintptr_t pd_no (const void *@var{va})
1741 @deftypefunx uintptr_t pt_no (const void *@var{va})
1742 Returns the page directory index or page table index, respectively, for
1743 virtual address @var{va}. These functions are defined in
1744 @file{threads/pte.h}.
1747 @deftypefun unsigned pg_ofs (const void *@var{va})
1748 Returns the page offset for virtual address @var{va}. This function is
1749 defined in @file{threads/vaddr.h}.
1752 @node Page Table Entry Format
1753 @subsubsection Page Table Entry Format
1755 You do not need to understand the PTE format to do the Pintos
1756 projects, unless you wish to incorporate the page table into your
1757 supplemental page table (@pxref{Managing the Supplemental Page Table}).
1759 The actual format of a page table entry is summarized below. For
1760 complete information, refer to section 3.7, ``Page Translation Using
1761 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
1765 31 12 11 9 6 5 2 1 0
1766 +---------------------------------------+----+----+-+-+---+-+-+-+
1767 | Physical Address | AVL| |D|A| |U|W|P|
1768 +---------------------------------------+----+----+-+-+---+-+-+-+
1772 Some more information on each bit is given below. The names are
1773 @file{threads/pte.h} macros that represent the bits' values:
1776 Bit 0, the ``present'' bit. When this bit is 1, the
1777 other bits are interpreted as described below. When this bit is 0, any
1778 attempt to access the page will page fault. The remaining bits are then
1779 not used by the CPU and may be used by the OS for any purpose.
1783 Bit 1, the ``read/write'' bit. When it is 1, the page
1784 is writable. When it is 0, write attempts will page fault.
1788 Bit 2, the ``user/supervisor'' bit. When it is 1, user
1789 processes may access the page. When it is 0, only the kernel may access
1790 the page (user accesses will page fault).
1792 Pintos clears this bit in PTEs for kernel virtual memory, to prevent
1793 user processes from accessing them.
1797 Bit 5, the ``accessed'' bit. @xref{Page Table Accessed
1802 Bit 6, the ``dirty'' bit. @xref{Page Table Accessed and
1807 Bits 9@dots{}11, available for operating system use.
1808 Pintos, as provided, does not use them and sets them to 0.
1812 Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
1813 The low 12 bits of the frame's address are always 0.
1816 Other bits are either reserved or uninteresting in a Pintos context and
1817 should be set to@tie{}0.
1819 Header @file{threads/pte.h} defines three functions for working with
1822 @deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
1823 Returns a page table entry that points to @var{page}, which should be a
1824 kernel virtual address. The PTE's present bit will be set. It will be
1825 marked for kernel-only access. If @var{writable} is true, the PTE will
1826 also be marked read/write; otherwise, it will be read-only.
1829 @deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
1830 Returns a page table entry that points to @var{page}, which should be
1831 the kernel virtual address of a frame in the user pool (@pxref{Why
1832 PAL_USER?}). The PTE's present bit will be set and it will be marked to
1833 allow user-mode access. If @var{writable} is true, the PTE will also be
1834 marked read/write; otherwise, it will be read-only.
1837 @deftypefun {void *} pte_get_page (uint32_t @var{pte})
1838 Returns the kernel virtual address for the frame that @var{pte} points
1839 to. The @var{pte} may be present or not-present; if it is not-present
1840 then the pointer returned is only meaningful if the address bits in the PTE
1841 actually represent a physical address.
1844 @node Page Directory Entry Format
1845 @subsubsection Page Directory Entry Format
1847 Page directory entries have the same format as PTEs, except that the
1848 physical address points to a page table page instead of a frame. Header
1849 @file{threads/pte.h} defines two functions for working with page
1852 @deftypefun uint32_t pde_create (uint32_t *@var{pt})
1853 Returns a page directory that points to @var{page}, which should be the
1854 kernel virtual address of a page table page. The PDE's present bit will
1855 be set, it will be marked to allow user-mode access, and it will be
1859 @deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
1860 Returns the kernel virtual address for the page table page that
1861 @var{pde}, which must be marked present, points to.
1867 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1868 To use it you will need to include its header file,
1869 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}.
1870 No code provided with Pintos uses the hash table, which means that you
1871 are free to use it as is, modify its implementation for your own
1872 purposes, or ignore it, as you wish.
1874 Most implementations of the virtual memory project use a hash table to
1875 translate pages to frames. You may find other uses for hash tables as
1880 * Basic Hash Functions::
1881 * Hash Search Functions::
1882 * Hash Iteration Functions::
1883 * Hash Table Example::
1884 * Hash Auxiliary Data::
1885 * Hash Synchronization::
1888 @node Hash Data Types
1889 @subsection Data Types
1891 A hash table is represented by @struct{hash}.
1893 @deftp {Type} {struct hash}
1894 Represents an entire hash table. The actual members of @struct{hash}
1895 are ``opaque.'' That is, code that uses a hash table should not access
1896 @struct{hash} members directly, nor should it need to. Instead, use
1897 hash table functions and macros.
1900 The hash table operates on elements of type @struct{hash_elem}.
1902 @deftp {Type} {struct hash_elem}
1903 Embed a @struct{hash_elem} member in the structure you want to include
1904 in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
1905 All functions for operating on hash table elements actually take and
1906 return pointers to @struct{hash_elem}, not pointers to your hash table's
1910 You will often need to obtain a @struct{hash_elem} given a real element
1911 of the hash table, and vice versa. Given a real element of the hash
1912 table, you may use the @samp{&} operator to obtain a pointer to its
1913 @struct{hash_elem}. Use the @code{hash_entry()} macro to go the other
1916 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1917 Returns a pointer to the structure that @var{elem}, a pointer to a
1918 @struct{hash_elem}, is embedded within. You must provide @var{type},
1919 the name of the structure that @var{elem} is inside, and @var{member},
1920 the name of the member in @var{type} that @var{elem} points to.
1922 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1923 that points to a @struct{thread} member (of type @struct{hash_elem})
1924 named @code{h_elem}. Then, @code{hash_entry@tie{}(h, struct thread, h_elem)}
1925 yields the address of the @struct{thread} that @code{h} points within.
1928 @xref{Hash Table Example}, for an example.
1930 Each hash table element must contain a key, that is, data that
1931 identifies and distinguishes elements, which must be unique
1932 among elements in the hash table. (Elements may
1933 also contain non-key data that need not be unique.) While an element is
1934 in a hash table, its key data must not be changed. Instead, if need be,
1935 remove the element from the hash table, modify its key, then reinsert
1938 For each hash table, you must write two functions that act on keys: a
1939 hash function and a comparison function. These functions must match the
1940 following prototypes:
1942 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1943 Returns a hash of @var{element}'s data, as a value anywhere in the range
1944 of @code{unsigned int}. The hash of an element should be a
1945 pseudo-random function of the element's key. It must not depend on
1946 non-key data in the element or on any non-constant data other than the
1947 key. Pintos provides the following functions as a suitable basis for
1950 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1951 Returns a hash of the @var{size} bytes starting at @var{buf}. The
1952 implementation is the general-purpose
1953 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1954 hash} for 32-bit words.
1957 @deftypefun unsigned hash_string (const char *@var{s})
1958 Returns a hash of null-terminated string @var{s}.
1961 @deftypefun unsigned hash_int (int @var{i})
1962 Returns a hash of integer @var{i}.
1965 If your key is a single piece of data of an appropriate type, it is
1966 sensible for your hash function to directly return the output of one of
1967 these functions. For multiple pieces of data, you may wish to combine
1968 the output of more than one call to them using, e.g., the @samp{^}
1970 operator. Finally, you may entirely ignore these functions and write
1971 your own hash function from scratch, but remember that your goal is to
1972 build an operating system kernel, not to design a hash function.
1974 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1977 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1978 Compares the keys stored in elements @var{a} and @var{b}. Returns
1979 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1980 or equal to @var{b}.
1982 If two elements compare equal, then they must hash to equal values.
1984 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1987 @xref{Hash Table Example}, for hash and comparison function examples.
1989 A few functions accept a pointer to a third kind of
1990 function as an argument:
1992 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1993 Performs some kind of action, chosen by the caller, on @var{element}.
1995 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1998 @node Basic Hash Functions
1999 @subsection Basic Functions
2001 These functions create, destroy, and inspect hash tables.
2003 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
2004 Initializes @var{hash} as a hash table with @var{hash_func} as hash
2005 function, @var{less_func} as comparison function, and @var{aux} as
2007 Returns true if successful, false on failure. @func{hash_init} calls
2008 @func{malloc} and fails if memory cannot be allocated.
2010 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
2011 most often a null pointer.
2014 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
2015 Removes all the elements from @var{hash}, which must have been
2016 previously initialized with @func{hash_init}.
2018 If @var{action} is non-null, then it is called once for each element in
2019 the hash table, which gives the caller an opportunity to deallocate any
2020 memory or other resources used by the element. For example, if the hash
2021 table elements are dynamically allocated using @func{malloc}, then
2022 @var{action} could @func{free} the element. This is safe because
2023 @func{hash_clear} will not access the memory in a given hash element
2024 after calling @var{action} on it. However, @var{action} must not call
2025 any function that may modify the hash table, such as @func{hash_insert}
2026 or @func{hash_delete}.
2029 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
2030 If @var{action} is non-null, calls it for each element in the hash, with
2031 the same semantics as a call to @func{hash_clear}. Then, frees the
2032 memory held by @var{hash}. Afterward, @var{hash} must not be passed to
2033 any hash table function, absent an intervening call to @func{hash_init}.
2036 @deftypefun size_t hash_size (struct hash *@var{hash})
2037 Returns the number of elements currently stored in @var{hash}.
2040 @deftypefun bool hash_empty (struct hash *@var{hash})
2041 Returns true if @var{hash} currently contains no elements,
2042 false if @var{hash} contains at least one element.
2045 @node Hash Search Functions
2046 @subsection Search Functions
2048 Each of these functions searches a hash table for an element that
2049 compares equal to one provided. Based on the success of the search,
2050 they perform some action, such as inserting a new element into the hash
2051 table, or simply return the result of the search.
2053 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
2054 Searches @var{hash} for an element equal to @var{element}. If none is
2055 found, inserts @var{element} into @var{hash} and returns a null pointer.
2056 If the table already contains an element equal to @var{element}, it is
2057 returned without modifying @var{hash}.
2060 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
2061 Inserts @var{element} into @var{hash}. Any element equal to
2062 @var{element} already in @var{hash} is removed. Returns the element
2063 removed, or a null pointer if @var{hash} did not contain an element
2064 equal to @var{element}.
2066 The caller is responsible for deallocating any resources associated with
2067 the returned element, as appropriate. For example, if the hash table
2068 elements are dynamically allocated using @func{malloc}, then the caller
2069 must @func{free} the element after it is no longer needed.
2072 The element passed to the following functions is only used for hashing
2073 and comparison purposes. It is never actually inserted into the hash
2074 table. Thus, only key data in the element needs to be initialized, and
2075 other data in the element will not be used. It often makes sense to
2076 declare an instance of the element type as a local variable, initialize
2077 the key data, and then pass the address of its @struct{hash_elem} to
2078 @func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
2079 an example. (Large structures should not be
2080 allocated as local variables. @xref{struct thread}, for more
2083 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
2084 Searches @var{hash} for an element equal to @var{element}. Returns the
2085 element found, if any, or a null pointer otherwise.
2088 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
2089 Searches @var{hash} for an element equal to @var{element}. If one is
2090 found, it is removed from @var{hash} and returned. Otherwise, a null
2091 pointer is returned and @var{hash} is unchanged.
2093 The caller is responsible for deallocating any resources associated with
2094 the returned element, as appropriate. For example, if the hash table
2095 elements are dynamically allocated using @func{malloc}, then the caller
2096 must @func{free} the element after it is no longer needed.
2099 @node Hash Iteration Functions
2100 @subsection Iteration Functions
2102 These functions allow iterating through the elements in a hash table.
2103 Two interfaces are supplied. The first requires writing and supplying a
2104 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
2106 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
2107 Calls @var{action} once for each element in @var{hash}, in arbitrary
2108 order. @var{action} must not call any function that may modify the hash
2109 table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
2110 must not modify key data in elements, although it may modify any other
2114 The second interface is based on an ``iterator'' data type.
2115 Idiomatically, iterators are used as follows:
2118 struct hash_iterator i;
2121 while (hash_next (&i))
2123 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
2124 @r{@dots{}do something with @i{f}@dots{}}
2128 @deftp {Type} {struct hash_iterator}
2129 Represents a position within a hash table. Calling any function that
2130 may modify a hash table, such as @func{hash_insert} or
2131 @func{hash_delete}, invalidates all iterators within that hash table.
2133 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
2136 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
2137 Initializes @var{iterator} to just before the first element in
2141 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
2142 Advances @var{iterator} to the next element in @var{hash}, and returns
2143 that element. Returns a null pointer if no elements remain. After
2144 @func{hash_next} returns null for @var{iterator}, calling it again
2145 yields undefined behavior.
2148 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
2149 Returns the value most recently returned by @func{hash_next} for
2150 @var{iterator}. Yields undefined behavior after @func{hash_first} has
2151 been called on @var{iterator} but before @func{hash_next} has been
2152 called for the first time.
2155 @node Hash Table Example
2156 @subsection Hash Table Example
2158 Suppose you have a structure, called @struct{page}, that you
2159 want to put into a hash table. First, define @struct{page} to include a
2160 @struct{hash_elem} member:
2165 struct hash_elem hash_elem; /* @r{Hash table element.} */
2166 void *addr; /* @r{Virtual address.} */
2167 /* @r{@dots{}other members@dots{}} */
2171 We write a hash function and a comparison function using @var{addr} as
2172 the key. A pointer can be hashed based on its bytes, and the @samp{<}
2173 operator works fine for comparing pointers:
2176 /* @r{Returns a hash value for page @var{p}.} */
2178 page_hash (const struct hash_elem *p_, void *aux UNUSED)
2180 const struct page *p = hash_entry (p_, struct page, hash_elem);
2181 return hash_bytes (&p->addr, sizeof p->addr);
2184 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
2186 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2189 const struct page *a = hash_entry (a_, struct page, hash_elem);
2190 const struct page *b = hash_entry (b_, struct page, hash_elem);
2192 return a->addr < b->addr;
2197 (The use of @code{UNUSED} in these functions' prototypes suppresses a
2198 warning that @var{aux} is unused. @xref{Function and Parameter
2199 Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
2200 Data}, for an explanation of @var{aux}.)
2202 Then, we can create a hash table like this:
2207 hash_init (&pages, page_hash, page_less, NULL);
2210 Now we can manipulate the hash table we've created. If @code{@var{p}}
2211 is a pointer to a @struct{page}, we can insert it into the hash table
2215 hash_insert (&pages, &p->hash_elem);
2218 @noindent If there's a chance that @var{pages} might already contain a
2219 page with the same @var{addr}, then we should check @func{hash_insert}'s
2222 To search for an element in the hash table, use @func{hash_find}. This
2223 takes a little setup, because @func{hash_find} takes an element to
2224 compare against. Here's a function that will find and return a page
2225 based on a virtual address, assuming that @var{pages} is defined at file
2229 /* @r{Returns the page containing the given virtual @var{address},}
2230 @r{or a null pointer if no such page exists.} */
2232 page_lookup (const void *address)
2235 struct hash_elem *e;
2238 e = hash_find (&pages, &p.hash_elem);
2239 return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
2244 @struct{page} is allocated as a local variable here on the assumption
2245 that it is fairly small. Large structures should not be allocated as
2246 local variables. @xref{struct thread}, for more information.
2248 A similar function could delete a page by address using
2251 @node Hash Auxiliary Data
2252 @subsection Auxiliary Data
2254 In simple cases like the example above, there's no need for the
2255 @var{aux} parameters. In these cases, just pass a null pointer to
2256 @func{hash_init} for @var{aux} and ignore the values passed to the hash
2257 function and comparison functions. (You'll get a compiler warning if
2258 you don't use the @var{aux} parameter, but you can turn that off with
2259 the @code{UNUSED} macro, as shown in the example, or you can just ignore
2262 @var{aux} is useful when you have some property of the data in the
2263 hash table is both constant and needed for hashing or comparison,
2264 but not stored in the data items themselves. For example, if
2265 the items in a hash table are fixed-length strings, but the items
2266 themselves don't indicate what that fixed length is, you could pass
2267 the length as an @var{aux} parameter.
2269 @node Hash Synchronization
2270 @subsection Synchronization
2272 The hash table does not do any internal synchronization. It is the
2273 caller's responsibility to synchronize calls to hash table functions.
2274 In general, any number of functions that examine but do not modify the
2275 hash table, such as @func{hash_find} or @func{hash_next}, may execute
2276 simultaneously. However, these function cannot safely execute at the
2277 same time as any function that may modify a given hash table, such as
2278 @func{hash_insert} or @func{hash_delete}, nor may more than one function
2279 that can modify a given hash table execute safely at once.
2281 It is also the caller's responsibility to synchronize access to data in
2282 hash table elements. How to synchronize access to this data depends on
2283 how it is designed and organized, as with any other data structure.