From:   Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= <toke@redhat.com>
To:     Felix Fietkau <nbd@nbd.name>, make-wifi-fast@lists.bufferbloat.net,
        linux-wireless@vger.kernel.org
Cc:     Rajkumar Manoharan <rmanohar@codeaurora.org>,
        Kan Yan <kyan@google.com>
Subject: Re: [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler
In-Reply-To: <a2b4c6c5-7b49-b809-a087-73548954e0bf@nbd.name>
References: <20190215170512.31512-1-toke@redhat.com> <f6c5bc25-a8b3-bac3-8d62-d41347a6c070@nbd.name> <874l8d7hjy.fsf@toke.dk> <a2b4c6c5-7b49-b809-a087-73548954e0bf@nbd.name>
Date:   Fri, 08 Mar 2019 20:06:00 +0100
Message-ID: <87mum55gpz.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

Felix Fietkau <nbd@nbd.name> writes:

> On 2019-03-08 12:05, Toke Høiland-Jørgensen wrote:
>> Felix Fietkau <nbd@nbd.name> writes:
>> 
>>> On 2019-02-15 18: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.
>>>> 
>>>> Signed-off-by: Toke Høiland-Jørgensen <toke@redhat.com>
>>> The approach looks good to me, but I haven't really reviewed it very
>>> carefully yet. Just some points that I noticed below:
>> 
>> Cool!
>> 
>>>> diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
>>>> index 11f058987a54..9d01fdd86e2d 100644
>>>> --- a/net/mac80211/sta_info.c
>>>> +++ b/net/mac80211/sta_info.c
>>>> @@ -389,7 +389,6 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
>>>>  	for (i = 0; i < IEEE80211_NUM_ACS; i++) {
>>>>  		skb_queue_head_init(&sta->ps_tx_buf[i]);
>>>>  		skb_queue_head_init(&sta->tx_filtered[i]);
>>>> -		sta->airtime[i].deficit = sta->airtime_weight;
>>>>  	}
>>>>  
>>>>  	for (i = 0; i < IEEE80211_NUM_TIDS; i++)
>>>> @@ -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;
>>>> +	sta->airtime[ac].v_t += airtime / sta->airtime_weight;
>>>> +	ieee80211_resort_txq(&local->hw, txq);
>>> These divisions could be a bit expensive, any way to change the
>>> calculation to avoid them?
>> 
>> Yeah, given that the denominators are constant from the PoV of the fast
>> path, we can pre-compute reciprocals and turn these divides into
>> multiplications. Will incorporate that...
> Sounds good.
>
>>> I'm a bit worried about this part. Does that mean that vif txqs always
>>> have priority over sta txqs?
>> 
>> Yeah, it does. This sort of mirrors what the existing airtime scheduler
>> does (because VIFs don't have an airtime deficit), but because it's a
>> round-robin scheduler the effect is less severe as long as there are
>> stations able to transmit.
>> 
>> I guess the obvious fix is to start accounting airtime usage for the VIF
>> as well? We may want to do that in any case, as that would also give
>> users a convenient way to set policy for multicast traffic. Any
>> objections to this?
> I think this is a good idea.

Great, thanks! I'll do a separate patch for accounting airtime for the
VIF queue, and then respin this on top. Will probably be a little while
before I get around to it, though.

-Toke