This document describes the GHC/Hugs run-time system. It serves as
a Glasgow/Yale/Nottingham ``contract'' about what the RTS does.
-\Subsection{New features compared to GHC 2.04}{new-features}
+\Subsection{New features compared to GHC 3.xx}{new-features}
\begin{itemize}
\item The RTS supports mixed compiled/interpreted execution, so
explicitly state where results should be returned in registers (or on
the stack) instead of on the heap.
-\item
+\item Exceptions are supported by the RTS.
+
+\item Weak Pointers generalise the previously available Foreign Object
+interface.
-Lazy black-holing has been replaced by eager black-holing. The
-problem with lazy black-holing is that it leaves slop in the heap
-which conflicts with the use of a mostly-copying collector.
-\ToDo{Why? I think we can still do lazy black holing without leaving
-slop (SDM)}
+\item The garbage collector supports a number of new features,
+including a dynamically resizable heap and multiple generations with
+aging within a generation.
\end{itemize}
generations, etc taking into account residency, GC rate and page fault
rate.
-\item
-There should be no need to specify the amnount of stack/heap space to
-allocate when you started a program - let it just take as much or as
-little as it wants. (It might be useful to be able to specify maximum
-sizes and to be able to suggest an initial size.)
-
\item
We could trigger a GC when all threads are blocked waiting for IO if
the allocation arena (or some of the generations) are nearly full.
The headers vary between different kinds of object but they all start
with a pointer to a pair consisting of an \emph{info table} and some
\emph{entry code}. The info table is used both by the evaluators and
-by the storage manager and contains an @INFO_TYPE@ field which
-identifies which kind of heap object uses it and determines the
-interpretation of the payload and of the other fields of the info
-table. The entry code is some machine code used by the machine code
-evaluator to evaluate closures and raises an error for other kinds of
-objects.
+by the storage manager and contains a @type@ field which identifies
+which kind of heap object uses it and determines the interpretation of
+the payload and of the other fields of the info table. The entry code
+is some machine code used by the machine code evaluator to evaluate
+closures and raises an error for other kinds of objects.
The major kinds of heap object used are as follows. (For simplicity,
this description omits certain optimisations and extra fields required
\end{tabular}
\end{center}
-\item[Primitive objects] are used to represent objects with unpointed
+\item[Primitive objects] are used to represent objects with unlifted
types which are too large to fit in a register (or stack slot) or for
which sharing must be preserved. Primitive objects include large
objects such as multiple precision integers and immutable arrays and
mutable objects such as mutable arrays, mutable variables, MVar's,
-IVar's and foreign object pointers. Since unpointed objects are not
-pointed, they cannot be entered. Their payload varies according to
-the kind of object.
+IVar's and foreign object pointers. Since primitive objects are not
+lifted, they cannot be entered. Their payload varies according to the
+kind of object.
\item[Function closures] are used to represent functions. Their
payload (if any) consists of the free variables of the function.
\item[Thunks] are used to represent unevaluated expressions which will
be updated with their result. Their payload (if any) consists of the
free variables of the function. The entry code for a thunk starts by
-pushing an \emph{update frame} onto the stack and overwriting the
-thunk with a \emph{black hole} (see Black Holes, below). When
-evaluation of the thunk completes, the update frame will cause the
-thunk to be overwritten again with an \emph{indirection} to the result
-of the thunk, which is always a constructor or a partial application.
+pushing an \emph{update frame} onto the stack. When evaluation of the
+thunk completes, the update frame will cause the thunk to be
+overwritten again with an \emph{indirection} to the result of the
+thunk, which is always a constructor or a partial application.
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
is overwritten with an indirection to the result of the closure and
any blocked threads are restored to the runnable queue.
+Closures are overwritten by black-holes during a ``lazy black-holing''
+phase which runs on each thread when it returns to the scheduler.
+\ToDo{section describing lazy black-holing}.
+
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
-@BH@ & \emph{Blocked threads} \\ \hline
+@BLACKHOLE@ & \emph{Blocked threads} \\ \hline
\end{tabular}
\end{center}
\ToDo{In a single threaded system, it's trivial to detect infinite
-loops: reentering a BH is always an error. How easy is it in a
+loops: reentering a BLACKHOLE is always an error. How easy is it in a
multi-threaded system?}
\item[Indirections] are used to update an unevaluated closure with its
Indirections needn't always point to a closure in WHNF. They can
point to a chain of indirections which point to an evaluated closure.
-When revertible black holes are added, they may also point to reverted
-black holes.
\item[Thread State Objects (@TSO@s)] represent Haskell threads. Their
-payload consists of a unique thread id, the status of the thread
-(runnable, blocked, etc) and the stack. @TSO@s may be resized by the
-scheduler if its stack is too small or too large.
+payload consists of some per-thread information such as the Thread ID
+and the status of the thread (runnable, blocked etc.), and the
+thread's stack. See @TSO.h@ for the full story. @TSO@s may be
+resized by the scheduler if its stack is too small or too large.
+
+The thread stack grows downwards from higher to lower addresses.
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
-@TSO@ & \emph{Thread Id} & \emph{Status} & \emph{Stack} \\ \hline
+@TSO@ & \emph{Thread info} & \emph{Stack} \\ \hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
-\emph{@RET_ADDR@} & \emph{Free Variables of the case alternatives} \\ \hline
+\emph{@RET_XXX@} & \emph{Free Variables of the case alternatives} \\ \hline
\end{tabular}
\end{center}
The free variables are a mixture of pointers and non-pointers whose
-layout is described by the info table.
+layout is described by a bitmask in the info table.
+
+There are several kinds of @RET_XXX@ return address - see
+\secref{activation-records} for the details.
Return addresses generated by the bytecode compiler look like this:
\begin{center}
\item[Update frames] are used to trigger updates. When an update
frame is entered, it overwrites the updatee with an indirection to the
-result, restarts any threads blocked on the @BH@ and returns to the
-stack object underneath the update frame.
+result, restarts any threads blocked on the @BLACKHOLE@ and returns to
+the stack object underneath the update frame.
\begin{center}
\begin{tabular}{|l|l|l|l|}\hline
-\emph{@UPDATE@} & \emph{Next Update Frame} & \emph{Updatee} \\ \hline
+\emph{@UPDATE_FRAME@} & \emph{Next Update Frame} & \emph{Updatee} \\ \hline
\end{tabular}
\end{center}
-\item[Seq frames] are used to implement the polymorphic @seq@ primitive.
-They are a special kind of update frame.
-
-\ToDo{Describe them properly}
+\item[Seq frames] are used to implement the polymorphic @seq@
+primitive. They are a special kind of update frame, and are linked on
+the update frame list.
+\begin{center}
+\begin{tabular}{|l|l|l|l|}\hline
+\emph{@SEQ_FRAME@} & \emph{Next Update Frame} \\ \hline
+\end{tabular}
+\end{center}
-\end{description}
+\item[Stop frames] are put on the bottom of each thread's stack, and
+act as sentinels for the update frame list (i.e. the last update frame
+points to the stop frame). Returning to a stop frame terminates the
+thread. Stop frames have no payload:
-\ToDo{We also need a stop frame which goes on the bottom of the stack
-when the thread terminates.}
+\begin{center}
+\begin{tabular}{|l|l|l|l|}\hline
+\emph{@SEQ_FRAME@} \\ \hline
+\end{tabular}
+\end{center}
+\end{description}
\Subsubsection{Case expressions}{case-expr-overview}
\item
-Foreign Objects are a form of weak pointer which lets Haskell access
-foreign objects.
+Weak pointers and foreign objects provide finalisation support for
+Haskell references to external objects.
\end{itemize}
never to leave less than @MIN_SIZE_SHRUNKEN_STACK@ empty words on the
stack when it does so.
-\ToDo{Would it be useful for the storage manager to enlarge the stack?}
-
\item
For efficiency reasons, very large objects (eg large arrays and TSOs)
\end{itemize}
Most of the RTS is completely insensitive to the number of admin
-words. The total size of the fixed header is @FIXED_HS@.
+words. The total size of the fixed header is given by
+@sizeof(StgHeader)@.
\Subsection{Info Tables}{info-tables}
\hline Parallelism Info & variable
\\ \hline Profile Info & variable
\\ \hline Debug Info & variable
-\\ \hline Static reference table & 32 bits (optional)
-\\ \hline Storage manager layout info & 32 bits
-\\ \hline Closure type & 16 bits
-\\ \hline Constructor Tag & 16 bits
+\\ \hline Static reference table & pointer word (optional)
+\\ \hline Storage manager layout info & pointer word
+\\ \hline Closure flags & 8 bits
+\\ \hline Closure type & 8 bits
+\\ \hline Constructor Tag / SRT length & 16 bits
\\ \hline entry code
\\ \vdots
\end{tabular}
\end{center}
+On a 64-bit machine the tag, type and flags fields will all be doubled
+in size, so the info table is a multiple of 64 bits.
+
An info table has the following contents (working backwards in memory
addresses):
preceded by the rest of the info table. An \emph{info pointer} always
points to the first byte of the entry code.
-\item A 16-bit constructor tag. This field is used for constructor
-info-tables only (\secref{CONSTR}), and contains an integer
-representing the tag value of the constructor, in the range $0..n-1$
-where $n$ is the number of constructors in the datatype.
+\item A 16-bit constructor tag / SRT length. For a constructor info
+table this field contains the tag of the constructor, in the range
+$0..n-1$ where $n$ is the number of constructors in the datatype.
+Otherwise, it contains the number of entries in this closure's Static
+Reference Table (\secref{srt}).
-\item An 16-bit {\em closure type field}, which identifies what kind of
+\item An 8-bit {\em closure type field}, which identifies what kind of
closure the object is. The various types of closure are described in
\secref{closures}.
+\item an 8-bit flags field, which holds various flags pertaining to
+the closure type.
+
\item A single pointer or word --- the {\em storage manager info
field}, contains auxiliary information describing the closure's
precise layout, for the benefit of the garbage collector and the code
field followed by two or more bitmap words. This layout information
is used for @RET_BIG@ and @RET_VEC_BIG@ closures.
-\item Selector Thunks (\secref{THUNK_SEL}) use the closure
+\item Selector Thunks (\secref{THUNK_SELECTOR}) use the closure
layout field to hold the selector index, since the layout is always
known (the closure contains a single pointer field).
\end{itemize}
\item @THUNK_*@
\item @RET_*@
\end{itemize}
-
+
\item \emph{Profiling info\/}
\ToDo{The profiling info is completely bogus. I've not deleted it
There's no need to link the stable pointer table onto the mutable
list because we always treat it as a root.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\Subsection{Garbage Collecting CAFs}{CAF}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% begin{direct quote from current paper}
+A CAF (constant applicative form) is a top-level expression with no
+arguments. The expression may need a large, even unbounded, amount of
+storage when it is fully evaluated.
+
+CAFs are represented by closures in static memory that are updated
+with indirections to objects in the heap space once the expression is
+evaluated. Previous version of GHC maintained a list of all evaluated
+CAFs and traversed them during GC, the result being that the storage
+allocated by a CAF would reside in the heap until the program ended.
+% end{direct quote from current paper}
+
+% begin{elaboration on why CAFs are very very bad}
+Treating CAFs this way has two problems:
+\begin{itemize}
+\item
+It can cause a very large space leak. For example, this program
+should run in constant space but, instead, will run out of memory.
+\begin{verbatim}
+> main :: IO ()
+> main = print nats
+>
+> nats :: [Int]
+> nats = [0..maxInt]
+\end{verbatim}
+
+\item
+Expressions with no arguments have very different space behaviour
+depending on whether or not they occur at the top level. For example,
+if we make \verb+nats+ a local definition, the space leak goes away
+and the resulting program runs in constant space, as expected.
+\begin{verbatim}
+> main :: IO ()
+> main = print nats
+> where
+> nats :: [Int]
+> nats = [0..maxInt]
+\end{verbatim}
+
+This huge change in the operational behaviour of the program
+is a problem for optimising compilers and for programmers.
+For example, GHC will normally flatten a set of let bindings using
+this transformation:
+\begin{verbatim}
+let x1 = let x2 = e2 in e1 ==> let x2 = e2 in let x1 = e1
+\end{verbatim}
+but it does not do so if this would raise \verb+x2+ to the top level
+since that may create a CAF. Many Haskell programmers avoid creating
+large CAFs by adding a dummy argument to a CAF or by moving a CAF away
+from the top level.
+
+\end{itemize}
+% end{elaboration on why CAFs are very very bad}
+
+Solving the CAF problem requires different treatment in interactive
+systems such as Hugs than in batch-mode systems such as GHC
+\begin{itemize}
+\item
+In a batch-mode the program the runtime system is terminated
+after every execution of the runtime system. In such systems,
+the garbage collector can completely ``destroy'' a CAF when it
+is no longer live --- in much the same way as it ``destroys''
+normal closures when they are no longer live.
+
+\item
+In an interactive system, many expressions are evaluated without
+restarting the runtime system between each evaluation. In such
+systems, the garbage collector cannot completely ``destroy'' a CAF
+when it is no longer live because, whilst it might not be required in
+the evaluation of the current expression, it might be required in the
+next evaluation.
+
+There are two possible behaviours we migth want:
+\begin{enumerate}
+\item
+When a CAF is no longer required for the current evaluation, the CAF
+should be reverted to its original form. This behaviour ensures that
+the operational behaviour of the interactive system is a reasonable
+predictor of the operational behaviour of the batch-mode system. This
+allows us to use Hugs for performance debugging (in particular, trying
+to understand and reduce the heap usage of a program) --- an area of
+increasing importance as Haskell is used more and more to solve ``real
+problems'' in ``real problem domains''.
+
+\item
+Even if a CAF is no longer required for the current evaluation, we might
+choose to hang onto it by collecting it in the normal way. This keeps
+the space leak but might be useful in a teaching environment when
+trying to teach the difference between call by name evaluation (which
+doesn't share work) and lazy evaluation (which does share work).
+
+\end{enumerate}
+
+It turns out that it is easy to support both styles of use, so the
+runtime system provides a switch which lets us turn this on and off
+during execution. \ToDo{What is this switch called?} It would also
+be easy to provide a function \verb+RevertCAF+ to let the interpreter
+revert any CAF it wanted between (but not during) executions, if we so
+desired. Running \verb+RevertCAF+ during execution would lose some sharing
+but is otherwise harmless.
+
+\end{itemize}
+
+% % begin{even more pointless observation?}
+% The simplest fix would be to remove the special treatment of
+% top level variables. This works but is very inefficient.
+% ToDo: say why.
+% (Note: delete this paragraph from final version.)
+% % end{even more pointless observation?}
+
+% begin{pointless observation?}
+An easy but inefficient fix to the CAF problem would be to make a
+complete copy of the heap before every evaluation and discard the copy
+after evaluation. This works but is inefficient.
+% end{pointless observation?}
+
+An efficient way to achieve a similar effect is to revert all
+updatable thunks to their original form as they become unnecessary for
+the current evaluation. To do this, we modify the compiler to ensure
+that the only updatable thunks generated by the compiler are CAFs and
+we modify the garbage collector to revert entered CAFs to unentered
+CAFs as their value becomes unnecessary.
+
+
+\subsubsection{New Heap Objects}
+
+We add three new kinds of heap object: unentered CAF closures, entered
+CAF objects and CAF blackholes. We first describe how they are
+evaluated and then how they are garbage collected.
+\begin{itemize}
+\item
+Unentered CAF closures contain a pointer to closure representing the
+body of the CAF. The ``body closure'' is not updatable.
+
+Unentered CAF closures contain two unused fields to make them the same
+size as entered CAF closures --- which allows us to perform an inplace
+update. \ToDo{Do we have to add another kind of inplace update operation
+to the storage manager interface or do we consider this to be internal
+to the SM?}
+\begin{center}
+\begin{tabular}{|l|l|l|l|}\hline
+\verb+CAF_unentered+ & \emph{body closure} & \emph{unused} & \emph{unused} \\ \hline
+\end{tabular}
+\end{center}
+When an unentered CAF is entered, we do the following:
+\begin{itemize}
+\item
+allocate a CAF black hole;
+
+\item
+push an update frame (to update the CAF black hole) onto the stack;
+
+\item
+overwrite the CAF with an entered CAF object (see below) with the same
+body and whose value field points to the black hole;
+
+\item
+add the CAF to a list of all entered CAFs (called ``the CAF list'');
+and
+
+\item
+the closure representing the value of the CAF is entered.
+
+\end{itemize}
+
+When evaluation of the CAF body returns a value, the update frame
+causes the CAF black hole to be updated with the value in the normal
+way.
+
+\ToDo{Add a picture}
+
+\item
+Entered CAF closures contain two pointers: a pointer to the CAF body
+(the same as for unentered CAF closures); a pointer to the CAF value
+(this is initialised with a CAF blackhole, as previously described);
+and a link to the next CAF in the CAF list
+
+\ToDo{How is the end of the list marked? Null pointer or sentinel value?}.
+
+\begin{center}
+\begin{tabular}{|l|l|l|l|}\hline
+\verb+CAF_entered+ & \emph{body closure} & \emph{value} & \emph{link} \\ \hline
+\end{tabular}
+\end{center}
+When an entered CAF is entered, it enters its value closure.
+
+\item
+CAF blackholes are identical to normal blackholes except that they
+have a different infotable. The only reason for having CAF blackholes
+is to allow an optimisation of lazy blackholing where we stop scanning
+the stack when we see the first {\em normal blackhole} but not
+when we see a {\em CAF blackhole.}
+\ToDo{The optimisation we want to allow should be described elsewhere
+so that all we have to do here is describe the difference.}
+
+Instead of allocating a blackhole to update with the value of the CAF,
+it might seem simpler to update the CAF directly. This would require
+a new kind of update frame which would update the value field of the
+CAF with a pointer to the value and wouldn't catch blackholes caused
+by CAFs that depend on themselves so we chose not to do so.
+
+\end{itemize}
+
+\subsubsection{Garbage Collection}
+
+To avoid the space leak, each run of the garbage collector must revert
+the entered CAFs which are not required to complete the current
+evaluation (that is all the closures reachable from the set of
+runnable threads and the stable pointer table).
+
+It does this by performing garbage collection in three phases:
+\begin{enumerate}
+\item
+During the first phase, we ``mark'' all closures reachable from the
+scheduler state.
+
+How we ``mark'' closures depends on the garbage collector. For
+example, in a 2-space collector, closures are ``marked'' by copying
+them into ``to-space'', overwriting them with a forwarding node and
+``marking'' all the closures reachable from the copy. The only
+requirements are that we can test whether a closure is marked and if a
+closure is marked then so are all closures reachable from it.
+
+\ToDo{At present we say that the scheduler state includes any state
+that Hugs may have. This is not true anymore.}
+
+Performing this phase first provides us with a cheap test for
+execution closures: at this stage in execution, the execution closures
+are precisely the marked closures.
+
+\item
+During the second phase, we revert all unmarked CAFs on the CAF list
+and remove them from the CAF list.
+
+Since the CAF list is exactly the set of all entered CAFs, this reverts
+all entered CAFs which are not execution closures.
+
+\item
+During the third phase, we mark all top level objects (including CAFs)
+by calling \verb+MarkHugsRoots+ which will call \verb+MarkRoot+ for
+each top level object known to Hugs.
+
+\end{enumerate}
+
+To implement the second style of interactive behaviour (where we
+deliberately keep the CAF-related space leak), we simply omit the
+second phase. Omitting the second phase causes the third phase to
+mark any unmarked CAF value closures.
+
+So far, we have been describing a pure Hugs system which contains no
+machine generated code. The main difference in a hybrid system is
+that GHC-generated code is statically allocated in memory instead of
+being dynamically allocated on the heap. We split both
+\verb+CAF_unentered+ and \verb+CAF_entered+ into two versions: a
+static and a dynamic version. The static and dynamic versions of each
+CAF differ only in whether they are moved during garbage collection.
+When reverting CAFs, we revert dynamic entered CAFs to dynamic
+unentered CAFs and static entered CAFs to static unentered CAFs.
+
+
\Section{The Bytecode Evaluator}{bytecode-evaluator}
projects / ghc-hetmet.git / blobdiff