Toke Høiland-Jørgensen <toke@xxxxxxxxxx> 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@xxxxxxxxxxxxxx> > Signed-off-by: Yibo Zhao <yiboz@xxxxxxxxxxxxxx> > Signed-off-by: Toke Høiland-Jørgensen <toke@xxxxxxxxxx> Hey Felix Had a chance to look at this yet? :) -Toke
