A Tour Through Pintos
*********************

This chapter is a brief tour through 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 corresponding project.

Hint: try using ``tags'' to follow along with references to function and variable names (see Tags).

Loading
=======

This section covers the Pintos loader and basic kernel initialization.

The Loader
----------

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 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.

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 start out 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.  At any rate, it's necessary.

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 equipped to handle interrupts in protected mode yet, so we disable interrupts.

Finally it's time to load the kernel from disk.  We choose a simple, although 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 contains the boot loader itself).  We also assume that the BIOS has already set up the IDE controller for us.  We read KERNEL_LOAD_PAGES 4 kB pages of data 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 that it begins with the assembly module threads/start.S.  This assembly module just calls main, which never returns.

There's one more trick to the loader: the Pintos kernel command line is stored in the boot loader.  The pintos program actually modifies 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 something of a nasty hack, but it is simple and effective.

Kernel Initialization
---------------------

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 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.  You should notice that 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 C, whenever you declare a variable outside a function without providing an initializer, that variable goes into the BSS. (This isn't actually required by the ANSI C standard, but it is the case with most implementations of C on most machines.)  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 below, tries to use locks and locks in turn require there to be a running thread.

Then we initialize the console so that we can use printf. 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 set up interrupts later.)  Finally we initialize the console device and print a startup message to the console.

main calls argv_init to parse the kernel command line. This entails reading the command line out of the loader and updating global variables appropriately.

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.  malloc_init sets up the allocator that handles odd-sized allocations. paging_init sets up a page table for the kernel.

In projects 2 and later, main also calls tss_init and gdt_init, but we'll talk about those later.

main calls random_init to initialize the kernel random number generator.  argv_init might already have done this (if the user specified -rs on the pintos command line) but calling it a second time is harmless and has no effect.

We initialize the interrupt system in the next set of calls. intr_init sets up the CPU's interrupt descriptor table (IDT) to ready it for interrupt handling, then timer_init and kbd_init prepare us to handle timer interrupts and keyboard interrupts, respectively.  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 preemptively scheduling threads with thread_start, which also enables interrupts. Interrupt-driven serial port I/O is also possible now, so we use serial_init_queue to switch to that mode.  Finally, timer_calibrate calibrates the timer for accurate short delays.

If the filesystem is compiled in, as it will be in project 2 and later, we now initialize the disks with disk_init, then the filesystem with filesys_init, and run any operations that were requested on the kernel command line with fsutil_run.

Boot is complete, so we print a message.

For project 1, now we execute test, which runs whatever test is currently compiled into the kernel.  For later projects, we will instead run a user program and wait for it to complete.

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.

Threads
=======

struct thread
-------------

The main Pintos data structure for threads is thread, declared in threads/thread.h.  thread has these members with the given type:

tid_t tid;
     The thread's thread identifier or tid.  Every thread must have a tid that is unique over the entire lifetime of the kernel.  By default, 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.

enum thread_status status;
     The thread's state, one of these:

     THREAD_RUNNING
          The thread is running.  Exactly one thread is running at a given time. thread_current returns the running thread.

     THREAD_READY
          The thread is ready to run, but it's not running right now.  The thread could be selected to run the next time the scheduler is invoked.  Ready threads are kept in a doubly linked list called ready_list.

     THREAD_BLOCKED
          The thread is waiting for something, e.g. a lock to become available, an interrupt to be invoked.  The thread won't be scheduled again until it transitions to the THREAD_READY state with a call to thread_unblock.

     THREAD_DYING
          The thread will be destroyed by the scheduler after switching to the next thread.

char name[16];
     The thread's name as a string, or at least the first few characters of it.

uint8_t *stack;
     Every thread has its own stack to keep track of its state.  When the thread is running, the CPU's stack pointer register tracks the top of the stack and this member is unused.  But when the CPU switches to another thread, this member saves the thread's stack pointer.  No other members are needed to save the thread's registers, because the other registers that must be saved are saved on the stack.

int priority;
     A thread priority, ranging from the lowest possible priority PRI_MIN (0) to the highest possible priority PRI_MAX (59).  Pintos as provided ignores thread priorities, but you will implement priority scheduling in problem 1-3 (see Problem 1-3 Priority Scheduling).

