Re: [PATCH mac80211-next v8] mac80211: Switch to a virtual time-based airtime scheduler

Toke Høiland-Jørgensen [off-list ref] writes:

This switches the airtime scheduler in mac80211 to use a virtual time-based
scheduler instead of the round-robin scheduler used before. This has a
couple of advantages:

- No need to sync up the round-robin scheduler in firmware/hardware with
  the round-robin airtime scheduler.

- If several stations are eligible for transmission we can schedule both of
  them; no need to hard-block the scheduling rotation until the head of the
  queue has used up its quantum.

- The check of whether a station is eligible for transmission becomes
  simpler (in ieee80211_txq_may_transmit()).

The drawback is that scheduling becomes slightly more expensive, as we need
to maintain an rbtree of TXQs sorted by virtual time. This means that
ieee80211_register_airtime() becomes O(logN) in the number of currently
scheduled TXQs because it can change the order of the scheduled stations.
We mitigate this overhead by only resorting when a station changes position
in the tree, and hopefully N rarely grows too big (it's only TXQs currently
backlogged, not all associated stations), so it shouldn't be too big of an
issue.

To prevent divisions in the fast path, we maintain both station sums and
pre-computed reciprocals of the sums. This turns the fast-path operation
into a multiplication, with divisions only happening as the number of
active stations change (to re-compute the current sum of all active station
weights). To prevent this re-computation of the reciprocal from happening
too frequently, we use a time-based notion of station activity, instead of
updating the weight every time a station gets scheduled or de-scheduled. As
queues can oscillate between empty and occupied quite frequently, this can
significantly cut down on the number of re-computations. It also has the
added benefit of making the station airtime calculation independent on
whether the queue happened to have drained at the time an airtime value was
accounted.

Co-developed-by: Yibo Zhao <redacted>
Signed-off-by: Yibo Zhao <redacted>
Signed-off-by: Toke Høiland-Jørgensen <redacted>

Hey Felix

Had a chance to look at this yet? :)

-Toke