2 @appendix Reference Guide
4 This chapter is a reference for the Pintos code. It covers the
5 entire code base, but you'll only be using Pintos one part at a time,
6 so you may find that you want to read each part as you work on the
7 project where it becomes important.
9 (Actually, the reference guide is currently incomplete.)
11 We recommend using ``tags'' to follow along with references to function
12 and variable names (@pxref{Tags}).
18 * Interrupt Handling::
28 This section covers the Pintos loader and basic kernel
33 * Kernel Initialization::
37 @subsection The Loader
39 The first part of Pintos that runs is the loader, in
40 @file{threads/loader.S}. The PC BIOS loads the loader into memory.
41 The loader, in turn, is responsible for initializing the CPU, loading
42 the rest of Pintos into memory, and then jumping to its start. It's
43 not important to understand exactly what the loader does, but if
44 you're interested, read on. You should probably read along with the
45 loader's source. You should also understand the basics of the
46 80@var{x}86 architecture as described by chapter 3, ``Basic Execution
47 Environment,'' of @bibref{IA32-v1}.
49 Because the PC BIOS loads the loader, the loader has to play by the
50 BIOS's rules. In particular, the BIOS only loads 512 bytes (one disk
51 sector) into memory. This is a severe restriction and it means that,
52 practically speaking, the loader has to be written in assembly
55 The Pintos loader first initializes the CPU. The first important part of
56 this is to enable the A20 line, that is, the CPU's address line
57 numbered 20. For historical reasons, PCs boot with this address
58 line fixed at 0, which means that attempts to access memory beyond the
59 first 1 MB (2 raised to the 20th power) will fail. Pintos wants to
60 access more memory than this, so we have to enable it.
62 Next, the loader asks the BIOS for the PC's memory size. Again for
63 historical reasons, the function that we call in the BIOS to do this
64 can only detect up to 64 MB of RAM, so that's the practical limit that
65 Pintos can support. The memory size is stashed away in a location in
66 the loader that the kernel can read after it boots.
68 Third, the loader creates a basic page table. This page table maps
69 the 64 MB at the base of virtual memory (starting at virtual address
70 0) directly to the identical physical addresses. It also maps the
71 same physical memory starting at virtual address
72 @code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB). The
73 Pintos kernel only wants the latter mapping, but there's a
74 chicken-and-egg problem if we don't include the former: our current
75 virtual address is roughly @t{0x7c00}, the location where the BIOS
76 loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
77 page table, but if we turn on the page table without jumping there,
78 then we've just pulled the rug out from under ourselves.
80 After the page table is initialized, we load the CPU's control
81 registers to turn on protected mode and paging, and then we set up the
82 segment registers. We aren't yet equipped to handle interrupts in
83 protected mode, so we disable interrupts.
85 Finally it's time to load the kernel from disk. We use a simple but
86 inflexible method to do this: we program the IDE disk
87 controller directly. We assume that the kernel is stored starting
88 from the second sector of the first IDE disk (the first sector normally
89 contains the boot loader). We also assume that the BIOS has
90 already set up the IDE controller for us. We read
91 @code{KERNEL_LOAD_PAGES} pages of data (4 kB per page) from the disk directly
92 into virtual memory, starting @code{LOADER_KERN_BASE} bytes past
93 @code{LOADER_PHYS_BASE}, which by default means that we load the
94 kernel starting 1 MB into physical memory.
96 Then we jump to the start of the compiled kernel image. Using the
97 ``linker script'' in @file{threads/kernel.lds.S}, the kernel has
98 arranged to begin with the assembly module
99 @file{threads/start.S}. This assembly module just calls
100 @func{main}, which never returns.
102 There's one more trick: the Pintos kernel command line
103 is in stored the boot loader. The @command{pintos} program actually
104 modifies a copy of the boot loader on disk each time it runs the kernel,
106 in whatever command line arguments the user supplies to the kernel,
107 and then the kernel at boot time reads those arguments out of the boot
108 loader in memory. This is not an elegant solution, but it is simple
111 @node Kernel Initialization
112 @subsection Kernel Initialization
114 The kernel proper starts with the @func{main} function. The
115 @func{main} function is written in C, as will be most of the code we
116 encounter in Pintos from here on out.
118 When @func{main} starts, the system is in a pretty raw state. We're
119 in 32-bit protected mode with paging enabled, but hardly anything else is
120 ready. Thus, the @func{main} function consists primarily of calls
121 into other Pintos modules' initialization functions.
122 These are usually named @func{@var{module}_init}, where
123 @var{module} is the module's name, @file{@var{module}.c} is the
124 module's source code, and @file{@var{module}.h} is the module's
127 First we initialize kernel RAM in @func{ram_init}. The first step
128 is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
129 segment that should be initialized to all zeros. In most C
130 implementations, whenever you
131 declare a variable outside a function without providing an
132 initializer, that variable goes into the BSS. Because it's all zeros, the
133 BSS isn't stored in the image that the loader brought into memory. We
134 just use @func{memset} to zero it out. The other task of
135 @func{ram_init} is to read out the machine's memory size from where
136 the loader stored it and put it into the @code{ram_pages} variable for
139 Next, @func{thread_init} initializes the thread system. We will defer
140 full discussion to our discussion of Pintos threads below. It is
141 called so early in initialization because the console, initialized
142 just afterward, tries to use locks, and locks in turn require there to be a
145 Then we initialize the console so that @func{printf} will work.
146 @func{main} calls @func{vga_init}, which initializes the VGA text
147 display and clears the screen. It also calls @func{serial_init_poll}
148 to initialize the first serial port in ``polling mode,'' that is,
149 where the kernel busy-waits for the port to be ready for each
150 character to be output. (We use polling mode until we're ready to enable
151 interrupts, later.) Finally we initialize the console device and
152 print a startup message to the console.
154 @func{main} calls @func{read_command_line} to break the kernel command
155 line into arguments, then @func{parse_options} to read any options at
156 the beginning of the command line. (Actions specified on the
157 command line execute later.)
159 @func{main} calls @func{random_init} to initialize the kernel random
160 number generator. If the user specified @option{-rs} on the
161 @command{pintos} command line, @func{parse_options} already did
162 this, but calling it a second time is harmless.
164 The next block of functions we call initialize the kernel's memory
165 system. @func{palloc_init} sets up the kernel page allocator, which
166 doles out memory one or more pages at a time (@pxref{Page Allocator}).
167 @func{malloc_init} sets
168 up the allocator that handles allocations of arbitrary-size blocks of
169 memory (@pxref{Block Allocator}).
170 @func{paging_init} sets up a page table for the kernel (@pxref{Page
173 In projects 2 and later, @func{main} also calls @func{tss_init} and
176 The next set of calls initializes the interrupt system.
177 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
178 (IDT) to ready it for interrupt handling (@pxref{Interrupt
179 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
180 handling timer interrupts and keyboard interrupts, respectively. In
181 projects 2 and later, we also prepare to handle interrupts caused by
182 user programs using @func{exception_init} and @func{syscall_init}.
184 Now that interrupts are set up, we can start the scheduler
185 with @func{thread_start}, which creates the idle thread and enables
187 With interrupts enabled, interrupt-driven serial port I/O becomes
189 @func{serial_init_queue} to switch to that mode. Finally,
190 @func{timer_calibrate} calibrates the timer for accurate short delays.
192 If the file system is compiled in, as it will starting in project 2, we
193 initialize the disks with @func{disk_init}, then the
194 file system with @func{filesys_init}.
196 Boot is complete, so we print a message.
198 Function @func{run_actions} now parses and executes actions specified on
199 the kernel command line, such as @command{run} to run a test (in project
200 1) or a user program (in later projects).
202 Finally, if @option{-q} was specified on the kernel command line, we
203 call @func{power_off} to terminate the machine simulator. Otherwise,
204 @func{main} calls @func{thread_exit}, which allows any other running
205 threads to continue running.
217 @subsection @code{struct thread}
219 The main Pintos data structure for threads is @struct{thread},
220 declared in @file{threads/thread.h}.
222 @deftp {Structure} {struct thread}
223 Represents a thread or a user process. In the projects, you will have
224 to add your own members to @struct{thread}. You may also change or
225 delete the definitions of existing members.
227 Every @struct{thread} occupies the beginning of its own page of
228 memory. The rest of the page is used for the thread's stack, which
229 grows downward from the end of the page. It looks like this:
233 4 kB +---------------------------------+
247 sizeof (struct thread) +---------------------------------+
253 0 kB +---------------------------------+
257 This has two consequences. First, @struct{thread} must not be allowed
258 to grow too big. If it does, then there will not be enough room for the
259 kernel stack. The base @struct{thread} is only a few bytes in size. It
260 probably should stay well under 1 kB.
262 Second, kernel stacks must not be allowed to grow too large. If a stack
263 overflows, it will corrupt the thread state. Thus, kernel functions
264 should not allocate large structures or arrays as non-static local
265 variables. Use dynamic allocation with @func{malloc} or
266 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
269 @deftypecv {Member} {@struct{thread}} {tid_t} tid
270 The thread's thread identifier or @dfn{tid}. Every thread must have a
271 tid that is unique over the entire lifetime of the kernel. By
272 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
273 thread receives the numerically next higher tid, starting from 1 for
274 the initial process. You can change the type and the numbering scheme
278 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
279 @anchor{Thread States}
280 The thread's state, one of the following:
282 @defvr {Thread State} @code{THREAD_RUNNING}
283 The thread is running. Exactly one thread is running at a given time.
284 @func{thread_current} returns the running thread.
287 @defvr {Thread State} @code{THREAD_READY}
288 The thread is ready to run, but it's not running right now. The
289 thread could be selected to run the next time the scheduler is
290 invoked. Ready threads are kept in a doubly linked list called
294 @defvr {Thread State} @code{THREAD_BLOCKED}
295 The thread is waiting for something, e.g.@: a lock to become
296 available, an interrupt to be invoked. The thread won't be scheduled
297 again until it transitions to the @code{THREAD_READY} state with a
298 call to @func{thread_unblock}. This is most conveniently done
299 indirectly, using one of the Pintos synchronization primitives that
300 block and unblock threads automatically (@pxref{Synchronization}).
302 There is no @i{a priori} way to tell what a blocked thread is waiting
303 for, but a backtrace can help (@pxref{Backtraces}).
306 @defvr {Thread State} @code{THREAD_DYING}
307 The thread will be destroyed by the scheduler after switching to the
312 @deftypecv {Member} {@struct{thread}} {char} name[16]
313 The thread's name as a string, or at least the first few characters of
317 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
318 Every thread has its own stack to keep track of its state. When the
319 thread is running, the CPU's stack pointer register tracks the top of
320 the stack and this member is unused. But when the CPU switches to
321 another thread, this member saves the thread's stack pointer. No
322 other members are needed to save the thread's registers, because the
323 other registers that must be saved are saved on the stack.
325 When an interrupt occurs, whether in the kernel or a user program, an
326 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
327 in a user program, the @struct{intr_frame} is always at the very top of
328 the page. @xref{Interrupt Handling}, for more information.
331 @deftypecv {Member} {@struct{thread}} {int} priority
332 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
333 (63). Lower numbers correspond to lower priorities, so that
334 priority 0 is the lowest priority and priority 63 is the highest.
335 Pintos as provided ignores thread priorities, but you will implement
336 priority scheduling in project 1 (@pxref{Priority Scheduling}).
339 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
340 A ``list element'' used to put the thread into doubly linked lists,
341 either @code{ready_list} (the list of threads ready to run) or a list of
342 threads waiting on a semaphore in @func{sema_down}. It can do double
343 duty because a thread waiting on a semaphore is not ready, and vice
347 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
348 Only present in project 2 and later. @xref{Page Tables}.
351 @deftypecv {Member} {@struct{thread}} {unsigned} magic
352 Always set to @code{THREAD_MAGIC}, which is just an arbitrary number defined
353 in @file{threads/thread.c}, and used to detect stack overflow.
354 @func{thread_current} checks that the @code{magic} member of the running
355 thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
356 tends to change this value, triggering the assertion. For greatest
357 benefit, as you add members to @struct{thread}, leave @code{magic} at
361 @node Thread Functions
362 @subsection Thread Functions
364 @file{threads/thread.c} implements several public functions for thread
365 support. Let's take a look at the most useful:
367 @deftypefun void thread_init (void)
368 Called by @func{main} to initialize the thread system. Its main
369 purpose is to create a @struct{thread} for Pintos's initial thread.
370 This is possible because the Pintos loader puts the initial
371 thread's stack at the top of a page, in the same position as any other
374 Before @func{thread_init} runs,
375 @func{thread_current} will fail because the running thread's
376 @code{magic} value is incorrect. Lots of functions call
377 @func{thread_current} directly or indirectly, including
378 @func{lock_acquire} for locking a lock, so @func{thread_init} is
379 called early in Pintos initialization.
382 @deftypefun void thread_start (void)
383 Called by @func{main} to start the scheduler. Creates the idle
384 thread, that is, the thread that is scheduled when no other thread is
385 ready. Then enables interrupts, which as a side effect enables the
386 scheduler because the scheduler runs on return from the timer interrupt, using
387 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
390 @deftypefun void thread_tick (void)
391 Called by the timer interrupt at each timer tick. It keeps track of
392 thread statistics and triggers the scheduler when a time slice expires.
395 @deftypefun void thread_print_stats (void)
396 Called during Pintos shutdown to print thread statistics.
399 @deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
400 Creates and starts a new thread named @var{name} with the given
401 @var{priority}, returning the new thread's tid. The thread executes
402 @var{func}, passing @var{aux} as the function's single argument.
404 @func{thread_create} allocates a page for the thread's
405 @struct{thread} and stack and initializes its members, then it sets
406 up a set of fake stack frames for it (@pxref{Thread Switching}). The
407 thread is initialized in the blocked state, then unblocked just before
408 returning, which allows the new thread to
409 be scheduled (@pxref{Thread States}).
411 @deftp {Type} {void thread_func (void *@var{aux})}
412 This is the type of the function passed to @func{thread_create}, whose
413 @var{aux} argument is passed along as the function's argument.
417 @deftypefun void thread_block (void)
418 Transitions the running thread from the running state to the blocked
419 state (@pxref{Thread States}). The thread will not run again until
420 @func{thread_unblock} is
421 called on it, so you'd better have some way arranged for that to happen.
422 Because @func{thread_block} is so low-level, you should prefer to use
423 one of the synchronization primitives instead (@pxref{Synchronization}).
426 @deftypefun void thread_unblock (struct thread *@var{thread})
427 Transitions @var{thread}, which must be in the blocked state, to the
428 ready state, allowing it to resume running (@pxref{Thread States}).
429 This is called when the event that the thread is waiting for occurs,
430 e.g.@: when the lock that
431 the thread is waiting on becomes available.
434 @deftypefun {struct thread *} thread_current (void)
435 Returns the running thread.
438 @deftypefun {tid_t} thread_tid (void)
439 Returns the running thread's thread id. Equivalent to
440 @code{thread_current ()->tid}.
443 @deftypefun {const char *} thread_name (void)
444 Returns the running thread's name. Equivalent to @code{thread_current
448 @deftypefun void thread_exit (void) @code{NO_RETURN}
449 Causes the current thread to exit. Never returns, hence
450 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
453 @deftypefun void thread_yield (void)
454 Yields the CPU to the scheduler, which picks a new thread to run. The
455 new thread might be the current thread, so you can't depend on this
456 function to keep this thread from running for any particular length of
460 @deftypefun int thread_get_priority (void)
461 @deftypefunx void thread_set_priority (int @var{new_priority})
462 Stub to set and get thread priority. @xref{Priority Scheduling}.
465 @deftypefun int thread_get_nice (void)
466 @deftypefunx void thread_set_nice (int @var{new_nice})
467 @deftypefunx int thread_get_recent_cpu (void)
468 @deftypefunx int thread_get_load_avg (void)
469 Stubs for the advanced scheduler. @xref{4.4BSD Scheduler}.
472 @node Thread Switching
473 @subsection Thread Switching
475 @func{schedule} is responsible for switching threads. It
476 is internal to @file{threads/thread.c} and called only by the three
477 public thread functions that need to switch threads:
478 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
479 Before any of these functions call @func{schedule}, they disable
480 interrupts (or ensure that they are already disabled) and then change
481 the running thread's state to something other than running.
483 @func{schedule} is short but tricky. It records the
484 current thread in local variable @var{cur}, determines the next thread
485 to run as local variable @var{next} (by calling
486 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
487 the actual thread switch. The thread we switched to was also running
488 inside @func{switch_threads}, as are all the threads not currently
489 running, so the new thread now returns out of
490 @func{switch_threads}, returning the previously running thread.
492 @func{switch_threads} is an assembly language routine in
493 @file{threads/switch.S}. It saves registers on the stack, saves the
494 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
495 member, restores the new thread's @code{stack} into the CPU's stack
496 pointer, restores registers from the stack, and returns.
498 The rest of the scheduler is implemented in @func{schedule_tail}. It
499 marks the new thread as running. If the thread we just switched from
500 is in the dying state, then it also frees the page that contained the
501 dying thread's @struct{thread} and stack. These couldn't be freed
502 prior to the thread switch because the switch needed to use it.
504 Running a thread for the first time is a special case. When
505 @func{thread_create} creates a new thread, it goes through a fair
506 amount of trouble to get it started properly. In particular, the new
507 thread hasn't started running yet, so there's no way for it to be
508 running inside @func{switch_threads} as the scheduler expects. To
509 solve the problem, @func{thread_create} creates some fake stack frames
510 in the new thread's stack:
514 The topmost fake stack frame is for @func{switch_threads}, represented
515 by @struct{switch_threads_frame}. The important part of this frame is
516 its @code{eip} member, the return address. We point @code{eip} to
517 @func{switch_entry}, indicating it to be the function that called
521 The next fake stack frame is for @func{switch_entry}, an assembly
522 language routine in @file{threads/switch.S} that adjusts the stack
523 pointer,@footnote{This is because @func{switch_threads} takes
524 arguments on the stack and the 80@var{x}86 SVR4 calling convention
525 requires the caller, not the called function, to remove them when the
526 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
527 calls @func{schedule_tail} (this special case is why
528 @func{schedule_tail} is separate from @func{schedule}), and returns.
529 We fill in its stack frame so that it returns into
530 @func{kernel_thread}, a function in @file{threads/thread.c}.
533 The final stack frame is for @func{kernel_thread}, which enables
534 interrupts and calls the thread's function (the function passed to
535 @func{thread_create}). If the thread's function returns, it calls
536 @func{thread_exit} to terminate the thread.
539 @node Synchronization
540 @section Synchronization
542 If sharing of resources between threads is not handled in a careful,
543 controlled fashion, then the result is usually a big mess.
544 This is especially the case in operating system kernels, where
545 faulty sharing can crash the entire machine. Pintos provides several
546 synchronization primitives to help out.
549 * Disabling Interrupts::
552 * Condition Variables::
556 @node Disabling Interrupts
557 @subsection Disabling Interrupts
559 The crudest way to do synchronization is to disable interrupts, that
560 is, to temporarily prevent the CPU from responding to interrupts. If
561 interrupts are off, no other thread will preempt the running thread,
562 because thread preemption is driven by the timer interrupt. If
563 interrupts are on, as they normally are, then the running thread may
564 be preempted by another at any time, whether between two C statements
565 or even within the execution of one.
567 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
568 is, kernel threads can be preempted at any time. Traditional Unix
569 systems are ``nonpreemptible,'' that is, kernel threads can only be
570 preempted at points where they explicitly call into the scheduler.
571 (User programs can be preempted at any time in both models.) As you
572 might imagine, preemptible kernels require more explicit
575 You should have little need to set the interrupt state directly. Most
576 of the time you should use the other synchronization primitives
577 described in the following sections. The main reason to disable
578 interrupts is to synchronize kernel threads with external interrupt
579 handlers, which cannot sleep and thus cannot use most other forms of
580 synchronization (@pxref{External Interrupt Handling}).
582 Types and functions for disabling and enabling interrupts are in
583 @file{threads/interrupt.h}.
585 @deftp Type {enum intr_level}
586 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
587 disabled or enabled, respectively.
590 @deftypefun {enum intr_level} intr_get_level (void)
591 Returns the current interrupt state.
594 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
595 Turns interrupts on or off according to @var{level}. Returns the
596 previous interrupt state.
599 @deftypefun {enum intr_level} intr_enable (void)
600 Turns interrupts on. Returns the previous interrupt state.
603 @deftypefun {enum intr_level} intr_disable (void)
604 Turns interrupts off. Returns the previous interrupt state.
608 @subsection Semaphores
610 Pintos' semaphore type and operations are declared in
611 @file{threads/synch.h}.
613 @deftp {Type} {struct semaphore}
614 Represents a @dfn{semaphore}, a nonnegative integer together with two
615 operators that manipulate it atomically, which are:
619 ``Down'' or ``P'': wait for the value to become positive, then
623 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
627 A semaphore initialized to 0 may be used to wait for an event
628 that will happen exactly once. For example, suppose thread @var{A}
629 starts another thread @var{B} and wants to wait for @var{B} to signal
630 that some activity is complete. @var{A} can create a semaphore
631 initialized to 0, pass it to @var{B} as it starts it, and then
632 ``down'' the semaphore. When @var{B} finishes its activity, it
633 ``ups'' the semaphore. This works regardless of whether @var{A}
634 ``downs'' the semaphore or @var{B} ``ups'' it first.
636 A semaphore initialized to 1 is typically used for controlling access
637 to a resource. Before a block of code starts using the resource, it
638 ``downs'' the semaphore, then after it is done with the resource it
639 ``ups'' the resource. In such a case a lock, described below, may be
642 Semaphores can also be initialized to values larger than 1. These are
646 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
647 Initializes @var{sema} as a new semaphore with the given initial
651 @deftypefun void sema_down (struct semaphore *@var{sema})
652 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
653 its value to become positive and then decrementing it by one.
656 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
657 Tries to execute the ``down'' or ``P'' operation on @var{sema},
658 without waiting. Returns true if @var{sema} had a positive value
659 that was successfully decremented, or false if it was already
660 zero and thus could not be decremented. Calling this function in a
661 tight loop wastes CPU time (use @func{sema_down} instead, or find a
665 @deftypefun void sema_up (struct semaphore *@var{sema})
666 Executes the ``up'' or ``V'' operation on @var{sema},
667 incrementing its value. If any threads are waiting on
668 @var{sema}, wakes one of them up.
671 Semaphores are internally built out of disabling interrupt
672 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
673 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
674 a list of waiting threads, using the linked list
675 implementation in @file{lib/kernel/list.c}.
680 Lock types and functions are declared in @file{threads/synch.h}.
682 @deftp {Type} {struct lock}
683 Represents a @dfn{lock}, a specialized semaphore with an initial value
684 of 1 (@pxref{Semaphores}). The difference between a lock and such a
685 semaphore is twofold. First, a semaphore does not have an owner,
686 meaning that one thread can ``down'' the semaphore and then another one
687 ``up'' it, but a single thread must both acquire and release a lock.
688 Second, a semaphore can have a value greater than 1, but a lock can only
689 be owned by a single thread at a time. If these restrictions prove
690 onerous, it's a good sign that a semaphore should be used, instead of a
693 Locks in Pintos are not ``recursive,'' that is, it is an error for the
694 thread currently holding a lock to try to acquire that lock.
697 @deftypefun void lock_init (struct lock *@var{lock})
698 Initializes @var{lock} as a new lock.
701 @deftypefun void lock_acquire (struct lock *@var{lock})
702 Acquires @var{lock} for use by the current thread, first waiting for
703 any current owner to release it if necessary.
706 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
707 Tries to acquire @var{lock} for use by the current thread, without
708 waiting. Returns true if successful, false if the lock is already
709 owned. Calling this function in a tight loop is a bad idea because it
710 wastes CPU time (use @func{lock_acquire} instead).
713 @deftypefun void lock_release (struct lock *@var{lock})
714 Releases @var{lock}, which the current thread must own.
717 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
718 Returns true if the running thread owns @var{lock},
722 @node Condition Variables
723 @subsection Condition Variables
725 Condition variable types and functions are declared in
726 @file{threads/synch.h}.
728 @deftp {Type} {struct condition}
729 Represents a condition variable, which allows one piece of code to
731 and cooperating code to receive the signal and act upon it. Each
732 condition variable is associated with a lock. A given condition
733 variable is associated with only a single lock, but one lock may be
734 associated with any number of condition variables. A set of condition
735 variables taken together with their lock is called a ``monitor.''
737 A thread that owns the monitor lock is said to be ``in the monitor.''
738 The thread in the monitor has control over all the data protected by
739 the lock. It may freely examine or modify this data. If it discovers
740 that it needs to wait for some condition to become true, then it
741 ``waits'' on the associated condition, which releases the lock and
742 waits for the condition to be signaled. If, on the other hand, it has
743 caused one of these conditions to become true, it ``signals'' the
744 condition to wake up one waiter, or ``broadcasts'' the condition to
747 Pintos monitors are ``Mesa'' style, not
748 ``Hoare'' style. That is, sending and receiving a signal are not an
749 atomic operation. Thus, typically the caller must recheck the
750 condition after the wait completes and, if necessary, wait again.
753 @deftypefun void cond_init (struct condition *@var{cond})
754 Initializes @var{cond} as a new condition variable.
757 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
758 Atomically releases @var{lock} (the monitor lock) and waits for
759 @var{cond} to be signaled by some other piece of code. After
760 @var{cond} is signaled, reacquires @var{lock} before returning.
761 @var{lock} must be held before calling this function.
764 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
765 If any threads are waiting on @var{cond} (protected by monitor lock
766 @var{lock}), then this function wakes up one of them. If no threads are
767 waiting, returns without performing any action.
768 @var{lock} must be held before calling this function.
771 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
772 Wakes up all threads, if any, waiting on @var{cond} (protected by
773 monitor lock @var{lock}). @var{lock} must be held before calling this
777 @subsubsection Monitor Example
779 The classical example of a monitor is handling a buffer into which one
780 ``producer'' thread writes characters and out of which a second
781 ``consumer'' thread reads characters. To implement this case we need,
782 besides the monitor lock, two condition variables which we will call
783 @var{not_full} and @var{not_empty}:
786 char buf[BUF_SIZE]; /* @r{Buffer.} */
787 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
788 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
789 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
790 struct lock lock; /* @r{Monitor lock.} */
791 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
792 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
794 @dots{}@r{initialize the locks and condition variables}@dots{}
796 void put (char ch) @{
797 lock_acquire (&lock);
798 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
799 cond_wait (¬_full, &lock);
800 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
802 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
803 lock_release (&lock);
808 lock_acquire (&lock);
809 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
810 cond_wait (¬_empty, &lock);
811 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
813 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
814 lock_release (&lock);
818 @node Memory Barriers
819 @subsection Memory Barriers
821 Suppose we add a ``feature'' that, whenever a timer interrupt
822 occurs, the character in global variable @code{timer_put_char} is
823 printed on the console, but only if global Boolean variable
824 @code{timer_do_put} is true.
826 If interrupts are enabled, this code for setting up @samp{x} to be
827 printed is clearly incorrect, because the timer interrupt could intervene
828 between the two assignments:
831 timer_do_put = true; /* INCORRECT CODE */
832 timer_put_char = 'x';
835 It might not be as obvious that the following code is just as
839 timer_put_char = 'x'; /* INCORRECT CODE */
843 The reason this second example might be a problem is that the compiler
844 is, in general, free to reorder operations when it doesn't have a
845 visible reason to keep them in the same order. In this case, the
846 compiler doesn't know that the order of assignments is important, so its
847 optimization pass is permitted to exchange their order.
848 There's no telling whether it will actually do this, and it is possible
849 that passing the compiler different optimization flags or changing
850 compiler versions will produce different behavior.
852 The following is @emph{not} a solution, because locks neither prevent
853 interrupts nor prevent the compiler from reordering the code within the
854 region where the lock is held:
857 lock_acquire (&timer_lock); /* INCORRECT CODE */
858 timer_put_char = 'x';
860 lock_release (&timer_lock);
863 Fortunately, real solutions do exist. One possibility is to
864 disable interrupts around the assignments. This does not prevent
865 reordering, but it makes the assignments atomic as observed by the
866 interrupt handler. It also has the extra runtime cost of disabling and
867 re-enabling interrupts:
870 enum intr_level old_level = intr_disable ();
871 timer_put_char = 'x';
873 intr_set_level (old_level);
876 A second possibility is to mark the declarations of
877 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
878 keyword tells the compiler that the variables are externally observable
879 and restricts its latitude for optimization. However, the semantics of
880 @samp{volatile} are not well-defined, so it is not a good general
883 Usually, the best solution is to use a compiler feature called a
884 @dfn{memory barrier}, a special statement that prevents the compiler
885 from reordering memory operations across the barrier. In Pintos,
886 @file{threads/synch.h} defines the @code{barrier()} macro as a memory
887 barrier. Here's how we would use a memory barrier to fix this code:
890 timer_put_char = 'x';
895 The compiler also treats invocation of any function defined externally,
896 that is, in another source file, as a limited form of a memory barrier.
897 Specifically, the compiler assumes that any externally defined function
898 may access any statically or dynamically allocated data and any local
899 variable whose address is taken. This often means that explicit
900 barriers can be omitted, and, indeed, this is why the base Pintos code
901 does not need any barriers.
903 A function defined in the same source file, or in a header included by
904 the source file, cannot be relied upon as a memory barrier.
905 This applies even to invocation of a function before its
906 definition, because the compiler may read and parse the entire source
907 file before performing optimization.
909 @node Interrupt Handling
910 @section Interrupt Handling
912 An @dfn{interrupt} notifies the CPU of some event. Much of the work
913 of an operating system relates to interrupts in one way or another.
914 For our purposes, we classify interrupts into two broad categories:
918 @dfn{External interrupts}, that is, interrupts originating outside the
919 CPU. These interrupts come from hardware devices such as the system
920 timer, keyboard, serial ports, and disks. External interrupts are
921 @dfn{asynchronous}, meaning that their delivery is not
922 synchronized with normal CPU activities. External interrupts
923 are what @func{intr_disable} and related functions
924 postpone (@pxref{Disabling Interrupts}).
927 @dfn{Internal interrupts}, that is, interrupts caused by something
928 executing on the CPU. These interrupts are caused by something
929 unusual happening during instruction execution: accessing invalid
930 memory (a @dfn{page fault}), executing invalid instructions, and
931 various other disallowed activities. Because they are caused by CPU
932 instructions, internal interrupts are @dfn{synchronous} or
933 synchronized with CPU instructions. @func{intr_disable} does not
934 disable internal interrupts.
937 Because the CPU treats all interrupts largely the same way, regardless
938 of source, Pintos uses the same infrastructure for both internal and
939 external interrupts, to a point. The following section describes this
940 common infrastructure, and sections after that give the specifics of
941 external and internal interrupts.
943 If you haven't already read chapter 3, ``Basic Execution Environment,''
944 in @bibref{IA32-v1}, it is recommended that you do so now. You might
945 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
949 * Interrupt Infrastructure::
950 * Internal Interrupt Handling::
951 * External Interrupt Handling::
954 @node Interrupt Infrastructure
955 @subsection Interrupt Infrastructure
957 When an interrupt occurs while the kernel is running, the CPU saves
958 its most essential state on the stack and jumps to an interrupt
959 handler routine. The 80@var{x}86 architecture allows for 256 possible
960 interrupts, each of which can have its own handler. The handler for
961 each interrupt is defined in an array called the @dfn{interrupt
962 descriptor table} or IDT.
964 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
965 IDT so that each entry points to a unique entry point in
966 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
967 @var{NN} is the interrupt number in
968 hexadecimal. Because the CPU doesn't give
969 us any other way to find out the interrupt number, this entry point
970 pushes the interrupt number on the stack. Then it jumps to
971 @func{intr_entry}, which pushes all the registers that the processor
972 didn't already save for us, and then calls @func{intr_handler}, which
973 brings us back into C in @file{threads/interrupt.c}.
975 The main job of @func{intr_handler} is to call any function that has
976 been registered for handling the particular interrupt. (If no
977 function is registered, it dumps some information to the console and
978 panics.) It does some extra processing for external
979 interrupts that we'll discuss later.
981 When @func{intr_handler} returns, the assembly code in
982 @file{threads/intr-stubs.S} restores all the CPU registers saved
983 earlier and directs the CPU to return from the interrupt.
985 A few types and functions apply to both internal and external
988 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
989 This is how an interrupt handler function must be declared. Its @var{frame}
990 argument (see below) allows it to determine the cause of the interrupt
991 and the state of the thread that was interrupted.
994 @deftp {Type} {struct intr_frame}
995 The stack frame of an interrupt handler, as saved by CPU, the interrupt
996 stubs, and @func{intr_entry}. Its most interesting members are described
1000 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
1001 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
1002 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
1003 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
1004 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
1005 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1006 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1007 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1008 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1009 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1010 Register values in the interrupted thread saved by @func{intr_entry}.
1011 The @code{esp_dummy} value isn't actually used (refer to the
1012 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1015 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1016 The interrupt vector number, ranging from 0 to 255.
1019 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1020 The ``error code'' pushed on the stack by the CPU for some internal
1024 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1025 The address of the next instruction to be executed by the interrupted
1029 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1030 The interrupted thread's stack pointer.
1033 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1034 Returns the name of the interrupt numbered @var{vec}, or
1035 @code{"unknown"} if the interrupt has no registered name.
1038 @node Internal Interrupt Handling
1039 @subsection Internal Interrupt Handling
1041 When an internal interrupt occurs, it is because the running kernel
1042 thread (or, starting from project 2, the running user process) has
1043 caused it. Thus, because it is related to a thread (or process), an
1044 internal interrupt is said to happen in a ``process context.''
1046 In an internal interrupt, it can make sense to examine the
1047 @struct{intr_frame} passed to the interrupt handler, or even to modify
1048 it. When the interrupt returns, modified members
1049 in @struct{intr_frame} become changes to the thread's registers.
1050 We'll use this in project 2 to return values from system call
1053 There are no special restrictions on what an internal interrupt
1054 handler can or can't do. Generally they should run with interrupts
1055 enabled, just like other code, and so they can be preempted by other
1056 kernel threads. Thus, they do need to synchronize with other threads
1057 on shared data and other resources (@pxref{Synchronization}).
1059 @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})
1060 Registers @var{handler} to be called when internal interrupt numbered
1061 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1064 If @var{level} is @code{INTR_OFF} then handling of further interrupts
1065 will be disabled while the interrupt is being processed. Interrupts
1066 should normally be turned on during the handling of an internal
1069 @var{dpl} determines how the interrupt can be
1070 invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
1071 kernel threads. Otherwise @var{dpl} should be 3, which allows user
1072 processes to invoke the interrupt as well (this is useful only
1073 starting with project 2).
1076 @node External Interrupt Handling
1077 @subsection External Interrupt Handling
1079 Whereas an internal interrupt runs in the context of the thread that
1080 caused it, external interrupts do not have any predictable context.
1081 They are asynchronous, so they can be invoked at any time that
1082 interrupts have not been disabled. We say that an external interrupt
1083 runs in an ``interrupt context.''
1085 In an external interrupt, the @struct{intr_frame} passed to the
1086 handler is not very meaningful. It describes the state of the thread
1087 or process that was interrupted, but there is no way to predict which
1088 one that is. It is possible, although rarely useful, to examine it, but
1089 modifying it is a recipe for disaster.
1091 The activities of an external interrupt handler are severely
1092 restricted. First, only one external interrupt may be processed at a
1093 time, that is, nested external interrupt handling is not supported.
1094 This means that external interrupts must be processed with interrupts
1095 disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
1096 enabled at any point during their execution.
1098 Second, an interrupt handler must not call any function that can
1099 sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
1100 many others. This is because external interrupts use space on the
1101 stack of the kernel thread that was running at the time the interrupt
1102 occurred. If the interrupt handler slept, it would effectively put that
1103 thread to sleep too until the interrupt handler resumed control and
1106 Because an external interrupt runs with interrupts disabled, it
1107 effectively monopolizes the machine and delays all other activities.
1108 Therefore, external interrupt handlers should complete as quickly as
1109 they can. Any activities that require much CPU time should instead
1110 run in a kernel thread, possibly a thread whose activity is triggered
1111 by the interrupt using some synchronization primitive.
1113 External interrupts are also special because they are controlled by a
1114 pair of devices outside the CPU called @dfn{programmable interrupt
1115 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1116 CPU's IDT, it also initializes the PICs for interrupt handling. The
1117 PICs also must be ``acknowledged'' at the end of processing for each
1118 external interrupt. @func{intr_handler} takes care of that by calling
1119 @func{pic_end_of_interrupt}, which sends the proper signals to the
1122 The following additional functions are related to external
1125 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1126 Registers @var{handler} to be called when external interrupt numbered
1127 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1128 purposes. The handler will run with interrupts disabled.
1131 @deftypefun bool intr_context (void)
1132 Returns true if we are running in an interrupt context, otherwise
1133 false. Mainly used at the beginning of functions that might sleep
1134 or that otherwise should not be called from interrupt context, in this
1137 ASSERT (!intr_context ());
1141 @deftypefun void intr_yield_on_return (void)
1142 When called in an interrupt context, causes @func{thread_yield} to be
1143 called just before the interrupt returns. This is used, for example,
1144 in the timer interrupt handler to cause a new thread to be scheduled
1145 when a thread's time slice expires.
1148 @node Memory Allocation
1149 @section Memory Allocation
1151 Pintos contains two memory allocators, one that allocates memory in
1152 units of a page, and one that can allocate blocks of any size.
1159 @node Page Allocator
1160 @subsection Page Allocator
1162 The page allocator declared in @file{threads/palloc.h} allocates
1163 memory in units of a page. It is most often used to allocate memory
1164 one page at a time, but it can also allocate multiple contiguous pages
1167 The page allocator divides the memory it allocates into two pools,
1168 called the kernel and user pools. By default, each pool gets half of
1169 system memory, but this can be changed with a kernel command line
1170 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1171 pool or the other. If one pool becomes empty, the other may still
1172 have free pages. The user pool should be used for allocating memory
1173 for user processes and the kernel pool for all other allocations.
1174 This will only become important starting with project 3. Until then,
1175 all allocations should be made from the kernel pool.
1177 Each pool's usage is tracked with a bitmap, one bit per page in
1178 the pool. A request to allocate @var{n} pages scans the bitmap
1179 for @var{n} consecutive bits set to
1180 false, indicating that those pages are free, and then sets those bits
1181 to true to mark them as used. This is a ``first fit'' allocation
1184 The page allocator is subject to fragmentation. That is, it may not
1185 be possible to allocate @var{n} contiguous pages even though @var{n}
1186 or more pages are free, because the free pages are separated by used
1187 pages. In fact, in pathological cases it may be impossible to
1188 allocate 2 contiguous pages even though @var{n} / 2 pages are free!
1189 Single-page requests can't fail due to fragmentation, so
1190 it is best to limit, as much as possible, the need for multiple
1193 Pages may not be allocated from interrupt context, but they may be
1196 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1197 a debugging aid (@pxref{Debugging Tips}).
1199 Page allocator types and functions are described below.
1201 @deftp {Type} {enum palloc_flags}
1202 A set of flags that describe how to allocate pages. These flags may
1203 be combined in any combination.
1206 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1207 If the pages cannot be allocated, panic the kernel. This is only
1208 appropriate during kernel initialization. User processes
1209 should never be permitted to panic the kernel.
1212 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1213 Zero all the bytes in the allocated pages before returning them. If not
1214 set, the contents of newly allocated pages are unpredictable.
1217 @defvr {Page Allocator Flag} @code{PAL_USER}
1218 Obtain the pages from the user pool. If not set, pages are allocated
1219 from the kernel pool.
1222 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1223 Obtains and returns a single page, allocating it in the manner specified by
1224 @var{flags}. Returns a null pointer if no pages are
1228 @deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1229 Obtains @var{page_cnt} contiguous free pages, allocating them in the
1230 manner specified by @var{flags}, and returns them. Returns a null
1231 pointer if no pages are free.
1234 @deftypefun void palloc_free_page (void *@var{page})
1235 Frees @var{page}, which must have been obtained using
1236 @func{palloc_get_page} or @func{palloc_get_multiple}.
1239 @deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1240 Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
1241 All of the pages must have been obtained using @func{palloc_get_page}
1242 or @func{palloc_get_multiple}.
1245 @node Block Allocator
1246 @subsection Block Allocator
1248 The block allocator, declared in @file{threads/malloc.h}, can allocate
1249 blocks of any size. It is layered on top of the page allocator
1250 described in the previous section. Blocks returned by the block
1251 allocator are obtained from the kernel pool.
1253 The block allocator uses two different strategies for allocating
1254 memory. The first of these applies to ``small'' blocks, those 1 kB or
1256 fourth of the page size). These allocations are rounded up to the
1257 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1258 grouped into a page used only for allocations of the smae
1261 The second strategy applies to allocating ``large'' blocks, those larger
1263 These allocations (plus a small amount of overhead) are rounded up to
1264 the nearest page in size, and then the block allocator requests that
1265 number of contiguous pages from the page allocator.
1267 In either case, the difference between the allocation requested size
1268 and the actual block size is wasted. A real operating system would
1269 carefully tune its allocator to minimize this waste, but this is
1270 unimportant in an instructional system like Pintos.
1272 As long as a page can be obtained from the page allocator, small
1273 allocations always succeed. Most small allocations will not require a
1274 new page from the page allocator at all. However, large allocations
1275 always require calling into the page allocator, and any allocation
1276 that needs more than one contiguous page can fail due to fragmentation,
1277 as already discussed in the previous section. Thus, you should
1278 minimize the number of large allocations in your code, especially
1279 those over approximately 4 kB each.
1281 The interface to the block allocator is through the standard C library
1282 functions @func{malloc}, @func{calloc}, and @func{free}.
1284 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1285 a debugging aid (@pxref{Debugging Tips}).
1287 The block allocator may not be called from interrupt context.
1289 @node Virtual Addresses
1290 @section Virtual Addresses
1292 A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
1293 and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
1298 +-------------------+-----------+
1299 | Page Number | Offset |
1300 +-------------------+-----------+
1305 Header @file{threads/vaddr.h} defines these functions and macros for
1306 working with virtual addresses:
1310 The bit index (0) and number of bits (12) in the offset part of a
1311 virtual address, respectively.
1315 A bit mask with value @t{0xfff}, so that the bits in the page offset are
1316 set to 1 and other bits set to 0.
1320 The page size in bytes (4096).
1323 @deftypefun unsigned pg_ofs (const void *@var{va})
1324 Extracts and returns the page offset in virtual address @var{va}.
1327 @deftypefun uintptr_t pg_no (const void *@var{va})
1328 Extracts and returns the page number in virtual address @var{va}.
1331 @deftypefun {void *} pg_round_down (const void *@var{va})
1332 Returns the start of the virtual page that @var{va} points within, that
1333 is, @var{va} with the page offset set to 0.
1336 @deftypefun {void *} pg_round_up (const void *@var{va})
1337 Returns @var{va} rounded up to the nearest page boundary.
1340 Virtual memory in Pintos is divided into two regions: user virtual
1341 memory and kernel virtual memory. The boundary between them is
1345 Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
1346 GB), but it may be changed to any multiple of @t{0x10000000} from
1347 @t{0x80000000} to @t{0xf0000000}.
1349 User virtual memory ranges from virtual address 0 up to
1350 @code{PHYS_BASE}. Kernel virtual memory occupies the rest of the
1351 virtual address space, from @code{PHYS_BASE} up to 4 GB.
1354 @deftypefun {bool} is_user_vaddr (const void *@var{va})
1355 @deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
1356 Returns true if @var{va} is a user or kernel virtual address,
1357 respectively, false otherwise.
1360 The 80@var{x}86 doesn't provide any way to directly access memory given
1361 a physical address. This ability is often necessary in an operating
1362 system kernel, so Pintos works around it by mapping kernel virtual
1363 memory one-to-one to physical memory. That is, virtual address
1364 @code{PHYS_BASE} accesses physical address 0, virtual address
1365 @code{PHYS_BASE} + @t{0x1234} accesses physical address @t{0x1234}, and
1366 so on up to the size of the machine's physical memory. Thus, adding
1367 @code{PHYS_BASE} to a physical address obtains a kernel virtual address
1368 that accesses that address; conversely, subtracting @code{PHYS_BASE}
1369 from a kernel virtual address obtains the corresponding physical
1370 address. Header @file{threads/vaddr.h} provides a pair of functions to
1371 do these translations:
1373 @deftypefun {void *} ptov (uintptr_t @var{pa})
1374 Returns the kernel virtual address corresponding to physical address
1375 @var{pa}, which should be between 0 and the number of bytes of physical
1379 @deftypefun {uintptr_t} vtop (void *@var{va})
1380 Returns the physical address corresponding to @var{va}, which must be a
1381 kernel virtual address.
1387 The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
1388 hardware page table, also called a ``page directory'' by Intel processor
1389 documentation. The page table interface uses a @code{uint32_t *} to
1390 represent a page table because this is convenient for accessing their
1393 The sections below describe the page table interface and internals.
1396 * Page Table Creation Destruction Activation::
1397 * Page Tables Inspection and Updates::
1398 * Page Table Accessed and Dirty Bits::
1399 * Page Table Details::
1402 @node Page Table Creation Destruction Activation
1403 @subsection Creation, Destruction, and Activation
1405 These functions create, destroy, and activate page tables. The base
1406 Pintos code already calls these functions where necessary, so it should
1407 not be necessary to call them yourself.
1409 @deftypefun {uint32_t *} pagedir_create (void)
1410 Creates and returns a new page table. The new page table contains
1411 Pintos's normal kernel virtual page mappings, but no user virtual
1414 Returns a null pointer if memory cannot be obtained.
1417 @deftypefun void pagedir_destroy (uint32_t *@var{pd})
1418 Frees all of the resources held by @var{pd}, including the page table
1419 itself and the frames that it maps.
1422 @deftypefun void pagedir_activate (uint32_t *@var{pd})
1423 Activates @var{pd}. The active page table is the one used by the CPU to
1424 translate memory references.
1427 @node Page Tables Inspection and Updates
1428 @subsection Inspection and Updates
1430 These functions examine or update the mappings from pages to frames
1431 encapsulated by a page table. They work on both active and inactive
1432 page tables (that is, those for running and suspended processes),
1433 flushing the TLB as necessary.
1435 User page parameters (@var{upage})to these functions should be user
1436 virtual addresses. Kernel page parameters (@var{kpage}) should be
1437 kernel virtual addresses and should have been obtained from the user
1438 pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why PAL_USER?}).
1440 @deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
1441 Adds to @var{pd} a mapping from page @var{upage} to the frame identified
1442 by kernel virtual address @var{kpage}. If @var{writable} is true, the
1443 page is mapped read/write; otherwise, it is mapped read-only.
1445 Page @var{upage} must not already be mapped. If it is, the kernel
1448 Returns true if successful, false on failure. Failure will occur if
1449 additional memory required for the page table cannot be obtained.
1452 @deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
1453 Looks up the frame mapped to @var{upage} in @var{pd}. Returns the
1454 kernel virtual address for that frame, if @var{upage} is mapped, or a
1455 null pointer if it is not.
1458 @deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{upage})
1459 Marks page @var{upage} ``not present'' in @var{pd}. Later accesses to
1460 the page will fault.
1462 Other bits in the page table for @var{upage} are preserved, permitting
1463 the accessed and dirty bits (see the next section) to be checked.
1465 If @var{upage} is not mapped, this function has no effect.
1468 @node Page Table Accessed and Dirty Bits
1469 @subsection Accessed and Dirty Bits
1471 80@var{x}86 hardware provides some assistance for implementing page
1472 replacement algorithms, through a pair of bits in the page table entry
1473 (PTE) for each page. On any read or write to a page, the CPU sets the
1474 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
1475 sets the @dfn{dirty bit} to 1. The CPU never resets these bits to 0,
1476 but the OS may do so.
1478 Proper interpretation of these bits requires understanding of
1479 @dfn{aliases}, that is, two (or more) pages that refer to the same
1480 frame. When an aliased frame is accessed, the accessed and dirty bits
1481 are updated in only one page table entry (the one for the page used for
1482 access). The accessed and dirty bits for the other aliases are not
1485 @xref{Accessed and Dirty Bits}, on applying these bits in implementing
1486 page replacement algorithms.
1488 @deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
1489 @deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
1490 Returns true if page directory @var{pd} contains a page table entry for
1491 @var{page} that is marked dirty (or accessed). Otherwise,
1495 @deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1496 @deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1497 If page directory @var{pd} has a page table entry for @var{page}, then
1498 its dirty (or accessed) bit is set to @var{value}.
1501 @node Page Table Details
1502 @subsection Page Table Details
1504 The functions provided with Pintos are sufficient to implement the
1505 projects. However, you may still find it worthwhile to understand the
1506 hardware page table format, so we'll go into a little detail in this
1510 * Page Table Structure::
1511 * Page Table Entry Format::
1512 * Page Directory Entry Format::
1515 @node Page Table Structure
1516 @subsubsection Structure
1518 The top-level paging data structure is a page called the ``page
1519 directory'' (PD) arranged as an array of 1,024 32-bit page directory
1520 entries (PDEs), each of which represents 4 MB of virtual memory. Each
1521 PDE may point to the physical address of another page called a
1522 ``page table'' (PT) arranged, similarly, as an array of 1,024
1523 32-bit page table entries (PTEs), each of which translates a single 4
1524 kB virtual page to a physical page.
1526 Translation of a virtual address into a physical address follows
1527 the three-step process illustrated in the diagram
1528 below:@footnote{Actually, virtual to physical translation on the
1529 80@var{x}86 architecture occurs via an intermediate ``linear
1530 address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
1531 so that linear and virtual addresses are one and the same. Thus, you
1532 can effectively ignore this CPU feature.}
1536 The most-significant 10 bits of the virtual address (bits 22@dots{}31)
1537 index the page directory. If the PDE is marked ``present,'' the
1538 physical address of a page table is read from the PDE thus obtained.
1539 If the PDE is marked ``not present'' then a page fault occurs.
1542 The next 10 bits of the virtual address (bits 12@dots{}21) index
1543 the page table. If the PTE is marked ``present,'' the physical
1544 address of a data page is read from the PTE thus obtained. If the PTE
1545 is marked ``not present'' then a page fault occurs.
1548 The least-significant 12 bits of the virtual address (bits 0@dots{}11)
1549 are added to the data page's physical base address, yielding the final
1556 +----------------------+----------------------+----------------------+
1557 | Page Directory Index | Page Table Index | Page Offset |
1558 +----------------------+----------------------+----------------------+
1560 _______/ _______/ _____/
1562 / Page Directory / Page Table / Data Page
1563 / .____________. / .____________. / .____________.
1564 |1,023|____________| |1,023|____________| | |____________|
1565 |1,022|____________| |1,022|____________| | |____________|
1566 |1,021|____________| |1,021|____________| \__\|____________|
1567 |1,020|____________| |1,020|____________| /|____________|
1569 | | | \____\| |_ | |
1570 | | . | /| . | \ | . |
1571 \____\| . |_ | . | | | . |
1572 /| . | \ | . | | | . |
1573 | . | | | . | | | . |
1575 |____________| | |____________| | |____________|
1576 4|____________| | 4|____________| | |____________|
1577 3|____________| | 3|____________| | |____________|
1578 2|____________| | 2|____________| | |____________|
1579 1|____________| | 1|____________| | |____________|
1580 0|____________| \__\0|____________| \____\|____________|
1585 Pintos provides some macros and functions that are useful for working
1586 with raw page tables:
1590 The bit index (12) and number of bits (10), respectively, in a page table
1591 index within a virtual address.
1595 A bit mask with the bits in the page table index set to 1 and other bits
1600 The number of bytes of virtual address space that a single page table
1601 page covers (4,194,304 bytes, or 4 MB).
1606 The bit index (22) and number of bits (10), respectively, in a page
1607 directory index within a virtual address.
1611 A bit mask with the bits in the page directory index set to 1 and other
1615 @deftypefun uintptr_t pd_no (const void *@var{va})
1616 @deftypefunx uintptr_t pt_no (const void *@var{va})
1617 Returns the page directory index or page table index, respectively, for
1618 virtual address @var{va}. These functions are defined in
1619 @file{threads/pte.h}.
1622 @deftypefun unsigned pg_ofs (const void *@var{va})
1623 Returns the page offset for virtual address @var{va}. This function is
1624 defined in @file{threads/vaddr.h}.
1627 @node Page Table Entry Format
1628 @subsubsection Page Table Entry Format
1630 You do not need to understand the PTE format to do the Pintos
1631 projects, unless you wish to incorporate the page table into your
1632 supplemental page table (@pxref{Managing the Supplemental Page Table}).
1634 The actual format of a page table entry is summarized below. For
1635 complete information, refer to section 3.7, ``Page Translation Using
1636 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
1640 31 12 11 9 6 5 2 1 0
1641 +---------------------------------------+----+----+-+-+---+-+-+-+
1642 | Physical Address | AVL| |D|A| |U|W|P|
1643 +---------------------------------------+----+----+-+-+---+-+-+-+
1647 Some more information on each bit is given below. The names are
1648 @file{threads/pte.h} macros that represent the bits' values:
1651 Bit 0, the ``present'' bit. When this bit is 1, the
1652 other bits are interpreted as described below. When this bit is 0, any
1653 attempt to access the page will page fault. The remaining bits are then
1654 not used by the CPU and may be used by the OS for any purpose.
1658 Bit 1, the ``read/write'' bit. When it is 1, the page
1659 is writable. When it is 0, write attempts will page fault.
1663 Bit 2, the ``user/supervisor'' bit. When it is 1, user
1664 processes may access the page. When it is 0, only the kernel may access
1665 the page (user accesses will page fault).
1667 Pintos clears this bit in PTEs for kernel virtual memory, to prevent
1668 user processes from accessing them.
1672 Bit 5, the ``accessed'' bit. @xref{Page Table Accessed
1677 Bit 6, the ``dirty'' bit. @xref{Page Table Accessed and
1682 Bits 9@dots{}11, available for operating system use.
1683 Pintos, as provided, does not use them and sets them to 0.
1687 Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
1688 The low 12 bits of the frame's address are always 0.
1691 Other bits are either reserved or uninteresting in a Pintos context and
1692 should be set to@tie{}0.
1694 Header @file{threads/pte.h} defines three functions for working with
1697 @deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
1698 Returns a page table entry that points to @var{page}, which should be a
1699 kernel virtual address. The PTE's present bit will be set. It will be
1700 marked for kernel-only access. If @var{writable} is true, the PTE will
1701 also be marked read/write; otherwise, it will be read-only.
1704 @deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
1705 Returns a page table entry that points to @var{page}, which should be
1706 the kernel virtual address of a frame in the user pool (@pxref{Why
1707 PAL_USER?}). The PTE's present bit will be set and it will be marked to
1708 allow user-mode access. If @var{writable} is true, the PTE will also be
1709 marked read/write; otherwise, it will be read-only.
1712 @deftypefun {void *} pte_get_page (uint32_t @var{pte})
1713 Returns the kernel virtual address for the frame that @var{pte} points
1714 to. The @var{pte} may be present or not-present; if it is not-present
1715 then the pointer return is only meaningful if the proper bits in the PTE
1716 actually represent a physical address.
1719 @node Page Directory Entry Format
1720 @subsubsection Page Directory Entry Format
1722 Page directory entries have the same format as PTEs, except that the
1723 physical address points to a page table page instead of a frame. Header
1724 @file{threads/pte.h} defines two functions for working with page
1727 @deftypefun uint32_t pde_create (uint32_t *@var{pt})
1728 Returns a page directory that points to @var{page}, which should be the
1729 kernel virtual address of a page table page. The PDE's present bit will
1730 be set, it will be marked to allow user-mode access, and it will be
1734 @deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
1735 Returns the kernel virtual address for the page table page that
1736 @var{pde} points to. The @var{pde} must be marked present.
1742 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1743 To use it you will need to manually include its header file,
1744 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}. Intentionally,
1745 no code provided with Pintos uses the hash table, which means that you
1746 are free to use it as is, modify its implementation for your own
1747 purposes, or ignore it, as you wish.
1749 Most implementations of the virtual memory project use a hash table to
1750 translate pages to frames. You may find other uses for hash tables as
1755 * Basic Hash Functions::
1756 * Hash Search Functions::
1757 * Hash Iteration Functions::
1758 * Hash Table Example::
1759 * Hash Auxiliary Data::
1760 * Hash Synchronization::
1763 @node Hash Data Types
1764 @subsection Data Types
1766 A hash table is represented by @struct{hash}.
1768 @deftp {Type} {struct hash}
1769 Represents an entire hash table. The actual members of @struct{hash}
1770 are ``opaque.'' That is, code that uses a hash table should not access
1771 @struct{hash} members directly, nor should it need to. Instead, use
1772 hash table functions and macros.
1775 The hash table operates on elements of type @struct{hash_elem}.
1777 @deftp {Type} {struct hash_elem}
1778 Embed a @struct{hash_elem} member in the structure you want to include
1779 in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
1780 All functions for operating on hash table elements actually take and
1781 return pointers to @struct{hash_elem}, not pointers to your hash table's
1785 You will often need to obtain a @struct{hash_elem}
1786 given a real element of the hash table, and vice versa. Given
1787 a real element of the hash table, obtaining a pointer to its
1788 @struct{hash_elem} is trivial: take the address of the
1789 @struct{hash_elem} member. Use the @code{hash_entry()} macro to go the
1792 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1793 Returns a pointer to the structure that @var{elem}, a pointer to a
1794 @struct{hash_elem}, is embedded within. You must provide @var{type},
1795 the name of the structure that @var{elem} is inside, and @var{member},
1796 the name of the member in @var{type} that @var{elem} points to.
1798 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1799 that points to a @struct{thread} member (of type @struct{hash_elem})
1800 named @code{h_elem}. Then, @code{hash_entry (h, struct thread, h_elem)}
1801 yields the address of the @struct{thread} that @code{h} points within.
1804 Each hash table element must contain a key, that is, data that
1805 identifies and distinguishes elements in the hash table. Every element
1806 in a hash table at a given time must have a unique key. (Elements may
1807 also contain non-key data that need not be unique.) While an element is
1808 in a hash table, its key data must not be changed. For each hash table,
1809 you must write two functions that act on keys: a hash function and a
1810 comparison function. These functions must match the following
1813 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1814 Returns a hash of @var{element}'s data, as a value anywhere in the range
1815 of @code{unsigned int}. The hash of an element should be a
1816 pseudo-random function of the element's key. It must not depend on
1817 non-key data in the element or on any non-constant data other than the
1818 key. Pintos provides the following functions as a suitable basis for
1821 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1822 Returns a hash of the @var{size} bytes starting at @var{buf}. The
1823 implementation is the general-purpose
1824 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1825 hash} for 32-bit words.
1828 @deftypefun unsigned hash_string (const char *@var{s})
1829 Returns a hash of null-terminated string @var{s}.
1832 @deftypefun unsigned hash_int (int @var{i})
1833 Returns a hash of integer @var{i}.
1836 If your key is a single piece of data of an appropriate type, it is
1837 sensible for your hash function to directly return the output of one of
1838 these functions. For multiple pieces of data, you may wish to combine
1839 the output of more than one call to them using, e.g., the @samp{^}
1841 operator. Finally, you may entirely ignore these functions and write
1842 your own hash function from scratch, but remember that your goal is to
1843 build an operating system kernel, not to design a hash function.
1845 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1848 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1849 Compares the keys stored in elements @var{a} and @var{b}. Returns
1850 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1851 or equal to @var{b}.
1853 If two elements compare equal, then they must hash to equal values.
1855 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1858 A few functions that act on hashes accept a pointer to a third kind of
1859 function as an argument:
1861 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1862 Performs some kind of action, chosen by the caller, on @var{element}.
1864 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1867 @node Basic Hash Functions
1868 @subsection Basic Functions
1870 These functions create and destroy hash tables and obtain basic
1871 information about their contents.
1873 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
1874 Initializes @var{hash} as a hash table using @var{hash_func} as hash
1875 function, @var{less_func} as comparison function, and @var{aux} as
1877 Returns true if successful, false on failure. @func{hash_init} calls
1878 @func{malloc} and fails if memory cannot be allocated.
1880 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
1881 most often a null pointer.
1884 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
1885 Removes all the elements from @var{hash}, which must have been
1886 previously initialized with @func{hash_init}.
1888 If @var{action} is non-null, then it is called once for each element in
1889 the hash table, which gives the caller an opportunity to deallocate any
1890 memory or other resources used by the element. For example, if the hash
1891 table elements are dynamically allocated using @func{malloc}, then
1892 @var{action} could @func{free} the element. This is safe because
1893 @func{hash_clear} will not access the memory in a given hash element
1894 after calling @var{action} on it. However, @var{action} must not call
1895 any function that may modify the hash table, such as @func{hash_insert}
1896 or @func{hash_delete}.
1899 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
1900 If @var{action} is non-null, calls it for each element in the hash, with
1901 the same semantics as a call to @func{hash_clear}. Then, frees the
1902 memory held by @var{hash}. Afterward, @var{hash} must not be passed to
1903 any hash table function, absent an intervening call to @func{hash_init}.
1906 @deftypefun size_t hash_size (struct hash *@var{hash})
1907 Returns the number of elements currently stored in @var{hash}.
1910 @deftypefun bool hash_empty (struct hash *@var{hash})
1911 Returns true if @var{hash} currently contains no elements,
1912 false if @var{hash} contains at least one element.
1915 @node Hash Search Functions
1916 @subsection Search Functions
1918 Each of these functions searches a hash table for an element that
1919 compares equal to one provided. Based on the success of the search,
1920 they perform some action, such as inserting a new element into the hash
1921 table, or simply return the result of the search.
1923 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
1924 Searches @var{hash} for an element equal to @var{element}. If none is
1925 found, inserts @var{element} into @var{hash} and returns a null pointer.
1926 If the table already contains an element equal to @var{element}, returns
1927 the existing element without modifying @var{hash}.
1930 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
1931 Inserts @var{element} into @var{hash}. Any element equal to
1932 @var{element} already in @var{hash} is removed. Returns the element
1933 removed, or a null pointer if @var{hash} did not contain an element
1934 equal to @var{element}.
1936 The caller is responsible for deallocating any resources associated with
1937 the element returned, as appropriate. For example, if the hash table
1938 elements are dynamically allocated using @func{malloc}, then the caller
1939 must @func{free} the element after it is no longer needed.
1942 The element passed to the following functions is only used for hashing
1943 and comparison purposes. It is never actually inserted into the hash
1944 table. Thus, only the key data in the element need be initialized, and
1945 other data in the element will not be used. It often makes sense to
1946 declare an instance of the element type as a local variable, initialize
1947 the key data, and then pass the address of its @struct{hash_elem} to
1948 @func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
1949 an example. (Large structures should not be
1950 allocated as local variables. @xref{struct thread}, for more
1953 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
1954 Searches @var{hash} for an element equal to @var{element}. Returns the
1955 element found, if any, or a null pointer otherwise.
1958 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
1959 Searches @var{hash} for an element equal to @var{element}. If one is
1960 found, it is removed from @var{hash} and returned. Otherwise, a null
1961 pointer is returned and @var{hash} is unchanged.
1963 The caller is responsible for deallocating any resources associated with
1964 the element returned, as appropriate. For example, if the hash table
1965 elements are dynamically allocated using @func{malloc}, then the caller
1966 must @func{free} the element after it is no longer needed.
1969 @node Hash Iteration Functions
1970 @subsection Iteration Functions
1972 These functions allow iterating through the elements in a hash table.
1973 Two interfaces are supplied. The first requires writing and supplying a
1974 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
1976 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
1977 Calls @var{action} once for each element in @var{hash}, in arbitrary
1978 order. @var{action} must not call any function that may modify the hash
1979 table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
1980 must not modify key data in elements, although it may modify any other
1984 The second interface is based on an ``iterator'' data type.
1985 Idiomatically, iterators are used as follows:
1988 struct hash_iterator i;
1991 while (hash_next (&i))
1993 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
1994 @r{@dots{}do something with @i{f}@dots{}}
1998 @deftp {Type} {struct hash_iterator}
1999 Represents a position within a hash table. Calling any function that
2000 may modify a hash table, such as @func{hash_insert} or
2001 @func{hash_delete}, invalidates all iterators within that hash table.
2003 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
2006 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
2007 Initializes @var{iterator} to just before the first element in
2011 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
2012 Advances @var{iterator} to the next element in @var{hash}, and returns
2013 that element. Returns a null pointer if no elements remain. After
2014 @func{hash_next} returns null for @var{iterator}, calling it again
2015 yields undefined behavior.
2018 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
2019 Returns the value most recently returned by @func{hash_next} for
2020 @var{iterator}. Yields undefined behavior after @func{hash_first} has
2021 been called on @var{iterator} but before @func{hash_next} has been
2022 called for the first time.
2025 @node Hash Table Example
2026 @subsection Hash Table Example
2028 Suppose you have a structure, called @struct{page}, that you
2029 want to put into a hash table. First, define @struct{page} to include a
2030 @struct{hash_elem} member:
2035 struct hash_elem hash_elem; /* @r{Hash table element.} */
2036 void *addr; /* @r{Virtual address.} */
2037 /* @r{@dots{}other members@dots{}} */
2041 We write a hash function and a comparison function using @var{addr} as
2042 the key. A pointer can be hashed based on its bytes, and the @samp{<}
2043 operator works fine for comparing pointers:
2046 /* @r{Returns a hash value for page @var{p}.} */
2048 page_hash (const struct hash_elem *p_, void *aux UNUSED)
2050 const struct page *p = hash_entry (p_, struct page, hash_elem);
2051 return hash_bytes (&p->addr, sizeof p->addr);
2054 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
2056 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2059 const struct page *a = hash_entry (a_, struct page, hash_elem);
2060 const struct page *b = hash_entry (b_, struct page, hash_elem);
2062 return a->addr < b->addr;
2067 (The use of @code{UNUSED} in these functions' prototypes suppresses a
2068 warning that @var{aux} is unused. @xref{Function and Parameter
2069 Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
2070 Data}, for an explanation of @var{aux}.)
2072 Then, we can create a hash table like this:
2077 hash_init (&pages, page_hash, page_less, NULL);
2080 Now we can manipulate the hash table we've created. If @code{@var{p}}
2081 is a pointer to a @struct{page}, we can insert it into the hash table
2085 hash_insert (&pages, &p->hash_elem);
2088 @noindent If there's a chance that @var{pages} might already contain a
2089 page with the same @var{addr}, then we should check @func{hash_insert}'s
2092 To search for an element in the hash table, use @func{hash_find}. This
2093 takes a little setup, because @func{hash_find} takes an element to
2094 compare against. Here's a function that will find and return a page
2095 based on a virtual address, assuming that @var{pages} is defined at file
2099 /* @r{Returns the page containing the given virtual @var{address},
2100 or a null pointer if no such page exists.} */
2102 page_lookup (const void *address)
2105 struct hash_elem *e;
2108 e = hash_find (&pages, &p.hash_elem);
2109 return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
2114 @struct{page} is allocated as a local variable here on the assumption
2115 that it is fairly small. Large structures should not be allocated as
2116 local variables. @xref{struct thread}, for more information.
2118 A similar function could delete a page by address using
2121 @node Hash Auxiliary Data
2122 @subsection Auxiliary Data
2124 In simple cases like the example above, there's no need for the
2125 @var{aux} parameters. In these cases, just pass a null pointer to
2126 @func{hash_init} for @var{aux} and ignore the values passed to the hash
2127 function and comparison functions. (You'll get a compiler warning if
2128 you don't use the @var{aux} parameter, but you can turn that off with
2129 the @code{UNUSED} macro, as shown in the example, or you can just ignore
2132 @var{aux} is useful when you have some property of the data in the
2133 hash table that's both constant and needed for hashing or comparisons,
2134 but which is not stored in the data items themselves. For example, if
2135 the items in a hash table contain fixed-length strings, but the items
2136 themselves don't indicate what that fixed length is, you could pass
2137 the length as an @var{aux} parameter.
2139 @node Hash Synchronization
2140 @subsection Synchronization
2142 The hash table does not do any internal synchronization. It is the
2143 caller's responsibility to synchronize calls to hash table functions.
2144 In general, any number of functions that examine but do not modify the
2145 hash table, such as @func{hash_find} or @func{hash_next}, may execute
2146 simultaneously. However, these function cannot safely execute at the
2147 same time as any function that may modify a given hash table, such as
2148 @func{hash_insert} or @func{hash_delete}, nor may more than one function
2149 that can modify a given hash table execute safely at once.
2151 It is also the caller's responsibility to synchronize access to data in
2152 hash table elements. How to synchronize access to this data depends on
2153 how it is designed and organized, as with any other data structure.