projects / openwrt / staging / luka.git / blob
? search:


78e8527a5c9000af54406960b0fa67e1bd2ca600
[openwrt/staging/luka.git] /
1 From: Felix Fietkau <nbd@nbd.name>
2 Date: Sat, 28 Sep 2019 15:46:06 +0200
3 Subject: [PATCH] mac80211: minstrel_ht: replace rate stats ewma with a
4 better moving average
5
6 Rate success probability usually fluctuates a lot under normal conditions.
7 With a simple EWMA, noise and fluctuation can be reduced by increasing the
8 window length, but that comes at the cost of introducing lag on sudden
9 changes.
10
11 This change replaces the EWMA implementation with a moving average that's
12 designed to significantly reduce lag while keeping a bigger window size
13 by being better at filtering out noise.
14
15 It is only slightly more expensive than the simple EWMA and still avoids
16 divisions in its calculation.
17
18 The algorithm is adapted from an implementation intended for a completely
19 different field (stock market trading), where the tradeoff of lag vs
20 noise filtering is equally important.
21
22 The algorithm works in the same way as the "smoothing filter" from
23 http://www.stockspotter.com/files/PredictiveIndicators.pdf adapted for
24 fixed-point math with some constants, using only addition, bit shifts
25 and multiplication
26
27 To better make use of the filtering and bigger window size, the update
28 interval is cut in half.
29
30 For testing, the algorithm can be reverted to the older one via debugfs
31
32 Signed-off-by: Felix Fietkau <nbd@nbd.name>
33 ---
34
35 --- a/net/mac80211/rc80211_minstrel.c
36 +++ b/net/mac80211/rc80211_minstrel.c
37 @@ -157,14 +157,18 @@ minstrel_update_rates(struct minstrel_pr
38 * Recalculate statistics and counters of a given rate
39 */
40 void
41 -minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs)
42 +minstrel_calc_rate_stats(struct minstrel_priv *mp,
43 + struct minstrel_rate_stats *mrs)
44 {
45 unsigned int cur_prob;
46
47 if (unlikely(mrs->attempts > 0)) {
48 mrs->sample_skipped = 0;
49 cur_prob = MINSTREL_FRAC(mrs->success, mrs->attempts);
50 - if (unlikely(!mrs->att_hist)) {
51 + if (mp->new_avg) {
52 + mrs->prob_ewma = minstrel_filter_avg_add(&mrs->avg,
53 + cur_prob);
54 + } else if (unlikely(!mrs->att_hist)) {
55 mrs->prob_ewma = cur_prob;
56 } else {
57 /*update exponential weighted moving avarage */
58 @@ -200,7 +204,7 @@ minstrel_update_stats(struct minstrel_pr
59 struct minstrel_rate_stats *tmp_mrs = &mi->r[tmp_prob_rate].stats;
60
61 /* Update statistics of success probability per rate */
62 - minstrel_calc_rate_stats(mrs);
63 + minstrel_calc_rate_stats(mp, mrs);
64
65 /* Sample less often below the 10% chance of success.
66 * Sample less often above the 95% chance of success. */
67 @@ -289,7 +293,8 @@ minstrel_tx_status(void *priv, struct ie
68 if (mi->sample_deferred > 0)
69 mi->sample_deferred--;
70
71 - if (time_after(jiffies, mi->last_stats_update + mp->update_interval))
72 + if (time_after(jiffies, mi->last_stats_update +
73 + mp->update_interval / (mp->new_avg ? 2 : 1)))
74 minstrel_update_stats(mp, mi);
75 }
76
77 --- a/net/mac80211/rc80211_minstrel.h
78 +++ b/net/mac80211/rc80211_minstrel.h
79 @@ -19,6 +19,21 @@
80 #define MAX_THR_RATES 4
81
82 /*
83 + * Coefficients for moving average with noise filter (period=16),
84 + * scaled by 10 bits
85 + *
86 + * a1 = exp(-pi * sqrt(2) / period)
87 + * coeff2 = 2 * a1 * cos(sqrt(2) * 2 * pi / period)
88 + * coeff3 = -sqr(a1)
89 + * coeff1 = 1 - coeff2 - coeff3
90 + */
91 +#define MINSTREL_AVG_COEFF1 (MINSTREL_FRAC(1, 1) - \
92 + MINSTREL_AVG_COEFF2 - \
93 + MINSTREL_AVG_COEFF3)
94 +#define MINSTREL_AVG_COEFF2 0x00001499
95 +#define MINSTREL_AVG_COEFF3 -0x0000092e
96 +
97 +/*
98 * Perform EWMA (Exponentially Weighted Moving Average) calculation
99 */
100 static inline int
101 @@ -32,6 +47,41 @@ minstrel_ewma(int old, int new, int weig
102 return old + incr;
103 }
104
105 +struct minstrel_avg_ctx {
106 + s32 prev[2];
107 +};
108 +
109 +static inline int minstrel_filter_avg_add(struct minstrel_avg_ctx *ctx, s32 in)
110 +{
111 + s32 out_1 = ctx->prev[0];
112 + s32 out_2 = ctx->prev[1];
113 + s32 val;
114 +
115 + if (!in)
116 + in += 1;
117 +
118 + if (!out_1) {
119 + val = out_1 = in;
120 + goto out;
121 + }
122 +
123 + val = MINSTREL_AVG_COEFF1 * in;
124 + val += MINSTREL_AVG_COEFF2 * out_1;
125 + val += MINSTREL_AVG_COEFF3 * out_2;
126 + val >>= MINSTREL_SCALE;
127 +
128 + if (val > 1 << MINSTREL_SCALE)
129 + val = 1 << MINSTREL_SCALE;
130 + if (val < 0)
131 + val = 1;
132 +
133 +out:
134 + ctx->prev[1] = out_1;
135 + ctx->prev[0] = val;
136 +
137 + return val;
138 +}
139 +
140 struct minstrel_rate_stats {
141 /* current / last sampling period attempts/success counters */
142 u16 attempts, last_attempts;
143 @@ -40,6 +90,8 @@ struct minstrel_rate_stats {
144 /* total attempts/success counters */
145 u32 att_hist, succ_hist;
146
147 + struct minstrel_avg_ctx avg;
148 +
149 /* prob_ewma - exponential weighted moving average of prob */
150 u16 prob_ewma;
151
152 @@ -95,6 +147,7 @@ struct minstrel_sta_info {
153 struct minstrel_priv {
154 struct ieee80211_hw *hw;
155 bool has_mrr;
156 + bool new_avg;
157 u32 sample_switch;
158 unsigned int cw_min;
159 unsigned int cw_max;
160 @@ -126,7 +179,8 @@ extern const struct rate_control_ops mac
161 void minstrel_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);
162
163 /* Recalculate success probabilities and counters for a given rate using EWMA */
164 -void minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs);
165 +void minstrel_calc_rate_stats(struct minstrel_priv *mp,
166 + struct minstrel_rate_stats *mrs);
167 int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_ewma);
168
169 /* debugfs */
170 --- a/net/mac80211/rc80211_minstrel_ht.c
171 +++ b/net/mac80211/rc80211_minstrel_ht.c
172 @@ -737,7 +737,7 @@ minstrel_ht_update_stats(struct minstrel
173
174 mrs = &mg->rates[i];
175 mrs->retry_updated = false;
176 - minstrel_calc_rate_stats(mrs);
177 + minstrel_calc_rate_stats(mp, mrs);
178 cur_prob = mrs->prob_ewma;
179
180 if (minstrel_ht_get_tp_avg(mi, group, i, cur_prob) == 0)
181 @@ -773,6 +773,8 @@ minstrel_ht_update_stats(struct minstrel
182
183 /* try to sample all available rates during each interval */
184 mi->sample_count *= 8;
185 + if (mp->new_avg)
186 + mi->sample_count /= 2;
187
188 if (sample)
189 minstrel_ht_rate_sample_switch(mp, mi);
190 @@ -889,6 +891,7 @@ minstrel_ht_tx_status(void *priv, struct
191 struct ieee80211_tx_rate *ar = info->status.rates;
192 struct minstrel_rate_stats *rate, *rate2, *rate_sample = NULL;
193 struct minstrel_priv *mp = priv;
194 + u32 update_interval = mp->update_interval / 2;
195 bool last, update = false;
196 bool sample_status = false;
197 int i;
198 @@ -943,6 +946,10 @@ minstrel_ht_tx_status(void *priv, struct
199
200 switch (mi->sample_mode) {
201 case MINSTREL_SAMPLE_IDLE:
202 + if (mp->new_avg &&
203 + (mp->hw->max_rates > 1 ||
204 + mi->total_packets_cur < SAMPLE_SWITCH_THR))
205 + update_interval /= 2;
206 break;
207
208 case MINSTREL_SAMPLE_ACTIVE:
209 @@ -983,8 +990,7 @@ minstrel_ht_tx_status(void *priv, struct
210 }
211 }
212
213 - if (time_after(jiffies, mi->last_stats_update +
214 - mp->update_interval / 2)) {
215 + if (time_after(jiffies, mi->last_stats_update + update_interval)) {
216 update = true;
217 minstrel_ht_update_stats(mp, mi, true);
218 }
219 @@ -1665,6 +1671,7 @@ minstrel_ht_alloc(struct ieee80211_hw *h
220
221 mp->hw = hw;
222 mp->update_interval = HZ / 10;
223 + mp->new_avg = true;
224
225 minstrel_ht_init_cck_rates(mp);
226
227 @@ -1682,6 +1689,8 @@ static void minstrel_ht_add_debugfs(stru
228 &mp->fixed_rate_idx);
229 debugfs_create_u32("sample_switch", S_IRUGO | S_IWUSR, debugfsdir,
230 &mp->sample_switch);
231 + debugfs_create_bool("new_avg", S_IRUGO | S_IWUSR, debugfsdir,
232 + &mp->new_avg);
233 }
234 #endif
235
tree of Luka Perkov resides here