%************************************************************************ %* * \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, , (_FHS+2)); /* Heap full. Call "PerformGC" with 2 arguments, "", (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{}, 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{} 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{}, 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}