mac80211: add an improved moving average algorithm to minstrel
[openwrt/openwrt.git] / package / kernel / mac80211 / patches / subsys / 364-mac80211-minstrel_ht-rename-prob_ewma-to-prob_avg-us.patch
1 From: Felix Fietkau <nbd@nbd.name>
2 Date: Tue, 8 Oct 2019 18:54:46 +0200
3 Subject: [PATCH] mac80211: minstrel_ht: rename prob_ewma to prob_avg, use it
4 for the new average
5
6 Reduces per-rate data structure size
7
8 Signed-off-by: Felix Fietkau <nbd@nbd.name>
9 ---
10
11 --- a/net/mac80211/rc80211_minstrel.c
12 +++ b/net/mac80211/rc80211_minstrel.c
13 @@ -70,7 +70,7 @@ rix_to_ndx(struct minstrel_sta_info *mi,
14 }
15
16 /* return current EMWA throughput */
17 -int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_ewma)
18 +int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_avg)
19 {
20 int usecs;
21
22 @@ -79,13 +79,13 @@ int minstrel_get_tp_avg(struct minstrel_
23 usecs = 1000000;
24
25 /* reset thr. below 10% success */
26 - if (mr->stats.prob_ewma < MINSTREL_FRAC(10, 100))
27 + if (mr->stats.prob_avg < MINSTREL_FRAC(10, 100))
28 return 0;
29
30 - if (prob_ewma > MINSTREL_FRAC(90, 100))
31 + if (prob_avg > MINSTREL_FRAC(90, 100))
32 return MINSTREL_TRUNC(100000 * (MINSTREL_FRAC(90, 100) / usecs));
33 else
34 - return MINSTREL_TRUNC(100000 * (prob_ewma / usecs));
35 + return MINSTREL_TRUNC(100000 * (prob_avg / usecs));
36 }
37
38 /* find & sort topmost throughput rates */
39 @@ -98,8 +98,8 @@ minstrel_sort_best_tp_rates(struct minst
40
41 for (j = MAX_THR_RATES; j > 0; --j) {
42 tmp_mrs = &mi->r[tp_list[j - 1]].stats;
43 - if (minstrel_get_tp_avg(&mi->r[i], cur_mrs->prob_ewma) <=
44 - minstrel_get_tp_avg(&mi->r[tp_list[j - 1]], tmp_mrs->prob_ewma))
45 + if (minstrel_get_tp_avg(&mi->r[i], cur_mrs->prob_avg) <=
46 + minstrel_get_tp_avg(&mi->r[tp_list[j - 1]], tmp_mrs->prob_avg))
47 break;
48 }
49
50 @@ -166,21 +166,21 @@ minstrel_calc_rate_stats(struct minstrel
51 mrs->sample_skipped = 0;
52 cur_prob = MINSTREL_FRAC(mrs->success, mrs->attempts);
53 if (mp->new_avg) {
54 - mrs->prob_ewma = minstrel_filter_avg_add(&mrs->avg,
55 - cur_prob);
56 + minstrel_filter_avg_add(&mrs->prob_avg,
57 + &mrs->prob_avg_1, cur_prob);
58 } else if (unlikely(!mrs->att_hist)) {
59 - mrs->prob_ewma = cur_prob;
60 + mrs->prob_avg = cur_prob;
61 } else {
62 /* update exponential weighted moving variance */
63 mrs->prob_ewmv = minstrel_ewmv(mrs->prob_ewmv,
64 cur_prob,
65 - mrs->prob_ewma,
66 + mrs->prob_avg,
67 EWMA_LEVEL);
68
69 /*update exponential weighted moving avarage */
70 - mrs->prob_ewma = minstrel_ewma(mrs->prob_ewma,
71 - cur_prob,
72 - EWMA_LEVEL);
73 + mrs->prob_avg = minstrel_ewma(mrs->prob_avg,
74 + cur_prob,
75 + EWMA_LEVEL);
76 }
77 mrs->att_hist += mrs->attempts;
78 mrs->succ_hist += mrs->success;
79 @@ -214,8 +214,8 @@ minstrel_update_stats(struct minstrel_pr
80
81 /* Sample less often below the 10% chance of success.
82 * Sample less often above the 95% chance of success. */
83 - if (mrs->prob_ewma > MINSTREL_FRAC(95, 100) ||
84 - mrs->prob_ewma < MINSTREL_FRAC(10, 100)) {
85 + if (mrs->prob_avg > MINSTREL_FRAC(95, 100) ||
86 + mrs->prob_avg < MINSTREL_FRAC(10, 100)) {
87 mr->adjusted_retry_count = mrs->retry_count >> 1;
88 if (mr->adjusted_retry_count > 2)
89 mr->adjusted_retry_count = 2;
90 @@ -235,14 +235,14 @@ minstrel_update_stats(struct minstrel_pr
91 * choose the maximum throughput rate as max_prob_rate
92 * (2) if all success probabilities < 95%, the rate with
93 * highest success probability is chosen as max_prob_rate */
94 - if (mrs->prob_ewma >= MINSTREL_FRAC(95, 100)) {
95 - tmp_cur_tp = minstrel_get_tp_avg(mr, mrs->prob_ewma);
96 + if (mrs->prob_avg >= MINSTREL_FRAC(95, 100)) {
97 + tmp_cur_tp = minstrel_get_tp_avg(mr, mrs->prob_avg);
98 tmp_prob_tp = minstrel_get_tp_avg(&mi->r[tmp_prob_rate],
99 - tmp_mrs->prob_ewma);
100 + tmp_mrs->prob_avg);
101 if (tmp_cur_tp >= tmp_prob_tp)
102 tmp_prob_rate = i;
103 } else {
104 - if (mrs->prob_ewma >= tmp_mrs->prob_ewma)
105 + if (mrs->prob_avg >= tmp_mrs->prob_avg)
106 tmp_prob_rate = i;
107 }
108 }
109 @@ -436,7 +436,7 @@ minstrel_get_rate(void *priv, struct iee
110 * has a probability of >95%, we shouldn't be attempting
111 * to use it, as this only wastes precious airtime */
112 if (!mrr_capable &&
113 - (mi->r[ndx].stats.prob_ewma > MINSTREL_FRAC(95, 100)))
114 + (mi->r[ndx].stats.prob_avg > MINSTREL_FRAC(95, 100)))
115 return;
116
117 mi->prev_sample = true;
118 @@ -587,7 +587,7 @@ static u32 minstrel_get_expected_through
119 * computing cur_tp
120 */
121 tmp_mrs = &mi->r[idx].stats;
122 - tmp_cur_tp = minstrel_get_tp_avg(&mi->r[idx], tmp_mrs->prob_ewma) * 10;
123 + tmp_cur_tp = minstrel_get_tp_avg(&mi->r[idx], tmp_mrs->prob_avg) * 10;
124 tmp_cur_tp = tmp_cur_tp * 1200 * 8 / 1024;
125
126 return tmp_cur_tp;
127 --- a/net/mac80211/rc80211_minstrel.h
128 +++ b/net/mac80211/rc80211_minstrel.h
129 @@ -63,14 +63,10 @@ minstrel_ewmv(int old_ewmv, int cur_prob
130 return weight * (old_ewmv + MINSTREL_TRUNC(diff * incr)) / EWMA_DIV;
131 }
132
133 -struct minstrel_avg_ctx {
134 - s32 prev[2];
135 -};
136 -
137 -static inline int minstrel_filter_avg_add(struct minstrel_avg_ctx *ctx, s32 in)
138 +static inline int minstrel_filter_avg_add(u16 *prev_1, u16 *prev_2, s32 in)
139 {
140 - s32 out_1 = ctx->prev[0];
141 - s32 out_2 = ctx->prev[1];
142 + s32 out_1 = *prev_1;
143 + s32 out_2 = *prev_2;
144 s32 val;
145
146 if (!in)
147 @@ -92,8 +88,8 @@ static inline int minstrel_filter_avg_ad
148 val = 1;
149
150 out:
151 - ctx->prev[1] = out_1;
152 - ctx->prev[0] = val;
153 + *prev_2 = out_1;
154 + *prev_1 = val;
155
156 return val;
157 }
158 @@ -106,14 +102,15 @@ struct minstrel_rate_stats {
159 /* total attempts/success counters */
160 u32 att_hist, succ_hist;
161
162 - struct minstrel_avg_ctx avg;
163 -
164 /* statistis of packet delivery probability
165 * prob_ewma - exponential weighted moving average of prob
166 * prob_ewmsd - exp. weighted moving standard deviation of prob */
167 - u16 prob_ewma;
168 u16 prob_ewmv;
169
170 + /* prob_avg - moving average of prob */
171 + u16 prob_avg;
172 + u16 prob_avg_1;
173 +
174 /* maximum retry counts */
175 u8 retry_count;
176 u8 retry_count_rtscts;
177 @@ -208,7 +205,7 @@ void minstrel_add_sta_debugfs(void *priv
178 /* Recalculate success probabilities and counters for a given rate using EWMA */
179 void minstrel_calc_rate_stats(struct minstrel_priv *mp,
180 struct minstrel_rate_stats *mrs);
181 -int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_ewma);
182 +int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_avg);
183
184 /* debugfs */
185 int minstrel_stats_open(struct inode *inode, struct file *file);
186 --- a/net/mac80211/rc80211_minstrel_debugfs.c
187 +++ b/net/mac80211/rc80211_minstrel_debugfs.c
188 @@ -91,8 +91,9 @@ minstrel_stats_open(struct inode *inode,
189 p += sprintf(p, "%6u ", mr->perfect_tx_time);
190
191 tp_max = minstrel_get_tp_avg(mr, MINSTREL_FRAC(100,100));
192 - tp_avg = minstrel_get_tp_avg(mr, mrs->prob_ewma);
193 - eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
194 + tp_avg = minstrel_get_tp_avg(mr, mrs->prob_avg);
195 + eprob = MINSTREL_TRUNC(mrs->prob_avg * 1000);
196 +
197 prob_ewmsd = minstrel_get_ewmsd10(mrs);
198
199 p += sprintf(p, "%4u.%1u %4u.%1u %3u.%1u %3u.%1u"
200 @@ -151,8 +152,8 @@ minstrel_stats_csv_open(struct inode *in
201 p += sprintf(p, "%u,",mr->perfect_tx_time);
202
203 tp_max = minstrel_get_tp_avg(mr, MINSTREL_FRAC(100,100));
204 - tp_avg = minstrel_get_tp_avg(mr, mrs->prob_ewma);
205 - eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
206 + tp_avg = minstrel_get_tp_avg(mr, mrs->prob_avg);
207 + eprob = MINSTREL_TRUNC(mrs->prob_avg * 1000);
208 prob_ewmsd = minstrel_get_ewmsd10(mrs);
209
210 p += sprintf(p, "%u.%u,%u.%u,%u.%u,%u.%u,%u,%u,%u,"
211 --- a/net/mac80211/rc80211_minstrel_ht.c
212 +++ b/net/mac80211/rc80211_minstrel_ht.c
213 @@ -313,12 +313,12 @@ minstrel_ht_avg_ampdu_len(struct minstre
214 */
215 int
216 minstrel_ht_get_tp_avg(struct minstrel_ht_sta *mi, int group, int rate,
217 - int prob_ewma)
218 + int prob_avg)
219 {
220 unsigned int nsecs = 0;
221
222 /* do not account throughput if sucess prob is below 10% */
223 - if (prob_ewma < MINSTREL_FRAC(10, 100))
224 + if (prob_avg < MINSTREL_FRAC(10, 100))
225 return 0;
226
227 if (group != MINSTREL_CCK_GROUP)
228 @@ -332,11 +332,11 @@ minstrel_ht_get_tp_avg(struct minstrel_h
229 * account for collision related packet error rate fluctuation
230 * (prob is scaled - see MINSTREL_FRAC above)
231 */
232 - if (prob_ewma > MINSTREL_FRAC(90, 100))
233 + if (prob_avg > MINSTREL_FRAC(90, 100))
234 return MINSTREL_TRUNC(100000 * ((MINSTREL_FRAC(90, 100) * 1000)
235 / nsecs));
236 else
237 - return MINSTREL_TRUNC(100000 * ((prob_ewma * 1000) / nsecs));
238 + return MINSTREL_TRUNC(100000 * ((prob_avg * 1000) / nsecs));
239 }
240
241 /*
242 @@ -356,13 +356,13 @@ minstrel_ht_sort_best_tp_rates(struct mi
243
244 cur_group = index / MCS_GROUP_RATES;
245 cur_idx = index % MCS_GROUP_RATES;
246 - cur_prob = mi->groups[cur_group].rates[cur_idx].prob_ewma;
247 + cur_prob = mi->groups[cur_group].rates[cur_idx].prob_avg;
248 cur_tp_avg = minstrel_ht_get_tp_avg(mi, cur_group, cur_idx, cur_prob);
249
250 do {
251 tmp_group = tp_list[j - 1] / MCS_GROUP_RATES;
252 tmp_idx = tp_list[j - 1] % MCS_GROUP_RATES;
253 - tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_ewma;
254 + tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_avg;
255 tmp_tp_avg = minstrel_ht_get_tp_avg(mi, tmp_group, tmp_idx,
256 tmp_prob);
257 if (cur_tp_avg < tmp_tp_avg ||
258 @@ -399,7 +399,7 @@ minstrel_ht_set_best_prob_rate(struct mi
259
260 tmp_group = mi->max_prob_rate / MCS_GROUP_RATES;
261 tmp_idx = mi->max_prob_rate % MCS_GROUP_RATES;
262 - tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_ewma;
263 + tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_avg;
264 tmp_tp_avg = minstrel_ht_get_tp_avg(mi, tmp_group, tmp_idx, tmp_prob);
265
266 /* if max_tp_rate[0] is from MCS_GROUP max_prob_rate get selected from
267 @@ -411,11 +411,11 @@ minstrel_ht_set_best_prob_rate(struct mi
268
269 max_gpr_group = mg->max_group_prob_rate / MCS_GROUP_RATES;
270 max_gpr_idx = mg->max_group_prob_rate % MCS_GROUP_RATES;
271 - max_gpr_prob = mi->groups[max_gpr_group].rates[max_gpr_idx].prob_ewma;
272 + max_gpr_prob = mi->groups[max_gpr_group].rates[max_gpr_idx].prob_avg;
273
274 - if (mrs->prob_ewma > MINSTREL_FRAC(75, 100)) {
275 + if (mrs->prob_avg > MINSTREL_FRAC(75, 100)) {
276 cur_tp_avg = minstrel_ht_get_tp_avg(mi, cur_group, cur_idx,
277 - mrs->prob_ewma);
278 + mrs->prob_avg);
279 if (cur_tp_avg > tmp_tp_avg)
280 mi->max_prob_rate = index;
281
282 @@ -425,9 +425,9 @@ minstrel_ht_set_best_prob_rate(struct mi
283 if (cur_tp_avg > max_gpr_tp_avg)
284 mg->max_group_prob_rate = index;
285 } else {
286 - if (mrs->prob_ewma > tmp_prob)
287 + if (mrs->prob_avg > tmp_prob)
288 mi->max_prob_rate = index;
289 - if (mrs->prob_ewma > max_gpr_prob)
290 + if (mrs->prob_avg > max_gpr_prob)
291 mg->max_group_prob_rate = index;
292 }
293 }
294 @@ -449,12 +449,12 @@ minstrel_ht_assign_best_tp_rates(struct
295
296 tmp_group = tmp_cck_tp_rate[0] / MCS_GROUP_RATES;
297 tmp_idx = tmp_cck_tp_rate[0] % MCS_GROUP_RATES;
298 - tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_ewma;
299 + tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_avg;
300 tmp_cck_tp = minstrel_ht_get_tp_avg(mi, tmp_group, tmp_idx, tmp_prob);
301
302 tmp_group = tmp_mcs_tp_rate[0] / MCS_GROUP_RATES;
303 tmp_idx = tmp_mcs_tp_rate[0] % MCS_GROUP_RATES;
304 - tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_ewma;
305 + tmp_prob = mi->groups[tmp_group].rates[tmp_idx].prob_avg;
306 tmp_mcs_tp = minstrel_ht_get_tp_avg(mi, tmp_group, tmp_idx, tmp_prob);
307
308 if (tmp_cck_tp_rate && tmp_cck_tp > tmp_mcs_tp) {
309 @@ -485,7 +485,7 @@ minstrel_ht_prob_rate_reduce_streams(str
310 continue;
311
312 tmp_idx = mg->max_group_prob_rate % MCS_GROUP_RATES;
313 - tmp_prob = mi->groups[group].rates[tmp_idx].prob_ewma;
314 + tmp_prob = mi->groups[group].rates[tmp_idx].prob_avg;
315
316 if (tmp_tp < minstrel_ht_get_tp_avg(mi, group, tmp_idx, tmp_prob) &&
317 (minstrel_mcs_groups[group].streams < tmp_max_streams)) {
318 @@ -590,7 +590,7 @@ minstrel_ht_rate_sample_switch(struct mi
319 * If that fails, look again for a rate that is at least as fast
320 */
321 mrs = minstrel_get_ratestats(mi, mi->max_tp_rate[0]);
322 - faster_rate = mrs->prob_ewma > MINSTREL_FRAC(75, 100);
323 + faster_rate = mrs->prob_avg > MINSTREL_FRAC(75, 100);
324 minstrel_ht_find_probe_rates(mi, rates, &n_rates, faster_rate);
325 if (!n_rates && faster_rate)
326 minstrel_ht_find_probe_rates(mi, rates, &n_rates, false);
327 @@ -705,7 +705,7 @@ minstrel_ht_update_stats(struct minstrel
328 mrs = &mg->rates[i];
329 mrs->retry_updated = false;
330 minstrel_calc_rate_stats(mp, mrs);
331 - cur_prob = mrs->prob_ewma;
332 + cur_prob = mrs->prob_avg;
333
334 if (minstrel_ht_get_tp_avg(mi, group, i, cur_prob) == 0)
335 continue;
336 @@ -979,7 +979,7 @@ minstrel_calc_retransmit(struct minstrel
337 unsigned int overhead = 0, overhead_rtscts = 0;
338
339 mrs = minstrel_get_ratestats(mi, index);
340 - if (mrs->prob_ewma < MINSTREL_FRAC(1, 10)) {
341 + if (mrs->prob_avg < MINSTREL_FRAC(1, 10)) {
342 mrs->retry_count = 1;
343 mrs->retry_count_rtscts = 1;
344 return;
345 @@ -1036,7 +1036,7 @@ minstrel_ht_set_rate(struct minstrel_pri
346 if (!mrs->retry_updated)
347 minstrel_calc_retransmit(mp, mi, index);
348
349 - if (mrs->prob_ewma < MINSTREL_FRAC(20, 100) || !mrs->retry_count) {
350 + if (mrs->prob_avg < MINSTREL_FRAC(20, 100) || !mrs->retry_count) {
351 ratetbl->rate[offset].count = 2;
352 ratetbl->rate[offset].count_rts = 2;
353 ratetbl->rate[offset].count_cts = 2;
354 @@ -1070,11 +1070,11 @@ minstrel_ht_set_rate(struct minstrel_pri
355 }
356
357 static inline int
358 -minstrel_ht_get_prob_ewma(struct minstrel_ht_sta *mi, int rate)
359 +minstrel_ht_get_prob_avg(struct minstrel_ht_sta *mi, int rate)
360 {
361 int group = rate / MCS_GROUP_RATES;
362 rate %= MCS_GROUP_RATES;
363 - return mi->groups[group].rates[rate].prob_ewma;
364 + return mi->groups[group].rates[rate].prob_avg;
365 }
366
367 static int
368 @@ -1086,7 +1086,7 @@ minstrel_ht_get_max_amsdu_len(struct min
369 unsigned int duration;
370
371 /* Disable A-MSDU if max_prob_rate is bad */
372 - if (mi->groups[group].rates[rate].prob_ewma < MINSTREL_FRAC(50, 100))
373 + if (mi->groups[group].rates[rate].prob_avg < MINSTREL_FRAC(50, 100))
374 return 1;
375
376 duration = g->duration[rate];
377 @@ -1109,7 +1109,7 @@ minstrel_ht_get_max_amsdu_len(struct min
378 * data packet size
379 */
380 if (duration > MCS_DURATION(1, 0, 260) ||
381 - (minstrel_ht_get_prob_ewma(mi, mi->max_tp_rate[0]) <
382 + (minstrel_ht_get_prob_avg(mi, mi->max_tp_rate[0]) <
383 MINSTREL_FRAC(75, 100)))
384 return 3200;
385
386 @@ -1216,7 +1216,7 @@ minstrel_get_sample_rate(struct minstrel
387 * rate, to avoid wasting airtime.
388 */
389 sample_dur = minstrel_get_duration(sample_idx);
390 - if (mrs->prob_ewma > MINSTREL_FRAC(95, 100) ||
391 + if (mrs->prob_avg > MINSTREL_FRAC(95, 100) ||
392 minstrel_get_duration(mi->max_prob_rate) * 3 < sample_dur)
393 return -1;
394
395 @@ -1679,7 +1679,7 @@ static u32 minstrel_ht_get_expected_thro
396
397 i = mi->max_tp_rate[0] / MCS_GROUP_RATES;
398 j = mi->max_tp_rate[0] % MCS_GROUP_RATES;
399 - prob = mi->groups[i].rates[j].prob_ewma;
400 + prob = mi->groups[i].rates[j].prob_avg;
401
402 /* convert tp_avg from pkt per second in kbps */
403 tp_avg = minstrel_ht_get_tp_avg(mi, i, j, prob) * 10;
404 --- a/net/mac80211/rc80211_minstrel_ht.h
405 +++ b/net/mac80211/rc80211_minstrel_ht.h
406 @@ -122,6 +122,6 @@ struct minstrel_ht_sta_priv {
407
408 void minstrel_ht_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);
409 int minstrel_ht_get_tp_avg(struct minstrel_ht_sta *mi, int group, int rate,
410 - int prob_ewma);
411 + int prob_avg);
412
413 #endif
414 --- a/net/mac80211/rc80211_minstrel_ht_debugfs.c
415 +++ b/net/mac80211/rc80211_minstrel_ht_debugfs.c
416 @@ -102,8 +102,8 @@ minstrel_ht_stats_dump(struct minstrel_h
417 p += sprintf(p, "%6u ", tx_time);
418
419 tp_max = minstrel_ht_get_tp_avg(mi, i, j, MINSTREL_FRAC(100, 100));
420 - tp_avg = minstrel_ht_get_tp_avg(mi, i, j, mrs->prob_ewma);
421 - eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
422 + tp_avg = minstrel_ht_get_tp_avg(mi, i, j, mrs->prob_avg);
423 + eprob = MINSTREL_TRUNC(mrs->prob_avg * 1000);
424 prob_ewmsd = minstrel_get_ewmsd10(mrs);
425
426 p += sprintf(p, "%4u.%1u %4u.%1u %3u.%1u %3u.%1u"
427 @@ -250,8 +250,8 @@ minstrel_ht_stats_csv_dump(struct minstr
428 p += sprintf(p, "%u,", tx_time);
429
430 tp_max = minstrel_ht_get_tp_avg(mi, i, j, MINSTREL_FRAC(100, 100));
431 - tp_avg = minstrel_ht_get_tp_avg(mi, i, j, mrs->prob_ewma);
432 - eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
433 + tp_avg = minstrel_ht_get_tp_avg(mi, i, j, mrs->prob_avg);
434 + eprob = MINSTREL_TRUNC(mrs->prob_avg * 1000);
435 prob_ewmsd = minstrel_get_ewmsd10(mrs);
436
437 p += sprintf(p, "%u.%u,%u.%u,%u.%u,%u.%u,%u,%u,"