2018-09-21 00:50:31

by Rajkumar Manoharan

[permalink] [raw]
Subject: [RFC v2] mac80211: budget outstanding airtime for transmission

Per frame airtime estimation could be used to track outstanding airtime
of each txq and can be used to throttle ieee80211_tx_dequeue(). This
mechanism on its own will get us the queue limiting and latency
reduction goodness for firmwares with deep queues. And for that it can
be completely independent of the airtime fairness scheduler, which can
use the after-tx-compl airtime information to presumably get more
accurate fairness which includes retransmissions etc.

Signed-off-by: Kan Yan <[email protected]>
Signed-off-by: Toke Høiland-Jørgensen <[email protected]>
Signed-off-by: Rajkumar Manoharan <[email protected]>
---
include/net/mac80211.h | 2 +-
net/mac80211/sta_info.h | 1 +
net/mac80211/status.c | 22 ++++++++++++++----
net/mac80211/tx.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++--
4 files changed, 79 insertions(+), 7 deletions(-)

diff --git a/include/net/mac80211.h b/include/net/mac80211.h
index 89b192e93ac9..3a9a61fe30b5 100644
--- a/include/net/mac80211.h
+++ b/include/net/mac80211.h
@@ -947,7 +947,7 @@ struct ieee80211_tx_info {
u8 use_cts_prot:1;
u8 short_preamble:1;
u8 skip_table:1;
- /* 2 bytes free */
+ u16 airtime_est;
};
/* only needed before rate control */
unsigned long jiffies;
diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
index b1b0fd6a2e21..06fdac2ee202 100644
--- a/net/mac80211/sta_info.h
+++ b/net/mac80211/sta_info.h
@@ -135,6 +135,7 @@ struct airtime_info {
u64 rx_airtime;
u64 tx_airtime;
s64 deficit;
+ u32 budget;
};

