[Make-wifi-fast] [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler

[Toke Høiland-Jørgensen]

Rajkumar Manoharan <rmanohar at codeaurora.org> writes:

> On 2019-03-05 07:45, Toke Høiland-Jørgensen wrote:
>> Toke Høiland-Jørgensen <toke at 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. However, hopefully this number rarely grows too big 
>>> (it's
>>> only TXQs currently backlogged, not all associated stations), so it
>>> shouldn't be too big of an issue.
>>> 
>>> Signed-off-by: Toke Høiland-Jørgensen <toke at redhat.com>
>>> ---
>>> This is basically the idea I mentioned earlier for a different way to
>>> handle the airtime scheduling.
>>> 
>>> I've tested it on ath9k, where it achieves the same fairness and
>>> weighing properties as the old scheduler. It would be good if you 
>>> could
>>> test it on your ath10k setup, Rajkumar; and all of you please comment 
>>> on
>>> whether you agree that this is better from an API point of view.
>> 
>> So no one has any comments on this? :)
>> 
> Toke,
>
> This is kind of design change. ;)

Yup, that was kinda the point ;)

> FMU w.r.t ath10k, earlier deficit adjustment and list rotation happens
> at next_txq and may_transmit. Now it seems the rbtree adjustment
> happens upon new txq insertion through wake_txq and whenever driver
> reports airtime by register_airtime. Am I right?

Yes. This change was, in part, motivated by the discussions we had
around your patches to ath10k, and the need to make the round-robin
schedulers sync up. I consider that a bit of a hack which this approach
avoids.

> We are using pretty old kernel (3.14, 4.4). It definitely needs backport 
> of rbtree.

Well I wasn't necessarily planning for this to be backported. It doesn't
change the driver API, and *in theory the aggregate fairness behaviour
should be the same between the two scheduling approaches (famous last
words). Verifying that this is actually the case is why I'm asking for
testing.

Also, isn't rbtree pretty old? A git blame on rbtree.c suggests it goes
all the way back to the 2.6 era...

> Have you used *Wrt image or validation on x86?

I have only tested this on x86 with a mac80211-next-based kernel...

-Toke