Closures.h 15.5 KB
Newer Older
1
/* ----------------------------------------------------------------------------
2
 *
3
 * (c) The GHC Team, 1998-2004
4 5 6 7 8
 *
 * Closures
 *
 * -------------------------------------------------------------------------- */

9
#pragma once
10 11 12 13 14 15 16 17 18 19 20

/*
 * The Layout of a closure header depends on which kind of system we're
 * compiling for: profiling, parallel, ticky, etc.
 */

/* -----------------------------------------------------------------------------
   The profiling header
   -------------------------------------------------------------------------- */

typedef struct {
21 22
  CostCentreStack *ccs;
  union {
23 24 25 26 27 28 29 30 31 32 33 34 35 36

    union {
      /* Accessor for the least significant bit of the entire union. Invariant:
       * This must be at least as large as the largest field in this union for
       * this to work. If you add more fields make sure you maintain this.
       *
       * See Note [Profiling heap traversal visited bit].
       */
      StgWord lsb;

      /* Retainer Set */
      struct _RetainerSet *rs;
    } trav;

37
    StgWord ldvw;             /* Lag/Drag/Void Word */
38
  } hp;
39 40
} StgProfHeader;

41 42
/* -----------------------------------------------------------------------------
   The SMP header
43

44 45 46
   A thunk has a padding word to take the updated value.  This is so
   that the update doesn't overwrite the payload, so we can avoid
   needing to lock the thunk during entry and update.
47

48 49 50 51
   Note: this doesn't apply to THUNK_STATICs, which have no payload.

   Note: we leave this padding word in all ways, rather than just SMP,
   so that we don't have to recompile all our libraries for SMP.
52 53 54 55 56 57
   -------------------------------------------------------------------------- */

typedef struct {
    StgWord pad;
} StgSMPThunkHeader;

58 59 60 61 62 63 64 65
/* -----------------------------------------------------------------------------
   The full fixed-size closure header

   The size of the fixed header is the sum of the optional parts plus a single
   word for the entry code pointer.
   -------------------------------------------------------------------------- */

typedef struct {
Simon Marlow's avatar
Simon Marlow committed
66
    const StgInfoTable* info;
Ben Gamari's avatar
Ben Gamari committed
67
#if defined(PROFILING)
68
    StgProfHeader         prof;
sof's avatar
sof committed
69
#endif
70 71
} StgHeader;

72
typedef struct {
Simon Marlow's avatar
Simon Marlow committed
73
    const StgInfoTable* info;
Ben Gamari's avatar
Ben Gamari committed
74
#if defined(PROFILING)
75 76 77 78 79
    StgProfHeader         prof;
#endif
    StgSMPThunkHeader     smp;
} StgThunkHeader;

80 81
#define THUNK_EXTRA_HEADER_W (sizeofW(StgThunkHeader)-sizeofW(StgHeader))

82 83 84 85 86 87 88 89 90 91
/* -----------------------------------------------------------------------------
   Closure Types

   For any given closure type (defined in InfoTables.h), there is a
   corresponding structure defined below.  The name of the structure
   is obtained by concatenating the closure type with '_closure'
   -------------------------------------------------------------------------- */

/* All closures follow the generic format */

Simon Marlow's avatar
Simon Marlow committed
92
typedef struct StgClosure_ {
93
    StgHeader   header;
94
    struct StgClosure_ *payload[];
Simon Marlow's avatar
Simon Marlow committed
95
} *StgClosurePtr; // StgClosure defined in rts/Types.h
96

Ben Gamari's avatar
Ben Gamari committed
97
typedef struct StgThunk_ {
98
    StgThunkHeader  header;
99
    struct StgClosure_ *payload[];
100 101 102 103
} StgThunk;

typedef struct {
    StgThunkHeader   header;
104 105 106
    StgClosure *selectee;
} StgSelector;

