Two-phase unwinding and its implications

[aheejin]

Foreword

Recently, the need for two-phase stack unwinding has been suggested. Two-phase unwinding is a useful feature for debugging, because the stack can be preserved when an exception is not caught and the program crashes. Also, it is necessary to implement the full semantics of languages such as C# (due to its when clause). While each language may implement it in their own library if necessary, supporting it in the spec level can be more convenient or faster. We didn’t think it was an essential feature to support in the spec before, and I think whether we should support this in the spec level or not is also something we should discuss.

In this issue, I’ll address the implication to the current proposal if we decide to support it. This issue is not only about adding syntax for two-phase unwinding itself; it is more about the extensibility of the current proposal in case we support the two-phase later.

Two-phase unwinding

Two-phase unwinding consists of two phases. The first phase is the ‘search’ phase; it walks up the stack without unwinding it and checks each catch instruction (= landing pad) to see if it catches the current exception. If it does not catch the current exception, we continue the search. If the search phase ends and none of the catches catches the current exception, we end the unwinding there without running the second phase, leaving the call stack intact. If we found a catch that catches the exception, we remember the result, and begin the second, ‘cleanup’ phase. In this phase, we actually unwind the stack, while running all cleanup (= destructor) code, until we reach the catch that catches the exception. After we arrive at the destination catch, we stop the second phase unwinding there, and transfer the control flow to that catch.

Two-phase unwinding will require catch instruction to have a way of filtering an exception. That can be an index to a wasm function, or a code block attached to a catch instruction. And the VM should be able to run these functions or code blocks without disturbing the call stack during the first ‘search’ phase of two phase unwinding.

But other than adding a filter function to catch, we may need more changes to the current proposal. The most important one of them is exnref, which I will elaborate on next.

Background on first-class exnref

We introduced first-class exnref type in 2018, mainly to support more expressive code transformation in the toolchain.

The specific problem that sparked this discussion was that, after the “CFG stackification” phase in the toolchain, in which we place marker instructions like block, try, loop, and end, it is possible that there can be mismatches in calls’ or throws’ unwind destinations. This problem was first discussed in #29 (with different solutions then). To re-summarize the problem here, suppose we have the following CFG:

bb0:
  call @foo (if it throws, unwind to bb2)
bb1:
  call @bar (if it throws, unwind to bb3)
bb2 (ehpad):
  catch
  ...
bb3 (ehpad):
  catch
  handler body

And the CFG is sorted in this order. Then after placing try markers, the wasm code will look like:

try $label1
  try
    call @foo
    call @bar   (if it throws, it should unwind to catch2, but is caught by catch1)
  catch1         <- ehpad (bb2)
    ...
  end_try
catch2           <- ehpad (bb3)
  handler body
end_try

The first-class exnref allows us to fix this kind of mismatches because with that now exnrefs can escape their original catch blocks they are originally caught and we can freely branch to the right handler to use them.

Incompatibility of first-class exnref and two-phase unwinding

Suppose we extend our current proposal to support two-phase stack unwinding. In the first phase of the unwinding, we walk up the stack to examine each catch’s filter function without actually unwinding the stack, meaning we shouldn’t run any catch bodies. In order to do that, we can use the internal EH pad stack maintained in the VM. But the problem when we have exnrefs that can escape catch bodies is, we don’t have a way to find out the next catch in this first search phase.

try
  try
    call @foo
  catch1
  end
catch2
end

In this example, when foo throws, the first phase should check catch1 first, and if it does not catch the current exception, it should check catch2 next. But with exnref, the code can look like this:

try
  try
    call @foo
  catch1
    local.set 0
    br 1
  end
catch2
end

In this case, semantically the program shouldn’t run catch2 body anymore, because we branch out of both try blocks. But the first phase, which does not run any catch bodies and only check filter functions, will check catch2 after checking catch1. This was not a problem when we only have a single phase, because in that case we run the actual program and unwind the stack as we go. But with two-phase unwinding, we need a way to examine a sequence of catches in the first phase without running the program.

Recently #118 and #122 claimed the current proposal is not extensible to support the two-phase unwinding feature. I, @dschuff, @tlively and @RossTate had a video meeting, and while I’m not sure Ross’s reasoning was the same as the things I described here, we agreed that escaping of first-class exnref can cause problems for future two-phase unwinding.

Necessary changes to the current proposal

