[tor-bugs] #29698 [Core Tor/Tor]: Edge case that causes improper circuit prioritization for one scheduling run

[Tor Bug Tracker & Wiki]

#29698: Edge case that causes improper circuit prioritization for one scheduling
run
------------------------------+--------------------------------
     Reporter:  pastly        |      Owner:  (none)
         Type:  defect        |     Status:  new
     Priority:  Medium        |  Milestone:  Tor: 0.3.5.x-final
    Component:  Core Tor/Tor  |    Version:  Tor: 0.3.2.1-alpha
     Severity:  Normal        |   Keywords:  tor-sched tor-cmux
Actual Points:                |  Parent ID:
       Points:                |   Reviewer:
      Sponsor:                |
------------------------------+--------------------------------
 = The Problem, Shortly

 A circuit that goes from very busy for a long time, to 100% idle for a
 long time, and then needs to send traffic again will be incorrectly
 deprioritized the first time it gets scheduled.

 = The Problem, Illustrated

 Consider a circuit that is very very busy for a significant length of time
 (minutes). There's constant traffic flowing in one (or both, but let's
 just say one) direction on this circuit, leading to it earning for itself
 a high `cell_count` EWMA value (thus a low priority for scheduling).
 ''Assume it is the only circuit on its channel''.

 Now assume it suddenly stops sending traffic but stays open. It stays this
 way for significant length of time (many 10s of seconds) such that ''its
 `cell_count` EWMA value should be essentially zero, but it hasn't actually
 been updated yet'' since this value isn't updated until a cell has been
 transmitted (see `circuitmux_notify_xmit_cells`).

 At this point in time the relay is still servicing some number of low-
 traffic circuits ''on other channels''. Maybe it has always been handling
 these circuits. Whatever. It doesn't matter. What matters is at this point
 in time there's lots of low-traffic circuits needing scheduling. Because
 they are low-traffic, these circuits have `cell_count` EWMA values that
 are relatively low (thus a high priority for scheduling).

 Now what happens when that original high-traffic circuit stops being
 totally idle? What happens when it wants to send another 1000, 100, or
 even just 1 cell?

 It gets put into KIST `channels_pending` smart list like any other
 circuit. In fact there are a bunch of low-bandwidth circuits in there with
 it. Observe what happens when KIST starts scheduling its collection of
 pending channels:

 KIST loops over and over until its list of pending channels is empty. Each
 time it gets the channel with the current best-priority circuit, schedules
 one cell, ''updates the appropriate `cell_count`'', and puts the channel
 back in the pending list if necessary.

 '''All those low-traffic circuits will be serviced first because they have
 low `cell_count` values (high priority) as compared to the outdated
 `cell_count` value for the original high-traffic circuit.'''

 When the circuit finally gets to send its first cell after its long period
 of inactivity, its `cell_count` EWMA value is corrected to be near zero.
 That's fine. ''But it should have been updated before scheduling decisions
 were made so that it was the first one to be scheduled''.

 = A solution

 Add a `touch` function in the circuitmux channel interface that tells the
 circuitmux and whatever its policy is to update its circuit priorities if
 desired.

 Before entering the main scheduling loop, call this `touch` function on
 all the pending channels. In the case of the EWMA policy, the `touch`
 function would ultimately drill down to something like

 {{{
 ewma_touch(circuitmux_policy_data_t *pol_data)
 {
   ewma_policy_data_t *pol = NULL;
   unsigned int tick;
   double fractional_tick;
   tor_assert(pol_data);
   pol = TO_EWMA_POL_DATA(pol_data);

   /* Rescale the EWMAs if needed */
   tick = cell_ewma_get_current_tick_and_fraction(&fractional_tick);

   if (tick != pol->active_circuit_pqueue_last_recalibrated) {
     scale_active_circuits(pol, tick);
   }
 }
 }}}

 (Which you might observe is essentially the first part of
 `ewma_notify_xmit_cells(...)`).

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/29698>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online