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(PROFILING)
 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 %************************************************************************
 249 %*                                                                      *
 250 \subsubsection[caf-update]{Entering CAFs}
 251 %*                                                                      *
 252 %************************************************************************
 253
 254 When we enter a CAF, we update it with an indirection to a
 255 heap-allocated black hole. The @UPD_CAF@ macro updates the CAF with an
 256 @CAF@ indirection to the heap-allocated closure and adds the updated
 257 CAF to the list of CAFs. It is up to the entry code to allocate the
 258 black hole.
 259
 260 The @CAF@ info table used is the @Caf_info@ table. It will be
 261 overwritten at the start of garbage collection with the @Caf_Evac_Upd@
 262 and then reset to @Caf_info@ during garbage collection.
 263
 264 In the parallel case, the new black hole will be a local node
 265 (with a GA of 0).  This means that the code to update indirections
 266 does not need to check whether it's updating a CAF: the situation
 267 simply never arises!  If you change how this code works (e.g. to
 268 update CAFs across the parallel machine), you should check @UPD_IND@
 269 etc.
 270
 271 \begin{code}
 272 EXTDATA_RO(Caf_info);
 273 EXTFUN(Caf_entry);
 274
 275 #define UPD_CAF(cafptr, bhptr)                                  \
 276   do {                                                          \
 277   SET_INFO_PTR(cafptr, Caf_info);                               \
 278   IND_CLOSURE_PTR(cafptr)  = (W_) (bhptr);                      \
 279   IND_CLOSURE_LINK(cafptr) = (W_) StorageMgrInfo.CAFlist;       \
 280   StorageMgrInfo.CAFlist   = (P_) (cafptr);                     \
 281   } while(0)
 282 \end{code}
 283
 284
 285 %************************************************************************
 286 %*                                                                      *
 287 \subsection[updating-closures]{Updating Closures}
 288 %*                                                                      *
 289 %************************************************************************
 290
 291 We provide three macros:
 292 \begin{description}
 293
 294 \item[@UPD_IND(updclosure, heapptr)@]\ \\
 295 Overwrites the updatable closure @updclosure@ with an indirection to
 296 @heapptr@.
 297
 298 \item[@UPD_INPLACE_NOPTRS(updclosure, livemask)@]\ \\
 299 This prepares the closure pointed to by @updclosure@ to be updated
 300 in-place with a closure of size @MIN_UPD_SIZE@ containing no pointers.
 301
 302 \item[@UPD_INPLACE_PTRS(updclosure, livemask)@]\ \\
 303 This prepares the closure pointed to by @updclosure@ to be updated
 304 in-place with a closure of size @MIN_UPD_SIZE@ which may contain
 305 pointers. It checks whether @updclosure@ is allowed to be updated
 306 inplace. If it is not it:
 307 \begin{enumerate}
 308 \item Allocates space for a new closure of size @MIN_UPD_SIZE@ (by
 309 calling @HEAP_CHK_RETRY@);
 310 \item Overwrites @updclosure@ with an indirection to this new closure;
 311 \item Modifies @updclosure@ to point to the newly-allocated closure.
 312 \end{enumerate}
 313
 314 All the macros ensure that @updclosure@ points to a closure of size
 315 @MIN_UPD_SIZE@ ready to be filled in with the result of the update.
 316
 317 The code following @UPDATE_INPLACE@ is responsible for filling it in.
 318 This requires the header to be set, with @INPLACE_UPD_HDR@, and the
 319 body to be filled out.
 320 \end{description}
 321
 322 The @UPD_IND@ and @UPDATE_INPLACE@ macros may have different
 323 definitions depending on the garbage collection schemes in use.
 324
 325 Before describing the update macros we declare the partial application
 326 entry and update code (See \tr{StgUpdate.lhc}).
 327
 328 \begin{code}
 329 EXTDATA_RO(PAP_info);
 330 EXTFUN(PAP_entry);
 331 EXTFUN(UpdatePAP);
 332 \end{code}
 333
 334 %************************************************************************
 335 %*                                                                      *
 336 \subsubsection[updates-standard]{Implementation of Standard Updates}
 337 %*                                                                      *
 338 %************************************************************************
 339
 340 \begin{code}
 341 #ifdef CONCURRENT
 342
 343 /* In the concurrent world, the targed of an update might
 344    be a black hole with a blocking queue attached.  If so,
 345    it will already be on the mutables list, and we have to be careful
 346    not to put it on twice else it screws up the list. */
 347 #define ALREADY_LINKED(closure) \
 348     (IS_MUTABLE(INFO_PTR(closure)) && MUT_LINK(closure) != MUT_NOT_LINKED)
 349
 350 # if defined(GRAN)
 351 P_ AwakenBlockingQueue PROTO((P_));
 352 # else
 353 void AwakenBlockingQueue PROTO((P_));
 354 # endif
 355
 356 # ifdef MAIN_REG_MAP
 357 #  define AWAKEN_BQ(updatee)                                            \
 358 do { if (IS_BQ_CLOSURE(updatee))                                        \
 359  STGCALL1(void,(void *, P_), AwakenBlockingQueue, (P_) BQ_ENTRIES(updatee)); \
 360 } while(0);
 361 # endif
 362
 363 # ifdef NULL_REG_MAP
 364 #  define AWAKEN_BQ(updatee)                    \
 365 do { if (IS_BQ_CLOSURE(updatee))                \
 366  AwakenBlockingQueue((P_)BQ_ENTRIES(updatee));  \
 367 } while(0);
 368 # endif
 369
 370 # define AWAKEN_INPLACE_BQ()
 371
 372 #else /* !CONCURRENT */
 373
 374 # define ALREADY_LINKED(closure) 0 /* NB: see note above in CONCURRENT */
 375
 376 # define AWAKEN_BQ(updatee)
 377 # define AWAKEN_INPLACE_BQ()
 378
 379 #endif /* CONCURRENT */
 380
 381 EXTDATA_RO(Ind_info);
 382 EXTFUN(Ind_entry);
 383 #ifndef TICKY_TICKY
 384 # define Ind_info_TO_USE Ind_info
 385 #else
 386 EXTDATA_RO(Perm_Ind_info);
 387 EXTFUN(Perm_Ind_entry);
 388
 389 # define Ind_info_TO_USE ((AllFlags.doUpdEntryCounts) ? Perm_Ind_info : Ind_info)
 390 #endif
 391
 392 #if defined(GC2s) || defined(GC1s) || defined(GCdu)
 393
 394 #define INPLACE_UPD_HDR(closure,infolbl,cc,size,ptrs)           \
 395         UPD_FIXED_HDR(closure,infolbl,cc)
 396
 397 #define UPD_IND(updclosure, heapptr)                            \
 398         UPDATED_SET_UPDATED(updclosure); /* ticky */            \
 399         AWAKEN_BQ(updclosure);                                  \
 400         SET_INFO_PTR(updclosure, Ind_info_TO_USE);              \
 401         IND_CLOSURE_PTR(updclosure) = (W_)(heapptr)
 402
 403 #define UPD_INPLACE_NOPTRS(livemask)                            \
 404         UPDATED_SET_UPDATED(Node); /* ticky */                  \
 405         AWAKEN_BQ(Node);
 406
 407 #define UPD_INPLACE_PTRS(livemask)                              \
 408         UPDATED_SET_UPDATED(Node); /* ticky */                  \
 409         AWAKEN_BQ(Node);
 410 \end{code}
 411
 412 %************************************************************************
 413 %*                                                                      *
 414 \subsubsection[updates-appel]{Implementation of Appel's Updates}
 415 %*                                                                      *
 416 %************************************************************************
 417
 418 Appel's updates require the identification of old generation closures
 419 which are updated. They must be updated with an indirection and linked
 420 onto the list of old generation closures.
 421
 422 \begin{code}
 423 #else /* !(2s/1s/du) */
 424 # if defined(GCap) || defined(GCgn)
 425
 426 /* same as before */
 427 #define INPLACE_UPD_HDR(closure,infolbl,cc,size,ptrs)                   \
 428   UPD_FIXED_HDR(closure,infolbl,cc)
 429
 430 /* updclosure is the updatee, heapptr is what to update it with */
 431 #define UPD_IND(updclosure, heapptr)                                    \
 432 { UPDATED_SET_UPDATED(updclosure); /* ticky */                          \
 433   if ( ((P_)(updclosure)) > StorageMgrInfo.OldLim ) {                   \
 434       UPD_NEW_IND(); /*ticky*/                                          \
 435   } else {                                                              \
 436       UPD_OLD_IND(); /*ticky*/                                          \
 437       if(!ALREADY_LINKED(updclosure)) {                                 \
 438           MUT_LINK(updclosure) = (W_) StorageMgrInfo.OldMutables;       \
 439           StorageMgrInfo.OldMutables = (P_) (updclosure);               \
 440       }                                                                 \
 441   }                                                                     \
 442   AWAKEN_BQ(updclosure);                                                \
 443   SET_INFO_PTR(updclosure, Ind_info_TO_USE);                            \
 444   IND_CLOSURE_PTR(updclosure) = (W_)(heapptr);                          \
 445 }
 446
 447 /*
 448  * In threaded-land, we have to do the same nonsense as UPD_INPLACE_PTRS if
 449  * we were a blocking queue on the old mutables list.
 450  */
 451 #define UPD_INPLACE_NOPTRS(live_regs_mask)                              \
 452   UPDATED_SET_UPDATED(Node); /* ticky */                                \
 453   if ( Node > StorageMgrInfo.OldLim) {                                  \
 454       UPD_NEW_IN_PLACE_NOPTRS(); /*ticky*/                              \
 455       AWAKEN_BQ(Node);                                                  \
 456   } else {                                                              \
 457       UPD_OLD_IN_PLACE_NOPTRS(); /*ticky*/                              \
 458       if(ALREADY_LINKED(Node)) {                                        \
 459           /* We are already on the old mutables list, so we             \
 460              can't update in place any more */                          \
 461           HEAP_CHK(live_regs_mask, _FHS+MIN_UPD_SIZE, 0);               \
 462             /* ticky-ticky (NB: was ALLOC_UPD_CON) */                   \
 463           ALLOC_CON(_FHS,1,MIN_UPD_SIZE-1,_FHS+MIN_UPD_SIZE);           \
 464           CC_ALLOC(CCC,_FHS+MIN_UPD_SIZE,CON_K);                        \
 465           /* must awaken after any possible GC */                       \
 466           AWAKEN_BQ(Node);                                              \
 467           SET_INFO_PTR(Node, Ind_info_TO_USE);                          \
 468           IND_CLOSURE_PTR(Node) = (W_)(Hp-(_FHS+MIN_UPD_SIZE-1));       \
 469           Node = Hp-(_FHS+MIN_UPD_SIZE-1);                              \
 470       }                                                                 \
 471   }
 472
 473 #define UPD_INPLACE_PTRS(live_regs_mask)                                \
 474   UPDATED_SET_UPDATED(Node); /* ticky */                                \
 475   if ( Node > StorageMgrInfo.OldLim) {                                  \
 476       UPD_NEW_IN_PLACE_PTRS(); /*ticky*/                                \
 477       AWAKEN_BQ(Node);                                                  \
 478   } else {                                                              \
 479       /* redirect update with indirection */                            \
 480       UPD_OLD_IN_PLACE_PTRS(); /*ticky*/                                \
 481       /* Allocate */                                                    \
 482       HEAP_CHK(live_regs_mask, _FHS+MIN_UPD_SIZE, 0);                   \
 483         /* ticky-ticky (NB: was ALLOC_UPD_CON) */                       \
 484       ALLOC_CON(_FHS,1,MIN_UPD_SIZE-1,_FHS+MIN_UPD_SIZE);               \
 485       CC_ALLOC(CCC,_FHS+MIN_UPD_SIZE,CON_K);                            \
 486                                                                         \
 487       if (!ALREADY_LINKED(Node)) {                                      \
 488           MUT_LINK(Node) = (W_) StorageMgrInfo.OldMutables;             \
 489           StorageMgrInfo.OldMutables = (P_) (Node);                     \
 490       }                                                                 \
 491       /* must awaken after any possible GC */                           \
 492       AWAKEN_BQ(Node);                                                  \
 493       SET_INFO_PTR(Node, Ind_info_TO_USE);                              \
 494       IND_CLOSURE_PTR(Node) = (W_)(Hp-(_FHS+MIN_UPD_SIZE-1));           \
 495       Node = Hp-(_FHS+MIN_UPD_SIZE-1);                                  \
 496   }
 497 # endif /* GCap || GCgn */
 498 #endif
 499 \end{code}
 500
 501 %************************************************************************
 502 %*                                                                      *
 503 \subsection[freezing-arrays]{Changing Mutable Pointer closures into Immutable Closures}
 504 %*                                                                      *
 505 %************************************************************************
 506
 507 When freezing an array of pointers we change the info table to
 508 indicate it is now immutable to the garbage collector. The array will
 509 be removed from the old generation mutable array list by the garbage\
 510 collector.
 511
 512 This is only required for generational garbage collectors but we always
 513 do it so better profiling information is provided.
 514
 515 \begin{code}
 516 #ifdef GC_MUT_REQUIRED
 517 #define FREEZE_MUT_HDR(freezeclosure,immutinfo) \
 518         SET_INFO_PTR(freezeclosure, immutinfo)
 519 #else
 520 #define FREEZE_MUT_HDR(freezeclosure,immutinfo) \
 521         SET_INFO_PTR(freezeclosure, immutinfo)
 522 #endif
 523
 524 #endif /* SMUPDATE_H */
 525 \end{code}