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 The thread's state, one of the following:
281 @defvr {Thread State} @code{THREAD_RUNNING}
282 The thread is running. Exactly one thread is running at a given time.
283 @func{thread_current} returns the running thread.
286 @defvr {Thread State} @code{THREAD_READY}
287 The thread is ready to run, but it's not running right now. The
288 thread could be selected to run the next time the scheduler is
289 invoked. Ready threads are kept in a doubly linked list called
293 @defvr {Thread State} @code{THREAD_BLOCKED}
294 The thread is waiting for something, e.g.@: a lock to become
295 available, an interrupt to be invoked. The thread won't be scheduled
296 again until it transitions to the @code{THREAD_READY} state with a
297 call to @func{thread_unblock}. This is most conveniently done
298 indirectly, using one of the Pintos synchronization primitives that
299 block and unblock threads automatically (@pxref{Synchronization}).
301 There is no @i{a priori} way to tell what a blocked thread is waiting
302 for, but a backtrace can help (@pxref{Backtraces}).
305 @defvr {Thread State} @code{THREAD_DYING}
306 The thread will be destroyed by the scheduler after switching to the
311 @deftypecv {Member} {@struct{thread}} {char} name[16]
312 The thread's name as a string, or at least the first few characters of
316 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
317 Every thread has its own stack to keep track of its state. When the
318 thread is running, the CPU's stack pointer register tracks the top of
319 the stack and this member is unused. But when the CPU switches to
320 another thread, this member saves the thread's stack pointer. No
321 other members are needed to save the thread's registers, because the
322 other registers that must be saved are saved on the stack.
324 When an interrupt occurs, whether in the kernel or a user program, an
325 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
326 in a user program, the @struct{intr_frame} is always at the very top of
327 the page. @xref{Interrupt Handling}, for more information.
330 @deftypecv {Member} {@struct{thread}} {int} priority
331 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
332 (63). Lower numbers correspond to lower priorities, so that
333 priority 0 is the lowest priority and priority 63 is the highest.
334 Pintos as provided ignores thread priorities, but you will implement
335 priority scheduling in project 1 (@pxref{Priority Scheduling}).
338 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
339 A ``list element'' used to put the thread into doubly linked lists,
340 either @code{ready_list} (the list of threads ready to run) or a list of
341 threads waiting on a semaphore in @func{sema_down}. It can do double
342 duty because a thread waiting on a semaphore is not ready, and vice
346 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
347 Only present in project 2 and later. @xref{Page Tables}.
350 @deftypecv {Member} {@struct{thread}} {unsigned} magic
351 Always set to @code{THREAD_MAGIC}, which is just an arbitrary number defined
352 in @file{threads/thread.c}, and used to detect stack overflow.
353 @func{thread_current} checks that the @code{magic} member of the running
354 thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
355 tends to change this value, triggering the assertion. For greatest
356 benefit, as you add members to @struct{thread}, leave @code{magic} at
360 @node Thread Functions
361 @subsection Thread Functions
363 @file{threads/thread.c} implements several public functions for thread
364 support. Let's take a look at the most useful:
366 @deftypefun void thread_init (void)
367 Called by @func{main} to initialize the thread system. Its main
368 purpose is to create a @struct{thread} for Pintos's initial thread.
369 This is possible because the Pintos loader puts the initial
370 thread's stack at the top of a page, in the same position as any other
373 Before @func{thread_init} runs,
374 @func{thread_current} will fail because the running thread's
375 @code{magic} value is incorrect. Lots of functions call
376 @func{thread_current} directly or indirectly, including
377 @func{lock_acquire} for locking a lock, so @func{thread_init} is
378 called early in Pintos initialization.
381 @deftypefun void thread_start (void)
382 Called by @func{main} to start the scheduler. Creates the idle
383 thread, that is, the thread that is scheduled when no other thread is
384 ready. Then enables interrupts, which as a side effect enables the
385 scheduler because the scheduler runs on return from the timer interrupt, using
386 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
389 @deftypefun void thread_tick (void)
390 Called by the timer interrupt at each timer tick. It keeps track of
391 thread statistics and triggers the scheduler when a time slice expires.
394 @deftypefun void thread_print_stats (void)
395 Called during Pintos shutdown to print thread statistics.
398 @deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
399 Creates and starts a new thread named @var{name} with the given
400 @var{priority}, returning the new thread's tid. The thread executes
401 @var{func}, passing @var{aux} as the function's single argument.
403 @func{thread_create} allocates a page for the thread's
404 @struct{thread} and stack and initializes its members, then it sets
405 up a set of fake stack frames for it (more about this
406 later). The thread is initialized in the blocked state, so the final
407 action before returning is to unblock it, which allows the new thread to
411 @deftp {Type} {void thread_func (void *@var{aux})}
412 This is the type of a thread function. Its @var{aux} argument is the
413 value passed to @func{thread_create}.
416 @deftypefun void thread_block (void)
417 Transitions the running thread from the running state to the blocked
418 state. The thread will not run again until @func{thread_unblock} is
419 called on it, so you'd better have some way arranged for that to happen.
420 Because @func{thread_block} is so low-level, you should prefer to use
421 one of the synchronization primitives instead (@pxref{Synchronization}).
424 @deftypefun void thread_unblock (struct thread *@var{thread})
425 Transitions @var{thread}, which must be in the blocked state, to the
426 ready state, allowing it to resume running. This is called when the
427 event that the thread is waiting for occurs, e.g.@: when the lock that
428 the thread is waiting on becomes available.
431 @deftypefun {struct thread *} thread_current (void)
432 Returns the running thread.
435 @deftypefun {tid_t} thread_tid (void)
436 Returns the running thread's thread id. Equivalent to
437 @code{thread_current ()->tid}.
440 @deftypefun {const char *} thread_name (void)
441 Returns the running thread's name. Equivalent to @code{thread_current
445 @deftypefun void thread_exit (void) @code{NO_RETURN}
446 Causes the current thread to exit. Never returns, hence
447 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
450 @deftypefun void thread_yield (void)
451 Yields the CPU to the scheduler, which picks a new thread to run. The
452 new thread might be the current thread, so you can't depend on this
453 function to keep this thread from running for any particular length of
457 @deftypefun int thread_get_priority (void)
458 @deftypefunx void thread_set_priority (int @var{new_priority})
459 Skeleton to set and get thread priority. @xref{Priority Scheduling}.
462 @deftypefun int thread_get_nice (void)
463 @deftypefunx void thread_set_nice (int @var{new_nice})
464 @deftypefunx int thread_get_recent_cpu (void)
465 @deftypefunx int thread_get_load_avg (void)
466 Skeletons for the advanced scheduler. @xref{4.4BSD Scheduler}.
469 @node Thread Switching
470 @subsection Thread Switching
472 @func{schedule} is the function responsible for switching threads. It
473 is internal to @file{threads/thread.c} and called only by the three
474 public thread functions that need to switch threads:
475 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
476 Before any of these functions call @func{schedule}, they disable
477 interrupts (or ensure that they are already disabled) and then change
478 the running thread's state to something other than running.
480 @func{schedule} is simple but tricky. It records the
481 current thread in local variable @var{cur}, determines the next thread
482 to run as local variable @var{next} (by calling
483 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
484 the actual thread switch. The thread we switched to was also running
485 inside @func{switch_threads}, as are all the threads not currently
486 running, so the new thread now returns out of
487 @func{switch_threads}, returning the previously running thread.
489 @func{switch_threads} is an assembly language routine in
490 @file{threads/switch.S}. It saves registers on the stack, saves the
491 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
492 member, restores the new thread's @code{stack} into the CPU's stack
493 pointer, restores registers from the stack, and returns.
495 The rest of the scheduler is implemented as @func{schedule_tail}. It
496 marks the new thread as running. If the thread we just switched from
497 is in the dying state, then it also frees the page that contained the
498 dying thread's @struct{thread} and stack. These couldn't be freed
499 prior to the thread switch because the switch needed to use it.
501 Running a thread for the first time is a special case. When
502 @func{thread_create} creates a new thread, it goes through a fair
503 amount of trouble to get it started properly. In particular, a new
504 thread hasn't started running yet, so there's no way for it to be
505 running inside @func{switch_threads} as the scheduler expects. To
506 solve the problem, @func{thread_create} creates some fake stack frames
507 in the new thread's stack:
511 The topmost fake stack frame is for @func{switch_threads}, represented
512 by @struct{switch_threads_frame}. The important part of this frame is
513 its @code{eip} member, the return address. We point @code{eip} to
514 @func{switch_entry}, indicating it to be the function that called
518 The next fake stack frame is for @func{switch_entry}, an assembly
519 language routine in @file{threads/switch.S} that adjusts the stack
520 pointer,@footnote{This is because @func{switch_threads} takes
521 arguments on the stack and the 80@var{x}86 SVR4 calling convention
522 requires the caller, not the called function, to remove them when the
523 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
524 calls @func{schedule_tail} (this special case is why
525 @func{schedule_tail} is separate from @func{schedule}), and returns.
526 We fill in its stack frame so that it returns into
527 @func{kernel_thread}, a function in @file{threads/thread.c}.
530 The final stack frame is for @func{kernel_thread}, which enables
531 interrupts and calls the thread's function (the function passed to
532 @func{thread_create}). If the thread's function returns, it calls
533 @func{thread_exit} to terminate the thread.
536 @node Synchronization
537 @section Synchronization
539 If sharing of resources between threads is not handled in a careful,
540 controlled fashion, then the result is usually a big mess.
541 This is especially the case in operating system kernels, where
542 faulty sharing can crash the entire machine. Pintos provides several
543 synchronization primitives to help out.
546 * Disabling Interrupts::
549 * Condition Variables::
553 @node Disabling Interrupts
554 @subsection Disabling Interrupts
556 The crudest way to do synchronization is to disable interrupts, that
557 is, to temporarily prevent the CPU from responding to interrupts. If
558 interrupts are off, no other thread will preempt the running thread,
559 because thread preemption is driven by the timer interrupt. If
560 interrupts are on, as they normally are, then the running thread may
561 be preempted by another at any time, whether between two C statements
562 or even within the execution of one.
564 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
565 is, kernel threads can be preempted at any time. Traditional Unix
566 systems are ``nonpreemptible,'' that is, kernel threads can only be
567 preempted at points where they explicitly call into the scheduler.
568 (User programs can be preempted at any time in both models.) As you
569 might imagine, preemptible kernels require more explicit
572 You should have little need to set the interrupt state directly. Most
573 of the time you should use the other synchronization primitives
574 described in the following sections. The main reason to disable
575 interrupts is to synchronize kernel threads with external interrupt
576 handlers, which cannot sleep and thus cannot use most other forms of
577 synchronization (@pxref{External Interrupt Handling}).
579 Types and functions for disabling and enabling interrupts are in
580 @file{threads/interrupt.h}.
582 @deftp Type {enum intr_level}
583 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
584 disabled or enabled, respectively.
587 @deftypefun {enum intr_level} intr_get_level (void)
588 Returns the current interrupt state.
591 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
592 Turns interrupts on or off according to @var{level}. Returns the
593 previous interrupt state.
596 @deftypefun {enum intr_level} intr_enable (void)
597 Turns interrupts on. Returns the previous interrupt state.
600 @deftypefun {enum intr_level} intr_disable (void)
601 Turns interrupts off. Returns the previous interrupt state.
605 @subsection Semaphores
607 Pintos' semaphore type and operations are declared in
608 @file{threads/synch.h}.
610 @deftp {Type} {struct semaphore}
611 Represents a @dfn{semaphore}, a nonnegative integer together with two
612 operators that manipulate it atomically, which are:
616 ``Down'' or ``P'': wait for the value to become positive, then
620 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
624 A semaphore initialized to 0 may be used to wait for an event
625 that will happen exactly once. For example, suppose thread @var{A}
626 starts another thread @var{B} and wants to wait for @var{B} to signal
627 that some activity is complete. @var{A} can create a semaphore
628 initialized to 0, pass it to @var{B} as it starts it, and then
629 ``down'' the semaphore. When @var{B} finishes its activity, it
630 ``ups'' the semaphore. This works regardless of whether @var{A}
631 ``downs'' the semaphore or @var{B} ``ups'' it first.
633 A semaphore initialized to 1 is typically used for controlling access
634 to a resource. Before a block of code starts using the resource, it
635 ``downs'' the semaphore, then after it is done with the resource it
636 ``ups'' the resource. In such a case a lock, described below, may be
639 Semaphores can also be initialized to values larger than 1. These are
643 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
644 Initializes @var{sema} as a new semaphore with the given initial
648 @deftypefun void sema_down (struct semaphore *@var{sema})
649 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
650 its value to become positive and then decrementing it by one.
653 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
654 Tries to execute the ``down'' or ``P'' operation on @var{sema},
655 without waiting. Returns true if @var{sema} had a positive value
656 that was successfully decremented, or false if it was already
657 zero and thus could not be decremented. Calling this function in a
658 tight loop wastes CPU time (use @func{sema_down} instead, or find a
662 @deftypefun void sema_up (struct semaphore *@var{sema})
663 Executes the ``up'' or ``V'' operation on @var{sema},
664 incrementing its value. If any threads are waiting on
665 @var{sema}, wakes one of them up.
668 Semaphores are internally built out of disabling interrupt
669 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
670 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
671 a list of waiting threads, using the linked list
672 implementation in @file{lib/kernel/list.c}.
677 Lock types and functions are declared in @file{threads/synch.h}.
679 @deftp {Type} {struct lock}
680 Represents a @dfn{lock}, a specialized semaphore with an initial value
681 of 1 (@pxref{Semaphores}). The difference between a lock and such a
682 semaphore is twofold. First, a semaphore does not have an owner,
683 meaning that one thread can ``down'' the semaphore and then another one
684 ``up'' it, but a single thread must both acquire and release a lock.
685 Second, a semaphore can have a value greater than 1, but a lock can only
686 be owned by a single thread at a time. If these restrictions prove
687 onerous, it's a good sign that a semaphore should be used, instead of a
690 Locks in Pintos are not ``recursive,'' that is, it is an error for the
691 thread currently holding a lock to try to acquire that lock.
694 @deftypefun void lock_init (struct lock *@var{lock})
695 Initializes @var{lock} as a new lock.
698 @deftypefun void lock_acquire (struct lock *@var{lock})
699 Acquires @var{lock} for use by the current thread, first waiting for
700 any current owner to release it if necessary.
703 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
704 Tries to acquire @var{lock} for use by the current thread, without
705 waiting. Returns true if successful, false if the lock is already
706 owned. Calling this function in a tight loop is a bad idea because it
707 wastes CPU time (use @func{lock_acquire} instead).
710 @deftypefun void lock_release (struct lock *@var{lock})
711 Releases @var{lock}, which the current thread must own.
714 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
715 Returns true if the running thread owns @var{lock},
719 @node Condition Variables
720 @subsection Condition Variables
722 Condition variable types and functions are declared in
723 @file{threads/synch.h}.
725 @deftp {Type} {struct condition}
726 Represents a condition variable, which allows one piece of code to
728 and cooperating code to receive the signal and act upon it. Each
729 condition variable is associated with a lock. A given condition
730 variable is associated with only a single lock, but one lock may be
731 associated with any number of condition variables. A set of condition
732 variables taken together with their lock is called a ``monitor.''
734 A thread that owns the monitor lock is said to be ``in the monitor.''
735 The thread in the monitor has control over all the data protected by
736 the lock. It may freely examine or modify this data. If it discovers
737 that it needs to wait for some condition to become true, then it
738 ``waits'' on the associated condition, which releases the lock and
739 waits for the condition to be signaled. If, on the other hand, it has
740 caused one of these conditions to become true, it ``signals'' the
741 condition to wake up one waiter, or ``broadcasts'' the condition to
744 Pintos monitors are ``Mesa'' style, not
745 ``Hoare'' style. That is, sending and receiving a signal are not an
746 atomic operation. Thus, typically the caller must recheck the
747 condition after the wait completes and, if necessary, wait again.
750 @deftypefun void cond_init (struct condition *@var{cond})
751 Initializes @var{cond} as a new condition variable.
754 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
755 Atomically releases @var{lock} (the monitor lock) and waits for
756 @var{cond} to be signaled by some other piece of code. After
757 @var{cond} is signaled, reacquires @var{lock} before returning.
758 @var{lock} must be held before calling this function.
761 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
762 If any threads are waiting on @var{cond} (protected by monitor lock
763 @var{lock}), then this function wakes up one of them. If no threads are
764 waiting, returns without performing any action.
765 @var{lock} must be held before calling this function.
768 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
769 Wakes up all threads, if any, waiting on @var{cond} (protected by
770 monitor lock @var{lock}). @var{lock} must be held before calling this
774 @subsubsection Monitor Example
776 The classical example of a monitor is handling a buffer into which one
777 ``producer'' thread writes characters and out of which a second
778 ``consumer'' thread reads characters. To implement this case we need,
779 besides the monitor lock, two condition variables which we will call
780 @var{not_full} and @var{not_empty}:
783 char buf[BUF_SIZE]; /* @r{Buffer.} */
784 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
785 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
786 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
787 struct lock lock; /* @r{Monitor lock.} */
788 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
789 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
791 @dots{}@r{initialize the locks and condition variables}@dots{}
793 void put (char ch) @{
794 lock_acquire (&lock);
795 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
796 cond_wait (¬_full, &lock);
797 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
799 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
800 lock_release (&lock);
805 lock_acquire (&lock);
806 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
807 cond_wait (¬_empty, &lock);
808 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
810 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
811 lock_release (&lock);
815 @node Memory Barriers
816 @subsection Memory Barriers
818 Suppose we add a ``feature'' that, whenever a timer interrupt
819 occurs, the character in global variable @code{timer_put_char} is
820 printed on the console, but only if global Boolean variable
821 @code{timer_do_put} is true.
823 If interrupts are enabled, this code for setting up @samp{x} to be
824 printed is clearly incorrect, because the timer interrupt could intervene
825 between the two assignments:
828 timer_do_put = true; /* INCORRECT CODE */
829 timer_put_char = 'x';
832 It might not be as obvious that the following code is just as
836 timer_put_char = 'x'; /* INCORRECT CODE */
840 The reason this second example might be a problem is that the compiler
841 is, in general, free to reorder operations when it doesn't have a
842 visible reason to keep them in the same order. In this case, the
843 compiler doesn't know that the order of assignments is important, so its
844 optimization pass is permitted to exchange their order.
845 There's no telling whether it will actually do this, and it is possible
846 that passing the compiler different optimization flags or changing
847 compiler versions will produce different behavior.
849 The following is @emph{not} a solution, because locks neither prevent
850 interrupts nor prevent the compiler from reordering the code within the
851 region where the lock is held:
854 lock_acquire (&timer_lock); /* INCORRECT CODE */
855 timer_put_char = 'x';
857 lock_release (&timer_lock);
860 Fortunately, real solutions do exist. One possibility is to
861 disable interrupts around the assignments. This does not prevent
862 reordering, but it makes the assignments atomic as observed by the
863 interrupt handler. It also has the extra runtime cost of disabling and
864 re-enabling interrupts:
867 enum intr_level old_level = intr_disable ();
868 timer_put_char = 'x';
870 intr_set_level (old_level);
873 A second possibility is to mark the declarations of
874 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
875 keyword tells the compiler that the variables are externally observable
876 and restricts its latitude for optimization. However, the semantics of
877 @samp{volatile} are not well-defined, so it is not a good general
880 Usually, the best solution is to use a compiler feature called a
881 @dfn{memory barrier}, a special statement that prevents the compiler
882 from reordering memory operations across the barrier. In Pintos,
883 @file{threads/synch.h} defines the @code{barrier()} macro as a memory
884 barrier. Here's how we would use a memory barrier to fix this code:
887 timer_put_char = 'x';
892 The compiler also treats invocation of any function defined externally,
893 that is, in another source file, as a limited form of a memory barrier.
894 Specifically, the compiler assumes that any externally defined function
895 may access any statically or dynamically allocated data and any local
896 variable whose address is taken. This often means that explicit
897 barriers can be omitted, and, indeed, this is why the base Pintos code
898 does not need any barriers.
900 A function defined in the same source file, or in a header included by
901 the source file, cannot be relied upon as a memory barrier.
902 This applies even to invocation of a function before its
903 definition, because the compiler may read and parse the entire source
904 file before performing optimization.
906 @node Interrupt Handling
907 @section Interrupt Handling
909 An @dfn{interrupt} notifies the CPU of some event. Much of the work
910 of an operating system relates to interrupts in one way or another.
911 For our purposes, we classify interrupts into two broad categories:
915 @dfn{External interrupts}, that is, interrupts originating outside the
916 CPU. These interrupts come from hardware devices such as the system
917 timer, keyboard, serial ports, and disks. External interrupts are
918 @dfn{asynchronous}, meaning that their delivery is not
919 synchronized with normal CPU activities. External interrupts
920 are what @func{intr_disable} and related functions
921 postpone (@pxref{Disabling Interrupts}).
924 @dfn{Internal interrupts}, that is, interrupts caused by something
925 executing on the CPU. These interrupts are caused by something
926 unusual happening during instruction execution: accessing invalid
927 memory (a @dfn{page fault}), executing invalid instructions, and
928 various other disallowed activities. Because they are caused by CPU
929 instructions, internal interrupts are @dfn{synchronous} or
930 synchronized with CPU instructions. @func{intr_disable} does not
931 disable internal interrupts.
934 Because the CPU treats all interrupts largely the same way, regardless
935 of source, Pintos uses the same infrastructure for both internal and
936 external interrupts, to a point. The following section describes this
937 common infrastructure, and sections after that give the specifics of
938 external and internal interrupts.
940 If you haven't already read chapter 3, ``Basic Execution Environment,''
941 in @bibref{IA32-v1}, it is recommended that you do so now. You might
942 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
946 * Interrupt Infrastructure::
947 * Internal Interrupt Handling::
948 * External Interrupt Handling::
951 @node Interrupt Infrastructure
952 @subsection Interrupt Infrastructure
954 When an interrupt occurs while the kernel is running, the CPU saves
955 its most essential state on the stack and jumps to an interrupt
956 handler routine. The 80@var{x}86 architecture allows for 256 possible
957 interrupts, each of which can have its own handler. The handler for
958 each interrupt is defined in an array called the @dfn{interrupt
959 descriptor table} or IDT.
961 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
962 IDT so that each entry points to a unique entry point in
963 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
964 @var{NN} is the interrupt number in
965 hexadecimal. Because the CPU doesn't give
966 us any other way to find out the interrupt number, this entry point
967 pushes the interrupt number on the stack. Then it jumps to
968 @func{intr_entry}, which pushes all the registers that the processor
969 didn't already save for us, and then calls @func{intr_handler}, which
970 brings us back into C in @file{threads/interrupt.c}.
972 The main job of @func{intr_handler} is to call any function that has
973 been registered for handling the particular interrupt. (If no
974 function is registered, it dumps some information to the console and
975 panics.) It does some extra processing for external
976 interrupts that we'll discuss later.
978 When @func{intr_handler} returns, the assembly code in
979 @file{threads/intr-stubs.S} restores all the CPU registers saved
980 earlier and directs the CPU to return from the interrupt.
982 A few types and functions apply to both internal and external
985 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
986 This is how an interrupt handler function must be declared. Its @var{frame}
987 argument (see below) allows it to determine the cause of the interrupt
988 and the state of the thread that was interrupted.
991 @deftp {Type} {struct intr_frame}
992 The stack frame of an interrupt handler, as saved by CPU, the interrupt
993 stubs, and @func{intr_entry}. Its most interesting members are described
997 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
998 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
999 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
1000 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
1001 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
1002 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1003 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1004 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1005 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1006 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1007 Register values in the interrupted thread saved by @func{intr_entry}.
1008 The @code{esp_dummy} value isn't actually used (refer to the
1009 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1012 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1013 The interrupt vector number, ranging from 0 to 255.
1016 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1017 The ``error code'' pushed on the stack by the CPU for some internal
1021 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1022 The address of the next instruction to be executed by the interrupted
1026 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1027 The interrupted thread's stack pointer.
1030 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1031 Returns the name of the interrupt numbered @var{vec}, or
1032 @code{"unknown"} if the interrupt has no registered name.
1035 @node Internal Interrupt Handling
1036 @subsection Internal Interrupt Handling
1038 When an internal interrupt occurs, it is because the running kernel
1039 thread (or, starting from project 2, the running user process) has
1040 caused it. Thus, because it is related to a thread (or process), an
1041 internal interrupt is said to happen in a ``process context.''
1043 In an internal interrupt, it can make sense to examine the
1044 @struct{intr_frame} passed to the interrupt handler, or even to modify
1045 it. When the interrupt returns, modified members
1046 in @struct{intr_frame} become changes to the thread's registers.
1047 We'll use this in project 2 to return values from system call
1050 There are no special restrictions on what an internal interrupt
1051 handler can or can't do. Generally they should run with interrupts
1052 enabled, just like other code, and so they can be preempted by other
1053 kernel threads. Thus, they do need to synchronize with other threads
1054 on shared data and other resources (@pxref{Synchronization}).
1056 @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})
1057 Registers @var{handler} to be called when internal interrupt numbered
1058 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1061 If @var{level} is @code{INTR_OFF} then handling of further interrupts
1062 will be disabled while the interrupt is being processed. Interrupts
1063 should normally be turned on during the handling of an internal
1066 @var{dpl} determines how the interrupt can be
1067 invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
1068 kernel threads. Otherwise @var{dpl} should be 3, which allows user
1069 processes to invoke the interrupt as well (this is useful only
1070 starting with project 2).
1073 @node External Interrupt Handling
1074 @subsection External Interrupt Handling
1076 Whereas an internal interrupt runs in the context of the thread that
1077 caused it, external interrupts do not have any predictable context.
1078 They are asynchronous, so they can be invoked at any time that
1079 interrupts have not been disabled. We say that an external interrupt
1080 runs in an ``interrupt context.''
1082 In an external interrupt, the @struct{intr_frame} passed to the
1083 handler is not very meaningful. It describes the state of the thread
1084 or process that was interrupted, but there is no way to predict which
1085 one that is. It is possible, although rarely useful, to examine it, but
1086 modifying it is a recipe for disaster.
1088 The activities of an external interrupt handler are severely
1089 restricted. First, only one external interrupt may be processed at a
1090 time, that is, nested external interrupt handling is not supported.
1091 This means that external interrupts must be processed with interrupts
1092 disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
1093 enabled at any point during their execution.
1095 Second, an interrupt handler must not call any function that can
1096 sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
1097 many others. This is because external interrupts use space on the
1098 stack of the kernel thread that was running at the time the interrupt
1099 occurred. If the interrupt handler slept, it would effectively put that
1100 thread to sleep too until the interrupt handler resumed control and
1103 Because an external interrupt runs with interrupts disabled, it
1104 effectively monopolizes the machine and delays all other activities.
1105 Therefore, external interrupt handlers should complete as quickly as
1106 they can. Any activities that require much CPU time should instead
1107 run in a kernel thread, possibly a thread whose activity is triggered
1108 by the interrupt using some synchronization primitive.
1110 External interrupts are also special because they are controlled by a
1111 pair of devices outside the CPU called @dfn{programmable interrupt
1112 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1113 CPU's IDT, it also initializes the PICs for interrupt handling. The
1114 PICs also must be ``acknowledged'' at the end of processing for each
1115 external interrupt. @func{intr_handler} takes care of that by calling
1116 @func{pic_end_of_interrupt}, which sends the proper signals to the
1119 The following additional functions are related to external
1122 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1123 Registers @var{handler} to be called when external interrupt numbered
1124 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1125 purposes. The handler will run with interrupts disabled.
1128 @deftypefun bool intr_context (void)
1129 Returns true if we are running in an interrupt context, otherwise
1130 false. Mainly used at the beginning of functions that might sleep
1131 or that otherwise should not be called from interrupt context, in this
1134 ASSERT (!intr_context ());
1138 @deftypefun void intr_yield_on_return (void)
1139 When called in an interrupt context, causes @func{thread_yield} to be
1140 called just before the interrupt returns. This is used, for example,
1141 in the timer interrupt handler to cause a new thread to be scheduled
1142 when a thread's time slice expires.
1145 @node Memory Allocation
1146 @section Memory Allocation
1148 Pintos contains two memory allocators, one that allocates memory in
1149 units of a page, and one that can allocate blocks of any size.
1156 @node Page Allocator
1157 @subsection Page Allocator
1159 The page allocator declared in @file{threads/palloc.h} allocates
1160 memory in units of a page. It is most often used to allocate memory
1161 one page at a time, but it can also allocate multiple contiguous pages
1164 The page allocator divides the memory it allocates into two pools,
1165 called the kernel and user pools. By default, each pool gets half of
1166 system memory, but this can be changed with a kernel command line
1167 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1168 pool or the other. If one pool becomes empty, the other may still
1169 have free pages. The user pool should be used for allocating memory
1170 for user processes and the kernel pool for all other allocations.
1171 This will only become important starting with project 3. Until then,
1172 all allocations should be made from the kernel pool.
1174 Each pool's usage is tracked with a bitmap, one bit per page in
1175 the pool. A request to allocate @var{n} pages scans the bitmap
1176 for @var{n} consecutive bits set to
1177 false, indicating that those pages are free, and then sets those bits
1178 to true to mark them as used. This is a ``first fit'' allocation
1181 The page allocator is subject to fragmentation. That is, it may not
1182 be possible to allocate @var{n} contiguous pages even though @var{n}
1183 or more pages are free, because the free pages are separated by used
1184 pages. In fact, in pathological cases it may be impossible to
1185 allocate 2 contiguous pages even though @var{n} / 2 pages are free!
1186 Single-page requests can't fail due to fragmentation, so
1187 it is best to limit, as much as possible, the need for multiple
1190 Pages may not be allocated from interrupt context, but they may be
1193 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1194 a debugging aid (@pxref{Debugging Tips}).
1196 Page allocator types and functions are described below.
1198 @deftp {Type} {enum palloc_flags}
1199 A set of flags that describe how to allocate pages. These flags may
1200 be combined in any combination.
1203 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1204 If the pages cannot be allocated, panic the kernel. This is only
1205 appropriate during kernel initialization. User processes
1206 should never be permitted to panic the kernel.
1209 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1210 Zero all the bytes in the allocated pages before returning them. If not
1211 set, the contents of newly allocated pages are unpredictable.
1214 @defvr {Page Allocator Flag} @code{PAL_USER}
1215 Obtain the pages from the user pool. If not set, pages are allocated
1216 from the kernel pool.
1219 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1220 Obtains and returns a single page, allocating it in the manner specified by
1221 @var{flags}. Returns a null pointer if no pages are
1225 @deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1226 Obtains @var{page_cnt} contiguous free pages, allocating them in the
1227 manner specified by @var{flags}, and returns them. Returns a null
1228 pointer if no pages are free.
1231 @deftypefun void palloc_free_page (void *@var{page})
1232 Frees @var{page}, which must have been obtained using
1233 @func{palloc_get_page} or @func{palloc_get_multiple}.
1236 @deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1237 Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
1238 All of the pages must have been obtained using @func{palloc_get_page}
1239 or @func{palloc_get_multiple}.
1242 @node Block Allocator
1243 @subsection Block Allocator
1245 The block allocator, declared in @file{threads/malloc.h}, can allocate
1246 blocks of any size. It is layered on top of the page allocator
1247 described in the previous section. Blocks returned by the block
1248 allocator are obtained from the kernel pool.
1250 The block allocator uses two different strategies for allocating
1251 memory. The first of these applies to ``small'' blocks, those 1 kB or
1253 fourth of the page size). These allocations are rounded up to the
1254 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1255 grouped into a page used only for allocations of the smae
1258 The second strategy applies to allocating ``large'' blocks, those larger
1260 These allocations (plus a small amount of overhead) are rounded up to
1261 the nearest page in size, and then the block allocator requests that
1262 number of contiguous pages from the page allocator.
1264 In either case, the difference between the allocation requested size
1265 and the actual block size is wasted. A real operating system would
1266 carefully tune its allocator to minimize this waste, but this is
1267 unimportant in an instructional system like Pintos.
1269 As long as a page can be obtained from the page allocator, small
1270 allocations always succeed. Most small allocations will not require a
1271 new page from the page allocator at all. However, large allocations
1272 always require calling into the page allocator, and any allocation
1273 that needs more than one contiguous page can fail due to fragmentation,
1274 as already discussed in the previous section. Thus, you should
1275 minimize the number of large allocations in your code, especially
1276 those over approximately 4 kB each.
1278 The interface to the block allocator is through the standard C library
1279 functions @func{malloc}, @func{calloc}, and @func{free}.
1281 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1282 a debugging aid (@pxref{Debugging Tips}).
1284 The block allocator may not be called from interrupt context.
1286 @node Virtual Addresses
1287 @section Virtual Addresses
1289 A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
1290 and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
1295 +-------------------+-----------+
1296 | Page Number | Offset |
1297 +-------------------+-----------+
1302 Header @file{threads/vaddr.h} defines these functions and macros for
1303 working with virtual addresses:
1307 The bit index (0) and number of bits (12) in the offset part of a
1308 virtual address, respectively.
1312 A bit mask with value @t{0xfff}, so that the bits in the page offset are
1313 set to 1 and other bits set to 0.
1317 The page size in bytes (4096).
1320 @deftypefun unsigned pg_ofs (const void *@var{va})
1321 Extracts and returns the page offset in virtual address @var{va}.
1324 @deftypefun uintptr_t pg_no (const void *@var{va})
1325 Extracts and returns the page number in virtual address @var{va}.
1328 @deftypefun {void *} pg_round_down (const void *@var{va})
1329 Returns the start of the virtual page that @var{va} points within, that
1330 is, @var{va} with the page offset set to 0.
1333 @deftypefun {void *} pg_round_up (const void *@var{va})
1334 Returns @var{va} rounded up to the nearest page boundary.
1337 Virtual memory in Pintos is divided into two regions: user virtual
1338 memory and kernel virtual memory. The boundary between them is
1342 Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
1343 GB), but it may be changed to any multiple of @t{0x10000000} from
1344 @t{0x80000000} to @t{0xf0000000}.
1346 User virtual memory ranges from virtual address 0 up to
1347 @code{PHYS_BASE}. Kernel virtual memory occupies the rest of the
1348 virtual address space, from @code{PHYS_BASE} up to 4 GB.
1351 @deftypefun {bool} is_user_vaddr (const void *@var{va})
1352 @deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
1353 Returns true if @var{va} is a user or kernel virtual address,
1354 respectively, false otherwise.
1357 The 80@var{x}86 doesn't provide any way to directly access memory given
1358 a physical address. This ability is often necessary in an operating
1359 system kernel, so Pintos works around it by mapping kernel virtual
1360 memory one-to-one to physical memory. That is, virtual address
1361 @code{PHYS_BASE} accesses physical address 0, virtual address
1362 @code{PHYS_BASE} + @t{0x1234} accesses physical address @t{0x1234}, and
1363 so on up to the size of the machine's physical memory. Thus, adding
1364 @code{PHYS_BASE} to a physical address obtains a kernel virtual address
1365 that accesses that address; conversely, subtracting @code{PHYS_BASE}
1366 from a kernel virtual address obtains the corresponding physical
1367 address. Header @file{threads/vaddr.h} provides a pair of functions to
1368 do these translations:
1370 @deftypefun {void *} ptov (uintptr_t @var{pa})
1371 Returns the kernel virtual address corresponding to physical address
1372 @var{pa}, which should be between 0 and the number of bytes of physical
1376 @deftypefun {uintptr_t} vtop (void *@var{va})
1377 Returns the physical address corresponding to @var{va}, which must be a
1378 kernel virtual address.
1384 The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
1385 hardware page table, also called a ``page directory'' by Intel processor
1386 documentation. The page table interface uses a @code{uint32_t *} to
1387 represent a page table because this is convenient for accessing their
1390 The sections below describe the page table interface and internals.
1393 * Page Table Creation Destruction Activation::
1394 * Page Tables Inspection and Updates::
1395 * Page Table Accessed and Dirty Bits::
1396 * Page Table Details::
1399 @node Page Table Creation Destruction Activation
1400 @subsection Creation, Destruction, and Activation
1402 These functions create, destroy, and activate page tables. The base
1403 Pintos code already calls these functions where necessary, so it should
1404 not be necessary to call them yourself.
1406 @deftypefun {uint32_t *} pagedir_create (void)
1407 Creates and returns a new page table. The new page table contains
1408 Pintos's normal kernel virtual page mappings, but no user virtual
1411 Returns a null pointer if memory cannot be obtained.
1414 @deftypefun void pagedir_destroy (uint32_t *@var{pd})
1415 Frees all of the resources held by @var{pd}, including the page table
1416 itself and the frames that it maps.
1419 @deftypefun void pagedir_activate (uint32_t *@var{pd})
1420 Activates @var{pd}. The active page table is the one used by the CPU to
1421 translate memory references.
1424 @node Page Tables Inspection and Updates
1425 @subsection Inspection and Updates
1427 These functions examine or update the mappings from pages to frames
1428 encapsulated by a page table. They work on both active and inactive
1429 page tables (that is, those for running and suspended processes),
1430 flushing the TLB as necessary.
1432 User page parameters (@var{upage})to these functions should be user
1433 virtual addresses. Kernel page parameters (@var{kpage}) should be
1434 kernel virtual addresses and should have been obtained from the user
1435 pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why PAL_USER?}).
1437 @deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
1438 Adds to @var{pd} a mapping from page @var{upage} to the frame identified
1439 by kernel virtual address @var{kpage}. If @var{writable} is true, the
1440 page is mapped read/write; otherwise, it is mapped read-only.
1442 Page @var{upage} must not already be mapped. If it is, the kernel
1445 Returns true if successful, false on failure. Failure will occur if
1446 additional memory required for the page table cannot be obtained.
1449 @deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
1450 Looks up the frame mapped to @var{upage} in @var{pd}. Returns the
1451 kernel virtual address for that frame, if @var{upage} is mapped, or a
1452 null pointer if it is not.
1455 @deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{upage})
1456 Marks page @var{upage} ``not present'' in @var{pd}. Later accesses to
1457 the page will fault.
1459 Other bits in the page table for @var{upage} are preserved, permitting
1460 the accessed and dirty bits (see the next section) to be checked.
1462 If @var{upage} is not mapped, this function has no effect.
1465 @node Page Table Accessed and Dirty Bits
1466 @subsection Accessed and Dirty Bits
1468 80@var{x}86 hardware provides some assistance for implementing page
1469 replacement algorithms, through a pair of bits in the page table entry
1470 (PTE) for each page. On any read or write to a page, the CPU sets the
1471 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
1472 sets the @dfn{dirty bit} to 1. The CPU never resets these bits to 0,
1473 but the OS may do so.
1475 Proper interpretation of these bits requires understanding of
1476 @dfn{aliases}, that is, two (or more) pages that refer to the same
1477 frame. When an aliased frame is accessed, the accessed and dirty bits
1478 are updated in only one page table entry (the one for the page used for
1479 access). The accessed and dirty bits for the other aliases are not
1482 @xref{Accessed and Dirty Bits}, on applying these bits in implementing
1483 page replacement algorithms.
1485 @deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
1486 @deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
1487 Returns true if page directory @var{pd} contains a page table entry for
1488 @var{page} that is marked dirty (or accessed). Otherwise,
1492 @deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1493 @deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1494 If page directory @var{pd} has a page table entry for @var{page}, then
1495 its dirty (or accessed) bit is set to @var{value}.
1498 @node Page Table Details
1499 @subsection Page Table Details
1501 The functions provided with Pintos are sufficient to implement the
1502 projects. However, you may still find it worthwhile to understand the
1503 hardware page table format, so we'll go into a little detail in this
1507 * Page Table Structure::
1508 * Page Table Entry Format::
1509 * Page Directory Entry Format::
1512 @node Page Table Structure
1513 @subsubsection Structure
1515 The top-level paging data structure is a page called the ``page
1516 directory'' (PD) arranged as an array of 1,024 32-bit page directory
1517 entries (PDEs), each of which represents 4 MB of virtual memory. Each
1518 PDE may point to the physical address of another page called a
1519 ``page table'' (PT) arranged, similarly, as an array of 1,024
1520 32-bit page table entries (PTEs), each of which translates a single 4
1521 kB virtual page to a physical page.
1523 Translation of a virtual address into a physical address follows
1524 the three-step process illustrated in the diagram
1525 below:@footnote{Actually, virtual to physical translation on the
1526 80@var{x}86 architecture occurs via an intermediate ``linear
1527 address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
1528 so that linear and virtual addresses are one and the same. Thus, you
1529 can effectively ignore this CPU feature.}
1533 The most-significant 10 bits of the virtual address (bits 22@dots{}31)
1534 index the page directory. If the PDE is marked ``present,'' the
1535 physical address of a page table is read from the PDE thus obtained.
1536 If the PDE is marked ``not present'' then a page fault occurs.
1539 The next 10 bits of the virtual address (bits 12@dots{}21) index
1540 the page table. If the PTE is marked ``present,'' the physical
1541 address of a data page is read from the PTE thus obtained. If the PTE
1542 is marked ``not present'' then a page fault occurs.
1545 The least-significant 12 bits of the virtual address (bits 0@dots{}11)
1546 are added to the data page's physical base address, yielding the final
1553 +----------------------+----------------------+----------------------+
1554 | Page Directory Index | Page Table Index | Page Offset |
1555 +----------------------+----------------------+----------------------+
1557 _______/ _______/ _____/
1559 / Page Directory / Page Table / Data Page
1560 / .____________. / .____________. / .____________.
1561 |1,023|____________| |1,023|____________| | |____________|
1562 |1,022|____________| |1,022|____________| | |____________|
1563 |1,021|____________| |1,021|____________| \__\|____________|
1564 |1,020|____________| |1,020|____________| /|____________|
1566 | | | \____\| |_ | |
1567 | | . | /| . | \ | . |
1568 \____\| . |_ | . | | | . |
1569 /| . | \ | . | | | . |
1570 | . | | | . | | | . |
1572 |____________| | |____________| | |____________|
1573 4|____________| | 4|____________| | |____________|
1574 3|____________| | 3|____________| | |____________|
1575 2|____________| | 2|____________| | |____________|
1576 1|____________| | 1|____________| | |____________|
1577 0|____________| \__\0|____________| \____\|____________|
1582 Pintos provides some macros and functions that are useful for working
1583 with raw page tables:
1587 The bit index (12) and number of bits (10), respectively, in a page table
1588 index within a virtual address.
1592 A bit mask with the bits in the page table index set to 1 and other bits
1597 The number of bytes of virtual address space that a single page table
1598 page covers (4,194,304 bytes, or 4 MB).
1603 The bit index (22) and number of bits (10), respectively, in a page
1604 directory index within a virtual address.
1608 A bit mask with the bits in the page directory index set to 1 and other
1612 @deftypefun uintptr_t pd_no (const void *@var{va})
1613 @deftypefunx uintptr_t pt_no (const void *@var{va})
1614 Returns the page directory index or page table index, respectively, for
1615 virtual address @var{va}. These functions are defined in
1616 @file{threads/pte.h}.
1619 @deftypefun unsigned pg_ofs (const void *@var{va})
1620 Returns the page offset for virtual address @var{va}. This function is
1621 defined in @file{threads/vaddr.h}.
1624 @node Page Table Entry Format
1625 @subsubsection Page Table Entry Format
1627 You do not need to understand the PTE format to do the Pintos
1628 projects, unless you wish to incorporate the page table into your
1629 supplemental page table (@pxref{Managing the Supplemental Page Table}).
1631 The actual format of a page table entry is summarized below. For
1632 complete information, refer to section 3.7, ``Page Translation Using
1633 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
1637 31 12 11 9 6 5 2 1 0
1638 +---------------------------------------+----+----+-+-+---+-+-+-+
1639 | Physical Address | AVL| |D|A| |U|W|P|
1640 +---------------------------------------+----+----+-+-+---+-+-+-+
1644 Some more information on each bit is given below. The names are
1645 @file{threads/pte.h} macros that represent the bits' values:
1648 Bit 0, the ``present'' bit. When this bit is 1, the
1649 other bits are interpreted as described below. When this bit is 0, any
1650 attempt to access the page will page fault. The remaining bits are then
1651 not used by the CPU and may be used by the OS for any purpose.
1655 Bit 1, the ``read/write'' bit. When it is 1, the page
1656 is writable. When it is 0, write attempts will page fault.
1660 Bit 2, the ``user/supervisor'' bit. When it is 1, user
1661 processes may access the page. When it is 0, only the kernel may access
1662 the page (user accesses will page fault).
1664 Pintos clears this bit in PTEs for kernel virtual memory, to prevent
1665 user processes from accessing them.
1669 Bit 5, the ``accessed'' bit. @xref{Page Table Accessed
1674 Bit 6, the ``dirty'' bit. @xref{Page Table Accessed and
1679 Bits 9@dots{}11, available for operating system use.
1680 Pintos, as provided, does not use them and sets them to 0.
1684 Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
1685 The low 12 bits of the frame's address are always 0.
1688 Other bits are either reserved or uninteresting in a Pintos context and
1689 should be set to@tie{}0.
1691 Header @file{threads/pte.h} defines three functions for working with
1694 @deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
1695 Returns a page table entry that points to @var{page}, which should be a
1696 kernel virtual address. The PTE's present bit will be set. It will be
1697 marked for kernel-only access. If @var{writable} is true, the PTE will
1698 also be marked read/write; otherwise, it will be read-only.
1701 @deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
1702 Returns a page table entry that points to @var{page}, which should be
1703 the kernel virtual address of a frame in the user pool (@pxref{Why
1704 PAL_USER?}). The PTE's present bit will be set and it will be marked to
1705 allow user-mode access. If @var{writable} is true, the PTE will also be
1706 marked read/write; otherwise, it will be read-only.
1709 @deftypefun {void *} pte_get_page (uint32_t @var{pte})
1710 Returns the kernel virtual address for the frame that @var{pte} points
1711 to. The @var{pte} may be present or not-present; if it is not-present
1712 then the pointer return is only meaningful if the proper bits in the PTE
1713 actually represent a physical address.
1716 @node Page Directory Entry Format
1717 @subsubsection Page Directory Entry Format
1719 Page directory entries have the same format as PTEs, except that the
1720 physical address points to a page table page instead of a frame. Header
1721 @file{threads/pte.h} defines two functions for working with page
1724 @deftypefun uint32_t pde_create (uint32_t *@var{pt})
1725 Returns a page directory that points to @var{page}, which should be the
1726 kernel virtual address of a page table page. The PDE's present bit will
1727 be set, it will be marked to allow user-mode access, and it will be
1731 @deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
1732 Returns the kernel virtual address for the page table page that
1733 @var{pde} points to. The @var{pde} must be marked present.
1739 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1740 To use it you will need to manually include its header file,
1741 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}. Intentionally,
1742 no code provided with Pintos uses the hash table, which means that you
1743 are free to use it as is, modify its implementation for your own
1744 purposes, or ignore it, as you wish.
1746 Most implementations of the virtual memory project use a hash table to
1747 translate pages to frames. You may find other uses for hash tables as
1752 * Basic Hash Functions::
1753 * Hash Search Functions::
1754 * Hash Iteration Functions::
1755 * Hash Table Example::
1756 * Hash Auxiliary Data::
1757 * Hash Synchronization::
1760 @node Hash Data Types
1761 @subsection Data Types
1763 A hash table is represented by @struct{hash}.
1765 @deftp {Type} {struct hash}
1766 Represents an entire hash table. The actual members of @struct{hash}
1767 are ``opaque.'' That is, code that uses a hash table should not access
1768 @struct{hash} members directly, nor should it need to. Instead, use
1769 hash table functions and macros.
1772 The hash table operates on elements of type @struct{hash_elem}.
1774 @deftp {Type} {struct hash_elem}
1775 Embed a @struct{hash_elem} member in the structure you want to include
1776 in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
1777 All functions for operating on hash table elements actually take and
1778 return pointers to @struct{hash_elem}, not pointers to your hash table's
1782 You will often need to obtain a @struct{hash_elem}
1783 given a real element of the hash table, and vice versa. Given
1784 a real element of the hash table, obtaining a pointer to its
1785 @struct{hash_elem} is trivial: take the address of the
1786 @struct{hash_elem} member. Use the @code{hash_entry()} macro to go the
1789 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1790 Returns a pointer to the structure that @var{elem}, a pointer to a
1791 @struct{hash_elem}, is embedded within. You must provide @var{type},
1792 the name of the structure that @var{elem} is inside, and @var{member},
1793 the name of the member in @var{type} that @var{elem} points to.
1795 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1796 that points to a @struct{thread} member (of type @struct{hash_elem})
1797 named @code{h_elem}. Then, @code{hash_entry (h, struct thread, h_elem)}
1798 yields the address of the @struct{thread} that @code{h} points within.
1801 Each hash table element must contain a key, that is, data that
1802 identifies and distinguishes elements in the hash table. Every element
1803 in a hash table at a given time must have a unique key. (Elements may
1804 also contain non-key data that need not be unique.) While an element is
1805 in a hash table, its key data must not be changed. For each hash table,
1806 you must write two functions that act on keys: a hash function and a
1807 comparison function. These functions must match the following
1810 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1811 Returns a hash of @var{element}'s data, as a value anywhere in the range
1812 of @code{unsigned int}. The hash of an element should be a
1813 pseudo-random function of the element's key. It must not depend on
1814 non-key data in the element or on any non-constant data other than the
1815 key. Pintos provides the following functions as a suitable basis for
1818 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1819 Returns a hash of the @var{size} bytes starting at @var{buf}. The
1820 implementation is the general-purpose
1821 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1822 hash} for 32-bit words.
1825 @deftypefun unsigned hash_string (const char *@var{s})
1826 Returns a hash of null-terminated string @var{s}.
1829 @deftypefun unsigned hash_int (int @var{i})
1830 Returns a hash of integer @var{i}.
1833 If your key is a single piece of data of an appropriate type, it is
1834 sensible for your hash function to directly return the output of one of
1835 these functions. For multiple pieces of data, you may wish to combine
1836 the output of more than one call to them using, e.g., the @samp{^}
1838 operator. Finally, you may entirely ignore these functions and write
1839 your own hash function from scratch, but remember that your goal is to
1840 build an operating system kernel, not to design a hash function.
1842 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1845 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1846 Compares the keys stored in elements @var{a} and @var{b}. Returns
1847 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1848 or equal to @var{b}.
1850 If two elements compare equal, then they must hash to equal values.
1852 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1855 A few functions that act on hashes accept a pointer to a third kind of
1856 function as an argument:
1858 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1859 Performs some kind of action, chosen by the caller, on @var{element}.
1861 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1864 @node Basic Hash Functions
1865 @subsection Basic Functions
1867 These functions create and destroy hash tables and obtain basic
1868 information about their contents.
1870 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
1871 Initializes @var{hash} as a hash table using @var{hash_func} as hash
1872 function, @var{less_func} as comparison function, and @var{aux} as
1874 Returns true if successful, false on failure. @func{hash_init} calls
1875 @func{malloc} and fails if memory cannot be allocated.
1877 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
1878 most often a null pointer.
1881 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
1882 Removes all the elements from @var{hash}, which must have been
1883 previously initialized with @func{hash_init}.
1885 If @var{action} is non-null, then it is called once for each element in
1886 the hash table, which gives the caller an opportunity to deallocate any
1887 memory or other resources used by the element. For example, if the hash
1888 table elements are dynamically allocated using @func{malloc}, then
1889 @var{action} could @func{free} the element. This is safe because
1890 @func{hash_clear} will not access the memory in a given hash element
1891 after calling @var{action} on it. However, @var{action} must not call
1892 any function that may modify the hash table, such as @func{hash_insert}
1893 or @func{hash_delete}.
1896 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
1897 If @var{action} is non-null, calls it for each element in the hash, with
1898 the same semantics as a call to @func{hash_clear}. Then, frees the
1899 memory held by @var{hash}. Afterward, @var{hash} must not be passed to
1900 any hash table function, absent an intervening call to @func{hash_init}.
1903 @deftypefun size_t hash_size (struct hash *@var{hash})
1904 Returns the number of elements currently stored in @var{hash}.
1907 @deftypefun bool hash_empty (struct hash *@var{hash})
1908 Returns true if @var{hash} currently contains no elements,
1909 false if @var{hash} contains at least one element.
1912 @node Hash Search Functions
1913 @subsection Search Functions
1915 Each of these functions searches a hash table for an element that
1916 compares equal to one provided. Based on the success of the search,
1917 they perform some action, such as inserting a new element into the hash
1918 table, or simply return the result of the search.
1920 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
1921 Searches @var{hash} for an element equal to @var{element}. If none is
1922 found, inserts @var{element} into @var{hash} and returns a null pointer.
1923 If the table already contains an element equal to @var{element}, returns
1924 the existing element without modifying @var{hash}.
1927 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
1928 Inserts @var{element} into @var{hash}. Any element equal to
1929 @var{element} already in @var{hash} is removed. Returns the element
1930 removed, or a null pointer if @var{hash} did not contain an element
1931 equal to @var{element}.
1933 The caller is responsible for deallocating any resources associated with
1934 the element returned, as appropriate. For example, if the hash table
1935 elements are dynamically allocated using @func{malloc}, then the caller
1936 must @func{free} the element after it is no longer needed.
1939 The element passed to the following functions is only used for hashing
1940 and comparison purposes. It is never actually inserted into the hash
1941 table. Thus, only the key data in the element need be initialized, and
1942 other data in the element will not be used. It often makes sense to
1943 declare an instance of the element type as a local variable, initialize
1944 the key data, and then pass the address of its @struct{hash_elem} to
1945 @func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
1946 an example. (Large structures should not be
1947 allocated as local variables. @xref{struct thread}, for more
1950 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
1951 Searches @var{hash} for an element equal to @var{element}. Returns the
1952 element found, if any, or a null pointer otherwise.
1955 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
1956 Searches @var{hash} for an element equal to @var{element}. If one is
1957 found, it is removed from @var{hash} and returned. Otherwise, a null
1958 pointer is returned and @var{hash} is unchanged.
1960 The caller is responsible for deallocating any resources associated with
1961 the element returned, as appropriate. For example, if the hash table
1962 elements are dynamically allocated using @func{malloc}, then the caller
1963 must @func{free} the element after it is no longer needed.
1966 @node Hash Iteration Functions
1967 @subsection Iteration Functions
1969 These functions allow iterating through the elements in a hash table.
1970 Two interfaces are supplied. The first requires writing and supplying a
1971 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
1973 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
1974 Calls @var{action} once for each element in @var{hash}, in arbitrary
1975 order. @var{action} must not call any function that may modify the hash
1976 table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
1977 must not modify key data in elements, although it may modify any other
1981 The second interface is based on an ``iterator'' data type.
1982 Idiomatically, iterators are used as follows:
1985 struct hash_iterator i;
1988 while (hash_next (&i))
1990 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
1991 @r{@dots{}do something with @i{f}@dots{}}
1995 @deftp {Type} {struct hash_iterator}
1996 Represents a position within a hash table. Calling any function that
1997 may modify a hash table, such as @func{hash_insert} or
1998 @func{hash_delete}, invalidates all iterators within that hash table.
2000 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
2003 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
2004 Initializes @var{iterator} to just before the first element in
2008 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
2009 Advances @var{iterator} to the next element in @var{hash}, and returns
2010 that element. Returns a null pointer if no elements remain. After
2011 @func{hash_next} returns null for @var{iterator}, calling it again
2012 yields undefined behavior.
2015 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
2016 Returns the value most recently returned by @func{hash_next} for
2017 @var{iterator}. Yields undefined behavior after @func{hash_first} has
2018 been called on @var{iterator} but before @func{hash_next} has been
2019 called for the first time.
2022 @node Hash Table Example
2023 @subsection Hash Table Example
2025 Suppose you have a structure, called @struct{page}, that you
2026 want to put into a hash table. First, define @struct{page} to include a
2027 @struct{hash_elem} member:
2032 struct hash_elem hash_elem; /* @r{Hash table element.} */
2033 void *addr; /* @r{Virtual address.} */
2034 /* @r{@dots{}other members@dots{}} */
2038 We write a hash function and a comparison function using @var{addr} as
2039 the key. A pointer can be hashed based on its bytes, and the @samp{<}
2040 operator works fine for comparing pointers:
2043 /* @r{Returns a hash value for page @var{p}.} */
2045 page_hash (const struct hash_elem *p_, void *aux UNUSED)
2047 const struct page *p = hash_entry (p_, struct page, hash_elem);
2048 return hash_bytes (&p->addr, sizeof p->addr);
2051 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
2053 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2056 const struct page *a = hash_entry (a_, struct page, hash_elem);
2057 const struct page *b = hash_entry (b_, struct page, hash_elem);
2059 return a->addr < b->addr;
2064 (The use of @code{UNUSED} in these functions' prototypes suppresses a
2065 warning that @var{aux} is unused. @xref{Function and Parameter
2066 Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
2067 Data}, for an explanation of @var{aux}.)
2069 Then, we can create a hash table like this:
2074 hash_init (&pages, page_hash, page_less, NULL);
2077 Now we can manipulate the hash table we've created. If @code{@var{p}}
2078 is a pointer to a @struct{page}, we can insert it into the hash table
2082 hash_insert (&pages, &p->hash_elem);
2085 @noindent If there's a chance that @var{pages} might already contain a
2086 page with the same @var{addr}, then we should check @func{hash_insert}'s
2089 To search for an element in the hash table, use @func{hash_find}. This
2090 takes a little setup, because @func{hash_find} takes an element to
2091 compare against. Here's a function that will find and return a page
2092 based on a virtual address, assuming that @var{pages} is defined at file
2096 /* @r{Returns the page containing the given virtual @var{address},
2097 or a null pointer if no such page exists.} */
2099 page_lookup (const void *address)
2102 struct hash_elem *e;
2105 e = hash_find (&pages, &p.hash_elem);
2106 return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
2111 @struct{page} is allocated as a local variable here on the assumption
2112 that it is fairly small. Large structures should not be allocated as
2113 local variables. @xref{struct thread}, for more information.
2115 A similar function could delete a page by address using
2118 @node Hash Auxiliary Data
2119 @subsection Auxiliary Data
2121 In simple cases like the example above, there's no need for the
2122 @var{aux} parameters. In these cases, just pass a null pointer to
2123 @func{hash_init} for @var{aux} and ignore the values passed to the hash
2124 function and comparison functions. (You'll get a compiler warning if
2125 you don't use the @var{aux} parameter, but you can turn that off with
2126 the @code{UNUSED} macro, as shown in the example, or you can just ignore
2129 @var{aux} is useful when you have some property of the data in the
2130 hash table that's both constant and needed for hashing or comparisons,
2131 but which is not stored in the data items themselves. For example, if
2132 the items in a hash table contain fixed-length strings, but the items
2133 themselves don't indicate what that fixed length is, you could pass
2134 the length as an @var{aux} parameter.
2136 @node Hash Synchronization
2137 @subsection Synchronization
2139 The hash table does not do any internal synchronization. It is the
2140 caller's responsibility to synchronize calls to hash table functions.
2141 In general, any number of functions that examine but do not modify the
2142 hash table, such as @func{hash_find} or @func{hash_next}, may execute
2143 simultaneously. However, these function cannot safely execute at the
2144 same time as any function that may modify a given hash table, such as
2145 @func{hash_insert} or @func{hash_delete}, nor may more than one function
2146 that can modify a given hash table execute safely at once.
2148 It is also the caller's responsibility to synchronize access to data in
2149 hash table elements. How to synchronize access to this data depends on
2150 how it is designed and organized, as with any other data structure.