In short, we need to remove the first-class exnref, which pretty much means going back to the first version of the exception handling proposal. catch instruction now can be back to catch $tag and catch_all (but this may not be a must). We may not need br_on_exn anymore if we restore tagged catches, but having it can also increase code generation flexibility, in which case, it will assume the current exception as an implicit argument. But if we remove first-class exnref, we need a way to solve the unwind destination mismatch problem I described above.

Adding catch_br instruction

One possible addition to the current spec I and @dschuff thought about is catch_br instruction. So now we have two kinds of try-catches: one is the same as the current one:

try
  …
catch
  …
end

On top of that, we now have one additional syntax:

try
  …
catch_br $label

catch_br does not have a body, so it does not need an end at the end. If any instruction between try and catch_br throws, we transfer control flow to an outer catch that is specified by the label. The label will be written as an immediate in binary, as in the case of br. The unwind mismatch example above can be solved using this instruction:

try $label2
  try
    call @foo (unwinds to catch1)
    try
      call @bar    (should unwind to catch2)
    catch_br $label2
  catch1
    ...
  end_try
catch2
  handler body
end_try

Now we introduce an internal try-catch_br, so when bar throws, we can transfer the control flow to catch2, bypassing catch1. We can follow these labels in the first phase search too. Because these labels (= immediates) are statically determined, we don’t need to run or refer to any catch bodies to search the stack.

Splitting of catch and unwind

The second, ‘cleanup’ phase involves running destructor code and unwinding the stack. But after running destructor code, we need a way to resume the second phase unwind until we arrive at the destination catch found by the search phase. rethrow will not solve this problem, because rethrow is the same as throw except it retains auxiliary information, such as stack traces, so it will trigger a full two-phase search from scratch. One way to fix this is splitting catch and unwind block, so that we add try-unwind, and assume at the end of unwind block the second phase search is automatically resumed:

try
  …
unwind
  destructor code
end

This was one of changes suggested in #118. Another alternative to this is to add another instruction resume. This is different from rethrow; this does not initiate a full two-phase search. This merely resumes the second phase unwinding. The toolchain will be responsible for generating resume after destructor code.

Concluding remarks

Apparently this is a lot to put in a single issue post, but I’d like to start discussions from here. There are many things we need to discuss:

1. Should we add two-phase stack unwinding to the spec?
2. If we add two-phase unwinding, what will the end goal look like? (This post is mostly dedicated to this part)
3. If we add two-phase unwinding, should we do that in the current EH proposal, or the follow-on proposal?
4. If we decide to split the EH proposals into current and follow-on, what is the splitting point?
5. If we decide to split the EH proposals into current and follow-on, how should two modules compiled with first and follow-on proposals work together?

Apparently we can’t discuss all these at once; I think we should start from 1 and 2.

Also I’d like to hear from VM people as well, because two-phase unwinding, especially running filter functions in a separate stack, will likely to be not a simple matter from the VM side.

[RossTate]

@aheejin This is a really great summary of our discussion and framing of the key questions! Thanks for putting it together!

I have only one thing to note: the filter functions do not need to be run on a separate stack; they can be run on the leaf of the stack being examined.

