STM.h defines the C-level interface to the STM.
- The interface is designed so that all of the operations return
- directly: if the specified StgTSO should block then the Haskell
- scheduler's data structures are updated within the STM
- implementation, rather than blocking the native thread.
+ The design follows that of the PPoPP 2005 paper "Composable memory
+ transactions" extended to include fine-grained locking of TVars.
- This interface can be supported by many different implementations,
- in particular it is left unspecified:
-
- - Whether nested transactions are fully supported.
+ Three different implementations can be built. In overview:
+
+ STM_UNIPROC -- no locking at all: not safe for concurrent invocations
- A simple implementation would count the number of
- stmStartTransaction operations that a thread invokes and only
- attempt to really commit it to the heap when the corresponding
- number of stmCommitTransaction calls have been made. This
- prevents enclosed transactions from being aborted without also
- aborting all of the outer ones.
+ STM_CG_LOCK -- coarse-grained locking : a single mutex protects all
+ TVars
- The current implementation does support proper nesting.
-
- - Whether stmWait and stmReWait are blocking.
-
- A simple implementation would always return 'false' from these
- operations, signalling that the calling thread should immediately
- retry its transaction.
-
- A fuller implementation would block the thread and return 'True'
- when it is safe for the thread to block.
-
- The current implementation does provide stmWait and stmReWait
- operations which can block the caller's TSO.
-
- - Whether the transactional read, write, commit and validate
- operations are blocking or non-blocking.
-
- A simple implementation would use an internal lock to prevent
- concurrent execution of any STM operations. (This does not
- prevent multiple threads having concurrent transactions, merely
- the concurrent execution of say stmCommitTransaction by two
- threads at the same time).
+ STM_FG_LOCKS -- per-TVar exclusion : each TVar can be owned by at
+ most one TRec at any time. This allows dynamically
+ non-conflicting transactions to commit in parallel.
+ The implementation treats reads optimisitcally --
+ extra versioning information is retained in the
+ saw_update_by field of the TVars so that they do not
+ need to be locked for reading.
- A fuller implementation would offer obstruction-free or lock-free
- progress guarantees, as in our OOPSLA 2003 paper.
+ STM.C contains more details about the locking schemes used.
- The current implementation is lock-free for simple uncontended
- operations, but uses an internal lock on SMP systems in some
- cases. This aims to provide good performance on uniprocessors:
- it substantially streamlines the design, when compared with the
- OOPSLA paper, and on a uniprocessor we can be sure that threads
- are never pre-empted within STM operations.
*/
#ifndef STM_H
#define STM_H
+#ifdef THREADED_RTS
+//#define STM_CG_LOCK
+#define STM_FG_LOCKS
+#else
+#define STM_UNIPROC
+#endif
+
#ifdef __cplusplus
extern "C" {
#endif
/*----------------------------------------------------------------------
- Start of day
- ------------
-
+ GC interaction
+ --------------
*/
-extern void initSTM(void);
-
extern void stmPreGCHook(void);
/*----------------------------------------------------------------------
*/
-// Create and enter a new transaction context
+/* Create and enter a new transaction context */
+
+extern StgTRecHeader *stmStartTransaction(Capability *cap, StgTRecHeader *outer);
+extern StgTRecHeader *stmStartNestedTransaction(Capability *cap, StgTRecHeader *outer
+);
+
+/*
+ * Exit the current transaction context, abandoning any read/write
+ * operations performed within it and removing the thread from any
+ * tvar wait queues if it was waitin. Note that if nested transactions
+ * are not fully supported then this may leave the enclosing
+ * transaction contexts doomed to abort.
+ */
-extern StgTRecHeader *stmStartTransaction(StgTRecHeader *outer);
+extern void stmAbortTransaction(Capability *cap, StgTRecHeader *trec);
-// Exit the current transaction context, abandoning any read/write
-// operations performed within it and removing the thread from any
-// tvar wait queues if it was waitin. Note that if nested transactions
-// are not fully supported then this may leave the enclosing
-// transaction contexts doomed to abort.
+/*
+ * Ensure that a subsequent commit / validation will fail. We use this
+ * in our current handling of transactions that may have become invalid
+ * and started looping. We strip their stack back to the ATOMICALLY_FRAME,
+ * and, when the thread is next scheduled, discover it to be invalid and
+ * re-execute it. However, we need to force the transaction to stay invalid
+ * in case other threads' updates make it valid in the mean time.
+ */
-extern void stmAbortTransaction(StgTRecHeader *trec);
+extern void stmCondemnTransaction(Capability *cap, StgTRecHeader *trec);
-// Return the trec within which the specified trec was created (not
-// valid if trec==NO_TREC).
+/*
+ * Return the trec within which the specified trec was created (not
+ * valid if trec==NO_TREC).
+ */
extern StgTRecHeader *stmGetEnclosingTRec(StgTRecHeader *trec);
/*----------------------------------------------------------------------
- Validate/commit/wait/rewait operations
- --------------------------------------
+ Validation
+ ----------
+ Test whether the specified transaction record, and all those within which
+ it is nested, are still valid.
+
+ Note: the caller can assume that once stmValidateTransaction has
+ returned FALSE for a given trec then that transaction will never
+ again be valid -- we rely on this in Schedule.c when kicking invalid
+ threads at GC (in case they are stuck looping)
+*/
+
+extern StgBool stmValidateNestOfTransactions(StgTRecHeader *trec);
+
+/*----------------------------------------------------------------------
+
+ Commit/wait/rewait operations
+ -----------------------------
These four operations return boolean results which should be interpreted
as follows:
- true => The transaction context was definitely valid
+ true => The transaction record was definitely valid
- false => The transaction context may not have been valid
+ false => The transaction record may not have been valid
+
+ Note that, for nested operations, validity here is solely in terms
+ of the specified trec: it does not say whether those that it may be
+ nested are themselves valid. Callers can check this with
+ stmValidateNestOfTransactions.
The user of the STM should ensure that it is always safe to assume that a
transaction context is not valid when in fact it is (i.e. to return false in
is actually still valid.
*/
-// Test whether the current transaction context is valid, i.e. whether
-// it is still possible for it to commit successfully. Note: we assume that
-// once stmValidateTransaction has returned FALSE for a given transaction then
-// that transaction will never again be valid -- we rely on this in Schedule.c when
-// kicking invalid threads at GC (in case they are stuck looping)
-
-extern StgBool stmValidateTransaction(StgTRecHeader *trec);
+/*
+ * Test whether the current transaction context is valid and, if so,
+ * commit its memory accesses to the heap. stmCommitTransaction must
+ * unblock any threads which are waiting on tvars that updates have
+ * been committed to.
+ */
-// Test whether the current transaction context is valid and, if so,
-// commit its memory accesses to the heap. stmCommitTransaction must
-// unblock any threads which are waiting on tvars that updates have
-// been committed to.
+extern StgBool stmCommitTransaction(Capability *cap, StgTRecHeader *trec);
+extern StgBool stmCommitNestedTransaction(Capability *cap, StgTRecHeader *trec);
-extern StgBool stmCommitTransaction(StgTRecHeader *trec);
+/*
+ * Test whether the current transaction context is valid and, if so,
+ * start the thread waiting for updates to any of the tvars it has
+ * ready from and mark it as blocked. It is an error to call stmWait
+ * if the thread is already waiting.
+ */
-// Test whether the current transaction context is valid and, if so,
-// start the thread waiting for updates to any of the tvars it has
-// ready from and mark it as blocked. It is an error to call stmWait
-// if the thread is already waiting.
+extern StgBool stmWait(Capability *cap,
+ StgTSO *tso,
+ StgTRecHeader *trec);
-extern StgBool stmWait(StgTSO *tso, StgTRecHeader *trec);
+extern void stmWaitUnlock(Capability *cap, StgTRecHeader *trec);
-// Test whether the current transaction context is valid and, if so,
-// leave the thread waiting and mark it as blocked again. If the
-// transaction context is no longer valid then stop the thread waiting
-// and leave it as unblocked. It is an error to call stmReWait if the
-// thread is not waiting.
+/*
+ * Test whether the current transaction context is valid and, if so,
+ * leave the thread waiting and mark it as blocked again. If the
+ * transaction context is no longer valid then stop the thread waiting
+ * and leave it as unblocked. It is an error to call stmReWait if the
+ * thread is not waiting.
+ */
-extern StgBool stmReWait(StgTRecHeader *trec);
+extern StgBool stmReWait(Capability *cap, StgTSO *tso);
-// Merge the accesses made so far in the second trec into the first trec.
-// Note that the resulting trec is only intended to be used in wait operations.
-// This avoids defining what happens if "trec" and "other" contain conflicting
-// updates.
+/*----------------------------------------------------------------------
-extern StgBool stmMergeForWaiting(StgTRecHeader *trec, StgTRecHeader *other);
+ TVar management operations
+ --------------------------
+*/
+extern StgTVar *stmNewTVar(Capability *cap,
+ StgClosure *new_value);
/*----------------------------------------------------------------------
----------------------
*/
-// Return the logical contents of 'tvar' within the context of the
-// thread's current transaction.
+/*
+ * Return the logical contents of 'tvar' within the context of the
+ * thread's current transaction.
+ */
-extern StgClosure *stmReadTVar(StgTRecHeader *trec,
+extern StgClosure *stmReadTVar(Capability *cap,
+ StgTRecHeader *trec,
StgTVar *tvar);
-// Update the logical contents of 'tvar' within the context of the
-// thread's current transaction.
+/* Update the logical contents of 'tvar' within the context of the
+ * thread's current transaction.
+ */
-extern void stmWriteTVar(StgTRecHeader *trec,
+extern void stmWriteTVar(Capability *cap,
+ StgTRecHeader *trec,
StgTVar *tvar,
StgClosure *new_value);
/*----------------------------------------------------------------------*/
-// NULLs
+/* NULLs */
#define END_STM_WAIT_QUEUE ((StgTVarWaitQueue *)(void *)&stg_END_STM_WAIT_QUEUE_closure)
#define END_STM_CHUNK_LIST ((StgTRecChunk *)(void *)&stg_END_STM_CHUNK_LIST_closure)
+
+#if IN_STG_CODE
+#define NO_TREC (stg_NO_TREC_closure)
+#else
#define NO_TREC ((StgTRecHeader *)(void *)&stg_NO_TREC_closure)
+#endif
/*----------------------------------------------------------------------*/
projects / ghc-hetmet.git / blobdiff