107 108 109 110 111 112
/*
   PAP payload contains pointers and non-pointers interleaved and we only have
   one info table for PAPs (stg_PAP_info). To visit pointers in a PAP payload we
   use the `fun`s bitmap. For a PAP with n_args arguments the first n_args bits
   in the fun's bitmap tell us which payload locations contain pointers.
*/
113 114
typedef struct {
    StgHeader   header;
115
    StgHalfWord arity;          /* zero if it is an AP */
116
    StgHalfWord n_args;
117
    StgClosure *fun;            /* really points to a fun */
118
    StgClosure *payload[];
119 120
} StgPAP;

121 122
typedef struct {
    StgThunkHeader   header;
123
    StgHalfWord arity;          /* zero if it is an AP */
124
    StgHalfWord n_args;
125
    StgClosure *fun;            /* really points to a fun */
126
    StgClosure *payload[];
127
} StgAP;
128

129
typedef struct {
130
    StgThunkHeader   header;
131
    StgWord     size;                    /* number of words in payload */
132
    StgClosure *fun;
133
    StgClosure *payload[]; /* contains a chunk of *stack* */
134
} StgAP_STACK;
135 136 137 138 139 140 141

typedef struct {
    StgHeader   header;
    StgClosure *indirectee;
} StgInd;

typedef struct {
142
    StgHeader     header;
143
    StgClosure   *indirectee;
144
    StgClosure   *static_link; // See Note [CAF lists]
Simon Marlow's avatar
Simon Marlow committed
145
    const StgInfoTable *saved_info;
146
        // `saved_info` also used for the link field for `debug_caf_list`,
Ben Gamari's avatar
Ben Gamari committed
147
        // see `newCAF` and Note [CAF lists] in rts/sm/Storage.h.
148
} StgIndStatic;
149

150 151
typedef struct StgBlockingQueue_ {
    StgHeader   header;
152 153 154
    struct StgBlockingQueue_ *link;
        // here so it looks like an IND, to be able to skip the queue without
        // deleting it (done in wakeBlockingQueue())
155 156 157
    StgClosure *bh;  // the BLACKHOLE
    StgTSO     *owner;
    struct MessageBlackHole_ *queue;
158
        // holds TSOs blocked on `bh`
159 160
} StgBlockingQueue;

161 162
typedef struct {
    StgHeader  header;
163
    StgWord    bytes;
164
    StgWord    payload[];
siddhanathan's avatar
siddhanathan committed
165
} StgArrBytes;
166 167 168 169

typedef struct {
    StgHeader   header;
    StgWord     ptrs;
170
    StgWord     size; // ptrs plus card table
171
    StgClosure *payload[];
172
    // see also: StgMutArrPtrs macros in ClosureMacros.h
173
} StgMutArrPtrs;
174

175 176 177
typedef struct {
    StgHeader   header;
    StgWord     ptrs;
178
    StgClosure *payload[];
179 180
} StgSmallMutArrPtrs;

181 182 183 184 185 186 187 188 189 190 191 192
typedef struct {
    StgHeader   header;
    StgClosure *var;
} StgMutVar;

typedef struct _StgUpdateFrame {
    StgHeader  header;
    StgClosure *updatee;
} StgUpdateFrame;

typedef struct {
    StgHeader  header;
193
    StgWord    exceptions_blocked;
194 195 196
    StgClosure *handler;
} StgCatchFrame;

197 198 199 200 201
typedef struct {
    const StgInfoTable* info;
    struct StgStack_ *next_chunk;
} StgUnderflowFrame;

202 203
typedef struct {
    StgHeader  header;
204
} StgStopFrame;
205 206 207 208 209 210 211 212 213 214 215

typedef struct {
  StgHeader header;
  StgWord data;
} StgIntCharlikeClosure;

/* statically allocated */
typedef struct {
  StgHeader  header;
} StgRetry;

216 217 218 219
typedef struct _StgStableName {
  StgHeader      header;
  StgWord        sn;
} StgStableName;
220

