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