Describe [Stack Cloning] better

2 files changed, 109 insertions, 20 deletions

diff --git a/compiler/GHC/Builtin/primops.txt.pp b/compiler/GHC/Builtin/primops.txt.pp
index 6f5bc57292..58d4ec91f3 100644
--- a/compiler/GHC/Builtin/primops.txt.pp
+++ b/compiler/GHC/Builtin/primops.txt.pp
@@ -190,9 +190,9 @@ defaults
 -- Note [Levity and representation polymorphic primops]
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 -- In the types of primops in this module,
--- 
+--
 -- * The names `a,b,c,s` stand for type variables of kind Type
--- 
+--
 -- * The names `v` and `w` stand for levity-polymorphic
 --   type variables.
 --   For example:
@@ -207,7 +207,7 @@ defaults
 --     - `v` and `w` end up written as `a` and `b` (respectively) in types,
 --       which means that one shouldn't write a primop type involving both
 --       `a` and `v`, nor `b` and `w`.
--- 
+--
 -- * The names `o` and `p` stand for representation-polymorphic
 --   type variables, similarly to `v` and `w` above. For example:
 --      op :: o -> p -> Int
@@ -3259,29 +3259,29 @@ primop  ReallyUnsafePtrEqualityOp "reallyUnsafePtrEquality#" GenPrimOp
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 -- The primop `reallyUnsafePtrEquality#` does a direct pointer
 -- equality between two (boxed) values.  Several things to note:
--- 
+--
 -- * It is levity-polymorphic. It works for TYPE (BoxedRep Lifted) and
 --   TYPE (BoxedRep Unlifted). But not TYPE IntRep, for example.
 --   This levity-polymorphism comes from the use of the type variables
 --   "v" and "w". See Note [Levity and representation polymorphic primops]
--- 
+--
 -- * It does not evaluate its arguments. The user of the primop is responsible
 --   for doing so.
--- 
+--
 -- * It is hetero-typed; you can compare pointers of different types.
 --   This is used in various packages such as containers & unordered-containers.
--- 
+--
 -- * It is obviously very dangerous, because
 --      let x = f y in reallyUnsafePtrEquality# x x
 --   will probably return True, whereas
 --      reallyUnsafePtrEquality# (f y) (f y)
 --   will probably return False. ("probably", because it's affected
 --   by CSE and inlining).