221
typedef struct _StgWeak {       /* Weak v */
222
  StgHeader header;
223
  StgClosure *cfinalizers;
224
  StgClosure *key;
225
  StgClosure *value;            /* v */
226
  StgClosure *finalizer;
227 228 229
  struct _StgWeak *link;
} StgWeak;

230
typedef struct _StgCFinalizerList {
231
  StgHeader header;
232 233 234 235 236 237
  StgClosure *link;
  void (*fptr)(void);
  void *ptr;
  void *eptr;
  StgWord flag; /* has environment (0 or 1) */
} StgCFinalizerList;
238

239 240 241 242 243 244 245 246 247
/* Byte code objects.  These are fixed size objects with pointers to
 * four arrays, designed so that a BCO can be easily "re-linked" to
 * other BCOs, to facilitate GHC's intelligent recompilation.  The
 * array of instructions is static and not re-generated when the BCO
 * is re-linked, but the other 3 arrays will be regenerated.
 *
 * A BCO represents either a function or a stack frame.  In each case,
 * it needs a bitmap to describe to the garbage collector the
 * pointerhood of its arguments/free variables respectively, and in
248 249 250 251 252 253 254 255 256 257
 * the case of a function it also needs an arity.  These are stored
 * directly in the BCO, rather than in the instrs array, for two
 * reasons:
 * (a) speed: we need to get at the bitmap info quickly when
 *     the GC is examining APs and PAPs that point to this BCO
 * (b) a subtle interaction with the compacting GC.  In compacting
 *     GC, the info that describes the size/layout of a closure
 *     cannot be in an object more than one level of indirection
 *     away from the current object, because of the order in
 *     which pointers are updated to point to their new locations.
258 259 260 261
 */

typedef struct {
    StgHeader      header;
siddhanathan's avatar
siddhanathan committed
262 263
    StgArrBytes   *instrs;      /* a pointer to an ArrWords */
    StgArrBytes   *literals;    /* a pointer to an ArrWords */
264
    StgMutArrPtrs *ptrs;        /* a pointer to a  MutArrPtrs */
265 266
    StgHalfWord   arity;        /* arity of this BCO */
    StgHalfWord   size;         /* size of this BCO (in words) */
267
    StgWord       bitmap[];  /* an StgLargeBitmap */
268 269
} StgBCO;

270
#define BCO_BITMAP(bco)      ((StgLargeBitmap *)((StgBCO *)(bco))->bitmap)
271 272 273
#define BCO_BITMAP_SIZE(bco) (BCO_BITMAP(bco)->size)
#define BCO_BITMAP_BITS(bco) (BCO_BITMAP(bco)->bitmap)
#define BCO_BITMAP_SIZEW(bco) ((BCO_BITMAP_SIZE(bco) + BITS_IN(StgWord) - 1) \
274
                                / BITS_IN(StgWord))
275 276 277 278 279 280 281

/* A function return stack frame: used when saving the state for a
 * garbage collection at a function entry point.  The function
 * arguments are on the stack, and we also save the function (its
 * info table describes the pointerhood of the arguments).
 *
 * The stack frame size is also cached in the frame for convenience.
282 283 284
 *
 * The only RET_FUN is stg_gc_fun, which is created by __stg_gc_fun,
 * both in HeapStackCheck.cmm.
285 286
 */
typedef struct {
Simon Marlow's avatar
Simon Marlow committed
287
    const StgInfoTable* info;
288
    StgWord        size;
289
    StgClosure *   fun;
290
    StgClosure *   payload[];
291 292
} StgRetFun;

293 294
/* Concurrent communication objects */

295 296 297 298 299 300
typedef struct StgMVarTSOQueue_ {
    StgHeader                header;
    struct StgMVarTSOQueue_ *link;
    struct StgTSO_          *tso;
} StgMVarTSOQueue;

301
typedef struct {
302 303 304 305
    StgHeader                header;
    struct StgMVarTSOQueue_ *head;
    struct StgMVarTSOQueue_ *tail;
    StgClosure*              value;
306 307
} StgMVar;

308

