From: Felix Fietkau <nbd@nbd.name>
To: "Toke Høiland-Jørgensen" <toke@redhat.com>,
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
Date: Thu, 7 Mar 2019 15:27:52 +0100 [thread overview]
Message-ID: <f6c5bc25-a8b3-bac3-8d62-d41347a6c070@nbd.name> (raw)
In-Reply-To: <20190215170512.31512-1-toke@redhat.com>
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:
> 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?
> --- 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 = &root->rb_root.rb_node;
> + struct rb_node *parent = NULL;
> + struct txq_info *__txqi;
> + bool leftmost = true;
> +
> + while (*new) {
> + parent = *new;
> + __txqi = rb_entry(parent, struct txq_info, schedule_order);
> +
> + if (!txqi->txq.sta) {
> + /* new txqi has no sta - insert to the left */
> + new = &parent->rb_left;
> + } else if (!__txqi->txq.sta) {
> + /* existing txqi has no sta - insert to the right */
> + new = &parent->rb_right;
> + leftmost = false;
> + } else {
> + struct sta_info *old_sta = container_of(__txqi->txq.sta,
> + struct sta_info,
> + sta);
> + struct sta_info *new_sta = container_of(txqi->txq.sta,
> + struct sta_info,
> + sta);
> +
> + if (new_sta->airtime[ac].v_t <= old_sta->airtime[ac].v_t)
> + new = &parent->rb_left;
> + else {
> + new = &parent->rb_right;
> + leftmost = 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?
- Felix
next prev parent reply other threads:[~2019-03-07 14:27 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-02-15 17:05 [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler Toke Høiland-Jørgensen
2019-02-15 19:44 ` [Make-wifi-fast] " Dave Taht
2019-03-05 15:45 ` Toke Høiland-Jørgensen
2019-03-06 23:09 ` Rajkumar Manoharan
2019-03-07 9:46 ` Toke Høiland-Jørgensen
2019-03-07 14:27 ` Felix Fietkau [this message]
2019-03-08 11:05 ` Toke Høiland-Jørgensen
2019-03-08 18:16 ` Felix Fietkau
2019-03-08 19:06 ` Toke Høiland-Jørgensen
2019-04-04 4:41 ` Yibo Zhao
2019-04-04 4:43 ` Yibo Zhao
2019-04-04 5:00 ` Yibo Zhao
2019-04-04 8:31 ` Toke Høiland-Jørgensen
2019-04-04 8:36 ` [Make-wifi-fast] " Dave Taht
2019-04-04 8:50 ` Toke Høiland-Jørgensen
2019-04-09 13:25 ` Yibo Zhao
2019-04-09 20:41 ` Toke Høiland-Jørgensen
2019-04-10 6:35 ` Yibo Zhao
2019-04-10 10:40 ` Toke Høiland-Jørgensen
2019-04-11 3:12 ` Yibo Zhao
2019-04-11 11:24 ` Toke Høiland-Jørgensen
2019-04-12 6:34 ` Yibo Zhao
2019-04-19 15:05 ` Yibo Zhao
2019-04-20 21:15 ` Toke Høiland-Jørgensen
2019-04-30 9:45 ` Yibo Zhao
2019-04-30 10:39 ` Toke Høiland-Jørgensen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f6c5bc25-a8b3-bac3-8d62-d41347a6c070@nbd.name \
--to=nbd@nbd.name \
--cc=kyan@google.com \
--cc=linux-wireless@vger.kernel.org \
--cc=make-wifi-fast@lists.bufferbloat.net \
--cc=rmanohar@codeaurora.org \
--cc=toke@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).