From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-f68.google.com (mail-ed1-f68.google.com [209.85.208.68]) (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 9C83C3B29E for ; Fri, 8 Mar 2019 06:05:07 -0500 (EST) Received: by mail-ed1-f68.google.com with SMTP id x7so16057524eds.8 for ; Fri, 08 Mar 2019 03:05: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=ABca4EoLzrJgYdMirNp2lP/sA/gVHBZHoR9KRUIIm0s=; b=K1s/C2+GKQqk5O+u/qo5LWjyPPhJmSo43mxio6/8w0zpkjpR27dxLzeM9Gv4D0D8i4 qSUpcadUT77wP7JR4IyGJTxoNHGOeJn/Zhg0eW3cPsZ4meDb/aZRHRxqoVj8Aq1YxHEO 94tcJUp0EEWgqyUMF2TOaD8eRCW13V5uVuRik6mmjYVeVTC0kh/KpRz1APGU1NKpgzYf PZNqoPt0JUFUAS3gY5Y2IgKHbo0pak1pKORkza61hgivTYNmcS3wGukaksxHnID6s0CS ew5nyjLQJfJGXIE9vkOPeCT+EANyZy1mCG1431GRFNIQiXZI/CcKO7oA6+NGcxBhkcIw xbcg== X-Gm-Message-State: APjAAAVo75tGp3X+3wlqIUfSV/9QKjaPCAPnSZqPxctiYrkNYFoeC9s6 qXClDnXBQ0hQYz2yNcMWJb0YwA== X-Google-Smtp-Source: APXvYqwOROezSumd74yZbKtbF4LypI4LK7W7T6hNaCbaWo6Oz57AmLkyEUlyiwASipEtSKQLD5MiCw== X-Received: by 2002:a17:906:5583:: with SMTP id y3mr11392084ejp.42.1552043106570; Fri, 08 Mar 2019 03:05:06 -0800 (PST) Received: from alrua-x1.borgediget.toke.dk (borgediget.toke.dk. [85.204.121.218]) by smtp.gmail.com with ESMTPSA id c20sm1356251ejm.58.2019.03.08.03.05.05 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 08 Mar 2019 03:05:05 -0800 (PST) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id 2AFEB180454; Fri, 8 Mar 2019 12:05:05 +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> X-Clacks-Overhead: GNU Terry Pratchett Date: Fri, 08 Mar 2019 12:05:05 +0100 Message-ID: <874l8d7hjy.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 11:05:07 -0000 Felix Fietkau writes: > 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-ba= sed >> 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 with >> the round-robin airtime scheduler. >>=20 >> - 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. >>=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 n= eed >> 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. >>=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: 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 =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 ieee8= 0211_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? 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... >> --- a/net/mac80211/tx.c >> +++ b/net/mac80211/tx.c >> -void ieee80211_return_txq(struct ieee80211_hw *hw, >> +static void __ieee80211_insert_txq(struct rb_root_cached *root, >> + struct txq_info *txqi, u8 ac) >> +{ >> + struct rb_node **new =3D &root->rb_root.rb_node; >> + struct rb_node *parent =3D NULL; >> + struct txq_info *__txqi; >> + bool leftmost =3D true; >> + >> + while (*new) { >> + parent =3D *new; >> + __txqi =3D rb_entry(parent, struct txq_info, schedule_order); >> + >> + if (!txqi->txq.sta) { >> + /* new txqi has no sta - insert to the left */ >> + new =3D &parent->rb_left; >> + } else if (!__txqi->txq.sta) { >> + /* existing txqi has no sta - insert to the right */ >> + new =3D &parent->rb_right; >> + leftmost =3D false; >> + } else { >> + struct sta_info *old_sta =3D container_of(__txqi->txq.sta, >> + struct sta_info, >> + sta); >> + struct sta_info *new_sta =3D container_of(txqi->txq.sta, >> + struct sta_info, >> + sta); >> + >> + if (new_sta->airtime[ac].v_t <=3D old_sta->airtime[ac].v_t) >> + new =3D &parent->rb_left; >> + else { >> + new =3D &parent->rb_right; >> + leftmost =3D false; >> + } >> + >> + } >> + } >> + >> + rb_link_node(&txqi->schedule_order, parent, new); >> + rb_insert_color_cached(&txqi->schedule_order, root, leftmost); >> +} > 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? -Toke