309 310 311 312
/* STM data structures
 *
 *  StgTVar defines the only type that can be updated through the STM
 *  interface.
313
 *
314 315 316 317
 *  Note that various optimisations may be possible in order to use less
 *  space for these data structures at the cost of more complexity in the
 *  implementation:
 *
tharris@microsoft.com's avatar
tharris@microsoft.com committed
318
 *   - In StgTVar, current_value and first_watch_queue_entry could be held in
319
 *     the same field: if any thread is waiting then its expected_value for
320
 *     the tvar is the current value.
321 322 323 324
 *
 *   - In StgTRecHeader, it might be worthwhile having separate chunks
 *     of read-only and read-write locations.  This would save a
 *     new_value field in the read-only locations.
325 326 327 328 329
 *
 *   - In StgAtomicallyFrame, we could combine the waiting bit into
 *     the header (maybe a different info tbl for a waiting transaction).
 *     This means we can specialise the code for the atomically frame
 *     (it immediately switches on frame->waiting anyway).
330 331
 */

tharris@microsoft.com's avatar
tharris@microsoft.com committed
332 333 334
typedef struct StgTRecHeader_ StgTRecHeader;

typedef struct StgTVarWatchQueue_ {
335
  StgHeader                  header;
336
  StgClosure                *closure; // StgTSO
tharris@microsoft.com's avatar
tharris@microsoft.com committed
337 338 339
  struct StgTVarWatchQueue_ *next_queue_entry;
  struct StgTVarWatchQueue_ *prev_queue_entry;
} StgTVarWatchQueue;
340 341 342

typedef struct {
  StgHeader                  header;
343
  StgClosure                *volatile current_value;
tharris@microsoft.com's avatar
tharris@microsoft.com committed
344
  StgTVarWatchQueue         *volatile first_watch_queue_entry;
345
  StgInt                     volatile num_updates;
346 347
} StgTVar;

348
/* new_value == expected_value for read-only accesses */
tharris@microsoft.com's avatar
tharris@microsoft.com committed
349
/* new_value is a StgTVarWatchQueue entry when trec in state TREC_WAITING */
350 351 352
typedef struct {
  StgTVar                   *tvar;
  StgClosure                *expected_value;
353
  StgClosure                *new_value;
354
#if defined(THREADED_RTS)
355
  StgInt                     num_updates;
356
#endif
357 358
} TRecEntry;

359
#define TREC_CHUNK_NUM_ENTRIES 16
360 361 362 363 364 365 366 367

typedef struct StgTRecChunk_ {
  StgHeader                  header;
  struct StgTRecChunk_      *prev_chunk;
  StgWord                    next_entry_idx;
  TRecEntry                  entries[TREC_CHUNK_NUM_ENTRIES];
} StgTRecChunk;

368
typedef enum {
369
  TREC_ACTIVE,        /* Transaction in progress, outcome undecided */
370
  TREC_CONDEMNED,     /* Transaction in progress, inconsistent / out of date reads */
371 372 373
  TREC_COMMITTED,     /* Transaction has committed, now updating tvars */
  TREC_ABORTED,       /* Transaction has aborted, now reverting tvars */
  TREC_WAITING,       /* Transaction currently waiting */
374 375
} TRecState;

tharris@microsoft.com's avatar
tharris@microsoft.com committed
376
struct StgTRecHeader_ {
377 378 379
  StgHeader                  header;
  struct StgTRecHeader_     *enclosing_trec;
  StgTRecChunk              *current_chunk;
380
  TRecState                  state;
tharris@microsoft.com's avatar
tharris@microsoft.com committed
381
};
382 383

typedef struct {
tharris@microsoft.com's avatar
tharris@microsoft.com committed
384 385
  StgHeader   header;
  StgClosure *code;
386
  StgClosure *result;
387 388 389
} StgAtomicallyFrame;

typedef struct {
tharris@microsoft.com's avatar
tharris@microsoft.com committed
390 391 392
  StgHeader   header;
  StgClosure *code;
  StgClosure *handler;
393 394 395
} StgCatchSTMFrame;