--- 
+--
 -- * reallyUnsafePtrEquality# can't fail, but it is marked as such
 --   to prevent it from floating out.
 --   See Note [reallyUnsafePtrEquality# can_fail]
--- 
+--
 -- The library GHC.Exts provides several less Wild-West functions
 -- for use in specific cases, namely:
 --
@@ -3651,7 +3651,12 @@ primtype StackSnapshot#
 
 primop  CloneMyStack "cloneMyStack#" GenPrimOp
    State# RealWorld -> (# State# RealWorld, StackSnapshot# #)
-   { Clones the stack of the current Haskell thread. }
+   { Clones the stack of the current (active) Haskell thread. A cloned stack is
+     represented by {\tt StackSnapshot# } and is not evaluated any further
+     (i.e. it's "cold"). This is useful for stack decoding (backtraces) and
+     analyses because there are no concurrent mutations on a cloned stack.
+     The module {\tt GHC.Stack.CloneStack } contains related funcions.
+     Please see Note [Stack Cloning] for technical details. }
    with
    has_side_effects = True
    out_of_line      = True
diff --git a/libraries/base/GHC/Stack/CloneStack.hs b/libraries/base/GHC/Stack/CloneStack.hs
index 67c3374d33..68077d4299 100644
--- a/libraries/base/GHC/Stack/CloneStack.hs
+++ b/libraries/base/GHC/Stack/CloneStack.hs
@@ -29,20 +29,105 @@ data StackSnapshot = StackSnapshot !StackSnapshot#
 {-
 Note [Stack Cloning]
 ~~~~~~~~~~~~~~~~~~~~
-"Cloning" a stack means that it's StgStack closure is copied including the
-stack memory (stack[]). The stack pointer (sp) of the clone is adjusted to be
-valid.
+"Cloning" a stack means that it's `StgStack` closure is copied including the
+stack memory (`stack[]`). Closures referenced by stack closures are not copied,
+i.e. pointer payloads are still referred to by the same pointer.
+In other words: Only those parts that are affected by stack evaluation are
+"cloned".
+
+The stack pointer (sp) of the clone is adjusted to be valid, i.e. to point into
+the cloned stack.
 
 The clone is "offline"/"cold", i.e. it won't be evaluated any further. This is
-useful for further analyses like stack unwinding or traversal.
+useful for further analyses like stack unwinding or traversal because all
+pointers stay valid.
+
+StackSnapshot#
+--------------
+A cloned stack is represented in Haskell by `StackSnapshot !StackSnapshot#`.
+`StackSnapshot#` is a primitive type, it's value is a pointer to the stack in
+RTS (`StgStack*`).
+
+To take advantage of the garbage collector, the representation cannot be `Ptr`
+or `StablePtr`:
+- Closures referenced by a `Ptr` may be garbage collected at any time (without
+  checking if it's still in use).
+- `StablePtr` has to be freed explictly, which would introduce nasty state
+   handling.
+
+By using a primitive type, the stack closure is kept and managed by the garbage
+collector as long as it's in use and automatically freed later.
+As closures referred to by stack closures (e.g. payloads) may be used by other
+closures that are not related to stack cloning, the memory has to be managed by
+the garbage collector; i.e. one cannot simply call free() in the RTS C code
+because it's hard to figure out what to free while the garbage collector is
+built to do this job.
 
+RTS interface
+-------------
 There are two different ways to clone a stack:
-1. By the corresponding thread via a primop call (cloneMyStack#).
-2. By sending a RTS message (Messages.c) with a MVar to the corresponding
-   thread and receiving the stack by taking it out of this MVar.
+1. `cloneMyStack#` - A primop for cloning the active thread's stack.
+2. `sendCloneStackMessage` - A FFI function for cloning another thread's stack.
+   Sends a RTS message (Messages.c) with a MVar to that thread. The cloned
+   stack is reveived by taking it out of this MVar.
+
+`cloneMyStack#` has to be a primop, because new primitive types
+(`StackSnapshot#`) cannot be marshalled by FFI. Using a `Ptr StackSnapshot` as
+FFI return type would not save the snapshot from being garbage collected, as
+discussed in the section above.
+
+C API
+-------------
+`cloneStack` is the function that really clones a given stack and returns
+the clone:
+`StgStack* cloneStack(Capability* capability, const StgStack* stack)`
+
+It's called directly by `stg_cloneMyStackzh` (`PrimOps.cmm`), the
+`cloneMyStack#` primop.
+
+To clone another thread's stack, there's a message passing mechanism such that
+the receiver's capability clones its. So, there's no need to stop/pause the
+other thread as it's capability will fulfill the cloning request when it's
+ready to do so.
 
-A StackSnapshot# is really a pointer to an immutable StgStack closure with
-the invariant that stack->sp points to a valid frame.
+The message is defined in `Closures.h`:
+
+```
+typedef struct MessageCloneStack_ {
+    StgHeader header;
+    Message   *link;
+    StgMVar   *result;
+    StgTSO    *tso;
+} MessageCloneStack;
+```
+
+The fields are:
+- `header`: It's a closure and thus subject to garbage collection (no manual
+   memory management needed)
+- `link`: Messages form a singly linked list in `Capability`, referred to by
+  `capability->inbox`.
+- `result`: An `MVar`. When the message is sent it's empty, after cloning the
+  `StackSnapshot` is put into it.
+- `tso`: `tso->stackobj` is the stack to clone.
+
+The asynchronous flow can be split into sending this message and putting the
+cloned stack into the MVar (expecting the sender to get it from there).
+
+Sending:
+The public C function to send is
+`void sendCloneStackMessage(StgTSO *tso, HsStablePtr mvar)`.
+It prepares the message for the thread to clone (identified by it's `tso`) and
+sets the `result` MVar (pointed to by `mvar`). Then it sends the message by
+calling `sendMessage` which puts it into the Capabilities `inbox`.
+
+Receiving:
+Inbox processing is part of the big work finding loop in `schedule`. The
+function that dispatches messages is `executeMessage`. From there
+`void handleCloneStackMessage(MessageCloneStack *msg)` is called.
+
+`handleCloneStackMessage` clones the stack, lifts the result to `StackSnapshot`
+(MVar needs a lifted value, no primitive) and puts it into the MVar
+(`msg->mvar`).
 -}
 
 -- | Clone the stack of the executing thread
@@ -67,4 +152,3 @@ cloneThreadStack (ThreadId tid#) = do
   sendCloneStackMessage tid# ptr
   freeStablePtr ptr
   takeMVar resultVar
-