Move reboot() and power_off() to new file, and rename to fit convention.
[pintos-anon] / doc / reference.texi
index bc0e3ad156190a3ac7d680fa101d2db9d9d4365e..bfa076081eafaf74591d50f537d6be4b63b67e0e 100644 (file)
@@ -100,7 +100,7 @@ arranged to begin with the assembly module
 @func{main}, which never returns.
 
 There's one more trick: the Pintos kernel command line
 @func{main}, which never returns.
 
 There's one more trick: the Pintos kernel command line
-is in stored the boot loader.  The @command{pintos} program actually
+is stored in the boot loader.  The @command{pintos} program actually
 modifies a copy of the boot loader on disk each time it runs the kernel,
 putting
 in whatever command line arguments the user supplies to the kernel,
 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,
@@ -136,32 +136,19 @@ just use @func{memset} to zero it out.  The other task of
 the loader stored it and put it into the @code{ram_pages} variable for
 later use.
 
 the loader stored it and put it into the @code{ram_pages} variable for
 later use.
 
-Next, @func{thread_init} initializes the thread system.  We will defer
-full discussion to our discussion of Pintos threads below.  It is
-called so early in initialization because the console, initialized
-just afterward, tries to use locks, and locks in turn require there to be a
-running thread.
-
-Then we initialize the console so that @func{printf} will work.
-@func{main} calls @func{vga_init}, which initializes the VGA text
-display and clears the screen.  It also calls @func{serial_init_poll}
-to initialize the first serial port in ``polling mode,'' that is,
-where the kernel busy-waits for the port to be ready for each
-character to be output.  (We use polling mode until we're ready to enable
-interrupts, later.)  Finally we initialize the console device and
-print a startup message to the console.
-
-@func{main} calls @func{read_command_line} to break the kernel command
+Next, @func{main} calls @func{read_command_line} to break the kernel command
 line into arguments, then @func{parse_options} to read any options at
 the beginning of the command line.  (Actions specified on the
 command line execute later.)
 
 line into arguments, then @func{parse_options} to read any options at
 the beginning of the command line.  (Actions specified on the
 command line execute later.)
 
-@func{main} calls @func{random_init} to initialize the kernel random
-number generator.  If the user specified @option{-rs} on the
-@command{pintos} command line, @func{parse_options} already did
-this, but calling it a second time is harmless.
+@func{thread_init} initializes the thread system.  We will defer full
+discussion to our discussion of Pintos threads below.  It is called so
+early in initialization because a valid thread structure is a
+prerequisite for acquiring a lock, and lock acquisition in turn is
+important to other Pintos subsystems.  Then we initialize the console
+and print a startup message to the console.
 
 
-The next block of functions we call initialize the kernel's memory
+The next block of functions we call initializes the kernel's memory
 system.  @func{palloc_init} sets up the kernel page allocator, which
 doles out memory one or more pages at a time (@pxref{Page Allocator}).
 @func{malloc_init} sets
 system.  @func{palloc_init} sets up the kernel page allocator, which
 doles out memory one or more pages at a time (@pxref{Page Allocator}).
 @func{malloc_init} sets
