Lwt: Lwt.pick/Lwt.cancel don't cancel certain pending tasks

[stijn-devriendt]

Consider followig snippet:

let test_lwt () =
  let sleeper =
    lwt () = Lwt_unix.sleep 1.0 in
    let () = Printf.printf "sleeper done\n" in
    Lwt.return ()
  in
  let fast_thread () =
    lwt () = sleeper in
    let () = Printf.printf "fast thread done\n" in
    Lwt.return ()
  in
  let slow_thread () =
    lwt () = sleeper in
    let () = Printf.printf "additional sleep\n" in
    lwt () = Lwt_unix.sleep 1.0 in
    let () = Printf.printf "slow thread done\n" in
    Lwt.return ()
  in
  let threadlist = [fast_thread (); slow_thread ()] in
  lwt () = Lwt.pick threadlist in
  let () = Lwt.cancel (List.nth threadlist 1) in
  let () = Printf.printf "canceled everything\n" in
  lwt () = List.nth threadlist 1 in
  let () = Printf.printf "threads bound\n" in
  Lwt.return ()

let result = Lwt_main.run (test_lwt ())

The expected behavior would be that the Lwt.pick and explicit Lwt.cancel cancel the slow_thread and the final bind to slow_thread raises Lwt.Canceled. In reality however, slow_thread runs to completion and the final bind succeeds:

sleeper done
fast thread done
canceled everything
additional sleep
slow thread done
threads bound

As for underlying behavior, this is probably caused by both fast_thread and slow_thread being bound on the same lwt-task. So, Lwt.pick sees that fast_thread ends and tries to cancel slow_thread, which is still bound on the sleeper, which in the mean-time has a result assigned so cannot be canceled anymore. Therefore the pick nor the cancel actually perform any cancellation work, letting the slow_thread run to completion.

[aantron]

The expected behavior...

I would also intuitively expect that behavior. I believe your last paragraph describes the actual behavior accurately. Cancelation may need to be adjusted somewhat.

As you may already know, you can avoid this behavior in current Lwt in at least two ways:

1. Don't bind on a common thread (make sleeper a thunk that generates threads).
2. Use Lwt.protected on the common thread:

ocaml let slow_thread () = lwt () = Lwt.protected sleeper in let () = Printf.printf "additional sleep\n" in lwt () = Lwt_unix.sleep 1.0 in let () = Printf.printf "slow thread done\n" in Lwt.return () in

I guess neither is ideal, because (1) can cause repetition of side effects, and (2) does not allow to automatically cancel sleeper if Lwt.protected is used in all threads that bind on it and may be canceled. However, if using (2), you can still cancel sleeper explicitly, though it means you must know about sleeper at the place in your code where you use Lwt.pick.

I'll take a look at this in more detail in some days. Proposals to fix this or rework cancelation are also welcome.

In the past, I have considered making all threads cancelable by default (i.e. task replaces wait), and making each bind generate a cancelable thread by default, though I think these are breaking changes, and may affect performance.

[stijn-devriendt]

We haven't actively looked for solutions to this; In the past it's been worked around by adding external cancellation flags, without really investigating the root cause.

One (perhaps naive) solution would be to extend a thread result:
Return of 'a
Return_cancel of 'a
Sleep of 'a sleeper
Fail of exn
Repr of 'a thread_repr

Bind's could then behave as follows:

• cancellable will get cancelled (i.e. cancel takes priority over result)
• non-cancellable will get result (i.e. result takes priority over cancel)

In the case of pick, it would mean that the elected thread needs to be handled first (seeing Return), followed by updating the result to 'Return_cancel', handling the remaining threads with that result.

Unfortunately, I believe this is quite an undertaking and I'm sure it will lead to interesting decisions to be made in some of the internals.

[aantron]

Yes, I will have to add this to some kind of to-be-created list of project-scale tasks to work on in the future. Issues around cancelation have been bothering me for a while, but dealing with this will require quite some study of usages and scenarios.

[raphael-proust]

I'm investigating this. I'm not sure I'll fix it, but I'll share notes and findings.

Also, I'll actually investigate on the human friendly rewrite because it's human-friendly.

[aantron]

Great. I actually recommend not fixing this for now, but investigation definitely welcome :)

• The old lwt.ml obviously is not friendly..
• The new one might suffer a rebase or other revisions.

