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.
181 @func{input_init} sets up to merge serial and keyboard input into one
183 projects 2 and later, we also prepare to handle interrupts caused by
184 user programs using @func{exception_init} and @func{syscall_init}.
186 Now that interrupts are set up, we can start the scheduler
187 with @func{thread_start}, which creates the idle thread and enables
189 With interrupts enabled, interrupt-driven serial port I/O becomes
191 @func{serial_init_queue} to switch to that mode. Finally,
192 @func{timer_calibrate} calibrates the timer for accurate short delays.
194 If the file system is compiled in, as it will starting in project 2, we
195 initialize the disks with @func{disk_init}, then the
196 file system with @func{filesys_init}.
198 Boot is complete, so we print a message.
200 Function @func{run_actions} now parses and executes actions specified on
201 the kernel command line, such as @command{run} to run a test (in project
202 1) or a user program (in later projects).
204 Finally, if @option{-q} was specified on the kernel command line, we
205 call @func{power_off} to terminate the machine simulator. Otherwise,
206 @func{main} calls @func{thread_exit}, which allows any other running
207 threads to continue running.
219 @subsection @code{struct thread}
221 The main Pintos data structure for threads is @struct{thread},
222 declared in @file{threads/thread.h}.
224 @deftp {Structure} {struct thread}
225 Represents a thread or a user process. In the projects, you will have
226 to add your own members to @struct{thread}. You may also change or
227 delete the definitions of existing members.
229 Every @struct{thread} occupies the beginning of its own page of
230 memory. The rest of the page is used for the thread's stack, which
231 grows downward from the end of the page. It looks like this:
235 4 kB +---------------------------------+
249 sizeof (struct thread) +---------------------------------+
255 0 kB +---------------------------------+
259 This has two consequences. First, @struct{thread} must not be allowed
260 to grow too big. If it does, then there will not be enough room for the
261 kernel stack. The base @struct{thread} is only a few bytes in size. It
262 probably should stay well under 1 kB.
264 Second, kernel stacks must not be allowed to grow too large. If a stack
265 overflows, it will corrupt the thread state. Thus, kernel functions
266 should not allocate large structures or arrays as non-static local
267 variables. Use dynamic allocation with @func{malloc} or
268 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
271 @deftypecv {Member} {@struct{thread}} {tid_t} tid
272 The thread's thread identifier or @dfn{tid}. Every thread must have a
273 tid that is unique over the entire lifetime of the kernel. By
274 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
275 thread receives the numerically next higher tid, starting from 1 for
276 the initial process. You can change the type and the numbering scheme
280 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
281 @anchor{Thread States}
282 The thread's state, one of the following:
284 @defvr {Thread State} @code{THREAD_RUNNING}
285 The thread is running. Exactly one thread is running at a given time.
286 @func{thread_current} returns the running thread.
289 @defvr {Thread State} @code{THREAD_READY}
290 The thread is ready to run, but it's not running right now. The
291 thread could be selected to run the next time the scheduler is
292 invoked. Ready threads are kept in a doubly linked list called
296 @defvr {Thread State} @code{THREAD_BLOCKED}
297 The thread is waiting for something, e.g.@: a lock to become
298 available, an interrupt to be invoked. The thread won't be scheduled
299 again until it transitions to the @code{THREAD_READY} state with a
300 call to @func{thread_unblock}. This is most conveniently done
301 indirectly, using one of the Pintos synchronization primitives that
302 block and unblock threads automatically (@pxref{Synchronization}).
304 There is no @i{a priori} way to tell what a blocked thread is waiting
305 for, but a backtrace can help (@pxref{Backtraces}).
308 @defvr {Thread State} @code{THREAD_DYING}
309 The thread will be destroyed by the scheduler after switching to the
314 @deftypecv {Member} {@struct{thread}} {char} name[16]
315 The thread's name as a string, or at least the first few characters of
319 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
320 Every thread has its own stack to keep track of its state. When the
321 thread is running, the CPU's stack pointer register tracks the top of
322 the stack and this member is unused. But when the CPU switches to
323 another thread, this member saves the thread's stack pointer. No
324 other members are needed to save the thread's registers, because the
325 other registers that must be saved are saved on the stack.
327 When an interrupt occurs, whether in the kernel or a user program, an
328 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
329 in a user program, the @struct{intr_frame} is always at the very top of
330 the page. @xref{Interrupt Handling}, for more information.
333 @deftypecv {Member} {@struct{thread}} {int} priority
334 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
335 (63). Lower numbers correspond to lower priorities, so that
336 priority 0 is the lowest priority and priority 63 is the highest.
337 Pintos as provided ignores thread priorities, but you will implement
338 priority scheduling in project 1 (@pxref{Priority Scheduling}).
341 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
342 A ``list element'' used to put the thread into doubly linked lists,
343 either @code{ready_list} (the list of threads ready to run) or a list of
344 threads waiting on a semaphore in @func{sema_down}. It can do double
345 duty because a thread waiting on a semaphore is not ready, and vice
349 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
350 Only present in project 2 and later. @xref{Page Tables}.
353 @deftypecv {Member} {@struct{thread}} {unsigned} magic
354 Always set to @code{THREAD_MAGIC}, which is just an arbitrary number defined
355 in @file{threads/thread.c}, and used to detect stack overflow.
356 @func{thread_current} checks that the @code{magic} member of the running
357 thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
358 tends to change this value, triggering the assertion. For greatest
359 benefit, as you add members to @struct{thread}, leave @code{magic} at
363 @node Thread Functions
364 @subsection Thread Functions
366 @file{threads/thread.c} implements several public functions for thread
367 support. Let's take a look at the most useful:
369 @deftypefun void thread_init (void)
370 Called by @func{main} to initialize the thread system. Its main
371 purpose is to create a @struct{thread} for Pintos's initial thread.
372 This is possible because the Pintos loader puts the initial
373 thread's stack at the top of a page, in the same position as any other
376 Before @func{thread_init} runs,
377 @func{thread_current} will fail because the running thread's
378 @code{magic} value is incorrect. Lots of functions call
379 @func{thread_current} directly or indirectly, including
380 @func{lock_acquire} for locking a lock, so @func{thread_init} is
381 called early in Pintos initialization.
384 @deftypefun void thread_start (void)
385 Called by @func{main} to start the scheduler. Creates the idle
386 thread, that is, the thread that is scheduled when no other thread is
387 ready. Then enables interrupts, which as a side effect enables the
388 scheduler because the scheduler runs on return from the timer interrupt, using
389 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
392 @deftypefun void thread_tick (void)
393 Called by the timer interrupt at each timer tick. It keeps track of
394 thread statistics and triggers the scheduler when a time slice expires.
397 @deftypefun void thread_print_stats (void)
398 Called during Pintos shutdown to print thread statistics.
401 @deftypefun tid_t thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
402 Creates and starts a new thread named @var{name} with the given
403 @var{priority}, returning the new thread's tid. The thread executes
404 @var{func}, passing @var{aux} as the function's single argument.
406 @func{thread_create} allocates a page for the thread's
407 @struct{thread} and stack and initializes its members, then it sets
408 up a set of fake stack frames for it (@pxref{Thread Switching}). The
409 thread is initialized in the blocked state, then unblocked just before
410 returning, which allows the new thread to
411 be scheduled (@pxref{Thread States}).
413 @deftp {Type} {void thread_func (void *@var{aux})}
414 This is the type of the function passed to @func{thread_create}, whose
415 @var{aux} argument is passed along as the function's argument.
419 @deftypefun void thread_block (void)
420 Transitions the running thread from the running state to the blocked
421 state (@pxref{Thread States}). The thread will not run again until
422 @func{thread_unblock} is
423 called on it, so you'd better have some way arranged for that to happen.
424 Because @func{thread_block} is so low-level, you should prefer to use
425 one of the synchronization primitives instead (@pxref{Synchronization}).
428 @deftypefun void thread_unblock (struct thread *@var{thread})
429 Transitions @var{thread}, which must be in the blocked state, to the
430 ready state, allowing it to resume running (@pxref{Thread States}).
431 This is called when the event that the thread is waiting for occurs,
432 e.g.@: when the lock that
433 the thread is waiting on becomes available.
436 @deftypefun {struct thread *} thread_current (void)
437 Returns the running thread.
440 @deftypefun {tid_t} thread_tid (void)
441 Returns the running thread's thread id. Equivalent to
442 @code{thread_current ()->tid}.
445 @deftypefun {const char *} thread_name (void)
446 Returns the running thread's name. Equivalent to @code{thread_current
450 @deftypefun void thread_exit (void) @code{NO_RETURN}
451 Causes the current thread to exit. Never returns, hence
452 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
455 @deftypefun void thread_yield (void)
456 Yields the CPU to the scheduler, which picks a new thread to run. The
457 new thread might be the current thread, so you can't depend on this
458 function to keep this thread from running for any particular length of
462 @deftypefun int thread_get_priority (void)
463 @deftypefunx void thread_set_priority (int @var{new_priority})
464 Stub to set and get thread priority. @xref{Priority Scheduling}.
467 @deftypefun int thread_get_nice (void)
468 @deftypefunx void thread_set_nice (int @var{new_nice})
469 @deftypefunx int thread_get_recent_cpu (void)
470 @deftypefunx int thread_get_load_avg (void)
471 Stubs for the advanced scheduler. @xref{4.4BSD Scheduler}.
474 @node Thread Switching
475 @subsection Thread Switching
477 @func{schedule} is responsible for switching threads. It
478 is internal to @file{threads/thread.c} and called only by the three
479 public thread functions that need to switch threads:
480 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
481 Before any of these functions call @func{schedule}, they disable
482 interrupts (or ensure that they are already disabled) and then change
483 the running thread's state to something other than running.
485 @func{schedule} is short but tricky. It records the
486 current thread in local variable @var{cur}, determines the next thread
487 to run as local variable @var{next} (by calling
488 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
489 the actual thread switch. The thread we switched to was also running
490 inside @func{switch_threads}, as are all the threads not currently
491 running, so the new thread now returns out of
492 @func{switch_threads}, returning the previously running thread.
494 @func{switch_threads} is an assembly language routine in
495 @file{threads/switch.S}. It saves registers on the stack, saves the
496 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
497 member, restores the new thread's @code{stack} into the CPU's stack
498 pointer, restores registers from the stack, and returns.
500 The rest of the scheduler is implemented in @func{schedule_tail}. It
501 marks the new thread as running. If the thread we just switched from
502 is in the dying state, then it also frees the page that contained the
503 dying thread's @struct{thread} and stack. These couldn't be freed
504 prior to the thread switch because the switch needed to use it.
506 Running a thread for the first time is a special case. When
507 @func{thread_create} creates a new thread, it goes through a fair
508 amount of trouble to get it started properly. In particular, the new
509 thread hasn't started running yet, so there's no way for it to be
510 running inside @func{switch_threads} as the scheduler expects. To
511 solve the problem, @func{thread_create} creates some fake stack frames
512 in the new thread's stack:
516 The topmost fake stack frame is for @func{switch_threads}, represented
517 by @struct{switch_threads_frame}. The important part of this frame is
518 its @code{eip} member, the return address. We point @code{eip} to
519 @func{switch_entry}, indicating it to be the function that called
523 The next fake stack frame is for @func{switch_entry}, an assembly
524 language routine in @file{threads/switch.S} that adjusts the stack
525 pointer,@footnote{This is because @func{switch_threads} takes
526 arguments on the stack and the 80@var{x}86 SVR4 calling convention
527 requires the caller, not the called function, to remove them when the
528 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
529 calls @func{schedule_tail} (this special case is why
530 @func{schedule_tail} is separate from @func{schedule}), and returns.
531 We fill in its stack frame so that it returns into
532 @func{kernel_thread}, a function in @file{threads/thread.c}.
535 The final stack frame is for @func{kernel_thread}, which enables
536 interrupts and calls the thread's function (the function passed to
537 @func{thread_create}). If the thread's function returns, it calls
538 @func{thread_exit} to terminate the thread.
541 @node Synchronization
542 @section Synchronization
544 If sharing of resources between threads is not handled in a careful,
545 controlled fashion, the result is usually a big mess.
546 This is especially the case in operating system kernels, where
547 faulty sharing can crash the entire machine. Pintos provides several
548 synchronization primitives to help out.
551 * Disabling Interrupts::
558 @node Disabling Interrupts
559 @subsection Disabling Interrupts
561 The crudest way to do synchronization is to disable interrupts, that
562 is, to temporarily prevent the CPU from responding to interrupts. If
563 interrupts are off, no other thread will preempt the running thread,
564 because thread preemption is driven by the timer interrupt. If
565 interrupts are on, as they normally are, then the running thread may
566 be preempted by another at any time, whether between two C statements
567 or even within the execution of one.
569 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
570 is, kernel threads can be preempted at any time. Traditional Unix
571 systems are ``nonpreemptible,'' that is, kernel threads can only be
572 preempted at points where they explicitly call into the scheduler.
573 (User programs can be preempted at any time in both models.) As you
574 might imagine, preemptible kernels require more explicit
577 You should have little need to set the interrupt state directly. Most
578 of the time you should use the other synchronization primitives
579 described in the following sections. The main reason to disable
580 interrupts is to synchronize kernel threads with external interrupt
581 handlers, which cannot sleep and thus cannot use most other forms of
582 synchronization (@pxref{External Interrupt Handling}).
584 Some external interrupts cannot be postponed, even by disabling
585 interrupts. These interrupts, called @dfn{non-maskable interrupts}
586 (NMIs), are supposed to be used only in emergencies, e.g.@: when the
587 computer is on fire. Pintos does not handle non-maskable interrupts.
589 Types and functions for disabling and enabling interrupts are in
590 @file{threads/interrupt.h}.
592 @deftp Type {enum intr_level}
593 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
594 disabled or enabled, respectively.
597 @deftypefun {enum intr_level} intr_get_level (void)
598 Returns the current interrupt state.
601 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
602 Turns interrupts on or off according to @var{level}. Returns the
603 previous interrupt state.
606 @deftypefun {enum intr_level} intr_enable (void)
607 Turns interrupts on. Returns the previous interrupt state.
610 @deftypefun {enum intr_level} intr_disable (void)
611 Turns interrupts off. Returns the previous interrupt state.
615 @subsection Semaphores
617 A @dfn{semaphore} is a nonnegative integer together with two operators
618 that manipulate it atomically, which are:
622 ``Down'' or ``P'': wait for the value to become positive, then
626 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
630 A semaphore initialized to 0 may be used to wait for an event
631 that will happen exactly once. For example, suppose thread @var{A}
632 starts another thread @var{B} and wants to wait for @var{B} to signal
633 that some activity is complete. @var{A} can create a semaphore
634 initialized to 0, pass it to @var{B} as it starts it, and then
635 ``down'' the semaphore. When @var{B} finishes its activity, it
636 ``ups'' the semaphore. This works regardless of whether @var{A}
637 ``downs'' the semaphore or @var{B} ``ups'' it first.
639 A semaphore initialized to 1 is typically used for controlling access
640 to a resource. Before a block of code starts using the resource, it
641 ``downs'' the semaphore, then after it is done with the resource it
642 ``ups'' the resource. In such a case a lock, described below, may be
645 Semaphores can also be initialized to values larger than 1. These are
648 Semaphores were invented by Edsger Dijkstra and first used in the THE
649 operating system (@bibref{Dijkstra}).
651 Pintos' semaphore type and operations are declared in
652 @file{threads/synch.h}.
654 @deftp {Type} {struct semaphore}
655 Represents a semaphore.
658 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
659 Initializes @var{sema} as a new semaphore with the given initial
663 @deftypefun void sema_down (struct semaphore *@var{sema})
664 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
665 its value to become positive and then decrementing it by one.
668 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
669 Tries to execute the ``down'' or ``P'' operation on @var{sema},
670 without waiting. Returns true if @var{sema}
671 was successfully decremented, or false if it was already
672 zero and thus could not be decremented without waiting. Calling this
674 tight loop wastes CPU time, so use @func{sema_down} or find a
675 different approach instead.
678 @deftypefun void sema_up (struct semaphore *@var{sema})
679 Executes the ``up'' or ``V'' operation on @var{sema},
680 incrementing its value. If any threads are waiting on
681 @var{sema}, wakes one of them up.
683 Unlike most synchronization primitives, @func{sema_up} may be called
684 inside an external interrupt handler (@pxref{External Interrupt
688 Semaphores are internally built out of disabling interrupt
689 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
690 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
691 a list of waiting threads, using the linked list
692 implementation in @file{lib/kernel/list.c}.
697 A @dfn{lock} is like a semaphore with an initial value of 1
698 (@pxref{Semaphores}). A lock's equivalent of ``up'' is called
699 ``acquire'', and the ``down'' operation is called ``release''.
701 Compared to a semaphore, a lock has one added restriction: only the
702 thread that acquires a lock, called the lock's ``owner'', is allowed to
703 release it. If this restriction is a problem, it's a good sign that a
704 semaphore should be used, instead of a lock.
706 Locks in Pintos are not ``recursive,'' that is, it is an error for the
707 thread currently holding a lock to try to acquire that lock.
709 Lock types and functions are declared in @file{threads/synch.h}.
711 @deftp {Type} {struct lock}
715 @deftypefun void lock_init (struct lock *@var{lock})
716 Initializes @var{lock} as a new lock.
717 The lock is not initially owned by any thread.
720 @deftypefun void lock_acquire (struct lock *@var{lock})
721 Acquires @var{lock} for the current thread, first waiting for
722 any current owner to release it if necessary.
725 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
726 Tries to acquire @var{lock} for use by the current thread, without
727 waiting. Returns true if successful, false if the lock is already
728 owned. Calling this function in a tight loop is a bad idea because it
729 wastes CPU time, so use @func{lock_acquire} instead.
732 @deftypefun void lock_release (struct lock *@var{lock})
733 Releases @var{lock}, which the current thread must own.
736 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
737 Returns true if the running thread owns @var{lock},
739 There is no function to test whether an arbitrary thread owns a lock,
740 because the answer could change before the caller could act on it.
746 A @dfn{monitor} is a higher-level form of synchronization than a
747 semaphore or a lock. A monitor consists of data being synchronized,
748 plus a lock, called the @dfn{monitor lock}, and one or more
749 @dfn{condition variables}. Before it accesses the protected data, a
750 thread first acquires the monitor lock. It is then said to be ``in the
751 monitor''. While in the monitor, the thread has control over all the
752 protected data, which it may freely examine or modify. When access to
753 the protected data is complete, it releases the monitor lock.
755 Condition variables allow code in the monitor to wait for a condition to
756 become true. Each condition variable is associated with an abstract
757 condition, e.g.@: ``some data has arrived for processing'' or ``over 10
758 seconds has passed since the user's last keystroke''. When code in the
759 monitor needs to wait for a condition to become true, it ``waits'' on
760 the associated condition variable, which releases the lock and waits for
761 the condition to be signaled. If, on the other hand, it has caused one
762 of these conditions to become true, it ``signals'' the condition to wake
763 up one waiter, or ``broadcasts'' the condition to wake all of them.
765 The theoretical framework for monitors was laid out by C.@: A.@: R.@:
766 Hoare (@bibref{Hoare}). Their practical usage was later elaborated in a
767 paper on the Mesa operating system (@bibref{Lampson}).
769 Condition variable types and functions are declared in
770 @file{threads/synch.h}.
772 @deftp {Type} {struct condition}
773 Represents a condition variable.
776 @deftypefun void cond_init (struct condition *@var{cond})
777 Initializes @var{cond} as a new condition variable.
780 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
781 Atomically releases @var{lock} (the monitor lock) and waits for
782 @var{cond} to be signaled by some other piece of code. After
783 @var{cond} is signaled, reacquires @var{lock} before returning.
784 @var{lock} must be held before calling this function.
786 Sending a signal and waking up from a wait are not an atomic operation.
787 Thus, typically @func{cond_wait}'s caller must recheck the condition
788 after the wait completes and, if necessary, wait again. See the next
789 section for an example.
792 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
793 If any threads are waiting on @var{cond} (protected by monitor lock
794 @var{lock}), then this function wakes up one of them. If no threads are
795 waiting, returns without performing any action.
796 @var{lock} must be held before calling this function.
799 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
800 Wakes up all threads, if any, waiting on @var{cond} (protected by
801 monitor lock @var{lock}). @var{lock} must be held before calling this
805 @subsubsection Monitor Example
807 The classical example of a monitor is handling a buffer into which one
809 ``producer'' threads write characters and out of which one or more
810 ``consumer'' threads read characters. To implement this we need,
811 besides the monitor lock, two condition variables which we will call
812 @var{not_full} and @var{not_empty}:
815 char buf[BUF_SIZE]; /* @r{Buffer.} */
816 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
817 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
818 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
819 struct lock lock; /* @r{Monitor lock.} */
820 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
821 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
823 @dots{}@r{initialize the locks and condition variables}@dots{}
825 void put (char ch) @{
826 lock_acquire (&lock);
827 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
828 cond_wait (¬_full, &lock);
829 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
831 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
832 lock_release (&lock);
837 lock_acquire (&lock);
838 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
839 cond_wait (¬_empty, &lock);
840 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
842 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
843 lock_release (&lock);
847 @node Memory Barriers
848 @subsection Memory Barriers
850 @c We should try to come up with a better example.
851 @c Perhaps something with a linked list?
853 Suppose we add a ``feature'' that, whenever a timer interrupt
854 occurs, the character in global variable @code{timer_put_char} is
855 printed on the console, but only if global Boolean variable
856 @code{timer_do_put} is true.
858 If interrupts are enabled, this code for setting up @samp{x} to be
859 printed is clearly incorrect, because the timer interrupt could intervene
860 between the two assignments:
863 timer_do_put = true; /* INCORRECT CODE */
864 timer_put_char = 'x';
867 It might not be as obvious that the following code is just as
871 timer_put_char = 'x'; /* INCORRECT CODE */
875 The reason this second example might be a problem is that the compiler
876 is, in general, free to reorder operations when it doesn't have a
877 visible reason to keep them in the same order. In this case, the
878 compiler doesn't know that the order of assignments is important, so its
879 optimization pass is permitted to exchange their order.
880 There's no telling whether it will actually do this, and it is possible
881 that passing the compiler different optimization flags or changing
882 compiler versions will produce different behavior.
884 The following is @emph{not} a solution, because locks neither prevent
885 interrupts nor prevent the compiler from reordering the code within the
886 region where the lock is held:
889 lock_acquire (&timer_lock); /* INCORRECT CODE */
890 timer_put_char = 'x';
892 lock_release (&timer_lock);
895 Fortunately, real solutions do exist. One possibility is to
896 disable interrupts around the assignments. This does not prevent
897 reordering, but it makes the assignments atomic as observed by the
898 interrupt handler. It also has the extra runtime cost of disabling and
899 re-enabling interrupts:
902 enum intr_level old_level = intr_disable ();
903 timer_put_char = 'x';
905 intr_set_level (old_level);
908 A second possibility is to mark the declarations of
909 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
910 keyword tells the compiler that the variables are externally observable
911 and restricts its latitude for optimization. However, the semantics of
912 @samp{volatile} are not well-defined, so it is not a good general
915 Usually, the best solution is to use a compiler feature called a
916 @dfn{memory barrier}, a special statement that prevents the compiler
917 from reordering memory operations across the barrier. In Pintos,
918 @file{threads/synch.h} defines the @code{barrier()} macro as a memory
919 barrier. Here's how we would use a memory barrier to fix this code:
922 timer_put_char = 'x';
927 The compiler also treats invocation of any function defined externally,
928 that is, in another source file, as a limited form of a memory barrier.
929 Specifically, the compiler assumes that any externally defined function
930 may access any statically or dynamically allocated data and any local
931 variable whose address is taken. This often means that explicit
932 barriers can be omitted, and, indeed, this is why the base Pintos code
933 does not need any barriers.
935 A function defined in the same source file, or in a header included by
936 the source file, cannot be relied upon as a memory barrier.
937 This applies even to invocation of a function before its
938 definition, because the compiler may read and parse the entire source
939 file before performing optimization.
941 @node Interrupt Handling
942 @section Interrupt Handling
944 An @dfn{interrupt} notifies the CPU of some event. Much of the work
945 of an operating system relates to interrupts in one way or another.
946 For our purposes, we classify interrupts into two broad categories:
950 @dfn{Internal interrupts}, that is, interrupts caused directly by CPU
951 instructions. System calls, attempts at invalid memory access
952 (@dfn{page faults}), and attempts to divide by zero are some activities
953 that cause internal interrupts. Because they are caused by CPU
954 instructions, internal interrupts are @dfn{synchronous} or synchronized
955 with CPU instructions. @func{intr_disable} does not disable internal
959 @dfn{External interrupts}, that is, interrupts originating outside the
960 CPU. These interrupts come from hardware devices such as the system
961 timer, keyboard, serial ports, and disks. External interrupts are
962 @dfn{asynchronous}, meaning that their delivery is not
963 synchronized with instruction execution. Handling of external interrupts
964 can be postponed with @func{intr_disable} and related functions
965 (@pxref{Disabling Interrupts}).
968 The CPU treats both classes of interrupts largely the same way,
969 so Pintos has common infrastructure to handle both classes.
970 The following section describes this
971 common infrastructure. The sections after that give the specifics of
972 external and internal interrupts.
974 If you haven't already read chapter 3, ``Basic Execution Environment,''
975 in @bibref{IA32-v1}, it is recommended that you do so now. You might
976 also want to skim chapter 5, ``Interrupt and Exception Handling,'' in
980 * Interrupt Infrastructure::
981 * Internal Interrupt Handling::
982 * External Interrupt Handling::
985 @node Interrupt Infrastructure
986 @subsection Interrupt Infrastructure
988 When an interrupt occurs, the CPU saves
989 its most essential state on a stack and jumps to an interrupt
990 handler routine. The 80@var{x}86 architecture supports 256
991 interrupts, numbered 0 through 255, each with an independent
992 handler defined in an array called the @dfn{interrupt
993 descriptor table} or IDT.
995 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
996 IDT so that each entry points to a unique entry point in
997 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
998 @var{NN} is the interrupt number in
999 hexadecimal. Because the CPU doesn't give
1000 us any other way to find out the interrupt number, this entry point
1001 pushes the interrupt number on the stack. Then it jumps to
1002 @func{intr_entry}, which pushes all the registers that the processor
1003 didn't already push for us, and then calls @func{intr_handler}, which
1004 brings us back into C in @file{threads/interrupt.c}.
1006 The main job of @func{intr_handler} is to call the function
1007 registered for handling the particular interrupt. (If no
1008 function is registered, it dumps some information to the console and
1009 panics.) It also does some extra processing for external
1010 interrupts (@pxref{External Interrupt Handling}).
1012 When @func{intr_handler} returns, the assembly code in
1013 @file{threads/intr-stubs.S} restores all the CPU registers saved
1014 earlier and directs the CPU to return from the interrupt.
1016 The following types and functions are common to all
1019 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
1020 This is how an interrupt handler function must be declared. Its @var{frame}
1021 argument (see below) allows it to determine the cause of the interrupt
1022 and the state of the thread that was interrupted.
1025 @deftp {Type} {struct intr_frame}
1026 The stack frame of an interrupt handler, as saved by the CPU, the interrupt
1027 stubs, and @func{intr_entry}. Its most interesting members are described
1031 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
1032 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
1033 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
1034 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
1035 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
1036 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
1037 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
1038 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
1039 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
1040 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
1041 Register values in the interrupted thread, pushed by @func{intr_entry}.
1042 The @code{esp_dummy} value isn't actually used (refer to the
1043 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1046 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1047 The interrupt vector number, ranging from 0 to 255.
1050 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1051 The ``error code'' pushed on the stack by the CPU for some internal
1055 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1056 The address of the next instruction to be executed by the interrupted
1060 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1061 The interrupted thread's stack pointer.
1064 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1065 Returns the name of the interrupt numbered @var{vec}, or
1066 @code{"unknown"} if the interrupt has no registered name.
1069 @node Internal Interrupt Handling
1070 @subsection Internal Interrupt Handling
1072 Internal interrupts are caused directly by CPU instructions executed by
1073 the running kernel thread or user process (from project 2 onward). An
1074 internal interrupt is therefore said to arise in a ``process context.''
1076 In an internal interrupt's handler, it can make sense to examine the
1077 @struct{intr_frame} passed to the interrupt handler, or even to modify
1078 it. When the interrupt returns, modifications in @struct{intr_frame}
1079 become changes to the calling thread or process's state. For example,
1080 the Pintos system call handler returns a value to the user program by
1081 modifying the saved EAX register (@pxref{System Call Details}).
1083 There are no special restrictions on what an internal interrupt
1084 handler can or can't do. Generally they should run with interrupts
1085 enabled, just like other code, and so they can be preempted by other
1086 kernel threads. Thus, they do need to synchronize with other threads
1087 on shared data and other resources (@pxref{Synchronization}).
1089 Internal interrupt handlers can be invoked recursively. For example,
1090 the system call handler might cause a page fault while attempting to
1091 read user memory. Deep recursion would risk overflowing the limited
1092 kernel stack (@pxref{struct thread}), but should be unnecessary.
1094 @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})
1095 Registers @var{handler} to be called when internal interrupt numbered
1096 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1099 If @var{level} is @code{INTR_ON}, external interrupts will be processed
1100 normally during the interrupt handler's execution, which is normally
1101 desirable. Specifying @code{INTR_OFF} will cause the CPU to disable
1102 external interrupts when it invokes the interrupt handler. The effect
1103 is slightly different from calling @func{intr_disable} inside the
1104 handler, because that leaves a window of one or more CPU instructions in
1105 which external interrupts are still enabled. This is important for the
1106 page fault handler; refer to the comments in @file{userprog/exception.c}
1109 @var{dpl} determines how the interrupt can be invoked. If @var{dpl} is
1110 0, then the interrupt can be invoked only by kernel threads. Otherwise
1111 @var{dpl} should be 3, which allows user processes to invoke the
1112 interrupt with an explicit INT instruction. The value of @var{dpl}
1113 doesn't affect user processes' ability to invoke the interrupt
1114 indirectly, e.g.@: an invalid memory reference will cause a page fault
1115 regardless of @var{dpl}.
1118 @node External Interrupt Handling
1119 @subsection External Interrupt Handling
1121 External interrupts are caused by events outside the CPU.
1122 They are asynchronous, so they can be invoked at any time that
1123 interrupts have not been disabled. We say that an external interrupt
1124 runs in an ``interrupt context.''
1126 In an external interrupt, the @struct{intr_frame} passed to the
1127 handler is not very meaningful. It describes the state of the thread
1128 or process that was interrupted, but there is no way to predict which
1129 one that is. It is possible, although rarely useful, to examine it, but
1130 modifying it is a recipe for disaster.
1132 Only one external interrupt may be processed at a time. Neither
1133 internal nor external interrupt may nest within an external interrupt
1134 handler. Thus, an external interrupt's handler must run with interrupts
1135 disabled (@pxref{Disabling Interrupts}).
1137 An external interrupt handler must not sleep or yield, which rules out
1138 calling @func{lock_acquire}, @func{thread_yield}, and many other
1139 functions. Sleeping in interrupt context would effectively put the
1140 interrupted thread to sleep, too, until the interrupt handler was again
1141 scheduled and returned. This would be unfair to the unlucky thread, and
1142 it would deadlock if the handler were waiting for the sleeping thread
1143 to, e.g., release a lock.
1145 An external interrupt handler
1146 effectively monopolizes the machine and delays all other activities.
1147 Therefore, external interrupt handlers should complete as quickly as
1148 they can. Anything that require much CPU time should instead run in a
1149 kernel thread, possibly one that the interrupt triggers using a
1150 synchronization primitive.
1152 External interrupts are controlled by a
1153 pair of devices outside the CPU called @dfn{programmable interrupt
1154 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1155 CPU's IDT, it also initializes the PICs for interrupt handling. The
1156 PICs also must be ``acknowledged'' at the end of processing for each
1157 external interrupt. @func{intr_handler} takes care of that by calling
1158 @func{pic_end_of_interrupt}, which properly signals the PICs.
1160 The following functions relate to external
1163 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1164 Registers @var{handler} to be called when external interrupt numbered
1165 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1166 purposes. The handler will run with interrupts disabled.
1169 @deftypefun bool intr_context (void)
1170 Returns true if we are running in an interrupt context, otherwise
1171 false. Mainly used in functions that might sleep
1172 or that otherwise should not be called from interrupt context, in this
1175 ASSERT (!intr_context ());
1179 @deftypefun void intr_yield_on_return (void)
1180 When called in an interrupt context, causes @func{thread_yield} to be
1181 called just before the interrupt returns. Used
1182 in the timer interrupt handler when a thread's time slice expires, to
1183 cause a new thread to be scheduled.
1186 @node Memory Allocation
1187 @section Memory Allocation
1189 Pintos contains two memory allocators, one that allocates memory in
1190 units of a page, and one that can allocate blocks of any size.
1197 @node Page Allocator
1198 @subsection Page Allocator
1200 The page allocator declared in @file{threads/palloc.h} allocates
1201 memory in units of a page. It is most often used to allocate memory
1202 one page at a time, but it can also allocate multiple contiguous pages
1205 The page allocator divides the memory it allocates into two pools,
1206 called the kernel and user pools. By default, each pool gets half of
1207 system memory, but this can be changed with the @option{-ul} kernel
1209 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1210 pool or the other. If one pool becomes empty, the other may still
1211 have free pages. The user pool should be used for allocating memory
1212 for user processes and the kernel pool for all other allocations.
1213 This will only become important starting with project 3. Until then,
1214 all allocations should be made from the kernel pool.
1216 Each pool's usage is tracked with a bitmap, one bit per page in
1217 the pool. A request to allocate @var{n} pages scans the bitmap
1218 for @var{n} consecutive bits set to
1219 false, indicating that those pages are free, and then sets those bits
1220 to true to mark them as used. This is a ``first fit'' allocation
1221 strategy (@pxref{Wilson}).
1223 The page allocator is subject to fragmentation. That is, it may not
1224 be possible to allocate @var{n} contiguous pages even though @var{n}
1225 or more pages are free, because the free pages are separated by used
1226 pages. In fact, in pathological cases it may be impossible to
1227 allocate 2 contiguous pages even though half of the pool's pages are free.
1228 Single-page requests can't fail due to fragmentation, so
1229 requests for multiple contiguous pages should be limited as much as
1232 Pages may not be allocated from interrupt context, but they may be
1235 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1236 a debugging aid (@pxref{Debugging Tips}).
1238 Page allocator types and functions are described below.
1240 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1241 @deftypefunx {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1242 Obtains and returns one page, or @var{page_cnt} contiguous pages,
1243 respectively. Returns a null pointer if the pages cannot be allocated.
1245 The @var{flags} argument may be any combination of the following flags:
1247 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1248 If the pages cannot be allocated, panic the kernel. This is only
1249 appropriate during kernel initialization. User processes
1250 should never be permitted to panic the kernel.
1253 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1254 Zero all the bytes in the allocated pages before returning them. If not
1255 set, the contents of newly allocated pages are unpredictable.
1258 @defvr {Page Allocator Flag} @code{PAL_USER}
1259 Obtain the pages from the user pool. If not set, pages are allocated
1260 from the kernel pool.
1264 @deftypefun void palloc_free_page (void *@var{page})
1265 @deftypefunx void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1266 Frees one page, or @var{page_cnt} contiguous pages, respectively,
1267 starting at @var{pages}. All of the pages must have been obtained using
1268 @func{palloc_get_page} or @func{palloc_get_multiple}.
1271 @node Block Allocator
1272 @subsection Block Allocator
1274 The block allocator, declared in @file{threads/malloc.h}, can allocate
1275 blocks of any size. It is layered on top of the page allocator
1276 described in the previous section. Blocks returned by the block
1277 allocator are obtained from the kernel pool.
1279 The block allocator uses two different strategies for allocating memory.
1280 The first strategy applies to blocks that are 1 kB or smaller
1281 (one-fourth of the page size). These allocations are rounded up to the
1282 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1283 grouped into a page used only for allocations of that size.
1285 The second strategy applies to blocks larger than 1 kB.
1286 These allocations (plus a small amount of overhead) are rounded up to
1287 the nearest page in size, and then the block allocator requests that
1288 number of contiguous pages from the page allocator.
1290 In either case, the difference between the allocation requested size
1291 and the actual block size is wasted. A real operating system would
1292 carefully tune its allocator to minimize this waste, but this is
1293 unimportant in an instructional system like Pintos.
1295 As long as a page can be obtained from the page allocator, small
1296 allocations always succeed. Most small allocations do not require a
1297 new page from the page allocator at all, because they are satisfied
1298 using part of a page already allocated. However, large allocations
1299 always require calling into the page allocator, and any allocation
1300 that needs more than one contiguous page can fail due to fragmentation,
1301 as already discussed in the previous section. Thus, you should
1302 minimize the number of large allocations in your code, especially
1303 those over approximately 4 kB each.
1305 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1306 a debugging aid (@pxref{Debugging Tips}).
1308 The block allocator may not be called from interrupt context.
1310 The block allocator functions are described below. Their interfaces are
1311 the same as the standard C library functions of the same names.
1313 @deftypefun {void *} malloc (size_t @var{size})
1314 Obtains and returns a new block, from the kernel pool, at least
1315 @var{size} bytes long. Returns a null pointer if @var{size} is zero or
1316 if memory is not available.
1319 @deftypefun {void *} calloc (size_t @var{a}, size_t @var{b})
1320 Obtains a returns a new block, from the kernel pool, at least
1321 @code{@var{a} * @var{b}} bytes long. The block's contents will be
1322 cleared to zeros. Returns a null pointer if @var{a} or @var{b} is zero
1323 or if insufficient memory is available.
1326 @deftypefun {void *} realloc (void *@var{block}, size_t @var{new_size})
1327 Attempts to resize @var{block} to @var{new_size} bytes, possibly moving
1328 it in the process. If successful, returns the new block, in which case
1329 the old block must no longer be accessed. On failure, returns a null
1330 pointer, and the old block remains valid.
1332 A call with @var{block} null is equivalent to @func{malloc}. A call
1333 with @var{new_size} zero is equivalent to @func{free}.
1336 @deftypefun void free (void *@var{block})
1337 Frees @var{block}, which must have been previously returned by
1338 @func{malloc}, @func{calloc}, or @func{realloc} (and not yet freed).
1341 @node Virtual Addresses
1342 @section Virtual Addresses
1344 A 32-bit virtual address can be divided into a 20-bit @dfn{page number}
1345 and a 12-bit @dfn{page offset} (or just @dfn{offset}), like this:
1350 +-------------------+-----------+
1351 | Page Number | Offset |
1352 +-------------------+-----------+
1357 Header @file{threads/vaddr.h} defines these functions and macros for
1358 working with virtual addresses:
1362 The bit index (0) and number of bits (12) of the offset part of a
1363 virtual address, respectively.
1367 A bit mask with the bits in the page offset set to 1, the rest set to 0
1372 The page size in bytes (4,096).
1375 @deftypefun unsigned pg_ofs (const void *@var{va})
1376 Extracts and returns the page offset in virtual address @var{va}.
1379 @deftypefun uintptr_t pg_no (const void *@var{va})
1380 Extracts and returns the page number in virtual address @var{va}.
1383 @deftypefun {void *} pg_round_down (const void *@var{va})
1384 Returns the start of the virtual page that @var{va} points within, that
1385 is, @var{va} with the page offset set to 0.
1388 @deftypefun {void *} pg_round_up (const void *@var{va})
1389 Returns @var{va} rounded up to the nearest page boundary.
1392 Virtual memory in Pintos is divided into two regions: user virtual
1393 memory and kernel virtual memory (@pxref{Virtual Memory Layout}). The
1394 boundary between them is @code{PHYS_BASE}:
1397 Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
1398 GB), but it may be changed to any multiple of @t{0x10000000} from
1399 @t{0x80000000} to @t{0xf0000000}.
1401 User virtual memory ranges from virtual address 0 up to
1402 @code{PHYS_BASE}. Kernel virtual memory occupies the rest of the
1403 virtual address space, from @code{PHYS_BASE} up to 4 GB.
1406 @deftypefun {bool} is_user_vaddr (const void *@var{va})
1407 @deftypefunx {bool} is_kernel_vaddr (const void *@var{va})
1408 Returns true if @var{va} is a user or kernel virtual address,
1409 respectively, false otherwise.
1412 The 80@var{x}86 doesn't provide any way to directly access memory given
1413 a physical address. This ability is often necessary in an operating
1414 system kernel, so Pintos works around it by mapping kernel virtual
1415 memory one-to-one to physical memory. That is, virtual address
1416 @code{PHYS_BASE} accesses physical address 0, virtual address
1417 @code{PHYS_BASE} + @t{0x1234} accesses physical address @t{0x1234}, and
1418 so on up to the size of the machine's physical memory. Thus, adding
1419 @code{PHYS_BASE} to a physical address obtains a kernel virtual address
1420 that accesses that address; conversely, subtracting @code{PHYS_BASE}
1421 from a kernel virtual address obtains the corresponding physical
1422 address. Header @file{threads/vaddr.h} provides a pair of functions to
1423 do these translations:
1425 @deftypefun {void *} ptov (uintptr_t @var{pa})
1426 Returns the kernel virtual address corresponding to physical address
1427 @var{pa}, which should be between 0 and the number of bytes of physical
1431 @deftypefun {uintptr_t} vtop (void *@var{va})
1432 Returns the physical address corresponding to @var{va}, which must be a
1433 kernel virtual address.
1439 The code in @file{pagedir.c} is an abstract interface to the 80@var{x}86
1440 hardware page table, also called a ``page directory'' by Intel processor
1441 documentation. The page table interface uses a @code{uint32_t *} to
1442 represent a page table because this is convenient for accessing their
1445 The sections below describe the page table interface and internals.
1448 * Page Table Creation Destruction Activation::
1449 * Page Tables Inspection and Updates::
1450 * Page Table Accessed and Dirty Bits::
1451 * Page Table Details::
1454 @node Page Table Creation Destruction Activation
1455 @subsection Creation, Destruction, and Activation
1457 These functions create, destroy, and activate page tables. The base
1458 Pintos code already calls these functions where necessary, so it should
1459 not be necessary to call them yourself.
1461 @deftypefun {uint32_t *} pagedir_create (void)
1462 Creates and returns a new page table. The new page table contains
1463 Pintos's normal kernel virtual page mappings, but no user virtual
1466 Returns a null pointer if memory cannot be obtained.
1469 @deftypefun void pagedir_destroy (uint32_t *@var{pd})
1470 Frees all of the resources held by @var{pd}, including the page table
1471 itself and the frames that it maps.
1474 @deftypefun void pagedir_activate (uint32_t *@var{pd})
1475 Activates @var{pd}. The active page table is the one used by the CPU to
1476 translate memory references.
1479 @node Page Tables Inspection and Updates
1480 @subsection Inspection and Updates
1482 These functions examine or update the mappings from pages to frames
1483 encapsulated by a page table. They work on both active and inactive
1484 page tables (that is, those for running and suspended processes),
1485 flushing the TLB as necessary.
1487 @deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
1488 Adds to @var{pd} a mapping from user page @var{upage} to the frame identified
1489 by kernel virtual address @var{kpage}. If @var{writable} is true, the
1490 page is mapped read/write; otherwise, it is mapped read-only.
1492 User page @var{upage} must not already be mapped in @var{pd}.
1494 Kernel page @var{kpage} should be a kernel virtual address obtained from
1495 the user pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why
1498 Returns true if successful, false on failure. Failure will occur if
1499 additional memory required for the page table cannot be obtained.
1502 @deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
1503 Looks up the frame mapped to @var{uaddr} in @var{pd}. Returns the
1504 kernel virtual address for that frame, if @var{uaddr} is mapped, or a
1505 null pointer if it is not.
1508 @deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{page})
1509 Marks @var{page} ``not present'' in @var{pd}. Later accesses to
1510 the page will fault.
1512 Other bits in the page table for @var{page} are preserved, permitting
1513 the accessed and dirty bits (see the next section) to be checked.
1515 This function has no effect if @var{page} is not mapped.
1518 @node Page Table Accessed and Dirty Bits
1519 @subsection Accessed and Dirty Bits
1521 80@var{x}86 hardware provides some assistance for implementing page
1522 replacement algorithms, through a pair of bits in the page table entry
1523 (PTE) for each page. On any read or write to a page, the CPU sets the
1524 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
1525 sets the @dfn{dirty bit} to 1. The CPU never resets these bits to 0,
1526 but the OS may do so.
1528 Proper interpretation of these bits requires understanding of
1529 @dfn{aliases}, that is, two (or more) pages that refer to the same
1530 frame. When an aliased frame is accessed, the accessed and dirty bits
1531 are updated in only one page table entry (the one for the page used for
1532 access). The accessed and dirty bits for the other aliases are not
1535 @xref{Accessed and Dirty Bits}, on applying these bits in implementing
1536 page replacement algorithms.
1538 @deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{page})
1539 @deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{page})
1540 Returns true if page directory @var{pd} contains a page table entry for
1541 @var{page} that is marked dirty (or accessed). Otherwise,
1545 @deftypefun void pagedir_set_dirty (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1546 @deftypefunx void pagedir_set_accessed (uint32_t *@var{pd}, const void *@var{page}, bool @var{value})
1547 If page directory @var{pd} has a page table entry for @var{page}, then
1548 its dirty (or accessed) bit is set to @var{value}.
1551 @node Page Table Details
1552 @subsection Page Table Details
1554 The functions provided with Pintos are sufficient to implement the
1555 projects. However, you may still find it worthwhile to understand the
1556 hardware page table format, so we'll go into a little detail in this
1560 * Page Table Structure::
1561 * Page Table Entry Format::
1562 * Page Directory Entry Format::
1565 @node Page Table Structure
1566 @subsubsection Structure
1568 The top-level paging data structure is a page called the ``page
1569 directory'' (PD) arranged as an array of 1,024 32-bit page directory
1570 entries (PDEs), each of which represents 4 MB of virtual memory. Each
1571 PDE may point to the physical address of another page called a
1572 ``page table'' (PT) arranged, similarly, as an array of 1,024
1573 32-bit page table entries (PTEs), each of which translates a single 4
1574 kB virtual page to a physical page.
1576 Translation of a virtual address into a physical address follows
1577 the three-step process illustrated in the diagram
1578 below:@footnote{Actually, virtual to physical translation on the
1579 80@var{x}86 architecture occurs via an intermediate ``linear
1580 address,'' but Pintos (and most modern 80@var{x}86 OSes) set up the CPU
1581 so that linear and virtual addresses are one and the same. Thus, you
1582 can effectively ignore this CPU feature.}
1586 The most-significant 10 bits of the virtual address (bits 22@dots{}31)
1587 index the page directory. If the PDE is marked ``present,'' the
1588 physical address of a page table is read from the PDE thus obtained.
1589 If the PDE is marked ``not present'' then a page fault occurs.
1592 The next 10 bits of the virtual address (bits 12@dots{}21) index
1593 the page table. If the PTE is marked ``present,'' the physical
1594 address of a data page is read from the PTE thus obtained. If the PTE
1595 is marked ``not present'' then a page fault occurs.
1598 The least-significant 12 bits of the virtual address (bits 0@dots{}11)
1599 are added to the data page's physical base address, yielding the final
1606 +----------------------+----------------------+----------------------+
1607 | Page Directory Index | Page Table Index | Page Offset |
1608 +----------------------+----------------------+----------------------+
1610 _______/ _______/ _____/
1612 / Page Directory / Page Table / Data Page
1613 / .____________. / .____________. / .____________.
1614 |1,023|____________| |1,023|____________| | |____________|
1615 |1,022|____________| |1,022|____________| | |____________|
1616 |1,021|____________| |1,021|____________| \__\|____________|
1617 |1,020|____________| |1,020|____________| /|____________|
1619 | | | \____\| |_ | |
1620 | | . | /| . | \ | . |
1621 \____\| . |_ | . | | | . |
1622 /| . | \ | . | | | . |
1623 | . | | | . | | | . |
1625 |____________| | |____________| | |____________|
1626 4|____________| | 4|____________| | |____________|
1627 3|____________| | 3|____________| | |____________|
1628 2|____________| | 2|____________| | |____________|
1629 1|____________| | 1|____________| | |____________|
1630 0|____________| \__\0|____________| \____\|____________|
1635 Pintos provides some macros and functions that are useful for working
1636 with raw page tables:
1640 The starting bit index (12) and number of bits (10), respectively, in a
1645 A bit mask with the bits in the page table index set to 1 and the rest
1646 set to 0 (@t{0x3ff000}).
1650 The number of bytes of virtual address space that a single page table
1651 page covers (4,194,304 bytes, or 4 MB).
1656 The starting bit index (22) and number of bits (10), respectively, in a
1657 page directory index.
1661 A bit mask with the bits in the page directory index set to 1 and other
1662 bits set to 0 (@t{0xffc00000}).
1665 @deftypefun uintptr_t pd_no (const void *@var{va})
1666 @deftypefunx uintptr_t pt_no (const void *@var{va})
1667 Returns the page directory index or page table index, respectively, for
1668 virtual address @var{va}. These functions are defined in
1669 @file{threads/pte.h}.
1672 @deftypefun unsigned pg_ofs (const void *@var{va})
1673 Returns the page offset for virtual address @var{va}. This function is
1674 defined in @file{threads/vaddr.h}.
1677 @node Page Table Entry Format
1678 @subsubsection Page Table Entry Format
1680 You do not need to understand the PTE format to do the Pintos
1681 projects, unless you wish to incorporate the page table into your
1682 supplemental page table (@pxref{Managing the Supplemental Page Table}).
1684 The actual format of a page table entry is summarized below. For
1685 complete information, refer to section 3.7, ``Page Translation Using
1686 32-Bit Physical Addressing,'' in @bibref{IA32-v3a}.
1690 31 12 11 9 6 5 2 1 0
1691 +---------------------------------------+----+----+-+-+---+-+-+-+
1692 | Physical Address | AVL| |D|A| |U|W|P|
1693 +---------------------------------------+----+----+-+-+---+-+-+-+
1697 Some more information on each bit is given below. The names are
1698 @file{threads/pte.h} macros that represent the bits' values:
1701 Bit 0, the ``present'' bit. When this bit is 1, the
1702 other bits are interpreted as described below. When this bit is 0, any
1703 attempt to access the page will page fault. The remaining bits are then
1704 not used by the CPU and may be used by the OS for any purpose.
1708 Bit 1, the ``read/write'' bit. When it is 1, the page
1709 is writable. When it is 0, write attempts will page fault.
1713 Bit 2, the ``user/supervisor'' bit. When it is 1, user
1714 processes may access the page. When it is 0, only the kernel may access
1715 the page (user accesses will page fault).
1717 Pintos clears this bit in PTEs for kernel virtual memory, to prevent
1718 user processes from accessing them.
1722 Bit 5, the ``accessed'' bit. @xref{Page Table Accessed
1727 Bit 6, the ``dirty'' bit. @xref{Page Table Accessed and
1732 Bits 9@dots{}11, available for operating system use.
1733 Pintos, as provided, does not use them and sets them to 0.
1737 Bits 12@dots{}31, the top 20 bits of the physical address of a frame.
1738 The low 12 bits of the frame's address are always 0.
1741 Other bits are either reserved or uninteresting in a Pintos context and
1742 should be set to@tie{}0.
1744 Header @file{threads/pte.h} defines three functions for working with
1747 @deftypefun uint32_t pte_create_kernel (uint32_t *@var{page}, bool @var{writable})
1748 Returns a page table entry that points to @var{page}, which should be a
1749 kernel virtual address. The PTE's present bit will be set. It will be
1750 marked for kernel-only access. If @var{writable} is true, the PTE will
1751 also be marked read/write; otherwise, it will be read-only.
1754 @deftypefun uint32_t pte_create_user (uint32_t *@var{page}, bool @var{writable})
1755 Returns a page table entry that points to @var{page}, which should be
1756 the kernel virtual address of a frame in the user pool (@pxref{Why
1757 PAL_USER?}). The PTE's present bit will be set and it will be marked to
1758 allow user-mode access. If @var{writable} is true, the PTE will also be
1759 marked read/write; otherwise, it will be read-only.
1762 @deftypefun {void *} pte_get_page (uint32_t @var{pte})
1763 Returns the kernel virtual address for the frame that @var{pte} points
1764 to. The @var{pte} may be present or not-present; if it is not-present
1765 then the pointer returned is only meaningful if the address bits in the PTE
1766 actually represent a physical address.
1769 @node Page Directory Entry Format
1770 @subsubsection Page Directory Entry Format
1772 Page directory entries have the same format as PTEs, except that the
1773 physical address points to a page table page instead of a frame. Header
1774 @file{threads/pte.h} defines two functions for working with page
1777 @deftypefun uint32_t pde_create (uint32_t *@var{pt})
1778 Returns a page directory that points to @var{page}, which should be the
1779 kernel virtual address of a page table page. The PDE's present bit will
1780 be set, it will be marked to allow user-mode access, and it will be
1784 @deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
1785 Returns the kernel virtual address for the page table page that
1786 @var{pde}, which must be marked present, points to.
1792 Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
1793 To use it you will need to include its header file,
1794 @file{lib/kernel/hash.h}, with @code{#include <hash.h>}.
1795 No code provided with Pintos uses the hash table, which means that you
1796 are free to use it as is, modify its implementation for your own
1797 purposes, or ignore it, as you wish.
1799 Most implementations of the virtual memory project use a hash table to
1800 translate pages to frames. You may find other uses for hash tables as
1805 * Basic Hash Functions::
1806 * Hash Search Functions::
1807 * Hash Iteration Functions::
1808 * Hash Table Example::
1809 * Hash Auxiliary Data::
1810 * Hash Synchronization::
1813 @node Hash Data Types
1814 @subsection Data Types
1816 A hash table is represented by @struct{hash}.
1818 @deftp {Type} {struct hash}
1819 Represents an entire hash table. The actual members of @struct{hash}
1820 are ``opaque.'' That is, code that uses a hash table should not access
1821 @struct{hash} members directly, nor should it need to. Instead, use
1822 hash table functions and macros.
1825 The hash table operates on elements of type @struct{hash_elem}.
1827 @deftp {Type} {struct hash_elem}
1828 Embed a @struct{hash_elem} member in the structure you want to include
1829 in a hash table. Like @struct{hash}, @struct{hash_elem} is opaque.
1830 All functions for operating on hash table elements actually take and
1831 return pointers to @struct{hash_elem}, not pointers to your hash table's
1835 You will often need to obtain a @struct{hash_elem} given a real element
1836 of the hash table, and vice versa. Given a real element of the hash
1837 table, you may use the @samp{&} operator to obtain a pointer to its
1838 @struct{hash_elem}. Use the @code{hash_entry()} macro to go the other
1841 @deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
1842 Returns a pointer to the structure that @var{elem}, a pointer to a
1843 @struct{hash_elem}, is embedded within. You must provide @var{type},
1844 the name of the structure that @var{elem} is inside, and @var{member},
1845 the name of the member in @var{type} that @var{elem} points to.
1847 For example, suppose @code{h} is a @code{struct hash_elem *} variable
1848 that points to a @struct{thread} member (of type @struct{hash_elem})
1849 named @code{h_elem}. Then, @code{hash_entry@tie{}(h, struct thread, h_elem)}
1850 yields the address of the @struct{thread} that @code{h} points within.
1853 @xref{Hash Table Example}, for an example.
1855 Each hash table element must contain a key, that is, data that
1856 identifies and distinguishes elements, which must be unique
1857 among elements in the hash table. (Elements may
1858 also contain non-key data that need not be unique.) While an element is
1859 in a hash table, its key data must not be changed. Instead, if need be,
1860 remove the element from the hash table, modify its key, then reinsert
1863 For each hash table, you must write two functions that act on keys: a
1864 hash function and a comparison function. These functions must match the
1865 following prototypes:
1867 @deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
1868 Returns a hash of @var{element}'s data, as a value anywhere in the range
1869 of @code{unsigned int}. The hash of an element should be a
1870 pseudo-random function of the element's key. It must not depend on
1871 non-key data in the element or on any non-constant data other than the
1872 key. Pintos provides the following functions as a suitable basis for
1875 @deftypefun unsigned hash_bytes (const void *@var{buf}, size_t *@var{size})
1876 Returns a hash of the @var{size} bytes starting at @var{buf}. The
1877 implementation is the general-purpose
1878 @uref{http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash, Fowler-Noll-Vo
1879 hash} for 32-bit words.
1882 @deftypefun unsigned hash_string (const char *@var{s})
1883 Returns a hash of null-terminated string @var{s}.
1886 @deftypefun unsigned hash_int (int @var{i})
1887 Returns a hash of integer @var{i}.
1890 If your key is a single piece of data of an appropriate type, it is
1891 sensible for your hash function to directly return the output of one of
1892 these functions. For multiple pieces of data, you may wish to combine
1893 the output of more than one call to them using, e.g., the @samp{^}
1895 operator. Finally, you may entirely ignore these functions and write
1896 your own hash function from scratch, but remember that your goal is to
1897 build an operating system kernel, not to design a hash function.
1899 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1902 @deftp {Type} {bool hash_less_func (const struct hash_elem *@var{a}, const struct hash_elem *@var{b}, void *@var{aux})}
1903 Compares the keys stored in elements @var{a} and @var{b}. Returns
1904 true if @var{a} is less than @var{b}, false if @var{a} is greater than
1905 or equal to @var{b}.
1907 If two elements compare equal, then they must hash to equal values.
1909 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1912 @xref{Hash Table Example}, for hash and comparison function examples.
1914 A few functions accept a pointer to a third kind of
1915 function as an argument:
1917 @deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
1918 Performs some kind of action, chosen by the caller, on @var{element}.
1920 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
1923 @node Basic Hash Functions
1924 @subsection Basic Functions
1926 These functions create, destroy, and inspect hash tables.
1928 @deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
1929 Initializes @var{hash} as a hash table with @var{hash_func} as hash
1930 function, @var{less_func} as comparison function, and @var{aux} as
1932 Returns true if successful, false on failure. @func{hash_init} calls
1933 @func{malloc} and fails if memory cannot be allocated.
1935 @xref{Hash Auxiliary Data}, for an explanation of @var{aux}, which is
1936 most often a null pointer.
1939 @deftypefun void hash_clear (struct hash *@var{hash}, hash_action_func *@var{action})
1940 Removes all the elements from @var{hash}, which must have been
1941 previously initialized with @func{hash_init}.
1943 If @var{action} is non-null, then it is called once for each element in
1944 the hash table, which gives the caller an opportunity to deallocate any
1945 memory or other resources used by the element. For example, if the hash
1946 table elements are dynamically allocated using @func{malloc}, then
1947 @var{action} could @func{free} the element. This is safe because
1948 @func{hash_clear} will not access the memory in a given hash element
1949 after calling @var{action} on it. However, @var{action} must not call
1950 any function that may modify the hash table, such as @func{hash_insert}
1951 or @func{hash_delete}.
1954 @deftypefun void hash_destroy (struct hash *@var{hash}, hash_action_func *@var{action})
1955 If @var{action} is non-null, calls it for each element in the hash, with
1956 the same semantics as a call to @func{hash_clear}. Then, frees the
1957 memory held by @var{hash}. Afterward, @var{hash} must not be passed to
1958 any hash table function, absent an intervening call to @func{hash_init}.
1961 @deftypefun size_t hash_size (struct hash *@var{hash})
1962 Returns the number of elements currently stored in @var{hash}.
1965 @deftypefun bool hash_empty (struct hash *@var{hash})
1966 Returns true if @var{hash} currently contains no elements,
1967 false if @var{hash} contains at least one element.
1970 @node Hash Search Functions
1971 @subsection Search Functions
1973 Each of these functions searches a hash table for an element that
1974 compares equal to one provided. Based on the success of the search,
1975 they perform some action, such as inserting a new element into the hash
1976 table, or simply return the result of the search.
1978 @deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
1979 Searches @var{hash} for an element equal to @var{element}. If none is
1980 found, inserts @var{element} into @var{hash} and returns a null pointer.
1981 If the table already contains an element equal to @var{element}, it is
1982 returned without modifying @var{hash}.
1985 @deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
1986 Inserts @var{element} into @var{hash}. Any element equal to
1987 @var{element} already in @var{hash} is removed. Returns the element
1988 removed, or a null pointer if @var{hash} did not contain an element
1989 equal to @var{element}.
1991 The caller is responsible for deallocating any resources associated with
1992 the returned element, as appropriate. For example, if the hash table
1993 elements are dynamically allocated using @func{malloc}, then the caller
1994 must @func{free} the element after it is no longer needed.
1997 The element passed to the following functions is only used for hashing
1998 and comparison purposes. It is never actually inserted into the hash
1999 table. Thus, only key data in the element needs to be initialized, and
2000 other data in the element will not be used. It often makes sense to
2001 declare an instance of the element type as a local variable, initialize
2002 the key data, and then pass the address of its @struct{hash_elem} to
2003 @func{hash_find} or @func{hash_delete}. @xref{Hash Table Example}, for
2004 an example. (Large structures should not be
2005 allocated as local variables. @xref{struct thread}, for more
2008 @deftypefun {struct hash_elem *} hash_find (struct hash *@var{hash}, struct hash_elem *@var{element})
2009 Searches @var{hash} for an element equal to @var{element}. Returns the
2010 element found, if any, or a null pointer otherwise.
2013 @deftypefun {struct hash_elem *} hash_delete (struct hash *@var{hash}, struct hash_elem *@var{element})
2014 Searches @var{hash} for an element equal to @var{element}. If one is
2015 found, it is removed from @var{hash} and returned. Otherwise, a null
2016 pointer is returned and @var{hash} is unchanged.
2018 The caller is responsible for deallocating any resources associated with
2019 the returned element, as appropriate. For example, if the hash table
2020 elements are dynamically allocated using @func{malloc}, then the caller
2021 must @func{free} the element after it is no longer needed.
2024 @node Hash Iteration Functions
2025 @subsection Iteration Functions
2027 These functions allow iterating through the elements in a hash table.
2028 Two interfaces are supplied. The first requires writing and supplying a
2029 @var{hash_action_func} to act on each element (@pxref{Hash Data Types}).
2031 @deftypefun void hash_apply (struct hash *@var{hash}, hash_action_func *@var{action})
2032 Calls @var{action} once for each element in @var{hash}, in arbitrary
2033 order. @var{action} must not call any function that may modify the hash
2034 table, such as @func{hash_insert} or @func{hash_delete}. @var{action}
2035 must not modify key data in elements, although it may modify any other
2039 The second interface is based on an ``iterator'' data type.
2040 Idiomatically, iterators are used as follows:
2043 struct hash_iterator i;
2046 while (hash_next (&i))
2048 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
2049 @r{@dots{}do something with @i{f}@dots{}}
2053 @deftp {Type} {struct hash_iterator}
2054 Represents a position within a hash table. Calling any function that
2055 may modify a hash table, such as @func{hash_insert} or
2056 @func{hash_delete}, invalidates all iterators within that hash table.
2058 Like @struct{hash} and @struct{hash_elem}, @struct{hash_elem} is opaque.
2061 @deftypefun void hash_first (struct hash_iterator *@var{iterator}, struct hash *@var{hash})
2062 Initializes @var{iterator} to just before the first element in
2066 @deftypefun {struct hash_elem *} hash_next (struct hash_iterator *@var{iterator})
2067 Advances @var{iterator} to the next element in @var{hash}, and returns
2068 that element. Returns a null pointer if no elements remain. After
2069 @func{hash_next} returns null for @var{iterator}, calling it again
2070 yields undefined behavior.
2073 @deftypefun {struct hash_elem *} hash_cur (struct hash_iterator *@var{iterator})
2074 Returns the value most recently returned by @func{hash_next} for
2075 @var{iterator}. Yields undefined behavior after @func{hash_first} has
2076 been called on @var{iterator} but before @func{hash_next} has been
2077 called for the first time.
2080 @node Hash Table Example
2081 @subsection Hash Table Example
2083 Suppose you have a structure, called @struct{page}, that you
2084 want to put into a hash table. First, define @struct{page} to include a
2085 @struct{hash_elem} member:
2090 struct hash_elem hash_elem; /* @r{Hash table element.} */
2091 void *addr; /* @r{Virtual address.} */
2092 /* @r{@dots{}other members@dots{}} */
2096 We write a hash function and a comparison function using @var{addr} as
2097 the key. A pointer can be hashed based on its bytes, and the @samp{<}
2098 operator works fine for comparing pointers:
2101 /* @r{Returns a hash value for page @var{p}.} */
2103 page_hash (const struct hash_elem *p_, void *aux UNUSED)
2105 const struct page *p = hash_entry (p_, struct page, hash_elem);
2106 return hash_bytes (&p->addr, sizeof p->addr);
2109 /* @r{Returns true if page @var{a} precedes page @var{b}.} */
2111 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2114 const struct page *a = hash_entry (a_, struct page, hash_elem);
2115 const struct page *b = hash_entry (b_, struct page, hash_elem);
2117 return a->addr < b->addr;
2122 (The use of @code{UNUSED} in these functions' prototypes suppresses a
2123 warning that @var{aux} is unused. @xref{Function and Parameter
2124 Attributes}, for information about @code{UNUSED}. @xref{Hash Auxiliary
2125 Data}, for an explanation of @var{aux}.)
2127 Then, we can create a hash table like this:
2132 hash_init (&pages, page_hash, page_less, NULL);
2135 Now we can manipulate the hash table we've created. If @code{@var{p}}
2136 is a pointer to a @struct{page}, we can insert it into the hash table
2140 hash_insert (&pages, &p->hash_elem);
2143 @noindent If there's a chance that @var{pages} might already contain a
2144 page with the same @var{addr}, then we should check @func{hash_insert}'s
2147 To search for an element in the hash table, use @func{hash_find}. This
2148 takes a little setup, because @func{hash_find} takes an element to
2149 compare against. Here's a function that will find and return a page
2150 based on a virtual address, assuming that @var{pages} is defined at file
2154 /* @r{Returns the page containing the given virtual @var{address},}
2155 @r{or a null pointer if no such page exists.} */
2157 page_lookup (const void *address)
2160 struct hash_elem *e;
2163 e = hash_find (&pages, &p.hash_elem);
2164 return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
2169 @struct{page} is allocated as a local variable here on the assumption
2170 that it is fairly small. Large structures should not be allocated as
2171 local variables. @xref{struct thread}, for more information.
2173 A similar function could delete a page by address using
2176 @node Hash Auxiliary Data
2177 @subsection Auxiliary Data
2179 In simple cases like the example above, there's no need for the
2180 @var{aux} parameters. In these cases, just pass a null pointer to
2181 @func{hash_init} for @var{aux} and ignore the values passed to the hash
2182 function and comparison functions. (You'll get a compiler warning if
2183 you don't use the @var{aux} parameter, but you can turn that off with
2184 the @code{UNUSED} macro, as shown in the example, or you can just ignore
2187 @var{aux} is useful when you have some property of the data in the
2188 hash table is both constant and needed for hashing or comparison,
2189 but not stored in the data items themselves. For example, if
2190 the items in a hash table are fixed-length strings, but the items
2191 themselves don't indicate what that fixed length is, you could pass
2192 the length as an @var{aux} parameter.
2194 @node Hash Synchronization
2195 @subsection Synchronization
2197 The hash table does not do any internal synchronization. It is the
2198 caller's responsibility to synchronize calls to hash table functions.
2199 In general, any number of functions that examine but do not modify the
2200 hash table, such as @func{hash_find} or @func{hash_next}, may execute
2201 simultaneously. However, these function cannot safely execute at the
2202 same time as any function that may modify a given hash table, such as
2203 @func{hash_insert} or @func{hash_delete}, nor may more than one function
2204 that can modify a given hash table execute safely at once.
2206 It is also the caller's responsibility to synchronize access to data in
2207 hash table elements. How to synchronize access to this data depends on
2208 how it is designed and organized, as with any other data structure.