A limited sync queue seems to break an unwritten rule about `std::task::Waker`
- 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
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