path: root/rts/Continuation.c

/* ---------------------------------------------------------------------------
 *
 * (c) The GHC Team, 2020
 *
 * Continuations
 *
 * --------------------------------------------------------------------------*/

#include "rts/PosixSource.h"
#include "Rts.h"

#include "sm/Storage.h"
#include "sm/Sanity.h"
#include "Continuation.h"
#include "Printer.h"
#include "Threads.h"

#include <string.h>

/* Note [Continuations overview]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A first-class continuation is represented in the RTS as a closure with type
CONTINUATION (which corresponds to the StgContinuation struct type).
Continuation closures are similar to AP_STACK closures in that they store a
chunk of stack, but while AP_STACK closures are a special type of thunk,
continuation closures are a special type of *function*. More specifically, every
continuation is a function of arity 2, accepting one pointer and one RealWorld
token.

Continuation capture is performed through the use of two cooperating primops,
`prompt#` and `control0#`, which morally have the following types:

    prompt# :: PromptTag a -> IO a -> IO a
    control0# :: PromptTag a -> ((IO b -> IO a) -> IO a) -> IO b

(In reality, their types use `State# RealWorld` rather than `IO` in the usual
way, but the type of control0# is nearly incomprehensible when presented in
those terms, so thinking in terms of `IO` is a helpful abbreviation.)

GHC implements *delimited* continuations: `prompt#` introduces a delimiter that
`control0#` looks for to determine how much of the local continuation should be
captured. Operationally, each use of `prompt#` pushes a *prompt frame* onto the
stack (annotated with a user-provided *prompt tag*), and each use of `control0#`
copies the portion of the stack up to the nearest prompt frame (with a matching
tag) into the heap to form a new continuation closure. `control0#` then aborts
to the prompt frame and resumes execution by applying the argument to
`control0#` to the continuation. This process is mostly handled in C, via
`captureContinuationAndAbort`.

When a continuation closure is applied, the process occurs in reverse: the chunk
of stack frames stored in the closure are pushed onto the current stack, and
execution resumes by applying the argument to the continuation to a RealWorld
token. This is a non-destructive operation---the caller is free to apply the
continuation arbitrarily many times. This process is handled in Cmm, via
`stg_CONTINUATION_apply` in ContinuationOps.cmm.

For the most part, capture and restoration of continuations is surprisingly
straightforward: the bulk of the work on each side of the process is just doing
the necessary copying. However, there are a few additional subtleties:

  * It is possible for continuation capture to *fail* if no matching prompt
    frame is on the stack or if the continuation would include thunk update or
    STM frames; see Note [When capturing the continuation fails] for details.

  * Special care must be taken to ensure the async exception masking state is
    properly updated across continuation captures and restores, see
    Note [Continuations and async exception masking] for details.

Note [When capturing the continuation fails]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
How can continuation capture fail? There are three possible scenarios:

  1. There’s no matching prompt frame *anywhere* on the stack.
  2. The captured continuation would include a thunk update frame.
  3. The captured continuation would include part of an STM transaction.

The first case is fairly self-explanatory: if there’s no matching prompt frame,
we don’t know where to capture up to. The other two cases are important to
protect RTS invariants, as continuations can be applied arbitrarily many times,
but both thunk updates and STM transactions are non-reentrant.

Moreover, any attempt to capture across a thunk update frame is necessarily
ill-defined. Such frames indicate the start of a given `State#` thread (i.e.
they likely correspond to `unsafePerformIO` or `runST`), but the “current
continuation” is only predictable in code with a well-defined evaluation order.
Any attempt to capture across such a boundary would be correspondingly
unpredictable, so we want to be sure to reject it as programmer error. However,
note that we cannot detect and reject *all* such errors, see Note [Detecting
illegal captures is not guaranteed] for why.

To identify these error cases while searching for a matching prompt frame, we
also look for any stack frames that would indicate we’ve gone astray:

  1. If we see a STOP_FRAME, we’ve just plain run out of stack frames.
  2. To identify thunk updates, we can just look for UPDATE_FRAMEs.
  3. To identify STM transactions, we look for STM-related frames, namely
     ATOMICALLY_FRAME, CATCH_RETRY_FRAME, or CATCH_STM_FRAME.

If it finds any of these frames before a matching prompt frame,
`captureContinuationAndAbort` returns NULL, which `stg_control0zh` treats as a
signal that it should raise an exception.

Note [Detecting illegal captures is not guaranteed]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As alluded to in Note [When capturing the continuation fails], the “current
continuation” is only well-defined within a given `State#` thread. For a
concrete example illustrating why, consider the following program:

    do tag <- newPromptTag
       let v = unsafePerformIO (control0 tag (\k -> k ()))
       prompt tag (pure $! v)

If we were to allow this program, what would its result be? The answer depends
on how and when we evaluate `v`. If we allocate a thunk for `v` and force it
once the prompt has been installed, the program would successfully return `()`.
But since GHC can tell that `v` is used strictly, it may very well choose to
evaluate it immediately, before the prompt has been installed, in which case
there would be no matching prompt in scope at the time the call to `control0` is
evaluated, and the program would raise an error.

Without uses of `pseq`, GHC makes no guarantees about the order in which it will
evaluate pure expressions, so the optimizer may rearrange them significantly.
Therefore, any code that attempts such a capture is ill-defined, and we want to
do our best to detect and reject such mistakes. However, we cannot guarantee
that we will catch all such misuses! For example, given the program

    prompt tag (pure (1 + unsafePerformIO (control0 tag f)))

it is extremely unlikely that we will signal an error, despite the erroneous
capture. The reason is Note [Simplification of runRW#] in GHC.CoreToStg.Prep:
when `runRW#` appears in a strict context, there is no reason to allocate a
thunk, so GHC takes care to ensure it will not do so. With no thunk to update,
there is naturally no thunk update frame, so we cannot possibly detect at
runtime that anything was amiss.

Preserving the information necessary to reliably detect all of these sorts of
misuses at runtime in all situations would be disastrous for performance, so it
is the programmer’s responsibility to ensure this does not happen. Any program
for which continuation capture fails is a buggy program---there is NO WAY to
write a safe program that relies upon catching exceptions raised by continuation
capture failure. In other words, such programs invoke undefined behavior.

Given the behavior of such programs is already undefined, one might ask why we
bother detecting and reporting such failure conditions at all. In theory, we
could ignore thunk update frames completely and let the program behave
unpredictably. But detecting the failures we *can* detect is still worthwhile:

  * From the programmer’s point of view, best-effort detection and reporting of
    such misuses is still helpful, and the performance overhead of checking for
    them is minimal.

  * From the runtime’s point of view, detecting and eagerly rejecting such uses
    gives us much more confidence they will not violate internal invariants, so
    even if a buggy program does the wrong thing, it won’t corrupt the runtime.

In summary, the runtime does the best it can, but if it fails to detect and
report a misuse of `control0#`, the bug is in the program, not GHC.

Note [Continuations and async exception masking]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
It’s possible for a captured continuation to include a frame that alters the
async exception masking state. For example, consider the following program:

    prompt tag $ maskAsyncExceptions $
      control0 tag (\k -> ...) >>= do_something

The captured continuation will look like this:

    \m -> maskAsyncExceptions (m >>= do_something)

This situation requires some additional care:

  1. When aborting to the prompt as part of continuation capture, we need to
     restore the async exception masking state to whatever it was when the
     prompt frame was initially pushed.

  2. When restoring the continuation, we need to update the async exception
     masking state to whatever it was when the continuation was captured.

  3. When restoring the continuation, we need to update the pushed stack frames
     themselves to restore the new context’s async exception masking state when
     they return.

The third point is by far the most subtle, and it stems from the way primops
like `maskAsyncExceptions#` arrange to restore the async exception masking state
when their subcomputation returns. Specifically, when a primop like
`unmaskAsyncExceptions#`, `maskAsyncExceptions#`, or `maskUninterruptible#` is
called, it pushes one of three different frames onto the stack, depending on the
enclosing context’s masking state:

  * If exceptions were unmasked, it pushes `stg_unmaskAsyncExceptionszh_ret`.
  * If exceptions were interruptibly masked, it pushes `stg_maskAsyncExceptionszh_ret`.
  * If exceptions were uninterruptibly masked, it pushes `stg_maskUninterruptiblezh_ret`.

Note that, somewhat confusingly, which frame is pushed depends only on the
*enclosing* context’s masking state, *not* the new masking state installed for
the subcomputation. This works out, since the frame only exists to restore the
previous masking state, but it means the frames on the stack do not themselves
determine how the masking state was modified.

To cooperate with this strategy, we look for the aforementioned return
frames while walking the stack during continuation capture. If we find any of
them, we record two pieces of information:

  1. The captured continuation is necessarily responsible for whatever the
     masking state happens to be currently, so the *current* masking state must
     be restored upon continuation resumption. We set the `apply_mask_frame`
     field to a stack frame info pointer that will update the masking state
     accordingly if returned to.

  2. We set the `mask_frame_offset` field to the word offset of the *outermost*
     stack frame that restores the masking state. This serves a dual purpose:

       a. When we return to Cmm, `stg_control0zh` returns to this frame to
          restore the async exception masking state.

       b. When the continuation is restored, this frame is substituted with one
          that restores the masking state of the new context (i.e. the one in
          which the continuation is restored).

This is all quite subtle, so to illustrate with an example, suppose we have the
following state at the start of a continuation capture:

    ┌───────┐                                       ┌───────────────────┐
    │ STACK │                                       │    tso->flags     │
    ╞═══════╡                                       ╞═══════════════╤═══╡
    │  ...  │                                       │ BLOCKEX       │ 1 │
    ├───────┤                                       ├───────────────┼───┤
    │  RET  │──→ stg_maskAsyncExceptionszh_ret      │ INTERRUPTIBLE │ 0 │
    ├───────┤                                       └───────────────┴───┘
    │  ...  │
    ├───────┤
    │  RET  │──→ stg_unmaskAsyncExceptionszh_ret
    ├───────┤
    │  ...  │
    ├───────┤
    │  RET  │──→ stg_prompt_frame
    ├───────┤

We’ll copy the relevant stack frames into the heap, and we’ll set the
`apply_mask_frame` and `mask_frame_offset` fields accordingly:

    ┌───────────────────┐
    │   CONTINUATION    │
    ╞═══════════════════╡  ╭──→ stg_maskUninterruptiblezh_ret
    │ apply_mask_frame  │──╯
    ├───────────────────┤      ┌───────┐
    │      stack        │─────→│ STACK │
    ├───────────────────┤      ╞═══════╡
    │ mask_frame_offset │──╮   │  ...  │
    └───────────────────┘  │   ├───────┤
                           │   │  RET  │──→ stg_maskAsyncExceptionszh_ret
                           │   ├───────┤
                           │   │  ...  │
                           │   ├───────┤
                           ╰──→│  RET  │──→ stg_unmaskAsyncExceptionszh_ret
                               ├───────┤
                               │  ...  │
                               └───────┘

Next, `captureContinuationAndAbort` returns to Cmm, which sets up the stack so
that it can return to the frame indicated by `mask_frame_offset`, which in this
case is `stg_unmaskAsyncExceptionszh_ret`:

    ┌───────┐                                        ┌───────────────────┐
    │ STACK │                                        │    tso->flags     │
    ╞═══════╡                                        ╞═══════════════╤═══╡
    │  RET  │──→ stg_unmaskAsyncExceptionszh_ret     │ BLOCKEX       │ 1 │
    ├───────┤                                        ├───────────────┼───┤
    │  RET  │──→ stg_ap_pv                           │ INTERRUPTIBLE │ 0 │
    ├───────┤                                        └───────────────┴───┘
    │ cont  │
    ├───────┤
    │  ...  │
    ├───────┤

`stg_control0zh` then returns to `stg_unmaskAsyncExceptionszh`, which restores
the exception masking state appropriately. It then returns to `stg_ap_pv`, which
applies the handler to the captured continuation, and execution continues with
exceptions properly unmasked.

Next, let’s consider what happens when the continuation is restored. Suppose we
start in the following state:

    ┌───────┐                                        ┌───────────────────┐
    │ STACK │                                        │    tso->flags     │
    ╞═══════╡                                        ╞═══════════════╤═══╡
    │  ...  │                                        │ BLOCKEX       │ 1 │
    ├───────┤                                        ├───────────────┼───┤
                                                     │ INTERRUPTIBLE │ 1 │
                                                     └───────────────┴───┘

`stg_CONTINUATION_apply` will start by copying the frames from the continuation
back onto the stack, plus `apply_mask_frame` on top, which in this case is
`stg_maskUninterruptiblezh_ret`:

                         ┌───────┐
                         │ STACK │
                         ╞═══════╡
                         │  RET  │──→ stg_maskUninterruptiblezh_ret
                         ├───────┤
                         │  RET  │──→ stg_ap_v
                         ├───────┤
                         │  ...  │
                         ├───────┤
                         │  RET  │──→ stg_maskAsyncExceptionszh_ret
                         ├───────┤
                         │  ...  │
                         ├───────┤
    mask_frame_offset──→ │  RET  │──→ stg_unmaskAsyncExceptionszh_ret
                         ├───────┤
                         │  ...  │
                         ├───────┤

Next, it will update the frame at `mask_frame_offset` based on the current async
exception masking state. In this case, exceptions are interruptibly masked, so
the frame will be replaced with `stg_maskAsyncExceptionszh_ret`.
`stg_CONTINUATION_apply` will then return to the top of the stack, and
`stg_maskUninterruptiblezh_ret` will update the async exception masking state:

    ┌───────┐                                        ┌───────────────────┐
    │ STACK │                                        │    tso->flags     │
    ╞═══════╡                                        ╞═══════════════╤═══╡
    │  RET  │──→ stg_ap_v                            │ BLOCKEX       │ 1 │
    ├───────┤                                        ├───────────────┼───┤
    │  ...  │                                        │ INTERRUPTIBLE │ 0 │
    ├───────┤                                        └───────────────┴───┘
    │  RET  │──→ stg_maskAsyncExceptionszh_ret
    ├───────┤
    │  ...  │
    ├───────┤
    │  RET  │──→ stg_unmaskAsyncExceptionszh_ret
    ├───────┤
    │  ...  │
    ├───────┤

Control then returns to `stg_ap_v`, which applies the argument in R1 to resume
execution with exceptions re-masked, and we’re done. Phew.

One might naturally wonder why we bother with all this complicated indirection
involving returning to mask/unmask frames rather than just adjusting
`tso->flags` directly ourselves. That would indeed be significantly simpler,
but returning to `stg_unmaskAsyncExceptionszh_ret` has the important side-effect
of checking eagerly for a pending async exception and raising it if one is
available. So we do some tricky trampolining, and that frees us from having to
worry about that in the continuation capture/restore logic as well. */