list_elem elem;
     A ``list element'' used to put the thread into doubly linked lists, either the list of threads ready to run or a list of threads waiting on a semaphore.  Take a look at lib/kernel/list.h for information on how to use the Pintos doubly linked list ADT.

uint32_t *pagedir;
     Only present in project 2 and later.

unsigned magic;
     Always set to THREAD_MAGIC, which is just a random number defined in threads/thread.c, and used to detect stack overflow. See below for more information.

Every 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          |
                  |                                 |
                  |                                 |
                  |                                 |
                  |                                 |
                  |                                 |
                  |                                 |
                  |                                 |
                  |                                 |
                  +---------------------------------+
                  |              magic              |
                  |                :                |
                  |                :                |
                  |              status             |
                  |               tid               |
             0 kB +---------------------------------+

The upshot of this is twofold.  First, thread must not be allowed to grow too big.  If it does, then there will not be enough room for the kernel stack.  Our base 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.

This brings us to the purpose of thread's magic member.  If a thread's stack does overflow, then magic will be the first member of thread to be overwritten, because it is closest to the kernel stack.  Thus, some of the thread functions (notably thread_current) check that magic has the proper value.

Thread Functions
----------------

threads/thread.c implements several public functions for thread support.  Let's take a look at the most useful:

 -- Function: void thread_init (void)
     Called by main to initialize the thread system.  Its main purpose is to create a thread for Pintos's initial thread. This is possible because the Pintos loader sets up the initial thread's stack at the end of a page.  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.

 -- Function: void thread_start (void)
     Called by 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 enables the scheduler because processes are rescheduled on return from the timer interrupt, using intr_yield_on_return (see External Interrupt Handling).

 -- Function: void thread_create (const char *NAME, int PRIORITY, thread_func *FUNC, void *AUX)
     Creates and starts a new thread named NAME with the given PRIORITY, returning the new thread's tid.  The thread executes FUNC, passing AUX as the function's single argument.

     thread_create works by allocating a page for the thread's thread and stack and initializing its members, then setting up a set of fake stack frames for it (we'll talk more about this later).  The thread was initialized in the blocked state, so the final action before returning is to unblock it, allowing the new thread to be scheduled.

 -- Function: void thread_block (void)
     Transitions the running thread from the running state to the blocked state.  This thread will not run again until thread_unblock is called on it, so you'd better have some way arranged for that to happen.

 -- Function: void thread_unblock (struct thread *THREAD)
     Transitions THREAD, which must be in the blocked state, to the ready state, allowing it to continue to run.  This is called when the event that the thread is waiting for happens, such as the lock that the thread is waiting on becoming available.

 -- Function: struct thread *thread_current (void)
     Returns the running thread.

 -- Function: void thread_exit (void) NO_RETURN
     Causes the current thread to exit.  Never returns (hence NO_RETURN: see UNUSED NO_RETURN NO_INLINE PRINTF_FORMAT).

 -- Function: void thread_yield (void)
     Yields the CPU to the scheduler, which picks a new thread to run.  The new thread might be the current thread, so you can't depend on this function to keep this thread from running for any particular length of time.

Thread Switching
----------------

schedule is the function 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 these functions call schedule, they all disable interrupts (or ensure that they are already disabled) and then change the running thread's state to something other than running.

The actual schedule implementation is simple.  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 in Pintos, 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, stores the CPU's current stack pointer into the current 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 as 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 thread and stack, which couldn't be freed before 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, a 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:

  * The topmost fake stack frame is for switch_threads, represented by switch_threads_frame.  The important part of this frame is its eip member, the return address.  We point eip to switch_entry.

  * The next fake stack frame is for switch_entry, an assembly language routine in threads/switch.S that adjusts the stack pointer, (This is because switch_threads takes arguments on the stack and the 80X86 SVR4 calling convention requires the caller, not the called function, to remove them when the call is complete.  See SysV-i386 chapter 3 for details.) 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.

  * The final stack frame is for 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.

Synchronization
---------------

Situations often arise in threaded programs in which threads want to share resources.  If resource sharing is not handled in a careful, controlled fashion, then threads can end up making 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.

Disabling Interrupts
....................

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.

