ghc/includes/SMinterface.lh

   1 %************************************************************************
   2 %*                                                                      *
   3 \section[SMinterface.lh]{Main storage manager interface}
   4 %*                                                                      *
   5 %************************************************************************
   6
   7 %%  I have changed most of the text here, in an attempt to understand
   8 %%  what's going on.  Please let me know about any mistakes, so that
   9 %%  I can correct them!  KH@15/10/92 (UK)
  10
  11 %%  I have also split the original monster into SMinterface.lh,
  12 %%  SMClosures.lh and SMInfoTables.lh.  The latter two are
  13 %%  included below.
  14
  15 This describes the interface used between the STG-machine
  16 reducer and the storage manager. The overriding goal is to isolate
  17 the implementation details of each from the other.
  18
  19 Multi-slurp protection:
  20 \begin{code}
  21 #ifndef SMinterface_H
  22 #define SMinterface_H
  23 \end{code}
  24
  25 \begin{rawlatex}
  26 {}\input{epsf} % Uses encapsulated PostScript diagrams
  27 \end{rawlatex}
  28
  29 %************************************************************************
  30 %*                                                                      *
  31 \subsection[SM-calling-interface]{Calling interface}
  32 %*                                                                      *
  33 %************************************************************************
  34
  35 The @smInfo@ structure is used to pass all information back and forth
  36 between the storage manager and the STG world.
  37
  38 WARNING: If you modify this structure, you {\em must} modify the
  39 native-code generator as well, because the offsets for various fields
  40 are hard-coded into the NCG. (In nativeGen/StixMacro.lhs).
  41
  42 \begin{code}
  43 typedef struct {
  44     P_ hp;      /* last successfully allocated word */
  45     P_ hplim;   /* last allocatable word */
  46
  47     I_ rootno; /* No of heap roots stored in roots */
  48     P_ *roots;  /* Array of heap roots -- must be allocated (not static) */
  49     P_ CAFlist; /* List of updated CAF's */
  50
  51 #if defined(GCap) || defined(GCgn)
  52     P_ OldMutables; /* List of old generation mutable closures */
  53     P_ OldLim;      /* Ptr to end of the old generation */
  54 #endif
  55
  56 #ifndef PAR
  57     P_ MallocPtrList;     /* List of all Malloc Pointers (in new generation) */
  58
  59 #if defined(GCap) || defined(GCgn)
  60     P_ OldMallocPtrList;  /* List of all Malloc Pointers in old generation */
  61 #endif
  62
  63     P_ StablePointerTable;
  64         /* Heap allocated table used to store stable pointers in */
  65 #endif /* !PAR */
  66
  67     I_ hardHpOverflowSize;  /* Some slop at the top of the heap which
  68                                (hopefully) provides enough space to let
  69                                us recover from heap overflow exceptions */
  70 } smInfo;
  71
  72 extern smInfo StorageMgrInfo;
  73
  74 \end{code}
  75
  76 Maximum number of roots storable in the heap roots array.
  77 Question: Where are the stable pointer roots? (JSM)
  78 Answer: They're on the heap in a "Stable Pointer Table". (ADR)
  79 \begin{code}
  80 #ifndef CONCURRENT
  81 # define SM_MAXROOTS 8          /* 8 Vanilla Regs */
  82 #else
  83 # ifndef PAR
  84 #   ifdef GRAN
  85 #    define SM_MAXROOTS (10 + (MAX_PROC*4) + 2 + (MAX_PROC*2) + MAX_SPARKS)
  86                                 /* unthreaded + spark/thread queues + Current/Main TSOs
  87                                    + events + sparks */
  88 #   else
  89 #     define SM_MAXROOTS 5      /* See c-as-asm/HpOverflow.lc */
  90 #   endif
  91 # else
  92 #  define SM_MAXROOTS 6         /* See c-as-asm/HpOverflow.lc */
  93 # endif
  94 #endif
  95 \end{code}
  96
  97 The storage manager is accessed exclusively through these routines:
  98 \begin{code}
  99 IF_RTS(void    initSM       (STG_NO_ARGS);)
 100 IF_RTS(rtsBool exitSM       PROTO((smInfo *sm));)
 101 IF_RTS(rtsBool initStacks   PROTO((smInfo *sm));)
 102 IF_RTS(rtsBool initHeap     PROTO((smInfo *sm));)
 103 #ifdef CONCURRENT
 104 IF_RTS(rtsBool initThreadPools (STG_NO_ARGS);)
 105 #endif
 106 #ifdef PAR
 107 IF_RTS(void init_gr_profiling PROTO((int, char **, int, char **));)
 108 #endif
 109
 110 I_ collectHeap      PROTO((W_ reqsize, smInfo *sm, rtsBool do_full_collection));
 111
 112 IF_RTS(void unmapMiddleStackPage PROTO((char *, int));) /* char * == caddr_t ? */
 113
 114 #if defined(PROFILING) || defined(PAR)
 115 IF_RTS(void handle_tick_serial(STG_NO_ARGS);)
 116 IF_RTS(void handle_tick_noserial(STG_NO_ARGS);)
 117 #endif
 118
 119 /* EXTFUN(_startMarkWorld); */
 120
 121 StgDouble usertime(STG_NO_ARGS);
 122 StgDouble elapsedtime(STG_NO_ARGS);
 123 void      start_time(STG_NO_ARGS);
 124 void      end_init(STG_NO_ARGS);
 125
 126 #ifdef PAR
 127 void EvacuateLocalGAs PROTO((rtsBool full));
 128 void RebuildGAtables PROTO((rtsBool full));
 129 #endif
 130
 131 \end{code}
 132
 133 @initSM@ finalizes any runtime parameters of the storage manager.
 134
 135 @exitSM@ does any cleaning up required by the storage manager before
 136 the program is executed. Its main purpose is to print any summary
 137 statistics.
 138
 139 @initStacks@ allocates the A and B stacks (sequential only). It
 140 initialises the @spa@, @spb@, @sua@, and @sub@ fields of @sm@
 141 appropriately for empty stacks.  Successive calls to @initStacks@
 142 re-initialise the stacks.
 143
 144 @initHeap@ allocates the heap. It initialises the @hp@ and @hplim@
 145 fields of @sm@ to represent an empty heap for the compiled-in garbage
 146 collector.  It also allocates the @roots@ array for later use within
 147 @collectHeap@, and initialises @CAFlist@ to be the empty list.  The
 148 @roots@ array must be large enough to hold at least @SM_MAXROOTS@
 149 roots.  If we are using Appel's collector it also initialises the
 150 @OldLim@ field.
 151
 152 In the sequential system, it also initialises the stable pointer table
 153 and the @MallocPtr@ (and @OldMallocPtrList@) fields.
 154
 155 @collectHeap@ invokes the garbage collector that was requested at
 156 compile time. @reqsize@ is the size of the request (in words) that
 157 resulted in the overflow. If the garbage collection succeeds, then at
 158 least @reqsize@ words will be available. @collectHeap@ requires all
 159 the fields of @sm@ to be initialised appropriately (from the
 160 STG-machine registers).  The following are identified as
 161 heap roots:
 162 \begin{itemize}
 163 \item The @roots@ array.
 164 \item The updated CAFs recorded in @CAFlist@.
 165 \item A Stack.
 166 \item Update frames on the B Stack. These may be ``squeezed'' out
 167 if they are the only reference to a closure --- thus avoiding the
 168 update.
 169 \item The stable pointer table. (In sequential system.)
 170 \end{itemize}
 171
 172 There are three possible results from a garbage collection:
 173 \begin{description}
 174 \item[\tr{GC_HARD_LIMIT_EXCEEDED} (\tr{reqsize > hplim - hp})]
 175 The heap size exceeds the hard heap limit: we report an error and
 176 exit.
 177
 178 \item[\tr{GC_SOFT_LIMIT_EXCEEDED} (\tr{reqsize + hardHpOverflowSize > hplim - hp})]
 179 The heap size exceeds the soft heap limit: set \tr{hardHpOverflowSize}
 180 to \tr{0} so that we can use the overflow space, unwind the stack and
 181 call an appropriate piece of Haskell to handle the error.
 182
 183 \item[\tr{GC_SUCCESS} (\tr{reqsize + hardHpOverflowSize <= hplim - hp})]
 184 The heap size is less than the soft heap limit.
 185
 186 \begin{itemize}
 187 \item @hp@ and @hplim@ will indicate the new space available for
 188 allocation.  But we'll subtract \tr{hardHpOverflowSize} from
 189 \tr{hplim} so that we'll GC when we hit the soft limit.
 190
 191 \item The elements of the @roots@ array will point to the new
 192 locations of the closures.
 193
 194 \item @spb@ and @sub@ will be updated to reflect the new state of the
 195 B stack arising from any update frame ``squeezing'' [sequential only].
 196
 197 \item The elements of @CAFlist@ and the stable pointers will be
 198 updated to point to the new locations of the closures they reference.
 199
 200 \item Any members of @MallocPtrList@ which became garbage should have
 201 been reported (by calling @FreeMallocPtr@; and the @(Old)MallocPtrList@
 202 updated to contain only those Malloc Pointers which are still live.
 203 \end{itemize}
 204
 205 \end{description}
 206
 207 \begin{code}
 208 #define GC_HARD_LIMIT_EXCEEDED 0
 209 #define GC_SOFT_LIMIT_EXCEEDED 1
 210 #define GC_SUCCESS 2
 211 \end{code}
 212
 213 %************************************************************************
 214 %*                                                                      *
 215 \subsection[SM-what-really-happens]{``What really happens in a garbage collection?''}
 216 %*                                                                      *
 217 %************************************************************************
 218
 219 This is a brief tutorial on ``what really happens'' going to/from the
 220 storage manager in a garbage collection.
 221
 222 \begin{description}
 223 %------------------------------------------------------------------------
 224 \item[The heap check:]
 225
 226 [OLD-ISH: WDP]
 227
 228 If you gaze into the C output of GHC, you see many macros calls like:
 229 \begin{verbatim}
 230 HEAP_CHK_2PtrsLive((_FHS+2));
 231 \end{verbatim}
 232
 233 This expands into the C (roughly speaking...):
 234 \begin{verbatim}
 235 Hp = Hp + (_FHS+2);     /* optimistically move heap pointer forward */
 236
 237 GC_WHILE_OR_IF (HEAP_OVERFLOW_OP(Hp, HpLim) OR_INTERVAL_EXPIRED) {
 238         STGCALL2_GC(PerformGC, <liveness-bits>, (_FHS+2));
 239         /* Heap full.  Call "PerformGC" with 2 arguments, "<liveness>",
 240            (info about what ptrs are live) and "_FHS+2" (words
 241            requested), via the magical routine "callWrapper_GC",
 242            which indicates ``I am calling a routine in which GC
 243            may happen'' (a safe bet for `PerformGC').
 244         */
 245 }
 246 \end{verbatim}
 247
 248 In the parallel world, where we will need to re-try the heap check,
 249 @GC_WHILE_OR_IF@ will be a ``while''; in the sequential world, it will
 250 be an ``if''.
 251
 252 The ``heap lookahead'' checks, which are similar and used for
 253 multi-precision @Integer@ ops, have some further complications.  See
 254 the commentary there (\tr{StgMacros.lh}).
 255
 256 %------------------------------------------------------------------------
 257 \item[Into @callWrapper_GC@...:]
 258
 259 When we failed the heap check (above), we were inside the
 260 GCC-registerised ``threaded world.''  @callWrapper_GC@ is all about
 261 getting in and out of the threaded world.  On SPARCs, with register
 262 windows, the name of the game is not shifting windows until we have
 263 what we want out of the old one.  In tricky cases like this, it's best
 264 written in assembly language.
 265
 266 Though the principle of ``save everything away'' is the same in both
 267 the sequential and parallel worlds, the details are different.
 268
 269 For the sequential world:
 270 \begin{enumerate}
 271 \item
 272 @callWrapper_GC@ saves the return address.
 273 \item
 274 It saves the arguments passed to it (so it doesn't get lost).
 275 \item
 276 Save the machine registers used in the STG threaded world in their
 277 \tr{*_SAVE} global-variable backup locations.  E.g., register \tr{Hp}
 278 is saved into \tr{Hp_SAVE}.
 279 \item
 280 Call the routine it was asked to call; in this example, call
 281 @PerformGC@ with arguments \tr{<liveness>}, and @_FHS+2@ (some constant)...
 282 \end{enumerate}
 283
 284 For the parallel world, a GC means giving up the thread of control.
 285 So we must fill in the thread-state-object (TSO) [and its associated
 286 stk object] with enough information for later resumption:
 287 \begin{enumerate}
 288 \item
 289 Save the return address in the TSO's PC field.
 290 \item
 291 Save the machine registers used in the STG threaded world in their
 292 corresponding TSO fields.  We also save the pointer-liveness
 293 information in the TSO.
 294 \item
 295 The registers that are not thread-specific, notably \tr{Hp} and
 296 \tr{HpLim}, are saved in the @StorageMgrInfo@ structure.
 297 \item
 298 Call the routine it was asked to call; in this example, call
 299 @PerformGC@ with arguments \tr{<liveness>} and @_FHS+2@ (some constant)...
 300
 301 (In the parallel world, we don't expect it to return...)
 302 \end{enumerate}
 303
 304 %------------------------------------------------------------------------
 305 \item[Into the heap overflow wrapper, @PerformGC@ [sequential]:]
 306
 307 The first argument (\tr{<liveness>}, in our example) say what registers
 308 are live, i.e., are ``roots'' the storage manager needs to know.
 309 \begin{verbatim}
 310 StorageMgrInfo.rootno   = 2;
 311 StorageMgrInfo.roots[0] = (P_) Ret1_SAVE;
 312 StorageMgrInfo.roots[1] = (P_) Ret2_SAVE;
 313 \end{verbatim}
 314
 315 We further: (a)~move the heap-pointer back [we had optimistically
 316 advanced it, in the initial heap check], (b)~load up the @smInfo@ data
 317 from the STG registers' \tr{*_SAVE} locations, and (c)~FINALLY: call
 318 @collectHeap@.
 319
 320 IT IS AT THIS POINT THAT THE WORLD IS COMPLETELY TIDY.
 321
 322 %------------------------------------------------------------------------
 323 \item[Into the heap overflow wrapper, @PerformGC@ [parallel]:]
 324
 325 Parallel execution is only slightly different.  Most information has
 326 already been saved in the TSO.
 327
 328 \begin{enumerate}
 329 \item
 330 We still need to set up the storage manager's @roots@ array.
 331 \item
 332 We mark on the scheduler's big ``blackboard'' that a GC is
 333 required.
 334 \item
 335 We reschedule, i.e., this thread gives up control.  (The scheduler
 336 will presumably initiate a garbage-collection, but it may have to do
 337 any number of other things---flushing, for example---before ``normal
 338 execution'' resumes; and it most certainly may not be this thread that
 339 resumes at that point!)
 340 \end{enumerate}
 341
 342 %------------------------------------------------------------------------
 343 \item[Into/out of @collectHeap@ [sequential only]:]
 344
 345 @collectHeap@ does the business and reports back whether it freed up
 346 enough space.
 347
 348 %------------------------------------------------------------------------
 349 \item[Out of the heap overflow wrapper, @PerformGC@ [sequential only]:]
 350
 351 We begin our return back to doing useful work by: (a)~reloading the
 352 appropriate STG-register \tr{*_SAVE} locations from (presumably
 353 changed) @smInfo@; (b) re-advance the heap-pointer---which we've been
 354 trying to do for a week or two---now that there is enough space.
 355
 356 We must further restore appropriate @Ret?@ registers from the storage
 357 manager's roots array; in this example:
 358
 359 \begin{verbatim}
 360 Ret1_SAVE = (W_) StorageMgrInfo.roots[0];
 361 Ret2_SAVE = (W_) StorageMgrInfo.roots[1];
 362 \end{verbatim}
 363
 364 %------------------------------------------------------------------------
 365 \item[Out of @callWrapper_GC@ [sequential]:]
 366
 367 We pop out of heap-overflow code and are ready to resume STG
 368 ``threaded world'' stuff.
 369
 370 The main thing is to re-load up the GCC-ised machine registers from
 371 the relevant \tr{*_SAVE} locations; e.g., \tr{SpA} from \tr{SpA_SAVE}.
 372
 373 To conclude, @callWrapper_GC@ merely {\em jumps} back to the return
 374 address which it was given originally.
 375
 376 WE'RE BACK IN (SEQUENTIAL) BUSINESS.
 377
 378 %------------------------------------------------------------------------
 379 \item[Out of @callWrapper_GC@ [parallel]:]
 380
 381 When this thread is finally resumed after GC (and who knows what
 382 else), it will restart by the normal enter-TSO/enter-stack-object
 383 sequence, which has the effect of re-loading the registers, etc.,
 384 (i.e., restoring the state).
 385
 386 Because the address we saved in the TSO's PC field was that at the end
 387 of the heap check, and because the check is a while-loop in the
 388 parallel system, we will now loop back around, and make sure there is
 389 enough space before continuing.
 390 \end{description}
 391
 392 %************************************************************************
 393 %*                                                                      *
 394 \subsection[SM-stack-info]{Stacks}
 395 %*                                                                      *
 396 %************************************************************************
 397
 398 There are two stacks, as in the STG paper \cite{new-stg-paper}.
 399 \begin{itemize}
 400 \item
 401 The A stack contains only closure pointers.
 402 \item
 403 The B stack contains, basic values, return addresses, and update
 404 frames.
 405 \end{itemize}
 406 The A stack and B stack grow towards each other, so they overflow when
 407 they collide. Currently the A stack grows downward (towards lower
 408 addresses); the B stack grows upward.  (We localise the stuff which
 409 uses this information within macros defined in @StgDirections.h@)
 410
 411 During reduction, SpA and SpB point to the topmost allocated word of
 412 the corresponding stack (though they may not be up to date in the
 413 middle of a basic block).
 414
 415 Each stack also has a {\em stack update pointer}, SuA and SuB, which
 416 point to the topmost word of the most recent update frame in the
 417 corresponding stack.  (Colloquially, SuA and Sub point to the first
 418 items on their respective stacks ``that you cannot have.'')
 419 \begin{rawlatex}
 420 A standard update frame (on the B stack) looks like this
 421 (stack grows downward in this picture):
 422 \begin{center}
 423 \mbox{\epsffile{update-frame.ps}}
 424 \end{center}
 425 The SuB therefore points to the Update return vector component of
 426 the topmost update frame.
 427 \end{rawlatex}
 428
 429 A {\em constructor} update frame, which is pushed only by closures
 430 which know they will evaluate to a data object, looks just the
 431 same, but without the saved SuA pointer.
 432
 433 We store the following information concerning the stacks in a global
 434 structure. (sequential only).
 435 \begin{code}
 436
 437 typedef struct {
 438     PP_ botA;   /* Points to bottom-most word of A stack */
 439     P_          botB;   /* Points to bottom-most word of B stack */
 440 } stackData;
 441
 442 extern stackData stackInfo;
 443 \end{code}
 444
 445 %************************************************************************
 446 %*                                                                      *
 447 \subsection[SM-choose-flavour]{Deciding which GC flavour is in force...}
 448 %*                                                                      *
 449 %************************************************************************
 450
 451 Each garbage collector requires different garbage collection entries
 452 in the info-table.
 453
 454 \begin{code}
 455 #if   defined(GC2s)
 456 #define _INFO_COPYING
 457
 458 #else
 459 #if defined(GC1s)
 460 #define _INFO_COMPACTING
 461 #define _INFO_MARKING
 462
 463 #else
 464 #if defined(GCdu) || defined (GCap) || defined (GCgn)
 465 #define _INFO_COPYING
 466 #define _INFO_COMPACTING
 467 #define _INFO_MARKING
 468
 469 #else
 470 /* NO_INFO_SPECIFIED (ToDo: an #error ???) */
 471 #endif
 472 #endif
 473 #endif
 474 \end{code}
 475
 476 %************************************************************************
 477 %*                                                                      *
 478 %\subsection[Info.lh]{Info Pointer Definitions}
 479 %*                                                                      *
 480 %************************************************************************
 481
 482 \downsection
 483 \input{Info.lh}
 484 \upsection
 485
 486 %************************************************************************
 487 %*                                                                      *
 488 %\subsection[Parallel.lh]{Parallel Machine Definitions}
 489 %*                                                                      *
 490 %************************************************************************
 491
 492 \downsection
 493 \input{Parallel.lh}
 494 \upsection
 495
 496
 497 %************************************************************************
 498 %*                                                                      *
 499 %\subsection[CostCentre.lh]{Profiling Definitions}
 500 %*                                                                      *
 501 %************************************************************************
 502
 503 \downsection
 504 \input{CostCentre.lh}
 505 \upsection
 506
 507
 508 %************************************************************************
 509 %*                                                                      *
 510 %\subsection[SM-closures]{Closure-Related Definitions}
 511 %*                                                                      *
 512 %************************************************************************
 513
 514 \downsection
 515 \input{SMClosures.lh}
 516 \upsection
 517
 518
 519
 520 %************************************************************************
 521 %*                                                                      *
 522 %\subsection[SM-info-tables]{Info-table Related Definitions}
 523 %*                                                                      *
 524 %************************************************************************
 525
 526 \downsection
 527 \input{SMInfoTables.lh}
 528 \upsection
 529
 530
 531 End multi-slurp protection:
 532 \begin{code}
 533 #endif /* SMinterface_H */
 534 \end{code}