uncancelable polls for cancelation at the start of the region

[djspiewak]

Spinning out of a chat which began here, in Discord.

The essence of this semantic question revolves around the following snippet:

uncancelable(p => fa >> p(uncancelable(_ => fb)).onCancel(fc))

If we imagine that the external cancelation signal "arrives" somewhere around the >>, where is it observed? Another way of looking at this: is the above equivalent to uncancelable(_ => fa >> fb)? In the present implementation, the cancelation is observed immediately prior to the inner uncancelable, and the fb will not run (the fc will).

This is happening because uncancelable, like every other IO stage, polls the cancelation flag at the start of its execution. Just prior to the 3.0 release, we made an adjustment to semantics where we changed uncancelable to no longer poll the cancelation flag at the end of its region, which was necessary to avert unavoidable boundary leaks. We did not, however, change the front of its region, which is what this discussion is about.

It's not entirely clear that this behavior is wrong, per se. It is, after all, basically the same as what happens with fibers. We can rewrite the above snippet to use the same trick that CE2 used for continual to surface this symmetry:

fa >> fb.start.flatMap(f => f.cancel >> f.join.flatMap(_.fold(fc, _ => unit, _ => unit)))

Conceptually, the cancelation is sneaking in prior to the body of the fiber being scheduled, meaning that in most cases, the above will execute fc and not fb. This is similar to how uncancelable polls the cancelation flag prior to execution. If we changed things such that uncancelable no longer does this, the above snippet involving fibers will still cancel prior to execution (since this goes through a different pathway), but the original snippet will be treated as an atomic block. There's no law which says this is bad, but it feels a bit weird.

Additionally, it's not entirely clear that this semantic creates unresolvable issues, unlike the more serious end-of-region issue. For example, the motivating case here comes from Queue#take, which has an internal bit which looks a lot like this:

              State(queue, size, takers.enqueue(taker), offerers) ->
                (poll(taker.get).onCancel(cleanup.flatten) >> poll(take))

Somewhat simplified, but still. This is inside of a Ref#modify, and the resulting F[F[A]] is flattened inside of an uncancelable, which is the definition of take. Thus, the poll here is directly wrapping around an uncancelable. The problem with the above is that cancelation might be observed at the start of the recursive take, and when it is, we don't sequence the cleanup action, which in turn leaks a notification and can result in system deadlock.

As noted though, this problem is avoidable simply by moving the onCancel outside of both polls, meaning that cleanup will run regardless of where cancelation is observed. The consequence for Queue is a slight expansion of the fairness corruption which happens when a blocked taker is canceled after being awakened, in that potentially more than one other taker will be spuriously awakened and then forced to go to the back of the line (depending on how deep the recursion goes), but this is a very minor problem. In particular, the recursion is almost never more than one level deep, and even when it is, the number of takers is often not high (MPSC is far and away the most common mode for Queue), and even when it is, this minor corruption of fairness is very rarely a problem or even noticeable in practice.

All of which is to say that this particular issue seems less concerning, which is why we are leaving the semantic in place for the time being. Please consider this discussion an open invitation to bikeshed and opine as to whether this is the right course of action. Note that changing this semantic is possible for IO, though likely to involve a small performance detriment (due to the injection of an additional conditional jump into runLoop and the corresponding degradation of CPU pipelining). The greater concern with making such a change is whether some code in the wild is implicitly relying on this semantic in some way.