@@ -177,7 +164,9 @@ The next set of calls initializes the interrupt system.
 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
 (IDT) to ready it for interrupt handling (@pxref{Interrupt
 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
 (IDT) to ready it for interrupt handling (@pxref{Interrupt
 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
-handling timer interrupts and keyboard interrupts, respectively.  In
+handling timer interrupts and keyboard interrupts, respectively. 
+@func{input_init} sets up to merge serial and keyboard input into one
+stream.  In
 projects 2 and later, we also prepare to handle interrupts caused by
 user programs using @func{exception_init} and @func{syscall_init}.
 
 projects 2 and later, we also prepare to handle interrupts caused by
 user programs using @func{exception_init} and @func{syscall_init}.
 
@@ -336,6 +325,13 @@ Pintos as provided ignores thread priorities, but you will implement
 priority scheduling in project 1 (@pxref{Priority Scheduling}).
 @end deftypecv
 
 priority scheduling in project 1 (@pxref{Priority Scheduling}).
 @end deftypecv
 
+@deftypecv {Member} {@struct{thread}} {@struct{list_elem}} allelem
+This ``list element'' is used to link the thread into the list of all
+threads.  Each thread is inserted into this list when it is created
+and removed when it exits.  The @func{thread_foreach} function should 
+be used to iterate over all threads.
+@end deftypecv
+
 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
 A ``list element'' used to put the thread into doubly linked lists,
 either @code{ready_list} (the list of threads ready to run) or a list of
 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
 A ``list element'' used to put the thread into doubly linked lists,
 either @code{ready_list} (the list of threads ready to run) or a list of
@@ -457,6 +453,16 @@ function to keep this thread from running for any particular length of
 time.
 @end deftypefun
 
 time.
 @end deftypefun
 
+@deftypefun void thread_foreach (thread_action_func *@var{action}, void *@var{aux})
+Iterates over all threads @var{t} and invokes @code{action(t, aux)} on each.
+@var{action} must refer to a function that matches the signature 
+given by @func{thread_action_func}:
+
+@deftp {Type} {void thread_action_func (struct thread *@var{thread}, void *@var{aux})}
+Performs some action on a thread, given @var{aux}.
+@end deftp
+@end deftypefun
+
 @deftypefun int thread_get_priority (void)
 @deftypefunx void thread_set_priority (int @var{new_priority})
 Stub to set and get thread priority.  @xref{Priority Scheduling}.
 @deftypefun int thread_get_priority (void)
 @deftypefunx void thread_set_priority (int @var{new_priority})
 Stub to set and get thread priority.  @xref{Priority Scheduling}.
@@ -495,7 +501,7 @@ CPU's current stack pointer in the current @struct{thread}'s @code{stack}
 member, restores the new thread's @code{stack} into the CPU's stack
 pointer, restores registers from the stack, and returns.
 
 member, restores the new thread's @code{stack} into the CPU's stack
 pointer, restores registers from the stack, and returns.
 
-The rest of the scheduler is implemented in @func{schedule_tail}.  It
+The rest of the scheduler is implemented in @func{thread_schedule_tail}.  It
 marks the new thread as running.  If the thread we just switched from
 is in the dying state, then it also frees the page that contained the
 dying thread's @struct{thread} and stack.  These couldn't be freed
 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
@@ -524,8 +530,8 @@ pointer,@footnote{This is because @func{switch_threads} takes
 arguments on the stack and the 80@var{x}86 SVR4 calling convention
 requires the caller, not the called function, to remove them when the
 call is complete.  See @bibref{SysV-i386} chapter 3 for details.}
 arguments on the stack and the 80@var{x}86 SVR4 calling convention
 requires the caller, not the called function, to remove them when the
 call is complete.  See @bibref{SysV-i386} chapter 3 for details.}
-calls @func{schedule_tail} (this special case is why
-@func{schedule_tail} is separate from @func{schedule}), and returns.
+calls @func{thread_schedule_tail} (this special case is why
+@func{thread_schedule_tail} is separate from @func{schedule}), and returns.
 We fill in its stack frame so that it returns into
 @func{kernel_thread}, a function in @file{threads/thread.c}.
 
 We fill in its stack frame so that it returns into
 @func{kernel_thread}, a function in @file{threads/thread.c}.
 
@@ -550,7 +556,7 @@ synchronization primitives to help out.
 * Semaphores::                  
 * Locks::                       
 * Monitors::                    
 * Semaphores::                  
 * Locks::                       
 * Monitors::                    
-* Memory Barriers::             
+* Optimization Barriers::             
 @end menu
 
 @node Disabling Interrupts
 @end menu
 
 @node Disabling Interrupts
@@ -694,7 +700,7 @@ implementation in @file{lib/kernel/list.c}.
 
 A @dfn{lock} is like a semaphore with an initial value of 1
 (@pxref{Semaphores}).  A lock's equivalent of ``up'' is called
 
 A @dfn{lock} is like a semaphore with an initial value of 1
 (@pxref{Semaphores}).  A lock's equivalent of ``up'' is called
-``acquire'', and the ``down'' operation is called ``release''.
+``release'', and the ``down'' operation is called ``acquire''.
 
 Compared to a semaphore, a lock has one added restriction: only the
 thread that acquires a lock, called the lock's ``owner'', is allowed to
 
 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
@@ -842,59 +848,88 @@ char get (void) @{
 @}
 @end example
 
 @}
 @end example
 
-@node Memory Barriers
-@subsection Memory Barriers
+Note that @code{BUF_SIZE} must divide evenly into @code{SIZE_MAX + 1}
+for the above code to be completely correct.  Otherwise, it will fail
+the first time @code{head} wraps around to 0.  In practice,
+@code{BUF_SIZE} would ordinarily be a power of 2.
+
+@node Optimization Barriers
+@subsection Optimization Barriers
 
 @c We should try to come up with a better example.
 @c Perhaps something with a linked list?
 
 
 @c We should try to come up with a better example.
 @c Perhaps something with a linked list?
 
-Suppose we add a ``feature'' that, whenever a timer interrupt
-occurs, the character in global variable @code{timer_put_char} is
-printed on the console, but only if global Boolean variable
-@code{timer_do_put} is true.
+An @dfn{optimization barrier} is a special statement that prevents the
+compiler from making assumptions about the state of memory across the
+barrier.  The compiler will not reorder reads or writes of variables
+across the barrier or assume that a variable's value is unmodified
+across the barrier, except for local variables whose address is never
+taken.  In Pintos, @file{threads/synch.h} defines the @code{barrier()}
+macro as an optimization barrier.
 
 
-If interrupts are enabled, this code for setting up @samp{x} to be
-printed is clearly incorrect, because the timer interrupt could intervene
-between the two assignments:
+One reason to use an optimization barrier is when data can change
+asynchronously, without the compiler's knowledge, e.g.@: by another
+thread or an interrupt handler.  The @func{too_many_loops} function in
+@file{devices/timer.c} is an example.  This function starts out by
+busy-waiting in a loop until a timer tick occurs:
 
 @example
 
 @example
-timer_do_put = true;            /* INCORRECT CODE */
-timer_put_char = 'x';
+/* Wait for a timer tick. */
+int64_t start = ticks;
+while (ticks == start)
+  barrier ();
 @end example
 
 @end example
 
-It might not be as obvious that the following code is just as
-incorrect:
+@noindent
+Without an optimization barrier in the loop, the compiler could
+conclude that the loop would never terminate, because @code{start} and
+@code{ticks} start out equal and the loop itself never changes them.
+It could then ``optimize'' the function into an infinite loop, which
+would definitely be undesirable.
+
+Optimization barriers can be used to avoid other compiler
+optimizations.  The @func{busy_wait} function, also in
+@file{devices/timer.c}, is an example.  It contains this loop:
 
 @example
 
 @example
-timer_put_char = 'x';           /* INCORRECT CODE */
-timer_do_put = true;
+while (loops-- > 0)
+  barrier ();
 @end example
 
 @end example
 
-The reason this second example might be a problem is that the compiler
-is, in general, free to reorder operations when it doesn't have a
-visible reason to keep them in the same order.  In this case, the
-compiler doesn't know that the order of assignments is important, so its
-optimization pass is permitted to exchange their order.
-There's no telling whether it will actually do this, and it is possible
-that passing the compiler different optimization flags or changing
-compiler versions will produce different behavior.
-
-The following is @emph{not} a solution, because locks neither prevent
-interrupts nor prevent the compiler from reordering the code within the
-region where the lock is held:
+@noindent
+The goal of this loop is to busy-wait by counting @code{loops} down
+from its original value to 0.  Without the barrier, the compiler could
+delete the loop entirely, because it produces no useful output and has
+no side effects.  The barrier forces the compiler to pretend that the
+loop body has an important effect.
+
+Finally, optimization barriers can be used to force the ordering of
+memory reads or writes.  For example, suppose we add a ``feature''
+that, whenever a timer interrupt occurs, the character in global
+variable @code{timer_put_char} is printed on the console, but only if
+global Boolean variable @code{timer_do_put} is true.  The best way to
+set up @samp{x} to be printed is then to use an optimization barrier,
+like this:
 
 @example
 
 @example
-lock_acquire (&timer_lock);     /* INCORRECT CODE */
 timer_put_char = 'x';
 timer_put_char = 'x';
+barrier ();
 timer_do_put = true;
 timer_do_put = true;
-lock_release (&timer_lock);
 @end example
 
 @end example
 
-Fortunately, real solutions do exist.  One possibility is to
-disable interrupts around the assignments.  This does not prevent
-reordering, but it makes the assignments atomic as observed by the
-interrupt handler.  It also has the extra runtime cost of disabling and
-re-enabling interrupts:
+Without the barrier, the code is buggy because the compiler is free to
+reorder operations when it doesn't see a reason to keep them in the
+same order.  In this case, the compiler doesn't know that the order of
+assignments is important, so its optimizer is permitted to exchange
+their order.  There's no telling whether it will actually do this, and
+it is possible that passing the compiler different optimization flags
+or using a different version of the compiler will produce different
+behavior.
+
+Another solution is to disable interrupts around the assignments.
+This does not prevent reordering, but it prevents the interrupt
+handler from intervening between the assignments.  It also has the
+extra runtime cost of disabling and re-enabling interrupts:
 
 @example
 enum intr_level old_level = intr_disable ();
 
 @example
 enum intr_level old_level = intr_disable ();
@@ -903,35 +938,34 @@ timer_do_put = true;
 intr_set_level (old_level);
 @end example
 
 intr_set_level (old_level);
 @end example
 
-A second possibility is to mark the declarations of
+A second solution is to mark the declarations of
 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}.  This
 keyword tells the compiler that the variables are externally observable
 and restricts its latitude for optimization.  However, the semantics of
 @samp{volatile} are not well-defined, so it is not a good general
 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}.  This
 keyword tells the compiler that the variables are externally observable
 and restricts its latitude for optimization.  However, the semantics of
 @samp{volatile} are not well-defined, so it is not a good general