I'm actually itching to merge the new one in, to get rid of the uncertainty, but there's the plan.

[raphael-proust]

Investigation notes:

The bug reproduces on both the pre-rewrite and post-rewrite versions.

The bug is in the cancel logic – see below. In particular, the Lwt_unix module is correct: it uses task which is cancellable.

---

From a high-level, the problems boils down to the fact that

1. the slow_thread is bound early, when sleeper is pending, and
2. the cancellation of slow_thread is done late, when sleeper is resolved.

Binding to a pending thread sets the cancellation to propagate down the graph.
Cancelling a resolved thread does nothing.

---

Specifically, the algorithm for cancellation does the following two things (marked THIS and THAT):

        match p.state with
        (* If the promise is not still pending, it can't be canceled. *)
        | Resolved _ ->  (* THIS *)
          callbacks_accumulator
        | Failed _ ->
          callbacks_accumulator

        | Pending callbacks ->
          match callbacks.how_to_cancel with
          […]
          | Propagate_cancel_to_one p' ->  (* THAT *)
            cancel_and_collect_callbacks callbacks_accumulator p'

And the binding algorithm does the following (HERE):

  let bind p f =
    […]
    match p.state with
    […]
    | Pending p_callbacks ->  (* HERE *)
      let p'' = new_pending ~how_to_cancel:(Propagate_cancel_to_one p) in

When the slow thread is created, the sleeper is pending.
As a result (because of HERE), the cancellation method is set to Propagate_cancel_to_one.
When cancelling, the algorithm finds that slow_thread is Pending.
The cancellation algorithm goes backward in the thread graph (because of THAT).
Ultimately, it arrives at the sleeper thread.
And then it does nothing (because of THIS).

---

Ideas for fixing:

• In cancel, when going up the graph, have a mechanism that detects that you are just going up towards a cancellable-but-resolved promise. In this case, set the farthest not-yet-cancelled thread to be cancelled.
• In cancel, set all visited threads to be cancelled. I'm not quite clear what that means exactly and whether it can even mean something. The idea would be that, in that particular case, the cancellation algorithm would set both slow_thread and sleep (as well as the other, nameless thread created by the bind inside the definition of slow_sleep) to be cancelled.

---

Things to do in the mean time

Note that the semantics of cancelling are currently not very clear. (E.g., this bug report.) This means that, if we are to revamp this system (e.g., to fix this bug report), we would need to spend some time checking that it doesn't break existing code.

This suggest two things that can be done now:

• have a conversation about the cancellation semantics
• collect regression tests

Both are a group effort: please contribute to the discussion; and collect in your source code the different uses of cancel and try to make a minimal example that capture that use.

[aantron]

Here is a small contribution to the conversation: a brief description of how cancelation currently works. Readers may want to scroll up a bit for context. Among other things, we need to put some such description into the .mli file, and have it be part of the published docs. The test suite already has the beginnings of thorough cancelation testing, but we need to include any more corner cases or complex scenarios we can find.

We should probably also look for links to other cancelation debates, such as one I heard happened during the standardization of ES6 promises. Cancelable promise libraries from other languages may help here, too.

[aantron]

There is also this: http://camlspotter.blogspot.ca/2017/03/a-glitch-of-lwt.html ("A Glitch of Lwt.cancel"). I think part of the overall problem is using thread language instead of promise language. It gives users the wrong idea about Lwt is actually implementing, what it is tracking, and therefore what can be done to it.

EDIT: opened an issue for it (#415).

[raphael-proust]

In Fut (http://erratique.ch/software/fut/doc/Fut.html), the function is called abort, not cancel and its semantics is to set the aborted future to a special state (Never) and to do the same on all the futures that it depends on.

The state Never propagates through bind. The programmer can use the function recover to transform 'a fut, a future of type α, into 'a set fut, where 'a set = [ Never | Det of 'a]. This way, the user can check explicitly for aborted (or otherwise never-determining) future.

(I'll check other libraries/frameworks and add comments below with a description of what cancelling does there.)

[raphael-proust]

For Javascript promises, there are currently no cancellation mechanisms. Someone proposes a hand-coded mechanism by which an additional promise is passed to a waiting function. This additional promise has a single purpose: raise a Cancel exception.

https://esdiscuss.org/topic/cancel-promise-pattern-no-cancellable-promises

The equivalent in Lwt would be something like the following:

exception CancelledError
let wait ms canceller =
    Lwt_unix.wait ms <?> canceller
;;

let foo () =
  let token, canceller = Lwt.task () in
  let promise =
    Lwt.catch (fun () ->
      do_stuff (* use token when waiting *) >>= fun ->
      Lwt.return ()
    ) (fun e ->
      …
    )
  in
  promise, canceller
;;

let t, canceller = foo () ;;
(* Use canceller to cancel t if need be *)

So basically, it's passing an explicit task (token, canceller) and what gets cancelled is this task. Because this token is explicitly passed to some calls to waiting/yielding functions, the programmer can choose the cancellation points.

Unlike Lwt, not only the possible cancellation points are explicit, which cancellation point is triggered is also explicit.

There are some weird stuff though. For example, if you do something like:

catch (fun () ->
  blah () >>= fun () ->
  wait 0 token >>= fun () ->
  gloubiboulga ()
) (function CancelledError ->
  lalala ()
)

Then some of the effects of lalala() can be observed before the effects of blah () finish.

---

It's interesting to have explicit cancellation points and to be able to choose them. I'm not sure it's practical (it's very verbose as is) or intuitive (it can cause strange orders).

Also, it's something that can be done by the programmer if they really need that feature. More important is to find the right behaviour for a library-side cancel.

[aantron]

This will also be useful if/when porting lwt.ml to JS. I was considering disabling cancelation completely in that variant.

[ibukanov]

In theory this bug can be fixed if cancel can change the state of a resolved promise from Return _ to Fail Canceled. This way if children promises are bound to the same parent and the first child cancels the parent, it prevents other children to run. In practice this immediately leads to a lot of issues like iterations with various callbacks breaking a lot of code in subtle ways with no help from the compiler to find out about that.

Perhaps a more practical approach is to focus on fixing Lwt.pick so it detects a case like this and stops binds that dependent on common ancestor? Compared to all-too-powerful cancel, the pick does not need to deal with promises besides those passed as its arguments. It is also interesting how pick is free from issues like #415.

[ibukanov]

@raphael-proust the issue of unexpected order of effects with explicit cancellation points and catch can be addressed if catch callbacks are never executed for CanceledError, so it triggers only finalize callbacks, not a generic catch. And in case when finalize itself triggers an exception, it will still trigger only later finalize callbacks, never any catch blocks. Essentially this is a Rust model where panic only executes pending destructors with no possibility of recovery besides starting a new thread.

[raphael-proust]

Modifying promises that have Returned to promises that have Failed seems like way too big of an invariant to break. Both within the internal logic of Lwt bu also in user code. Users are allowed to hang on to terminated promises for as long as they want and use them in other bindings.

---

I think that cancel is currently broken (the documentation is wrong; the semantic is basically not explainable without references to the code or very precise description of the code) and should be fixed. That might make pick better. Or maybe pick will need further fixing. In any way, fixing only pick doesn't seem like the right thing to do.

---

So in your model, the cancellation and the exception raising are separate? Basically the cancels are not normal exceptions but have a different control-flow mechanism (which happens to resemble but be independent from the raise/catch)? @ibukanov

[ibukanov]

@raphael-proust You are right that it is not possible to change the pick to address this bug without changing how cancellation works. For example, what should be a natural expected behavior when there are several picks waiting on a common promise?

So cancel model must be changed to make the behavior more useful. This issue and #415 suggests that a cancelable promise should have a flag like Canceled. This is in addition to the state. When the flag is set, it stops farther execution of any bind and catch callbacks no matter what was the current state of the promise. That is, if the promise was already resolved and the code was in one of the binds associated with it, no other binds will be executed. And if it was not resolved, not bind or finally will be executed at all.

To deal with cleanups on cancel, if the flag is set the first time before the promise is resolved, all finalize callbacks are run and the promise is resolved to Canceled or to the exception thrown during the finalization if any. This special casing of finalize allows to avoid any problems with catch that tries to swallow the cancel without adding an extra control flow constructions to deal with cleanups.

Such behavior clearly fixes this bug or more complex variations of it involving multiple waiting picks. In addition it also fixes #415 as cancel becomes:

val cancel : `a Lwt.t -> () Lwt.t

naturally stopping execution of the current code that self-reference a canceled promise.

[stijn-devriendt]

The solution to this problem doesn't necessarily need to be changing cancel semantics. Having a second call with different semantics might work too.

As a background to this discussion I'd like to highlight some of the issues we're facing:

• sometimes you want part of an operation to complete regardless of cancellation. i.e. postpone cancellation to a point where we're prepared to handle it. Currently we've written some fairly complex logic to accomplish this, but having such behavior in Lwt would help. Semantics would be along the lines of: when cancelling a promise, Lwt goes out to find the deepest child. Some Lwt.t along the line could be marked as a cancellation barrier, soaking up the cancel, but letting child promises run. The result of such barrier would still be the cancellation, but it wouldn't be 'ready to run' until all children have completed.
• What triggered this bug is that cancel operations sometimes get lost simply because one thread was resolved (e.g. due to a C-call completing), but the bound functions have not run yet. If a new function 'abort' could have semantics where "Returned _" is overwritten with "Canceled" that's equally fine for us.
  I'm not sure if 'cancel' would still have a useful meaning if such a primitive was added or if everybody wouldn't just start converting to abort at such time.

Perhaps both problems can be fixed by making cancellation an out-of-band property of a promise (i.e. returned and canceled can co-exist, with one overriding the other). This allows for more states and differentiated handling. It does increase complexity, however.

[aantron]

@stijn-devriendt The first point sounds a lot like the current Lwt.protected. Is that a correct identification?

[stijn-devriendt]

I think the difference is that when Lwt.protected x is canceled, it does not wait for x to complete, prior to returning. Think of something like a remote procedure call over a socket being executed: returning the socket to a pool shouldn't be done untill the call has completed, even when the call is canceled/no longer necessary. Otherwise the next user of the socket will find it in an inconsistent state.

[aantron]

Thanks for clarifying that. Can I ask your point of view on why cancelation is necessary at all? I do think it's useful, and I use it, but I'd like to discuss more opinions and experience with it :)

The alternative to cancelation built into the API, is explicit management of cancelation points, and that kind of stuff. I imagine that would be painful, but it should give the ability to get exact control in all situations, to the extent the underlying system APIs allow it.

[stijn-devriendt]

I'd say we have 3 main use-cases:

• when a client unexpectedly aborts a transaction, we want to cancel all processing
• canceling as a timeout for remote procedure calls
• client operations typically fan out to multiple concurrent operations. In many cases it's not a hard requirement for all those parallel operations to succeed (or succeed within a timeout). At that point we can safely cancel the remainder of the operations.

So, from this, I'd say there's definitely a use-case for the ability to stop operations. If it weren't available, we'd probably be passing something that boils down to mutable booleans down the stack with the downside of not being able to cancel I/O.
Perhaps an alternative to look at is .NET's thread interrupt behavior. It's somewhat similar in that it's most useful to cancel during blocking operations, but it differs in its capability to interrupt during CPU-only processing.

[aantron]

I'm closing this issue. Thanks for all the discussion.

• All variants of cancel I know of, including the Lwt one, complicate programming. Users rarely understand what cancel really does. Library authors have to put in effort to make sure cancel semantics are preserved for users across library function calls. Readers and contributors are burdened with understanding cancel semantics, if a call to cancel appears in the code.
• cancel doesn't do what its name seems to suggest. It doesn't cancel ongoing operations. It has unexpected effects in case of non-trivial dependencies between promises, and it has various corner cases.
• cancel breaks the nice property that an initial promise can only be resolved through its resolver. It's the only mechanism by which information flows "backwards" along promise dependencies.
• Based on the above, I think we should not try to fix cancel, but discourage using it, and leave it alone. For now, I think it's better to ask people to do cancelation explicitly.
• If we find a good model for cancelation later, we can look into it at that time.

• I added a note to Lwt.cancel to discourage its use:

  It is recommended to avoid Lwt.cancel, and handle cancelation by tracking
  the needed extra state explicitly within your library or application.

• Soon after we last discussed this issue, I added documentation for cancel's current semantics:

  https://github.com/ocsigen/lwt/blob/e4f70d66aa4a5f965bdaff78b43e0dd1c44ab821/src/core/lwt.mli#L1033-L1115

• There is also internal documentation of how it works:

  https://github.com/ocsigen/lwt/blob/e4f70d66aa4a5f965bdaff78b43e0dd1c44ab821/src/core/lwt.ml#L213-L250