From:   Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= <toke@redhat.com>
To:     Dave Taht <dave.taht@gmail.com>
Cc:     Yibo Zhao <yiboz@codeaurora.org>, Kan Yan <kyan@google.com>,
        Rajkumar Manoharan <rmanohar@codeaurora.org>,
        linux-wireless-owner@vger.kernel.org,
        Make-Wifi-fast <make-wifi-fast@lists.bufferbloat.net>,
        linux-wireless <linux-wireless@vger.kernel.org>,
        Felix Fietkau <nbd@nbd.name>
Subject: Re: [Make-wifi-fast] [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler
In-Reply-To: <CAA93jw5WA8eOUvw9PGJE11Dq1-cYFcYHjWj+jb8bA=zosUgc3Q@mail.gmail.com>
References: <20190215170512.31512-1-toke@redhat.com> <753b328855b85f960ceaf974194a7506@codeaurora.org> <87ftqy41ea.fsf@toke.dk> <CAA93jw5WA8eOUvw9PGJE11Dq1-cYFcYHjWj+jb8bA=zosUgc3Q@mail.gmail.com>
Date:   Thu, 04 Apr 2019 10:50:17 +0200
Message-ID: <87a7h640ja.fsf@toke.dk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8BIT
Sender: linux-wireless-owner@vger.kernel.org
Precedence: bulk

Dave Taht <dave.taht@gmail.com> writes:

> On Thu, Apr 4, 2019 at 10:31 AM Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> Yibo Zhao <yiboz@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?

Yeah, WiFi stuff generally thinks in coarser time scales than you, then;
everything tends to be microseconds here (the actual time unit in the
standard is 1.024 us IIRC).

> 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

Heh, yeah, not sure the WiFi MAC is appropriate for those distances ;)

-Toke