Tunnel circuits should be polled fairly
In !3235 (comment 3253194), @opara and @nickm pointed out that our use of FuturesUnordered
to drive the circuits in a conflux set is hard to reason about, and that it could lead to starvation (in ConfluxSet::next_circ_action()
, we drop the FuturesUnordered
after extracting the first ready result, so if the future at the head of the list is always ready, the other ones won't be polled, and so they won't have a chance to make any progress). Having looked at the FuturesUnordered
implementation, I convinced myself this is indeed a problem.
To fix this, I propose we replace FuturesUnordered
with a new PollAll
abstraction that implements Future
and wraps a list of dyn Stream
s. When .await
ed, PollAll
will poll each of its underlying streams, and return all the ready results instead of just the first. Under the hood, PollAll
will drive all of its streams in lockstep (by polling them all, even if the first one has already yielded a result). Or possibly, PollAll
could be a wrapper over a list of dyn Future
and not dyn Stream
.
With PollAll
, ConfluxSet::next_circ_action()
will end up roughly like this:
pub(super) async fn next_circ_action<'a>(
&mut self,
runtime: &tor_rtcompat::DynTimeProvider,
) -> Result<Vec<CircuitAction>, crate::Error> { // XXX: this can be a SmallVec or similar
let mut poll_all = PollAll::<CircuitAction>::new();
for leg in &mut self.legs {
// Push all the streams/futures we want to poll in lockstep
poll_all.push(...);
poll_all.push(...);
poll_all.push(...);
}
Ok(poll_all.await)
}
This will of course mean that in the reactor main loop we will need to handle a list of CircuitAction
instead of just one, which can potentially cause it to block until several cells are sent. While is not ideal, I think it is better than the alternative.
Another option would be to keep using FuturesUnordered
: we could shuffle the list of circuit futures before collecting them into FuturesUnordered
, which would solve the starvation issue, but IMO that would be a kludge on top of a kludge.