Skip to content

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 Streams. When .awaited, 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.