2 @appendix Reference Guide
4 This chapter is a reference for the Pintos code. The reference guide
5 does not cover all of the code in Pintos, but it does cover those
6 pieces that students most often find troublesome. You may find that
7 you want to read each part of the reference guide as you work on the
8 project where it becomes important.
10 We recommend using ``tags'' to follow along with references to function
11 and variable names (@pxref{Tags}).
17 * Interrupt Handling::
27 This section covers the Pintos loader and basic kernel
32 * Kernel Initialization::
33 * Physical Memory Map::
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 stored in 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 The first step in @func{main} is to call @func{bss_init}, which clears
128 out the kernel's ``BSS'', which is the traditional name for 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.
136 Next, @func{main} calls @func{read_command_line} to break the kernel command
137 line into arguments, then @func{parse_options} to read any options at
138 the beginning of the command line. (Actions specified on the
139 command line execute later.)
141 @func{thread_init} initializes the thread system. We will defer full
142 discussion to our discussion of Pintos threads below. It is called so
143 early in initialization because a valid thread structure is a
144 prerequisite for acquiring a lock, and lock acquisition in turn is
145 important to other Pintos subsystems. Then we initialize the console
146 and print a startup message to the console.
148 The next block of functions we call initializes the kernel's memory
149 system. @func{palloc_init} sets up the kernel page allocator, which
150 doles out memory one or more pages at a time (@pxref{Page Allocator}).
151 @func{malloc_init} sets
152 up the allocator that handles allocations of arbitrary-size blocks of
153 memory (@pxref{Block Allocator}).
154 @func{paging_init} sets up a page table for the kernel (@pxref{Page
157 In projects 2 and later, @func{main} also calls @func{tss_init} and
160 The next set of calls initializes the interrupt system.
161 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
162 (IDT) to ready it for interrupt handling (@pxref{Interrupt
163 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
164 handling timer interrupts and keyboard interrupts, respectively.
165 @func{input_init} sets up to merge serial and keyboard input into one
167 projects 2 and later, we also prepare to handle interrupts caused by
168 user programs using @func{exception_init} and @func{syscall_init}.
170 Now that interrupts are set up, we can start the scheduler
171 with @func{thread_start}, which creates the idle thread and enables
173 With interrupts enabled, interrupt-driven serial port I/O becomes
175 @func{serial_init_queue} to switch to that mode. Finally,
176 @func{timer_calibrate} calibrates the timer for accurate short delays.
178 If the file system is compiled in, as it will starting in project 2, we
179 initialize the IDE disks with @func{ide_init}, then the
180 file system with @func{filesys_init}.
182 Boot is complete, so we print a message.
184 Function @func{run_actions} now parses and executes actions specified on
185 the kernel command line, such as @command{run} to run a test (in project
186 1) or a user program (in later projects).
188 Finally, if @option{-q} was specified on the kernel command line, we
189 call @func{power_off} to terminate the machine simulator. Otherwise,
190 @func{main} calls @func{thread_exit}, which allows any other running
191 threads to continue running.
193 @node Physical Memory Map
194 @subsection Physical Memory Map
196 @multitable {@t{00000000}--@t{00000000}} {Hardware} {Some much longer explanatory text}
197 @headitem Memory Range
201 @item @t{00000000}--@t{000003ff} @tab CPU @tab Real mode interrupt table.
202 @item @t{00000400}--@t{000005ff} @tab BIOS @tab Miscellaneous data area.
203 @item @t{00000600}--@t{00007bff} @tab --- @tab ---
204 @item @t{00007c00}--@t{00007dff} @tab Pintos @tab Loader.
205 @item @t{0000e000}--@t{0000efff} @tab Pintos
206 @tab Stack for loader; kernel stack and @struct{thread} for initial
208 @item @t{0000f000}--@t{0000ffff} @tab Pintos
209 @tab Page directory for startup code.
210 @item @t{00010000}--@t{00020000} @tab Pintos
211 @tab Page tables for startup code.
212 @item @t{00020000}--@t{0009ffff} @tab Pintos
213 @tab Kernel code, data, and uninitialized data segments.
214 @item @t{000a0000}--@t{000bffff} @tab Video @tab VGA display memory.
215 @item @t{000c0000}--@t{000effff} @tab Hardware
216 @tab Reserved for expansion card RAM and ROM.
217 @item @t{000f0000}--@t{000fffff} @tab BIOS @tab ROM BIOS.
218 @item @t{00100000}--@t{03ffffff} @tab Pintos @tab Dynamic memory allocation.
231 @subsection @code{struct thread}
233 The main Pintos data structure for threads is @struct{thread},
234 declared in @file{threads/thread.h}.
236 @deftp {Structure} {struct thread}
237 Represents a thread or a user process. In the projects, you will have
238 to add your own members to @struct{thread}. You may also change or
239 delete the definitions of existing members.
241 Every @struct{thread} occupies the beginning of its own page of
242 memory. The rest of the page is used for the thread's stack, which
243 grows downward from the end of the page. It looks like this:
247 4 kB +---------------------------------+
261 sizeof (struct thread) +---------------------------------+
267 0 kB +---------------------------------+
271 This has two consequences. First, @struct{thread} must not be allowed
272 to grow too big. If it does, then there will not be enough room for the
273 kernel stack. The base @struct{thread} is only a few bytes in size. It
274 probably should stay well under 1 kB.
276 Second, kernel stacks must not be allowed to grow too large. If a stack
277 overflows, it will corrupt the thread state. Thus, kernel functions
278 should not allocate large structures or arrays as non-static local
279 variables. Use dynamic allocation with @func{malloc} or
280 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
283 @deftypecv {Member} {@struct{thread}} {tid_t} tid
284 The thread's thread identifier or @dfn{tid}. Every thread must have a
285 tid that is unique over the entire lifetime of the kernel. By
286 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
287 thread receives the numerically next higher tid, starting from 1 for
288 the initial process. You can change the type and the numbering scheme
292 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
293 @anchor{Thread States}
294 The thread's state, one of the following:
296 @defvr {Thread State} @code{THREAD_RUNNING}
297 The thread is running. Exactly one thread is running at a given time.
298 @func{thread_current} returns the running thread.
301 @defvr {Thread State} @code{THREAD_READY}
302 The thread is ready to run, but it's not running right now. The
303 thread could be selected to run the next time the scheduler is
304 invoked. Ready threads are kept in a doubly linked list called
308 @defvr {Thread State} @code{THREAD_BLOCKED}
309 The thread is waiting for something, e.g.@: a lock to become
310 available, an interrupt to be invoked. The thread won't be scheduled
311 again until it transitions to the @code{THREAD_READY} state with a
312 call to @func{thread_unblock}. This is most conveniently done
313 indirectly, using one of the Pintos synchronization primitives that
314 block and unblock threads automatically (@pxref{Synchronization}).
316 There is no @i{a priori} way to tell what a blocked thread is waiting
317 for, but a backtrace can help (@pxref{Backtraces}).
320 @defvr {Thread State} @code{THREAD_DYING}
321 The thread will be destroyed by the scheduler after switching to the
326 @deftypecv {Member} {@struct{thread}} {char} name[16]
327 The thread's name as a string, or at least the first few characters of
331 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
332 Every thread has its own stack to keep track of its state. When the
333 thread is running, the CPU's stack pointer register tracks the top of
334 the stack and this member is unused. But when the CPU switches to
335 another thread, this member saves the thread's stack pointer. No
336 other members are needed to save the thread's registers, because the
337 other registers that must be saved are saved on the stack.
339 When an interrupt occurs, whether in the kernel or a user program, an
340 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
341 in a user program, the @struct{intr_frame} is always at the very top of
342 the page. @xref{Interrupt Handling}, for more information.
345 @deftypecv {Member} {@struct{thread}} {int} priority
346 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
347 (63). Lower numbers correspond to lower priorities, so that
348 priority 0 is the lowest priority and priority 63 is the highest.
349 Pintos as provided ignores thread priorities, but you will implement
350 priority scheduling in project 1 (@pxref{Priority Scheduling}).
353 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
354 A ``list element'' used to put the thread into doubly linked lists,
355 either @code{ready_list} (the list of threads ready to run) or a list of
356 threads waiting on a semaphore in @func{sema_down}. It can do double
357 duty because a thread waiting on a semaphore is not ready, and vice
361 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
362 Only present in project 2 and later. @xref{Page Tables}.
365 @deftypecv {Member} {@struct{thread}} {unsigned} magic
366 Always set to @code{THREAD_MAGIC}, which is just an arbitrary number defined
367 in @file{threads/thread.c}, and used to detect stack overflow.
368 @func{thread_current} checks that the @code{magic} member of the running
369 thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
370 tends to change this value, triggering the assertion. For greatest
371 benefit, as you add members to @struct{thread}, leave @code{magic} at
375 @node Thread Functions
376 @subsection Thread Functions
378 @file{threads/thread.c} implements several public functions for thread
379 support. Let's take a look at the most useful:
381 @deftypefun void thread_init (void)
382 Called by @func{main} to initialize the thread system. Its main
383 purpose is to create a @struct{thread} for Pintos's initial thread.
384 This is possible because the Pintos loader puts the initial
385 thread's stack at the top of a page, in the same position as any other
388 Before @func{thread_init} runs,
389 @func{thread_current} will fail because the running thread's
390 @code{magic} value is incorrect. Lots of functions call
391 @func{thread_current} directly or indirectly, including
392 @func{lock_acquire} for locking a lock, so @func{thread_init} is
393 called early in Pintos initialization.
396 @deftypefun void thread_start (void)
397 Called by @func{main} to start the scheduler. Creates the idle
398 thread, that is, the thread that is scheduled when no other thread is
399 ready. Then enables interrupts, which as a side effect enables the
400 scheduler because the scheduler runs on return from the timer interrupt, using
401 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
404 @deftypefun void thread_tick (void)
405 Called by the timer interrupt at each timer tick. It keeps track of
406 thread statistics and triggers the scheduler when a time slice expires.
409 @deftypefun void thread_print_stats (void)
410 Called during Pintos shutdown to print thread statistics.
413 @deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
414 Creates and starts a new thread named @var{name} with the given
415 @var{priority}, returning the new thread's tid. The thread executes
416 @var{func}, passing @var{aux} as the function's single argument.
418 @func{thread_create} allocates a page for the thread's
419 @struct{thread} and stack and initializes its members, then it sets
420 up a set of fake stack frames for it (@pxref{Thread Switching}). The
421 thread is initialized in the blocked state, then unblocked just before
422 returning, which allows the new thread to
423 be scheduled (@pxref{Thread States}).
425 @deftp {Type} {void thread_func (void *@var{aux})}
426 This is the type of the function passed to @func{thread_create}, whose
427 @var{aux} argument is passed along as the function's argument.
431 @deftypefun void thread_block (void)
432 Transitions the running thread from the running state to the blocked
433 state (@pxref{Thread States}). The thread will not run again until
434 @func{thread_unblock} is
435 called on it, so you'd better have some way arranged for that to happen.
436 Because @func{thread_block} is so low-level, you should prefer to use
437 one of the synchronization primitives instead (@pxref{Synchronization}).
440 @deftypefun void thread_unblock (struct thread *@var{thread})
441 Transitions @var{thread}, which must be in the blocked state, to the
442 ready state, allowing it to resume running (@pxref{Thread States}).
443 This is called when the event that the thread is waiting for occurs,
444 e.g.@: when the lock that
445 the thread is waiting on becomes available.
448 @deftypefun {struct thread *} thread_current (void)
449 Returns the running thread.
452 @deftypefun {tid_t} thread_tid (void)
453 Returns the running thread's thread id. Equivalent to
454 @code{thread_current ()->tid}.
457 @deftypefun {const char *} thread_name (void)
458 Returns the running thread's name. Equivalent to @code{thread_current
462 @deftypefun void thread_exit (void) @code{NO_RETURN}
463 Causes the current thread to exit. Never returns, hence
464 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
467 @deftypefun void thread_yield (void)
468 Yields the CPU to the scheduler, which picks a new thread to run. The
469 new thread might be the current thread, so you can't depend on this
470 function to keep this thread from running for any particular length of
474 @deftypefun int thread_get_priority (void)
475 @deftypefunx void thread_set_priority (int @var{new_priority})
476 Stub to set and get thread priority. @xref{Priority Scheduling}.
479 @deftypefun int thread_get_nice (void)
480 @deftypefunx void thread_set_nice (int @var{new_nice})
481 @deftypefunx int thread_get_recent_cpu (void)
482 @deftypefunx int thread_get_load_avg (void)
483 Stubs for the advanced scheduler. @xref{4.4BSD Scheduler}.
486 @node Thread Switching
487 @subsection Thread Switching
489 @func{schedule} is responsible for switching threads. It
490 is internal to @file{threads/thread.c} and called only by the three
491 public thread functions that need to switch threads:
492 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
493 Before any of these functions call @func{schedule}, they disable
494 interrupts (or ensure that they are already disabled) and then change
495 the running thread's state to something other than running.
497 @func{schedule} is short but tricky. It records the
498 current thread in local variable @var{cur}, determines the next thread
499 to run as local variable @var{next} (by calling
500 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
501 the actual thread switch. The thread we switched to was also running
502 inside @func{switch_threads}, as are all the threads not currently
503 running, so the new thread now returns out of
504 @func{switch_threads}, returning the previously running thread.
506 @func{switch_threads} is an assembly language routine in
507 @file{threads/switch.S}. It saves registers on the stack, saves the
508 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
509 member, restores the new thread's @code{stack} into the CPU's stack
510 pointer, restores registers from the stack, and returns.
512 The rest of the scheduler is implemented in @func{schedule_tail}. It
513 marks the new thread as running. If the thread we just switched from
514 is in the dying state, then it also frees the page that contained the
515 dying thread's @struct{thread} and stack. These couldn't be freed
516 prior to the thread switch because the switch needed to use it.
518 Running a thread for the first time is a special case. When
519 @func{thread_create} creates a new thread, it goes through a fair
520 amount of trouble to get it started properly. In particular, the new
521 thread hasn't started running yet, so there's no way for it to be
522 running inside @func{switch_threads} as the scheduler expects. To
523 solve the problem, @func{thread_create} creates some fake stack frames
524 in the new thread's stack:
528 The topmost fake stack frame is for @func{switch_threads}, represented
529 by @struct{switch_threads_frame}. The important part of this frame is
530 its @code{eip} member, the return address. We point @code{eip} to
531 @func{switch_entry}, indicating it to be the function that called
535 The next fake stack frame is for @func{switch_entry}, an assembly
536 language routine in @file{threads/switch.S} that adjusts the stack
537 pointer,@footnote{This is because @func{switch_threads} takes
538 arguments on the stack and the 80@var{x}86 SVR4 calling convention
539 requires the caller, not the called function, to remove them when the
540 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
541 calls @func{schedule_tail} (this special case is why
542 @func{schedule_tail} is separate from @func{schedule}), and returns.
543 We fill in its stack frame so that it returns into
544 @func{kernel_thread}, a function in @file{threads/thread.c}.
547 The final stack frame is for @func{kernel_thread}, which enables
548 interrupts and calls the thread's function (the function passed to
549 @func{thread_create}). If the thread's function returns, it calls
550 @func{thread_exit} to terminate the thread.
553 @node Synchronization
554 @section Synchronization
556 If sharing of resources between threads is not handled in a careful,
557 controlled fashion, the result is usually a big mess.
558 This is especially the case in operating system kernels, where
559 faulty sharing can crash the entire machine. Pintos provides several
560 synchronization primitives to help out.
563 * Disabling Interrupts::
567 * Optimization Barriers::
570 @node Disabling Interrupts
571 @subsection Disabling Interrupts
573 The crudest way to do synchronization is to disable interrupts, that
574 is, to temporarily prevent the CPU from responding to interrupts. If
575 interrupts are off, no other thread will preempt the running thread,
576 because thread preemption is driven by the timer interrupt. If
577 interrupts are on, as they normally are, then the running thread may
578 be preempted by another at any time, whether between two C statements
579 or even within the execution of one.
581 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
582 is, kernel threads can be preempted at any time. Traditional Unix
583 systems are ``nonpreemptible,'' that is, kernel threads can only be
584 preempted at points where they explicitly call into the scheduler.
585 (User programs can be preempted at any time in both models.) As you
586 might imagine, preemptible kernels require more explicit
589 You should have little need to set the interrupt state directly. Most
590 of the time you should use the other synchronization primitives
591 described in the following sections. The main reason to disable
592 interrupts is to synchronize kernel threads with external interrupt
593 handlers, which cannot sleep and thus cannot use most other forms of
594 synchronization (@pxref{External Interrupt Handling}).
596 Some external interrupts cannot be postponed, even by disabling
597 interrupts. These interrupts, called @dfn{non-maskable interrupts}
598 (NMIs), are supposed to be used only in emergencies, e.g.@: when the
599 computer is on fire. Pintos does not handle non-maskable interrupts.
601 Types and functions for disabling and enabling interrupts are in
602 @file{threads/interrupt.h}.
604 @deftp Type {enum intr_level}
605 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
606 disabled or enabled, respectively.
609 @deftypefun {enum intr_level} intr_get_level (void)
610 Returns the current interrupt state.
613 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
614 Turns interrupts on or off according to @var{level}. Returns the
615 previous interrupt state.
618 @deftypefun {enum intr_level} intr_enable (void)
619 Turns interrupts on. Returns the previous interrupt state.
622 @deftypefun {enum intr_level} intr_disable (void)
623 Turns interrupts off. Returns the previous interrupt state.
627 @subsection Semaphores
629 A @dfn{semaphore} is a nonnegative integer together with two operators
630 that manipulate it atomically, which are:
634 ``Down'' or ``P'': wait for the value to become positive, then
638 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
642 A semaphore initialized to 0 may be used to wait for an event
643 that will happen exactly once. For example, suppose thread @var{A}
644 starts another thread @var{B} and wants to wait for @var{B} to signal
645 that some activity is complete. @var{A} can create a semaphore
646 initialized to 0, pass it to @var{B} as it starts it, and then
647 ``down'' the semaphore. When @var{B} finishes its activity, it
648 ``ups'' the semaphore. This works regardless of whether @var{A}
649 ``downs'' the semaphore or @var{B} ``ups'' it first.
651 A semaphore initialized to 1 is typically used for controlling access
652 to a resource. Before a block of code starts using the resource, it
653 ``downs'' the semaphore, then after it is done with the resource it
654 ``ups'' the resource. In such a case a lock, described below, may be
657 Semaphores can also be initialized to values larger than 1. These are
660 Semaphores were invented by Edsger Dijkstra and first used in the THE
661 operating system (@bibref{Dijkstra}).
663 Pintos' semaphore type and operations are declared in
664 @file{threads/synch.h}.
666 @deftp {Type} {struct semaphore}
667 Represents a semaphore.
670 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
671 Initializes @var{sema} as a new semaphore with the given initial
675 @deftypefun void sema_down (struct semaphore *@var{sema})
676 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
677 its value to become positive and then decrementing it by one.
680 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
681 Tries to execute the ``down'' or ``P'' operation on @var{sema},
682 without waiting. Returns true if @var{sema}
683 was successfully decremented, or false if it was already
684 zero and thus could not be decremented without waiting. Calling this
686 tight loop wastes CPU time, so use @func{sema_down} or find a
687 different approach instead.
690 @deftypefun void sema_up (struct semaphore *@var{sema})
691 Executes the ``up'' or ``V'' operation on @var{sema},
692 incrementing its value. If any threads are waiting on
693 @var{sema}, wakes one of them up.
695 Unlike most synchronization primitives, @func{sema_up} may be called
696 inside an external interrupt handler (@pxref{External Interrupt
700 Semaphores are internally built out of disabling interrupt
701 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
702 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
703 a list of waiting threads, using the linked list
704 implementation in @file{lib/kernel/list.c}.
709 A @dfn{lock} is like a semaphore with an initial value of 1
710 (@pxref{Semaphores}). A lock's equivalent of ``up'' is called
711 ``release'', and the ``down'' operation is called ``acquire''.
713 Compared to a semaphore, a lock has one added restriction: only the
714 thread that acquires a lock, called the lock's ``owner'', is allowed to
715 release it. If this restriction is a problem, it's a good sign that a
716 semaphore should be used, instead of a lock.
718 Locks in Pintos are not ``recursive,'' that is, it is an error for the
719 thread currently holding a lock to try to acquire that lock.
721 Lock types and functions are declared in @file{threads/synch.h}.
723 @deftp {Type} {struct lock}
727 @deftypefun void lock_init (struct lock *@var{lock})
728 Initializes @var{lock} as a new lock.
729 The lock is not initially owned by any thread.
732 @deftypefun void lock_acquire (struct lock *@var{lock})
733 Acquires @var{lock} for the current thread, first waiting for
734 any current owner to release it if necessary.
737 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
738 Tries to acquire @var{lock} for use by the current thread, without
739 waiting. Returns true if successful, false if the lock is already
740 owned. Calling this function in a tight loop is a bad idea because it
741 wastes CPU time, so use @func{lock_acquire} instead.
744 @deftypefun void lock_release (struct lock *@var{lock})
745 Releases @var{lock}, which the current thread must own.
748 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
749 Returns true if the running thread owns @var{lock},
751 There is no function to test whether an arbitrary thread owns a lock,
752 because the answer could change before the caller could act on it.
758 A @dfn{monitor} is a higher-level form of synchronization than a
759 semaphore or a lock. A monitor consists of data being synchronized,
760 plus a lock, called the @dfn{monitor lock}, and one or more
761 @dfn{condition variables}. Before it accesses the protected data, a
762 thread first acquires the monitor lock. It is then said to be ``in the
763 monitor''. While in the monitor, the thread has control over all the
764 protected data, which it may freely examine or modify. When access to
765 the protected data is complete, it releases the monitor lock.
767 Condition variables allow code in the monitor to wait for a condition to
768 become true. Each condition variable is associated with an abstract
769 condition, e.g.@: ``some data has arrived for processing'' or ``over 10
770 seconds has passed since the user's last keystroke''. When code in the
771 monitor needs to wait for a condition to become true, it ``waits'' on
772 the associated condition variable, which releases the lock and waits for
773 the condition to be signaled. If, on the other hand, it has caused one
774 of these conditions to become true, it ``signals'' the condition to wake
775 up one waiter, or ``broadcasts'' the condition to wake all of them.
777 The theoretical framework for monitors was laid out by C.@: A.@: R.@:
778 Hoare (@bibref{Hoare}). Their practical usage was later elaborated in a
779 paper on the Mesa operating system (@bibref{Lampson}).
781 Condition variable types and functions are declared in
782 @file{threads/synch.h}.
784 @deftp {Type} {struct condition}
785 Represents a condition variable.
788 @deftypefun void cond_init (struct condition *@var{cond})
789 Initializes @var{cond} as a new condition variable.
792 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
793 Atomically releases @var{lock} (the monitor lock) and waits for
794 @var{cond} to be signaled by some other piece of code. After
795 @var{cond} is signaled, reacquires @var{lock} before returning.
796 @var{lock} must be held before calling this function.
798 Sending a signal and waking up from a wait are not an atomic operation.
799 Thus, typically @func{cond_wait}'s caller must recheck the condition
800 after the wait completes and, if necessary, wait again. See the next
801 section for an example.
804 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
805 If any threads are waiting on @var{cond} (protected by monitor lock
806 @var{lock}), then this function wakes up one of them. If no threads are
807 waiting, returns without performing any action.
808 @var{lock} must be held before calling this function.
811 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
812 Wakes up all threads, if any, waiting on @var{cond} (protected by
813 monitor lock @var{lock}). @var{lock} must be held before calling this
817 @subsubsection Monitor Example
819 The classical example of a monitor is handling a buffer into which one
821 ``producer'' threads write characters and out of which one or more
822 ``consumer'' threads read characters. To implement this we need,
823 besides the monitor lock, two condition variables which we will call
824 @var{not_full} and @var{not_empty}:
827 char buf[BUF_SIZE]; /* @r{Buffer.} */
828 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
829 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
830 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
831 struct lock lock; /* @r{Monitor lock.} */
832 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
833 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
835 @dots{}@r{initialize the locks and condition variables}@dots{}
837 void put (char ch) @{
838 lock_acquire (&lock);
839 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
840 cond_wait (¬_full, &lock);
841 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
843 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
844 lock_release (&lock);
849 lock_acquire (&lock);
850 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
851 cond_wait (¬_empty, &lock);
852 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
854 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
855 lock_release (&lock);
859 Note that @code{BUF_SIZE} must divide evenly into @code{SIZE_MAX + 1}
860 for the above code to be completely correct. Otherwise, it will fail
861 the first time @code{head} wraps around to 0. In practice,
862 @code{BUF_SIZE} would ordinarily be a power of 2.
864 @node Optimization Barriers
865 @subsection Optimization Barriers
867 @c We should try to come up with a better example.
868 @c Perhaps something with a linked list?
870 An @dfn{optimization barrier} is a special statement that prevents the
871 compiler from making assumptions about the state of memory across the
872 barrier. The compiler will not reorder reads or writes of variables
873 across the barrier or assume that a variable's value is unmodified
874 across the barrier, except for local variables whose address is never
875 taken. In Pintos, @file{threads/synch.h} defines the @code{barrier()}
876 macro as an optimization barrier.
878 One reason to use an optimization barrier is when data can change
879 asynchronously, without the compiler's knowledge, e.g.@: by another
880 thread or an interrupt handler. The @func{too_many_loops} function in
881 @file{devices/timer.c} is an example. This function starts out by
882 busy-waiting in a loop until a timer tick occurs:
885 /* Wait for a timer tick. */
886 int64_t start = ticks;
887 while (ticks == start)
892 Without an optimization barrier in the loop, the compiler could
893 conclude that the loop would never terminate, because @code{start} and
894 @code{ticks} start out equal and the loop itself never changes them.
895 It could then ``optimize'' the function into an infinite loop, which
896 would definitely be undesirable.
898 Optimization barriers can be used to avoid other compiler
899 optimizations. The @func{busy_wait} function, also in
900 @file{devices/timer.c}, is an example. It contains this loop:
908 The goal of this loop is to busy-wait by counting @code{loops} down
909 from its original value to 0. Without the barrier, the compiler could
910 delete the loop entirely, because it produces no useful output and has
911 no side effects. The barrier forces the compiler to pretend that the
912 loop body has an important effect.
914 Finally, optimization barriers can be used to force the ordering of
915 memory reads or writes. For example, suppose we add a ``feature''
916 that, whenever a timer interrupt occurs, the character in global
917 variable @code{timer_put_char} is printed on the console, but only if
918 global Boolean variable @code{timer_do_put} is true. The best way to
919 set up @samp{x} to be printed is then to use an optimization barrier,
923 timer_put_char = 'x';
928 Without the barrier, the code is buggy because the compiler is free to
929 reorder operations when it doesn't see a reason to keep them in the
930 same order. In this case, the compiler doesn't know that the order of
931 assignments is important, so its optimizer is permitted to exchange
932 their order. There's no telling whether it will actually do this, and
933 it is possible that passing the compiler different optimization flags
934 or using a different version of the compiler will produce different
937 Another solution is to disable interrupts around the assignments.
938 This does not prevent reordering, but it prevents the interrupt
939 handler from intervening between the assignments. It also has the
940 extra runtime cost of disabling and re-enabling interrupts:
943 enum intr_level old_level = intr_disable ();
944 timer_put_char = 'x';
946 intr_set_level (old_level);
949 A second solution is to mark the declarations of
950 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
951 keyword tells the compiler that the variables are externally observable
952 and restricts its latitude for optimization. However, the semantics of
953 @samp{volatile} are not well-defined, so it is not a good general
954 solution. The base Pintos code does not use @samp{volatile} at all.
956 The following is @emph{not} a solution, because locks neither prevent
957 interrupts nor prevent the compiler from reordering the code within the
958 region where the lock is held:
961 lock_acquire (&timer_lock); /* INCORRECT CODE */
962 timer_put_char = 'x';
964 lock_release (&timer_lock);
967 The compiler treats invocation of any function defined externally,
968 that is, in another source file, as a limited form of optimization
969 barrier. Specifically, the compiler assumes that any externally
970 defined function may access any statically or dynamically allocated
971 data and any local variable whose address is taken. This often means
972 that explicit barriers can be omitted. It is one reason that Pintos
973 contains few explicit barriers.
975 A function defined in the same source file, or in a header included by
976 the source file, cannot be relied upon as a optimization barrier.
977 This applies even to invocation of a function before its
978 definition, because the compiler may read and parse the entire source
979 file before performing optimization.
981 @node Interrupt Handling
982 @section Interrupt Handling
984 An @dfn{interrupt} notifies the CPU of some event. Much of the work
985 of an operating system relates to interrupts in one way or another.
986 For our purposes, we classify interrupts into two broad categories:
990 @dfn{Internal interrupts}, that is, interrupts caused directly by CPU
991 instructions. System calls, attempts at invalid memory access
992 (@dfn{page faults}), and attempts to divide by zero are some activities
993 that cause internal interrupts. Because they are caused by CPU
994 instructions, internal interrupts are @dfn{synchronous} or synchronized
995 with CPU instructions. @func{intr_disable} does not disable internal
999 @dfn{External interrupts}, that is, interrupts originating outside the
1000 CPU. These interrupts come from hardware devices such as the system
1001 timer, keyboard, serial ports, and disks. External interrupts are
1002 @dfn{asynchronous}, meaning that their delivery is not
1003 synchronized with instruction execution. Handling of external interrupts
1004 can be postponed with @func{intr_disable} and related functions
1005 (@pxref{Disabling Interrupts}).
1008 The CPU treats both classes of interrupts largely the same way,
1009 so Pintos has common infrastructure to handle both classes.
1010 The following section describes this
1011 common infrastructure. The sections after that give the specifics of
1012 external and internal interrupts.
1014 If you haven't already read chapter 3, ``Basic Execution Environment,''
1015 in @bibref{IA32-v1}, it is recommended that you do so now. You might
1016 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
1020 * Interrupt Infrastructure::
1021 * Internal Interrupt Handling::
1022 * External Interrupt Handling::
1025 @node Interrupt Infrastructure
1026 @subsection Interrupt Infrastructure
1028 When an interrupt occurs, the CPU saves
1029 its most essential state on a stack and jumps to an interrupt
1030 handler routine. The 80@var{x}86 architecture supports 256
1031 interrupts, numbered 0 through 255, each with an independent
1032 handler defined in an array called the @dfn{interrupt
1033 descriptor table} or IDT.
1035 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
1036 IDT so that each entry points to a unique entry point in
1037 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
1038 @var{NN} is the interrupt number in
1039 hexadecimal. Because the CPU doesn't give
1040 us any other way to find out the interrupt number, this entry point
1041 pushes the interrupt number on the stack. Then it jumps to
1042 @func{intr_entry}, which pushes all the registers that the processor
1043 didn't already push for us, and then calls @func{intr_handler}, which
1044 brings us back into C in @file{threads/interrupt.c}.
1046 The main job of @func{intr_handler} is to call the function
1047 registered for handling the particular interrupt. (If no
1048 function is registered, it dumps some information to the console and
1049 panics.) It also does some extra processing for external
1050 interrupts (@pxref{External Interrupt Handling}).
1052 When @func{intr_handler} returns, the assembly code in
1053 @file{threads/intr-stubs.S} restores all the CPU registers saved
1054 earlier and directs the CPU to return from the interrupt.
1056 The following types and functions are common to all
1059 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
1060 This is how an interrupt handler function must be declared. Its @var{frame}
1061 argument (see below) allows it to determine the cause of the interrupt
1062 and the state of the thread that was interrupted.
1065 @deftp {Type} {struct intr_frame}
1066 The stack frame of an interrupt handler, as saved by the CPU, the interrupt
1067 stubs, and @func{intr_entry}. Its most interesting members are described
1071 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
1072 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
1073 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
1074 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
1075 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
1076 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1077 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1078 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1079 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1080 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1081 Register values in the interrupted thread, pushed by @func{intr_entry}.
1082 The @code{esp_dummy} value isn't actually used (refer to the
1083 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1086 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1087 The interrupt vector number, ranging from 0 to 255.
1090 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1091 The ``error code'' pushed on the stack by the CPU for some internal
1095 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1096 The address of the next instruction to be executed by the interrupted
1100 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1101 The interrupted thread's stack pointer.
1104 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1105 Returns the name of the interrupt numbered @var{vec}, or
1106 @code{"unknown"} if the interrupt has no registered name.
1109 @node Internal Interrupt Handling
1110 @subsection Internal Interrupt Handling
1112 Internal interrupts are caused directly by CPU instructions executed by
1113 the running kernel thread or user process (from project 2 onward). An
1114 internal interrupt is therefore said to arise in a ``process context.''
1116 In an internal interrupt's handler, it can make sense to examine the
1117 @struct{intr_frame} passed to the interrupt handler, or even to modify
1118 it. When the interrupt returns, modifications in @struct{intr_frame}
1119 become changes to the calling thread or process's state. For example,
1120 the Pintos system call handler returns a value to the user program by
1121 modifying the saved EAX register (@pxref{System Call Details}).
1123 There are no special restrictions on what an internal interrupt
1124 handler can or can't do. Generally they should run with interrupts
1125 enabled, just like other code, and so they can be preempted by other
1126 kernel threads. Thus, they do need to synchronize with other threads
1127 on shared data and other resources (@pxref{Synchronization}).
1129 Internal interrupt handlers can be invoked recursively. For example,
1130 the system call handler might cause a page fault while attempting to
1131 read user memory. Deep recursion would risk overflowing the limited
1132 kernel stack (@pxref{struct thread}), but should be unnecessary.
1134 @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})
1135 Registers @var{handler} to be called when internal interrupt numbered
1136 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1139 If @var{level} is @code{INTR_ON}, external interrupts will be processed
1140 normally during the interrupt handler's execution, which is normally
1141 desirable. Specifying @code{INTR_OFF} will cause the CPU to disable
1142 external interrupts when it invokes the interrupt handler. The effect
1143 is slightly different from calling @func{intr_disable} inside the
1144 handler, because that leaves a window of one or more CPU instructions in
1145 which external interrupts are still enabled. This is important for the
1146 page fault handler; refer to the comments in @file{userprog/exception.c}
1149 @var{dpl} determines how the interrupt can be invoked. If @var{dpl} is
1150 0, then the interrupt can be invoked only by kernel threads. Otherwise
1151 @var{dpl} should be 3, which allows user processes to invoke the
1152 interrupt with an explicit INT instruction. The value of @var{dpl}
1153 doesn't affect user processes' ability to invoke the interrupt
1154 indirectly, e.g.@: an invalid memory reference will cause a page fault
1155 regardless of @var{dpl}.
1158 @node External Interrupt Handling
1159 @subsection External Interrupt Handling
1161 External interrupts are caused by events outside the CPU.
1162 They are asynchronous, so they can be invoked at any time that
1163 interrupts have not been disabled. We say that an external interrupt
1164 runs in an ``interrupt context.''
1166 In an external interrupt, the @struct{intr_frame} passed to the
1167 handler is not very meaningful. It describes the state of the thread
1168 or process that was interrupted, but there is no way to predict which
1169 one that is. It is possible, although rarely useful, to examine it, but
1170 modifying it is a recipe for disaster.
1172 Only one external interrupt may be processed at a time. Neither
1173 internal nor external interrupt may nest within an external interrupt
1174 handler. Thus, an external interrupt's handler must run with interrupts
1175 disabled (@pxref{Disabling Interrupts}).
1177 An external interrupt handler must not sleep or yield, which rules out
1178 calling @func{lock_acquire}, @func{thread_yield}, and many other
1179 functions. Sleeping in interrupt context would effectively put the
1180 interrupted thread to sleep, too, until the interrupt handler was again
1181 scheduled and returned. This would be unfair to the unlucky thread, and
1182 it would deadlock if the handler were waiting for the sleeping thread
1183 to, e.g., release a lock.
1185 An external interrupt handler
1186 effectively monopolizes the machine and delays all other activities.
1187 Therefore, external interrupt handlers should complete as quickly as
1188 they can. Anything that require much CPU time should instead run in a
1189 kernel thread, possibly one that the interrupt triggers using a
1190 synchronization primitive.
1192 External interrupts are controlled by a
1193 pair of devices outside the CPU called @dfn{programmable interrupt
1194 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1195 CPU's IDT, it also initializes the PICs for interrupt handling. The
1196 PICs also must be ``acknowledged'' at the end of processing for each
1197 external interrupt. @func{intr_handler} takes care of that by calling
1198 @func{pic_end_of_interrupt}, which properly signals the PICs.
1200 The following functions relate to external
1203 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1204 Registers @var{handler} to be called when external interrupt numbered
1205 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1206 purposes. The handler will run with interrupts disabled.
1209 @deftypefun bool intr_context (void)
1210 Returns true if we are running in an interrupt context, otherwise
1211 false. Mainly used in functions that might sleep
1212 or that otherwise should not be called from interrupt context, in this
1215 ASSERT (!intr_context ());
1219 @deftypefun void intr_yield_on_return (void)
1220 When called in an interrupt context, causes @func{thread_yield} to be
1221 called just before the interrupt returns. Used
1222 in the timer interrupt handler when a thread's time slice expires, to
1223 cause a new thread to be scheduled.
1226 @node Memory Allocation
1227 @section Memory Allocation
1229 Pintos contains two memory allocators, one that allocates memory in
1230 units of a page, and one that can allocate blocks of any size.
1237 @node Page Allocator
1238 @subsection Page Allocator
1240 The page allocator declared in @file{threads/palloc.h} allocates
1241 memory in units of a page. It is most often used to allocate memory
1242 one page at a time, but it can also allocate multiple contiguous pages
1245 The page allocator divides the memory it allocates into two pools,
1246 called the kernel and user pools. By default, each pool gets half of
1247 system memory above @w{1 MB}, but the division can be changed with the
1250 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1251 pool or the other. If one pool becomes empty, the other may still
1252 have free pages. The user pool should be used for allocating memory
1253 for user processes and the kernel pool for all other allocations.
1254 This will only become important starting with project 3. Until then,
1255 all allocations should be made from the kernel pool.
1257 Each pool's usage is tracked with a bitmap, one bit per page in
1258 the pool. A request to allocate @var{n} pages scans the bitmap
1259 for @var{n} consecutive bits set to
1260 false, indicating that those pages are free, and then sets those bits
1261 to true to mark them as used. This is a ``first fit'' allocation
1262 strategy (@pxref{Wilson}).
1264 The page allocator is subject to fragmentation. That is, it may not
1265 be possible to allocate @var{n} contiguous pages even though @var{n}
1266 or more pages are free, because the free pages are separated by used
1267 pages. In fact, in pathological cases it may be impossible to
1268 allocate 2 contiguous pages even though half of the pool's pages are free.
1269 Single-page requests can't fail due to fragmentation, so
1270 requests for multiple contiguous pages should be limited as much as
1273 Pages may not be allocated from interrupt context, but they may be
1276 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1277 a debugging aid (@pxref{Debugging Tips}).
1279 Page allocator types and functions are described below.
1281 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1282 @deftypefunx {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1283 Obtains and returns one page, or @var{page_cnt} contiguous pages,
1284 respectively. Returns a null pointer if the pages cannot be allocated.
1286 The @var{flags} argument may be any combination of the following flags:
1288 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1289 If the pages cannot be allocated, panic the kernel. This is only
1290 appropriate during kernel initialization. User processes
1291 should never be permitted to panic the kernel.
1294 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1295 Zero all the bytes in the allocated pages before returning them. If not
1296 set, the contents of newly allocated pages are unpredictable.
1299 @defvr {Page Allocator Flag} @code{PAL_USER}
1300 Obtain the pages from the user pool. If not set, pages are allocated
1301 from the kernel pool.
1305 @deftypefun void palloc_free_page (void *@var{page})
1306 @deftypefunx void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1307 Frees one page, or @var{page_cnt} contiguous pages, respectively,
1308 starting at @var{pages}. All of the pages must have been obtained using
1309 @func{palloc_get_page} or @func{palloc_get_multiple}.
1312 @node Block Allocator
1313 @subsection Block Allocator
1315 The block allocator, declared in @file{threads/malloc.h}, can allocate
1316 blocks of any size. It is layered on top of the page allocator
1317 described in the previous section. Blocks returned by the block
1318 allocator are obtained from the kernel pool.
1320 The block allocator uses two different strategies for allocating memory.
1321 The first strategy applies to blocks that are 1 kB or smaller
1322 (one-fourth of the page size). These allocations are rounded up to the
1323 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1324 grouped into a page used only for allocations of that size.
1326 The second strategy applies to blocks larger than 1 kB.
1327 These allocations (plus a small amount of overhead) are rounded up to
1328 the nearest page in size, and then the block allocator requests that
1329 number of contiguous pages from the page allocator.
1331 In either case, the difference between the allocation requested size
1332 and the actual block size is wasted. A real operating system would
1333 carefully tune its allocator to minimize this waste, but this is
1334 unimportant in an instructional system like Pintos.
1336 As long as a page can be obtained from the page allocator, small
1337 allocations always succeed. Most small allocations do not require a
1338 new page from the page allocator at all, because they are satisfied
1339 using part of a page already allocated. However, large allocations
1340 always require calling into the page allocator, and any allocation
1341 that needs more than one contiguous page can fail due to fragmentation,
1342 as already discussed in the previous section. Thus, you should
1343 minimize the number of large allocations in your code, especially
1344 those over approximately 4 kB each.
1346 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1347 a debugging aid (@pxref{Debugging Tips}).
1349 The block allocator may not be called from interrupt context.
1351 The block allocator functions are described below. Their interfaces are
1352 the same as the standard C library functions of the same names.
1354 @deftypefun {void *} malloc (size_t @var{size})
1355 Obtains and returns a new block, from the kernel pool, at least
1356 @var{size} bytes long. Returns a null pointer if @var{size} is zero or
1357 if memory is not available.
1360 @deftypefun {void *} calloc (size_t @var{a}, size_t @var{b})
1361 Obtains a returns a new block, from the kernel pool, at least
1362 @code{@var{a} * @var{b}} bytes long. The block's contents will be
1363 cleared to zeros. Returns a null pointer if @var{a} or @var{b} is zero
1364 or if insufficient memory is available.
1367 @deftypefun {void *} realloc (void *@var{block}, size_t @var{new_size})
1368 Attempts to resize @var{block} to @var{new_size} bytes, possibly moving
1369 it in the process. If successful, returns the new block, in which case
1370 the old block must no longer be accessed. On failure, returns a null
1371 pointer, and the old block remains valid.
1373 A call with @var{block} null is equivalent to @func{malloc}. A call
1374 with @var{new_size} zero is equivalent to @func{free}.
1377 @deftypefun void free (void *@var{block})
1378 Frees @var{block}, which must have been previously returned by
1379 @func{malloc}, @func{calloc}, or @func{realloc} (and not yet freed).
1382 @node Virtual Addresses
1383 @section Virtual Addresses
1385 A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
1386 and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
1391 +-------------------+-----------+
1392 | Page Number | Offset |
1393 +-------------------+-----------+
1398 Header @file{threads/vaddr.h} defines these functions and macros for
1399 working with virtual addresses:
1403 The bit index (0) and number of bits (12) of the offset part of a
1404 virtual address, respectively.
1408 A bit mask with the bits in the page offset set to 1, the rest set to 0
1413 The page size in bytes (4,096).
1416 @deftypefun unsigned pg_ofs (const void *@var{va})
1417 Extracts and returns the page offset in virtual address @var{va}.
1420 @deftypefun uintptr_t pg_no (const void *@var{va})
1421 Extracts and returns the page number in virtual address @var{va}.
1424 @deftypefun {void *} pg_round_down (const void *@var{va})
1425 Returns the start of the virtual page that @var{va} points within, that
1426 is, @var{va} with the page offset set to 0.
1429 @deftypefun {void *} pg_round_up (const void *@var{va})
1430 Returns @var{va} rounded up to the nearest page boundary.
1433 Virtual memory in Pintos is divided into two regions: user virtual
1434 memory and kernel virtual memory (@pxref{Virtual Memory Layout}). The
1435 boundary between them is @code{PHYS_BASE}:
1438 Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
1439 GB), but it may be changed to any multiple of @t{0x10000000} from
1440 @t{0x80000000} to @t{0xf0000000}.
1442 User virtual memory ranges from virtual address 0 up to
1443 @code{PHYS_BASE}. Kernel virtual memory occupies the rest of the
1444 virtual address space, from @code{PHYS_BASE} up to 4 GB.
1447 @deftypefun {bool} is_user_vaddr (const void *@var{va})
1448 @deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
1449 Returns true if @var{va} is a user or kernel virtual address,
1450 respectively, false otherwise.
1453 The 80@var{x}86 doesn't provide any way to directly access memory given
1454 a physical address. This ability is often necessary in an operating
1455 system kernel, so Pintos works around it by mapping kernel virtual
1456 memory one-to-one to physical memory. That is, virtual address
1457 @code{PHYS_BASE} accesses physical address 0, virtual address
1458 @code{PHYS_BASE} + @t{0x1234} accesses physical address @t{0x1234}, and
1459 so on up to the size of the machine's physical memory. Thus, adding
1460 @code{PHYS_BASE} to a physical address obtains a kernel virtual address
1461 that accesses that address; conversely, subtracting @code{PHYS_BASE}
1462 from a kernel virtual address obtains the corresponding physical
1463 address. Header @file{threads/vaddr.h} provides a pair of functions to
1464 do these translations:
1466 @deftypefun {void *} ptov (uintptr_t @var{pa})
1467 Returns the kernel virtual address corresponding to physical address
1468 @var{pa}, which should be between 0 and the number of bytes of physical
1472 @deftypefun {uintptr_t} vtop (void *@var{va})
1473 Returns the physical address corresponding to @var{va}, which must be a
1474 kernel virtual address.
1480 The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
1481 hardware page table, also called a ``page directory'' by Intel processor
1482 documentation. The page table interface uses a @code{uint32_t *} to
1483 represent a page table because this is convenient for accessing their
1486 The sections below describe the page table interface and internals.
1489 * Page Table Creation Destruction Activation::
1490 * Page Tables Inspection and Updates::
1491 * Page Table Accessed and Dirty Bits::
1492 * Page Table Details::
1495 @node Page Table Creation Destruction Activation
1496 @subsection Creation, Destruction, and Activation
1498 These functions create, destroy, and activate page tables. The base
1499 Pintos code already calls these functions where necessary, so it should
1500 not be necessary to call them yourself.
1502 @deftypefun {uint32_t *} pagedir_create (void)
1503 Creates and returns a new page table. The new page table contains
1504 Pintos's normal kernel virtual page mappings, but no user virtual
1507 Returns a null pointer if memory cannot be obtained.
1510 @deftypefun void pagedir_destroy (uint32_t *@var{pd})
1511 Frees all of the resources held by @var{pd}, including the page table
1512 itself and the frames that it maps.
1515 @deftypefun void pagedir_activate (uint32_t *@var{pd})
1516 Activates @var{pd}. The active page table is the one used by the CPU to
1517 translate memory references.
1520 @node Page Tables Inspection and Updates
1521 @subsection Inspection and Updates
1523 These functions examine or update the mappings from pages to frames
1524 encapsulated by a page table. They work on both active and inactive
1525 page tables (that is, those for running and suspended processes),
1526 flushing the TLB as necessary.
1528 @deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
1529 Adds to @var{pd} a mapping from user page @var{upage} to the frame identified
1530 by kernel virtual address @var{kpage}. If @var{writable} is true, the
1531 page is mapped read/write; otherwise, it is mapped read-only.
1533 User page @var{upage} must not already be mapped in @var{pd}.
1535 Kernel page @var{kpage} should be a kernel virtual address obtained from
1536 the user pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why
1539 Returns true if successful, false on failure. Failure will occur if
1540 additional memory required for the page table cannot be obtained.
1543 @deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
1544 Looks up the frame mapped to @var{uaddr} in @var{pd}. Returns the
1545 kernel virtual address for that frame, if @var{uaddr} is mapped, or a
1546 null pointer if it is not.
1549 @deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{page})
1550 Marks @var{page} ``not present'' in @var{pd}. Later accesses to
1551 the page will fault.
1553 Other bits in the page table for @var{page} are preserved, permitting
1554 the accessed and dirty bits (see the next section) to be checked.
1556 This function has no effect if @var{page} is not mapped.
1559 @node Page Table Accessed and Dirty Bits
1560 @subsection Accessed and Dirty Bits
1562 80@var{x}86 hardware provides some assistance for implementing page
1563 replacement algorithms, through a pair of bits in the page table entry
1564 (PTE) for each page. On any read or write to a page, the CPU sets the
1565 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
1566 sets the @dfn{dirty bit} to 1. The CPU never resets these bits to 0,
1567 but the OS may do so.
1569 Proper interpretation of these bits requires understanding of
1570 @dfn{aliases}, that is, two (or more) pages that refer to the same
1571 frame. When an aliased frame is accessed, the accessed and dirty bits
1572 are updated in only one page table entry (the one for the page used for
1573 access). The accessed and dirty bits for the other aliases are not
1576 @xref{Accessed and Dirty Bits}, on applying these bits in implementing
1577 page replacement algorithms.
1579 @deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
1580 @deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
1581 Returns true if page directory @var{pd} contains a page table entry for
1582 @var{page} that is marked dirty (or accessed). Otherwise,
1586 @deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1587 @deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1588 If page directory @var{pd} has a page table entry for @var{page}, then
1589 its dirty (or accessed) bit is set to @var{value}.
1592 @node Page Table Details
1593 @subsection Page Table Details
1595 The functions provided with Pintos are sufficient to implement the
1596 projects. However, you may still find it worthwhile to understand the
1597 hardware page table format, so we'll go into a little detail in this
1601 * Page Table Structure::
1602 * Page Table Entry Format::
1603 * Page Directory Entry Format::
1606 @node Page Table Structure
1607 @subsubsection Structure
1609 The top-level paging data structure is a page called the ``page
1610 directory'' (PD) arranged as an array of 1,024 32-bit page directory
1611 entries (PDEs), each of which represents 4 MB of virtual memory. Each
1612 PDE may point to the physical address of another page called a
1613 ``page table'' (PT) arranged, similarly, as an array of 1,024
1614 32-bit page table entries (PTEs), each of which translates a single 4
1615 kB virtual page to a physical page.
1617 Translation of a virtual address into a physical address follows
1618 the three-step process illustrated in the diagram
1619 below:@footnote{Actually, virtual to physical translation on the
1620 80@var{x}86 architecture occurs via an intermediate ``linear
1621 address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
1622 so that linear and virtual addresses are one and the same. Thus, you
1623 can effectively ignore this CPU feature.}
1627 The most-significant 10 bits of the virtual address (bits 22@dots{}31)
1628 index the page directory. If the PDE is marked ``present,'' the
1629 physical address of a page table is read from the PDE thus obtained.
1630 If the PDE is marked ``not present'' then a page fault occurs.
1633 The next 10 bits of the virtual address (bits 12@dots{}21) index
1634 the page table. If the PTE is marked ``present,'' the physical
1635 address of a data page is read from the PTE thus obtained. If the PTE
1636 is marked ``not present'' then a page fault occurs.
1639 The least-significant 12 bits of the virtual address (bits 0@dots{}11)
1640 are added to the data page's physical base address, yielding the final
1647 +----------------------+----------------------+----------------------+
1648 | Page Directory Index | Page Table Index | Page Offset |
1649 +----------------------+----------------------+----------------------+
1651 _______/ _______/ _____/
1653 / Page Directory / Page Table / Data Page
1654 / .____________. / .____________. / .____________.
1655 |1,023|____________| |1,023|____________| | |____________|
1656 |1,022|____________| |1,022|____________| | |____________|
1657 |1,021|____________| |1,021|____________| \__\|____________|
1658 |1,020|____________| |1,020|____________| /|____________|
1660 | | | \____\| |_ | |
1661 | | . | /| . | \ | . |
1662 \____\| . |_ | . | | | . |
1663 /| . | \ | . | | | . |
1664 | . | | | . | | | . |
1666 |____________| | |____________| | |____________|
1667 4|____________| | 4|____________| | |____________|
1668 3|____________| | 3|____________| | |____________|
1669 2|____________| | 2|____________| | |____________|
1670 1|____________| | 1|____________| | |____________|
1671 0|____________| \__\0|____________| \____\|____________|
1676 Pintos provides some macros and functions that are useful for working
1677 with raw page tables:
1681 The starting bit index (12) and number of bits (10), respectively, in a
1686 A bit mask with the bits in the page table index set to 1 and the rest
1687 set to 0 (@t{0x3ff000}).
1691 The number of bytes of virtual address space that a single page table
1692 page covers (4,194,304 bytes, or 4 MB).
1697 The starting bit index (22) and number of bits (10), respectively, in a
1698 page directory index.
1702 A bit mask with the bits in the page directory index set to 1 and other
1703 bits set to 0 (@t{0xffc00000}).
1706 @deftypefun uintptr_t pd_no (const void *@var{va})
1707 @deftypefunx uintptr_t pt_no (const void *@var{va})
1708 Returns the page directory index or page table index, respectively, for
1709 virtual address @var{va}. These functions are defined in
1710 @file{threads/pte.h}.
1713 @deftypefun unsigned pg_ofs (const void *@var{va})
1714 Returns the page offset for virtual address @var{va}. This function is
1715 defined in @file{threads/vaddr.h}.
1718 @node Page Table Entry Format
1719 @subsubsection Page Table Entry Format
1721 You do not need to understand the PTE format to do the Pintos
1722 projects, unless you wish to incorporate the page table into your
1723 supplemental page table (@pxref{Managing the Supplemental Page Table}).
1725 The actual format of a page table entry is summarized below. For
1726 complete information, refer to section 3.7, ``Page Translation Using
1727 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
1731 31 12 11 9 6 5 2 1 0
1732 +---------------------------------------+----+----+-+-+---+-+-+-+
1733 | Physical Address | AVL| |D|A| |U|W|P|
1734 +---------------------------------------+----+----+-+-+---+-+-+-+
1738 Some more information on each bit is given below. The names are
1739 @file{threads/pte.h} macros that represent the bits' values:
1742 Bit 0, the ``present'' bit. When this bit is 1, the
1743 other bits are interpreted as described below. When this bit is 0, any
1744 attempt to access the page will page fault. The remaining bits are then
1745 not used by the CPU and may be used by the OS for any purpose.
1749 Bit 1, the ``read/write'' bit. When it is 1, the page
1750 is writable. When it is 0, write attempts will page fault.
1754 Bit 2, the ``user/supervisor'' bit. When it is 1, user
1755 processes may access the page. When it is 0, only the kernel may access
1756 the page (user accesses will page fault).
1758 Pintos clears this bit in PTEs for kernel virtual memory, to prevent
1759 user processes from accessing them.
1763 Bit 5, the ``accessed'' bit. @xref{Page Table Accessed
1768 Bit 6, the ``dirty'' bit. @xref{Page Table Accessed and
1773 Bits 9@dots{}11, available for operating system use.
1774 Pintos, as provided, does not use them and sets them to 0.
1778 Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
1779 The low 12 bits of the frame's address are always 0.
1782 Other bits are either reserved or uninteresting in a Pintos context and
1783 should be set to@tie{}0.
1785 Header @file{threads/pte.h} defines three functions for working with
1788 @deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
1789 Returns a page table entry that points to @var{page}, which should be a
1790 kernel virtual address. The PTE's present bit will be set. It will be
1791 marked for kernel-only access. If @var{writable} is true, the PTE will
1792 also be marked read/write; otherwise, it will be read-only.
1795 @deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
1796 Returns a page table entry that points to @var{page}, which should be
1797 the kernel virtual address of a frame in the user pool (@pxref{Why
1798 PAL_USER?}). The PTE's present bit will be set and it will be marked to
1799 allow user-mode access. If @var{writable} is true, the PTE will also be
1800 marked read/write; otherwise, it will be read-only.
1803 @deftypefun {void *} pte_get_page (uint32_t @var{pte})
1804 Returns the kernel virtual address for the frame that @var{pte} points
1805 to. The @var{pte} may be present or not-present; if it is not-present
1806 then the pointer returned is only meaningful if the address bits in the PTE
1807 actually represent a physical address.
1810 @node Page Directory Entry Format
1811 @subsubsection Page Directory Entry Format
1813 Page directory entries have the same format as PTEs, except that the
1814 physical address points to a page table page instead of a frame. Header
1815 @file{threads/pte.h} defines two functions for working with page
1818 @deftypefun uint32_t pde_create (uint32_t *@var{pt})
1819 Returns a page directory that points to @var{page}, which should be the
1820 kernel virtual address of a page table page. The PDE's present bit will
1821 be set, it will be marked to allow user-mode access, and it will be
1825 @deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
1826 Returns the kernel virtual address for the page table page that
1827 @var{pde}, which must be marked present, points to.
1833 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1834 To use it you will need to include its header file,
1835 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}.
1836 No code provided with Pintos uses the hash table, which means that you
1837 are free to use it as is, modify its implementation for your own
1838 purposes, or ignore it, as you wish.
1840 Most implementations of the virtual memory project use a hash table to
1841 translate pages to frames. You may find other uses for hash tables as
1846 * Basic Hash Functions::
1847 * Hash Search Functions::
1848 * Hash Iteration Functions::
1849 * Hash Table Example::
1850 * Hash Auxiliary Data::
1851 * Hash Synchronization::
1854 @node Hash Data Types
1855 @subsection Data Types
1857 A hash table is represented by @struct{hash}.
1859 @deftp {Type} {struct hash}
1860 Represents an entire hash table. The actual members of @struct{hash}
1861 are ``opaque.'' That is, code that uses a hash table should not access
1862 @struct{hash} members directly, nor should it need to. Instead, use
1863 hash table functions and macros.
1866 The hash table operates on elements of type @struct{hash_elem}.
1868 @deftp {Type} {struct hash_elem}
1869 Embed a @struct{hash_elem} member in the structure you want to include
1870 in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
1871 All functions for operating on hash table elements actually take and
1872 return pointers to @struct{hash_elem}, not pointers to your hash table's
1876 You will often need to obtain a @struct{hash_elem} given a real element
1877 of the hash table, and vice versa. Given a real element of the hash
1878 table, you may use the @samp{&} operator to obtain a pointer to its
1879 @struct{hash_elem}. Use the @code{hash_entry()} macro to go the other
1882 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1883 Returns a pointer to the structure that @var{elem}, a pointer to a
1884 @struct{hash_elem}, is embedded within. You must provide @var{type},
1885 the name of the structure that @var{elem} is inside, and @var{member},
1886 the name of the member in @var{type} that @var{elem} points to.
1888 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1889 that points to a @struct{thread} member (of type @struct{hash_elem})
1890 named @code{h_elem}. Then, @code{hash_entry@tie{}(h, struct thread, h_elem)}
1891 yields the address of the @struct{thread} that @code{h} points within.
1894 @xref{Hash Table Example}, for an example.
1896 Each hash table element must contain a key, that is, data that
1897 identifies and distinguishes elements, which must be unique
1898 among elements in the hash table. (Elements may
1899 also contain non-key data that need not be unique.) While an element is
1900 in a hash table, its key data must not be changed. Instead, if need be,
1901 remove the element from the hash table, modify its key, then reinsert
1904 For each hash table, you must write two functions that act on keys: a
1905 hash function and a comparison function. These functions must match the
1906 following prototypes:
1908 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1909 Returns a hash of @var{element}'s data, as a value anywhere in the range
1910 of @code{unsigned int}. The hash of an element should be a
1911 pseudo-random function of the element's key. It must not depend on
1912 non-key data in the element or on any non-constant data other than the
1913 key. Pintos provides the following functions as a suitable basis for
1916 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1917 Returns a hash of the @var{size} bytes starting at @var{buf}. The
1918 implementation is the general-purpose
1919 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1920 hash} for 32-bit words.
1923 @deftypefun unsigned hash_string (const char *@var{s})
1924 Returns a hash of null-terminated string @var{s}.
1927 @deftypefun unsigned hash_int (int @var{i})
1928 Returns a hash of integer @var{i}.
1931 If your key is a single piece of data of an appropriate type, it is
1932 sensible for your hash function to directly return the output of one of
1933 these functions. For multiple pieces of data, you may wish to combine
1934 the output of more than one call to them using, e.g., the @samp{^}
1936 operator. Finally, you may entirely ignore these functions and write
1937 your own hash function from scratch, but remember that your goal is to
1938 build an operating system kernel, not to design a hash function.
1940 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1943 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1944 Compares the keys stored in elements @var{a} and @var{b}. Returns
1945 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1946 or equal to @var{b}.
1948 If two elements compare equal, then they must hash to equal values.
1950 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1953 @xref{Hash Table Example}, for hash and comparison function examples.
1955 A few functions accept a pointer to a third kind of
1956 function as an argument:
1958 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1959 Performs some kind of action, chosen by the caller, on @var{element}.
1961 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1964 @node Basic Hash Functions
1965 @subsection Basic Functions
1967 These functions create, destroy, and inspect hash tables.
1969 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
1970 Initializes @var{hash} as a hash table with @var{hash_func} as hash
1971 function, @var{less_func} as comparison function, and @var{aux} as
1973 Returns true if successful, false on failure. @func{hash_init} calls
1974 @func{malloc} and fails if memory cannot be allocated.
1976 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
1977 most often a null pointer.
1980 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
1981 Removes all the elements from @var{hash}, which must have been
1982 previously initialized with @func{hash_init}.
1984 If @var{action} is non-null, then it is called once for each element in
1985 the hash table, which gives the caller an opportunity to deallocate any
1986 memory or other resources used by the element. For example, if the hash
1987 table elements are dynamically allocated using @func{malloc}, then
1988 @var{action} could @func{free} the element. This is safe because
1989 @func{hash_clear} will not access the memory in a given hash element
1990 after calling @var{action} on it. However, @var{action} must not call
1991 any function that may modify the hash table, such as @func{hash_insert}
1992 or @func{hash_delete}.
1995 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
1996 If @var{action} is non-null, calls it for each element in the hash, with
1997 the same semantics as a call to @func{hash_clear}. Then, frees the
1998 memory held by @var{hash}. Afterward, @var{hash} must not be passed to
1999 any hash table function, absent an intervening call to @func{hash_init}.
2002 @deftypefun size_t hash_size (struct hash *@var{hash})
2003 Returns the number of elements currently stored in @var{hash}.
2006 @deftypefun bool hash_empty (struct hash *@var{hash})
2007 Returns true if @var{hash} currently contains no elements,
2008 false if @var{hash} contains at least one element.
2011 @node Hash Search Functions
2012 @subsection Search Functions
2014 Each of these functions searches a hash table for an element that
2015 compares equal to one provided. Based on the success of the search,
2016 they perform some action, such as inserting a new element into the hash
2017 table, or simply return the result of the search.
2019 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
2020 Searches @var{hash} for an element equal to @var{element}. If none is
2021 found, inserts @var{element} into @var{hash} and returns a null pointer.
2022 If the table already contains an element equal to @var{element}, it is
2023 returned without modifying @var{hash}.
2026 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
2027 Inserts @var{element} into @var{hash}. Any element equal to
2028 @var{element} already in @var{hash} is removed. Returns the element
2029 removed, or a null pointer if @var{hash} did not contain an element
2030 equal to @var{element}.
2032 The caller is responsible for deallocating any resources associated with
2033 the returned element, as appropriate. For example, if the hash table
2034 elements are dynamically allocated using @func{malloc}, then the caller
2035 must @func{free} the element after it is no longer needed.
2038 The element passed to the following functions is only used for hashing
2039 and comparison purposes. It is never actually inserted into the hash
2040 table. Thus, only key data in the element needs to be initialized, and
2041 other data in the element will not be used. It often makes sense to
2042 declare an instance of the element type as a local variable, initialize
2043 the key data, and then pass the address of its @struct{hash_elem} to
2044 @func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
2045 an example. (Large structures should not be
2046 allocated as local variables. @xref{struct thread}, for more
2049 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
2050 Searches @var{hash} for an element equal to @var{element}. Returns the
2051 element found, if any, or a null pointer otherwise.
2054 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
2055 Searches @var{hash} for an element equal to @var{element}. If one is
2056 found, it is removed from @var{hash} and returned. Otherwise, a null
2057 pointer is returned and @var{hash} is unchanged.
2059 The caller is responsible for deallocating any resources associated with
2060 the returned element, as appropriate. For example, if the hash table
2061 elements are dynamically allocated using @func{malloc}, then the caller
2062 must @func{free} the element after it is no longer needed.
2065 @node Hash Iteration Functions
2066 @subsection Iteration Functions
2068 These functions allow iterating through the elements in a hash table.
2069 Two interfaces are supplied. The first requires writing and supplying a
2070 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
2072 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
2073 Calls @var{action} once for each element in @var{hash}, in arbitrary
2074 order. @var{action} must not call any function that may modify the hash
2075 table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
2076 must not modify key data in elements, although it may modify any other
2080 The second interface is based on an ``iterator'' data type.
2081 Idiomatically, iterators are used as follows:
2084 struct hash_iterator i;
2087 while (hash_next (&i))
2089 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
2090 @r{@dots{}do something with @i{f}@dots{}}
2094 @deftp {Type} {struct hash_iterator}
2095 Represents a position within a hash table. Calling any function that
2096 may modify a hash table, such as @func{hash_insert} or
2097 @func{hash_delete}, invalidates all iterators within that hash table.
2099 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
2102 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
2103 Initializes @var{iterator} to just before the first element in
2107 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
2108 Advances @var{iterator} to the next element in @var{hash}, and returns
2109 that element. Returns a null pointer if no elements remain. After
2110 @func{hash_next} returns null for @var{iterator}, calling it again
2111 yields undefined behavior.
2114 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
2115 Returns the value most recently returned by @func{hash_next} for
2116 @var{iterator}. Yields undefined behavior after @func{hash_first} has
2117 been called on @var{iterator} but before @func{hash_next} has been
2118 called for the first time.
2121 @node Hash Table Example
2122 @subsection Hash Table Example
2124 Suppose you have a structure, called @struct{page}, that you
2125 want to put into a hash table. First, define @struct{page} to include a
2126 @struct{hash_elem} member:
2131 struct hash_elem hash_elem; /* @r{Hash table element.} */
2132 void *addr; /* @r{Virtual address.} */
2133 /* @r{@dots{}other members@dots{}} */
2137 We write a hash function and a comparison function using @var{addr} as
2138 the key. A pointer can be hashed based on its bytes, and the @samp{<}
2139 operator works fine for comparing pointers:
2142 /* @r{Returns a hash value for page @var{p}.} */
2144 page_hash (const struct hash_elem *p_, void *aux UNUSED)
2146 const struct page *p = hash_entry (p_, struct page, hash_elem);
2147 return hash_bytes (&p->addr, sizeof p->addr);
2150 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
2152 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2155 const struct page *a = hash_entry (a_, struct page, hash_elem);
2156 const struct page *b = hash_entry (b_, struct page, hash_elem);
2158 return a->addr < b->addr;
2163 (The use of @code{UNUSED} in these functions' prototypes suppresses a
2164 warning that @var{aux} is unused. @xref{Function and Parameter
2165 Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
2166 Data}, for an explanation of @var{aux}.)
2168 Then, we can create a hash table like this:
2173 hash_init (&pages, page_hash, page_less, NULL);
2176 Now we can manipulate the hash table we've created. If @code{@var{p}}
2177 is a pointer to a @struct{page}, we can insert it into the hash table
2181 hash_insert (&pages, &p->hash_elem);
2184 @noindent If there's a chance that @var{pages} might already contain a
2185 page with the same @var{addr}, then we should check @func{hash_insert}'s
2188 To search for an element in the hash table, use @func{hash_find}. This
2189 takes a little setup, because @func{hash_find} takes an element to
2190 compare against. Here's a function that will find and return a page
2191 based on a virtual address, assuming that @var{pages} is defined at file
2195 /* @r{Returns the page containing the given virtual @var{address},}
2196 @r{or a null pointer if no such page exists.} */
2198 page_lookup (const void *address)
2201 struct hash_elem *e;
2204 e = hash_find (&pages, &p.hash_elem);
2205 return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
2210 @struct{page} is allocated as a local variable here on the assumption
2211 that it is fairly small. Large structures should not be allocated as
2212 local variables. @xref{struct thread}, for more information.
2214 A similar function could delete a page by address using
2217 @node Hash Auxiliary Data
2218 @subsection Auxiliary Data
2220 In simple cases like the example above, there's no need for the
2221 @var{aux} parameters. In these cases, just pass a null pointer to
2222 @func{hash_init} for @var{aux} and ignore the values passed to the hash
2223 function and comparison functions. (You'll get a compiler warning if
2224 you don't use the @var{aux} parameter, but you can turn that off with
2225 the @code{UNUSED} macro, as shown in the example, or you can just ignore
2228 @var{aux} is useful when you have some property of the data in the
2229 hash table is both constant and needed for hashing or comparison,
2230 but not stored in the data items themselves. For example, if
2231 the items in a hash table are fixed-length strings, but the items
2232 themselves don't indicate what that fixed length is, you could pass
2233 the length as an @var{aux} parameter.
2235 @node Hash Synchronization
2236 @subsection Synchronization
2238 The hash table does not do any internal synchronization. It is the
2239 caller's responsibility to synchronize calls to hash table functions.
2240 In general, any number of functions that examine but do not modify the
2241 hash table, such as @func{hash_find} or @func{hash_next}, may execute
2242 simultaneously. However, these function cannot safely execute at the
2243 same time as any function that may modify a given hash table, such as
2244 @func{hash_insert} or @func{hash_delete}, nor may more than one function
2245 that can modify a given hash table execute safely at once.
2247 It is also the caller's responsibility to synchronize access to data in
2248 hash table elements. How to synchronize access to this data depends on
2249 how it is designed and organized, as with any other data structure.