-solution.
+solution.  The base Pintos code does not use @samp{volatile} at all.
 
 
-Usually, the best solution is to use a compiler feature called a
-@dfn{memory barrier}, a special statement that prevents the compiler
-from reordering memory operations across the barrier.  In Pintos,
-@file{threads/synch.h} defines the @code{barrier()} macro as a memory
-barrier.  Here's how we would use a memory barrier to fix this code:
+The following is @emph{not} a solution, because locks neither prevent
+interrupts nor prevent the compiler from reordering the code within the
+region where the lock is held:
 
 @example
 
 @example
+lock_acquire (&timer_lock);     /* INCORRECT CODE */
 timer_put_char = 'x';
 timer_put_char = 'x';
-barrier ();
 timer_do_put = true;
 timer_do_put = true;
+lock_release (&timer_lock);
 @end example
 
 @end example
 
-The compiler also treats invocation of any function defined externally,
-that is, in another source file, as a limited form of a memory barrier.
-Specifically, the compiler assumes that any externally defined function
-may access any statically or dynamically allocated data and any local
-variable whose address is taken.  This often means that explicit
-barriers can be omitted, and, indeed, this is why the base Pintos code
-does not need any barriers.
+The compiler treats invocation of any function defined externally,
+that is, in another source file, as a limited form of optimization
+barrier.  Specifically, the compiler assumes that any externally
+defined function may access any statically or dynamically allocated
+data and any local variable whose address is taken.  This often means
+that explicit barriers can be omitted.  It is one reason that Pintos
+contains few explicit barriers.
 
 A function defined in the same source file, or in a header included by
 
 A function defined in the same source file, or in a header included by
-the source file, cannot be relied upon as a memory barrier.
+the source file, cannot be relied upon as a optimization barrier.
 This applies even to invocation of a function before its
 definition, because the compiler may read and parse the entire source
 file before performing optimization.
 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.