typedef struct {
tharris@microsoft.com's avatar
tharris@microsoft.com committed
396
  StgHeader      header;
397
  StgWord        running_alt_code;
tharris@microsoft.com's avatar
tharris@microsoft.com committed
398 399
  StgClosure    *first_code;
  StgClosure    *alt_code;
400 401
} StgCatchRetryFrame;

402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
/* ----------------------------------------------------------------------------
   Messages
   ------------------------------------------------------------------------- */

typedef struct Message_ {
    StgHeader        header;
    struct Message_ *link;
} Message;

typedef struct MessageWakeup_ {
    StgHeader header;
    Message  *link;
    StgTSO   *tso;
} MessageWakeup;

typedef struct MessageThrowTo_ {
    StgHeader   header;
419
    struct MessageThrowTo_ *link;
420 421 422 423 424
    StgTSO     *source;
    StgTSO     *target;
    StgClosure *exception;
} MessageThrowTo;

425 426 427
typedef struct MessageBlackHole_ {
    StgHeader   header;
    struct MessageBlackHole_ *link;
428 429
        // here so it looks like an IND, to be able to skip the message without
        // deleting it (done in throwToMsg())
430 431 432 433
    StgTSO     *tso;
    StgClosure *bh;
} MessageBlackHole;

434 435 436 437 438 439 440 441 442 443
/* ----------------------------------------------------------------------------
   Compact Regions
   ------------------------------------------------------------------------- */

//
// A compact region is a list of blocks.  Each block starts with an
// StgCompactNFDataBlock structure, and the list is chained through the next
// field of these structs.  (the link field of the bdescr is used to chain
// together multiple compact region on the compact_objects field of a
// generation).
gcampax's avatar
gcampax committed
444 445
//
// See Note [Compact Normal Forms] for details
446
//
gcampax's avatar
gcampax committed
447
typedef struct StgCompactNFDataBlock_ {
448 449 450 451 452 453 454 455 456 457 458 459
    struct StgCompactNFDataBlock_ *self;
       // the address of this block this is copied over to the
       // receiving end when serializing a compact, so the receiving
       // end can allocate the block at best as it can, and then
       // verify if pointer adjustment is needed or not by comparing
       // self with the actual address; the same data is sent over as
       // SerializedCompact metadata, but having it here simplifies
       // the fixup implementation.
    struct StgCompactNFData_ *owner;
       // the closure who owns this block (used in objectGetCompact)
    struct StgCompactNFDataBlock_ *next;
       // chain of blocks used for serialization and freeing
gcampax's avatar
gcampax committed
460 461
} StgCompactNFDataBlock;

462 463 464
//
// This is the Compact# primitive object.
//
gcampax's avatar
gcampax committed
465
typedef struct StgCompactNFData_ {
466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488
    StgHeader header;
      // for sanity and other checks in practice, nothing should ever
      // need the compact info pointer (we don't even need fwding
      // pointers because it's a large object)
    StgWord totalW;
      // Total number of words in all blocks in the compact
    StgWord autoBlockW;
      // size of automatically appended blocks
    StgPtr hp, hpLim;
      // the beginning and end of the free area in the nursery block.  This is
      // just a convenience so that we can avoid multiple indirections through
      // the nursery pointer below during compaction.
    StgCompactNFDataBlock *nursery;
      // where to (try to) allocate from when appending
    StgCompactNFDataBlock *last;
      // the last block of the chain (to know where to append new
      // blocks for resize)
    struct hashtable *hash;
      // the hash table for the current compaction, or NULL if
      // there's no (sharing-preserved) compaction in progress.
    StgClosure *result;
      // Used temporarily to store the result of compaction.  Doesn't need to be
      // a GC root.
489 490 491
    struct StgCompactNFData_ *link;
      // Used by compacting GC for linking CNFs with threaded hash tables. See
      // Note [CNFs in compacting GC] in Compact.c for details.
gcampax's avatar
gcampax committed
492
} StgCompactNFData;