diff options
Diffstat (limited to 'ghc/includes/SMinterface.lh')
| -rw-r--r-- | ghc/includes/SMinterface.lh | 537 |
1 files changed, 537 insertions, 0 deletions
diff --git a/ghc/includes/SMinterface.lh b/ghc/includes/SMinterface.lh new file mode 100644 index 0000000000..0622d4decf --- /dev/null +++ b/ghc/includes/SMinterface.lh @@ -0,0 +1,537 @@ +%************************************************************************ +%* * +\section[SMinterface.lh]{Main storage manager interface} +%* * +%************************************************************************ + +%% I have changed most of the text here, in an attempt to understand +%% what's going on. Please let me know about any mistakes, so that +%% I can correct them! KH@15/10/92 (UK) + +%% I have also split the original monster into SMinterface.lh, +%% SMClosures.lh and SMInfoTables.lh. The latter two are +%% included below. + +This describes the interface used between the STG-machine +reducer and the storage manager. The overriding goal is to isolate +the implementation details of each from the other. + +Multi-slurp protection: +\begin{code} +#ifndef SMinterface_H +#define SMinterface_H +\end{code} + +\begin{rawlatex} +{}\input{epsf} % Uses encapsulated PostScript diagrams +\end{rawlatex} + +%************************************************************************ +%* * +\subsection[SM-calling-interface]{Calling interface} +%* * +%************************************************************************ + +The @smInfo@ structure is used to pass all information back and forth +between the storage manager and the STG world. + +WARNING: If you modify this structure, you {\em must} modify the +native-code generator as well, because the offsets for various fields +are hard-coded into the NCG. (In nativeGen/StixMacro.lhs). + +\begin{code} +typedef struct { + P_ hp; /* last successfully allocated word */ + P_ hplim; /* last allocatable word */ + + I_ rootno; /* No of heap roots stored in roots */ + P_ *roots; /* Array of heap roots -- must be allocated (not static) */ + P_ CAFlist; /* List of updated CAF's */ + +#if defined(GCap) || defined(GCgn) + P_ OldMutables; /* List of old generation mutable closures */ + P_ OldLim; /* Ptr to end of the old generation */ +#endif + +#ifndef PAR + P_ MallocPtrList; /* List of all Malloc Pointers (in new generation) */ + +#if defined(GCap) || defined(GCgn) + P_ OldMallocPtrList; /* List of all Malloc Pointers in old generation */ +#endif + + P_ StablePointerTable; + /* Heap allocated table used to store stable pointers in */ +#endif /* !PAR */ + + I_ hardHpOverflowSize; /* Some slop at the top of the heap which + (hopefully) provides enough space to let + us recover from heap overflow exceptions */ +} smInfo; + +extern smInfo StorageMgrInfo; + +\end{code} + +Maximum number of roots storable in the heap roots array. +Question: Where are the stable pointer roots? (JSM) +Answer: They're on the heap in a "Stable Pointer Table". (ADR) +\begin{code} +#ifndef CONCURRENT +# define SM_MAXROOTS 8 /* 8 Vanilla Regs */ +#else +# ifndef PAR +# ifdef GRAN +# define SM_MAXROOTS (10 + (MAX_PROC*4) + 2 + (MAX_PROC*2) + MAX_SPARKS) + /* unthreaded + spark/thread queues + Current/Main TSOs + + events + sparks */ +# else +# define SM_MAXROOTS 5 /* See c-as-asm/HpOverflow.lc */ +# endif +# else +# define SM_MAXROOTS 6 /* See c-as-asm/HpOverflow.lc */ +# endif +#endif +\end{code} + +The storage manager is accessed exclusively through these routines: +\begin{code} +IF_RTS(I_ initSM PROTO((I_ rts_argc, char **rts_argv, FILE *statsfile));) +IF_RTS(I_ exitSM PROTO((smInfo *sm));) +IF_RTS(I_ initStacks PROTO((smInfo *sm));) +IF_RTS(I_ initHeap PROTO((smInfo *sm));) +#ifdef CONCURRENT +IF_RTS(rtsBool initThreadPool PROTO((I_ size));) +#endif +#ifdef PAR +IF_RTS(void init_gr_profiling PROTO((int, char **, int, char **));) +#endif + +I_ collectHeap PROTO((W_ reqsize, smInfo *sm, rtsBool do_full_collection)); + +IF_RTS(void unmapMiddleStackPage PROTO((char *, int));) /* char * == caddr_t ? */ + +#if defined(USE_COST_CENTRES) || defined(GUM) +IF_RTS(void handle_tick_serial(STG_NO_ARGS);) +IF_RTS(void handle_tick_noserial(STG_NO_ARGS);) +#endif + +/* EXTFUN(_startMarkWorld); */ + +StgDouble usertime(STG_NO_ARGS); +StgDouble elapsedtime(STG_NO_ARGS); +void start_time(STG_NO_ARGS); +void end_init(STG_NO_ARGS); + +#ifdef PAR +void EvacuateLocalGAs PROTO((rtsBool full)); +void RebuildGAtables PROTO((rtsBool full)); +#endif + +\end{code} + +@initSM@ processes any runtime parameters directed towards the storage +manager. The @statsfile@ parameter is an open file, which will contain +any garbage collection statistics requested by the user. This file +must be opened for writing. + +@exitSM@ does any cleaning up required by the storage manager before +the program is executed. Its main purpose is to print any summary +statistics. + +@initStacks@ allocates the A and B stacks (sequential only). It +initialises the @spa@, @spb@, @sua@, and @sub@ fields of @sm@ +appropriately for empty stacks. Successive calls to @initStacks@ +re-initialise the stacks. + +@initHeap@ allocates the heap. It initialises the @hp@ and @hplim@ +fields of @sm@ to represent an empty heap for the compiled-in garbage +collector. It also allocates the @roots@ array for later use within +@collectHeap@, and initialises @CAFlist@ to be the empty list. The +@roots@ array must be large enough to hold at least @SM_MAXROOTS@ +roots. If we are using Appel's collector it also initialises the +@OldLim@ field. + +In the sequential system, it also initialises the stable pointer table +and the @MallocPtr@ (and @OldMallocPtrList@) fields. + +@collectHeap@ invokes the garbage collector that was requested at +compile time. @reqsize@ is the size of the request (in words) that +resulted in the overflow. If the garbage collection succeeds, then at +least @reqsize@ words will be available. @collectHeap@ requires all +the fields of @sm@ to be initialised appropriately (from the +STG-machine registers). The following are identified as +heap roots: +\begin{itemize} +\item The @roots@ array. +\item The updated CAFs recorded in @CAFlist@. +\item A Stack. +\item Update frames on the B Stack. These may be ``squeezed'' out +if they are the only reference to a closure --- thus avoiding the +update. +\item The stable pointer table. (In sequential system.) +\end{itemize} + +There are three possible results from a garbage collection: +\begin{description} +\item[\tr{GC_HARD_LIMIT_EXCEEDED} (\tr{reqsize > hplim - hp})] +The heap size exceeds the hard heap limit: we report an error and +exit. + +\item[\tr{GC_SOFT_LIMIT_EXCEEDED} (\tr{reqsize + hardHpOverflowSize > hplim - hp})] +The heap size exceeds the soft heap limit: set \tr{hardHpOverflowSize} +to \tr{0} so that we can use the overflow space, unwind the stack and +call an appropriate piece of Haskell to handle the error. + +\item[\tr{GC_SUCCESS} (\tr{reqsize + hardHpOverflowSize <= hplim - hp})] +The heap size is less than the soft heap limit. + +\begin{itemize} +\item @hp@ and @hplim@ will indicate the new space available for +allocation. But we'll subtract \tr{hardHpOverflowSize} from +\tr{hplim} so that we'll GC when we hit the soft limit. + +\item The elements of the @roots@ array will point to the new +locations of the closures. + +\item @spb@ and @sub@ will be updated to reflect the new state of the +B stack arising from any update frame ``squeezing'' [sequential only]. + +\item The elements of @CAFlist@ and the stable pointers will be +updated to point to the new locations of the closures they reference. + +\item Any members of @MallocPtrList@ which became garbage should have +been reported (by calling @FreeMallocPtr@; and the @(Old)MallocPtrList@ +updated to contain only those Malloc Pointers which are still live. +\end{itemize} + +\end{description} + +\begin{code} +#define GC_HARD_LIMIT_EXCEEDED 0 +#define GC_SOFT_LIMIT_EXCEEDED 1 +#define GC_SUCCESS 2 +\end{code} + +%************************************************************************ +%* * +\subsection[SM-what-really-happens]{``What really happens in a garbage collection?''} +%* * +%************************************************************************ + +This is a brief tutorial on ``what really happens'' going to/from the +storage manager in a garbage collection. + +\begin{description} +%------------------------------------------------------------------------ +\item[The heap check:] + +[OLD-ISH: WDP] + +If you gaze into the C output of GHC, you see many macros calls like: +\begin{verbatim} +HEAP_CHK_2PtrsLive((_FHS+2)); +\end{verbatim} + +This expands into the C (roughly speaking...): +\begin{verbatim} +Hp = Hp + (_FHS+2); /* optimistically move heap pointer forward */ + +GC_WHILE_OR_IF (HEAP_OVERFLOW_OP(Hp, HpLim) OR_INTERVAL_EXPIRED) { + STGCALL2_GC(PerformGC, <liveness-bits>, (_FHS+2)); + /* Heap full. Call "PerformGC" with 2 arguments, "<liveness>", + (info about what ptrs are live) and "_FHS+2" (words + requested), via the magical routine "callWrapper_GC", + which indicates ``I am calling a routine in which GC + may happen'' (a safe bet for `PerformGC'). + */ +} +\end{verbatim} + +In the parallel world, where we will need to re-try the heap check, +@GC_WHILE_OR_IF@ will be a ``while''; in the sequential world, it will +be an ``if''. + +The ``heap lookahead'' checks, which are similar and used for +multi-precision @Integer@ ops, have some further complications. See +the commentary there (\tr{StgMacros.lh}). + +%------------------------------------------------------------------------ +\item[Into @callWrapper_GC@...:] + +When we failed the heap check (above), we were inside the +GCC-registerised ``threaded world.'' @callWrapper_GC@ is all about +getting in and out of the threaded world. On SPARCs, with register +windows, the name of the game is not shifting windows until we have +what we want out of the old one. In tricky cases like this, it's best +written in assembly language. + +Though the principle of ``save everything away'' is the same in both +the sequential and parallel worlds, the details are different. + +For the sequential world: +\begin{enumerate} +\item +@callWrapper_GC@ saves the return address. +\item +It saves the arguments passed to it (so it doesn't get lost). +\item +Save the machine registers used in the STG threaded world in their +\tr{*_SAVE} global-variable backup locations. E.g., register \tr{Hp} +is saved into \tr{Hp_SAVE}. +\item +Call the routine it was asked to call; in this example, call +@PerformGC@ with arguments \tr{<liveness>}, and @_FHS+2@ (some constant)... +\end{enumerate} + +For the parallel world, a GC means giving up the thread of control. +So we must fill in the thread-state-object (TSO) [and its associated +stk object] with enough information for later resumption: +\begin{enumerate} +\item +Save the return address in the TSO's PC field. +\item +Save the machine registers used in the STG threaded world in their +corresponding TSO fields. We also save the pointer-liveness +information in the TSO. +\item +The registers that are not thread-specific, notably \tr{Hp} and +\tr{HpLim}, are saved in the @StorageMgrInfo@ structure. +\item +Call the routine it was asked to call; in this example, call +@PerformGC@ with arguments \tr{<liveness>} and @_FHS+2@ (some constant)... + +(In the parallel world, we don't expect it to return...) +\end{enumerate} + +%------------------------------------------------------------------------ +\item[Into the heap overflow wrapper, @PerformGC@ [sequential]:] + +The first argument (\tr{<liveness>}, in our example) say what registers +are live, i.e., are ``roots'' the storage manager needs to know. +\begin{verbatim} +StorageMgrInfo.rootno = 2; +StorageMgrInfo.roots[0] = (P_) Ret1_SAVE; +StorageMgrInfo.roots[1] = (P_) Ret2_SAVE; +\end{verbatim} + +We further: (a)~move the heap-pointer back [we had optimistically +advanced it, in the initial heap check], (b)~load up the @smInfo@ data +from the STG registers' \tr{*_SAVE} locations, and (c)~FINALLY: call +@collectHeap@. + +IT IS AT THIS POINT THAT THE WORLD IS COMPLETELY TIDY. + +%------------------------------------------------------------------------ +\item[Into the heap overflow wrapper, @PerformGC@ [parallel]:] + +Parallel execution is only slightly different. Most information has +already been saved in the TSO. + +\begin{enumerate} +\item +We still need to set up the storage manager's @roots@ array. +\item +We mark on the scheduler's big ``blackboard'' that a GC is +required. +\item +We reschedule, i.e., this thread gives up control. (The scheduler +will presumably initiate a garbage-collection, but it may have to do +any number of other things---flushing, for example---before ``normal +execution'' resumes; and it most certainly may not be this thread that +resumes at that point!) +\end{enumerate} + +%------------------------------------------------------------------------ +\item[Into/out of @collectHeap@ [sequential only]:] + +@collectHeap@ does the business and reports back whether it freed up +enough space. + +%------------------------------------------------------------------------ +\item[Out of the heap overflow wrapper, @PerformGC@ [sequential only]:] + +We begin our return back to doing useful work by: (a)~reloading the +appropriate STG-register \tr{*_SAVE} locations from (presumably +changed) @smInfo@; (b) re-advance the heap-pointer---which we've been +trying to do for a week or two---now that there is enough space. + +We must further restore appropriate @Ret?@ registers from the storage +manager's roots array; in this example: + +\begin{verbatim} +Ret1_SAVE = (W_) StorageMgrInfo.roots[0]; +Ret2_SAVE = (W_) StorageMgrInfo.roots[1]; +\end{verbatim} + +%------------------------------------------------------------------------ +\item[Out of @callWrapper_GC@ [sequential]:] + +We pop out of heap-overflow code and are ready to resume STG +``threaded world'' stuff. + +The main thing is to re-load up the GCC-ised machine registers from +the relevant \tr{*_SAVE} locations; e.g., \tr{SpA} from \tr{SpA_SAVE}. + +To conclude, @callWrapper_GC@ merely {\em jumps} back to the return +address which it was given originally. + +WE'RE BACK IN (SEQUENTIAL) BUSINESS. + +%------------------------------------------------------------------------ +\item[Out of @callWrapper_GC@ [parallel]:] + +When this thread is finally resumed after GC (and who knows what +else), it will restart by the normal enter-TSO/enter-stack-object +sequence, which has the effect of re-loading the registers, etc., +(i.e., restoring the state). + +Because the address we saved in the TSO's PC field was that at the end +of the heap check, and because the check is a while-loop in the +parallel system, we will now loop back around, and make sure there is +enough space before continuing. +\end{description} + +%************************************************************************ +%* * +\subsection[SM-stack-info]{Stacks} +%* * +%************************************************************************ + +There are two stacks, as in the STG paper \cite{new-stg-paper}. +\begin{itemize} +\item +The A stack contains only closure pointers. +\item +The B stack contains, basic values, return addresses, and update +frames. +\end{itemize} +The A stack and B stack grow towards each other, so they overflow when +they collide. Currently the A stack grows downward (towards lower +addresses); the B stack grows upward. (We localise the stuff which +uses this information within macros defined in @StgDirections.h@) + +During reduction, SpA and SpB point to the topmost allocated word of +the corresponding stack (though they may not be up to date in the +middle of a basic block). + +Each stack also has a {\em stack update pointer}, SuA and SuB, which +point to the topmost word of the most recent update frame in the +corresponding stack. (Colloquially, SuA and Sub point to the first +items on their respective stacks ``that you cannot have.'') +\begin{rawlatex} +A standard update frame (on the B stack) looks like this +(stack grows downward in this picture): +\begin{center} +\mbox{\epsffile{update-frame.ps}} +\end{center} +The SuB therefore points to the Update return vector component of +the topmost update frame. +\end{rawlatex} + +A {\em constructor} update frame, which is pushed only by closures +which know they will evaluate to a data object, looks just the +same, but without the saved SuA pointer. + +We store the following information concerning the stacks in a global +structure. (sequential only). +\begin{code} + +typedef struct { + PP_ botA; /* Points to bottom-most word of A stack */ + P_ botB; /* Points to bottom-most word of B stack */ +} stackData; + +extern stackData stackInfo; +\end{code} + +%************************************************************************ +%* * +\subsection[SM-choose-flavour]{Deciding which GC flavour is in force...} +%* * +%************************************************************************ + +Each garbage collector requires different garbage collection entries +in the info-table. + +\begin{code} +#if defined(GC2s) +#define _INFO_COPYING + +#else +#if defined(GC1s) +#define _INFO_COMPACTING +#define _INFO_MARKING + +#else +#if defined(GCdu) || defined (GCap) || defined (GCgn) +#define _INFO_COPYING +#define _INFO_COMPACTING +#define _INFO_MARKING + +#else +/* NO_INFO_SPECIFIED (ToDo: an #error ???) */ +#endif +#endif +#endif +\end{code} + +%************************************************************************ +%* * +%\subsection[Info.lh]{Info Pointer Definitions} +%* * +%************************************************************************ + +\downsection +\input{Info.lh} +\upsection + +%************************************************************************ +%* * +%\subsection[Parallel.lh]{Parallel Machine Definitions} +%* * +%************************************************************************ + +\downsection +\input{Parallel.lh} +\upsection + + +%************************************************************************ +%* * +%\subsection[CostCentre.lh]{Profiling Definitions} +%* * +%************************************************************************ + +\downsection +\input{CostCentre.lh} +\upsection + + +%************************************************************************ +%* * +%\subsection[SM-closures]{Closure-Related Definitions} +%* * +%************************************************************************ + +\downsection +\input{SMClosures.lh} +\upsection + + + +%************************************************************************ +%* * +%\subsection[SM-info-tables]{Info-table Related Definitions} +%* * +%************************************************************************ + +\downsection +\input{SMInfoTables.lh} +\upsection + + +End multi-slurp protection: +\begin{code} +#endif /* SMinterface_H */ +\end{code} |