Types and functions for disabling and enabling interrupts are in threads/interrupt.h.

 -- Type: enum intr_level
     One of INTR_OFF or INTR_ON, denoting that interrupts are disabled or enabled, respectively.

 -- Function: enum intr_level intr_get_level (void)
     Returns the current interrupt state.

 -- Function: enum intr_level intr_set_level (enum intr_level LEVEL)
     Turns interrupts on or off according to LEVEL and returns the previous interrupt state.

 -- Function: enum intr_level intr_enable (void)
     Turns interrupts on and returns the previous interrupt state.

 -- Function: enum intr_level intr_disable (void)
     Turns interrupts off and returns the previous interrupt state.

Semaphores
..........

A semaphore is a nonnegative integer along with two operators for atomically manipulating it, which are:

  * ``Down'' or ``P'': wait for the value to become positive, then decrement it.

  * ``Up'' or ``V'': increment the value (and wake up one waiting thread, if any).

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.

A semaphore initialized to 0 can be useful for waiting 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.

Pintos declared its semaphore type and operations on them in threads/synch.h.

 -- Type: struct semaphore
     Represents a semaphore.

 -- Function: void sema_init (struct semaphore *sema, unsigned value, const char *name)
     Initializes SEMA as a new semaphore with the given initial VALUE.  Gives SEMA the specified NAME for use in debugging.

 -- Function: void sema_down (struct semaphore *SEMA)
     Executes the ``down'' or ``P'' operation on the semaphore, waiting for its value to become positive and then decrementing it by one.

 -- Function: void sema_up (struct semaphore *SEMA)
     Increments SEMA's value.  If any threads are waiting on SEMA, wakes one of them up.

Semaphores are internally built out of interrupt disabling (see Disabling Interrupts), thread blocking and unblocking (thread_block and thread_unblock).  Semaphores maintain a doubly linked list of waiting threads using the linked list implementation in lib/kernel/list.c.

Locks
.....

A lock is a specialization of a semaphore (see Semaphores) with an initial value of 1.  The difference between a lock and such a semaphore is twofold.  First, a semaphore can have a value greater than 1, but a lock can only be owned by a single thread at a time. Second, a semaphore does not have an owner, meaning that one thread can ``down'' the semaphore and then another one ``up'' it, but with a lock a single thread must both acquire and release it.  When these restrictions prove onerous, 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.

 -- Type: struct lock
     Represents a lock.

 -- Function: void lock_init (struct lock *LOCK, const char *NAME)
     Initializes LOCK as a new lock and gives it the specified NAME for use in debugging.

 -- Function: void lock_acquire (struct lock *LOCK)
     Acquires LOCK for use by the current thread, first waiting for any current owner to release it if necessary.

 -- Function: void lock_release (struct lock *LOCK)
     Releases LOCK, which the current thread must own.

 -- Function: bool lock_held_by_current_thread (const struct lock *LOCK)
     Returns true if the running thread owns LOCK, false otherwise.

Condition Variables
...................

A condition variable allows one piece of code to signal a condition and cooperating code to receive the signal and act upon it.  Each condition variable is associated with a lock.  A given condition variable is associated with only a single lock, but one lock may be associated with any number of condition variables.  A set of condition variables taken together with their lock is called a ``monitor.''

A thread that owns the monitor lock is said to be ``in the monitor.'' The thread in the monitor has control over all the data protected with the lock.  It may freely examine or modify this data.  If it discovers that it needs to wait for some condition to become true, then it ``waits'' on the associated condition, which releases the lock and waits for the condition to be signaled.  If it, on the other hand, 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 classical example of a monitor is handling a buffer into which one ``producer'' thread writes characters and out of which a second ``consumer'' thread reads characters.  To implement this case 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 (&not_full, &lock);
       buf[head++ % BUF_SIZE] = ch;     /* Add CH to BUF. */
       n++;
       cond_signal (&not_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 from BUF as long as it's empty. */
         cond_wait (&not_empty, &lock);
       ch = buf[tail++ % BUF_SIZE];    /* Get CH from BUF. */
       n--;
       cond_signal (&not_full, &lock); /* BUF can't be full anymore. */
       lock_release (&lock);
     }

As the code above illustrates, Pintos monitors are ``Mesa'' style, not ``Hoare'' style, that is, sending and receiving a signal are not an atomic operation.  Thus, typically the caller must recheck the condition after the wait completes and, if necessary, wait again.

