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 {
 309   StgHeader       header;
 310   struct StgTSO_ *head;
 311   struct StgTSO_ *tail;
 312   StgClosure*     value;
 313 } StgMVar;
 314
 315
 316 /* STM data structures
 317  *
 318  *  StgTVar defines the only type that can be updated through the STM
 319  *  interface.
 320  *
 321  *  Note that various optimisations may be possible in order to use less
 322  *  space for these data structures at the cost of more complexity in the
 323  *  implementation:
 324  *
 325  *   - In StgTVar, current_value and first_watch_queue_entry could be held in
 326  *     the same field: if any thread is waiting then its expected_value for
 327  *     the tvar is the current value.
 328  *
 329  *   - In StgTRecHeader, it might be worthwhile having separate chunks
 330  *     of read-only and read-write locations.  This would save a
 331  *     new_value field in the read-only locations.
 332  *
 333  *   - In StgAtomicallyFrame, we could combine the waiting bit into
 334  *     the header (maybe a different info tbl for a waiting transaction).
 335  *     This means we can specialise the code for the atomically frame
 336  *     (it immediately switches on frame->waiting anyway).
 337  */
 338
 339 typedef struct StgTRecHeader_ StgTRecHeader;
 340
 341 typedef struct StgTVarWatchQueue_ {
 342   StgHeader                  header;
 343   StgClosure                *closure; // StgTSO or StgAtomicInvariant
 344   struct StgTVarWatchQueue_ *next_queue_entry;
 345   struct StgTVarWatchQueue_ *prev_queue_entry;
 346 } StgTVarWatchQueue;
 347
 348 typedef struct {
 349   StgHeader                  header;
 350   StgClosure                *volatile current_value;
 351   StgTVarWatchQueue         *volatile first_watch_queue_entry;
 352 #if defined(THREADED_RTS)
 353   StgInt                     volatile num_updates;
 354 #endif
 355 } StgTVar;
 356
 357 typedef struct {
 358   StgHeader      header;
 359   StgClosure    *code;
 360   StgTRecHeader *last_execution;
 361   StgWord        lock;
 362 } StgAtomicInvariant;
 363
 364 /* new_value == expected_value for read-only accesses */
 365 /* new_value is a StgTVarWatchQueue entry when trec in state TREC_WAITING */
 366 typedef struct {
 367   StgTVar                   *tvar;
 368   StgClosure                *expected_value;
 369   StgClosure                *new_value;
 370 #if defined(THREADED_RTS)
 371   StgInt                     num_updates;
 372 #endif
 373 } TRecEntry;
 374
 375 #define TREC_CHUNK_NUM_ENTRIES 16
 376
 377 typedef struct StgTRecChunk_ {
 378   StgHeader                  header;
 379   struct StgTRecChunk_      *prev_chunk;
 380   StgWord                    next_entry_idx;
 381   TRecEntry                  entries[TREC_CHUNK_NUM_ENTRIES];
 382 } StgTRecChunk;
 383
 384 typedef enum {
 385   TREC_ACTIVE,        /* Transaction in progress, outcome undecided */
 386   TREC_CONDEMNED,     /* Transaction in progress, inconsistent / out of date reads */
 387   TREC_COMMITTED,     /* Transaction has committed, now updating tvars */
 388   TREC_ABORTED,       /* Transaction has aborted, now reverting tvars */
 389   TREC_WAITING,       /* Transaction currently waiting */
 390 } TRecState;
 391
 392 typedef struct StgInvariantCheckQueue_ {
 393   StgHeader                       header;
 394   StgAtomicInvariant             *invariant;
 395   StgTRecHeader                  *my_execution;
 396   struct StgInvariantCheckQueue_ *next_queue_entry;
 397 } StgInvariantCheckQueue;
 398
 399 struct StgTRecHeader_ {
 400   StgHeader                  header;
 401   struct StgTRecHeader_     *enclosing_trec;
 402   StgTRecChunk              *current_chunk;
 403   StgInvariantCheckQueue    *invariants_to_check;
 404   TRecState                  state;
 405 };
 406
 407 typedef struct {
 408   StgHeader   header;
 409   StgClosure *code;
 410   StgTVarWatchQueue *next_invariant_to_check;
 411   StgClosure *result;
 412 } StgAtomicallyFrame;
 413
 414 typedef struct {
 415   StgHeader   header;
 416   StgClosure *code;
 417   StgClosure *handler;
 418 } StgCatchSTMFrame;
 419
 420 typedef struct {
 421   StgHeader      header;
 422   StgBool        running_alt_code;
 423   StgClosure    *first_code;
 424   StgClosure    *alt_code;
 425 } StgCatchRetryFrame;
 426
 427 /* ----------------------------------------------------------------------------
 428    Messages
 429    ------------------------------------------------------------------------- */
 430
 431 typedef struct Message_ {
 432     StgHeader        header;
 433     struct Message_ *link;
 434 } Message;
 435
 436 typedef struct MessageWakeup_ {
 437     StgHeader header;
 438     Message  *link;
 439     StgTSO   *tso;
 440 } MessageWakeup;
 441
 442 typedef struct MessageThrowTo_ {
 443     StgHeader   header;
 444     struct MessageThrowTo_ *link;
 445     StgTSO     *source;
 446     StgTSO     *target;
 447     StgClosure *exception;
 448 } MessageThrowTo;
 449
 450 typedef struct MessageBlackHole_ {
 451     StgHeader   header;
 452     struct MessageBlackHole_ *link;
 453     StgTSO     *tso;
 454     StgClosure *bh;
 455 } MessageBlackHole;
 456
 457 #endif /* RTS_STORAGE_CLOSURES_H */