/* ----------------------------------------------------------------------------
- * $Id: Closures.h,v 1.17 2000/03/31 03:09:35 hwloidl Exp $
*
- * (c) The GHC Team, 1998-1999
+ * (c) The GHC Team, 1998-2004
*
* Closures
*
The profiling header
-------------------------------------------------------------------------- */
-#ifdef PROFILING
-
-typedef struct {
- CostCentreStack *ccs;
-} StgProfHeader;
-
-#else /* !PROFILING */
-
typedef struct {
- /* empty */
+ CostCentreStack *ccs;
+ union {
+ struct _RetainerSet *rs; /* Retainer Set */
+ StgWord ldvw; /* Lag/Drag/Void Word */
+ } hp;
} StgProfHeader;
-#endif /* PROFILING */
-
-/* -----------------------------------------------------------------------------
- The parallel header
- -------------------------------------------------------------------------- */
-
-#ifdef PAR
-
-typedef struct {
- /* StgWord ga; */ /* nope! global addresses are managed via a hash table */
-} StgParHeader;
-
-#else /* !PAR */
-
-typedef struct {
- /* empty */
-} StgParHeader;
-
-#endif /* PAR */
-
/* -----------------------------------------------------------------------------
The GranSim header
-------------------------------------------------------------------------- */
-#if defined(GRAN)
-
typedef struct {
StgWord procs; /* bitmask indicating on which PEs this closure resides */
} StgGranHeader;
-#else /* !GRAN */
-
-typedef struct {
- /* empty */
-} StgGranHeader;
-
-#endif /* GRAN */
-
/* -----------------------------------------------------------------------------
- The ticky-ticky header
-
- Comment from old Ticky.h:
-
- This is used to record if a closure has been updated but not yet
- entered. It is set when the closure is updated and cleared when
- subsequently entered.
+ The SMP header
- NB: It is {\em not} an ``entry count'', it is an
- ``entries-after-update count.''
+ 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.
- The commoning up of @CONST@, @CHARLIKE@ and @INTLIKE@ closures is
- turned off(?) if this is required. This has only been done for 2s
- collection. It is done using a nasty hack which defines the
- @_Evacuate@ and @_Scavenge@ code for @CONST@, @CHARLIKE@ and @INTLIKE@
- info tables to be @_Evacuate_1@ and @_Scavenge_1_0@.
- -------------------------------------------------------------------------- */
-
-#ifdef TICKY_TICKY
+ Note: this doesn't apply to THUNK_STATICs, which have no payload.
-typedef struct {
- /* old: W_ updated; */
-} StgTickyHeader;
-
-#else /* !TICKY_TICKY */
+ 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.
+ -------------------------------------------------------------------------- */
typedef struct {
- /* empty */
-} StgTickyHeader;
-
-#endif /* TICKY_TICKY */
+ StgWord pad;
+} StgSMPThunkHeader;
/* -----------------------------------------------------------------------------
The full fixed-size closure header
-------------------------------------------------------------------------- */
typedef struct {
- const struct _StgInfoTable* info;
+ const struct _StgInfoTable* info;
#ifdef PROFILING
- StgProfHeader prof;
-#endif
-#ifdef PAR
- StgParHeader par;
+ StgProfHeader prof;
#endif
#ifdef GRAN
- StgGranHeader gran;
-#endif
-#ifdef TICKY_TICKY
- StgTickyHeader ticky;
+ StgGranHeader gran;
#endif
} StgHeader;
-#define FIXED_HS (sizeof(StgHeader))
+typedef struct {
+ const struct _StgInfoTable* info;
+#ifdef PROFILING
+ StgProfHeader prof;
+#endif
+#ifdef GRAN
+ StgGranHeader gran;
+#endif
+ StgSMPThunkHeader smp;
+} StgThunkHeader;
+
+#define THUNK_EXTRA_HEADER_W (sizeofW(StgThunkHeader)-sizeofW(StgHeader))
/* -----------------------------------------------------------------------------
Closure Types
/* All closures follow the generic format */
-typedef struct StgClosure_ {
+struct StgClosure_ {
StgHeader header;
- struct StgClosure_ *payload[0];
-} StgClosure;
-
-/* What a stroke of luck - all our mutable closures follow the same
- * basic layout, with the mutable link field as the second field after
- * the header. This means the following structure is the supertype of
- * mutable closures.
- */
+ struct StgClosure_ *payload[FLEXIBLE_ARRAY];
+};
-typedef struct StgMutClosure_ {
- StgHeader header;
- StgPtr *padding;
- struct StgMutClosure_ *mut_link;
- struct StgClosure_ *payload[0];
-} StgMutClosure;
+typedef struct {
+ StgThunkHeader header;
+ struct StgClosure_ *payload[FLEXIBLE_ARRAY];
+} StgThunk;
typedef struct {
- StgHeader header;
+ StgThunkHeader header;
StgClosure *selectee;
} StgSelector;
typedef struct {
StgHeader header;
- StgWord n_args;
- StgClosure *fun;
- StgPtr payload[0];
+ StgHalfWord arity; /* zero if it is an AP */
+ StgHalfWord n_args;
+ StgClosure *fun; /* really points to a fun */
+ StgClosure *payload[FLEXIBLE_ARRAY];
} StgPAP;
typedef struct {
- StgHeader header;
- StgWord n_args;
- StgClosure *fun;
- StgPtr payload[0];
-} StgAP_UPD;
+ StgThunkHeader header;
+ StgHalfWord arity; /* zero if it is an AP */
+ StgHalfWord n_args;
+ StgClosure *fun; /* really points to a fun */
+ StgClosure *payload[FLEXIBLE_ARRAY];
+} StgAP;
typedef struct {
- StgHeader header;
- StgWord n_ptrs;
- StgWord n_words;
- StgWord n_instrs;
- StgWord stgexpr;
- StgPtr payload[0];
-} StgBCO;
+ StgThunkHeader header;
+ StgWord size; /* number of words in payload */
+ StgClosure *fun;
+ StgClosure *payload[FLEXIBLE_ARRAY]; /* contains a chunk of *stack* */
+} StgAP_STACK;
typedef struct {
StgHeader header;
} StgInd;
typedef struct {
- StgHeader header;
- StgClosure *indirectee;
- StgMutClosure *mut_link;
-} StgIndOldGen;
-
-typedef struct {
- StgHeader header;
- StgClosure *indirectee;
- StgClosure *static_link;
-} StgIndStatic;
-
-typedef struct StgCAF_ {
StgHeader header;
- StgClosure *body;
- StgMutClosure *mut_link;
- StgClosure *value;
- struct StgCAF_ *link;
-} StgCAF;
+ StgClosure *indirectee;
+ StgClosure *static_link;
+ struct _StgInfoTable *saved_info;
+} StgIndStatic;
typedef struct {
StgHeader header;
StgWord words;
- StgWord payload[0];
+ StgWord payload[FLEXIBLE_ARRAY];
} StgArrWords;
typedef struct {
StgHeader header;
StgWord ptrs;
- StgMutClosure *mut_link; /* mutable list */
- StgClosure *payload[0];
+ StgClosure *payload[FLEXIBLE_ARRAY];
} StgMutArrPtrs;
typedef struct {
StgHeader header;
StgClosure *var;
- StgMutClosure *mut_link;
} StgMutVar;
-/*
- A collective typedef for all linkable stack frames i.e.
- StgUpdateFrame, StgSeqFrame, StgCatchFrame
-*/
-typedef struct _StgFrame {
- StgHeader header;
- struct _StgFrame *link;
-} StgFrame;
-
typedef struct _StgUpdateFrame {
StgHeader header;
- struct _StgUpdateFrame *link;
StgClosure *updatee;
} StgUpdateFrame;
typedef struct {
StgHeader header;
- struct _StgUpdateFrame *link;
-} StgSeqFrame;
-
-typedef struct {
- StgHeader header;
- struct _StgUpdateFrame *link;
StgInt exceptions_blocked;
StgClosure *handler;
} StgCatchFrame;
StgHeader header;
} StgRetry;
-typedef struct _StgForeignObj {
- StgHeader header;
- StgAddr data; /* pointer to data in non-haskell-land */
-} StgForeignObj;
-
typedef struct _StgStableName {
StgHeader header;
StgWord sn;
struct _StgWeak *link;
} StgDeadWeak;
-/* Dynamic stack frames - these have a liveness mask in the object
- * itself, rather than in the info table. Useful for generic heap
- * check code.
+/* 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
+ * 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.
*/
-
+
+typedef struct {
+ StgHeader header;
+ StgArrWords *instrs; /* a pointer to an ArrWords */
+ StgArrWords *literals; /* a pointer to an ArrWords */
+ StgMutArrPtrs *ptrs; /* a pointer to a MutArrPtrs */
+ StgArrWords *itbls; /* a pointer to an ArrWords */
+ StgHalfWord arity; /* arity of this BCO */
+ StgHalfWord size; /* size of this BCO (in words) */
+ StgWord bitmap[FLEXIBLE_ARRAY]; /* an StgLargeBitmap */
+} StgBCO;
+
+#define BCO_BITMAP(bco) ((StgLargeBitmap *)((StgBCO *)(bco))->bitmap)
+#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) \
+ / BITS_IN(StgWord))
+
+/* -----------------------------------------------------------------------------
+ Dynamic stack frames for generic heap checks.
+
+ These generic heap checks are slow, but have the advantage of being
+ usable in a variety of situations.
+
+ The one restriction is that any relevant SRTs must already be pointed
+ to from the stack. The return address doesn't need to have an info
+ table attached: hence it can be any old code pointer.
+
+ The liveness mask contains a 1 at bit n, if register Rn contains a
+ non-pointer. The contents of all 8 vanilla registers are always saved
+ on the stack; the liveness mask tells the GC which ones contain
+ pointers.
+
+ Good places to use a generic heap check:
+
+ - case alternatives (the return address with an SRT is already
+ on the stack).
+
+ - primitives (no SRT required).
+
+ The stack frame layout for a RET_DYN is like this:
+
+ some pointers |-- RET_DYN_PTRS(liveness) words
+ some nonpointers |-- RET_DYN_NONPTRS(liveness) words
+
+ L1 \
+ D1-2 |-- RET_DYN_NONPTR_REGS_SIZE words
+ F1-4 /
+
+ R1-8 |-- RET_DYN_BITMAP_SIZE words
+
+ return address \
+ liveness mask |-- StgRetDyn structure
+ stg_gen_chk_info /
+
+ we assume that the size of a double is always 2 pointers (wasting a
+ word when it is only one pointer, but avoiding lots of #ifdefs).
+
+ See Liveness.h for the macros (RET_DYN_PTRS() etc.).
+
+ NOTE: if you change the layout of RET_DYN stack frames, then you
+ might also need to adjust the value of RESERVED_STACK_WORDS in
+ Constants.h.
+ -------------------------------------------------------------------------- */
+
typedef struct {
- const struct _StgInfoTable* info;
- StgWord liveness;
- StgWord ret_addr;
- StgWord payload[0];
+ const struct _StgInfoTable* info;
+ StgWord liveness;
+ StgWord ret_addr;
+ StgClosure * payload[FLEXIBLE_ARRAY];
} StgRetDyn;
+/* 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.
+ */
+typedef struct {
+ const struct _StgInfoTable* info;
+ StgWord size;
+ StgClosure * fun;
+ StgClosure * payload[FLEXIBLE_ARRAY];
+} StgRetFun;
+
/* Concurrent communication objects */
typedef struct {
StgHeader header;
struct StgTSO_ *head;
- StgMutClosure *mut_link;
struct StgTSO_ *tail;
StgClosure* value;
} StgMVar;
+
+/* STM data structures
+ *
+ * StgTVar defines the only type that can be updated through the STM
+ * interface.
+ *
+ * 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:
+ *
+ * - In StgTVar, current_value and first_wait_queue_entry could be held in
+ * the same field: if any thread is waiting then its expected_value for
+ * the tvar is the current value.
+ *
+ * - 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.
+ *
+ * - 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).
+ */
+
+typedef struct StgTVarWaitQueue_ {
+ StgHeader header;
+ struct StgTSO_ *waiting_tso;
+ struct StgTVarWaitQueue_ *next_queue_entry;
+ struct StgTVarWaitQueue_ *prev_queue_entry;
+} StgTVarWaitQueue;
+
+typedef struct {
+ StgHeader header;
+ StgClosure *volatile current_value;
+ StgTVarWaitQueue *volatile first_wait_queue_entry;
+#if defined(THREADED_RTS)
+ StgInt volatile num_updates;
+#endif
+} StgTVar;
+
+/* new_value == expected_value for read-only accesses */
+/* new_value is a StgTVarWaitQueue entry when trec in state TREC_WAITING */
+typedef struct {
+ StgTVar *tvar;
+ StgClosure *expected_value;
+ StgClosure *new_value;
+#if defined(THREADED_RTS)
+ StgInt num_updates;
+#endif
+} TRecEntry;
+
+#define TREC_CHUNK_NUM_ENTRIES 16
+
+typedef struct StgTRecChunk_ {
+ StgHeader header;
+ struct StgTRecChunk_ *prev_chunk;
+ StgWord next_entry_idx;
+ TRecEntry entries[TREC_CHUNK_NUM_ENTRIES];
+} StgTRecChunk;
+
+typedef enum {
+ TREC_ACTIVE, /* Transaction in progress, outcome undecided */
+ TREC_CONDEMNED, /* Transaction in progress, inconsistent / out of date reads */
+ TREC_COMMITTED, /* Transaction has committed, now updating tvars */
+ TREC_ABORTED, /* Transaction has aborted, now reverting tvars */
+ TREC_WAITING, /* Transaction currently waiting */
+} TRecState;
+
+typedef struct StgTRecHeader_ {
+ StgHeader header;
+ TRecState state;
+ struct StgTRecHeader_ *enclosing_trec;
+ StgTRecChunk *current_chunk;
+} StgTRecHeader;
+
+typedef struct {
+ StgHeader header;
+ StgClosure *code;
+} StgAtomicallyFrame;
+
+typedef struct {
+ StgHeader header;
+ StgClosure *handler;
+} StgCatchSTMFrame;
+
+typedef struct {
+ StgHeader header;
+ StgBool running_alt_code;
+ StgClosure *first_code;
+ StgClosure *alt_code;
+ StgTRecHeader *first_code_trec;
+} StgCatchRetryFrame;
+
#if defined(PAR) || defined(GRAN)
/*
StgBlockingQueueElement is a ``collective type'' representing the types
of closures that can be found on a blocking queue: StgTSO, StgRBHSave,
StgBlockedFetch. (StgRBHSave can only appear at the end of a blocking
queue). Logically, this is a union type, but defining another struct
- with a common layout is easier to handle in the code (same as for
- StgMutClosures).
+ with a common layout is easier to handle in the code.
Note that in the standard setup only StgTSOs can be on a blocking queue.
This is one of the main reasons for slightly different code in files
such as Schedule.c.
typedef struct StgBlockingQueueElement_ {
StgHeader header;
struct StgBlockingQueueElement_ *link; /* next elem in BQ */
- StgMutClosure *mut_link; /* next elem in mutable list */
- struct StgClosure_ *payload[0];/* contents of the closure */
+ struct StgClosure_ *payload[FLEXIBLE_ARRAY];/* contents of the closure */
} StgBlockingQueueElement;
/* only difference to std code is type of the elem in the BQ */
typedef struct StgBlockingQueue_ {
StgHeader header;
struct StgBlockingQueueElement_ *blocking_queue; /* start of the BQ */
- StgMutClosure *mut_link; /* next elem in mutable list */
} StgBlockingQueue;
/* this closure is hanging at the end of a blocking queue in (see RBH.c) */
typedef struct StgRBHSave_ {
StgHeader header;
- StgPtr payload[0]; /* 2 words ripped out of the guts of the */
+ StgClosure *payload[FLEXIBLE_ARRAY]; /* 2 words ripped out of the guts of the */
} StgRBHSave; /* closure holding the blocking queue */
typedef struct StgRBH_ {
StgHeader header;
struct StgBlockingQueueElement_ *blocking_queue; /* start of the BQ */
- StgMutClosure *mut_link; /* next elem in mutable list */
} StgRBH;
-#else
-
-typedef struct StgBlockingQueue_ {
- StgHeader header;
- struct StgTSO_ *blocking_queue;
- StgMutClosure *mut_link;
-} StgBlockingQueue;
-
#endif
#if defined(PAR)
typedef struct StgFetchMe_ {
StgHeader header;
globalAddr *ga; /* ptr to unique id for a closure */
- StgMutClosure *mut_link; /* next elem in mutable list */
} StgFetchMe;
/* same contents as an ordinary StgBlockingQueue */
typedef struct StgFetchMeBlockingQueue_ {
StgHeader header;
struct StgBlockingQueueElement_ *blocking_queue; /* start of the BQ */
- StgMutClosure *mut_link; /* next elem in mutable list */
} StgFetchMeBlockingQueue;
/* This is an entry in a blocking queue. It indicates a fetch request from a
typedef struct StgBlockedFetch_ {
StgHeader header;
struct StgBlockingQueueElement_ *link; /* next elem in the BQ */
- StgMutClosure *mut_link; /* next elem in mutable list */
StgClosure *node; /* node to fetch */
globalAddr ga; /* where to send the result to */
} StgBlockedFetch; /* NB: not just a ptr to a GA */