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

["Toke Høiland-Jørgensen" <toke@redhat.com>]

Toke Høiland-Jørgensen <toke@redhat.com> 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 <yiboz@codeaurora.org>
> Signed-off-by: Yibo Zhao <yiboz@codeaurora.org>
> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>

Hey Felix

Had a chance to look at this yet? :)

-Toke