mac80211: minstrel: remove divisions in tx status path
PATCH v2 1/3 mac80211: minstrel: remove divisions in tx status path
Use a slightly different threshold for downgrading spatial streams to make it easier to calculate without divisions.
Slightly reduces CPU overhead.
--- net/mac80211/rc80211_minstrel.c | 3 +-- net/mac80211/rc80211_minstrel_ht.c | 10 ++++------ 2 files changed, 5 insertions(+), 8 deletions(-)
net/mac80211/rc80211_minstrel.c +1 -2
@@ -289,8 +289,7 @@ minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband,if (mi->sample_deferred >0 ) mi->sample_deferred--; -if (time_after (jiffies, mi->last_stats_update + - (mp->update_interval *HZ ) /1000 )) +if (time_after (jiffies, mi->last_stats_update + mp->update_interval))minstrel_update_stats (mp, mi); }
net/mac80211/rc80211_minstrel_ht.c +4 -6
@@ -970,23 +970,21 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,*/ rate =minstrel_get_ratestats (mi, mi->max_tp_rate[0 ]);if (rate->attempts >30 && -MINSTREL_FRAC (rate->success, rate->attempts) < -MINSTREL_FRAC (20 ,100 )) { + rate->success < rate->attempts /4 ) {minstrel_downgrade_rate (mi, &mi->max_tp_rate[0 ], true); update = true; } rate2 =minstrel_get_ratestats (mi, mi->max_tp_rate[1 ]);if (rate2->attempts >30 && -MINSTREL_FRAC (rate2->success, rate2->attempts) < -MINSTREL_FRAC (20 ,100 )) { + rate2->success < rate2->attempts /4 ) {minstrel_downgrade_rate (mi, &mi->max_tp_rate[1 ], false); update = true; } }if (time_after (jiffies, mi->last_stats_update + - (mp->update_interval /2 *HZ ) /1000 )) { + mp->update_interval /2 )) { update = true;minstrel_ht_update_stats (mp, mi, true); }
@@ -1666,7 +1664,7 @@ minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir) mp->has_mrr = true; mp->hw = hw; - mp->update_interval =100 ; + mp->update_interval =HZ /10 ;#ifdef CONFIG_MAC80211_DEBUGFS mp->fixed_rate_idx = (u32) -1 ;
Signature · 1 line
2.17.0
PATCH v2 2/3 mac80211: minstrel_ht: replace rate stats ewma with a better moving average
Rate success probability usually fluctuates a lot under normal conditions. With a simple EWMA, noise and fluctuation can be reduced by increasing the window length, but that comes at the cost of introducing lag on sudden changes.
This change replaces the EWMA implementation with a moving average that's designed to significantly reduce lag while keeping a bigger window size by being better at filtering out noise.
It is only slightly more expensive than the simple EWMA and still avoids divisions in its calculation.
The algorithm is adapted from an implementation intended for a completely different field (stock market trading), where the tradeoff of lag vs noise filtering is equally important. It is based on the "smoothing filter" from http://www.stockspotter.com/files/PredictiveIndicators.pdf.
I have adapted it to fixed-point math with some constants so that it uses only addition, bit shifts and multiplication
To better make use of the filtering and bigger window size, the update interval time is cut in half.
For testing, the algorithm can be reverted to the older one via debugfs
---
v2:
- remove in_1 (previous input value) from the context struct the (in + in_1)/2 average was only adding some very slight smoothing to the resulting average, which is not needed here
- remove coeff1 value, it is equal to 1 - coeff2 - coeff3
- reduce the number of bitshift operations to make the code a tiny bit more efficient
net/mac80211/rc80211_minstrel.c | 13 ++++--- net/mac80211/rc80211_minstrel.h | 56 +++++++++++++++++++++++++++++- net/mac80211/rc80211_minstrel_ht.c | 15 ++++++-- 3 files changed, 76 insertions(+), 8 deletions(-)
net/mac80211/rc80211_minstrel.c +9 -4
@@ -157,14 +157,18 @@ minstrel_update_rates(struct minstrel_priv *mp, struct minstrel_sta_info *mi)* Recalculate statistics and counters of a given rate */ void -minstrel_calc_rate_stats (struct minstrel_rate_stats *mrs) +minstrel_calc_rate_stats (struct minstrel_priv *mp, +struct minstrel_rate_stats *mrs) {unsigned int cur_prob;if (unlikely (mrs->attempts >0 )) { mrs->sample_skipped =0 ; cur_prob =MINSTREL_FRAC (mrs->success, mrs->attempts); -if (unlikely (!mrs->att_hist)) { +if (mp->new_avg) { + mrs->prob_ewma =minstrel_filter_avg_add (&mrs->avg, + cur_prob); + }else if (unlikely (!mrs->att_hist)) { mrs->prob_ewma = cur_prob; }else {/*update exponential weighted moving avarage */
@@ -200,7 +204,7 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)struct minstrel_rate_stats *tmp_mrs = &mi->r[tmp_prob_rate].stats;/* Update statistics of success probability per rate */ -minstrel_calc_rate_stats (mrs); +minstrel_calc_rate_stats (mp, mrs);/* Sample less often below the 10% chance of success. * Sample less often above the 95% chance of success. */
@@ -289,7 +293,8 @@ minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband,if (mi->sample_deferred >0 ) mi->sample_deferred--; -if (time_after (jiffies, mi->last_stats_update + mp->update_interval)) +if (time_after (jiffies, mi->last_stats_update + + mp->update_interval / (mp->new_avg ?2 :1 )))minstrel_update_stats (mp, mi); }
net/mac80211/rc80211_minstrel.h +55 -1
86 lines not on this page · raw message
net/mac80211/rc80211_minstrel_ht.c +12 -3
@@ -737,7 +737,7 @@ minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi, mrs = &mg->rates[i]; mrs->retry_updated = false; -minstrel_calc_rate_stats (mrs); +minstrel_calc_rate_stats (mp, mrs); cur_prob = mrs->prob_ewma;if (minstrel_ht_get_tp_avg (mi, group, i, cur_prob) ==0 )
@@ -773,6 +773,8 @@ minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,/* try to sample all available rates during each interval */ mi->sample_count *=8 ; +if (mp->new_avg) + mi->sample_count /=2 ;if (sample)minstrel_ht_rate_sample_switch (mp, mi);
@@ -889,6 +891,7 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,struct ieee80211_tx_rate *ar = info->status.rates;struct minstrel_rate_stats *rate, *rate2, *rate_sample =NULL ;struct minstrel_priv *mp = priv; +u32 update_interval = mp->update_interval /2 ;bool last, update = false;bool sample_status = false;int i;
@@ -943,6 +946,10 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,switch (mi->sample_mode) {case MINSTREL_SAMPLE_IDLE : +if (mp->new_avg && + (mp->hw->max_rates >1 || + mi->total_packets_cur <SAMPLE_SWITCH_THR )) + update_interval /=2 ;break ;case MINSTREL_SAMPLE_ACTIVE :
@@ -983,8 +990,7 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband, } } -if (time_after (jiffies, mi->last_stats_update + - mp->update_interval /2 )) { +if (time_after (jiffies, mi->last_stats_update + update_interval)) { update = true;minstrel_ht_update_stats (mp, mi, true); }
@@ -1665,6 +1671,7 @@ minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir) mp->hw = hw; mp->update_interval =HZ /10 ; + mp->new_avg = true;#ifdef CONFIG_MAC80211_DEBUGFS mp->fixed_rate_idx = (u32) -1 ;
@@ -1672,6 +1679,8 @@ minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir) &mp->fixed_rate_idx);debugfs_create_u32 ("sample_switch" ,S_IRUGO |S_IWUSR , debugfsdir, &mp->sample_switch); +debugfs_create_bool ("new_avg" ,S_IRUGO |S_IWUSR , debugfsdir, + &mp->new_avg);#endif minstrel_ht_init_cck_rates (mp);
Signature · 1 line
2.17.0
PATCH v2 3/3 mac80211: minstrel_ht: rename prob_ewma to prob_avg, use it for the new average
In reply to Felix FietkauReduces per-rate data structure size
--- net/mac80211/rc80211_minstrel.c | 40 ++++++++--------- net/mac80211/rc80211_minstrel.h | 23 ++++------ net/mac80211/rc80211_minstrel_debugfs.c | 8 ++-- net/mac80211/rc80211_minstrel_ht.c | 50 +++++++++++----------- net/mac80211/rc80211_minstrel_ht.h | 2 +- net/mac80211/rc80211_minstrel_ht_debugfs.c | 8 ++-- 6 files changed, 63 insertions(+), 68 deletions(-)
net/mac80211/rc80211_minstrel.c +20 -20
@@ -70,7 +70,7 @@ rix_to_ndx(struct minstrel_sta_info *mi, int rix) }/* return current EMWA throughput */ -int minstrel_get_tp_avg (struct minstrel_rate *mr,int prob_ewma) +int minstrel_get_tp_avg (struct minstrel_rate *mr,int prob_avg) {int usecs;
@@ -79,13 +79,13 @@ int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_ewma) usecs =1000000 ;/* reset thr. below 10% success */ -if (mr->stats.prob_ewma <MINSTREL_FRAC (10 ,100 )) +if (mr->stats.prob_avg <MINSTREL_FRAC (10 ,100 ))return 0 ; -if (prob_ewma >MINSTREL_FRAC (90 ,100 )) +if (prob_avg >MINSTREL_FRAC (90 ,100 ))return MINSTREL_TRUNC (100000 * (MINSTREL_FRAC (90 ,100 ) / usecs));else -return MINSTREL_TRUNC (100000 * (prob_ewma / usecs)); +return MINSTREL_TRUNC (100000 * (prob_avg / usecs)); }/* find & sort topmost throughput rates */
@@ -98,8 +98,8 @@ minstrel_sort_best_tp_rates(struct minstrel_sta_info *mi, int i, u8 *tp_list)for (j =MAX_THR_RATES ; j >0 ; --j) { tmp_mrs = &mi->r[tp_list[j -1 ]].stats; -if (minstrel_get_tp_avg (&mi->r[i], cur_mrs->prob_ewma) <= -minstrel_get_tp_avg (&mi->r[tp_list[j -1 ]], tmp_mrs->prob_ewma)) +if (minstrel_get_tp_avg (&mi->r[i], cur_mrs->prob_avg) <= +minstrel_get_tp_avg (&mi->r[tp_list[j -1 ]], tmp_mrs->prob_avg))break ; }
@@ -166,15 +166,15 @@ minstrel_calc_rate_stats(struct minstrel_priv *mp, mrs->sample_skipped =0 ; cur_prob =MINSTREL_FRAC (mrs->success, mrs->attempts);if (mp->new_avg) { - mrs->prob_ewma =minstrel_filter_avg_add (&mrs->avg, - cur_prob); +minstrel_filter_avg_add (&mrs->prob_avg, + &mrs->prob_avg_1, cur_prob); }else if (unlikely (!mrs->att_hist)) { - mrs->prob_ewma = cur_prob; + mrs->prob_avg = cur_prob; }else {/*update exponential weighted moving avarage */ - mrs->prob_ewma =minstrel_ewma (mrs->prob_ewma, - cur_prob, -EWMA_LEVEL ); + mrs->prob_avg =minstrel_ewma (mrs->prob_avg, + cur_prob, +EWMA_LEVEL ); } mrs->att_hist += mrs->attempts; mrs->succ_hist += mrs->success;
@@ -208,8 +208,8 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)/* Sample less often below the 10% chance of success. * Sample less often above the 95% chance of success. */ -if (mrs->prob_ewma >MINSTREL_FRAC (95 ,100 ) || - mrs->prob_ewma <MINSTREL_FRAC (10 ,100 )) { +if (mrs->prob_avg >MINSTREL_FRAC (95 ,100 ) || + mrs->prob_avg <MINSTREL_FRAC (10 ,100 )) { mr->adjusted_retry_count = mrs->retry_count >>1 ;if (mr->adjusted_retry_count >2 ) mr->adjusted_retry_count =2 ;
@@ -229,14 +229,14 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)* choose the maximum throughput rate as max_prob_rate * (2) if all success probabilities < 95%, the rate with * highest success probability is chosen as max_prob_rate */ -if (mrs->prob_ewma >=MINSTREL_FRAC (95 ,100 )) { - tmp_cur_tp =minstrel_get_tp_avg (mr, mrs->prob_ewma); +if (mrs->prob_avg >=MINSTREL_FRAC (95 ,100 )) { + tmp_cur_tp =minstrel_get_tp_avg (mr, mrs->prob_avg); tmp_prob_tp =minstrel_get_tp_avg (&mi->r[tmp_prob_rate], - tmp_mrs->prob_ewma); + tmp_mrs->prob_avg);if (tmp_cur_tp >= tmp_prob_tp) tmp_prob_rate = i; }else { -if (mrs->prob_ewma >= tmp_mrs->prob_ewma) +if (mrs->prob_avg >= tmp_mrs->prob_avg) tmp_prob_rate = i; } }
@@ -426,7 +426,7 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,* has a probability of >95%, we shouldn't be attempting * to use it, as this only wastes precious airtime */ if (!mrr_capable && - (mi->r[ndx].stats.prob_ewma >MINSTREL_FRAC (95 ,100 ))) + (mi->r[ndx].stats.prob_avg >MINSTREL_FRAC (95 ,100 )))return ; mi->prev_sample = true;
@@ -577,7 +577,7 @@ static u32 minstrel_get_expected_throughput(void *priv_sta)* computing cur_tp */ tmp_mrs = &mi->r[idx].stats; - tmp_cur_tp =minstrel_get_tp_avg (&mi->r[idx], tmp_mrs->prob_ewma) *10 ; + tmp_cur_tp =minstrel_get_tp_avg (&mi->r[idx], tmp_mrs->prob_avg) *10 ; tmp_cur_tp = tmp_cur_tp *1200 *8 /1024 ;return tmp_cur_tp;
net/mac80211/rc80211_minstrel.h +9 -14
@@ -47,14 +47,10 @@ minstrel_ewma(int old, int new, int weight)return old + incr; } -struct minstrel_avg_ctx { -s32 prev[2 ]; -}; - -static inline int minstrel_filter_avg_add (struct minstrel_avg_ctx *ctx,s32 in) +static inline int minstrel_filter_avg_add (u16 *prev_1,u16 *prev_2,s32 in) { -s32 out_1 = ctx->prev[0 ]; -s32 out_2 = ctx->prev[1 ]; +s32 out_1 = *prev_1; +s32 out_2 = *prev_2;s32 val;if (!in)
@@ -76,8 +72,8 @@ static inline int minstrel_filter_avg_add(struct minstrel_avg_ctx *ctx, s32 in) val =1 ; out: - ctx->prev[1 ] = out_1; - ctx->prev[0 ] = val; + *prev_2 = out_1; + *prev_1 = val;return val; }
@@ -90,10 +86,9 @@ struct minstrel_rate_stats {/* total attempts/success counters */ u32 att_hist, succ_hist; -struct minstrel_avg_ctx avg; - -/* prob_ewma - exponential weighted moving average of prob */ -u16 prob_ewma; +/* prob_avg - moving average of prob */ +u16 prob_avg; +u16 prob_avg_1;/* maximum retry counts */ u8 retry_count;
@@ -181,7 +176,7 @@ void minstrel_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);/* Recalculate success probabilities and counters for a given rate using EWMA */ void minstrel_calc_rate_stats (struct minstrel_priv *mp,struct minstrel_rate_stats *mrs); -int minstrel_get_tp_avg (struct minstrel_rate *mr,int prob_ewma); +int minstrel_get_tp_avg (struct minstrel_rate *mr,int prob_avg);/* debugfs */ int minstrel_stats_open (struct inode *inode,struct file *file);
net/mac80211/rc80211_minstrel_debugfs.c +4 -4
@@ -90,8 +90,8 @@ minstrel_stats_open(struct inode *inode, struct file *file) p +=sprintf (p,"%6u " , mr->perfect_tx_time); tp_max =minstrel_get_tp_avg (mr,MINSTREL_FRAC (100 ,100 )); - tp_avg =minstrel_get_tp_avg (mr, mrs->prob_ewma); - eprob =MINSTREL_TRUNC (mrs->prob_ewma *1000 ); + tp_avg =minstrel_get_tp_avg (mr, mrs->prob_avg); + eprob =MINSTREL_TRUNC (mrs->prob_avg *1000 ); p +=sprintf (p,"%4u.%1u %4u.%1u %3u.%1u" " %3u %3u %-3u "
@@ -147,8 +147,8 @@ minstrel_stats_csv_open(struct inode *inode, struct file *file) p +=sprintf (p,"%u," ,mr->perfect_tx_time); tp_max =minstrel_get_tp_avg (mr,MINSTREL_FRAC (100 ,100 )); - tp_avg =minstrel_get_tp_avg (mr, mrs->prob_ewma); - eprob =MINSTREL_TRUNC (mrs->prob_ewma *1000 ); + tp_avg =minstrel_get_tp_avg (mr, mrs->prob_avg); + eprob =MINSTREL_TRUNC (mrs->prob_avg *1000 ); p += sprintf(p, "%u.%u,%u.%u,%u.%u,%u,%u,%u," "%llu,%llu,%d,%d\n",
net/mac80211/rc80211_minstrel_ht.c +25 -25
174 lines not on this page · raw message
net/mac80211/rc80211_minstrel_ht.h +1 -1
@@ -119,6 +119,6 @@ struct minstrel_ht_sta_priv {void minstrel_ht_add_sta_debugfs (void *priv,void *priv_sta,struct dentry *dir);int minstrel_ht_get_tp_avg (struct minstrel_ht_sta *mi,int group,int rate, -int prob_ewma); +int prob_avg);#endif
net/mac80211/rc80211_minstrel_ht_debugfs.c +4 -4
@@ -98,8 +98,8 @@ minstrel_ht_stats_dump(struct minstrel_ht_sta *mi, int i, char *p) p +=sprintf (p,"%6u " , tx_time); tp_max =minstrel_ht_get_tp_avg (mi, i, j,MINSTREL_FRAC (100 ,100 )); - tp_avg =minstrel_ht_get_tp_avg (mi, i, j, mrs->prob_ewma); - eprob =MINSTREL_TRUNC (mrs->prob_ewma *1000 ); + tp_avg =minstrel_ht_get_tp_avg (mi, i, j, mrs->prob_avg); + eprob =MINSTREL_TRUNC (mrs->prob_avg *1000 ); p +=sprintf (p,"%4u.%1u %4u.%1u %3u.%1u" " %3u %3u %-3u "
@@ -243,8 +243,8 @@ minstrel_ht_stats_csv_dump(struct minstrel_ht_sta *mi, int i, char *p) p +=sprintf (p,"%u," , tx_time); tp_max =minstrel_ht_get_tp_avg (mi, i, j,MINSTREL_FRAC (100 ,100 )); - tp_avg =minstrel_ht_get_tp_avg (mi, i, j, mrs->prob_ewma); - eprob =MINSTREL_TRUNC (mrs->prob_ewma *1000 ); + tp_avg =minstrel_ht_get_tp_avg (mi, i, j, mrs->prob_avg); + eprob =MINSTREL_TRUNC (mrs->prob_avg *1000 ); p += sprintf(p, "%u.%u,%u.%u,%u.%u,%u,%u," "%u,%llu,%llu,",
Signature · 1 line
2.17.0