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.

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

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              |
                  |                :                |
                  |                :                |
                  |               name              |
                  |              status             |
             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 some of them:

 -- 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 in the return path from the timer interrupt.  FIXME

 -- Function: void thread_tick (void)
     Called by timer_interrupt on every timer interrupt.  Just increments counters that keep track of how often various kinds of threads run.

 -- Function: void thread_print_stats (void)
     Prints the statistics kept by thread_ticK] to the console.
     Called when Pintos is terminating.

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