Condition variable types and functions are declared in threads/synch.h.

 -- Type: struct condition
     Represents a condition variable.

 -- Function: void cond_init (struct condition *COND, const char *NAME)
     Initializes COND as a new condition variable and gives it the specified NAME for use in debugging.

 -- Function: void cond_wait (struct condition *COND, struct lock *NAME)
     Atomically releases LOCK (the monitor lock) and waits for COND to be signaled by some other piece of code.  After COND is signaled, LOCK is reacquired before returning. LOCK must be held before calling this function.

 -- Function: void cond_signal (struct condition *COND, struct lock *LOCK)
     If any threads are waiting on COND (protected by monitor lock LOCK), then this function signals one of them to wake up from its wait.  LOCK must be held before calling this function.

 -- Function: void cond_broadcast (struct condition *COND, struct lock *LOCK)
     Wakes up all threads, if any, waiting on COND (protected by monitor lock LOCK).  LOCK must be held before calling this function.

Interrupt Handling
------------------

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:

  * External interrupts, that is, interrupts originating outside the CPU.  These interrupts come from hardware devices such as the system timer, keyboard, serial ports, and disks.  External interrupts are asynchronous, meaning that they don't occur in a fashion synchronized with anything going on in the CPU.  External interrupts are what intr_disable and related functions can arrange to postpone (see Disabling Interrupts).

  * Internal interrupts, that is, interrupts caused by something executing on the CPU.  These interrupts are caused by something unusual happening during instruction execution: accessing invalid memory (a page fault), executing invalid instructions, and various other disallowed activities.  Because they are caused by CPU instructions, internal interrupts are synchronous or synchronized with CPU instructions.  intr_disable does not disable internal interrupts.

Because the CPU treats all interrupts largely the same way, regardless of source, Pintos uses the same infrastructure for both internal and external interrupts, up to a point.  The next section describes this common infrastructure.  But external and internal interrupts are actually quite different, so we also follow up that section with one specific to each category.

If you haven't already read chapter 3 in IA32-v1, it is recommended that you do so now.  You might also want to skim chapter 5 in IA32-v3.

Interrupt Infrastructure
........................

When an interrupt occurs while the kernel is running, the CPU saves its most essential state on the stack and jumps to an interrupt handler routine.  The 80X86 architecture allows for 256 possible interrupts, each of which can have its own handler. The handler for each interrupt is 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. (threads/intr-stubs.S is so repetitive that it is actually generated by a Perl script, threads/intr-stubs.pl.  Thus, you will actually find threads/intr-stubs.S in your threads/build/threads directory, not in plain threads.)  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 save 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 any function that has been registered for handling the particular interrupt.  (If there's no function registered, it dumps some information to the console and panics the kernel.)  It does some extra processing for external interrupts that we'll discuss later.

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.

A few types and functions apply to both internal and external interrupts.

 -- Function: void intr_register (uint8_t VEC, int DPL, enum intr_level LEVEL, intr_handler_func *FUNC, const char *NAME)
     Registers FUNC to be called when the interrupt numbered VEC is triggered.  Names the interrupt NAME for debugging purposes.

     If LEVEL is INTR_OFF then handling of further interrupts will be disabled while the interrupt is being processed.  If VEC denotes an external interrupt, then LEVEL must be INTR_OFF.  Otherwise, interrupts should normally be turned on during the handling of an internal interrupt.

     For internal interrupts, 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 as well (this is useful only starting with project 2).  DPL has no effect on external interrupts

 -- Type: void intr_handler_func (struct intr_frame *FRAME)
     This is the type of an interrupt handler function.  Its FRAME argument (see below) allows it to determine the cause of the interrupt and the state of the thread that was interrupted.

 -- Type: struct intr_frame
     The stack frame of an interrupt handler.  Its most interesting members are as follows:

     uint32_t edi;

     uint32_t esi;

     uint32_t ebp;

     uint32_t esp_dummy;

     uint32_t ebx;

     uint32_t edx;

     uint32_t ecx;

     uint32_t eax;

     uint16_t es;

     uint16_t ds;
          Register values in the interrupted thread saved by intr_entry. The esp_dummy value isn't actually used (refer to the description of PUSHA in IA32-v2b for details).

     uint32_t vec_no;
          The interrupt vector number, ranging from 0 to 255.

     uint32_t error_code;
          The ``error code'' pushed on the stack by the CPU for some internal interrupts.

     void (*eip) (void);
          The address of the next instruction to be executed by the interrupted thread.

     void *esp;
          The interrupted thread's stack pointer.

 -- Function: const char * intr_name (uint8_t VEC)
     Returns the registered name of the interrupt numbered VEC, or "unknown" if the interrupt's name is not known.

Internal Interrupt Handling
...........................

When an internal interrupt occurs, it is because the running kernel thread (or, starting from project 2, the running user process) has caused it.  Thus, because it is related to a thread (or process), an internal interrupt is said to happen in a ``process context.''

In an internal interrupt, it can make sense to examine the intr_frame passed to the interrupt handler.  In cases where the interrupted thread intentionally caused the interrupt, it can even make sense to modify it.  When the interrupt returns, modified members in intr_frame become changes to the thread's registers. We'll use this in project 2 to return values from system call handlers.

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 Synchronization).

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. They are asynchronous, so it can be invoked at any time that interrupts have not been enabled.  We say that an external interrupt runs in an ``interrupt context.''

