From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-f66.google.com (mail-ed1-f66.google.com [209.85.208.66]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id E1F573B2A4 for ; Fri, 8 Mar 2019 14:06:07 -0500 (EST) Received: by mail-ed1-f66.google.com with SMTP id g19so17263194edp.2 for ; Fri, 08 Mar 2019 11:06:07 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=8z01g5zwuFq7bgyK/hshJLvTveVcR3huiQ8sO5CsujY=; b=mVQebHjIHBrPazCvSLXnliq9bE7Z/YKTAtru0ShLbawJScFc0rnljdDeniVbj39jUc mJoCLAW/cOiywnOJuiCPa6EsrLZRkVsvImZtjt1BIG6geYM1lZLLYavnEtxjhYoTuucY FeRaW3oo2pTPQzS2KRTQcrmScvRFT7dtthe5kiHWaztY8wQn/NbzZiWbYtSgzQOga/MM 8STLVQH6wIYpBr/VazwLO+H5wL9JIZbQeJpfVhi4jRFhwkOE0tC7DQ6CdAUePtX+RNYb A0W2tvxhK8gCH2u0baPtpJ7eJZAdvaE+Y0aj5pn0QTRLM71zPAGNN6De/LO3QUPWByi7 1xCQ== X-Gm-Message-State: APjAAAVIrlHnNzH3rt3Ds9KDh07r8XnApkptcCFlk1SRij5QFqZW6ZPg 9Gc6EGieDlqwtbUV7H2X++xccw== X-Google-Smtp-Source: APXvYqxkvBNGGEGC7qlOG/rRtPEpntBGHeIBxPhWB+kmyhZhBz8jtJ9noyvdiHizEYwKHag1GfvPTw== X-Received: by 2002:a50:a5f6:: with SMTP id b51mr34220982edc.9.1552071966965; Fri, 08 Mar 2019 11:06:06 -0800 (PST) Received: from alrua-x1.borgediget.toke.dk ([2a00:7660:6da:10::2]) by smtp.gmail.com with ESMTPSA id n19sm1553892eja.38.2019.03.08.11.06.05 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 08 Mar 2019 11:06:06 -0800 (PST) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id 73A6818049E; Fri, 8 Mar 2019 20:06:00 +0100 (CET) From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= To: Felix Fietkau , make-wifi-fast@lists.bufferbloat.net, linux-wireless@vger.kernel.org Cc: Rajkumar Manoharan , Kan Yan In-Reply-To: References: <20190215170512.31512-1-toke@redhat.com> <874l8d7hjy.fsf@toke.dk> X-Clacks-Overhead: GNU Terry Pratchett 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: quoted-printable Subject: Re: [Make-wifi-fast] [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler X-BeenThere: make-wifi-fast@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 08 Mar 2019 19:06:08 -0000 Felix Fietkau writes: > On 2019-03-08 12:05, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >> Felix Fietkau writes: >>=20 >>> On 2019-02-15 18:05, Toke H=C3=B8iland-J=C3=B8rgensen 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: >>>>=20 >>>> - No need to sync up the round-robin scheduler in firmware/hardware wi= th >>>> the round-robin airtime scheduler. >>>>=20 >>>> - If several stations are eligible for transmission we can schedule bo= th of >>>> them; no need to hard-block the scheduling rotation until the head o= f the >>>> queue has used up its quantum. >>>>=20 >>>> - The check of whether a station is eligible for transmission becomes >>>> simpler (in ieee80211_txq_may_transmit()). >>>>=20 >>>> 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 (i= t's >>>> only TXQs currently backlogged, not all associated stations), so it >>>> shouldn't be too big of an issue. >>>>=20 >>>> Signed-off-by: Toke H=C3=B8iland-J=C3=B8rgensen >>> The approach looks good to me, but I haven't really reviewed it very >>> carefully yet. Just some points that I noticed below: >>=20 >> Cool! >>=20 >>>> 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_s= ub_if_data *sdata, >>>> for (i =3D 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 =3D sta->airtime_weight; >>>> } >>>>=20=20 >>>> for (i =3D 0; i < IEEE80211_NUM_TIDS; i++) >>>> @@ -1831,18 +1830,32 @@ void ieee80211_sta_register_airtime(struct iee= e80211_sta *pubsta, u8 tid, >>>> { >>>> struct sta_info *sta =3D container_of(pubsta, struct sta_info, sta); >>>> struct ieee80211_local *local =3D sta->sdata->local; >>>> + struct ieee80211_txq *txq =3D sta->sta.txq[tid]; >>>> u8 ac =3D ieee80211_ac_from_tid(tid); >>>> - u32 airtime =3D 0; >>>> + u64 airtime =3D 0, weight_sum; >>>> + >>>> + if (!txq) >>>> + return; >>>>=20=20 >>>> if (sta->local->airtime_flags & AIRTIME_USE_TX) >>>> airtime +=3D tx_airtime; >>>> if (sta->local->airtime_flags & AIRTIME_USE_RX) >>>> airtime +=3D rx_airtime; >>>>=20=20 >>>> + /* Weights scale so the unit weight is 256 */ >>>> + airtime <<=3D 8; >>>> + >>>> spin_lock_bh(&local->active_txq_lock[ac]); >>>> + >>>> sta->airtime[ac].tx_airtime +=3D tx_airtime; >>>> sta->airtime[ac].rx_airtime +=3D rx_airtime; >>>> - sta->airtime[ac].deficit -=3D airtime; >>>> + >>>> + weight_sum =3D local->airtime_weight_sum[ac] ?: sta->airtime_weight; >>>> + >>>> + local->airtime_v_t[ac] +=3D airtime / weight_sum; >>>> + sta->airtime[ac].v_t +=3D 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? >>=20 >> 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? >>=20 >> 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. >>=20 >> 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