ghc/includes/SMupdate.lh

   1 \section[SMupdate.h]{Update interface}
   2
   3 This interface provides a second level of abstraction from the storage
   4 manager hiding all the nasties associated with updates, indirections,
   5 CAFs and black holes.
   6
   7 \begin{code}
   8 #ifndef SMUPDATE_H
   9 #define SMUPDATE_H
  10 \end{code}
  11
  12 %************************************************************************
  13 %*                                                                      *
  14 \subsubsection[update-frames]{Pushing Update Frames}
  15 %*                                                                      *
  16 %************************************************************************
  17
  18 If a closure is to be updated with the result of the computation an
  19 update frame must be pushed onto the B stack.
  20
  21 A {\em Standard update frame} contains (in order from the top of the
  22 frame):
  23 \begin{itemize}
  24 \item The return vector.
  25 \item The closure to be updated.
  26 \item Saved @SuB@ (points to the next update frame).
  27 \item Saved @SuA@.
  28 \end{itemize}
  29
  30 Note: We used to keep the {\em offsets} smashed into one word, but the
  31       introduction of strict evaluation meant we could overflow this.
  32
  33 [Don't really believe this cost-centre stuff WDP 94/07]
  34
  35 If we are keeping track of the current cost centre we have to make the
  36 following additions:
  37 \begin{enumerate}
  38 \item
  39 The current cost centre, @CCC@, is added as an additional field to the
  40 update frames described above. It is the last field in the frame.
  41 When the update is executed the cost centre is restored.
  42
  43 \item
  44 A special restore cost centre frame is introduced which does not
  45 contain a closure to update, but just a cost centre to restore.
  46 \end{enumerate}
  47
  48 The different update frame sizes, @STD_UF_SIZE@, @CON_UF_SIZE@ and
  49 optionally @RCC_UF_SIZE@, and the offsets within a frame (@UF_RET@,
  50 @UF_UPDATEE@, etc) are declared in \tr{GhcConstants.lh}.
  51
  52 We now have the macros to push update frames. They are passed the
  53 update @target@ and the A and B stack offsets at which the current top
  54 of stack is found. E.g. @SpX + SpX_offset@ points to the top word on
  55 the stack. The update frame is pushed directly above this position on
  56 the B stack.  @SpB + SpB_offset + xxx_UF_SIZE@ gives the topmost word
  57 of the update frame, from which we subtract the offsets.
  58
  59 ``A picture is worth five thousand bytes.''
  60 \begin{verbatim}
  61 A stk | |-----------------------|
  62       v |                       |
  63         |-----------------------|
  64         |                       |
  65         |-----------------------|
  66         |                       |
  67         |-----------------------|
  68         |                       |
  69
  70
  71
  72         |=======================| (new update frame)
  73         |   upd code or vector  | <- new SuB
  74         |-----------------------|
  75         |   updatee (target)    |
  76         |-----------------------|
  77         |   SuB (grip: SuB_off) | (SuX_off = abs ( new SuX - prev SuX );e.g., 7 for SuB
  78         |-----------------------|
  79         |   SuA (grip: SuA_off) |
  80         |-----------------------|
  81         |   CCC                 |
  82         |=======================|
  83         |                       | <- SpB now [really (SpB + SpB_offset)]
  84         |-----------------------|
  85         |                       |
  86         |-----------------------|
  87         |                       |
  88         |=======================| (prev update frame [e.g.])
  89         |   upd code or vector  | <- prev SuB
  90         |-----------------------|
  91         |   its updatee         |
  92         |-----------------------|
  93         |         ...           |
  94         |-----------------------|
  95         |         ...           |
  96         |-----------------------|
  97         |    its cost-centre    |
  98         |=======================|
  99         |                       |
 100       ^ |-----------------------|
 101 B stk | |                       |
 102 \end{verbatim}
 103
 104 \begin{code}
 105 I_ SqueezeUpdateFrames PROTO((P_, P_, P_));
 106
 107 EXTDATA_RO(vtbl_StdUpdFrame);
 108 EXTFUN(StdUpdFrameDirectReturn);
 109
 110 EXTFUN(StdErrorCode); /* Where should this go? */
 111 EXTFUN(UpdErr);
 112 EXTFUN(IndUpdRetV0);
 113 EXTFUN(IndUpdRetV1);
 114 EXTFUN(IndUpdRetV2);
 115 EXTFUN(IndUpdRetV3);
 116 EXTFUN(IndUpdRetV4);
 117 EXTFUN(IndUpdRetV5);
 118 EXTFUN(IndUpdRetV6);
 119 EXTFUN(IndUpdRetV7);
 120 EXTFUN(IndUpdRetDir);
 121
 122 /*
 123    Note that UNVEC() is used to select whole statements (declarations) as
 124    well as labels.  Please don't put parentheses around the expansion.
 125  */
 126
 127 #ifdef __STG_REV_TBLS__
 128 #define RVREL(offset) (-(offset)-1)
 129 #define DIRECT(target) (target)
 130 #define UNVEC(direct,vector) direct
 131 #else
 132 #define RVREL(offset) (offset)
 133 #define DIRECT(target) (*(target))
 134 #define UNVEC(direct,vector) vector
 135 #endif
 136
 137 #ifdef CONCURRENT
 138 /* for stack chunking */
 139 extern const W_ vtbl_Underflow[];
 140 EXTFUN(UnderflowDirectReturn);
 141 EXTFUN(UnderflowVect0);
 142 EXTFUN(UnderflowVect1);
 143 EXTFUN(UnderflowVect2);
 144 EXTFUN(UnderflowVect3);
 145 EXTFUN(UnderflowVect4);
 146 EXTFUN(UnderflowVect5);
 147 EXTFUN(UnderflowVect6);
 148 EXTFUN(UnderflowVect7);
 149 EXTFUN(StackUnderflowEnterNode);
 150 EXTFUN(CommonUnderflow);
 151 EXTFUN(PrimUnderflow);
 152 #endif  /* CONCURRENT */
 153
 154 /* Now, we always use pointers in update frame, even in the threaded world */
 155
 156 #define PUSH_RET(frame, rv)             (frame)[BREL(UF_RET)] = (W_)(rv)
 157 #define PUSH_UPDATEE(frame, updatee)    (frame)[BREL(UF_UPDATEE)] = (W_)(updatee)
 158 #define PUSH_SuB(frame, sub)            (frame)[BREL(UF_SUB)] = (W_)(sub)
 159 #define PUSH_SuA(frame, sua)            (frame)[BREL(UF_SUA)] = (W_)(sua)
 160
 161 #if defined(USE_COST_CENTRES)
 162 #define PUSH_STD_CCC(frame) (frame)[BREL(UF_COST_CENTRE)] = (W_)(CCC)
 163 #else
 164 #define PUSH_STD_CCC(frame)
 165 #endif
 166
 167 /* When GRABing, "frame" pts to an update frame */
 168
 169 #define GRAB_RET(frame)         ((void *)((frame)[BREL(UF_RET)]))
 170 #define GRAB_SuB(frame)         ((P_)((frame)[BREL(UF_SUB)]))
 171 #define GRAB_SuA(frame)         ((PP_)((frame)[BREL(UF_SUA)]))
 172 #define GRAB_UPDATEE(frame)     ((P_)((frame)[BREL(UF_UPDATEE)]))
 173 #define GRAB_COST_CENTRE(frame) ((CostCentre)((frame)[BREL(UF_COST_CENTRE)]))
 174
 175 #define PUSH_STD_UPD_FRAME(target, SpA_offset, SpB_offset)      \
 176     do {                                                        \
 177         P_ __frame;                                             \
 178         UPDF_STD_PUSHED();      /* ticky-ticky, spat */         \
 179         __frame = SpB - BREL(SpB_offset + STD_UF_SIZE);         \
 180         PUSH_RET(__frame, RetReg);                              \
 181         PUSH_SuB(__frame, SuB);                                 \
 182         PUSH_SuA(__frame, SuA);                                 \
 183         PUSH_UPDATEE(__frame, target);                          \
 184         PUSH_STD_CCC(__frame);                                  \
 185         SuB = __frame;                                          \
 186         SuA = SpA - AREL(SpA_offset);                           \
 187     } while(0)
 188
 189 #define POP_STD_UPD_FRAME()                                     \
 190     do {                                                        \
 191         RetReg = GRAB_RET(SpB);                                 \
 192         SuB = GRAB_SuB(SpB);                                    \
 193         SuA = GRAB_SuA(SpB);                                    \
 194         SpB += BREL(STD_UF_SIZE);                               \
 195     } while(0);
 196
 197 \end{code}
 198
 199
 200 %************************************************************************
 201 %*                                                                      *
 202 \subsubsection[black-hole-overwrite]{Overwriting with Black Holes}
 203 %*                                                                      *
 204 %************************************************************************
 205
 206 An updatable closure may be overwritten with a black hole so that
 207 the free variables in the closure being evaluated are not kept alive.
 208 This may be done on entering the closure or later by the garbage
 209 collector.
 210
 211 \begin{code}
 212 EXTDATA_RO(BH_UPD_info);
 213 EXTFUN(BH_UPD_entry);
 214 EXTDATA_RO(BH_SINGLE_info);
 215 EXTFUN(BH_SINGLE_entry);
 216
 217 #define UPD_BH(heapptr,infolbl)         INFO_PTR(heapptr) = (W_) infolbl
 218 \end{code}
 219
 220 The following macros are actually planted by the code generator. They
 221 allow us to delay the decision about if/when we black hole. It should
 222 be noted that single entry closures do not have update frames which
 223 can be traced by the garbage collector. It is only possibly to
 224 overwrite with a black hole on entry.
 225
 226 In the sequential system, updatable closures are not black-holed until GC.
 227 When GC occurs, the only active updatable closures are those with update
 228 frames on the stack, so the GC routine can walk the stack frames to find
 229 the updatable closures to black hole (primarily for plugging space leaks).
 230 This approach saves the overhead of black-holing every updatable closure on
 231 entry.
 232
 233 In the parallel system, however, it is essential that updatable closures
 234 be black-holed immediately on entry, so that other local threads will
 235 block when attempting to enter a closure already under evaluation.
 236
 237 \begin{code}
 238 #if defined(CONCURRENT)
 239 #define UPD_BH_UPDATABLE(heapptr)       UPD_BH(heapptr,BH_UPD_info)
 240 #else
 241 #define UPD_BH_UPDATABLE(heapptr)       /* nothing -- BHed by GC */
 242 #endif
 243
 244 #define UPD_BH_SINGLE_ENTRY(heapptr)    UPD_BH(heapptr,BH_SINGLE_info)
 245                                         /* BHed on entry -- GC cant do it */
 246 \end{code}
 247
 248 Finally we indicate to the storage manager if it is required to trace
 249 closures on the B stack and overwrite them with black holes.
 250
 251 \begin{code}
 252 /* define SM_DO_BH_UPDATE if B stack closures to be BHed by GC */
 253 #if !defined(CONCURRENT)
 254 #define SM_DO_BH_UPDATE
 255 #endif
 256 \end{code}
 257
 258
 259 %************************************************************************
 260 %*                                                                      *
 261 \subsubsection[caf-update]{Entering CAFs}
 262 %*                                                                      *
 263 %************************************************************************
 264
 265 When we enter a CAF we update it with an indirection to a heap
 266 allocated black hole. The @UPD_CAF@ macro updates the CAF with an
 267 @CAF@ indirection to the heap allocated closure and adds the updated
 268 CAF to the list of CAFs. It is up to the entry code to allocate the
 269 black hole.
 270
 271 The @CAF@ info table used is the @Caf_Return@ table. It will be
 272 overwritten at the start of garbage collection with the @Caf_Evac_Upd@
 273 and then reset to @Caf_Return@ during garbage collection.
 274
 275 In the parallel case, the new black hole will be a local node
 276 (with a GA of 0).  This means that the code to update indirections
 277 does not need to check whether it's updating a CAF: the situation
 278 simply never arises!  If you change how this code works (e.g. to
 279 update CAFs across the parallel machine), you should check @UPD_IND@
 280 etc.
 281
 282 \begin{code}
 283
 284 EXTDATA_RO(Caf_info);
 285 EXTFUN(Caf_entry);
 286
 287 #define UPD_CAF(cafptr, bhptr)                                  \
 288   do {                                                          \
 289   SET_INFO_PTR(cafptr, Caf_info);                               \
 290   IND_CLOSURE_PTR(cafptr) = (W_) (bhptr);                       \
 291   IND_CLOSURE_LINK(cafptr) = (W_) StorageMgrInfo.CAFlist;       \
 292   StorageMgrInfo.CAFlist = (P_) (cafptr);                       \
 293   } while(0)
 294
 295 \end{code}
 296
 297
 298 %************************************************************************
 299 %*                                                                      *
 300 \subsection[updating-closures]{Updating Closures}
 301 %*                                                                      *
 302 %************************************************************************
 303
 304 We provide three macros:
 305 \begin{description}
 306
 307 \item[@UPD_IND(updclosure, heapptr)@]\ \\
 308 Overwrites the updatable closure @updclosure@ with an indirection to
 309 @heapptr@.
 310
 311 \item[@UPD_INPLACE_NOPTRS(updclosure, livemask)@]\ \\
 312 This prepares the closure pointed to by @updclosure@ to be updated in-place
 313 with a closure of size @MIN_UPD_SIZE@ containing no pointers.
 314
 315 \item[@UPD_INPLACE_PTRS(updclosure, livemask)@]\ \\
 316 This prepares the closure pointed to by @updclosure@ to be updated in-place
 317 with a closure of size @MIN_UPD_SIZE@ which may contain pointers. It checks
 318 whether @updclosure@ is allowed to be updated inplace. If it is not
 319 it:
 320 \begin{enumerate}
 321 \item Allocates space for a new closure of size @MIN_UPD_SIZE@ (by
 322 calling @HEAP_CHK_RETRY@);
 323 \item Overwrites @updclosure@ with an indirection to this new closure;
 324 \item Modifies @updclosure@ to point to the newly-allocated closure.
 325 \end{enumerate}
 326
 327 All the macros ensure that @updclosure@ points to a closure of size
 328 @MIN_UPD_SIZE@ ready to be filled in with the result of the update.
 329
 330 The code following @UPDATE_INPLACE@ is responsible for filling it in.
 331 This requires the header to be set, with @INPLACE_UPD_HDR@, and the
 332 body to be filled out.
 333 \end{description}
 334
 335 The @UPD_IND@ and @UPDATE_INPLACE@ macros may have different
 336 definitions depending on the garbage collection schemes in use.
 337
 338 First we have the declarations which trace updates. These are calls to
 339 tracing routines inserted if @DO_RUNTIME_TRACE_UPDATES@ is defined and
 340 printed if @traceUpdates@ is true.
 341
 342 \begin{code}
 343 #if defined(DO_RUNTIME_TRACE_UPDATES)
 344
 345 extern I_ traceUpdates;
 346 extern void TRACE_UPDATE_Ind();
 347 extern void TRACE_UPDATE_Inplace_NoPtrs();
 348 extern void TRACE_UPDATE_Inplace_Ptrs();
 349
 350 #define TRACE_UPDATE(_trace) _trace
 351 #else
 352 #define TRACE_UPDATE(_trace) /* nothing */
 353 #endif
 354 \end{code}
 355
 356 Before describing the update macros we declare the partial application
 357 entry and update code (See \tr{StgUpdate.lhc}).
 358
 359 \begin{code}
 360 EXTDATA_RO(PAP_info);
 361 EXTFUN(PAP_entry);
 362 EXTFUN(UpdatePAP);
 363 \end{code}
 364
 365 %************************************************************************
 366 %*                                                                      *
 367 \subsubsection[updates-standard]{Implementation of Standard Updates}
 368 %*                                                                      *
 369 %************************************************************************
 370
 371 \begin{code}
 372 #ifdef CONCURRENT
 373
 374 #define ALREADY_LINKED(closure) \
 375     (IS_MUTABLE(INFO_PTR(closure)) && MUT_LINK(closure) != MUT_NOT_LINKED)
 376
 377 #if defined(GRAN)
 378 extern I_ AwakenBlockingQueue PROTO((P_));
 379 #else
 380 extern void AwakenBlockingQueue PROTO((P_));
 381 #endif
 382
 383 #ifdef MAIN_REG_MAP
 384 #define AWAKEN_BQ(updatee)                                              \
 385 do { if (IS_BQ_CLOSURE(updatee))                                        \
 386  STGCALL1(void,(void *, P_), AwakenBlockingQueue, (P_) BQ_ENTRIES(updatee)); \
 387 } while(0);
 388 #endif
 389
 390 #ifdef NULL_REG_MAP
 391 #define AWAKEN_BQ(updatee)                      \
 392 do { if (IS_BQ_CLOSURE(updatee))                \
 393  AwakenBlockingQueue((P_)BQ_ENTRIES(updatee));  \
 394 } while(0);
 395 #endif
 396
 397 #define AWAKEN_INPLACE_BQ()
 398
 399 #else
 400
 401 #define ALREADY_LINKED(closure) 0
 402
 403 #define AWAKEN_BQ(updatee)
 404 #define AWAKEN_INPLACE_BQ()
 405
 406 #endif
 407
 408 EXTDATA_RO(Ind_info);
 409 EXTFUN(Ind_entry);
 410
 411 #if defined(GC2s) || defined(GC1s) || defined(GCdu)
 412
 413 #define UPD_IND(updclosure, heapptr)                            \
 414         TRACE_UPDATE(TRACE_UPDATE_Ind(updclosure,heapptr));     \
 415         UPDATED_SET_UPDATED(updclosure); /* subs entry count */ \
 416         UPDATE_PROFILE_CLOSURE((P_)updclosure);                 \
 417         AWAKEN_BQ(updclosure);                                  \
 418         SET_INFO_PTR(updclosure, Ind_info);                     \
 419         IND_CLOSURE_PTR(updclosure) = (W_)(heapptr)
 420
 421 #define UPD_INPLACE_NOPTRS(livemask)                            \
 422         TRACE_UPDATE(TRACE_UPDATE_Inplace_NoPtrs(Node));        \
 423         UPDATED_SET_UPDATED(Node); /* subs entry count */       \
 424         UPDATE_PROFILE_CLOSURE(Node);                           \
 425         AWAKEN_BQ(Node);
 426
 427 #define UPD_INPLACE_PTRS(livemask)                              \
 428         TRACE_UPDATE(TRACE_UPDATE_Inplace_Ptrs(Node,hp));       \
 429         UPDATED_SET_UPDATED(Node); /* subs entry count */       \
 430         UPDATE_PROFILE_CLOSURE(Node);                           \
 431         AWAKEN_BQ(Node);
 432
 433 #define INPLACE_UPD_HDR(closure,infolbl,cc,size,ptrs)           \
 434         UPD_FIXED_HDR(closure,infolbl,cc)
 435 \end{code}
 436
 437 %************************************************************************
 438 %*                                                                      *
 439 \subsubsection[updates-appel]{Implementation of Appel's Updates}
 440 %*                                                                      *
 441 %************************************************************************
 442
 443 Appel's updates require the identification of old generation closures
 444 which are updated. They must be updated with an indirection and linked
 445 onto the list of old generation closures.
 446
 447 \begin{code}
 448 #else
 449 #if defined(GCap) || defined(GCgn)
 450
 451 #define UPD_IND(updclosure, heapptr)                            \
 452 { TRACE_UPDATE(TRACE_UPDATE_Ind(updclosure,heapptr));           \
 453   if ( ((P_)(updclosure)) <= StorageMgrInfo.OldLim) {           \
 454       UPD_OLD_IND();                                            \
 455       if(!ALREADY_LINKED(updclosure)) {                         \
 456           MUT_LINK(updclosure)                                  \
 457               = (W_) StorageMgrInfo.OldMutables;                \
 458           StorageMgrInfo.OldMutables = (P_) (updclosure);       \
 459       }                                                         \
 460   } else {                                                      \
 461       UPD_NEW_IND();                                            \
 462   }                                                             \
 463   AWAKEN_BQ(updclosure);                                        \
 464   SET_INFO_PTR(updclosure, Ind_info);                           \
 465   IND_CLOSURE_PTR(updclosure) = (W_)(heapptr);                  \
 466 }
 467
 468 /*
 469  * In threaded-land, we have to do the same nonsense as UPD_INPLACE_PTRS if
 470  * we were a blocking queue on the old mutables list.
 471  */
 472 #define UPD_INPLACE_NOPTRS(live_regs_mask)              \
 473   TRACE_UPDATE(TRACE_UPDATE_Inplace_NoPtrs(Node));      \
 474   if ( Node <= StorageMgrInfo.OldLim) {                 \
 475       UPD_OLD_IN_PLACE_NOPTRS();                                \
 476       if(ALREADY_LINKED(Node)) {                                \
 477           /* We are already on the old mutables list, so we     \
 478              can't update in place any more */                  \
 479           HEAP_CHK(live_regs_mask, _FHS+MIN_UPD_SIZE, 0);       \
 480             /* ticky-ticky (NB: was ALLOC_UPD_CON) */           \
 481           ALLOC_CON(_FHS,1,MIN_UPD_SIZE-1,_FHS+MIN_UPD_SIZE);   \
 482           CC_ALLOC(CCC,_FHS+MIN_UPD_SIZE,CON_K);                \
 483           /* must awaken after any possible GC */       \
 484           AWAKEN_BQ(Node);                              \
 485           SET_INFO_PTR(Node, Ind_info);                 \
 486           IND_CLOSURE_PTR(Node) =                       \
 487             (W_)(Hp-(_FHS+MIN_UPD_SIZE-1));             \
 488           Node = Hp-(_FHS+MIN_UPD_SIZE-1);              \
 489       }                                                 \
 490   } else {                                              \
 491       UPD_NEW_IN_PLACE_NOPTRS();                        \
 492       AWAKEN_BQ(Node);                                  \
 493   }
 494
 495 #define UPD_INPLACE_PTRS(live_regs_mask)                \
 496   TRACE_UPDATE(TRACE_UPDATE_Inplace_Ptrs(Node,hp));     \
 497   if ( Node <= StorageMgrInfo.OldLim) {                 \
 498       /* redirect update with indirection */                    \
 499       UPD_OLD_IN_PLACE_PTRS();                                  \
 500       /* Allocate */                                            \
 501       HEAP_CHK(live_regs_mask, _FHS+MIN_UPD_SIZE, 0);           \
 502         /* ticky-ticky (NB: was ALLOC_UPD_CON) */               \
 503       ALLOC_CON(_FHS,1,MIN_UPD_SIZE-1,_FHS+MIN_UPD_SIZE);       \
 504       CC_ALLOC(CCC,_FHS+MIN_UPD_SIZE,CON_K);                    \
 505                                                                 \
 506       if (!ALREADY_LINKED(Node)) {                      \
 507           MUT_LINK(Node)                                \
 508             = (W_) StorageMgrInfo.OldMutables;          \
 509           StorageMgrInfo.OldMutables = (P_) (Node);     \
 510       }                                                 \
 511       /* must awaken after any possible GC */           \
 512       AWAKEN_BQ(Node);                                  \
 513       SET_INFO_PTR(Node, Ind_info);                     \
 514       IND_CLOSURE_PTR(Node)                             \
 515         = (W_)(Hp-(_FHS+MIN_UPD_SIZE-1));               \
 516       Node = Hp-(_FHS+MIN_UPD_SIZE-1);                  \
 517   } else {                                              \
 518       UPD_NEW_IN_PLACE_PTRS();                          \
 519       AWAKEN_BQ(Node);                                  \
 520   }                                                     \
 521
 522
 523 /* same as before */
 524 #define INPLACE_UPD_HDR(closure,infolbl,cc,size,ptrs)           \
 525   UPD_FIXED_HDR(closure,infolbl,cc)
 526
 527 #endif /* GCap || GCgn */
 528 #endif
 529 \end{code}
 530
 531 %************************************************************************
 532 %*                                                                      *
 533 \subsection[freezing-arrays]{Changing Mutable Pointer closures into Immutable Closures}
 534 %*                                                                      *
 535 %************************************************************************
 536
 537 When freezing an array of pointers we change the info table to
 538 indicate it is now immutable to the garbage collector. The array will
 539 be removed from the old generation mutable array list by the garbage\
 540 collector.
 541
 542 This is only required for generational garbage collectors but we always
 543 do it so better profiling information is provided.
 544
 545 \begin{code}
 546 #ifdef GC_MUT_REQUIRED
 547 #define FREEZE_MUT_HDR(freezeclosure,immutinfo) \
 548         SET_INFO_PTR(freezeclosure, immutinfo)
 549 #else
 550 #define FREEZE_MUT_HDR(freezeclosure,immutinfo) \
 551         SET_INFO_PTR(freezeclosure, immutinfo)
 552 #endif
 553
 554
 555 #endif /* SMUPDATE_H */
 556 \end{code}