static bool is_mask_frame_info(const StgInfoTable *info)
{
  return info == &stg_unmaskAsyncExceptionszh_ret_info
      || info == &stg_maskAsyncExceptionszh_ret_info
      || info == &stg_maskUninterruptiblezh_ret_info;
}

static StgStack *pop_stack_chunk(Capability *cap, StgTSO *tso)
{
  StgStack *stack = tso->stackobj;
  stack->sp = stack->stack + stack->stack_size - sizeofW(StgUnderflowFrame);
  threadStackUnderflow(cap, tso);
  return tso->stackobj;
}

// see Note [Continuations overview]
StgClosure *captureContinuationAndAbort(Capability *cap, StgTSO *tso, StgPromptTag prompt_tag)
{
  // We’d better own this thread if we’re doing this!
  ASSERT(tso->cap == cap);

  StgStack *stack = tso->stackobj;
  StgPtr frame = stack->sp;

  // We perform the capture in two phases:
  //
  //   1. We walk the stack to find the prompt frame to capture up to (if any).
  //
  //   2. If we successfully find a matching prompt, we proceed with the actual
  //      by allocating space for the continuation, performing the necessary
  //      copying, and unwinding the stack.
  //
  // These variables are modified in Phase 1 to keep track of how far we had to
  // walk before finding the prompt frame. Afterwards, Phase 2 consults them to
  // determine how to proceed with the actual capture.

  StgWord total_words = 0;
  bool in_first_chunk = true;
  StgWord first_chunk_words = 0;
  StgWord last_chunk_words = 0;
  StgWord full_chunks = 0;

  // see Note [Continuations and async exception masking]
  const StgInfoTable *apply_mask_frame = NULL;
  StgWord mask_frame_offset = 0;

  /* --- Phase 1: Find the matching prompt frame ---------------------------- */

  IF_DEBUG(continuation,
    debugBelch("captureContinuationAndAbort: searching for prompt\n");
    debugBelch("  prompt_tag = "); printClosure(prompt_tag));

  while (true) {
    IF_DEBUG(continuation,
      printStackChunk(frame, frame + stack_frame_sizeW((StgClosure *)frame)));

    const StgInfoTable *info_ptr = ((StgClosure *)frame)->header.info;
    const StgRetInfoTable *info = get_ret_itbl((StgClosure *)frame);
    StgWord chunk_words = frame - stack->sp;

    if (info_ptr == &stg_prompt_frame_info
        && ((StgPromptFrame *)frame)->tag == prompt_tag) {
      total_words += chunk_words;
      if (in_first_chunk) {
        first_chunk_words = chunk_words;
      } else {
        last_chunk_words = chunk_words;
      }
      break;
    }

    if (info->i.type == UNDERFLOW_FRAME) {
      total_words += chunk_words;
      if (in_first_chunk) {
        first_chunk_words = chunk_words;
      } else {
        full_chunks++;
      }

      stack = ((StgUnderflowFrame *)frame)->next_chunk;
      frame = stack->sp;
      in_first_chunk = false;
      continue;
    }

    // Finding any of these mean we failed to find the prompt frame;
    // see Note [When capturing the continuation fails] for details
    if (RTS_UNLIKELY(info->i.type == STOP_FRAME
                  || info->i.type == UPDATE_FRAME
                  || info->i.type == ATOMICALLY_FRAME
                  || info->i.type == CATCH_RETRY_FRAME
                  || info->i.type == CATCH_STM_FRAME)) {
      IF_DEBUG(continuation,
        debugBelch("captureContinuationAndAbort: could not find prompt, bailing out\n"));
      return NULL; // Bail out
    }

    // see Note [Continuations and async exception masking]
    if (is_mask_frame_info(info_ptr)) {
      mask_frame_offset = total_words + chunk_words;
      if (apply_mask_frame == NULL) {
        if ((tso->flags & TSO_BLOCKEX) == 0) {
          apply_mask_frame = &stg_unmaskAsyncExceptionszh_ret_info;
        } else if ((tso->flags & TSO_INTERRUPTIBLE) == 0) {
          apply_mask_frame = &stg_maskUninterruptiblezh_ret_info;
        } else {
          apply_mask_frame = &stg_maskAsyncExceptionszh_ret_info;
        }
      }
    }

    // Advance to the next frame.
    frame += stack_frame_sizeW((StgClosure *)frame);
  }

  /* --- Phase 2: Perform the capture --------------------------------------- */

  IF_DEBUG(continuation,
    debugBelch("captureContinuationAndAbort: found prompt, "
               "capturing %" FMT_Word " words of stack\n", total_words));

  dirty_TSO(cap, tso);
  dirty_STACK(cap, stack);

  StgContinuation *cont = (StgContinuation *)allocate(cap, CONTINUATION_sizeW(total_words));
  SET_HDR(cont, &stg_CONTINUATION_info, stack->header.prof.ccs);
  cont->apply_mask_frame = apply_mask_frame;
  cont->mask_frame_offset = mask_frame_offset;
  cont->stack_size = total_words;

  stack = tso->stackobj;
  StgPtr cont_stack = cont->stack;
  memcpy(cont_stack, stack->sp, first_chunk_words * sizeof(StgWord));
  cont_stack += first_chunk_words;

  if (in_first_chunk) {
    stack->sp += first_chunk_words;
  } else {
    stack = pop_stack_chunk(cap, tso);

    for (StgWord i = 0; i < full_chunks; i++) {
      const size_t chunk_words = stack->stack + stack->stack_size - stack->sp - sizeofW(StgUnderflowFrame);
      memcpy(cont_stack, stack->sp, chunk_words * sizeof(StgWord));
      cont_stack += chunk_words;
      stack = pop_stack_chunk(cap, tso);
    }

    memcpy(cont_stack, stack->sp, last_chunk_words * sizeof(StgWord));
    cont_stack += last_chunk_words;
    stack->sp += last_chunk_words;
  }

  ASSERT(cont->stack + total_words == cont_stack);
  ASSERT(((StgClosure *)stack->sp)->header.info == &stg_prompt_frame_info);
  stack->sp += stack_frame_sizeW((StgClosure *)frame);
  IF_DEBUG(sanity,
    checkClosure((StgClosure *)cont);
    checkTSO(tso));

  return TAG_CLOSURE(2, (StgClosure *)cont);
}