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(I_ initSM            PROTO((I_ rts_argc, char **rts_argv, FILE *statsfile));)
 100 IF_RTS(I_ exitSM            PROTO((smInfo *sm));)
 101 IF_RTS(I_ initStacks        PROTO((smInfo *sm));)
 102 IF_RTS(I_ initHeap          PROTO((smInfo *sm));)
 103 #ifdef CONCURRENT
 104 IF_RTS(rtsBool initThreadPool PROTO((I_ size));)
 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(USE_COST_CENTRES) || defined(GUM)
 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@ processes any runtime parameters directed towards the storage
 134 manager. The @statsfile@ parameter is an open file, which will contain
 135 any garbage collection statistics requested by the user.  This file
 136 must be opened for writing.
 137
 138 @exitSM@ does any cleaning up required by the storage manager before
 139 the program is executed. Its main purpose is to print any summary
 140 statistics.
 141
 142 @initStacks@ allocates the A and B stacks (sequential only). It
 143 initialises the @spa@, @spb@, @sua@, and @sub@ fields of @sm@
 144 appropriately for empty stacks.  Successive calls to @initStacks@
 145 re-initialise the stacks.
 146
 147 @initHeap@ allocates the heap. It initialises the @hp@ and @hplim@
 148 fields of @sm@ to represent an empty heap for the compiled-in garbage
 149 collector.  It also allocates the @roots@ array for later use within
 150 @collectHeap@, and initialises @CAFlist@ to be the empty list.  The
 151 @roots@ array must be large enough to hold at least @SM_MAXROOTS@
 152 roots.  If we are using Appel's collector it also initialises the
 153 @OldLim@ field.
 154
 155 In the sequential system, it also initialises the stable pointer table
 156 and the @MallocPtr@ (and @OldMallocPtrList@) fields.
 157
 158 @collectHeap@ invokes the garbage collector that was requested at
 159 compile time. @reqsize@ is the size of the request (in words) that
 160 resulted in the overflow. If the garbage collection succeeds, then at
 161 least @reqsize@ words will be available. @collectHeap@ requires all
 162 the fields of @sm@ to be initialised appropriately (from the
 163 STG-machine registers).  The following are identified as
 164 heap roots:
 165 \begin{itemize}
 166 \item The @roots@ array.
 167 \item The updated CAFs recorded in @CAFlist@.
 168 \item A Stack.
 169 \item Update frames on the B Stack. These may be ``squeezed'' out
 170 if they are the only reference to a closure --- thus avoiding the
 171 update.
 172 \item The stable pointer table. (In sequential system.)
 173 \end{itemize}
 174
 175 There are three possible results from a garbage collection:
 176 \begin{description}
 177 \item[\tr{GC_HARD_LIMIT_EXCEEDED} (\tr{reqsize > hplim - hp})]
 178 The heap size exceeds the hard heap limit: we report an error and
 179 exit.
 180
 181 \item[\tr{GC_SOFT_LIMIT_EXCEEDED} (\tr{reqsize + hardHpOverflowSize > hplim - hp})]
 182 The heap size exceeds the soft heap limit: set \tr{hardHpOverflowSize}
 183 to \tr{0} so that we can use the overflow space, unwind the stack and
 184 call an appropriate piece of Haskell to handle the error.
 185
 186 \item[\tr{GC_SUCCESS} (\tr{reqsize + hardHpOverflowSize <= hplim - hp})]
 187 The heap size is less than the soft heap limit.
 188
 189 \begin{itemize}
 190 \item @hp@ and @hplim@ will indicate the new space available for
 191 allocation.  But we'll subtract \tr{hardHpOverflowSize} from
 192 \tr{hplim} so that we'll GC when we hit the soft limit.
 193
 194 \item The elements of the @roots@ array will point to the new
 195 locations of the closures.
 196
 197 \item @spb@ and @sub@ will be updated to reflect the new state of the
 198 B stack arising from any update frame ``squeezing'' [sequential only].
 199
 200 \item The elements of @CAFlist@ and the stable pointers will be
 201 updated to point to the new locations of the closures they reference.
 202
 203 \item Any members of @MallocPtrList@ which became garbage should have
 204 been reported (by calling @FreeMallocPtr@; and the @(Old)MallocPtrList@
 205 updated to contain only those Malloc Pointers which are still live.
 206 \end{itemize}
 207
 208 \end{description}
 209
 210 \begin{code}
 211 #define GC_HARD_LIMIT_EXCEEDED 0
 212 #define GC_SOFT_LIMIT_EXCEEDED 1
 213 #define GC_SUCCESS 2
 214 \end{code}
 215
 216 %************************************************************************
 217 %*                                                                      *
 218 \subsection[SM-what-really-happens]{``What really happens in a garbage collection?''}
 219 %*                                                                      *
 220 %************************************************************************
 221
 222 This is a brief tutorial on ``what really happens'' going to/from the
 223 storage manager in a garbage collection.
 224
 225 \begin{description}
 226 %------------------------------------------------------------------------
 227 \item[The heap check:]
 228
 229 [OLD-ISH: WDP]
 230
 231 If you gaze into the C output of GHC, you see many macros calls like:
 232 \begin{verbatim}
 233 HEAP_CHK_2PtrsLive((_FHS+2));
 234 \end{verbatim}
 235
 236 This expands into the C (roughly speaking...):
 237 \begin{verbatim}
 238 Hp = Hp + (_FHS+2);     /* optimistically move heap pointer forward */
 239
 240 GC_WHILE_OR_IF (HEAP_OVERFLOW_OP(Hp, HpLim) OR_INTERVAL_EXPIRED) {
 241         STGCALL2_GC(PerformGC, <liveness-bits>, (_FHS+2));
 242         /* Heap full.  Call "PerformGC" with 2 arguments, "<liveness>",
 243            (info about what ptrs are live) and "_FHS+2" (words
 244            requested), via the magical routine "callWrapper_GC",
 245            which indicates ``I am calling a routine in which GC
 246            may happen'' (a safe bet for `PerformGC').
 247         */
 248 }
 249 \end{verbatim}
 250
 251 In the parallel world, where we will need to re-try the heap check,
 252 @GC_WHILE_OR_IF@ will be a ``while''; in the sequential world, it will
 253 be an ``if''.
 254
 255 The ``heap lookahead'' checks, which are similar and used for
 256 multi-precision @Integer@ ops, have some further complications.  See
 257 the commentary there (\tr{StgMacros.lh}).
 258
 259 %------------------------------------------------------------------------
 260 \item[Into @callWrapper_GC@...:]
 261
 262 When we failed the heap check (above), we were inside the
 263 GCC-registerised ``threaded world.''  @callWrapper_GC@ is all about
 264 getting in and out of the threaded world.  On SPARCs, with register
 265 windows, the name of the game is not shifting windows until we have
 266 what we want out of the old one.  In tricky cases like this, it's best
 267 written in assembly language.
 268
 269 Though the principle of ``save everything away'' is the same in both
 270 the sequential and parallel worlds, the details are different.
 271
 272 For the sequential world:
 273 \begin{enumerate}
 274 \item
 275 @callWrapper_GC@ saves the return address.
 276 \item
 277 It saves the arguments passed to it (so it doesn't get lost).
 278 \item
 279 Save the machine registers used in the STG threaded world in their
 280 \tr{*_SAVE} global-variable backup locations.  E.g., register \tr{Hp}
 281 is saved into \tr{Hp_SAVE}.
 282 \item
 283 Call the routine it was asked to call; in this example, call
 284 @PerformGC@ with arguments \tr{<liveness>}, and @_FHS+2@ (some constant)...
 285 \end{enumerate}
 286
 287 For the parallel world, a GC means giving up the thread of control.
 288 So we must fill in the thread-state-object (TSO) [and its associated
 289 stk object] with enough information for later resumption:
 290 \begin{enumerate}
 291 \item
 292 Save the return address in the TSO's PC field.
 293 \item
 294 Save the machine registers used in the STG threaded world in their
 295 corresponding TSO fields.  We also save the pointer-liveness
 296 information in the TSO.
 297 \item
 298 The registers that are not thread-specific, notably \tr{Hp} and
 299 \tr{HpLim}, are saved in the @StorageMgrInfo@ structure.
 300 \item
 301 Call the routine it was asked to call; in this example, call
 302 @PerformGC@ with arguments \tr{<liveness>} and @_FHS+2@ (some constant)...
 303
 304 (In the parallel world, we don't expect it to return...)
 305 \end{enumerate}
 306
 307 %------------------------------------------------------------------------
 308 \item[Into the heap overflow wrapper, @PerformGC@ [sequential]:]
 309
 310 The first argument (\tr{<liveness>}, in our example) say what registers
 311 are live, i.e., are ``roots'' the storage manager needs to know.
 312 \begin{verbatim}
 313 StorageMgrInfo.rootno   = 2;
 314 StorageMgrInfo.roots[0] = (P_) Ret1_SAVE;
 315 StorageMgrInfo.roots[1] = (P_) Ret2_SAVE;
 316 \end{verbatim}
 317
 318 We further: (a)~move the heap-pointer back [we had optimistically
 319 advanced it, in the initial heap check], (b)~load up the @smInfo@ data
 320 from the STG registers' \tr{*_SAVE} locations, and (c)~FINALLY: call
 321 @collectHeap@.
 322
 323 IT IS AT THIS POINT THAT THE WORLD IS COMPLETELY TIDY.
 324
 325 %------------------------------------------------------------------------
 326 \item[Into the heap overflow wrapper, @PerformGC@ [parallel]:]
 327
 328 Parallel execution is only slightly different.  Most information has
 329 already been saved in the TSO.
 330
 331 \begin{enumerate}
 332 \item
 333 We still need to set up the storage manager's @roots@ array.
 334 \item
 335 We mark on the scheduler's big ``blackboard'' that a GC is
 336 required.
 337 \item
 338 We reschedule, i.e., this thread gives up control.  (The scheduler
 339 will presumably initiate a garbage-collection, but it may have to do
 340 any number of other things---flushing, for example---before ``normal
 341 execution'' resumes; and it most certainly may not be this thread that
 342 resumes at that point!)
 343 \end{enumerate}
 344
 345 %------------------------------------------------------------------------
 346 \item[Into/out of @collectHeap@ [sequential only]:]
 347
 348 @collectHeap@ does the business and reports back whether it freed up
 349 enough space.
 350
 351 %------------------------------------------------------------------------
 352 \item[Out of the heap overflow wrapper, @PerformGC@ [sequential only]:]
 353
 354 We begin our return back to doing useful work by: (a)~reloading the
 355 appropriate STG-register \tr{*_SAVE} locations from (presumably
 356 changed) @smInfo@; (b) re-advance the heap-pointer---which we've been
 357 trying to do for a week or two---now that there is enough space.
 358
 359 We must further restore appropriate @Ret?@ registers from the storage
 360 manager's roots array; in this example:
 361
 362 \begin{verbatim}
 363 Ret1_SAVE = (W_) StorageMgrInfo.roots[0];
 364 Ret2_SAVE = (W_) StorageMgrInfo.roots[1];
 365 \end{verbatim}
 366
 367 %------------------------------------------------------------------------
 368 \item[Out of @callWrapper_GC@ [sequential]:]
 369
 370 We pop out of heap-overflow code and are ready to resume STG
 371 ``threaded world'' stuff.
 372
 373 The main thing is to re-load up the GCC-ised machine registers from
 374 the relevant \tr{*_SAVE} locations; e.g., \tr{SpA} from \tr{SpA_SAVE}.
 375
 376 To conclude, @callWrapper_GC@ merely {\em jumps} back to the return
 377 address which it was given originally.
 378
 379 WE'RE BACK IN (SEQUENTIAL) BUSINESS.
 380
 381 %------------------------------------------------------------------------
 382 \item[Out of @callWrapper_GC@ [parallel]:]
 383
 384 When this thread is finally resumed after GC (and who knows what
 385 else), it will restart by the normal enter-TSO/enter-stack-object
 386 sequence, which has the effect of re-loading the registers, etc.,
 387 (i.e., restoring the state).
 388
 389 Because the address we saved in the TSO's PC field was that at the end
 390 of the heap check, and because the check is a while-loop in the
 391 parallel system, we will now loop back around, and make sure there is
 392 enough space before continuing.
 393 \end{description}
 394
 395 %************************************************************************
 396 %*                                                                      *
 397 \subsection[SM-stack-info]{Stacks}
 398 %*                                                                      *
 399 %************************************************************************
 400
 401 There are two stacks, as in the STG paper \cite{new-stg-paper}.
 402 \begin{itemize}
 403 \item
 404 The A stack contains only closure pointers.
 405 \item
 406 The B stack contains, basic values, return addresses, and update
 407 frames.
 408 \end{itemize}
 409 The A stack and B stack grow towards each other, so they overflow when
 410 they collide. Currently the A stack grows downward (towards lower
 411 addresses); the B stack grows upward.  (We localise the stuff which
 412 uses this information within macros defined in @StgDirections.h@)
 413
 414 During reduction, SpA and SpB point to the topmost allocated word of
 415 the corresponding stack (though they may not be up to date in the
 416 middle of a basic block).
 417
 418 Each stack also has a {\em stack update pointer}, SuA and SuB, which
 419 point to the topmost word of the most recent update frame in the
 420 corresponding stack.  (Colloquially, SuA and Sub point to the first
 421 items on their respective stacks ``that you cannot have.'')
 422 \begin{rawlatex}
 423 A standard update frame (on the B stack) looks like this
 424 (stack grows downward in this picture):
 425 \begin{center}
 426 \mbox{\epsffile{update-frame.ps}}
 427 \end{center}
 428 The SuB therefore points to the Update return vector component of
 429 the topmost update frame.
 430 \end{rawlatex}
 431
 432 A {\em constructor} update frame, which is pushed only by closures
 433 which know they will evaluate to a data object, looks just the
 434 same, but without the saved SuA pointer.
 435
 436 We store the following information concerning the stacks in a global
 437 structure. (sequential only).
 438 \begin{code}
 439
 440 typedef struct {
 441     PP_ botA;   /* Points to bottom-most word of A stack */
 442     P_          botB;   /* Points to bottom-most word of B stack */
 443 } stackData;
 444
 445 extern stackData stackInfo;
 446 \end{code}
 447
 448 %************************************************************************
 449 %*                                                                      *
 450 \subsection[SM-choose-flavour]{Deciding which GC flavour is in force...}
 451 %*                                                                      *
 452 %************************************************************************
 453
 454 Each garbage collector requires different garbage collection entries
 455 in the info-table.
 456
 457 \begin{code}
 458 #if   defined(GC2s)
 459 #define _INFO_COPYING
 460
 461 #else
 462 #if defined(GC1s)
 463 #define _INFO_COMPACTING
 464 #define _INFO_MARKING
 465
 466 #else
 467 #if defined(GCdu) || defined (GCap) || defined (GCgn)
 468 #define _INFO_COPYING
 469 #define _INFO_COMPACTING
 470 #define _INFO_MARKING
 471
 472 #else
 473 /* NO_INFO_SPECIFIED (ToDo: an #error ???) */
 474 #endif
 475 #endif
 476 #endif
 477 \end{code}
 478
 479 %************************************************************************
 480 %*                                                                      *
 481 %\subsection[Info.lh]{Info Pointer Definitions}
 482 %*                                                                      *
 483 %************************************************************************
 484
 485 \downsection
 486 \input{Info.lh}
 487 \upsection
 488
 489 %************************************************************************
 490 %*                                                                      *
 491 %\subsection[Parallel.lh]{Parallel Machine Definitions}
 492 %*                                                                      *
 493 %************************************************************************
 494
 495 \downsection
 496 \input{Parallel.lh}
 497 \upsection
 498
 499
 500 %************************************************************************
 501 %*                                                                      *
 502 %\subsection[CostCentre.lh]{Profiling Definitions}
 503 %*                                                                      *
 504 %************************************************************************
 505
 506 \downsection
 507 \input{CostCentre.lh}
 508 \upsection
 509
 510
 511 %************************************************************************
 512 %*                                                                      *
 513 %\subsection[SM-closures]{Closure-Related Definitions}
 514 %*                                                                      *
 515 %************************************************************************
 516
 517 \downsection
 518 \input{SMClosures.lh}
 519 \upsection
 520
 521
 522
 523 %************************************************************************
 524 %*                                                                      *
 525 %\subsection[SM-info-tables]{Info-table Related Definitions}
 526 %*                                                                      *
 527 %************************************************************************
 528
 529 \downsection
 530 \input{SMInfoTables.lh}
 531 \upsection
 532
 533
 534 End multi-slurp protection:
 535 \begin{code}
 536 #endif /* SMinterface_H */
 537 \end{code}