includes/rts/storage/Closures.h

   1 /* ----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 1998-2004
   4  *
   5  * Closures
   6  *
   7  * -------------------------------------------------------------------------- */
   8
   9 #ifndef RTS_STORAGE_CLOSURES_H
  10 #define RTS_STORAGE_CLOSURES_H
  11
  12 /*
  13  * The Layout of a closure header depends on which kind of system we're
  14  * compiling for: profiling, parallel, ticky, etc.
  15  */
  16
  17 /* -----------------------------------------------------------------------------
  18    The profiling header
  19    -------------------------------------------------------------------------- */
  20
  21 typedef struct {
  22   CostCentreStack *ccs;
  23   union {
  24     struct _RetainerSet *rs;  /* Retainer Set */
  25     StgWord ldvw;             /* Lag/Drag/Void Word */
  26   } hp;
  27 } StgProfHeader;
  28
  29 /* -----------------------------------------------------------------------------
  30    The SMP header
  31
  32    A thunk has a padding word to take the updated value.  This is so
  33    that the update doesn't overwrite the payload, so we can avoid
  34    needing to lock the thunk during entry and update.
  35
  36    Note: this doesn't apply to THUNK_STATICs, which have no payload.
  37
  38    Note: we leave this padding word in all ways, rather than just SMP,
  39    so that we don't have to recompile all our libraries for SMP.
  40    -------------------------------------------------------------------------- */
  41
  42 typedef struct {
  43     StgWord pad;
  44 } StgSMPThunkHeader;
  45
  46 /* -----------------------------------------------------------------------------
  47    The full fixed-size closure header
  48
  49    The size of the fixed header is the sum of the optional parts plus a single
  50    word for the entry code pointer.
  51    -------------------------------------------------------------------------- */
  52
  53 typedef struct {
  54     const StgInfoTable* info;
  55 #ifdef PROFILING
  56     StgProfHeader         prof;
  57 #endif
  58 } StgHeader;
  59
  60 typedef struct {
  61     const StgInfoTable* info;
  62 #ifdef PROFILING
  63     StgProfHeader         prof;
  64 #endif
  65     StgSMPThunkHeader     smp;
  66 } StgThunkHeader;
  67
  68 #define THUNK_EXTRA_HEADER_W (sizeofW(StgThunkHeader)-sizeofW(StgHeader))
  69
  70 /* -----------------------------------------------------------------------------
  71    Closure Types
  72
  73    For any given closure type (defined in InfoTables.h), there is a
  74    corresponding structure defined below.  The name of the structure
  75    is obtained by concatenating the closure type with '_closure'
  76    -------------------------------------------------------------------------- */
  77
  78 /* All closures follow the generic format */
  79
  80 typedef struct StgClosure_ {
  81     StgHeader   header;
  82     struct StgClosure_ *payload[FLEXIBLE_ARRAY];
  83 } *StgClosurePtr; // StgClosure defined in Rts.h
  84
  85 typedef struct {
  86     StgThunkHeader  header;
  87     struct StgClosure_ *payload[FLEXIBLE_ARRAY];
  88 } StgThunk;
  89
  90 typedef struct {
  91     StgThunkHeader   header;
  92     StgClosure *selectee;
  93 } StgSelector;
  94
  95 typedef struct {
  96     StgHeader   header;
  97     StgHalfWord arity;          /* zero if it is an AP */
  98     StgHalfWord n_args;
  99     StgClosure *fun;            /* really points to a fun */
 100     StgClosure *payload[FLEXIBLE_ARRAY];
 101 } StgPAP;
 102
 103 typedef struct {
 104     StgThunkHeader   header;
 105     StgHalfWord arity;          /* zero if it is an AP */
 106     StgHalfWord n_args;
 107     StgClosure *fun;            /* really points to a fun */
 108     StgClosure *payload[FLEXIBLE_ARRAY];
 109 } StgAP;
 110
 111 typedef struct {
 112     StgThunkHeader   header;
 113     StgWord     size;                    /* number of words in payload */
 114     StgClosure *fun;
 115     StgClosure *payload[FLEXIBLE_ARRAY]; /* contains a chunk of *stack* */
 116 } StgAP_STACK;
 117
 118 typedef struct {
 119     StgHeader   header;
 120     StgClosure *indirectee;
 121 } StgInd;
 122
 123 typedef struct {
 124     StgHeader     header;
 125     StgClosure   *indirectee;
 126     StgClosure   *static_link;
 127     StgInfoTable *saved_info;
 128 } StgIndStatic;
 129
 130 typedef struct StgBlockingQueue_ {
 131     StgHeader   header;
 132     struct StgBlockingQueue_ *link; // here so it looks like an IND
 133     StgClosure *bh;  // the BLACKHOLE
 134     StgTSO     *owner;
 135     struct MessageBlackHole_ *queue;
 136 } StgBlockingQueue;
 137
 138 typedef struct {
 139     StgHeader  header;
 140     StgWord    words;
 141     StgWord    payload[FLEXIBLE_ARRAY];
 142 } StgArrWords;
 143
 144 typedef struct {
 145     StgHeader   header;
 146     StgWord     ptrs;
 147     StgWord     size; // ptrs plus card table
 148     StgClosure *payload[FLEXIBLE_ARRAY];
 149     // see also: StgMutArrPtrs macros in ClosureMacros.h
 150 } StgMutArrPtrs;
 151
 152 typedef struct {
 153     StgHeader   header;
 154     StgClosure *var;
 155 } StgMutVar;
 156
 157 typedef struct _StgUpdateFrame {
 158     StgHeader  header;
 159     StgClosure *updatee;
 160 } StgUpdateFrame;
 161
 162 typedef struct {
 163     StgHeader  header;
 164     StgInt      exceptions_blocked;
 165     StgClosure *handler;
 166 } StgCatchFrame;
 167
 168 typedef struct {
 169     StgHeader  header;
 170 } StgStopFrame;
 171
 172 typedef struct {
 173   StgHeader header;
 174   StgWord data;
 175 } StgIntCharlikeClosure;
 176
 177 /* statically allocated */
 178 typedef struct {
 179   StgHeader  header;
 180 } StgRetry;
 181
 182 typedef struct _StgStableName {
 183   StgHeader      header;
 184   StgWord        sn;
 185 } StgStableName;
 186
 187 typedef struct _StgWeak {       /* Weak v */
 188   StgHeader header;
 189   StgClosure *cfinalizer;
 190   StgClosure *key;
 191   StgClosure *value;            /* v */
 192   StgClosure *finalizer;
 193   struct _StgWeak *link;
 194 } StgWeak;
 195
 196 typedef struct _StgDeadWeak {   /* Weak v */
 197   StgHeader header;
 198   struct _StgWeak *link;
 199 } StgDeadWeak;
 200
 201 /* Byte code objects.  These are fixed size objects with pointers to
 202  * four arrays, designed so that a BCO can be easily "re-linked" to
 203  * other BCOs, to facilitate GHC's intelligent recompilation.  The
 204  * array of instructions is static and not re-generated when the BCO
 205  * is re-linked, but the other 3 arrays will be regenerated.
 206  *
 207  * A BCO represents either a function or a stack frame.  In each case,
 208  * it needs a bitmap to describe to the garbage collector the
 209  * pointerhood of its arguments/free variables respectively, and in
 210  * the case of a function it also needs an arity.  These are stored
 211  * directly in the BCO, rather than in the instrs array, for two
 212  * reasons:
 213  * (a) speed: we need to get at the bitmap info quickly when
 214  *     the GC is examining APs and PAPs that point to this BCO
 215  * (b) a subtle interaction with the compacting GC.  In compacting
 216  *     GC, the info that describes the size/layout of a closure
 217  *     cannot be in an object more than one level of indirection
 218  *     away from the current object, because of the order in
 219  *     which pointers are updated to point to their new locations.
 220  */
 221
 222 typedef struct {
 223     StgHeader      header;
 224     StgArrWords   *instrs;      /* a pointer to an ArrWords */
 225     StgArrWords   *literals;    /* a pointer to an ArrWords */
 226     StgMutArrPtrs *ptrs;        /* a pointer to a  MutArrPtrs */
 227     StgHalfWord   arity;        /* arity of this BCO */
 228     StgHalfWord   size;         /* size of this BCO (in words) */
 229     StgWord       bitmap[FLEXIBLE_ARRAY];  /* an StgLargeBitmap */
 230 } StgBCO;
 231
 232 #define BCO_BITMAP(bco)      ((StgLargeBitmap *)((StgBCO *)(bco))->bitmap)
 233 #define BCO_BITMAP_SIZE(bco) (BCO_BITMAP(bco)->size)
 234 #define BCO_BITMAP_BITS(bco) (BCO_BITMAP(bco)->bitmap)
 235 #define BCO_BITMAP_SIZEW(bco) ((BCO_BITMAP_SIZE(bco) + BITS_IN(StgWord) - 1) \
 236                                 / BITS_IN(StgWord))
 237
 238 /* -----------------------------------------------------------------------------
 239    Dynamic stack frames for generic heap checks.
 240
 241    These generic heap checks are slow, but have the advantage of being
 242    usable in a variety of situations.
 243
 244    The one restriction is that any relevant SRTs must already be pointed
 245    to from the stack.  The return address doesn't need to have an info
 246    table attached: hence it can be any old code pointer.
 247
 248    The liveness mask contains a 1 at bit n, if register Rn contains a
 249    non-pointer.  The contents of all 8 vanilla registers are always saved
 250    on the stack; the liveness mask tells the GC which ones contain
 251    pointers.
 252
 253    Good places to use a generic heap check:
 254
 255         - case alternatives (the return address with an SRT is already
 256           on the stack).
 257
 258         - primitives (no SRT required).
 259
 260    The stack frame layout for a RET_DYN is like this:
 261
 262           some pointers         |-- RET_DYN_PTRS(liveness) words
 263           some nonpointers      |-- RET_DYN_NONPTRS(liveness) words
 264
 265           L1                    \
 266           D1-2                  |-- RET_DYN_NONPTR_REGS_SIZE words
 267           F1-4                  /
 268
 269           R1-8                  |-- RET_DYN_BITMAP_SIZE words
 270
 271           return address        \
 272           liveness mask         |-- StgRetDyn structure
 273           stg_gen_chk_info      /
 274
 275    we assume that the size of a double is always 2 pointers (wasting a
 276    word when it is only one pointer, but avoiding lots of #ifdefs).
 277
 278    See Liveness.h for the macros (RET_DYN_PTRS() etc.).
 279
 280    NOTE: if you change the layout of RET_DYN stack frames, then you
 281    might also need to adjust the value of RESERVED_STACK_WORDS in
 282    Constants.h.
 283    -------------------------------------------------------------------------- */
 284
 285 typedef struct {
 286     const StgInfoTable* info;
 287     StgWord        liveness;
 288     StgWord        ret_addr;
 289     StgClosure *   payload[FLEXIBLE_ARRAY];
 290 } StgRetDyn;
 291
 292 /* A function return stack frame: used when saving the state for a
 293  * garbage collection at a function entry point.  The function
 294  * arguments are on the stack, and we also save the function (its
 295  * info table describes the pointerhood of the arguments).
 296  *
 297  * The stack frame size is also cached in the frame for convenience.
 298  */
 299 typedef struct {
 300     const StgInfoTable* info;
 301     StgWord        size;
 302     StgClosure *   fun;
 303     StgClosure *   payload[FLEXIBLE_ARRAY];
 304 } StgRetFun;
 305
 306 /* Concurrent communication objects */
 307
 308 typedef struct StgMVarTSOQueue_ {
 309     StgHeader                header;
 310     struct StgMVarTSOQueue_ *link;
 311     struct StgTSO_          *tso;
 312 } StgMVarTSOQueue;
 313
 314 typedef struct {
 315     StgHeader                header;
 316     struct StgMVarTSOQueue_ *head;
 317     struct StgMVarTSOQueue_ *tail;
 318     StgClosure*              value;
 319 } StgMVar;
 320
 321
 322 /* STM data structures
 323  *
 324  *  StgTVar defines the only type that can be updated through the STM
 325  *  interface.
 326  *
 327  *  Note that various optimisations may be possible in order to use less
 328  *  space for these data structures at the cost of more complexity in the
 329  *  implementation:
 330  *
 331  *   - In StgTVar, current_value and first_watch_queue_entry could be held in
 332  *     the same field: if any thread is waiting then its expected_value for
 333  *     the tvar is the current value.
 334  *
 335  *   - In StgTRecHeader, it might be worthwhile having separate chunks
 336  *     of read-only and read-write locations.  This would save a
 337  *     new_value field in the read-only locations.
 338  *
 339  *   - In StgAtomicallyFrame, we could combine the waiting bit into
 340  *     the header (maybe a different info tbl for a waiting transaction).
 341  *     This means we can specialise the code for the atomically frame
 342  *     (it immediately switches on frame->waiting anyway).
 343  */
 344
 345 typedef struct StgTRecHeader_ StgTRecHeader;
 346
 347 typedef struct StgTVarWatchQueue_ {
 348   StgHeader                  header;
 349   StgClosure                *closure; // StgTSO or StgAtomicInvariant
 350   struct StgTVarWatchQueue_ *next_queue_entry;
 351   struct StgTVarWatchQueue_ *prev_queue_entry;
 352 } StgTVarWatchQueue;
 353
 354 typedef struct {
 355   StgHeader                  header;
 356   StgClosure                *volatile current_value;
 357   StgTVarWatchQueue         *volatile first_watch_queue_entry;
 358 #if defined(THREADED_RTS)
 359   StgInt                     volatile num_updates;
 360 #endif
 361 } StgTVar;
 362
 363 typedef struct {
 364   StgHeader      header;
 365   StgClosure    *code;
 366   StgTRecHeader *last_execution;
 367   StgWord        lock;
 368 } StgAtomicInvariant;
 369
 370 /* new_value == expected_value for read-only accesses */
 371 /* new_value is a StgTVarWatchQueue entry when trec in state TREC_WAITING */
 372 typedef struct {
 373   StgTVar                   *tvar;
 374   StgClosure                *expected_value;
 375   StgClosure                *new_value;
 376 #if defined(THREADED_RTS)
 377   StgInt                     num_updates;
 378 #endif
 379 } TRecEntry;
 380
 381 #define TREC_CHUNK_NUM_ENTRIES 16
 382
 383 typedef struct StgTRecChunk_ {
 384   StgHeader                  header;
 385   struct StgTRecChunk_      *prev_chunk;
 386   StgWord                    next_entry_idx;
 387   TRecEntry                  entries[TREC_CHUNK_NUM_ENTRIES];
 388 } StgTRecChunk;
 389
 390 typedef enum {
 391   TREC_ACTIVE,        /* Transaction in progress, outcome undecided */
 392   TREC_CONDEMNED,     /* Transaction in progress, inconsistent / out of date reads */
 393   TREC_COMMITTED,     /* Transaction has committed, now updating tvars */
 394   TREC_ABORTED,       /* Transaction has aborted, now reverting tvars */
 395   TREC_WAITING,       /* Transaction currently waiting */
 396 } TRecState;
 397
 398 typedef struct StgInvariantCheckQueue_ {
 399   StgHeader                       header;
 400   StgAtomicInvariant             *invariant;
 401   StgTRecHeader                  *my_execution;
 402   struct StgInvariantCheckQueue_ *next_queue_entry;
 403 } StgInvariantCheckQueue;
 404
 405 struct StgTRecHeader_ {
 406   StgHeader                  header;
 407   struct StgTRecHeader_     *enclosing_trec;
 408   StgTRecChunk              *current_chunk;
 409   StgInvariantCheckQueue    *invariants_to_check;
 410   TRecState                  state;
 411 };
 412
 413 typedef struct {
 414   StgHeader   header;
 415   StgClosure *code;
 416   StgTVarWatchQueue *next_invariant_to_check;
 417   StgClosure *result;
 418 } StgAtomicallyFrame;
 419
 420 typedef struct {
 421   StgHeader   header;
 422   StgClosure *code;
 423   StgClosure *handler;
 424 } StgCatchSTMFrame;
 425
 426 typedef struct {
 427   StgHeader      header;
 428   StgBool        running_alt_code;
 429   StgClosure    *first_code;
 430   StgClosure    *alt_code;
 431 } StgCatchRetryFrame;
 432
 433 /* ----------------------------------------------------------------------------
 434    Messages
 435    ------------------------------------------------------------------------- */
 436
 437 typedef struct Message_ {
 438     StgHeader        header;
 439     struct Message_ *link;
 440 } Message;
 441
 442 typedef struct MessageWakeup_ {
 443     StgHeader header;
 444     Message  *link;
 445     StgTSO   *tso;
 446 } MessageWakeup;
 447
 448 typedef struct MessageThrowTo_ {
 449     StgHeader   header;
 450     struct MessageThrowTo_ *link;
 451     StgTSO     *source;
 452     StgTSO     *target;
 453     StgClosure *exception;
 454 } MessageThrowTo;
 455
 456 typedef struct MessageBlackHole_ {
 457     StgHeader   header;
 458     struct MessageBlackHole_ *link;
 459     StgTSO     *tso;
 460     StgClosure *bh;
 461 } MessageBlackHole;
 462
 463 #endif /* RTS_STORAGE_CLOSURES_H */