| [ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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 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 (see section F.1 Tags).
This section covers the Pintos loader and basic kernel initialization.
The first part of Pintos that runs is the loader, in
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
you're interested, read on. You should probably read along with the
loader's source. You should also understand the basics of the
80x86 architecture as described by chapter 3, "Basic Execution
Environment," of [ 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 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
LOADER_PHYS_BASE, which defaults to 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 0x7c00, the location where the BIOS
loaded us, and we can't jump to 0xc0007c00 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
KERNEL_LOAD_PAGES pages of data (4 kB per page) from the disk directly
into virtual memory, starting LOADER_KERN_BASE bytes past
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 threads/kernel.lds.S
, the kernel has
arranged to begin with the assembly module
threads/start.S
. This assembly module just calls
main(), which never returns.
There's one more trick: the Pintos kernel command line
is in stored the boot loader. The 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.
The kernel proper starts with the main() function. The
main() function is written in C, as will be most of the code we
encounter in Pintos from here on out.
When main() starts, the system is in a pretty raw state. We're
in 32-bit protected mode with paging enabled, but hardly anything else is
ready. Thus, the main() function consists primarily of calls
into other Pintos modules' initialization functions.
These are usually named module_init(), where
module is the module's name, module.c
is the
module's source code, and module.h
is the module's
header.
First we initialize kernel RAM in ram_init(). The first step
is to clear out the kernel's so-called "BSS" segment. The BSS is 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 memset() to zero it out. The other task of
ram_init() is to read out the machine's memory size from where
the loader stored it and put it into the ram_pages variable for
later use.
Next, 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 printf() will work.
main() calls vga_init(), which initializes the VGA text
display and clears the screen. It also calls 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.
main() calls read_command_line() to break the kernel command
line into arguments, then parse_options() to read any options at
the beginning of the command line. (Actions specified on the
command line execute later.)
main() calls random_init() to initialize the kernel random
number generator. If the user specified -rs
on the
pintos command line, parse_options() already did
this, but calling it a second time is harmless.
The next block of functions we call initialize the kernel's memory
system. palloc_init() sets up the kernel page allocator, which
doles out memory one or more pages at a time (see section A.5.1 Page Allocator).
malloc_init() sets
up the allocator that handles allocations of arbitrary-size blocks of
memory (see section A.5.2 Block Allocator).
paging_init() sets up a page table for the kernel (see section A.7 Page Table).
In projects 2 and later, main() also calls tss_init() and
gdt_init().
The next set of calls initializes the interrupt system.
intr_init() sets up the CPU's interrupt descriptor table
(IDT) to ready it for interrupt handling (see section A.4.1 Interrupt Infrastructure), then timer_init() and kbd_init() prepare for
handling timer interrupts and keyboard interrupts, respectively.
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 exception_init() and syscall_init().
Now that interrupts are set up, we can start the scheduler
with thread_start(), which creates the idle thread and enables
interrupts.
With interrupts enabled, interrupt-driven serial port I/O becomes
possible, so we use
serial_init_queue() to switch to that mode. Finally,
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 disk_init(), then the
file system with filesys_init().
Boot is complete, so we print a message.
Function run_actions() now parses and executes actions specified on
the kernel command line, such as run to run a test (in project
1) or a user program (in later projects).
Finally, if -q
was specified on the kernel command line, we
call power_off() to terminate the machine simulator. Otherwise,
main() calls thread_exit(), which allows any other running
threads to continue running.
struct thread
The main Pintos data structure for threads is struct thread,
declared in threads/thread.h
.
struct thread. You may also change or
delete the definitions of existing members.
Every struct thread occupies the beginning of its own page of
memory. The rest of the page is used for the thread's stack, which
grows downward from the end of the page. It looks like this:
4 kB +---------------------------------+
| kernel stack |
| | |
| | |
| V |
| grows downward |
| |
| |
| |
| |
| |
| |
| |
| |
sizeof (struct thread) +---------------------------------+
| magic |
| : |
| : |
| status |
| tid |
0 kB +---------------------------------+
|
This has two consequences. First, struct thread must not be allowed
to grow too big. If it does, then there will not be enough room for the
kernel stack. The base struct thread is only a few bytes in size. It
probably should stay well under 1 kB.
Second, kernel stacks must not be allowed to grow too large. If a stack
overflows, it will corrupt the thread state. Thus, kernel functions
should not allocate large structures or arrays as non-static local
variables. Use dynamic allocation with malloc() or
palloc_get_page() instead (see section A.5 Memory Allocation).
struct thread: tid_t tid
tid_t is a typedef for int and each new
thread receives the numerically next higher tid, starting from 1 for
the initial process. You can change the type and the numbering scheme
if you like.
struct thread: enum thread_status status
THREAD_RUNNING
thread_current() returns the running thread.
THREAD_READY
ready_list.
THREAD_BLOCKED
THREAD_READY state with a
call to thread_unblock(). This is most conveniently done
indirectly, using one of the Pintos synchronization primitives that
block and unblock threads automatically (see section A.3 Synchronization).
There is no a priori way to tell what a blocked thread is waiting for, but a backtrace can help (see section E.4 Backtraces).
THREAD_DYING
struct thread: char name[16]
struct thread: uint8_t *stack
When an interrupt occurs, whether in the kernel or a user program, an
struct intr_frame is pushed onto the stack. When the interrupt occurs
in a user program, the struct intr_frame is always at the very top of
the page. See section A.4 Interrupt Handling, for more information.
struct thread: int priority
PRI_MIN (0) to PRI_MAX
(63). Lower numbers correspond to lower priorities, so that
priority 0 is the lowest priority and priority 63 is the highest.
Pintos as provided ignores thread priorities, but you will implement
priority scheduling in project 1 (see section 2.2.3 Priority Scheduling).
struct thread: struct list_elem elem
ready_list (the list of threads ready to run) or a list of
threads waiting on a semaphore in sema_down(). It can do double
duty because a thread waiting on a semaphore is not ready, and vice
versa.
struct thread: uint32_t *pagedir
struct thread: unsigned magic
THREAD_MAGIC, which is just an arbitrary number defined
in threads/thread.c, and used to detect stack overflow.
thread_current() checks that the magic member of the running
thread's struct thread is set to THREAD_MAGIC. Stack overflow
tends to change this value, triggering the assertion. For greatest
benefit, as you add members to struct thread, leave magic at
the end.
threads/thread.c
implements several public functions for thread
support. Let's take a look at the most useful:
main() to initialize the thread system. Its main
purpose is to create a struct thread for Pintos's initial thread.
This is possible because the Pintos loader puts the initial
thread's stack at the top of a page, in the same position as any other
Pintos thread.
Before thread_init() runs,
thread_current() will fail because the running thread's
magic value is incorrect. Lots of functions call
thread_current() directly or indirectly, including
lock_acquire() for locking a lock, so thread_init() is
called early in Pintos initialization.
main() to start the scheduler. Creates the idle
thread, that is, the thread that is scheduled when no other thread is
ready. Then enables interrupts, which as a side effect enables the
scheduler because the scheduler runs on return from the timer interrupt, using
intr_yield_on_return() (see section A.4.3 External Interrupt Handling).
thread_create() allocates a page for the thread's
struct thread and stack and initializes its members, then it sets
up a set of fake stack frames for it (see section A.2.3 Thread Switching). The
thread is initialized in the blocked state, then unblocked just before
returning, which allows the new thread to
be scheduled (see Thread States).
thread_create(), whose
aux argument is passed along as the function's argument.
thread_unblock() is
called on it, so you'd better have some way arranged for that to happen.
Because thread_block() is so low-level, you should prefer to use
one of the synchronization primitives instead (see section A.3 Synchronization).
thread_current ()->tid.
thread_current
()->name.
NO_RETURN
NO_RETURN (see section E.3 Function and Parameter Attributes).
schedule() is responsible for switching threads. It
is internal to threads/thread.c
and called only by the three
public thread functions that need to switch threads:
thread_block(), thread_exit(), and thread_yield().
Before any of these functions call schedule(), they disable
interrupts (or ensure that they are already disabled) and then change
the running thread's state to something other than running.
schedule() is short but tricky. It records the
current thread in local variable cur, determines the next thread
to run as local variable next (by calling
next_thread_to_run()), and then calls switch_threads() to do
the actual thread switch. The thread we switched to was also running
inside switch_threads(), as are all the threads not currently
running, so the new thread now returns out of
switch_threads(), returning the previously running thread.
switch_threads() is an assembly language routine in
threads/switch.S
. It saves registers on the stack, saves the
CPU's current stack pointer in the current struct thread's stack
member, restores the new thread's stack into the CPU's stack
pointer, restores registers from the stack, and returns.
The rest of the scheduler is implemented in 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
prior to the thread switch because the switch needed to use it.
Running a thread for the first time is a special case. When
thread_create() creates a new thread, it goes through a fair
amount of trouble to get it started properly. In particular, the new
thread hasn't started running yet, so there's no way for it to be
running inside switch_threads() as the scheduler expects. To
solve the problem, thread_create() creates some fake stack frames
in the new thread's stack:
switch_threads(), represented
by struct switch_threads_frame. The important part of this frame is
its eip member, the return address. We point eip to
switch_entry(), indicating it to be the function that called
switch_entry().
switch_entry(), an assembly
language routine in threads/switch.Sthat adjusts the stack pointer,(4) calls
schedule_tail() (this special case is why
schedule_tail() is separate from schedule()), and returns.
We fill in its stack frame so that it returns into
kernel_thread(), a function in threads/thread.c.
kernel_thread(), which enables
interrupts and calls the thread's function (the function passed to
thread_create()). If the thread's function returns, it calls
thread_exit() to terminate the thread.
If sharing of resources between threads is not handled in a careful, controlled fashion, the result is usually a big mess. This is especially the case in operating system kernels, where faulty sharing can crash the entire machine. Pintos provides several synchronization primitives to help out.
The crudest way to do synchronization is to disable interrupts, that is, to temporarily prevent the CPU from responding to interrupts. If interrupts are off, no other thread will preempt the running thread, because thread preemption is driven by the timer interrupt. If interrupts are on, as they normally are, then the running thread may be preempted by another at any time, whether between two C statements or even within the execution of one.
Incidentally, this means that Pintos is a "preemptible kernel," that is, kernel threads can be preempted at any time. Traditional Unix systems are "nonpreemptible," that is, kernel threads can only be preempted at points where they explicitly call into the scheduler. (User programs can be preempted at any time in both models.) As you might imagine, preemptible kernels require more explicit synchronization.
You should have little need to set the interrupt state directly. Most of the time you should use the other synchronization primitives described in the following sections. The main reason to disable interrupts is to synchronize kernel threads with external interrupt handlers, which cannot sleep and thus cannot use most other forms of synchronization (see section A.4.3 External Interrupt Handling).
Some external interrupts cannot be postponed, even by disabling interrupts. These interrupts, called non-maskable interrupts (NMIs), are supposed to be used only in emergencies, e.g. when the computer is on fire. Pintos does not handle non-maskable interrupts.
Types and functions for disabling and enabling interrupts are in
threads/interrupt.h
.
INTR_OFF or INTR_ON, denoting that interrupts are
disabled or enabled, respectively.
A semaphore is a nonnegative integer together with two operators that manipulate it atomically, which are:
A semaphore initialized to 0 may be used to wait for an event that will happen exactly once. For example, suppose thread A starts another thread B and wants to wait for B to signal that some activity is complete. A can create a semaphore initialized to 0, pass it to B as it starts it, and then "down" the semaphore. When B finishes its activity, it "ups" the semaphore. This works regardless of whether A "downs" the semaphore or B "ups" it first.
A semaphore initialized to 1 is typically used for controlling access to a resource. Before a block of code starts using the resource, it "downs" the semaphore, then after it is done with the resource it "ups" the resource. In such a case a lock, described below, may be more appropriate.
Semaphores can also be initialized to values larger than 1. These are rarely used.
Semaphores were invented by Edsger Dijkstra and first used in the THE operating system ([ Dijkstra]).
Pintos' semaphore type and operations are declared in
threads/synch.h
.
sema_down() or find a
different approach instead.
Unlike most synchronization primitives, sema_up() may be called
inside an external interrupt handler (see section A.4.3 External Interrupt Handling).
Semaphores are internally built out of disabling interrupt
(see section A.3.1 Disabling Interrupts) and thread blocking and unblocking
(thread_block() and thread_unblock()). Each semaphore maintains
a list of waiting threads, using the linked list
implementation in lib/kernel/list.c
.
A lock is like a semaphore with an initial value of 1 (see section A.3.2 Semaphores). A lock's equivalent of "up" is called "acquire", and the "down" operation is called "release".
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 release it. If this restriction is a problem, it's a good sign that a semaphore should be used, instead of a lock.
Locks in Pintos are not "recursive," that is, it is an error for the thread currently holding a lock to try to acquire that lock.
Lock types and functions are declared in threads/synch.h
.
lock_acquire() instead.
A monitor is a higher-level form of synchronization than a semaphore or a lock. A monitor consists of data being synchronized, plus a lock, called the monitor lock, and one or more condition variables. Before it accesses the protected data, a thread first acquires the monitor lock. It is then said to be "in the monitor". While in the monitor, the thread has control over all the protected data, which it may freely examine or modify. When access to the protected data is complete, it releases the monitor lock.
Condition variables allow code in the monitor to wait for a condition to become true. Each condition variable is associated with an abstract condition, e.g. "some data has arrived for processing" or "over 10 seconds has passed since the user's last keystroke". When code in the monitor needs to wait for a condition to become true, it "waits" on the associated condition variable, which releases the lock and waits for the condition to be signaled. If, on the other hand, it has caused one of these conditions to become true, it "signals" the condition to wake up one waiter, or "broadcasts" the condition to wake all of them.
The theoretical framework for monitors was laid out by C. A. R. Hoare ([ Hoare]). Their practical usage was later elaborated in a paper on the Mesa operating system ([ Lampson]).
Condition variable types and functions are declared in
threads/synch.h
.
Sending a signal and waking up from a wait are not an atomic operation.
Thus, typically cond_wait()'s caller must recheck the condition
after the wait completes and, if necessary, wait again. See the next
section for an example.
The classical example of a monitor is handling a buffer into which one or more "producer" threads write characters and out of which one or more "consumer" threads read characters. To implement this we need, besides the monitor lock, two condition variables which we will call not_full and not_empty:
char buf[BUF_SIZE]; /* Buffer. */
size_t n = 0; /* 0 <= n <= BUF_SIZE: # of characters in buffer. */
size_t head = 0; /* buf index of next char to write (mod BUF_SIZE). */
size_t tail = 0; /* buf index of next char to read (mod BUF_SIZE). */
struct lock lock; /* Monitor lock. */
struct condition not_empty; /* Signaled when the buffer is not empty. */
struct condition not_full; /* Signaled when the buffer is not full. */
...initialize the locks and condition variables...
void put (char ch) {
lock_acquire (&lock);
while (n == BUF_SIZE) /* Can't add to buf as long as it's full. */
cond_wait (¬_full, &lock);
buf[head++ % BUF_SIZE] = ch; /* Add ch to buf. */
n++;
cond_signal (¬_empty, &lock); /* buf can't be empty anymore. */
lock_release (&lock);
}
char get (void) {
char ch;
lock_acquire (&lock);
while (n == 0) /* Can't read buf as long as it's empty. */
cond_wait (¬_empty, &lock);
ch = buf[tail++ % BUF_SIZE]; /* Get ch from buf. */
n--;
cond_signal (¬_full, &lock); /* buf can't be full anymore. */
lock_release (&lock);
}
|
Suppose we add a "feature" that, whenever a timer interrupt
occurs, the character in global variable timer_put_char is
printed on the console, but only if global Boolean variable
timer_do_put is true.
If interrupts are enabled, this code for setting up x
to be
printed is clearly incorrect, because the timer interrupt could intervene
between the two assignments:
timer_do_put = true; /* INCORRECT CODE */ timer_put_char = 'x'; |
It might not be as obvious that the following code is just as incorrect:
timer_put_char = 'x'; /* INCORRECT CODE */ timer_do_put = true; |
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 not a solution, because locks neither prevent interrupts nor prevent the compiler from reordering the code within the region where the lock is held:
lock_acquire (&timer_lock); /* INCORRECT CODE */ timer_put_char = 'x'; timer_do_put = true; lock_release (&timer_lock); |
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:
enum intr_level old_level = intr_disable (); timer_put_char = 'x'; timer_do_put = true; intr_set_level (old_level); |
A second possibility is to mark the declarations of
timer_put_char and timer_do_put as volatile
. This
keyword tells the compiler that the variables are externally observable
and restricts its latitude for optimization. However, the semantics of
volatile
are not well-defined, so it is not a good general
solution.
Usually, the best solution is to use a compiler feature called a
memory barrier, a special statement that prevents the compiler
from reordering memory operations across the barrier. In Pintos,
threads/synch.h
defines the barrier() macro as a memory
barrier. Here's how we would use a memory barrier to fix this code:
timer_put_char = 'x'; barrier (); timer_do_put = true; |
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.
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. 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.
An interrupt notifies the CPU of some event. Much of the work of an operating system relates to interrupts in one way or another. For our purposes, we classify interrupts into two broad categories:
intr_disable() does not disable internal
interrupts.
intr_disable() and related functions
(see section A.3.1 Disabling Interrupts).
The CPU treats both classes of interrupts largely the same way, so Pintos has common infrastructure to handle both classes. The following section describes this common infrastructure. The sections after that give the specifics of external and internal interrupts.
If you haven't already read chapter 3, "Basic Execution Environment," in [ IA32-v1], it is recommended that you do so now. You might also want to skim chapter 5, "Interrupt and Exception Handling," in [ IA32-v3a].
When an interrupt occurs, the CPU saves its most essential state on a stack and jumps to an interrupt handler routine. The 80x86 architecture supports 256 interrupts, numbered 0 through 255, each with an independent handler defined in an array called the interrupt descriptor table or IDT.
In Pintos, intr_init() in threads/interrupt.c
sets up the
IDT so that each entry points to a unique entry point in
threads/intr-stubs.S
named intrNN_stub(), where
NN is the interrupt number in
hexadecimal. Because the CPU doesn't give
us any other way to find out the interrupt number, this entry point
pushes the interrupt number on the stack. Then it jumps to
intr_entry(), which pushes all the registers that the processor
didn't already push for us, and then calls intr_handler(), which
brings us back into C in threads/interrupt.c
.
The main job of intr_handler() is to call the function
registered for handling the particular interrupt. (If no
function is registered, it dumps some information to the console and
panics.) It also does some extra processing for external
interrupts (see section A.4.3 External Interrupt Handling).
When intr_handler() returns, the assembly code in
threads/intr-stubs.S
restores all the CPU registers saved
earlier and directs the CPU to return from the interrupt.
The following types and functions are common to all interrupts.
intr_entry(). Its most interesting members are described
below.
struct intr_frame: uint32_t edi
struct intr_frame: uint32_t esi
struct intr_frame: uint32_t ebp
struct intr_frame: uint32_t esp_dummy
struct intr_frame: uint32_t ebx
struct intr_frame: uint32_t edx
struct intr_frame: uint32_t ecx
struct intr_frame: uint32_t eax
struct intr_frame: uint16_t es
struct intr_frame: uint16_t ds
intr_entry().
The esp_dummy value isn't actually used (refer to the
description of PUSHA in [ IA32-v2b] for details).
struct intr_frame: uint32_t vec_no
struct intr_frame: uint32_t error_code
struct intr_frame: void (*eip) (void)
struct intr_frame: void *esp
"unknown" if the interrupt has no registered name.
Internal interrupts are caused directly by CPU instructions executed by the running kernel thread or user process (from project 2 onward). An internal interrupt is therefore said to arise in a "process context."
In an internal interrupt's handler, it can make sense to examine the
struct intr_frame passed to the interrupt handler, or even to modify
it. When the interrupt returns, modifications in struct intr_frame
become changes to the calling thread or process's state. For example,
the Pintos system call handler returns a value to the user program by
modifying the saved EAX register (see section 3.5.2 System Call Details).
There are no special restrictions on what an internal interrupt handler can or can't do. Generally they should run with interrupts enabled, just like other code, and so they can be preempted by other kernel threads. Thus, they do need to synchronize with other threads on shared data and other resources (see section A.3 Synchronization).
Internal interrupt handlers can be invoked recursively. For example,
the system call handler might cause a page fault while attempting to
read user memory. Deep recursion would risk overflowing the limited
kernel stack (see section A.2.1 struct thread), but should be unnecessary.
If level is INTR_ON, external interrupts will be processed
normally during the interrupt handler's execution, which is normally
desirable. Specifying INTR_OFF will cause the CPU to disable
external interrupts when it invokes the interrupt handler. The effect
is slightly different from calling intr_disable() inside the
handler, because that leaves a window of one or more CPU instructions in
which external interrupts are still enabled. This is important for the
page fault handler; refer to the comments in userprog/exception.c
for details.
dpl determines how the interrupt can be invoked. If dpl is 0, then the interrupt can be invoked only by kernel threads. Otherwise dpl should be 3, which allows user processes to invoke the interrupt with an explicit INT instruction. The value of dpl doesn't affect user processes' ability to invoke the interrupt indirectly, e.g. an invalid memory reference will cause a page fault regardless of dpl.
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."
In an external interrupt, the struct intr_frame passed to the
handler is not very meaningful. It describes the state of the thread
or process that was interrupted, but there is no way to predict which
one that is. It is possible, although rarely useful, to examine it, but
modifying it is a recipe for disaster.
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 (see section A.3.1 Disabling Interrupts).
An external interrupt handler must not sleep or yield, which rules out
calling lock_acquire(), 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. 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 controlled by a
pair of devices outside the CPU called programmable interrupt
controllers, PICs for short. When 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. intr_handler() takes care of that by calling
pic_end_of_interrupt(), which properly signals the PICs.
The following functions relate to external interrupts.
ASSERT (!intr_context ()); |
thread_yield() to be
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.
Pintos contains two memory allocators, one that allocates memory in units of a page, and one that can allocate blocks of any size.
The page allocator declared in threads/palloc.h
allocates
memory in units of a page. It is most often used to allocate memory
one page at a time, but it can also allocate multiple contiguous pages
at once.
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 the -ul
kernel
command line
option (see 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 user processes and the kernel pool for all other allocations.
This will only become important starting with project 3. Until then,
all allocations should be made from the kernel pool.
Each pool's usage is tracked with a bitmap, one bit per page in the pool. A request to allocate n pages scans the bitmap for 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 (see Wilson).
The page allocator is subject to fragmentation. That is, it may not be possible to allocate n contiguous pages even though 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 half of the pool's pages are free. Single-page requests can't fail due to fragmentation, so 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.
When a page is freed, all of its bytes are cleared to 0xcc, as a debugging aid (see section E.8 Tips).
Page allocator types and functions are described below.
The flags argument may be any combination of the following flags:
PAL_ASSERT
PAL_ZERO
PAL_USER
palloc_get_page() or palloc_get_multiple().
The block allocator, declared in threads/malloc.h
, can allocate
blocks of any size. It is layered on top of the page 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 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 that size.
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.
In either case, the difference between the allocation requested size and the actual block size is wasted. A real operating system would carefully tune its allocator to minimize this waste, but this is 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 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.
When a block is freed, all of its bytes are cleared to 0xcc, as a debugging aid (see section E.8 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.
a * b bytes long. The block's contents will be
cleared to zeros. Returns a null pointer if a or b is zero
or if insufficient memory is available.
A call with block null is equivalent to malloc(). A call
with new_size zero is equivalent to free().
malloc(), calloc(), or realloc() (and not yet freed).
A 32-bit virtual address can be divided into a 20-bit page number and a 12-bit page offset (or just offset), like this:
31 12 11 0
+-------------------+-----------+
| Page Number | Offset |
+-------------------+-----------+
Virtual Address
|
Header threads/vaddr.h
defines these functions and macros for
working with virtual addresses:
Virtual memory in Pintos is divided into two regions: user virtual
memory and kernel virtual memory (see section 3.1.4 Virtual Memory Layout). The
boundary between them is PHYS_BASE:
User virtual memory ranges from virtual address 0 up to
PHYS_BASE. Kernel virtual memory occupies the rest of the
virtual address space, from PHYS_BASE up to 4 GB.
The 80x86 doesn't provide any way to directly access memory given
a physical address. This ability is often necessary in an operating
system kernel, so Pintos works around it by mapping kernel virtual
memory one-to-one to physical memory. That is, virtual address
PHYS_BASE accesses physical address 0, virtual address
PHYS_BASE + 0x1234 accesses physical address 0x1234, and
so on up to the size of the machine's physical memory. Thus, adding
PHYS_BASE to a physical address obtains a kernel virtual address
that accesses that address; conversely, subtracting PHYS_BASE
from a kernel virtual address obtains the corresponding physical
address. Header threads/vaddr.h
provides a pair of functions to
do these translations:
The code in pagedir.c
is an abstract interface to the 80x86
hardware page table, also called a "page directory" by Intel processor
documentation. The page table interface uses a uint32_t * to
represent a page table because this is convenient for accessing their
internal structure.
The sections below describe the page table interface and internals.
These functions create, destroy, and activate page tables. The base Pintos code already calls these functions where necessary, so it should not be necessary to call them yourself.
Returns a null pointer if memory cannot be obtained.
These functions examine or update the mappings from pages to frames encapsulated by a page table. They work on both active and inactive page tables (that is, those for running and suspended processes), flushing the TLB as necessary.
User page upage must not already be mapped in pd.
Kernel page kpage should be a kernel virtual address obtained from
the user pool with palloc_get_page(PAL_USER) (see Why PAL_USER?).
Returns true if successful, false on failure. Failure will occur if additional memory required for the page table cannot be obtained.
Other bits in the page table for page are preserved, permitting the accessed and dirty bits (see the next section) to be checked.
This function has no effect if page is not mapped.
80x86 hardware provides some assistance for implementing page replacement algorithms, through a pair of bits in the page table entry (PTE) for each page. On any read or write to a page, the CPU sets the accessed bit to 1 in the page's PTE, and on any write, the CPU sets the dirty bit to 1. The CPU never resets these bits to 0, but the OS may do so.
Proper interpretation of these bits requires understanding of aliases, that is, two (or more) pages that refer to the same frame. When an aliased frame is accessed, the accessed and dirty bits are updated in only one page table entry (the one for the page used for access). The accessed and dirty bits for the other aliases are not updated.
See section 4.1.5.1 Accessed and Dirty Bits, on applying these bits in implementing page replacement algorithms.
The functions provided with Pintos are sufficient to implement the projects. However, you may still find it worthwhile to understand the hardware page table format, so we'll go into a little detail in this section.
The top-level paging data structure is a page called the "page directory" (PD) arranged as an array of 1,024 32-bit page directory entries (PDEs), each of which represents 4 MB of virtual memory. Each PDE may point to the physical address of another page called a "page table" (PT) arranged, similarly, as an array of 1,024 32-bit page table entries (PTEs), each of which translates a single 4 kB virtual page to a physical page.
Translation of a virtual address into a physical address follows the three-step process illustrated in the diagram below:(5)
31 22 21 12 11 0
+----------------------+----------------------+----------------------+
| Page Directory Index | Page Table Index | Page Offset |
+----------------------+----------------------+----------------------+
| | |
_______/ _______/ _____/
/ / /
/ Page Directory / Page Table / Data Page
/ .____________. / .____________. / .____________.
|1,023|____________| |1,023|____________| | |____________|
|1,022|____________| |1,022|____________| | |____________|
|1,021|____________| |1,021|____________| \__\|____________|
|1,020|____________| |1,020|____________| /|____________|
| | | | | | | |
| | | \____\| |_ | |
| | . | /| . | \ | . |
\____\| . |_ | . | | | . |
/| . | \ | . | | | . |
| . | | | . | | | . |
| | | | | | | |
|____________| | |____________| | |____________|
4|____________| | 4|____________| | |____________|
3|____________| | 3|____________| | |____________|
2|____________| | 2|____________| | |____________|
1|____________| | 1|____________| | |____________|
0|____________| \__\0|____________| \____\|____________|
/ /
|
Pintos provides some macros and functions that are useful for working with raw page tables:
threads/pte.h.
threads/vaddr.h.
You do not need to understand the PTE format to do the Pintos projects, unless you wish to incorporate the page table into your supplemental page table (see section 4.1.4 Managing the Supplemental Page Table).
The actual format of a page table entry is summarized below. For complete information, refer to section 3.7, "Page Translation Using 32-Bit Physical Addressing," in [ IA32-v3a].
31 12 11 9 6 5 2 1 0 +---------------------------------------+----+----+-+-+---+-+-+-+ | Physical Address | AVL| |D|A| |U|W|P| +---------------------------------------+----+----+-+-+---+-+-+-+ |
Some more information on each bit is given below. The names are
threads/pte.h
macros that represent the bits' values:
Pintos clears this bit in PTEs for kernel virtual memory, to prevent user processes from accessing them.
Other bits are either reserved or uninteresting in a Pintos context and should be set to@tie{}0.
Header threads/pte.h
defines three functions for working with
page table entries:
Page directory entries have the same format as PTEs, except that the
physical address points to a page table page instead of a frame. Header
threads/pte.h
defines two functions for working with page
directory entries:
Pintos provides a hash table data structure in lib/kernel/hash.c
.
To use it you will need to include its header file,
lib/kernel/hash.h
, with #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.
Most implementations of the virtual memory project use a hash table to translate pages to frames. You may find other uses for hash tables as well.
A hash table is represented by struct hash.
struct hash
are "opaque." That is, code that uses a hash table should not access
struct hash members directly, nor should it need to. Instead, use
hash table functions and macros.
The hash table operates on elements of type struct hash_elem.
struct hash_elem member in the structure you want to include
in a hash table. Like struct hash, struct hash_elem is opaque.
All functions for operating on hash table elements actually take and
return pointers to struct hash_elem, not pointers to your hash table's
real element type.
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 &
operator to obtain a pointer to its
struct hash_elem. Use the hash_entry() macro to go the other
direction.
struct hash_elem, is embedded within. You must provide type,
the name of the structure that elem is inside, and member,
the name of the member in type that elem points to.
For example, suppose h is a struct hash_elem * variable
that points to a struct thread member (of type struct hash_elem)
named h_elem. Then, hash_entry@tie{(h, struct thread, h_elem)}
yields the address of the struct thread that h points within.
See section A.8.5 Hash Table Example, for an example.
Each hash table element must contain a key, that is, data that 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. 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:
unsigned int. The hash of an element should be a
pseudo-random function of the element's key. It must not depend on
non-key data in the element or on any non-constant data other than the
key. Pintos provides the following functions as a suitable basis for
hash functions.
If your key is a single piece of data of an appropriate type, it is
sensible for your hash function to directly return the output of one of
these functions. For multiple pieces of data, you may wish to combine
the output of more than one call to them using, e.g., the ^
(exclusive or)
operator. Finally, you may entirely ignore these functions and write
your own hash function from scratch, but remember that your goal is to
build an operating system kernel, not to design a hash function.
See section A.8.6 Auxiliary Data, for an explanation of aux.
If two elements compare equal, then they must hash to equal values.
See section A.8.6 Auxiliary Data, for an explanation of aux.
See section A.8.5 Hash Table Example, for hash and comparison function examples.
A few functions accept a pointer to a third kind of function as an argument:
See section A.8.6 Auxiliary Data, for an explanation of aux.
These functions create, destroy, and inspect hash tables.
hash_init() calls
malloc() and fails if memory cannot be allocated.
See section A.8.6 Auxiliary Data, for an explanation of aux, which is most often a null pointer.
hash_init().
If action is non-null, then it is called once for each element in
the hash table, which gives the caller an opportunity to deallocate any
memory or other resources used by the element. For example, if the hash
table elements are dynamically allocated using malloc(), then
action could free() the element. This is safe because
hash_clear() will not access the memory in a given hash element
after calling action on it. However, action must not call
any function that may modify the hash table, such as hash_insert()
or hash_delete().
hash_clear(). Then, frees the
memory held by hash. Afterward, hash must not be passed to
any hash table function, absent an intervening call to hash_init().
Each of these functions searches a hash table for an element that compares equal to one provided. Based on the success of the search, they perform some action, such as inserting a new element into the hash table, or simply return the result of the search.
The caller is responsible for deallocating any resources associated with
the returned element, as appropriate. For example, if the hash table
elements are dynamically allocated using malloc(), then the caller
must free() the element after it is no longer needed.
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 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
hash_find() or hash_delete(). See section A.8.5 Hash Table Example, for
an example. (Large structures should not be
allocated as local variables. See section A.2.1 struct thread, for more
information.)
The caller is responsible for deallocating any resources associated with
the returned element, as appropriate. For example, if the hash table
elements are dynamically allocated using malloc(), then the caller
must free() the element after it is no longer needed.
These functions allow iterating through the elements in a hash table. Two interfaces are supplied. The first requires writing and supplying a hash_action_func to act on each element (see section A.8.1 Data Types).
hash_insert() or hash_delete(). action
must not modify key data in elements, although it may modify any other
data.
The second interface is based on an "iterator" data type. Idiomatically, iterators are used as follows:
struct hash_iterator i;
hash_first (&i, h);
while (hash_next (&i))
{
struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
...do something with f...
}
|
hash_insert() or
hash_delete(), invalidates all iterators within that hash table.
Like struct hash and struct hash_elem, struct hash_elem is opaque.
hash_next() returns null for iterator, calling it again
yields undefined behavior.
hash_next() for
iterator. Yields undefined behavior after hash_first() has
been called on iterator but before hash_next() has been
called for the first time.
Suppose you have a structure, called struct page, that you
want to put into a hash table. First, define struct page to include a
struct hash_elem member:
struct page
{
struct hash_elem hash_elem; /* Hash table element. */
void *addr; /* Virtual address. */
/* ...other members... */
};
|
We write a hash function and a comparison function using addr as
the key. A pointer can be hashed based on its bytes, and the <
operator works fine for comparing pointers:
/* Returns a hash value for page p. */
unsigned
page_hash (const struct hash_elem *p_, void *aux UNUSED)
{
const struct page *p = hash_entry (p_, struct page, hash_elem);
return hash_bytes (&p->addr, sizeof p->addr);
}
/* Returns true if page a precedes page b. */
bool
page_less (const struct hash_elem *a_, const struct hash_elem *b_,
void *aux UNUSED)
{
const struct page *a = hash_entry (a_, struct page, hash_elem);
const struct page *b = hash_entry (b_, struct page, hash_elem);
return a->addr < b->addr;
}
|
(The use of UNUSED in these functions' prototypes suppresses a
warning that aux is unused. See section E.3 Function and Parameter Attributes, for information about UNUSED. See section A.8.6 Auxiliary Data, for an explanation of aux.)
Then, we can create a hash table like this:
struct hash pages; hash_init (&pages, page_hash, page_less, NULL); |
Now we can manipulate the hash table we've created. If p
is a pointer to a struct page, we can insert it into the hash table
with:
hash_insert (&pages, &p->hash_elem); |
If there's a chance that pages might already contain a
page with the same addr, then we should check hash_insert()'s
return value.
To search for an element in the hash table, use hash_find(). This
takes a little setup, because hash_find() takes an element to
compare against. Here's a function that will find and return a page
based on a virtual address, assuming that pages is defined at file
scope:
/* Returns the page containing the given virtual address,
or a null pointer if no such page exists. */
struct page *
page_lookup (const void *address)
{
struct page p;
struct hash_elem *e;
p.addr = address;
e = hash_find (&pages, &p.hash_elem);
return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}
|
struct page is allocated as a local variable here on the assumption
that it is fairly small. Large structures should not be allocated as
local variables. See section A.2.1 struct thread, for more information.
A similar function could delete a page by address using
hash_delete().
In simple cases like the example above, there's no need for the
aux parameters. In these cases, just pass a null pointer to
hash_init() for aux and ignore the values passed to the hash
function and comparison functions. (You'll get a compiler warning if
you don't use the aux parameter, but you can turn that off with
the UNUSED macro, as shown in the example, or you can just ignore
it.)
aux is useful when you have some property of the data in the 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 aux parameter.
The hash table does not do any internal synchronization. It is the
caller's responsibility to synchronize calls to hash table functions.
In general, any number of functions that examine but do not modify the
hash table, such as hash_find() or hash_next(), may execute
simultaneously. However, these function cannot safely execute at the
same time as any function that may modify a given hash table, such as
hash_insert() or hash_delete(), nor may more than one function
that can modify a given hash table execute safely at once.
It is also the caller's responsibility to synchronize access to data in hash table elements. How to synchronize access to this data depends on how it is designed and organized, as with any other data structure.
| [ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |