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

[Dave Taht]

On Thu, Apr 4, 2019 at 10:31 AM Toke Høiland-Jørgensen <toke at redhat.com> wrote:
>
> Yibo Zhao <yiboz at codeaurora.org> writes:
>
> > On 2019-02-16 01:05, Toke Høiland-Jørgensen wrote:
> >> 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.
> >>
> >> @@ -1831,18 +1830,32 @@ void ieee80211_sta_register_airtime(struct
> >> ieee80211_sta *pubsta, u8 tid,
> >>  {
> >>      struct sta_info *sta = container_of(pubsta, struct sta_info, sta);
> >>      struct ieee80211_local *local = sta->sdata->local;
> >> +    struct ieee80211_txq *txq = sta->sta.txq[tid];
> >>      u8 ac = ieee80211_ac_from_tid(tid);
> >> -    u32 airtime = 0;
> >> +    u64 airtime = 0, weight_sum;
> >> +
> >> +    if (!txq)
> >> +            return;
> >>
> >>      if (sta->local->airtime_flags & AIRTIME_USE_TX)
> >>              airtime += tx_airtime;
> >>      if (sta->local->airtime_flags & AIRTIME_USE_RX)
> >>              airtime += rx_airtime;
> >>
> >> +    /* Weights scale so the unit weight is 256 */
> >> +    airtime <<= 8;
> >> +
> >>      spin_lock_bh(&local->active_txq_lock[ac]);
> >> +
> >>      sta->airtime[ac].tx_airtime += tx_airtime;
> >>      sta->airtime[ac].rx_airtime += rx_airtime;
> >> -    sta->airtime[ac].deficit -= airtime;
> >> +
> >> +    weight_sum = local->airtime_weight_sum[ac] ?: sta->airtime_weight;
> >> +
> >> +    local->airtime_v_t[ac] += airtime / weight_sum;
> > Hi Toke,
> >
> > Please ignore the previous two broken emails regarding this new proposal
> > from me.
> >
> > It looks like local->airtime_v_t acts like a Tx criteria. Only the
> > stations with less airtime than that are valid for Tx. That means there
> > are situations, like 50 clients, that some of the stations can be used
> > to Tx when putting next_txq in the loop. Am I right?
>
> I'm not sure what you mean here. Are you referring to the case where new
> stations appear with a very low (zero) airtime_v_t? That is handled when
> the station is enqueued.
>
> >> +    sta->airtime[ac].v_t += airtime / sta->airtime_weight;
> > Another question. Any plan for taking v_t overflow situation into
> > consideration? u64 might be enough for low throughput products but not
> > sure for high end products. Something like below for reference:
>
> The unit for the variable is time, not bytes, so it is unaffected by
> throughput. 2**64 microseconds is 584554 *years* according to my
> 'units' binary, so don't think we have to worry too much about this
> overflowing ;)

I tend to think more in terms in ns than us. Is this metric in us currently?

I figure having stuff that at least works correctly within the solar
system is a good start, and getting coverage to 250 light years
is sufficiently forward looking: http://www.atlasoftheuniverse.com/250lys.html

>
> -Toke
> _______________________________________________
> Make-wifi-fast mailing list
> Make-wifi-fast at lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/make-wifi-fast



-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740