In an external interrupt, the 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, though 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 (see 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 includes thread_yield, 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 tried to sleep and that thread resumed, then the two uses of the single stack would interfere, which cannot be allowed.

Because an external interrupt runs with interrupts disabled, it 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.

External interrupts are also special because they are controlled by a device external to the CPU called a programmable interrupt controller or PIC for short.  When intr_init sets up the CPU's IDT, it also initializes the PIC for interrupt handling.  The PIC also has to be ``acknowledged'' at the end of processing for each external interrupt.  intr_handler takes care of that by calling pic_end_of_interrupt, which sends the proper signals to the PIC.

The following additional interrupts functions are related to external interrupts.

 -- Function: bool intr_context (void)
     Returns true if we are running in an interrupt context and false otherwise.  Mainly used at the beginning of functions that might sleep or that otherwise should not be, in this form:

          ASSERT (!intr_context ());

 -- Function: intr_yield_on_return (void)
     When called in an interrupt context, causes 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 on every timer tick.

Memory Allocation
-----------------

Pintos contains two memory allocators, one that allocates memory in units of a page, and one that can allocate blocks of any size.

Page Allocation
...............

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 a 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 pools is managed with a bitmap of used pages, one bit per page in the pool.  An allocation request for N pages scans the bitmap, starting from the beginning, for N consecutive bits set to false, indicating that those pages are free, and then sets those bits to true to mark them as now used.  This is a ``first fit'' allocation strategy.

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 N / 2 pages are free! However, single-page requests can't fail due to fragmentation.  Thus, it is best to limit the need to allocate more than one contiguous page as much as possible.

The interesting page allocator types and functions are described below.

 -- Type: enum palloc_flags
     A set of flags that describe how to allocate pages.  These flags may be combined in any combination:

     PAL_ASSERT
          If the pages cannot be allocated, panic the kernel.  This is only appropriate during kernel initialization, because user processes should never be permitted to panic the kernel.

     PAL_ZERO
          Clear the pages to all zeros before returning them.  If not set, newly allocated pages' contents are unpredictable.

     PAL_USER
          Obtain the pages from the user pool.  If not set, pages are allocated from the kernel pool.

 -- Function: void * palloc_get_page (enum palloc_flags FLAGS)
     Obtains a single free page, allocating it in the manner specified by FLAGS, and returns it.  Returns a null pointer if no pages are free.

 -- Function: void * palloc_get_multiple (enum palloc_flags FLAGS, size_t PAGE_CNT)
     Obtains PAGE_CNT contiguous free pages, allocating them in the manner specified by FLAGS, and returns them.  Returns a null pointer if no pages are free.

 -- Function: void palloc_free_page (void *PAGE)
     Frees PAGE, which must have been obtained using palloc_get_page or palloc_get_multiple.

 -- Function: void palloc_free_multiple (void *PAGES, size_t PAGE_CNT)
     Frees the PAGE_CNT contiguous pages starting at PAGES. All of the pages must have been obtained using palloc_get_page or palloc_get_multiple.

Block Allocator
...............

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 of these applies to blocks no larger than 1 kB (one fourth of the 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 power of 2 size.

A different strategy applies to allocating 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 will not require a new page from the page allocator at all.  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 malloc, calloc, and free.