compio-rs / compio-rs/compio

A limited sync queue seems to break an unwritten rule about `std::task::Waker`

Open
#1,044 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
1.9k
Forks
133
Avg merge
1d 4h
Merged PRs (30d)
20

Description

I ran into this issue when trying to port rqbit to compio. It uses a tree of `tokio_util::sync::CancellationToken` through every task it spawns, and when handling a `SIGINT` on a different thread, it cancels the token from that thread.

The number of tasks it spawns can grow arbitrarily large, and when I tried to `SIGINT` the process with a single torrent running, there was already more than 64 cross-thread `Waker::wake()` calls by the cancellation of the root token (the default `sync_queue_size`), which made the calling thread spin, waiting for free slots. Worse, it spins holding the mutex for the `CancellationToken` tree.

Then the executor runs, empties the queue, runs tasks, and in rqbit bit case, it happens to poll a cancellation token while the cancelling thread is holding the `CancellationToken` mutex, who blocks the executor thread on the same mutex. Then the queue fills, and the cancelling thread spins waiting for room in the queue, deadlocking.

It seems that `tokio_util` relies on the unwritten expectation that `std::task::Waker::wake()` will not block, and it seems to be upheld by all the major async runtimes. This paragraph on the [`Waker` documentation](https://doc.rust-lang.org/beta/std/task/struct.Waker.html) is the one I found the closest to justify this expectation:

> Implements [Clone](https://doc.rust-lang.org/beta/std/clone/trait.Clone.html), [Send](https://doc.rust-lang.org/beta/std/marker/trait.Send.html), and [Sync](https://doc.rust-lang.org/beta/std/marker/trait.Sync.html); therefore, a waker may be invoked from any thread, including ones not in any way managed by the executor. For example, this might be done to wake a future when a blocking function call completes on another thread.

The reasoning goes that the `Waker` should not block a thread the runtime knows nothing about, (particularly, what locks it might be holding), precisely because of the risk of deadlock.

I think compio should uphold this expectation too. The easiest fix is simply to replace

```
sync: ArrayQueue,
```

with

```
sync: SegQueue,
```

We lose allocation free, but is still pretty good, as it only allocates every 32 pushes.

AI wrote this minimal reproduction: https://github.com/lvella/compio-cancel-deadlock

Contributor guide

Open the contributing guide

Research direction

Search the executor code for the `sync: ArrayQueue` field and trace how cross-thread `Waker::wake()` calls enqueue tasks while cancellation holds the token-tree mutex. Review the linked minimal reproduction and compare the queue behavior with `SegQueue`. Done means cancellation no longer deadlocks when the sync queue reaches its default capacity.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.