I also have something new to add relevant to Question 1. We've been working on stack switching, and we were stuck on how to provide a good way to detach stacks, say in order to attach them to a JS promise so that execution can be continued later. While most of the proposal uses exception-handling events incorporating the changes above, we recently realized that the best way to specify when to detach stacks would be to let code specify a phase-one filter-like function. I won't go into the details (we'll hopefully have a draft up soon), but likely this sort of functionality will need two-phase exception handling. To clarify per Question 3, stack switching does not need two-phase in the current EH proposal; it just seems to need the current EH proposal to be compatible with it.

[backes]

Also I’d like to hear from VM people as well, because two-phase unwinding, especially running filter functions in a separate stack, will likely to be not a simple matter from the VM side.

Agreed, it's not totally straight-forward, but doable. If we decide to spec filter functions, we will also need to think about what happens if the filter function throws another exception which is not caught within the scope of the filter function.

[littledan]

Recently, the need for two-phase stack unwinding has been suggested. Two-phase unwinding is a useful feature for debugging, because the stack can be preserved when an exception is not caught and the program crashes. [...] We didn’t think it was an essential feature to support in the spec before, and I think whether we should support this in the spec level or not is also something we should discuss.

This part seems pretty core. How should we evaluate whether two-phase unwinding is important for the MVP of exception handling? Do we have new information that leads us to change the previous judgement that it wasn't an essential feature to support? Would a later evolution from the current design to two-phase unwinding be possible if we were OK with having some duplication in the instruction set?

[tlively]

The new information we have is that there is no clear way to extend the current exception mechanism to allow two-phase unwinding. Another piece of new (to me) information is that there exist languages (e.g. C#) that need to use two-phase unwinding because they make the phases semantically observable.

IMO, supporting a niche feature of C# is not important enough that we have to introduce two-phase unwinding into this initial EH proposal, but it might be important enough (in combination with other benefits of two-phase unwinding) that we would want to make this proposal easily extensible to support two-phase unwinding in the future. The alternatives are that either we would never support two-phase unwinding or we would have to introduce a whole new exception handling mechanism to support two-phase unwinding in the future, which would significantly complicate WebAssembly's semantics.

[aheejin]

Recently, the need for two-phase stack unwinding has been suggested. Two-phase unwinding is a useful feature for debugging, because the stack can be preserved when an exception is not caught and the program crashes. [...] We didn’t think it was an essential feature to support in the spec before, and I think whether we should support this in the spec level or not is also something we should discuss.

This part seems pretty core. How should we evaluate whether two-phase unwinding is important for the MVP of exception handling? Do we have new information that leads us to change the previous judgement that it wasn't an essential feature to support? Would a later evolution from the current design to two-phase unwinding be possible if we were OK with having some duplication in the instruction set?

I personally think the importance of C#'s niche feature is not very significant. We asked Blazor developers and they said the usage of that feature is very rare and they didn't think it warrants a whole redesign. If we go two-phase unwinding route, I think a more important reason would be it allows us to preserve the whole stack intact in case an exception is not caught, which will help debugging.

What changed in our assessment about the two-phase unwinding is little unclear. I only found one mention of that in this repo here: #49 (comment). It seems that we didn't want to enforce all implementors to have two-phase unwinding, and wanted to leave it as an implementation choice. It is true that we can implement this in languages' own library. The downside of that can be it will not work with multiple languages and it will be slower (it will not be zero-cost anymore). But that will simplify the spec and allow implementors not implement the (relatively more complicated) two-phase unwinding.

[backes]

If we go two-phase unwinding route, I think a more important reason would be it allows us to preserve the whole stack intact in case an exception is not caught, which will help debugging.

This is an interesting feature indeed, but it does not require the full-fledged two-phase design proposed here. Without filter functions (which need to be executed in order to know whether they match) it would be enough to split catch and unwind, and we could determine whether an exception will be caught when it is thrown.

[aheejin]

If we go two-phase unwinding route, I think a more important reason would be it allows us to preserve the whole stack intact in case an exception is not caught, which will help debugging.

This is an interesting feature indeed, but it does not require the full-fledged two-phase design proposed here. Without filter functions (which need to be executed in order to know whether they match) it would be enough to split catch and unwind, and we could determine whether an exception will be caught when it is thrown.

How can we know if it will be caught or not in advance without running filter functions? Do you mean tag checks? But what I meant here by "caught" is that it really be caught in the language level. For example, in this C++ program,

try {
  throw 3;
} catch (float f) {
}

This exception will not be caught in C++. What the filter function for this catch will check is if the current exception is of type float or not. If we only check tags, within C++, every C++ catch will catch every C++ exception, which will not be very helpful for debugging.

Please let me know if you didn't mean this and I'm mistaken.

[backes]

Note the "without filter functions" in my comment. What I meant was: As long as we don't introduce filter functions, we don't need heavy machinery to figure out if an exception is caught or not. All it needs is splitting catch and unwind.

But from your comment I learned that even for C++ we would need filter functions, so my comment is pretty pointless I guess.

[littledan]

If we go two-phase unwinding route, I think a more important reason would be it allows us to preserve the whole stack intact in case an exception is not caught, which will help debugging.

What problems do you see with the JavaScript approach of snapshotting the stack when the exception is allocated and/or first thrown, and then also having a feature in DevTools to allow pausing on uncaught or all exceptions? Does this provide insufficient information for debugging?

For example, maybe the purpose of this is to make the DevTools catch prediction more accurate, so we preserve not just the stack but the full execution state, in the case where there's a catch block enclosing the throw which does not correspond to this type of exception. If this were the goal, then I could vaguely imagine a scheme for a custom section that could be specifically to help DevTools catch prediction, but not affect the normal runtime semantics.

[RossTate]

Also I’d like to hear from VM people as well, because two-phase unwinding, especially running filter functions in a separate stack, will likely to be not a simple matter from the VM side.

Agreed, it's not totally straight-forward, but doable. If we decide to spec filter functions, we will also need to think about what happens if the filter function throws another exception which is not caught within the scope of the filter function.

@backes It's not the case that filter functions need to be run on a separate stack. Many language runtimes run them on the current stack. That is, semantically they are just like function calls. And implementation-wise, they're similar to function calls, except that the engine finds the code pointer for the call by walking the stack (to find the filter function) and when making the call the engine provides the code pointer with the stack frame that has all the local variables the filter function uses.

We will likely need to support this functionality anyways for stack inspection, which is very widely used. For example, stack inspection is used to collect the roots for an implemented-in-linear-memory (rather than host supported) garbage collector, and also to collect the current stack trace in terms of source code (rather then WebAssembly code). In other words, most language runtimes rely on stack inspection, i.e. the first phase, in some way or another. C# is only an outlier in that its semantics visibly relies on stack inspection as well.

It is true that we can implement this in languages' own library. The downside of that can be it will not work with multiple languages and it will be slower (it will not be zero-cost anymore).

Note that the same is true for single-phase exception handling.

Putting the above together, without supporting the same functionality that two-phase exception handling would require, most language implementations would likely have to implement all exception handling on their own and not use the exception-handling proposal (except for interop) in order to provide full functionality.

[aheejin]

@littledan

If we go two-phase unwinding route, I think a more important reason would be it allows us to preserve the whole stack intact in case an exception is not caught, which will help debugging.

What problems do you see with the JavaScript approach of snapshotting the stack when the exception is allocated and/or first thrown, and then also having a feature in DevTools to allow pausing on uncaught or all exceptions? Does this provide insufficient information for debugging?

For example, maybe the purpose of this is to make the DevTools catch prediction more accurate, so we preserve not just the stack but the full execution state, in the case where there's a catch block enclosing the throw which does not correspond to this type of exception. If this were the goal, then I could vaguely imagine a scheme for a custom section that could be specifically to help DevTools catch prediction, but not affect the normal runtime semantics.

As you said, we can get the stack trace with JavaScript approach of snapshotting the stack, but we wouldn't be able to inspect the full stack and all memory and locals at each call frame, the functionality most debuggers provide when a program crashes. I don't think this can be done by some auxiliary info in the custom section..? And not very sure what you mean by catch prediction. Could you elaborate?

[littledan]

Across multiple (all?) browsers, DevTools supports pausing on only exceptions which are uncaught. For example, in Chrome, open up the "sources" panel and click on the stop sign/pause button icon in the top right corner--if you don't check the "Pause on caught exceptions" box, then only exceptions which DevTools thinks are uncaught will lead to a breakpoint. During this pause, you can inspect the full program state.

Catch prediction the term used inside Chrome to refer to the algorithm used to guess whether an exception will be caught, at the point in time that it's thrown. Catch prediction is just a heuristic (e.g., due to some edge cases around returning from finally blocks), but it's a very useful one.

One problem, common to this current proposal and JS, is that all catch blocks predict as catching all exceptions. If we could expose some metadata to DevTools so that it could approximate the filters at the time the exception is thrown, then catch prediction could become more accurate without changing how ordinary program execution works.

I'd be happy to discuss this further on this thread, in a call, gchat, whatever works for you. But I'm actually not working on Wasm debugging; it'd probably be good to pull in people who are actually working on that to this conversation, if we're making a decision motivated by debugging (not sure who the right contacts are at the moment).

[rossberg]

Thanks for writing this up @aheejin and summarising a longish discussion. I'm still a bit confused, though.

we agreed that escaping of first-class exnref can cause problems for future two-phase unwinding.

I don't follow where this conclusion is coming from. AFAICS, the problem with the example you give is that it branches out of the handler, presumably without rethrowing to propagate to the next handler. That would be wrong in this context regardless of whether you have an exnref or not -- the problem is the control flow, not whatever the way is the exn value is provided. Can you elaborate on how specifically exnref is relevant to the problem?

Adding catch_br instruction

As a side note, replacing a block-like catch clause with a branch is something we also did for the continuations/stack switching stuff I presented in February (where it is part of the resume instruction instead of try). That seems simpler than another block. If it was earlier in the lifetime of the current proposal, I would indeed propose to simplify the existing try instruction to

try <instr>* catch $l

where $l is a label receiving type [exnref].

But the motivation here seems to avoid the exnref, so I can perhaps say more once I understand what actual problem that solves, see question above.

Splitting catch and unwind

I believe this could be added as a later refinement to the semantics in the current proposal just fine, for example by adding a filtering variant of the try instruction:

try <instr1>* catch-when $f <instr2>* end

This works like the existing try, except that in the first phase it doesn't run <instr2>* but merely invokes $f, which is a function of type [exnref] -> [i32]. If this returns 0, find the next handler. Otherwise, unwind and run <instr2>*.

The existing try could then be viewed as a shorthand whose function always returns 1 immediately.

(The extension could similarly be made to the simplified branching try above, like (try <instr>* catch-when $l $f).)

There might be alternatives to this design, e.g., replacing the filter function with another jump label and an additional propagate instruction. However, I think not having the filter as a separate function would make it way more difficult to run it without switching stacks, especially since it would then expect access to locals of each try-context.

[RossTate]

Can you elaborate on how specifically exnref is relevant to the problem?

Here's my sense of the problem. In two-phase EH systems, the first phase concludes by determining where(/if) to unwind to. In WebAssembly, this destination seems to best correspond to a label (and there is no event involved). The important implication of this is that unwinding is conducted with a destination in mind. That destination information has to be maintained throughout the unwinding process (which ends either upon reaching the destination or if an unwinder aborts the unwinding process, e.g. by branching out of the unwinding block). This is typically done by treating unwinders on the stack as functions, running each unwinder and then continuing the unwinding process to the predetermined destination once the unwinder concludes.

This unwinders-as-functions strategy requires unwinders to have a clear start and end. But the reason exnref was introduced was so that it could escape the catch block and be handled elsewhere in the CFG, which was important for handling various code transformations. We realized we could also solve the problem exnref was solving by enabling a try block to specify an unwinder that is defined elsewhere. With that problem solved, we could have unwinders be function-like blocks that continue the unwinding process upon reaching the end of the block.

However, I think not having the filter as a separate function would make it way more difficult to run it without switching stacks, especially since it would then expect access to locals of each try-context.

There is no need for multiple stacks. You can just call the filter function on the current stack, giving it the relevant stack-frame pointer. This implementation strategy is capable of more than just filter functions. In fact, it's how Common Lisp implements resumable/restartable exceptions. In order to avoid digging into Common Lisp, I found this blog post by someone exploring/discussing how to add resumable exceptions to the Java language and runtime, in case it's helpful for anyone wanting to understand how one implements two-phase exception handling on a single stack.

[aheejin]

@rossberg

I don't follow where this conclusion is coming from. AFAICS, the problem with the example you give is that it branches out of the handler, presumably without rethrowing to propagate to the next handler. That would be wrong in this context regardless of whether you have an exnref or not -- the problem is the control flow, not whatever the way is the exn value is provided. Can you elaborate on how specifically exnref is relevant to the problem?

The problem is, I branch out without rethrowing in order to rethrow from another catch, to solve the unwind destination mismatch problem above. So let me bring my example mismatching problem again:

try $label2
  try
    call @foo
    call @bar   (if it throws, it should unwind to catch2, but is caught by catch1)
  catch1
    ...
  end_try
catch2
  handler body
end_try

To solve this mismatch, the toolchain does this kind of transformation:

try $label2
  try
    call @foo
    try
      call @bar
    catch
      local.set 0
      br $label2    <- branch to 'handler body'
    end
  catch1
    ...
  end_try
catch2
end
handler body   <- Now factored out of catch2
end_try

What this does is basically to introduce an inner try-catch, and within its catch body, branch to the right handler code. Here 'handler body' was originally in catch2 but factored out so that it can be the destination of br $label1.

The problem is, this kind of transformation happens within toolchain, and the user should be unaware of it. Assuming we have two-phase unwinding and a filter function is attached to every catch. From the user's perspective, if bar throws and it is not caught by any catches, the first search phase should be able to determine that. But in this transformation we navigate from an programmatically introduced inner catch to the correct outer catch using br, the first phase cannot determine the search path in the first place for this exception thrown from bar. What I meant by two-phase unwinding is not compatible in the post is that we cannot make two-phase unwinding work correctly in the language level, such as C++. This problem will occur not only in C++ or LLVM, but with any compiler framework that transforms basic block structure into the linearized wasm block structure.

If we don't allow exnref and thus don't allow rethrowing outside of catch, the first phase will simply be able to walk up the EH pad to find a matching catch. But we still have the unwinding mismatch problem then, so that's the reason I came up with catch_br; this transfers control flow from one catch to another, which I did with exnref to fix this mismatch problem. But now this trasnfer is statically encoded in catch_br instruction, so the first search phase has no problem accessing that info and following it.