From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-io1-xd33.google.com (mail-io1-xd33.google.com [IPv6:2607:f8b0:4864:20::d33]) (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 A631F3B29E for ; Wed, 23 Jun 2021 10:28:03 -0400 (EDT) Received: by mail-io1-xd33.google.com with SMTP id d9so3683813ioo.2 for ; Wed, 23 Jun 2021 07:28:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=6qbKIyjueoKPMpQqddHZI+HY7bkhCzfrkHCIBBqFOL4=; b=dsrLFfEQYbTDhXwlAlguseQfelC4S8aXf64K3H2NqcJ+0FGOgs1IoFkthMmaLfR/92 Nxvi8mLf6ULMqtkQqKJcMX6WUKzmlRVpKQXrTTxjJ2B1uTh8MUmAaxKGL7OnA6MFi5Uj Fez8tbknIYoq75XH1ZUhaC5K3ZG4eNV8wTuHly2YMJzOkevxraBtfk/QfSHhqxbr6Txg 0EiGYdqMNC7RmwywPa8BsPNt6AWIStcYY2THW6hsNA6D7e+VSWwtxfuNUHaeCk+0VR2P SuFIlWIz/SKlN0MeFWTbMF1+YrwBswS0xSs8IqYNF0qz8XEO44cbyu8oKNDol+e7ewJm nC+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=6qbKIyjueoKPMpQqddHZI+HY7bkhCzfrkHCIBBqFOL4=; b=KszWA134f2Cy/AYlfe/MtsFHbHqFK1Zjiy951j99WNAJBtSnowQMsGbiIstGBRAtUO d3rRoSkt9xXdC8qPtIWdFpIuWCvFdm+86yXNXciD3S4Ihd0WJyipv42Qk10rNCy6t1+n LV2iIaUV4Ob9WncMH1kNK6oe737jlD6ZM4UPqV2695Wap0IvHTXlI8QCVgm4rOeCYX2n kyFqmbna1SJ+ETTdDfzcnd3us5UoqzQrPOKpBM+WN4Hfq9E/7jQYDj+HX+LjXHRqNRd5 T5RuJJy9+rKwktZC+FGVQiq8c2V7PlpbyhNlLpvN9D63JvsQ3hIZ5joT4WzFGopk6kyO B7tA== X-Gm-Message-State: AOAM531ecRe4sEUSPmuuNQ50qIjCM1fxEcPA2ec/RztjVYYm+BDpFfy+ ZmYFIipANQsSce4HV0+qpWpBWYDy5Y1S13N20XE= X-Google-Smtp-Source: ABdhPJwgbzDH8Enh/ktG6T/FSTD3fpVlLC6YhSUWLyaxtfKeZEXgJ1V81pSGgMz8SG9Wg3Jl+3a2uO8bUEVIaw7VYYs= X-Received: by 2002:a5d:9c59:: with SMTP id 25mr7359974iof.27.1624458482436; Wed, 23 Jun 2021 07:28:02 -0700 (PDT) MIME-Version: 1.0 References: <20210623134755.235545-1-toke@redhat.com> In-Reply-To: <20210623134755.235545-1-toke@redhat.com> From: Dave Taht Date: Wed, 23 Jun 2021 07:27:51 -0700 Message-ID: To: =?UTF-8?B?VG9rZSBIw7hpbGFuZC1Kw7hyZ2Vuc2Vu?= Cc: Kan Yan , Make-Wifi-fast , Felix Fietkau Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: Re: [Make-wifi-fast] [PATCH mac80211-next v9] 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: Wed, 23 Jun 2021 14:28:03 -0000 did this make it into openwrt rcX ? On Wed, Jun 23, 2021 at 6:48 AM 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: > > - 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 because it can change the order of the > scheduled stations. We mitigate this overhead by only resorting when a > station changes position in the tree, and hopefully N rarely grows too > big (it's only TXQs currently backlogged, not all associated stations), > so it shouldn't be too big of an issue. > > To prevent divisions in the fast path, we maintain both station sums and > pre-computed reciprocals of the sums. This turns the fast-path operation > into a multiplication, with divisions only happening as the number of > active stations change (to re-compute the current sum of all active > station weights). To prevent this re-computation of the reciprocal from > happening too frequently, we use a time-based notion of station > activity, instead of updating the weight every time a station gets > scheduled or de-scheduled. As queues can oscillate between empty and > occupied quite frequently, this can significantly cut down on the number > of re-computations. It also has the added benefit of making the station > airtime calculation independent on whether the queue happened to have > drained at the time an airtime value was accounted. > > Co-developed-by: Yibo Zhao > Signed-off-by: Yibo Zhao > Signed-off-by: Toke H=C3=B8iland-J=C3=B8rgensen > --- > Changelog: > v9: > Rebase to newest mac80211-next. > > Reflow commit message to 72 chars and remove some long lines in the cod= e. > > Refactor the sta parameter parsing to a separate sta_apply_airtime_para= ms() > > v8: > Fix locking issue pointed out by kbot > > v7: > Rebase on latest mac80211-next, fix a kbot compile warning. > > Add back a hard limit on how far a station call fall behind in addition= to > the activity-based catchup, to avoid the case where a station manages t= o get > a single packet scheduled every 100ms and thus stays "active" indefinit= ely. > > v6: > Rebase on latest mac80211-next. > > Fix issue with scheduling hanging because the schedule position was not > cleared when starting a new scheduling round. > > Switch the reciprocal calculation to use u32 (split 19/13) for per-stat= ion > weights and a u64 only for the weight sum (to cut down on the number of= 64-bit > operations performed) > > Introduce the notion of time-based station activity when calculating we= ight > sums. This also gets rid of the need for a "grace time" when catching u= p > stations, since we now have a direct notion of when a station has been > inactive for a while. > > Add a debugfs file for the netdev so users can inspect the airtime usag= e of > the vif TXQ. > > v5: > Rebase on latest mac80211-next. > > Squash everything into a single patch again, and add back Yibo's > co-developed-by tag and signoff. > > Move all the per-ac airtime-related data into separate structs. > > Use pre-calculated reciprocals to avoid divisions in the fast path. > > Record airtime usage for the vif TXQ to avoid it always being > scheduled first. > > v4: > Change schedule_pos to previous node once it has chance to be moved/rem= oved > from current position in the tree in loop scenario and bring back sched= ule_round > in case that same node is to be scheduled again in the mean time. > > Increase airtime grace period to 2000 us in the first patch. > > Put per-AC station weight checking in its lock during configuration fro= m application. > > v3: > Changes station airtime weight to be per-AC based to avoid sync issue > Remove Co-developed-by and Toke's sign-off as Toke suggested > > v2: > Modify the author of Co-developed-by as Johannes suggested > > include/net/mac80211.h | 17 +- > net/mac80211/cfg.c | 35 +++- > net/mac80211/debugfs.c | 70 +++++-- > net/mac80211/debugfs_netdev.c | 32 ++- > net/mac80211/debugfs_sta.c | 24 +-- > net/mac80211/ieee80211_i.h | 182 +++++++++++++++-- > net/mac80211/iface.c | 3 + > net/mac80211/main.c | 11 +- > net/mac80211/rx.c | 6 +- > net/mac80211/sta_info.c | 67 +++++-- > net/mac80211/sta_info.h | 11 +- > net/mac80211/status.c | 19 ++ > net/mac80211/tx.c | 366 ++++++++++++++++++++++++---------- > 13 files changed, 653 insertions(+), 190 deletions(-) > > diff --git a/include/net/mac80211.h b/include/net/mac80211.h > index 9afbcac61c2a..d8a1d09a2141 100644 > --- a/include/net/mac80211.h > +++ b/include/net/mac80211.h > @@ -6605,9 +6605,6 @@ static inline void ieee80211_txq_schedule_end(struc= t ieee80211_hw *hw, u8 ac) > { > } > > -void __ieee80211_schedule_txq(struct ieee80211_hw *hw, > - struct ieee80211_txq *txq, bool force); > - > /** > * ieee80211_schedule_txq - schedule a TXQ for transmission > * > @@ -6620,11 +6617,7 @@ void __ieee80211_schedule_txq(struct ieee80211_hw = *hw, > * The driver may call this function if it has buffered packets for > * this TXQ internally. > */ > -static inline void > -ieee80211_schedule_txq(struct ieee80211_hw *hw, struct ieee80211_txq *tx= q) > -{ > - __ieee80211_schedule_txq(hw, txq, true); > -} > +void ieee80211_schedule_txq(struct ieee80211_hw *hw, struct ieee80211_tx= q *txq); > > /** > * ieee80211_return_txq - return a TXQ previously acquired by ieee80211_= next_txq() > @@ -6636,12 +6629,8 @@ ieee80211_schedule_txq(struct ieee80211_hw *hw, st= ruct ieee80211_txq *txq) > * The driver may set force=3Dtrue if it has buffered packets for this T= XQ > * internally. > */ > -static inline void > -ieee80211_return_txq(struct ieee80211_hw *hw, struct ieee80211_txq *txq, > - bool force) > -{ > - __ieee80211_schedule_txq(hw, txq, force); > -} > +void ieee80211_return_txq(struct ieee80211_hw *hw, struct ieee80211_txq = *txq, > + bool force); > > /** > * ieee80211_txq_may_transmit - check whether TXQ is allowed to transmit > diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c > index 0d29a9d1f910..84cc7733ea66 100644 > --- a/net/mac80211/cfg.c > +++ b/net/mac80211/cfg.c > @@ -1442,6 +1442,38 @@ static void sta_apply_mesh_params(struct ieee80211= _local *local, > #endif > } > > +static void sta_apply_airtime_params(struct ieee80211_local *local, > + struct sta_info *sta, > + struct station_parameters *params) > +{ > + u8 ac; > + > + for (ac =3D 0; ac < IEEE80211_NUM_ACS; ac++) { > + struct airtime_sched_info *air_sched =3D &local->airtime[= ac]; > + struct airtime_info *air_info =3D &sta->airtime[ac]; > + struct txq_info *txqi; > + u8 tid; > + > + spin_lock_bh(&air_sched->lock); > + for (tid =3D 0; tid < IEEE80211_NUM_TIDS + 1; tid++) { > + if (air_info->weight =3D=3D params->airtime_weigh= t || > + !sta->sta.txq[tid] || > + ac !=3D ieee80211_ac_from_tid(tid)) > + continue; > + > + airtime_weight_set(air_info, params->airtime_weig= ht); > + > + txqi =3D to_txq_info(sta->sta.txq[tid]); > + if (RB_EMPTY_NODE(&txqi->schedule_order)) > + continue; > + > + ieee80211_update_airtime_weight(local, air_sched, > + 0, true); > + } > + spin_unlock_bh(&air_sched->lock); > + } > +} > + > static int sta_apply_parameters(struct ieee80211_local *local, > struct sta_info *sta, > struct station_parameters *params) > @@ -1629,7 +1661,8 @@ static int sta_apply_parameters(struct ieee80211_lo= cal *local, > sta_apply_mesh_params(local, sta, params); > > if (params->airtime_weight) > - sta->airtime_weight =3D params->airtime_weight; > + sta_apply_airtime_params(local, sta, params); > + > > /* set the STA state after all sta info from usermode has been se= t */ > if (test_sta_flag(sta, WLAN_STA_TDLS_PEER) || > diff --git a/net/mac80211/debugfs.c b/net/mac80211/debugfs.c > index fc34ae2b604c..8dbfe325ee66 100644 > --- a/net/mac80211/debugfs.c > +++ b/net/mac80211/debugfs.c > @@ -216,14 +216,14 @@ static ssize_t aql_txq_limit_read(struct file *file= , > "VI %u %u\n" > "BE %u %u\n" > "BK %u %u\n", > - local->aql_txq_limit_low[IEEE80211_AC_VO], > - local->aql_txq_limit_high[IEEE80211_AC_VO], > - local->aql_txq_limit_low[IEEE80211_AC_VI], > - local->aql_txq_limit_high[IEEE80211_AC_VI], > - local->aql_txq_limit_low[IEEE80211_AC_BE], > - local->aql_txq_limit_high[IEEE80211_AC_BE], > - local->aql_txq_limit_low[IEEE80211_AC_BK], > - local->aql_txq_limit_high[IEEE80211_AC_BK]); > + local->airtime[IEEE80211_AC_VO].aql_txq_limit_low= , > + local->airtime[IEEE80211_AC_VO].aql_txq_limit_hig= h, > + local->airtime[IEEE80211_AC_VI].aql_txq_limit_low= , > + local->airtime[IEEE80211_AC_VI].aql_txq_limit_hig= h, > + local->airtime[IEEE80211_AC_BE].aql_txq_limit_low= , > + local->airtime[IEEE80211_AC_BE].aql_txq_limit_hig= h, > + local->airtime[IEEE80211_AC_BK].aql_txq_limit_low= , > + local->airtime[IEEE80211_AC_BK].aql_txq_limit_hig= h); > return simple_read_from_buffer(user_buf, count, ppos, > buf, len); > } > @@ -255,11 +255,11 @@ static ssize_t aql_txq_limit_write(struct file *fil= e, > if (ac >=3D IEEE80211_NUM_ACS) > return -EINVAL; > > - q_limit_low_old =3D local->aql_txq_limit_low[ac]; > - q_limit_high_old =3D local->aql_txq_limit_high[ac]; > + q_limit_low_old =3D local->airtime[ac].aql_txq_limit_low; > + q_limit_high_old =3D local->airtime[ac].aql_txq_limit_high; > > - local->aql_txq_limit_low[ac] =3D q_limit_low; > - local->aql_txq_limit_high[ac] =3D q_limit_high; > + local->airtime[ac].aql_txq_limit_low =3D q_limit_low; > + local->airtime[ac].aql_txq_limit_high =3D q_limit_high; > > mutex_lock(&local->sta_mtx); > list_for_each_entry(sta, &local->sta_list, list) { > @@ -382,6 +382,46 @@ static const struct file_operations force_tx_status_= ops =3D { > .llseek =3D default_llseek, > }; > > +static ssize_t airtime_read(struct file *file, > + char __user *user_buf, > + size_t count, > + loff_t *ppos) > +{ > + struct ieee80211_local *local =3D file->private_data; > + char buf[200]; > + u64 v_t[IEEE80211_NUM_ACS]; > + u64 wt[IEEE80211_NUM_ACS]; > + int len =3D 0, ac; > + > + for (ac =3D 0; ac < IEEE80211_NUM_ACS; ac++) { > + spin_lock_bh(&local->airtime[ac].lock); > + v_t[ac] =3D local->airtime[ac].v_t; > + wt[ac] =3D local->airtime[ac].weight_sum; > + spin_unlock_bh(&local->airtime[ac].lock); > + } > + len =3D scnprintf(buf, sizeof(buf), > + "\tVO VI BE BK\n" > + "Virt-t\t%-10llu %-10llu %-10llu %-10llu\n" > + "Weight\t%-10llu %-10llu %-10llu %-10llu\n", > + v_t[0], > + v_t[1], > + v_t[2], > + v_t[3], > + wt[0], > + wt[1], > + wt[2], > + wt[3]); > + > + return simple_read_from_buffer(user_buf, count, ppos, > + buf, len); > +} > + > +static const struct file_operations airtime_ops =3D { > + .read =3D airtime_read, > + .open =3D simple_open, > + .llseek =3D default_llseek, > +}; > + > #ifdef CONFIG_PM > static ssize_t reset_write(struct file *file, const char __user *user_bu= f, > size_t count, loff_t *ppos) > @@ -632,7 +672,11 @@ void debugfs_hw_add(struct ieee80211_local *local) > if (local->ops->wake_tx_queue) > DEBUGFS_ADD_MODE(aqm, 0600); > > - DEBUGFS_ADD_MODE(airtime_flags, 0600); > + if (wiphy_ext_feature_isset(local->hw.wiphy, > + NL80211_EXT_FEATURE_AIRTIME_FAIRNESS)= ) { > + DEBUGFS_ADD_MODE(airtime, 0600); > + DEBUGFS_ADD_MODE(airtime_flags, 0600); > + } > > DEBUGFS_ADD(aql_txq_limit); > debugfs_create_u32("aql_threshold", 0600, > diff --git a/net/mac80211/debugfs_netdev.c b/net/mac80211/debugfs_netdev.= c > index f7aac8955681..db724fc10a5f 100644 > --- a/net/mac80211/debugfs_netdev.c > +++ b/net/mac80211/debugfs_netdev.c > @@ -512,6 +512,34 @@ static ssize_t ieee80211_if_fmt_aqm( > } > IEEE80211_IF_FILE_R(aqm); > > +static ssize_t ieee80211_if_fmt_airtime( > + const struct ieee80211_sub_if_data *sdata, char *buf, int buflen) > +{ > + struct ieee80211_local *local =3D sdata->local; > + struct ieee80211_txq *txq =3D sdata->vif.txq; > + struct airtime_info *air_info; > + int len; > + > + if (!txq) > + return 0; > + > + spin_lock_bh(&local->airtime[txq->ac].lock); > + air_info =3D to_airtime_info(txq); > + len =3D scnprintf(buf, > + buflen, > + "RX: %llu us\nTX: %llu us\nWeight: %u\n" > + "Virt-T: %lld us\n", > + air_info->rx_airtime, > + air_info->tx_airtime, > + air_info->weight, > + air_info->v_t); > + spin_unlock_bh(&local->airtime[txq->ac].lock); > + > + return len; > +} > + > +IEEE80211_IF_FILE_R(airtime); > + > IEEE80211_IF_FILE(multicast_to_unicast, u.ap.multicast_to_unicast, HEX); > > /* IBSS attributes */ > @@ -657,8 +685,10 @@ static void add_common_files(struct ieee80211_sub_if= _data *sdata) > > if (sdata->local->ops->wake_tx_queue && > sdata->vif.type !=3D NL80211_IFTYPE_P2P_DEVICE && > - sdata->vif.type !=3D NL80211_IFTYPE_NAN) > + sdata->vif.type !=3D NL80211_IFTYPE_NAN) { > DEBUGFS_ADD(aqm); > + DEBUGFS_ADD(airtime); > + } > } > > static void add_sta_files(struct ieee80211_sub_if_data *sdata) > diff --git a/net/mac80211/debugfs_sta.c b/net/mac80211/debugfs_sta.c > index 936c9dfa86c8..8be28cfd6f64 100644 > --- a/net/mac80211/debugfs_sta.c > +++ b/net/mac80211/debugfs_sta.c > @@ -202,7 +202,7 @@ static ssize_t sta_airtime_read(struct file *file, ch= ar __user *userbuf, > size_t bufsz =3D 400; > char *buf =3D kzalloc(bufsz, GFP_KERNEL), *p =3D buf; > u64 rx_airtime =3D 0, tx_airtime =3D 0; > - s64 deficit[IEEE80211_NUM_ACS]; > + u64 v_t[IEEE80211_NUM_ACS]; > ssize_t rv; > int ac; > > @@ -210,18 +210,18 @@ static ssize_t sta_airtime_read(struct file *file, = char __user *userbuf, > return -ENOMEM; > > for (ac =3D 0; ac < IEEE80211_NUM_ACS; ac++) { > - spin_lock_bh(&local->active_txq_lock[ac]); > + spin_lock_bh(&local->airtime[ac].lock); > rx_airtime +=3D sta->airtime[ac].rx_airtime; > tx_airtime +=3D sta->airtime[ac].tx_airtime; > - deficit[ac] =3D sta->airtime[ac].deficit; > - spin_unlock_bh(&local->active_txq_lock[ac]); > + v_t[ac] =3D sta->airtime[ac].v_t; > + spin_unlock_bh(&local->airtime[ac].lock); > } > > p +=3D scnprintf(p, bufsz + buf - p, > "RX: %llu us\nTX: %llu us\nWeight: %u\n" > - "Deficit: VO: %lld us VI: %lld us BE: %lld us BK: %lld us= \n", > - rx_airtime, tx_airtime, sta->airtime_weight, > - deficit[0], deficit[1], deficit[2], deficit[3]); > + "Virt-T: VO: %lld us VI: %lld us BE: %lld us BK: %lld us\= n", > + rx_airtime, tx_airtime, sta->airtime[0].weight, > + v_t[0], v_t[1], v_t[2], v_t[3]); > > rv =3D simple_read_from_buffer(userbuf, count, ppos, buf, p - buf= ); > kfree(buf); > @@ -236,11 +236,11 @@ static ssize_t sta_airtime_write(struct file *file,= const char __user *userbuf, > int ac; > > for (ac =3D 0; ac < IEEE80211_NUM_ACS; ac++) { > - spin_lock_bh(&local->active_txq_lock[ac]); > + spin_lock_bh(&local->airtime[ac].lock); > sta->airtime[ac].rx_airtime =3D 0; > sta->airtime[ac].tx_airtime =3D 0; > - sta->airtime[ac].deficit =3D sta->airtime_weight; > - spin_unlock_bh(&local->active_txq_lock[ac]); > + sta->airtime[ac].v_t =3D 0; > + spin_unlock_bh(&local->airtime[ac].lock); > } > > return count; > @@ -263,10 +263,10 @@ static ssize_t sta_aql_read(struct file *file, char= __user *userbuf, > return -ENOMEM; > > for (ac =3D 0; ac < IEEE80211_NUM_ACS; ac++) { > - spin_lock_bh(&local->active_txq_lock[ac]); > + spin_lock_bh(&local->airtime[ac].lock); > q_limit_l[ac] =3D sta->airtime[ac].aql_limit_low; > q_limit_h[ac] =3D sta->airtime[ac].aql_limit_high; > - spin_unlock_bh(&local->active_txq_lock[ac]); > + spin_unlock_bh(&local->airtime[ac].lock); > q_depth[ac] =3D atomic_read(&sta->airtime[ac].aql_tx_pend= ing); > } > > diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h > index 17068408b27d..22549b95d1aa 100644 > --- a/net/mac80211/ieee80211_i.h > +++ b/net/mac80211/ieee80211_i.h > @@ -831,20 +831,16 @@ enum txq_info_flags { > * @def_flow: used as a fallback flow when a packet destined to @tin has= hes to > * a fq_flow which is already owned by a different tin > * @def_cvars: codel vars for @def_flow > - * @frags: used to keep fragments created after dequeue > * @schedule_order: used with ieee80211_local->active_txqs > - * @schedule_round: counter to prevent infinite loops on TXQ scheduling > + * @frags: used to keep fragments created after dequeue > */ > struct txq_info { > struct fq_tin tin; > struct codel_vars def_cvars; > struct codel_stats cstats; > - > - u16 schedule_round; > - struct list_head schedule_order; > + struct rb_node schedule_order; > > struct sk_buff_head frags; > - > unsigned long flags; > > /* keep last! */ > @@ -921,6 +917,8 @@ struct ieee80211_sub_if_data { > struct ieee80211_tx_queue_params tx_conf[IEEE80211_NUM_ACS]; > struct mac80211_qos_map __rcu *qos_map; > > + struct airtime_info airtime[IEEE80211_NUM_ACS]; > + > struct work_struct csa_finalize_work; > bool csa_block_tx; /* write-protected by sdata_lock and local->mt= x */ > struct cfg80211_chan_def csa_chandef; > @@ -1133,6 +1131,44 @@ enum mac80211_scan_state { > SCAN_ABORT, > }; > > +/** > + * struct airtime_sched_info - state used for airtime scheduling and AQL > + * > + * @lock: spinlock that protects all the fields in this struct > + * @active_txqs: rbtree of currently backlogged queues, sorted by virtua= l time > + * @schedule_pos: the current position maintained while a driver walks t= he tree > + * with ieee80211_next_txq() > + * @active_list: list of struct airtime_info structs that were active wi= thin > + * the last AIRTIME_ACTIVE_DURATION (100 ms), used to comp= ute > + * weight_sum > + * @last_weight_update: used for rate limiting walking active_list > + * @last_schedule_time: tracks the last time a transmission was schedule= d; used > + * for catching up v_t if no stations are eligible = for > + * transmission. > + * @v_t: global virtual time; queues with v_t < this are eligible for > + * transmission > + * @weight_sum: total sum of all active stations used for dividing airti= me > + * @weight_sum_reciprocal: reciprocal of weight_sum (to avoid divisions = in fast > + * path - see comment above > + * IEEE80211_RECIPROCAL_DIVISOR_64) > + * @aql_txq_limit_low: AQL limit when total outstanding airtime > + * is < IEEE80211_AQL_THRESHOLD > + * @aql_txq_limit_high: AQL limit when total outstanding airtime > + * is > IEEE80211_AQL_THRESHOLD > + */ > +struct airtime_sched_info { > + spinlock_t lock; > + struct rb_root_cached active_txqs; > + struct rb_node *schedule_pos; > + struct list_head active_list; > + u64 last_weight_update; > + u64 last_schedule_activity; > + u64 v_t; > + u64 weight_sum; > + u64 weight_sum_reciprocal; > + u32 aql_txq_limit_low; > + u32 aql_txq_limit_high; > +}; > DECLARE_STATIC_KEY_FALSE(aql_disable); > > struct ieee80211_local { > @@ -1146,13 +1182,8 @@ struct ieee80211_local { > struct codel_params cparams; > > /* protects active_txqs and txqi->schedule_order */ > - spinlock_t active_txq_lock[IEEE80211_NUM_ACS]; > - struct list_head active_txqs[IEEE80211_NUM_ACS]; > - u16 schedule_round[IEEE80211_NUM_ACS]; > - > + struct airtime_sched_info airtime[IEEE80211_NUM_ACS]; > u16 airtime_flags; > - u32 aql_txq_limit_low[IEEE80211_NUM_ACS]; > - u32 aql_txq_limit_high[IEEE80211_NUM_ACS]; > u32 aql_threshold; > atomic_t aql_total_pending_airtime; > > @@ -1566,6 +1597,125 @@ static inline bool txq_has_queue(struct ieee80211= _txq *txq) > return !(skb_queue_empty(&txqi->frags) && !txqi->tin.backlog_pack= ets); > } > > +static inline struct airtime_info *to_airtime_info(struct ieee80211_txq = *txq) > +{ > + struct ieee80211_sub_if_data *sdata; > + struct sta_info *sta; > + > + if (txq->sta) { > + sta =3D container_of(txq->sta, struct sta_info, sta); > + return &sta->airtime[txq->ac]; > + } > + > + sdata =3D vif_to_sdata(txq->vif); > + return &sdata->airtime[txq->ac]; > +} > + > +/* To avoid divisions in the fast path, we keep pre-computed reciprocals= for > + * airtime weight calculations. There are two different weights to keep = track > + * of: The per-station weight and the sum of weights per phy. > + * > + * For the per-station weights (kept in airtime_info below), we use 32-b= it > + * reciprocals with a devisor of 2^19. This lets us keep the multiplicat= ions and > + * divisions for the station weights as 32-bit operations at the cost of= a bit > + * of rounding error for high weights; but the choice of divisor keeps r= ounding > + * errors <10% for weights <2^15, assuming no more than 8ms of airtime i= s > + * reported at a time. > + * > + * For the per-phy sum of weights the values can get higher, so we use 6= 4-bit > + * operations for those with a 32-bit divisor, which should avoid any > + * significant rounding errors. > + */ > +#define IEEE80211_RECIPROCAL_DIVISOR_64 0x100000000ULL > +#define IEEE80211_RECIPROCAL_SHIFT_64 32 > +#define IEEE80211_RECIPROCAL_DIVISOR_32 0x80000U > +#define IEEE80211_RECIPROCAL_SHIFT_32 19 > + > +static inline void airtime_weight_set(struct airtime_info *air_info, u16= weight) > +{ > + if (air_info->weight =3D=3D weight) > + return; > + > + air_info->weight =3D weight; > + if (weight) { > + air_info->weight_reciprocal =3D > + IEEE80211_RECIPROCAL_DIVISOR_32 / weight; > + } else { > + air_info->weight_reciprocal =3D 0; > + } > +} > + > +static inline void airtime_weight_sum_set(struct airtime_sched_info *air= _sched, > + int weight_sum) > +{ > + if (air_sched->weight_sum =3D=3D weight_sum) > + return; > + > + air_sched->weight_sum =3D weight_sum; > + if (air_sched->weight_sum) { > + air_sched->weight_sum_reciprocal =3D IEEE80211_RECIPROCAL= _DIVISOR_64; > + do_div(air_sched->weight_sum_reciprocal, air_sched->weigh= t_sum); > + } else { > + air_sched->weight_sum_reciprocal =3D 0; > + } > +} > + > +/* A problem when trying to enforce airtime fairness is that we want to = divide > + * the airtime between the currently *active* stations. However, basing = this on > + * the instantaneous queue state of stations doesn't work, as queues ten= d to > + * oscillate very quickly between empty and occupied, leading to the sch= eduler > + * thinking only a single station is active when deciding whether to all= ow > + * transmission (and thus not throttling correctly). > + * > + * To fix this we use a timer-based notion of activity: a station is con= sidered > + * active if it has been scheduled within the last 100 ms; we keep a sep= arate > + * list of all the stations considered active in this manner, and lazily= update > + * the total weight of active stations from this list (filtering the sta= tions in > + * the list by their 'last active' time). > + * > + * We add one additional safeguard to guard against stations that manage= to get > + * scheduled every 100 ms but don't transmit a lot of data, and thus don= 't use > + * up any airtime. Such stations would be able to get priority for an ex= tended > + * period of time if they do start transmitting at full capacity again, = and so > + * we add an explicit maximum for how far behind a station is allowed to= fall in > + * the virtual airtime domain. This limit is set to a relatively high va= lue of > + * 20 ms because the main mechanism for catching up idle stations is the= active > + * state as described above; i.e., the hard limit should only be hit in > + * pathological cases. > + */ > +#define AIRTIME_ACTIVE_DURATION (100 * NSEC_PER_MSEC) > +#define AIRTIME_MAX_BEHIND 20000 /* 20 ms */ > + > +static inline bool airtime_is_active(struct airtime_info *air_info, u64 = now) > +{ > + return air_info->last_scheduled >=3D now - AIRTIME_ACTIVE_DURATIO= N; > +} > + > +static inline void airtime_set_active(struct airtime_sched_info *air_sch= ed, > + struct airtime_info *air_info, u64 = now) > +{ > + air_info->last_scheduled =3D now; > + air_sched->last_schedule_activity =3D now; > + list_move_tail(&air_info->list, &air_sched->active_list); > +} > + > +static inline bool airtime_catchup_v_t(struct airtime_sched_info *air_sc= hed, > + u64 v_t, u64 now) > +{ > + air_sched->v_t =3D v_t; > + return true; > +} > + > +static inline void init_airtime_info(struct airtime_info *air_info, > + struct airtime_sched_info *air_sched= ) > +{ > + atomic_set(&air_info->aql_tx_pending, 0); > + air_info->aql_limit_low =3D air_sched->aql_txq_limit_low; > + air_info->aql_limit_high =3D air_sched->aql_txq_limit_high; > + airtime_weight_set(air_info, IEEE80211_DEFAULT_AIRTIME_WEIGHT); > + INIT_LIST_HEAD(&air_info->list); > +} > + > static inline int ieee80211_bssid_match(const u8 *raddr, const u8 *addr) > { > return ether_addr_equal(raddr, addr) || > @@ -1808,6 +1958,14 @@ int ieee80211_tx_control_port(struct wiphy *wiphy,= struct net_device *dev, > u64 *cookie); > int ieee80211_probe_mesh_link(struct wiphy *wiphy, struct net_device *de= v, > const u8 *buf, size_t len); > +void ieee80211_resort_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq); > +void ieee80211_unschedule_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq, > + bool purge); > +void ieee80211_update_airtime_weight(struct ieee80211_local *local, > + struct airtime_sched_info *air_sched= , > + u64 now, bool force); > > /* HT */ > void ieee80211_apply_htcap_overrides(struct ieee80211_sub_if_data *sdata= , > diff --git a/net/mac80211/iface.c b/net/mac80211/iface.c > index 68375ef56b4a..1e5e9fc45523 100644 > --- a/net/mac80211/iface.c > +++ b/net/mac80211/iface.c > @@ -1977,6 +1977,9 @@ int ieee80211_if_add(struct ieee80211_local *local,= const char *name, > } > } > > + for (i =3D 0; i < IEEE80211_NUM_ACS; i++) > + init_airtime_info(&sdata->airtime[i], &local->airtime[i])= ; > + > ieee80211_set_default_queues(sdata); > > sdata->ap_power_level =3D IEEE80211_UNSET_POWER_LEVEL; > diff --git a/net/mac80211/main.c b/net/mac80211/main.c > index 95a8300da2d0..05f4c3c72619 100644 > --- a/net/mac80211/main.c > +++ b/net/mac80211/main.c > @@ -705,10 +705,13 @@ struct ieee80211_hw *ieee80211_alloc_hw_nm(size_t p= riv_data_len, > spin_lock_init(&local->queue_stop_reason_lock); > > for (i =3D 0; i < IEEE80211_NUM_ACS; i++) { > - INIT_LIST_HEAD(&local->active_txqs[i]); > - spin_lock_init(&local->active_txq_lock[i]); > - local->aql_txq_limit_low[i] =3D IEEE80211_DEFAULT_AQL_TXQ= _LIMIT_L; > - local->aql_txq_limit_high[i] =3D > + struct airtime_sched_info *air_sched =3D &local->airtime[= i]; > + > + air_sched->active_txqs =3D RB_ROOT_CACHED; > + INIT_LIST_HEAD(&air_sched->active_list); > + spin_lock_init(&air_sched->lock); > + air_sched->aql_txq_limit_low =3D IEEE80211_DEFAULT_AQL_TX= Q_LIMIT_L; > + air_sched->aql_txq_limit_high =3D > IEEE80211_DEFAULT_AQL_TXQ_LIMIT_H; > } > > diff --git a/net/mac80211/rx.c b/net/mac80211/rx.c > index a6400adf08bf..771921c057e8 100644 > --- a/net/mac80211/rx.c > +++ b/net/mac80211/rx.c > @@ -1578,12 +1578,8 @@ static void sta_ps_start(struct sta_info *sta) > > for (tid =3D 0; tid < IEEE80211_NUM_TIDS; tid++) { > struct ieee80211_txq *txq =3D sta->sta.txq[tid]; > - struct txq_info *txqi =3D to_txq_info(txq); > > - spin_lock(&local->active_txq_lock[txq->ac]); > - if (!list_empty(&txqi->schedule_order)) > - list_del_init(&txqi->schedule_order); > - spin_unlock(&local->active_txq_lock[txq->ac]); > + ieee80211_unschedule_txq(&local->hw, txq, false); > > if (txq_has_queue(txq)) > set_bit(tid, &sta->txq_buffered_tids); > diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c > index 641a6657d0c9..f984f01fa0ab 100644 > --- a/net/mac80211/sta_info.c > +++ b/net/mac80211/sta_info.c > @@ -425,15 +425,11 @@ struct sta_info *sta_info_alloc(struct ieee80211_su= b_if_data *sdata, > if (sta_prepare_rate_control(local, sta, gfp)) > goto free_txq; > > - sta->airtime_weight =3D IEEE80211_DEFAULT_AIRTIME_WEIGHT; > > 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; > - atomic_set(&sta->airtime[i].aql_tx_pending, 0); > - sta->airtime[i].aql_limit_low =3D local->aql_txq_limit_lo= w[i]; > - sta->airtime[i].aql_limit_high =3D local->aql_txq_limit_h= igh[i]; > + init_airtime_info(&sta->airtime[i], &local->airtime[i]); > } > > for (i =3D 0; i < IEEE80211_NUM_TIDS; i++) > @@ -1897,24 +1893,59 @@ void ieee80211_sta_set_buffered(struct ieee80211_= sta *pubsta, > } > EXPORT_SYMBOL(ieee80211_sta_set_buffered); > > -void ieee80211_sta_register_airtime(struct ieee80211_sta *pubsta, u8 tid= , > - u32 tx_airtime, u32 rx_airtime) > +void ieee80211_register_airtime(struct ieee80211_txq *txq, > + u32 tx_airtime, u32 rx_airtime) > { > - struct sta_info *sta =3D container_of(pubsta, struct sta_info, st= a); > - struct ieee80211_local *local =3D sta->sdata->local; > - u8 ac =3D ieee80211_ac_from_tid(tid); > + struct ieee80211_sub_if_data *sdata =3D vif_to_sdata(txq->vif); > + struct ieee80211_local *local =3D sdata->local; > + u64 weight_sum, weight_sum_reciprocal; > + struct airtime_sched_info *air_sched; > + struct airtime_info *air_info; > u32 airtime =3D 0; > > - if (sta->local->airtime_flags & AIRTIME_USE_TX) > + air_sched =3D &local->airtime[txq->ac]; > + air_info =3D to_airtime_info(txq); > + > + if (local->airtime_flags & AIRTIME_USE_TX) > airtime +=3D tx_airtime; > - if (sta->local->airtime_flags & AIRTIME_USE_RX) > + if (local->airtime_flags & AIRTIME_USE_RX) > airtime +=3D rx_airtime; > > - 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; > - spin_unlock_bh(&local->active_txq_lock[ac]); > + /* Weights scale so the unit weight is 256 */ > + airtime <<=3D 8; > + > + spin_lock_bh(&air_sched->lock); > + > + air_info->tx_airtime +=3D tx_airtime; > + air_info->rx_airtime +=3D rx_airtime; > + > + if (air_sched->weight_sum) { > + weight_sum =3D air_sched->weight_sum; > + weight_sum_reciprocal =3D air_sched->weight_sum_reciproca= l; > + } else { > + weight_sum =3D air_info->weight; > + weight_sum_reciprocal =3D air_info->weight_reciprocal; > + } > + > + /* Round the calculation of global vt */ > + air_sched->v_t +=3D (u64)((airtime + (weight_sum >> 1)) * > + weight_sum_reciprocal) >> IEEE80211_RECIP= ROCAL_SHIFT_64; > + air_info->v_t +=3D (u32)((airtime + (air_info->weight >> 1)) * > + air_info->weight_reciprocal) >> IEEE80211_= RECIPROCAL_SHIFT_32; > + ieee80211_resort_txq(&local->hw, txq); > + > + spin_unlock_bh(&air_sched->lock); > +} > + > +void ieee80211_sta_register_airtime(struct ieee80211_sta *pubsta, u8 tid= , > + u32 tx_airtime, u32 rx_airtime) > +{ > + struct ieee80211_txq *txq =3D pubsta->txq[tid]; > + > + if (!txq) > + return; > + > + ieee80211_register_airtime(txq, tx_airtime, rx_airtime); > } > EXPORT_SYMBOL(ieee80211_sta_register_airtime); > > @@ -2358,7 +2389,7 @@ void sta_set_sinfo(struct sta_info *sta, struct sta= tion_info *sinfo, > } > > if (!(sinfo->filled & BIT_ULL(NL80211_STA_INFO_AIRTIME_WEIGHT))) = { > - sinfo->airtime_weight =3D sta->airtime_weight; > + sinfo->airtime_weight =3D sta->airtime[0].weight; > sinfo->filled |=3D BIT_ULL(NL80211_STA_INFO_AIRTIME_WEIGH= T); > } > > diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h > index 0333072ebd98..ba2796782008 100644 > --- a/net/mac80211/sta_info.h > +++ b/net/mac80211/sta_info.h > @@ -135,18 +135,25 @@ enum ieee80211_agg_stop_reason { > #define AIRTIME_USE_TX BIT(0) > #define AIRTIME_USE_RX BIT(1) > > + > struct airtime_info { > u64 rx_airtime; > u64 tx_airtime; > - s64 deficit; > + u64 v_t; > + u64 last_scheduled; > + struct list_head list; > atomic_t aql_tx_pending; /* Estimated airtime for frames pending = */ > u32 aql_limit_low; > u32 aql_limit_high; > + u32 weight_reciprocal; > + u16 weight; > }; > > void ieee80211_sta_update_pending_airtime(struct ieee80211_local *local, > struct sta_info *sta, u8 ac, > u16 tx_airtime, bool tx_complet= ed); > +void ieee80211_register_airtime(struct ieee80211_txq *txq, > + u32 tx_airtime, u32 rx_airtime); > > struct sta_info; > > @@ -515,7 +522,6 @@ struct ieee80211_fragment_cache { > * @tid_seq: per-TID sequence numbers for sending to this STA > * @airtime: per-AC struct airtime_info describing airtime statistics fo= r this > * station > - * @airtime_weight: station weight for airtime fairness calculation purp= oses > * @ampdu_mlme: A-MPDU state machine state > * @mesh: mesh STA information > * @debugfs_dir: debug filesystem directory dentry > @@ -646,7 +652,6 @@ struct sta_info { > u16 tid_seq[IEEE80211_QOS_CTL_TID_MASK + 1]; > > struct airtime_info airtime[IEEE80211_NUM_ACS]; > - u16 airtime_weight; > > /* > * Aggregation information, locked with lock. > diff --git a/net/mac80211/status.c b/net/mac80211/status.c > index 9baf185ee4c7..606902e03c01 100644 > --- a/net/mac80211/status.c > +++ b/net/mac80211/status.c > @@ -970,6 +970,25 @@ static void __ieee80211_tx_status(struct ieee80211_h= w *hw, > if (!(info->flags & IEEE80211_TX_CTL_INJECTED) && acked) > ieee80211_frame_acked(sta, skb); > > + } else if (wiphy_ext_feature_isset(local->hw.wiphy, > + NL80211_EXT_FEATURE_AIRTIME_FA= IRNESS)) { > + struct ieee80211_sub_if_data *sdata; > + struct ieee80211_txq *txq; > + u32 airtime; > + > + /* Account airtime to multicast queue */ > + sdata =3D ieee80211_sdata_from_skb(local, skb); > + > + if (sdata && (txq =3D sdata->vif.txq)) { > + airtime =3D info->status.tx_time ?: > + ieee80211_calc_expected_tx_airtime(hw, > + &sdata= ->vif, > + NULL, > + skb->l= en, > + false)= ; > + > + ieee80211_register_airtime(txq, airtime, 0); > + } > } > > /* SNMP counters > diff --git a/net/mac80211/tx.c b/net/mac80211/tx.c > index caa7caa89ab9..e96981144358 100644 > --- a/net/mac80211/tx.c > +++ b/net/mac80211/tx.c > @@ -18,6 +18,7 @@ > #include > #include > #include > +#include > #include > #include > #include > @@ -1449,7 +1450,7 @@ void ieee80211_txq_init(struct ieee80211_sub_if_dat= a *sdata, > codel_vars_init(&txqi->def_cvars); > codel_stats_init(&txqi->cstats); > __skb_queue_head_init(&txqi->frags); > - INIT_LIST_HEAD(&txqi->schedule_order); > + RB_CLEAR_NODE(&txqi->schedule_order); > > txqi->txq.vif =3D &sdata->vif; > > @@ -1493,9 +1494,7 @@ void ieee80211_txq_purge(struct ieee80211_local *lo= cal, > ieee80211_purge_tx_queue(&local->hw, &txqi->frags); > spin_unlock_bh(&fq->lock); > > - spin_lock_bh(&local->active_txq_lock[txqi->txq.ac]); > - list_del_init(&txqi->schedule_order); > - spin_unlock_bh(&local->active_txq_lock[txqi->txq.ac]); > + ieee80211_unschedule_txq(&local->hw, &txqi->txq, true); > } > > void ieee80211_txq_set_params(struct ieee80211_local *local) > @@ -3783,102 +3782,259 @@ EXPORT_SYMBOL(ieee80211_tx_dequeue); > struct ieee80211_txq *ieee80211_next_txq(struct ieee80211_hw *hw, u8 ac) > { > struct ieee80211_local *local =3D hw_to_local(hw); > + struct airtime_sched_info *air_sched; > + u64 now =3D ktime_get_boottime_ns(); > struct ieee80211_txq *ret =3D NULL; > - struct txq_info *txqi =3D NULL, *head =3D NULL; > - bool found_eligible_txq =3D false; > + struct airtime_info *air_info; > + struct txq_info *txqi =3D NULL; > + struct rb_node *node; > + bool first =3D false; > > - spin_lock_bh(&local->active_txq_lock[ac]); > + air_sched =3D &local->airtime[ac]; > + spin_lock_bh(&air_sched->lock); > > - begin: > - txqi =3D list_first_entry_or_null(&local->active_txqs[ac], > - struct txq_info, > - schedule_order); > - if (!txqi) > + node =3D air_sched->schedule_pos; > + > +begin: > + if (!node) { > + node =3D rb_first_cached(&air_sched->active_txqs); > + first =3D true; > + } else { > + node =3D rb_next(node); > + } > + > + if (!node) > goto out; > > - if (txqi =3D=3D head) { > - if (!found_eligible_txq) > - goto out; > - else > - found_eligible_txq =3D false; > + txqi =3D container_of(node, struct txq_info, schedule_order); > + air_info =3D to_airtime_info(&txqi->txq); > + > + if (air_info->v_t > air_sched->v_t && > + (!first || !airtime_catchup_v_t(air_sched, air_info->v_t, now= ))) > + goto out; > + > + if (!ieee80211_txq_airtime_check(hw, &txqi->txq)) { > + first =3D false; > + goto begin; > } > > - if (!head) > - head =3D txqi; > + air_sched->schedule_pos =3D node; > + air_sched->last_schedule_activity =3D now; > + ret =3D &txqi->txq; > +out: > + spin_unlock_bh(&air_sched->lock); > + return ret; > +} > +EXPORT_SYMBOL(ieee80211_next_txq); > > - if (txqi->txq.sta) { > - struct sta_info *sta =3D container_of(txqi->txq.sta, > - struct sta_info, sta)= ; > - bool aql_check =3D ieee80211_txq_airtime_check(hw, &txqi-= >txq); > - s64 deficit =3D sta->airtime[txqi->txq.ac].deficit; > +static void __ieee80211_insert_txq(struct rb_root_cached *root, > + struct txq_info *txqi) > +{ > + struct rb_node **new =3D &root->rb_root.rb_node; > + struct airtime_info *old_air, *new_air; > + 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_ord= er); > + old_air =3D to_airtime_info(&__txqi->txq); > + new_air =3D to_airtime_info(&txqi->txq); > + > + if (new_air->v_t <=3D old_air->v_t) { > + new =3D &parent->rb_left; > + } else { > + new =3D &parent->rb_right; > + leftmost =3D false; > + } > + } > > - if (aql_check) > - found_eligible_txq =3D true; > + rb_link_node(&txqi->schedule_order, parent, new); > + rb_insert_color_cached(&txqi->schedule_order, root, leftmost); > +} > > - if (deficit < 0) > - sta->airtime[txqi->txq.ac].deficit +=3D > - sta->airtime_weight; > +void ieee80211_resort_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq) > +{ > + struct airtime_info *air_info =3D to_airtime_info(txq); > + struct ieee80211_local *local =3D hw_to_local(hw); > + struct txq_info *txqi =3D to_txq_info(txq); > + struct airtime_sched_info *air_sched; > > - if (deficit < 0 || !aql_check) { > - list_move_tail(&txqi->schedule_order, > - &local->active_txqs[txqi->txq.ac])= ; > - goto begin; > + air_sched =3D &local->airtime[txq->ac]; > + > + lockdep_assert_held(&air_sched->lock); > + > + if (!RB_EMPTY_NODE(&txqi->schedule_order)) { > + struct airtime_info *a_prev =3D NULL, *a_next =3D NULL; > + struct txq_info *t_prev, *t_next; > + struct rb_node *n_prev, *n_next; > + > + /* Erasing a node can cause an expensive rebalancing oper= ation, > + * so we check the previous and next nodes first and only= remove > + * and re-insert if the current node is not already in th= e > + * correct position. > + */ > + if ((n_prev =3D rb_prev(&txqi->schedule_order)) !=3D NULL= ) { > + t_prev =3D container_of(n_prev, struct txq_info, > + schedule_order); > + a_prev =3D to_airtime_info(&t_prev->txq); > } > + > + if ((n_next =3D rb_next(&txqi->schedule_order)) !=3D NULL= ) { > + t_next =3D container_of(n_next, struct txq_info, > + schedule_order); > + a_next =3D to_airtime_info(&t_next->txq); > + } > + > + if ((!a_prev || a_prev->v_t <=3D air_info->v_t) && > + (!a_next || a_next->v_t > air_info->v_t)) > + return; > + > + if (air_sched->schedule_pos =3D=3D &txqi->schedule_order) > + air_sched->schedule_pos =3D n_prev; > + > + rb_erase_cached(&txqi->schedule_order, > + &air_sched->active_txqs); > + RB_CLEAR_NODE(&txqi->schedule_order); > + __ieee80211_insert_txq(&air_sched->active_txqs, txqi); > } > +} > > +void ieee80211_update_airtime_weight(struct ieee80211_local *local, > + struct airtime_sched_info *air_sched= , > + u64 now, bool force) > +{ > + struct airtime_info *air_info, *tmp; > + u64 weight_sum =3D 0; > + > + if (unlikely(!now)) > + now =3D ktime_get_boottime_ns(); > > - if (txqi->schedule_round =3D=3D local->schedule_round[ac]) > + lockdep_assert_held(&air_sched->lock); > + > + if (!force && (air_sched->last_weight_update < > + now - AIRTIME_ACTIVE_DURATION)) > + return; > + > + list_for_each_entry_safe(air_info, tmp, > + &air_sched->active_list, list) { > + if (airtime_is_active(air_info, now)) > + weight_sum +=3D air_info->weight; > + else > + list_del_init(&air_info->list); > + } > + airtime_weight_sum_set(air_sched, weight_sum); > + air_sched->last_weight_update =3D now; > +} > + > +void ieee80211_schedule_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq) > + __acquires(txq_lock) __releases(txq_lock) > +{ > + struct ieee80211_local *local =3D hw_to_local(hw); > + struct txq_info *txqi =3D to_txq_info(txq); > + struct airtime_sched_info *air_sched; > + u64 now =3D ktime_get_boottime_ns(); > + struct airtime_info *air_info; > + u8 ac =3D txq->ac; > + bool was_active; > + > + air_sched =3D &local->airtime[ac]; > + air_info =3D to_airtime_info(txq); > + > + spin_lock_bh(&air_sched->lock); > + was_active =3D airtime_is_active(air_info, now); > + airtime_set_active(air_sched, air_info, now); > + > + if (!RB_EMPTY_NODE(&txqi->schedule_order)) > goto out; > > - list_del_init(&txqi->schedule_order); > - txqi->schedule_round =3D local->schedule_round[ac]; > - ret =3D &txqi->txq; > + /* If the station has been inactive for a while, catch up its v_t= so it > + * doesn't get indefinite priority; see comment above the definit= ion of > + * AIRTIME_MAX_BEHIND. > + */ > + if ((!was_active && air_info->v_t < air_sched->v_t) || > + air_info->v_t < air_sched->v_t - AIRTIME_MAX_BEHIND) > + air_info->v_t =3D air_sched->v_t; > + > + ieee80211_update_airtime_weight(local, air_sched, now, !was_activ= e); > + __ieee80211_insert_txq(&air_sched->active_txqs, txqi); > > out: > - spin_unlock_bh(&local->active_txq_lock[ac]); > - return ret; > + spin_unlock_bh(&air_sched->lock); > } > -EXPORT_SYMBOL(ieee80211_next_txq); > +EXPORT_SYMBOL(ieee80211_schedule_txq); > > -void __ieee80211_schedule_txq(struct ieee80211_hw *hw, > - struct ieee80211_txq *txq, > - bool force) > +static void __ieee80211_unschedule_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq, > + bool purge) > { > struct ieee80211_local *local =3D hw_to_local(hw); > struct txq_info *txqi =3D to_txq_info(txq); > + struct airtime_sched_info *air_sched; > + struct airtime_info *air_info; > > - spin_lock_bh(&local->active_txq_lock[txq->ac]); > - > - if (list_empty(&txqi->schedule_order) && > - (force || !skb_queue_empty(&txqi->frags) || > - txqi->tin.backlog_packets)) { > - /* If airtime accounting is active, always enqueue STAs a= t the > - * head of the list to ensure that they only get moved to= the > - * back by the airtime DRR scheduler once they have a neg= ative > - * deficit. A station that already has a negative deficit= will > - * get immediately moved to the back of the list on the n= ext > - * call to ieee80211_next_txq(). > - */ > - if (txqi->txq.sta && local->airtime_flags && > - wiphy_ext_feature_isset(local->hw.wiphy, > - NL80211_EXT_FEATURE_AIRTIME_F= AIRNESS)) > - list_add(&txqi->schedule_order, > - &local->active_txqs[txq->ac]); > - else > - list_add_tail(&txqi->schedule_order, > - &local->active_txqs[txq->ac]); > + air_sched =3D &local->airtime[txq->ac]; > + air_info =3D to_airtime_info(&txqi->txq); > + > + lockdep_assert_held(&air_sched->lock); > + > + if (purge) { > + list_del_init(&air_info->list); > + ieee80211_update_airtime_weight(local, air_sched, 0, true= ); > } > > - spin_unlock_bh(&local->active_txq_lock[txq->ac]); > + if (RB_EMPTY_NODE(&txqi->schedule_order)) > + return; > + > + if (air_sched->schedule_pos =3D=3D &txqi->schedule_order) > + air_sched->schedule_pos =3D rb_prev(&txqi->schedule_order= ); > + > + if (!purge) > + airtime_set_active(air_sched, air_info, > + ktime_get_boottime_ns()); > + > + rb_erase_cached(&txqi->schedule_order, > + &air_sched->active_txqs); > + RB_CLEAR_NODE(&txqi->schedule_order); > +} > + > +void ieee80211_unschedule_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq, > + bool purge) > + __acquires(txq_lock) __releases(txq_lock) > +{ > + struct ieee80211_local *local =3D hw_to_local(hw); > + > + spin_lock_bh(&local->airtime[txq->ac].lock); > + __ieee80211_unschedule_txq(hw, txq, purge); > + spin_unlock_bh(&local->airtime[txq->ac].lock); > +} > + > +void ieee80211_return_txq(struct ieee80211_hw *hw, > + struct ieee80211_txq *txq, bool force) > +{ > + struct ieee80211_local *local =3D hw_to_local(hw); > + struct txq_info *txqi =3D to_txq_info(txq); > + > + spin_lock_bh(&local->airtime[txq->ac].lock); > + > + if (!RB_EMPTY_NODE(&txqi->schedule_order) && !force && > + !txq_has_queue(txq)) > + __ieee80211_unschedule_txq(hw, txq, false); > + > + spin_unlock_bh(&local->airtime[txq->ac].lock); > } > -EXPORT_SYMBOL(__ieee80211_schedule_txq); > +EXPORT_SYMBOL(ieee80211_return_txq); > > DEFINE_STATIC_KEY_FALSE(aql_disable); > > bool ieee80211_txq_airtime_check(struct ieee80211_hw *hw, > struct ieee80211_txq *txq) > { > - struct sta_info *sta; > + struct airtime_info *air_info =3D to_airtime_info(txq); > struct ieee80211_local *local =3D hw_to_local(hw); > > if (!wiphy_ext_feature_isset(local->hw.wiphy, NL80211_EXT_FEATURE= _AQL)) > @@ -3893,15 +4049,12 @@ bool ieee80211_txq_airtime_check(struct ieee80211= _hw *hw, > if (unlikely(txq->tid =3D=3D IEEE80211_NUM_TIDS)) > return true; > > - sta =3D container_of(txq->sta, struct sta_info, sta); > - if (atomic_read(&sta->airtime[txq->ac].aql_tx_pending) < > - sta->airtime[txq->ac].aql_limit_low) > + if (atomic_read(&air_info->aql_tx_pending) < air_info->aql_limit_= low) > return true; > > if (atomic_read(&local->aql_total_pending_airtime) < > local->aql_threshold && > - atomic_read(&sta->airtime[txq->ac].aql_tx_pending) < > - sta->airtime[txq->ac].aql_limit_high) > + atomic_read(&air_info->aql_tx_pending) < air_info->aql_limit_= high) > return true; > > return false; > @@ -3911,60 +4064,59 @@ EXPORT_SYMBOL(ieee80211_txq_airtime_check); > bool ieee80211_txq_may_transmit(struct ieee80211_hw *hw, > struct ieee80211_txq *txq) > { > + struct txq_info *first_txqi =3D NULL, *txqi =3D to_txq_info(txq); > struct ieee80211_local *local =3D hw_to_local(hw); > - struct txq_info *iter, *tmp, *txqi =3D to_txq_info(txq); > - struct sta_info *sta; > - u8 ac =3D txq->ac; > + struct airtime_sched_info *air_sched; > + struct airtime_info *air_info; > + struct rb_node *node =3D NULL; > + bool ret =3D false; > + u64 now; > > - spin_lock_bh(&local->active_txq_lock[ac]); > > - if (!txqi->txq.sta) > - goto out; > + if (!ieee80211_txq_airtime_check(hw, txq)) > + return false; > + > + air_sched =3D &local->airtime[txq->ac]; > + spin_lock_bh(&air_sched->lock); > > - if (list_empty(&txqi->schedule_order)) > + if (RB_EMPTY_NODE(&txqi->schedule_order)) > goto out; > > - list_for_each_entry_safe(iter, tmp, &local->active_txqs[ac], > - schedule_order) { > - if (iter =3D=3D txqi) > - break; > + now =3D ktime_get_boottime_ns(); > > - if (!iter->txq.sta) { > - list_move_tail(&iter->schedule_order, > - &local->active_txqs[ac]); > - continue; > - } > - sta =3D container_of(iter->txq.sta, struct sta_info, sta)= ; > - if (sta->airtime[ac].deficit < 0) > - sta->airtime[ac].deficit +=3D sta->airtime_weight= ; > - list_move_tail(&iter->schedule_order, &local->active_txqs= [ac]); > - } > + /* Like in ieee80211_next_txq(), make sure the first station in t= he > + * scheduling order is eligible for transmission to avoid starvat= ion. > + */ > + node =3D rb_first_cached(&air_sched->active_txqs); > + if (node) { > + first_txqi =3D container_of(node, struct txq_info, > + schedule_order); > + air_info =3D to_airtime_info(&first_txqi->txq); > > - sta =3D container_of(txqi->txq.sta, struct sta_info, sta); > - if (sta->airtime[ac].deficit >=3D 0) > - goto out; > + if (air_sched->v_t < air_info->v_t) > + airtime_catchup_v_t(air_sched, air_info->v_t, now= ); > + } > > - sta->airtime[ac].deficit +=3D sta->airtime_weight; > - list_move_tail(&txqi->schedule_order, &local->active_txqs[ac]); > - spin_unlock_bh(&local->active_txq_lock[ac]); > + air_info =3D to_airtime_info(&txqi->txq); > + if (air_info->v_t <=3D air_sched->v_t) { > + air_sched->last_schedule_activity =3D now; > + ret =3D true; > + } > > - return false; > out: > - if (!list_empty(&txqi->schedule_order)) > - list_del_init(&txqi->schedule_order); > - spin_unlock_bh(&local->active_txq_lock[ac]); > - > - return true; > + spin_unlock_bh(&air_sched->lock); > + return ret; > } > EXPORT_SYMBOL(ieee80211_txq_may_transmit); > > void ieee80211_txq_schedule_start(struct ieee80211_hw *hw, u8 ac) > { > struct ieee80211_local *local =3D hw_to_local(hw); > + struct airtime_sched_info *air_sched =3D &local->airtime[ac]; > > - spin_lock_bh(&local->active_txq_lock[ac]); > - local->schedule_round[ac]++; > - spin_unlock_bh(&local->active_txq_lock[ac]); > + spin_lock_bh(&air_sched->lock); > + air_sched->schedule_pos =3D NULL; > + spin_unlock_bh(&air_sched->lock); > } > EXPORT_SYMBOL(ieee80211_txq_schedule_start); > > -- > 2.32.0 > > _______________________________________________ > Make-wifi-fast mailing list > Make-wifi-fast@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/make-wifi-fast --=20 Latest Podcast: https://www.linkedin.com/feed/update/urn:li:activity:6791014284936785920/ Dave T=C3=A4ht CTO, TekLibre, LLC