struct sta_info;
diff --git a/net/mac80211/status.c b/net/mac80211/status.c
index 664379797c46..81cc4a2c98b2 100644
--- a/net/mac80211/status.c
+++ b/net/mac80211/status.c
@@ -718,6 +718,7 @@ static void __ieee80211_tx_status(struct ieee80211_hw *hw,
struct ieee80211_bar *bar;
int shift = 0;
int tid = IEEE80211_NUM_TIDS;
+ u32 ac = IEEE80211_AC_BE;

rates_idx = ieee80211_tx_get_rates(hw, info, &retry_count);

@@ -733,6 +734,23 @@ static void __ieee80211_tx_status(struct ieee80211_hw *hw,

acked = !!(info->flags & IEEE80211_TX_STAT_ACK);

+ if (ieee80211_is_data_qos(fc)) {
+ u8 *qc = ieee80211_get_qos_ctl(hdr);
+
+ tid = qc[0] & 0xf;
+ ac = ieee80211_ac_from_tid(tid);
+ }
+ if (wiphy_ext_feature_isset(local->hw.wiphy,
+ NL80211_EXT_FEATURE_AIRTIME_FAIRNESS)) {
+ spin_lock_bh(&local->active_txq_lock[ac]);
+ if (sta->airtime[ac].budget < info->control.airtime_est)
+ sta->airtime[ac].budget = 0;
+ else
+ sta->airtime[ac].budget -=
+ info->control.airtime_est;
+ spin_unlock_bh(&local->active_txq_lock[ac]);
+ }
+
/* mesh Peer Service Period support */
if (ieee80211_vif_is_mesh(&sta->sdata->vif) &&
ieee80211_is_data_qos(fc))
@@ -765,10 +783,6 @@ static void __ieee80211_tx_status(struct ieee80211_hw *hw,
& IEEE80211_SCTL_SEQ);
ieee80211_send_bar(&sta->sdata->vif, hdr->addr1,
tid, ssn);
- } else if (ieee80211_is_data_qos(fc)) {
- u8 *qc = ieee80211_get_qos_ctl(hdr);
-
- tid = qc[0] & 0xf;
}

if (!acked && ieee80211_is_back_req(fc)) {
diff --git a/net/mac80211/tx.c b/net/mac80211/tx.c
index e4bc43904a8e..c9997a63e5cf 100644
--- a/net/mac80211/tx.c
+++ b/net/mac80211/tx.c
@@ -3485,6 +3485,54 @@ static bool ieee80211_xmit_fast(struct ieee80211_sub_if_data *sdata,
return true;
}

+/* The estimated airtime (in microseconds), which is calculated using last
+ * reported TX rate is stored in info context buffer. The budget will be
+ * adjusted upon tx completion.
+ */
+#define IEEE80211_AIRTIME_BUDGET_MAX 4000 /* txq airtime limit: 4ms */
+#define IEEE80211_AIRTIME_OVERHEAD 100 /* IFS + some slot time */
+#define IEEE80211_AIRTIME_OVERHEAD_IFS 16 /* IFS only */
+static void ieee80211_calc_airtime_budget(struct ieee80211_local *local,
+ struct sta_info *sta,
+ struct sk_buff *skb, u8 ac)
+{
+ struct ieee80211_tx_info *info;
+ struct ieee80211_hdr *hdr;
+ struct rate_info rinfo;
+ u32 pktlen, bitrate;
+ u16 airtime = 0;
+
+ if (!wiphy_ext_feature_isset(local->hw.wiphy,
+ NL80211_EXT_FEATURE_AIRTIME_FAIRNESS))
+ return;
+
+ lockdep_assert_held(&local->active_txq_lock[ac]);
+
+ hdr = (struct ieee80211_hdr *)skb->data;
+ info = IEEE80211_SKB_CB(skb);
+
+ sta_set_rate_info_tx(sta, &sta->tx_stats.last_rate, &rinfo);
+ bitrate = cfg80211_calculate_bitrate(&rinfo);
+
+ pktlen = skb->len + 38; /* Assume MAC header 30, SNAP 8 for most case */
+ if (!is_multicast_ether_addr(hdr->addr1)) {
+ /* airtime in us, last tx bitrate in 100kbps */
+ airtime = (pktlen * 8 * (1000 / 100)) / bitrate;
+ airtime += IEEE80211_AIRTIME_OVERHEAD_IFS;
+ } else {
+ /* This is mostly for throttle excessive BC/MC frames, and the
+ * airtime/rate doesn't need be exact. Airtime of BC/MC frames
+ * in 2G get some discount, which helps prevent very low rate
+ * frames from being blocked for too long.
+ */
+ airtime = (pktlen * 8 * (1000 / 100)) / 60; /* 6M */
+ airtime += IEEE80211_AIRTIME_OVERHEAD;
+ }
+
+ info->control.airtime_est = airtime;
+ sta->airtime[ac].budget += airtime;
+}
+
struct sk_buff *ieee80211_tx_dequeue(struct ieee80211_hw *hw,
struct ieee80211_txq *txq)
{
@@ -3498,6 +3546,7 @@ struct sk_buff *ieee80211_tx_dequeue(struct ieee80211_hw *hw,
struct ieee80211_tx_data tx;
ieee80211_tx_result r;
struct ieee80211_vif *vif = txq->vif;
+ struct sta_info *sta = NULL;

spin_lock_bh(&fq->lock);

@@ -3510,6 +3559,12 @@ struct sk_buff *ieee80211_tx_dequeue(struct ieee80211_hw *hw,
goto out;
}

+ if (txq->sta) {
+ sta = container_of(txq->sta, struct sta_info, sta);
+ if (sta->airtime[txq->ac].budget > IEEE80211_AIRTIME_BUDGET_MAX)
+ goto out;
+ }
+
/* Make sure fragments stay together. */
skb = __skb_dequeue(&txqi->frags);
if (skb)
@@ -3529,8 +3584,7 @@ struct sk_buff *ieee80211_tx_dequeue(struct ieee80211_hw *hw,
tx.skb = skb;
tx.sdata = vif_to_sdata(info->control.vif);

- if (txq->sta)
- tx.sta = container_of(txq->sta, struct sta_info, sta);
+ tx.sta = sta;

/*
* The key can be removed while the packet was queued, so need to call
@@ -3542,6 +3596,9 @@ struct sk_buff *ieee80211_tx_dequeue(struct ieee80211_hw *hw,
goto begin;
}

+ if (sta)
+ ieee80211_calc_airtime_budget(local, sta, skb, txq->ac);
+
if (test_bit(IEEE80211_TXQ_AMPDU, &txqi->flags))
info->flags |= IEEE80211_TX_CTL_AMPDU;
else
--
1.9.1


2018-09-22 06:45:09

by Kan Yan

[permalink] [raw]
Subject: Re: [RFC v2] mac80211: budget outstanding airtime for transmission

Hi Rajkumar,

It is great to see your patches and thank you for helping bring this
to upstream.

> Why signed? This should never become negative unless something is wrong
> with the accounting somewhere?

It is signed because the "budget" is allowed to go negative. In the
original version, as long as the budget is > 0, at least one packet
is released even the budget is less than the airtime required for the
packet. One major issue I had when doing airtime based queue limit is
how to prevent txq with very low data rate (e.g., 6 mbps) from getting
stalled for too long. My solution is to allow budget to go negative
for one packet, then reset budget to 0 when all frames from that txq
has been completed and the inflight packets count reaches to 0.

For the ieee80211_calc_airtime_budget(), although it is sufficient for
the purpose of enforcing queue limit, the airtime overhead estimation
in the original patch really crude and could use some improvement.
Instead of using the last reported tx PHY rate and a guesstimate of
overhead to calculate airtime, one possible improvement is to
calculate the estimated "real" tx rate from a windowed moving average
of past tx_bytes/tx_airtime, if the firmware is capable of reporting
tx airtime for each completed PPDU.

2018-09-22 06:17:21

by Rajkumar Manoharan

[permalink] [raw]
Subject: Re: [RFC v2] mac80211: budget outstanding airtime for transmission

On 2018-09-21 04:13, Felix Fietkau wrote:
> On 2018-09-20 21:05, Rajkumar Manoharan wrote:
>> Per frame airtime estimation could be used to track outstanding
>> airtime
>> of each txq and can be used to throttle ieee80211_tx_dequeue(). This
>> mechanism on its own will get us the queue limiting and latency
>> reduction goodness for firmwares with deep queues. And for that it can
>> be completely independent of the airtime fairness scheduler, which can
>> use the after-tx-compl airtime information to presumably get more
>> accurate fairness which includes retransmissions etc.
> What about packets that get dequeued from the txq, but get freed by
> ieee80211_free_txskb?
> I think this may be a bit fragile, since if for any reason accounting
> isn't perfect here, tx queues might stall.
>
Good point. As Johannes mentioned, I will also handle free_txskb().

>> diff --git a/net/mac80211/tx.c b/net/mac80211/tx.c
>> index e4bc43904a8e..c9997a63e5cf 100644
>> --- a/net/mac80211/tx.c
>> +++ b/net/mac80211/tx.c
>> @@ -3485,6 +3485,54 @@ static bool ieee80211_xmit_fast(struct
>> ieee80211_sub_if_data *sdata,
>> return true;
>> }
>>
>> +/* The estimated airtime (in microseconds), which is calculated using
>> last
>> + * reported TX rate is stored in info context buffer. The budget will
>> be
>> + * adjusted upon tx completion.
>> + */
>> +#define IEEE80211_AIRTIME_BUDGET_MAX 4000 /* txq airtime limit:
>> 4ms */
>> +#define IEEE80211_AIRTIME_OVERHEAD 100 /* IFS + some slot time
>> */
>> +#define IEEE80211_AIRTIME_OVERHEAD_IFS 16 /* IFS only */
>> +static void ieee80211_calc_airtime_budget(struct ieee80211_local
>> *local,
>> + struct sta_info *sta,
>> + struct sk_buff *skb, u8 ac)
>> +{
>> + struct ieee80211_tx_info *info;
>> + struct ieee80211_hdr *hdr;
>> + struct rate_info rinfo;
>> + u32 pktlen, bitrate;
>> + u16 airtime = 0;
>> +
>> + if (!wiphy_ext_feature_isset(local->hw.wiphy,
>> + NL80211_EXT_FEATURE_AIRTIME_FAIRNESS))
>> + return;
>> +
>> + lockdep_assert_held(&local->active_txq_lock[ac]);
>> +
>> + hdr = (struct ieee80211_hdr *)skb->data;
>> + info = IEEE80211_SKB_CB(skb);
>> +
>> + sta_set_rate_info_tx(sta, &sta->tx_stats.last_rate, &rinfo);
>> + bitrate = cfg80211_calculate_bitrate(&rinfo);
> I think for drivers using software rate control, we should use the
> primary rate from the last rate_control_set_rates() call.
> In that case, we should calculate the bitrate value inside
> rate_control_set_rates itself in order to avoid re-calculating it for
> every single dequeued packet.
> It might make sense to use similar caching on changes to
> tx_stats.last_rate.
>
I thought of having common place for calculating bitrate for both
software based and offloaded rate control. let me explore caching
option.

-Rajkumar

2018-09-21 18:36:31

by Toke Høiland-Jørgensen

[permalink] [raw]
Subject: Re: [RFC v2] mac80211: budget outstanding airtime for transmission

Felix Fietkau <[email protected]> writes:

> On 2018-09-20 21:05, Rajkumar Manoharan wrote:
>> Per frame airtime estimation could be used to track outstanding airtime
>> of each txq and can be used to throttle ieee80211_tx_dequeue(). This
>> mechanism on its own will get us the queue limiting and latency
>> reduction goodness for firmwares with deep queues. And for that it can
>> be completely independent of the airtime fairness scheduler, which can
>> use the after-tx-compl airtime information to presumably get more
>> accurate fairness which includes retransmissions etc.
> What about packets that get dequeued from the txq, but get freed by
> ieee80211_free_txskb?
> I think this may be a bit fragile, since if for any reason accounting
> isn't perfect here, tx queues might stall.

Yeah, I worry about that as well. I guess we basically have three
avenues for fixing this?

1. Make sure packets are not freed after dequeue (probably not
feasible).

2. Add a mechanism to get queues unstuck if accounting does deviate (a
watchdog-type thing, or tie it to packet enqueue or something?).

3. Tie this back into the airtime fairness scheduler deficit, the same
way Kan's original patch did.


The problem with (3) is that we lose the ability to use a different
source of airtime usage information for the fairness scheduler (without
doing weird subtractions in the accounting). In particular, this would
mean we can't account for retransmissions. So I'd prefer (2), I think.

Anyone else with bright ideas? :)

-Toke

2018-09-21 17:02:17

by Felix Fietkau

[permalink] [raw]
Subject: Re: [RFC v2] mac80211: budget outstanding airtime for transmission

On 2018-09-20 21:05, Rajkumar Manoharan wrote:
> Per frame airtime estimation could be used to track outstanding airtime
> of each txq and can be used to throttle ieee80211_tx_dequeue(). This
> mechanism on its own will get us the queue limiting and latency
> reduction goodness for firmwares with deep queues. And for that it can
> be completely independent of the airtime fairness scheduler, which can
> use the after-tx-compl airtime information to presumably get more
> accurate fairness which includes retransmissions etc.
What about packets that get dequeued from the txq, but get freed by
ieee80211_free_txskb?
I think this may be a bit fragile, since if for any reason accounting
isn't perfect here, tx queues might stall.

> diff --git a/net/mac80211/tx.c b/net/mac80211/tx.c
> index e4bc43904a8e..c9997a63e5cf 100644
> --- a/net/mac80211/tx.c
> +++ b/net/mac80211/tx.c
> @@ -3485,6 +3485,54 @@ static bool ieee80211_xmit_fast(struct ieee80211_sub_if_data *sdata,
> return true;
> }
>
> +/* The estimated airtime (in microseconds), which is calculated using last
> + * reported TX rate is stored in info context buffer. The budget will be
> + * adjusted upon tx completion.
> + */
> +#define IEEE80211_AIRTIME_BUDGET_MAX 4000 /* txq airtime limit: 4ms */
> +#define IEEE80211_AIRTIME_OVERHEAD 100 /* IFS + some slot time */
> +#define IEEE80211_AIRTIME_OVERHEAD_IFS 16 /* IFS only */
> +static void ieee80211_calc_airtime_budget(struct ieee80211_local *local,
> + struct sta_info *sta,
> + struct sk_buff *skb, u8 ac)
> +{
> + struct ieee80211_tx_info *info;
> + struct ieee80211_hdr *hdr;
> + struct rate_info rinfo;
> + u32 pktlen, bitrate;
> + u16 airtime = 0;
> +
> + if (!wiphy_ext_feature_isset(local->hw.wiphy,
> + NL80211_EXT_FEATURE_AIRTIME_FAIRNESS))
> + return;
> +
> + lockdep_assert_held(&local->active_txq_lock[ac]);
> +
> + hdr = (struct ieee80211_hdr *)skb->data;
> + info = IEEE80211_SKB_CB(skb);
> +
> + sta_set_rate_info_tx(sta, &sta->tx_stats.last_rate, &rinfo);
> + bitrate = cfg80211_calculate_bitrate(&rinfo);
I think for drivers using software rate control, we should use the
primary rate from the last rate_control_set_rates() call.
In that case, we should calculate the bitrate value inside
rate_control_set_rates itself in order to avoid re-calculating it for
every single dequeued packet.
It might make sense to use similar caching on changes to
tx_stats.last_rate.

- Felix

2018-09-21 20:01:11

by Johannes Berg

[permalink] [raw]
Subject: Re: [RFC v2] mac80211: budget outstanding airtime for transmission


> 1. Make sure packets are not freed after dequeue (probably not
> feasible).

We already require you free via mac80211 after TX, so could tie into
that for adjustment?

johannes