@node Reference Guide
@appendix Reference Guide
-This chapter is a reference for the Pintos code. It covers the
-entire code base, but you'll only be using Pintos one part at a time,
-so you may find that you want to read each part as you work on the
+This chapter is a reference for the Pintos code. The reference guide
+does not cover all of the code in Pintos, but it does cover those
+pieces that students most often find troublesome. You may find that
+you want to read each part of the reference guide as you work on the
project where it becomes important.
-(Actually, the reference guide is currently incomplete.)
-
We recommend using ``tags'' to follow along with references to function
and variable names (@pxref{Tags}).
@menu
* Pintos Loader::
-* Kernel Initialization::
+* Low-Level Kernel Initialization::
+* High-Level Kernel Initialization::
+* Physical Memory Map::
@end menu
@node Pintos Loader
The first part of Pintos that runs is the loader, in
@file{threads/loader.S}. The PC BIOS loads the loader into memory.
-The loader, in turn, is responsible for initializing the CPU, loading
-the rest of Pintos into memory, and then jumping to its start. It's
-not important to understand exactly what the loader does, but if
+The loader, in turn, is responsible for finding the kernel on disk,
+loading it into memory, and then jumping to its start. It's
+not important to understand exactly how the loader works, but if
you're interested, read on. You should probably read along with the
loader's source. You should also understand the basics of the
80@var{x}86 architecture as described by chapter 3, ``Basic Execution
Environment,'' of @bibref{IA32-v1}.
-Because the PC BIOS loads the loader, the loader has to play by the
-BIOS's rules. In particular, the BIOS only loads 512 bytes (one disk
-sector) into memory. This is a severe restriction and it means that,
-practically speaking, the loader has to be written in assembly
-language.
-
-The Pintos loader first initializes the CPU. The first important part of
-this is to enable the A20 line, that is, the CPU's address line
-numbered 20. For historical reasons, PCs boot with this address
-line fixed at 0, which means that attempts to access memory beyond the
-first 1 MB (2 raised to the 20th power) will fail. Pintos wants to
-access more memory than this, so we have to enable it.
-
-Next, the loader asks the BIOS for the PC's memory size. Again for
-historical reasons, the function that we call in the BIOS to do this
-can only detect up to 64 MB of RAM, so that's the practical limit that
-Pintos can support. The memory size is stashed away in a location in
-the loader that the kernel can read after it boots.
-
-Third, the loader creates a basic page table. This page table maps
+The PC BIOS loads the loader from the first sector of the first hard
+disk, called the @dfn{master boot record} (MBR). PC conventions
+reserve 64 bytes of the MBR for the partition table, and Pintos uses
+about 128 additional bytes for kernel command-line arguments. This
+leaves a little over 300 bytes for the loader's own code. This is a
+severe restriction that means, practically speaking, the loader must
+be written in assembly language.
+
+The Pintos loader and kernel don't have to be on the same disk, nor
+does is the kernel required to be in any particular location on a
+given disk. The loader's first job, then, is to find the kernel by
+reading the partition table on each hard disk, looking for a bootable
+partition of the type used for a Pintos kernel.
+
+When the loader finds a bootable kernel partition, it reads the
+partition's contents into memory at physical address @w{128 kB}. The
+kernel is at the beginning of the partition, which might be larger
+than necessary due to partition boundary alignment conventions, so the
+loader reads no more than @w{512 kB} (and the Pintos build process
+will refuse to produce kernels larger than that). Reading more data
+than this would cross into the region from @w{640 kB} to @w{1 MB} that
+the PC architecture reserves for hardware and the BIOS, and a standard
+PC BIOS does not provide any means to load the kernel above @w{1 MB}.
+
+The loader's final job is to extract the entry point from the loaded
+kernel image and transfer control to it. The entry point is not at a
+predictable location, but the kernel's ELF header contains a pointer
+to it. The loader extracts the pointer and jumps to the location it
+points to.
+
+The Pintos kernel command line
+is stored in the boot loader. The @command{pintos} program actually
+modifies a copy of the boot loader on disk each time it runs the kernel,
+inserting whatever command-line arguments the user supplies to the kernel,
+and then the kernel at boot time reads those arguments out of the boot
+loader in memory. This is not an elegant solution, but it is simple
+and effective.
+
+@node Low-Level Kernel Initialization
+@subsection Low-Level Kernel Initialization
+
+The loader's last action is to transfer control to the kernel's entry
+point, which is @func{start} in @file{threads/start.S}. The job of
+this code is to switch the CPU from legacy 16-bit ``real mode'' into
+the 32-bit ``protected mode'' used by all modern 80@var{x}86 operating
+systems.
+
+The startup code's first task is actually to obtain the machine's
+memory size, by asking the BIOS for the PC's memory size. The
+simplest BIOS function to do this can only detect up to 64 MB of RAM,
+so that's the practical limit that Pintos can support. The function
+stores the memory size, in pages, in global variable
+@code{init_ram_pages}.
+
+The first part of CPU initialization is to enable the A20 line, that
+is, the CPU's address line numbered 20. For historical reasons, PCs
+boot with this address line fixed at 0, which means that attempts to
+access memory beyond the first 1 MB (2 raised to the 20th power) will
+fail. Pintos wants to access more memory than this, so we have to
+enable it.
+
+Next, the loader creates a basic page table. This page table maps
the 64 MB at the base of virtual memory (starting at virtual address
0) directly to the identical physical addresses. It also maps the
same physical memory starting at virtual address
@code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB). The
Pintos kernel only wants the latter mapping, but there's a
chicken-and-egg problem if we don't include the former: our current
-virtual address is roughly @t{0x7c00}, the location where the BIOS
-loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
+virtual address is roughly @t{0x20000}, the location where the loader
+put us, and we can't jump to @t{0xc0020000} until we turn on the
page table, but if we turn on the page table without jumping there,
then we've just pulled the rug out from under ourselves.
After the page table is initialized, we load the CPU's control
-registers to turn on protected mode and paging, and then we set up the
-segment registers. We aren't yet equipped to handle interrupts in
-protected mode, so we disable interrupts.
-
-Finally it's time to load the kernel from disk. We use a simple but
-inflexible method to do this: we program the IDE disk
-controller directly. We assume that the kernel is stored starting
-from the second sector of the first IDE disk (the first sector normally
-contains the boot loader). We also assume that the BIOS has
-already set up the IDE controller for us. We read
-@code{KERNEL_LOAD_PAGES} pages of data (4 kB per page) from the disk directly
-into virtual memory, starting @code{LOADER_KERN_BASE} bytes past
-@code{LOADER_PHYS_BASE}, which by default means that we load the
-kernel starting 1 MB into physical memory.
-
-Then we jump to the start of the compiled kernel image. Using the
-``linker script'' in @file{threads/kernel.lds.S}, the kernel has
-arranged to begin with the assembly module
-@file{threads/start.S}. This assembly module just calls
-@func{main}, which never returns.
-
-There's one more trick: the Pintos kernel command line
-is in stored the boot loader. The @command{pintos} program actually
-modifies a copy of the boot loader on disk each time it runs the kernel,
-putting
-in whatever command line arguments the user supplies to the kernel,
-and then the kernel at boot time reads those arguments out of the boot
-loader in memory. This is not an elegant solution, but it is simple
-and effective.
+registers to turn on protected mode and paging, and set up the segment
+registers. We aren't yet equipped to handle interrupts in protected
+mode, so we disable interrupts. The final step is to call @func{main}.
-@node Kernel Initialization
-@subsection Kernel Initialization
+@node High-Level Kernel Initialization
+@subsection High-Level Kernel Initialization
The kernel proper starts with the @func{main} function. The
@func{main} function is written in C, as will be most of the code we
module's source code, and @file{@var{module}.h} is the module's
header.
-First we initialize kernel RAM in @func{ram_init}. The first step
-is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
+The first step in @func{main} is to call @func{bss_init}, which clears
+out the kernel's ``BSS'', which is the traditional name for a
segment that should be initialized to all zeros. In most C
implementations, whenever you
declare a variable outside a function without providing an
initializer, that variable goes into the BSS. Because it's all zeros, the
BSS isn't stored in the image that the loader brought into memory. We
-just use @func{memset} to zero it out. The other task of
-@func{ram_init} is to read out the machine's memory size from where
-the loader stored it and put it into the @code{ram_pages} variable for
-later use.
-
-Next, @func{thread_init} initializes the thread system. We will defer
-full discussion to our discussion of Pintos threads below. It is
-called so early in initialization because the console, initialized
-just afterward, tries to use locks, and locks in turn require there to be a
-running thread.
-
-Then we initialize the console so that @func{printf} will work.
-@func{main} calls @func{vga_init}, which initializes the VGA text
-display and clears the screen. It also calls @func{serial_init_poll}
-to initialize the first serial port in ``polling mode,'' that is,
-where the kernel busy-waits for the port to be ready for each
-character to be output. (We use polling mode until we're ready to enable
-interrupts, later.) Finally we initialize the console device and
-print a startup message to the console.
-
-@func{main} calls @func{read_command_line} to break the kernel command
+just use @func{memset} to zero it out.
+
+Next, @func{main} calls @func{read_command_line} to break the kernel command
line into arguments, then @func{parse_options} to read any options at
the beginning of the command line. (Actions specified on the
command line execute later.)
-@func{main} calls @func{random_init} to initialize the kernel random
-number generator. If the user specified @option{-rs} on the
-@command{pintos} command line, @func{parse_options} already did
-this, but calling it a second time is harmless.
+@func{thread_init} initializes the thread system. We will defer full
+discussion to our discussion of Pintos threads below. It is called so
+early in initialization because a valid thread structure is a
+prerequisite for acquiring a lock, and lock acquisition in turn is
+important to other Pintos subsystems. Then we initialize the console
+and print a startup message to the console.
-The next block of functions we call initialize the kernel's memory
+The next block of functions we call initializes the kernel's memory
system. @func{palloc_init} sets up the kernel page allocator, which
doles out memory one or more pages at a time (@pxref{Page Allocator}).
@func{malloc_init} sets
@func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
(IDT) to ready it for interrupt handling (@pxref{Interrupt
Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
-handling timer interrupts and keyboard interrupts, respectively. In
+handling timer interrupts and keyboard interrupts, respectively.
+@func{input_init} sets up to merge serial and keyboard input into one
+stream. In
projects 2 and later, we also prepare to handle interrupts caused by
user programs using @func{exception_init} and @func{syscall_init}.
@func{timer_calibrate} calibrates the timer for accurate short delays.
If the file system is compiled in, as it will starting in project 2, we
-initialize the disks with @func{disk_init}, then the
+initialize the IDE disks with @func{ide_init}, then the
file system with @func{filesys_init}.
Boot is complete, so we print a message.
@func{main} calls @func{thread_exit}, which allows any other running
threads to continue running.
+@node Physical Memory Map
+@subsection Physical Memory Map
+
+@multitable {@t{00000000}--@t{00000000}} {Hardware} {Some much longer explanatory text}
+@headitem Memory Range
+@tab Owner
+@tab Contents
+
+@item @t{00000000}--@t{000003ff} @tab CPU @tab Real mode interrupt table.
+@item @t{00000400}--@t{000005ff} @tab BIOS @tab Miscellaneous data area.
+@item @t{00000600}--@t{00007bff} @tab --- @tab ---
+@item @t{00007c00}--@t{00007dff} @tab Pintos @tab Loader.
+@item @t{0000e000}--@t{0000efff} @tab Pintos
+@tab Stack for loader; kernel stack and @struct{thread} for initial
+kernel thread.
+@item @t{0000f000}--@t{0000ffff} @tab Pintos
+@tab Page directory for startup code.
+@item @t{00010000}--@t{00020000} @tab Pintos
+@tab Page tables for startup code.
+@item @t{00020000}--@t{0009ffff} @tab Pintos
+@tab Kernel code, data, and uninitialized data segments.
+@item @t{000a0000}--@t{000bffff} @tab Video @tab VGA display memory.
+@item @t{000c0000}--@t{000effff} @tab Hardware
+@tab Reserved for expansion card RAM and ROM.
+@item @t{000f0000}--@t{000fffff} @tab BIOS @tab ROM BIOS.
+@item @t{00100000}--@t{03ffffff} @tab Pintos @tab Dynamic memory allocation.
+@end multitable
+
@node Threads
@section Threads
priority scheduling in project 1 (@pxref{Priority Scheduling}).
@end deftypecv
+@deftypecv {Member} {@struct{thread}} {@struct{list_elem}} allelem
+This ``list element'' is used to link the thread into the list of all
+threads. Each thread is inserted into this list when it is created
+and removed when it exits. The @func{thread_foreach} function should
+be used to iterate over all threads.
+@end deftypecv
+
@deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
A ``list element'' used to put the thread into doubly linked lists,
either @code{ready_list} (the list of threads ready to run) or a list of
time.
@end deftypefun
+@deftypefun void thread_foreach (thread_action_func *@var{action}, void *@var{aux})
+Iterates over all threads @var{t} and invokes @code{action(t, aux)} on each.
+@var{action} must refer to a function that matches the signature
+given by @func{thread_action_func}:
+
+@deftp {Type} {void thread_action_func (struct thread *@var{thread}, void *@var{aux})}
+Performs some action on a thread, given @var{aux}.
+@end deftp
+@end deftypefun
+
@deftypefun int thread_get_priority (void)
@deftypefunx void thread_set_priority (int @var{new_priority})
Stub to set and get thread priority. @xref{Priority Scheduling}.
member, restores the new thread's @code{stack} into the CPU's stack
pointer, restores registers from the stack, and returns.
-The rest of the scheduler is implemented in @func{schedule_tail}. It
+The rest of the scheduler is implemented in @func{thread_schedule_tail}. It
marks the new thread as running. If the thread we just switched from
is in the dying state, then it also frees the page that contained the
dying thread's @struct{thread} and stack. These couldn't be freed
arguments on the stack and the 80@var{x}86 SVR4 calling convention
requires the caller, not the called function, to remove them when the
call is complete. See @bibref{SysV-i386} chapter 3 for details.}
-calls @func{schedule_tail} (this special case is why
-@func{schedule_tail} is separate from @func{schedule}), and returns.
+calls @func{thread_schedule_tail} (this special case is why
+@func{thread_schedule_tail} is separate from @func{schedule}), and returns.
We fill in its stack frame so that it returns into
@func{kernel_thread}, a function in @file{threads/thread.c}.
* Semaphores::
* Locks::
* Monitors::
-* Memory Barriers::
+* Optimization Barriers::
@end menu
@node Disabling Interrupts
rarely used.
Semaphores were invented by Edsger Dijkstra and first used in the THE
-operating system (@bibref{THE}).
+operating system (@bibref{Dijkstra}).
Pintos' semaphore type and operations are declared in
@file{threads/synch.h}.
A @dfn{lock} is like a semaphore with an initial value of 1
(@pxref{Semaphores}). A lock's equivalent of ``up'' is called
-``acquire'', and the ``down'' operation is called ``release''.
+``release'', and the ``down'' operation is called ``acquire''.
Compared to a semaphore, a lock has one added restriction: only the
thread that acquires a lock, called the lock's ``owner'', is allowed to
The theoretical framework for monitors was laid out by C.@: A.@: R.@:
Hoare (@bibref{Hoare}). Their practical usage was later elaborated in a
-paper on the Mesa operating system (@bibref{Mesa}).
+paper on the Mesa operating system (@bibref{Lampson}).
Condition variable types and functions are declared in
@file{threads/synch.h}.
@}
@end example
-@node Memory Barriers
-@subsection Memory Barriers
+Note that @code{BUF_SIZE} must divide evenly into @code{SIZE_MAX + 1}
+for the above code to be completely correct. Otherwise, it will fail
+the first time @code{head} wraps around to 0. In practice,
+@code{BUF_SIZE} would ordinarily be a power of 2.
+
+@node Optimization Barriers
+@subsection Optimization Barriers
@c We should try to come up with a better example.
@c Perhaps something with a linked list?
-Suppose we add a ``feature'' that, whenever a timer interrupt
-occurs, the character in global variable @code{timer_put_char} is
-printed on the console, but only if global Boolean variable
-@code{timer_do_put} is true.
+An @dfn{optimization barrier} is a special statement that prevents the
+compiler from making assumptions about the state of memory across the
+barrier. The compiler will not reorder reads or writes of variables
+across the barrier or assume that a variable's value is unmodified
+across the barrier, except for local variables whose address is never
+taken. In Pintos, @file{threads/synch.h} defines the @code{barrier()}
+macro as an optimization barrier.
-If interrupts are enabled, this code for setting up @samp{x} to be
-printed is clearly incorrect, because the timer interrupt could intervene
-between the two assignments:
+One reason to use an optimization barrier is when data can change
+asynchronously, without the compiler's knowledge, e.g.@: by another
+thread or an interrupt handler. The @func{too_many_loops} function in
+@file{devices/timer.c} is an example. This function starts out by
+busy-waiting in a loop until a timer tick occurs:
@example
-timer_do_put = true; /* INCORRECT CODE */
-timer_put_char = 'x';
+/* Wait for a timer tick. */
+int64_t start = ticks;
+while (ticks == start)
+ barrier ();
@end example
-It might not be as obvious that the following code is just as
-incorrect:
+@noindent
+Without an optimization barrier in the loop, the compiler could
+conclude that the loop would never terminate, because @code{start} and
+@code{ticks} start out equal and the loop itself never changes them.
+It could then ``optimize'' the function into an infinite loop, which
+would definitely be undesirable.
+
+Optimization barriers can be used to avoid other compiler
+optimizations. The @func{busy_wait} function, also in
+@file{devices/timer.c}, is an example. It contains this loop:
@example
-timer_put_char = 'x'; /* INCORRECT CODE */
-timer_do_put = true;
+while (loops-- > 0)
+ barrier ();
@end example
-The reason this second example might be a problem is that the compiler
-is, in general, free to reorder operations when it doesn't have a
-visible reason to keep them in the same order. In this case, the
-compiler doesn't know that the order of assignments is important, so its
-optimization pass is permitted to exchange their order.
-There's no telling whether it will actually do this, and it is possible
-that passing the compiler different optimization flags or changing
-compiler versions will produce different behavior.
-
-The following is @emph{not} a solution, because locks neither prevent
-interrupts nor prevent the compiler from reordering the code within the
-region where the lock is held:
+@noindent
+The goal of this loop is to busy-wait by counting @code{loops} down
+from its original value to 0. Without the barrier, the compiler could
+delete the loop entirely, because it produces no useful output and has
+no side effects. The barrier forces the compiler to pretend that the
+loop body has an important effect.
+
+Finally, optimization barriers can be used to force the ordering of
+memory reads or writes. For example, suppose we add a ``feature''
+that, whenever a timer interrupt occurs, the character in global
+variable @code{timer_put_char} is printed on the console, but only if
+global Boolean variable @code{timer_do_put} is true. The best way to
+set up @samp{x} to be printed is then to use an optimization barrier,
+like this:
@example
-lock_acquire (&timer_lock); /* INCORRECT CODE */
timer_put_char = 'x';
+barrier ();
timer_do_put = true;
-lock_release (&timer_lock);
@end example
-Fortunately, real solutions do exist. One possibility is to
-disable interrupts around the assignments. This does not prevent
-reordering, but it makes the assignments atomic as observed by the
-interrupt handler. It also has the extra runtime cost of disabling and
-re-enabling interrupts:
+Without the barrier, the code is buggy because the compiler is free to
+reorder operations when it doesn't see a reason to keep them in the
+same order. In this case, the compiler doesn't know that the order of
+assignments is important, so its optimizer is permitted to exchange
+their order. There's no telling whether it will actually do this, and
+it is possible that passing the compiler different optimization flags
+or using a different version of the compiler will produce different
+behavior.
+
+Another solution is to disable interrupts around the assignments.
+This does not prevent reordering, but it prevents the interrupt
+handler from intervening between the assignments. It also has the
+extra runtime cost of disabling and re-enabling interrupts:
@example
enum intr_level old_level = intr_disable ();
intr_set_level (old_level);
@end example
-A second possibility is to mark the declarations of
+A second solution is to mark the declarations of
@code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
keyword tells the compiler that the variables are externally observable
and restricts its latitude for optimization. However, the semantics of
@samp{volatile} are not well-defined, so it is not a good general
-solution.
+solution. The base Pintos code does not use @samp{volatile} at all.
-Usually, the best solution is to use a compiler feature called a
-@dfn{memory barrier}, a special statement that prevents the compiler
-from reordering memory operations across the barrier. In Pintos,
-@file{threads/synch.h} defines the @code{barrier()} macro as a memory
-barrier. Here's how we would use a memory barrier to fix this code:
+The following is @emph{not} a solution, because locks neither prevent
+interrupts nor prevent the compiler from reordering the code within the
+region where the lock is held:
@example
+lock_acquire (&timer_lock); /* INCORRECT CODE */
timer_put_char = 'x';
-barrier ();
timer_do_put = true;
+lock_release (&timer_lock);
@end example
-The compiler also treats invocation of any function defined externally,
-that is, in another source file, as a limited form of a memory barrier.
-Specifically, the compiler assumes that any externally defined function
-may access any statically or dynamically allocated data and any local
-variable whose address is taken. This often means that explicit
-barriers can be omitted, and, indeed, this is why the base Pintos code
-does not need any barriers.
+The compiler treats invocation of any function defined externally,
+that is, in another source file, as a limited form of optimization
+barrier. Specifically, the compiler assumes that any externally
+defined function may access any statically or dynamically allocated
+data and any local variable whose address is taken. This often means
+that explicit barriers can be omitted. It is one reason that Pintos
+contains few explicit barriers.
A function defined in the same source file, or in a header included by
-the source file, cannot be relied upon as a memory barrier.
+the source file, cannot be relied upon as a optimization barrier.
This applies even to invocation of a function before its
definition, because the compiler may read and parse the entire source
file before performing optimization.
@node External Interrupt Handling
@subsection External Interrupt Handling
-Whereas an internal interrupt runs in the context of the thread that
-caused it, external interrupts do not have any predictable context.
+External interrupts are caused by events outside the CPU.
They are asynchronous, so they can be invoked at any time that
interrupts have not been disabled. We say that an external interrupt
runs in an ``interrupt context.''
one that is. It is possible, although rarely useful, to examine it, but
modifying it is a recipe for disaster.
-The activities of an external interrupt handler are severely
-restricted. First, only one external interrupt may be processed at a
-time, that is, nested external interrupt handling is not supported.
-This means that external interrupts must be processed with interrupts
-disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
-enabled at any point during their execution.
-
-Second, an interrupt handler must not call any function that can
-sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
-many others. This is because external interrupts use space on the
-stack of the kernel thread that was running at the time the interrupt
-occurred. If the interrupt handler slept, it would effectively put that
-thread to sleep too until the interrupt handler resumed control and
-returned.
-
-Because an external interrupt runs with interrupts disabled, it
+Only one external interrupt may be processed at a time. Neither
+internal nor external interrupt may nest within an external interrupt
+handler. Thus, an external interrupt's handler must run with interrupts
+disabled (@pxref{Disabling Interrupts}).
+
+An external interrupt handler must not sleep or yield, which rules out
+calling @func{lock_acquire}, @func{thread_yield}, and many other
+functions. Sleeping in interrupt context would effectively put the
+interrupted thread to sleep, too, until the interrupt handler was again
+scheduled and returned. This would be unfair to the unlucky thread, and
+it would deadlock if the handler were waiting for the sleeping thread
+to, e.g., release a lock.
+
+An external interrupt handler
effectively monopolizes the machine and delays all other activities.
Therefore, external interrupt handlers should complete as quickly as
-they can. Any activities that require much CPU time should instead
-run in a kernel thread, possibly a thread whose activity is triggered
-by the interrupt using some synchronization primitive.
+they can. Anything that require much CPU time should instead run in a
+kernel thread, possibly one that the interrupt triggers using a
+synchronization primitive.
-External interrupts are also special because they are controlled by a
+External interrupts are controlled by a
pair of devices outside the CPU called @dfn{programmable interrupt
controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
CPU's IDT, it also initializes the PICs for interrupt handling. The
PICs also must be ``acknowledged'' at the end of processing for each
external interrupt. @func{intr_handler} takes care of that by calling
-@func{pic_end_of_interrupt}, which sends the proper signals to the
-right PIC.
+@func{pic_end_of_interrupt}, which properly signals the PICs.
-The following additional functions are related to external
+The following functions relate to external
interrupts.
@deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
@deftypefun bool intr_context (void)
Returns true if we are running in an interrupt context, otherwise
-false. Mainly used at the beginning of functions that might sleep
+false. Mainly used in functions that might sleep
or that otherwise should not be called from interrupt context, in this
form:
@example
@deftypefun void intr_yield_on_return (void)
When called in an interrupt context, causes @func{thread_yield} to be
-called just before the interrupt returns. This is used, for example,
-in the timer interrupt handler to cause a new thread to be scheduled
-when a thread's time slice expires.
+called just before the interrupt returns. Used
+in the timer interrupt handler when a thread's time slice expires, to
+cause a new thread to be scheduled.
@end deftypefun
@node Memory Allocation
The page allocator divides the memory it allocates into two pools,
called the kernel and user pools. By default, each pool gets half of
-system memory, but this can be changed with a kernel command line
+system memory above @w{1 MB}, but the division can be changed with the
+@option{-ul} kernel
+command line
option (@pxref{Why PAL_USER?}). An allocation request draws from one
pool or the other. If one pool becomes empty, the other may still
have free pages. The user pool should be used for allocating memory
for @var{n} consecutive bits set to
false, indicating that those pages are free, and then sets those bits
to true to mark them as used. This is a ``first fit'' allocation
-strategy.
+strategy (@pxref{Wilson}).
The page allocator is subject to fragmentation. That is, it may not
be possible to allocate @var{n} contiguous pages even though @var{n}
or more pages are free, because the free pages are separated by used
pages. In fact, in pathological cases it may be impossible to
-allocate 2 contiguous pages even though @var{n} / 2 pages are free!
+allocate 2 contiguous pages even though half of the pool's pages are free.
Single-page requests can't fail due to fragmentation, so
-it is best to limit, as much as possible, the need for multiple
-contiguous pages.
+requests for multiple contiguous pages should be limited as much as
+possible.
Pages may not be allocated from interrupt context, but they may be
freed.
Page allocator types and functions are described below.
-@deftp {Type} {enum palloc_flags}
-A set of flags that describe how to allocate pages. These flags may
-be combined in any combination.
-@end deftp
+@deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
+@deftypefunx {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
+Obtains and returns one page, or @var{page_cnt} contiguous pages,
+respectively. Returns a null pointer if the pages cannot be allocated.
+
+The @var{flags} argument may be any combination of the following flags:
@defvr {Page Allocator Flag} @code{PAL_ASSERT}
If the pages cannot be allocated, panic the kernel. This is only
Obtain the pages from the user pool. If not set, pages are allocated
from the kernel pool.
@end defvr
-
-@deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
-Obtains and returns a single page, allocating it in the manner specified by
-@var{flags}. Returns a null pointer if no pages are
-free.
-@end deftypefun
-
-@deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
-Obtains @var{page_cnt} contiguous free pages, allocating them in the
-manner specified by @var{flags}, and returns them. Returns a null
-pointer if no pages are free.
@end deftypefun
@deftypefun void palloc_free_page (void *@var{page})
-Frees @var{page}, which must have been obtained using
+@deftypefunx void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
+Frees one page, or @var{page_cnt} contiguous pages, respectively,
+starting at @var{pages}. All of the pages must have been obtained using
@func{palloc_get_page} or @func{palloc_get_multiple}.
@end deftypefun
-@deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
-Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
-All of the pages must have been obtained using @func{palloc_get_page}
-or @func{palloc_get_multiple}.
-@end deftypefun
-
@node Block Allocator
@subsection Block Allocator
described in the previous section. Blocks returned by the block
allocator are obtained from the kernel pool.
-The block allocator uses two different strategies for allocating
-memory. The first of these applies to ``small'' blocks, those 1 kB or
-smaller (one
-fourth of the page size). These allocations are rounded up to the
+The block allocator uses two different strategies for allocating memory.
+The first strategy applies to blocks that are 1 kB or smaller
+(one-fourth of the page size). These allocations are rounded up to the
nearest power of 2, or 16 bytes, whichever is larger. Then they are
-grouped into a page used only for allocations of the smae
-size.
+grouped into a page used only for allocations of that size.
-The second strategy applies to allocating ``large'' blocks, those larger
-than 1 kB.
+The second strategy applies to blocks larger than 1 kB.
These allocations (plus a small amount of overhead) are rounded up to
the nearest page in size, and then the block allocator requests that
number of contiguous pages from the page allocator.
unimportant in an instructional system like Pintos.
As long as a page can be obtained from the page allocator, small
-allocations always succeed. Most small allocations will not require a
-new page from the page allocator at all. However, large allocations
+allocations always succeed. Most small allocations do not require a
+new page from the page allocator at all, because they are satisfied
+using part of a page already allocated. However, large allocations
always require calling into the page allocator, and any allocation
that needs more than one contiguous page can fail due to fragmentation,
as already discussed in the previous section. Thus, you should
minimize the number of large allocations in your code, especially
those over approximately 4 kB each.
-The interface to the block allocator is through the standard C library
-functions @func{malloc}, @func{calloc}, and @func{free}.
-
When a block is freed, all of its bytes are cleared to @t{0xcc}, as
a debugging aid (@pxref{Debugging Tips}).
The block allocator may not be called from interrupt context.
+The block allocator functions are described below. Their interfaces are
+the same as the standard C library functions of the same names.
+
+@deftypefun {void *} malloc (size_t @var{size})
+Obtains and returns a new block, from the kernel pool, at least
+@var{size} bytes long. Returns a null pointer if @var{size} is zero or
+if memory is not available.
+@end deftypefun
+
+@deftypefun {void *} calloc (size_t @var{a}, size_t @var{b})
+Obtains a returns a new block, from the kernel pool, at least
+@code{@var{a} * @var{b}} bytes long. The block's contents will be
+cleared to zeros. Returns a null pointer if @var{a} or @var{b} is zero
+or if insufficient memory is available.
+@end deftypefun
+
+@deftypefun {void *} realloc (void *@var{block}, size_t @var{new_size})
+Attempts to resize @var{block} to @var{new_size} bytes, possibly moving
+it in the process. If successful, returns the new block, in which case
+the old block must no longer be accessed. On failure, returns a null
+pointer, and the old block remains valid.
+
+A call with @var{block} null is equivalent to @func{malloc}. A call
+with @var{new_size} zero is equivalent to @func{free}.
+@end deftypefun
+
+@deftypefun void free (void *@var{block})
+Frees @var{block}, which must have been previously returned by
+@func{malloc}, @func{calloc}, or @func{realloc} (and not yet freed).
+@end deftypefun
+
@node Virtual Addresses
@section Virtual Addresses
@defmac PGSHIFT
@defmacx PGBITS
-The bit index (0) and number of bits (12) in the offset part of a
+The bit index (0) and number of bits (12) of the offset part of a
virtual address, respectively.
@end defmac
@defmac PGMASK
-A bit mask with value @t{0xfff}, so that the bits in the page offset are
-set to 1 and other bits set to 0.
+A bit mask with the bits in the page offset set to 1, the rest set to 0
+(@t{0xfff}).
@end defmac
@defmac PGSIZE
-The page size in bytes (4096).
+The page size in bytes (4,096).
@end defmac
@deftypefun unsigned pg_ofs (const void *@var{va})
@end deftypefun
Virtual memory in Pintos is divided into two regions: user virtual
-memory and kernel virtual memory. The boundary between them is
-@code{PHYS_BASE}:
+memory and kernel virtual memory (@pxref{Virtual Memory Layout}). The
+boundary between them is @code{PHYS_BASE}:
@defmac PHYS_BASE
Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
page tables (that is, those for running and suspended processes),
flushing the TLB as necessary.
-User page parameters (@var{upage})to these functions should be user
-virtual addresses. Kernel page parameters (@var{kpage}) should be
-kernel virtual addresses and should have been obtained from the user
-pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why PAL_USER?}).
-
@deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
-Adds to @var{pd} a mapping from page @var{upage} to the frame identified
+Adds to @var{pd} a mapping from user page @var{upage} to the frame identified
by kernel virtual address @var{kpage}. If @var{writable} is true, the
page is mapped read/write; otherwise, it is mapped read-only.
-Page @var{upage} must not already be mapped. If it is, the kernel
-panics.
+User page @var{upage} must not already be mapped in @var{pd}.
+
+Kernel page @var{kpage} should be a kernel virtual address obtained from
+the user pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why
+PAL_USER?}).
Returns true if successful, false on failure. Failure will occur if
additional memory required for the page table cannot be obtained.
@end deftypefun
@deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
-Looks up the frame mapped to @var{upage} in @var{pd}. Returns the
-kernel virtual address for that frame, if @var{upage} is mapped, or a
+Looks up the frame mapped to @var{uaddr} in @var{pd}. Returns the
+kernel virtual address for that frame, if @var{uaddr} is mapped, or a
null pointer if it is not.
@end deftypefun
-@deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{upage})
-Marks page @var{upage} ``not present'' in @var{pd}. Later accesses to
+@deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{page})
+Marks @var{page} ``not present'' in @var{pd}. Later accesses to
the page will fault.
-Other bits in the page table for @var{upage} are preserved, permitting
+Other bits in the page table for @var{page} are preserved, permitting
the accessed and dirty bits (see the next section) to be checked.
-If @var{upage} is not mapped, this function has no effect.
+This function has no effect if @var{page} is not mapped.
@end deftypefun
@node Page Table Accessed and Dirty Bits
@defmac PTSHIFT
@defmacx PTBITS
-The bit index (12) and number of bits (10), respectively, in a page table
-index within a virtual address.
+The starting bit index (12) and number of bits (10), respectively, in a
+page table index.
@end defmac
@defmac PTMASK
-A bit mask with the bits in the page table index set to 1 and other bits
-set to 0.
+A bit mask with the bits in the page table index set to 1 and the rest
+set to 0 (@t{0x3ff000}).
@end defmac
@defmac PTSPAN
@defmac PDSHIFT
@defmacx PDBITS
-The bit index (22) and number of bits (10), respectively, in a page
-directory index within a virtual address.
+The starting bit index (22) and number of bits (10), respectively, in a
+page directory index.
@end defmac
@defmac PDMASK
A bit mask with the bits in the page directory index set to 1 and other
-bits set to 0.
+bits set to 0 (@t{0xffc00000}).
@end defmac
@deftypefun uintptr_t pd_no (const void *@var{va})
@deftypefun {void *} pte_get_page (uint32_t @var{pte})
Returns the kernel virtual address for the frame that @var{pte} points
to. The @var{pte} may be present or not-present; if it is not-present
-then the pointer return is only meaningful if the proper bits in the PTE
+then the pointer returned is only meaningful if the address bits in the PTE
actually represent a physical address.
@end deftypefun
@deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
Returns the kernel virtual address for the page table page that
-@var{pde} points to. The @var{pde} must be marked present.
+@var{pde}, which must be marked present, points to.
@end deftypefun
@node Hash Table
@section Hash Table
Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
-To use it you will need to manually include its header file,
-@file{lib/kernel/hash.h}, with @code{#include <hash.h>}. Intentionally,
-no code provided with Pintos uses the hash table, which means that you
+To use it you will need to include its header file,
+@file{lib/kernel/hash.h}, with @code{#include <hash.h>}.
+No code provided with Pintos uses the hash table, which means that you
are free to use it as is, modify its implementation for your own
purposes, or ignore it, as you wish.
real element type.
@end deftp
-You will often need to obtain a @struct{hash_elem}
-given a real element of the hash table, and vice versa. Given
-a real element of the hash table, obtaining a pointer to its
-@struct{hash_elem} is trivial: take the address of the
-@struct{hash_elem} member. Use the @code{hash_entry()} macro to go the
-other direction.
+You will often need to obtain a @struct{hash_elem} given a real element
+of the hash table, and vice versa. Given a real element of the hash
+table, you may use the @samp{&} operator to obtain a pointer to its
+@struct{hash_elem}. Use the @code{hash_entry()} macro to go the other
+direction.
@deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
Returns a pointer to the structure that @var{elem}, a pointer to a
For example, suppose @code{h} is a @code{struct hash_elem *} variable
that points to a @struct{thread} member (of type @struct{hash_elem})
-named @code{h_elem}. Then, @code{hash_entry (h, struct thread, h_elem)}
+named @code{h_elem}. Then, @code{hash_entry@tie{}(h, struct thread, h_elem)}
yields the address of the @struct{thread} that @code{h} points within.
@end deftypefn
+@xref{Hash Table Example}, for an example.
+
Each hash table element must contain a key, that is, data that
-identifies and distinguishes elements in the hash table. Every element
-in a hash table at a given time must have a unique key. (Elements may
+identifies and distinguishes elements, which must be unique
+among elements in the hash table. (Elements may
also contain non-key data that need not be unique.) While an element is
-in a hash table, its key data must not be changed. For each hash table,
-you must write two functions that act on keys: a hash function and a
-comparison function. These functions must match the following
-prototypes:
+in a hash table, its key data must not be changed. Instead, if need be,
+remove the element from the hash table, modify its key, then reinsert
+the element.
+
+For each hash table, you must write two functions that act on keys: a
+hash function and a comparison function. These functions must match the
+following prototypes:
@deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
Returns a hash of @var{element}'s data, as a value anywhere in the range
@xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
@end deftp
-A few functions that act on hashes accept a pointer to a third kind of
+@xref{Hash Table Example}, for hash and comparison function examples.
+
+A few functions accept a pointer to a third kind of
function as an argument:
@deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
@node Basic Hash Functions
@subsection Basic Functions
-These functions create and destroy hash tables and obtain basic
-information about their contents.
+These functions create, destroy, and inspect hash tables.
@deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
-Initializes @var{hash} as a hash table using @var{hash_func} as hash
+Initializes @var{hash} as a hash table with @var{hash_func} as hash
function, @var{less_func} as comparison function, and @var{aux} as
auxiliary data.
Returns true if successful, false on failure. @func{hash_init} calls
@deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
Searches @var{hash} for an element equal to @var{element}. If none is
found, inserts @var{element} into @var{hash} and returns a null pointer.
-If the table already contains an element equal to @var{element}, returns
-the existing element without modifying @var{hash}.
+If the table already contains an element equal to @var{element}, it is
+returned without modifying @var{hash}.
@end deftypefun
@deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
equal to @var{element}.
The caller is responsible for deallocating any resources associated with
-the element returned, as appropriate. For example, if the hash table
+the returned element, as appropriate. For example, if the hash table
elements are dynamically allocated using @func{malloc}, then the caller
must @func{free} the element after it is no longer needed.
@end deftypefun
The element passed to the following functions is only used for hashing
and comparison purposes. It is never actually inserted into the hash
-table. Thus, only the key data in the element need be initialized, and
+table. Thus, only key data in the element needs to be initialized, and
other data in the element will not be used. It often makes sense to
declare an instance of the element type as a local variable, initialize
the key data, and then pass the address of its @struct{hash_elem} to
pointer is returned and @var{hash} is unchanged.
The caller is responsible for deallocating any resources associated with
-the element returned, as appropriate. For example, if the hash table
+the returned element, as appropriate. For example, if the hash table
elements are dynamically allocated using @func{malloc}, then the caller
must @func{free} the element after it is no longer needed.
@end deftypefun
scope:
@example
-/* @r{Returns the page containing the given virtual @var{address},
- or a null pointer if no such page exists.} */
+/* @r{Returns the page containing the given virtual @var{address},}
+ @r{or a null pointer if no such page exists.} */
struct page *
page_lookup (const void *address)
@{
it.)
@var{aux} is useful when you have some property of the data in the
-hash table that's both constant and needed for hashing or comparisons,
-but which is not stored in the data items themselves. For example, if
-the items in a hash table contain fixed-length strings, but the items
+hash table is both constant and needed for hashing or comparison,
+but not stored in the data items themselves. For example, if
+the items in a hash table are fixed-length strings, but the items
themselves don't indicate what that fixed length is, you could pass
the length as an @var{aux} parameter.
projects / pintos-anon / blobdiff