1 /* $OpenBSD: ieee80211_ra.c,v 1.5 2022/03/19 10:28:44 stsp Exp $ */
2
3 /*
4 * Copyright (c) 2021 Christian Ehrhardt <ehrhardt@genua.de>
5 * Copyright (c) 2016, 2021 Stefan Sperling <stsp@openbsd.org>
6 * Copyright (c) 2016 Theo Buehler <tb@openbsd.org>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21 #include <sys/param.h>
22 #include <sys/systm.h>
23 #include <sys/socket.h>
24
25 #include <net/if.h>
26 #include <net/if_media.h>
27
28 #include <netinet/in.h>
29 #include <netinet/if_ether.h>
30
31 #include <net80211/ieee80211_var.h>
32 #include <net80211/ieee80211_ra.h>
33
34 int ieee80211_ra_next_intra_rate(struct ieee80211_ra_node *,
35 struct ieee80211_node *);
36 const struct ieee80211_ht_rateset * ieee80211_ra_next_rateset(
37 struct ieee80211_ra_node *, struct ieee80211_node *);
38 int ieee80211_ra_best_mcs_in_rateset(struct ieee80211_ra_node *,
39 const struct ieee80211_ht_rateset *);
40 void ieee80211_ra_probe_next_rateset(struct ieee80211_ra_node *,
41 struct ieee80211_node *, const struct ieee80211_ht_rateset *);
42 int ieee80211_ra_next_mcs(struct ieee80211_ra_node *,
43 struct ieee80211_node *);
44 void ieee80211_ra_probe_done(struct ieee80211_ra_node *);
45 int ieee80211_ra_intra_mode_ra_finished(
46 struct ieee80211_ra_node *, struct ieee80211_node *);
47 void ieee80211_ra_trigger_next_rateset(struct ieee80211_ra_node *,
48 struct ieee80211_node *);
49 int ieee80211_ra_inter_mode_ra_finished(
50 struct ieee80211_ra_node *, struct ieee80211_node *);
51 int ieee80211_ra_best_rate(struct ieee80211_ra_node *,
52 struct ieee80211_node *);
53 void ieee80211_ra_probe_next_rate(struct ieee80211_ra_node *,
54 struct ieee80211_node *);
55 int ieee80211_ra_valid_tx_mcs(struct ieee80211com *, int);
56 uint32_t ieee80211_ra_valid_rates(struct ieee80211com *,
57 struct ieee80211_node *);
58 int ieee80211_ra_probe_valid(struct ieee80211_ra_goodput_stats *);
59
60 /* We use fixed point arithmetic with 64 bit integers. */
61 #define RA_FP_SHIFT 21
62 #define RA_FP_INT(x) (x ## ULL << RA_FP_SHIFT) /* the integer x */
63 #define RA_FP_1 RA_FP_INT(1)
64
65 /* Multiply two fixed point numbers. */
66 #define RA_FP_MUL(a, b) \
67 (((a) * (b)) >> RA_FP_SHIFT)
68
69 /* Divide two fixed point numbers. */
70 #define RA_FP_DIV(a, b) \
71 (b == 0 ? (uint64_t)-1 : (((a) << RA_FP_SHIFT) / (b)))
72
73 #ifdef RA_DEBUG
74 #define DPRINTF(x) do { if (ra_debug > 0) printf x; } while (0)
75 #define DPRINTFN(n, x) do { if (ra_debug >= (n)) printf x; } while (0)
76 int ra_debug = 0;
77 #else
78 #define DPRINTF(x) do { ; } while (0)
79 #define DPRINTFN(n, x) do { ; } while (0)
80 #endif
81
82 #ifdef RA_DEBUG
83 void
ra_fixedp_split(uint32_t * i,uint32_t * f,uint64_t fp)84 ra_fixedp_split(uint32_t *i, uint32_t *f, uint64_t fp)
85 {
86 uint64_t tmp;
87
88 /* integer part */
89 *i = (fp >> RA_FP_SHIFT);
90
91 /* fractional part */
92 tmp = (fp & ((uint64_t)-1 >> (64 - RA_FP_SHIFT)));
93 tmp *= 100;
94 *f = (uint32_t)(tmp >> RA_FP_SHIFT);
95 }
96
97 char *
ra_fp_sprintf(uint64_t fp)98 ra_fp_sprintf(uint64_t fp)
99 {
100 uint32_t i, f;
101 static char buf[64];
102 int ret;
103
104 ra_fixedp_split(&i, &f, fp);
105 ret = snprintf(buf, sizeof(buf), "%u.%02u", i, f);
106 if (ret == -1 || ret >= sizeof(buf))
107 return "ERR";
108
109 return buf;
110 }
111 #endif /* RA_DEBUG */
112
113 const struct ieee80211_ht_rateset *
ieee80211_ra_get_ht_rateset(int mcs,int chan40,int sgi)114 ieee80211_ra_get_ht_rateset(int mcs, int chan40, int sgi)
115 {
116 const struct ieee80211_ht_rateset *rs;
117 int i;
118
119 for (i = 0; i < IEEE80211_HT_NUM_RATESETS; i++) {
120 rs = &ieee80211_std_ratesets_11n[i];
121 if (chan40 == rs->chan40 && sgi == rs->sgi &&
122 mcs >= rs->min_mcs && mcs <= rs->max_mcs)
123 return rs;
124 }
125
126 panic("MCS %d is not part of any rateset", mcs);
127 }
128
129 int
ieee80211_ra_use_ht_sgi(struct ieee80211_node * ni)130 ieee80211_ra_use_ht_sgi(struct ieee80211_node *ni)
131 {
132 if ((ni->ni_chan->ic_flags & IEEE80211_CHAN_40MHZ) &&
133 ieee80211_node_supports_ht_chan40(ni)) {
134 if (ni->ni_flags & IEEE80211_NODE_HT_SGI40)
135 return 1;
136 } else if (ni->ni_flags & IEEE80211_NODE_HT_SGI20)
137 return 1;
138
139 return 0;
140 }
141
142 /*
143 * Update goodput statistics.
144 */
145
146 uint64_t
ieee80211_ra_get_txrate(int mcs,int chan40,int sgi)147 ieee80211_ra_get_txrate(int mcs, int chan40, int sgi)
148 {
149 const struct ieee80211_ht_rateset *rs;
150 uint64_t txrate;
151
152 rs = ieee80211_ra_get_ht_rateset(mcs, chan40, sgi);
153 txrate = rs->rates[mcs - rs->min_mcs];
154 txrate <<= RA_FP_SHIFT; /* convert to fixed-point */
155 txrate *= 500; /* convert to kbit/s */
156 txrate /= 1000; /* convert to mbit/s */
157
158 return txrate;
159 }
160
161 /*
162 * Rate selection.
163 */
164
165 /* A rate's goodput has to be at least this much larger to be "better". */
166 #define IEEE80211_RA_RATE_THRESHOLD (RA_FP_1 / 64) /* ~ 0.015 */
167
168 int
ieee80211_ra_next_lower_intra_rate(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)169 ieee80211_ra_next_lower_intra_rate(struct ieee80211_ra_node *rn,
170 struct ieee80211_node *ni)
171 {
172 const struct ieee80211_ht_rateset *rs;
173 int i, next;
174
175 rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs,
176 ieee80211_node_supports_ht_chan40(ni), ieee80211_ra_use_ht_sgi(ni));
177 if (ni->ni_txmcs == rs->min_mcs)
178 return rs->min_mcs;
179
180 next = ni->ni_txmcs;
181 for (i = rs->nrates - 1; i >= 0; i--) {
182 if ((rn->valid_rates & (1 << (i + rs->min_mcs))) == 0)
183 continue;
184 if (i + rs->min_mcs < ni->ni_txmcs) {
185 next = i + rs->min_mcs;
186 break;
187 }
188 }
189
190 return next;
191 }
192
193 int
ieee80211_ra_next_intra_rate(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)194 ieee80211_ra_next_intra_rate(struct ieee80211_ra_node *rn,
195 struct ieee80211_node *ni)
196 {
197 const struct ieee80211_ht_rateset *rs;
198 int i, next;
199
200 rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs,
201 ieee80211_node_supports_ht_chan40(ni), ieee80211_ra_use_ht_sgi(ni));
202 if (ni->ni_txmcs == rs->max_mcs)
203 return rs->max_mcs;
204
205 next = ni->ni_txmcs;
206 for (i = 0; i < rs->nrates; i++) {
207 if ((rn->valid_rates & (1 << (i + rs->min_mcs))) == 0)
208 continue;
209 if (i + rs->min_mcs > ni->ni_txmcs) {
210 next = i + rs->min_mcs;
211 break;
212 }
213 }
214
215 return next;
216 }
217
218 const struct ieee80211_ht_rateset *
ieee80211_ra_next_rateset(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)219 ieee80211_ra_next_rateset(struct ieee80211_ra_node *rn,
220 struct ieee80211_node *ni)
221 {
222 const struct ieee80211_ht_rateset *rs, *rsnext;
223 int next;
224 int chan40 = ieee80211_node_supports_ht_chan40(ni);
225 int sgi = ieee80211_ra_use_ht_sgi(ni);
226 int mcs = ni->ni_txmcs;
227
228 rs = ieee80211_ra_get_ht_rateset(mcs, chan40, sgi);
229 if (rn->probing & IEEE80211_RA_PROBING_UP) {
230 if (rs->max_mcs == 7) { /* MCS 0-7 */
231 if (chan40)
232 next = sgi ? IEEE80211_HT_RATESET_MIMO2_SGI40 :
233 IEEE80211_HT_RATESET_MIMO2_40;
234 else
235 next = sgi ? IEEE80211_HT_RATESET_MIMO2_SGI :
236 IEEE80211_HT_RATESET_MIMO2;
237 } else if (rs->max_mcs == 15) { /* MCS 8-15 */
238 if (chan40)
239 next = sgi ? IEEE80211_HT_RATESET_MIMO3_SGI40 :
240 IEEE80211_HT_RATESET_MIMO3_40;
241 else
242 next = sgi ? IEEE80211_HT_RATESET_MIMO3_SGI :
243 IEEE80211_HT_RATESET_MIMO3;
244 } else if (rs->max_mcs == 23) { /* MCS 16-23 */
245 if (chan40)
246 next = sgi ? IEEE80211_HT_RATESET_MIMO4_SGI40 :
247 IEEE80211_HT_RATESET_MIMO4_40;
248 else
249 next = sgi ? IEEE80211_HT_RATESET_MIMO4_SGI :
250 IEEE80211_HT_RATESET_MIMO4;
251 } else /* MCS 24-31 */
252 return NULL;
253 } else if (rn->probing & IEEE80211_RA_PROBING_DOWN) {
254 if (rs->min_mcs == 24) { /* MCS 24-31 */
255 if (chan40)
256 next = sgi ? IEEE80211_HT_RATESET_MIMO3_SGI40 :
257 IEEE80211_HT_RATESET_MIMO3_40;
258 else
259 next = sgi ? IEEE80211_HT_RATESET_MIMO3_SGI :
260 IEEE80211_HT_RATESET_MIMO3;
261 } else if (rs->min_mcs == 16) { /* MCS 16-23 */
262 if (chan40)
263 next = sgi ? IEEE80211_HT_RATESET_MIMO2_SGI40 :
264 IEEE80211_HT_RATESET_MIMO2_40;
265 else
266 next = sgi ? IEEE80211_HT_RATESET_MIMO2_SGI :
267 IEEE80211_HT_RATESET_MIMO2;
268 } else if (rs->min_mcs == 8) { /* MCS 8-15 */
269 if (chan40)
270 next = sgi ? IEEE80211_HT_RATESET_SISO_SGI40 :
271 IEEE80211_HT_RATESET_SISO_40;
272 else
273 next = sgi ? IEEE80211_HT_RATESET_SISO_SGI :
274 IEEE80211_HT_RATESET_SISO;
275 } else /* MCS 0-7 */
276 return NULL;
277 } else
278 panic("%s: invalid probing mode %d", __func__, rn->probing);
279
280 rsnext = &ieee80211_std_ratesets_11n[next];
281 if ((rsnext->mcs_mask & rn->valid_rates) == 0)
282 return NULL;
283
284 return rsnext;
285 }
286
287 int
ieee80211_ra_best_mcs_in_rateset(struct ieee80211_ra_node * rn,const struct ieee80211_ht_rateset * rs)288 ieee80211_ra_best_mcs_in_rateset(struct ieee80211_ra_node *rn,
289 const struct ieee80211_ht_rateset *rs)
290 {
291 uint64_t gmax = 0;
292 int i, best_mcs = rs->min_mcs;
293
294 for (i = 0; i < rs->nrates; i++) {
295 int mcs = rs->min_mcs + i;
296 struct ieee80211_ra_goodput_stats *g = &rn->g[mcs];
297 if (((1 << mcs) & rn->valid_rates) == 0)
298 continue;
299 if (g->measured > gmax + IEEE80211_RA_RATE_THRESHOLD) {
300 gmax = g->measured;
301 best_mcs = mcs;
302 }
303 }
304
305 return best_mcs;
306 }
307
308 void
ieee80211_ra_probe_next_rateset(struct ieee80211_ra_node * rn,struct ieee80211_node * ni,const struct ieee80211_ht_rateset * rsnext)309 ieee80211_ra_probe_next_rateset(struct ieee80211_ra_node *rn,
310 struct ieee80211_node *ni, const struct ieee80211_ht_rateset *rsnext)
311 {
312 const struct ieee80211_ht_rateset *rs;
313 struct ieee80211_ra_goodput_stats *g;
314 int best_mcs, i;
315
316 /* Find most recently measured best MCS from the current rateset. */
317 rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs,
318 ieee80211_node_supports_ht_chan40(ni), ieee80211_ra_use_ht_sgi(ni));
319 best_mcs = ieee80211_ra_best_mcs_in_rateset(rn, rs);
320
321 /* Switch to the next rateset. */
322 ni->ni_txmcs = rsnext->min_mcs;
323 if ((rn->valid_rates & (1 << rsnext->min_mcs)) == 0)
324 ni->ni_txmcs = ieee80211_ra_next_intra_rate(rn, ni);
325
326 /* Select the lowest rate from the next rateset with loss-free
327 * goodput close to the current best measurement. */
328 g = &rn->g[best_mcs];
329 for (i = 0; i < rsnext->nrates; i++) {
330 int mcs = rsnext->min_mcs + i;
331 uint64_t txrate = rsnext->rates[i];
332
333 if ((rn->valid_rates & (1 << mcs)) == 0)
334 continue;
335
336 txrate = txrate * 500; /* convert to kbit/s */
337 txrate <<= RA_FP_SHIFT; /* convert to fixed-point */
338 txrate /= 1000; /* convert to mbit/s */
339
340 if (txrate > g->measured + IEEE80211_RA_RATE_THRESHOLD) {
341 ni->ni_txmcs = mcs;
342 break;
343 }
344 }
345 /* If all rates are lower the maximum rate is the closest match. */
346 if (i == rsnext->nrates)
347 ni->ni_txmcs = rsnext->max_mcs;
348
349 /* Add rates from the next rateset as candidates. */
350 rn->candidate_rates |= (1 << ni->ni_txmcs);
351 if (rn->probing & IEEE80211_RA_PROBING_UP) {
352 rn->candidate_rates |=
353 (1 << ieee80211_ra_next_intra_rate(rn, ni));
354 } else if (rn->probing & IEEE80211_RA_PROBING_DOWN) {
355 rn->candidate_rates |=
356 (1 << ieee80211_ra_next_lower_intra_rate(rn, ni));
357 } else
358 panic("%s: invalid probing mode %d", __func__, rn->probing);
359 }
360
361 int
ieee80211_ra_next_mcs(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)362 ieee80211_ra_next_mcs(struct ieee80211_ra_node *rn,
363 struct ieee80211_node *ni)
364 {
365 int next;
366
367 if (rn->probing & IEEE80211_RA_PROBING_DOWN)
368 next = ieee80211_ra_next_lower_intra_rate(rn, ni);
369 else if (rn->probing & IEEE80211_RA_PROBING_UP)
370 next = ieee80211_ra_next_intra_rate(rn, ni);
371 else
372 panic("%s: invalid probing mode %d", __func__, rn->probing);
373
374 return next;
375 }
376
377 void
ieee80211_ra_probe_clear(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)378 ieee80211_ra_probe_clear(struct ieee80211_ra_node *rn,
379 struct ieee80211_node *ni)
380 {
381 struct ieee80211_ra_goodput_stats *g = &rn->g[ni->ni_txmcs];
382
383 g->nprobe_pkts = 0;
384 g->nprobe_fail = 0;
385 }
386
387 void
ieee80211_ra_probe_done(struct ieee80211_ra_node * rn)388 ieee80211_ra_probe_done(struct ieee80211_ra_node *rn)
389 {
390 rn->probing = IEEE80211_RA_NOT_PROBING;
391 rn->probed_rates = 0;
392 rn->valid_probes = 0;
393 rn->candidate_rates = 0;
394 }
395
396 int
ieee80211_ra_intra_mode_ra_finished(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)397 ieee80211_ra_intra_mode_ra_finished(struct ieee80211_ra_node *rn,
398 struct ieee80211_node *ni)
399 {
400 const struct ieee80211_ht_rateset *rs;
401 struct ieee80211_ra_goodput_stats *g = &rn->g[ni->ni_txmcs];
402 int next_mcs, best_mcs;
403 uint64_t next_rate;
404 int chan40 = ieee80211_node_supports_ht_chan40(ni);
405 int sgi = ieee80211_ra_use_ht_sgi(ni);
406
407 rn->probed_rates = (rn->probed_rates | (1 << ni->ni_txmcs));
408
409 /* Check if the min/max MCS in this rateset has been probed. */
410 rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, chan40, sgi);
411 if (rn->probing & IEEE80211_RA_PROBING_DOWN) {
412 if (ni->ni_txmcs == rs->min_mcs ||
413 rn->probed_rates & (1 << rs->min_mcs)) {
414 ieee80211_ra_trigger_next_rateset(rn, ni);
415 return 1;
416 }
417 } else if (rn->probing & IEEE80211_RA_PROBING_UP) {
418 if (ni->ni_txmcs == rs->max_mcs ||
419 rn->probed_rates & (1 << rs->max_mcs)) {
420 ieee80211_ra_trigger_next_rateset(rn, ni);
421 return 1;
422 }
423 }
424
425 /*
426 * Check if the measured goodput is loss-free and better than the
427 * loss-free goodput of the candidate rate.
428 */
429 next_mcs = ieee80211_ra_next_mcs(rn, ni);
430 if (next_mcs == ni->ni_txmcs) {
431 ieee80211_ra_trigger_next_rateset(rn, ni);
432 return 1;
433 }
434 next_rate = ieee80211_ra_get_txrate(next_mcs, chan40, sgi);
435 if (g->loss == 0 &&
436 g->measured >= next_rate + IEEE80211_RA_RATE_THRESHOLD) {
437 ieee80211_ra_trigger_next_rateset(rn, ni);
438 return 1;
439 }
440
441 /* Check if we had a better measurement at a previously probed MCS. */
442 best_mcs = ieee80211_ra_best_mcs_in_rateset(rn, rs);
443 if (best_mcs != ni->ni_txmcs && (rn->probed_rates & (1 << best_mcs))) {
444 if ((rn->probing & IEEE80211_RA_PROBING_UP) &&
445 best_mcs < ni->ni_txmcs) {
446 ieee80211_ra_trigger_next_rateset(rn, ni);
447 return 1;
448 }
449 if ((rn->probing & IEEE80211_RA_PROBING_DOWN) &&
450 best_mcs > ni->ni_txmcs) {
451 ieee80211_ra_trigger_next_rateset(rn, ni);
452 return 1;
453 }
454 }
455
456 /* Check if all rates in the set of candidate rates have been probed. */
457 if ((rn->candidate_rates & rn->probed_rates) == rn->candidate_rates) {
458 /* Remain in the current rateset until above checks trigger. */
459 rn->probing &= ~IEEE80211_RA_PROBING_INTER;
460 return 1;
461 }
462
463 return 0;
464 }
465
466 void
ieee80211_ra_trigger_next_rateset(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)467 ieee80211_ra_trigger_next_rateset(struct ieee80211_ra_node *rn,
468 struct ieee80211_node *ni)
469 {
470 const struct ieee80211_ht_rateset *rsnext;
471
472 rsnext = ieee80211_ra_next_rateset(rn, ni);
473 if (rsnext) {
474 ieee80211_ra_probe_next_rateset(rn, ni, rsnext);
475 rn->probing |= IEEE80211_RA_PROBING_INTER;
476 } else
477 rn->probing &= ~IEEE80211_RA_PROBING_INTER;
478 }
479
480 int
ieee80211_ra_inter_mode_ra_finished(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)481 ieee80211_ra_inter_mode_ra_finished(struct ieee80211_ra_node *rn,
482 struct ieee80211_node *ni)
483 {
484 return ((rn->probing & IEEE80211_RA_PROBING_INTER) == 0);
485 }
486
487 int
ieee80211_ra_best_rate(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)488 ieee80211_ra_best_rate(struct ieee80211_ra_node *rn,
489 struct ieee80211_node *ni)
490 {
491 int i, best = rn->best_mcs;
492 uint64_t gmax = rn->g[rn->best_mcs].measured;
493
494 for (i = 0; i < nitems(rn->g); i++) {
495 struct ieee80211_ra_goodput_stats *g = &rn->g[i];
496 if (((1 << i) & rn->valid_rates) == 0)
497 continue;
498 if (g->measured > gmax + IEEE80211_RA_RATE_THRESHOLD) {
499 gmax = g->measured;
500 best = i;
501 }
502 }
503
504 #ifdef RA_DEBUG
505 if (rn->best_mcs != best) {
506 DPRINTF(("MCS %d is best; MCS{cur|avg|loss}:", best));
507 for (i = 0; i < IEEE80211_HT_RATESET_NUM_MCS; i++) {
508 struct ieee80211_ra_goodput_stats *g = &rn->g[i];
509 if ((rn->valid_rates & (1 << i)) == 0)
510 continue;
511 DPRINTF((" %d{%s|", i, ra_fp_sprintf(g->measured)));
512 DPRINTF(("%s|", ra_fp_sprintf(g->average)));
513 DPRINTF(("%s%%}", ra_fp_sprintf(g->loss)));
514 }
515 DPRINTF(("\n"));
516 }
517 #endif
518 return best;
519 }
520
521 void
ieee80211_ra_probe_next_rate(struct ieee80211_ra_node * rn,struct ieee80211_node * ni)522 ieee80211_ra_probe_next_rate(struct ieee80211_ra_node *rn,
523 struct ieee80211_node *ni)
524 {
525 /* Select the next rate to probe. */
526 rn->probed_rates |= (1 << ni->ni_txmcs);
527 ni->ni_txmcs = ieee80211_ra_next_mcs(rn, ni);
528 }
529
530 int
ieee80211_ra_valid_tx_mcs(struct ieee80211com * ic,int mcs)531 ieee80211_ra_valid_tx_mcs(struct ieee80211com *ic, int mcs)
532 {
533 uint32_t ntxstreams = 1;
534 static const int max_mcs[] = { 7, 15, 23, 31 };
535
536 if ((ic->ic_tx_mcs_set & IEEE80211_TX_RX_MCS_NOT_EQUAL) == 0)
537 return isset(ic->ic_sup_mcs, mcs);
538
539 ntxstreams += ((ic->ic_tx_mcs_set & IEEE80211_TX_SPATIAL_STREAMS) >> 2);
540 if (ntxstreams < 1 || ntxstreams > 4)
541 panic("invalid number of Tx streams: %u", ntxstreams);
542 return (mcs <= max_mcs[ntxstreams - 1] && isset(ic->ic_sup_mcs, mcs));
543 }
544
545 uint32_t
ieee80211_ra_valid_rates(struct ieee80211com * ic,struct ieee80211_node * ni)546 ieee80211_ra_valid_rates(struct ieee80211com *ic, struct ieee80211_node *ni)
547 {
548 uint32_t valid_mcs = 0;
549 int i;
550
551 for (i = 0; i < IEEE80211_HT_RATESET_NUM_MCS; i++) {
552 if (!isset(ni->ni_rxmcs, i))
553 continue;
554 if (!ieee80211_ra_valid_tx_mcs(ic, i))
555 continue;
556 valid_mcs |= (1 << i);
557 }
558
559 return valid_mcs;
560 }
561
562 int
ieee80211_ra_probe_valid(struct ieee80211_ra_goodput_stats * g)563 ieee80211_ra_probe_valid(struct ieee80211_ra_goodput_stats *g)
564 {
565 /* 128 packets make up a valid probe in any case. */
566 if (g->nprobe_pkts >= 128)
567 return 1;
568
569 /* 8 packets with > 75% loss make a valid probe, too. */
570 if (g->nprobe_pkts >= 8 &&
571 g->nprobe_pkts - g->nprobe_fail < g->nprobe_pkts / 4)
572 return 1;
573
574 return 0;
575 }
576
577 void
ieee80211_ra_add_stats_ht(struct ieee80211_ra_node * rn,struct ieee80211com * ic,struct ieee80211_node * ni,int mcs,uint32_t total,uint32_t fail)578 ieee80211_ra_add_stats_ht(struct ieee80211_ra_node *rn,
579 struct ieee80211com *ic, struct ieee80211_node *ni,
580 int mcs, uint32_t total, uint32_t fail)
581 {
582 static const uint64_t alpha = RA_FP_1 / 8; /* 1/8 = 0.125 */
583 static const uint64_t beta = RA_FP_1 / 4; /* 1/4 = 0.25 */
584 int s;
585 struct ieee80211_ra_goodput_stats *g;
586 uint64_t sfer, rate, delta;
587
588 /*
589 * Ignore invalid values. These values may come from hardware
590 * so asserting valid values via panic is not appropriate.
591 */
592 if (mcs < 0 || mcs >= IEEE80211_HT_RATESET_NUM_MCS)
593 return;
594 if (total == 0)
595 return;
596
597 s = splnet();
598
599 g = &rn->g[mcs];
600 g->nprobe_pkts += total;
601 g->nprobe_fail += fail;
602
603 if (!ieee80211_ra_probe_valid(g)) {
604 splx(s);
605 return;
606 }
607 rn->valid_probes |= 1U << mcs;
608
609 if (g->nprobe_fail > g->nprobe_pkts) {
610 DPRINTF(("%s fail %u > pkts %u\n",
611 ether_sprintf(ni->ni_macaddr),
612 g->nprobe_fail, g->nprobe_pkts));
613 g->nprobe_fail = g->nprobe_pkts;
614 }
615
616 sfer = g->nprobe_fail << RA_FP_SHIFT;
617 sfer /= g->nprobe_pkts;
618 g->nprobe_fail = 0;
619 g->nprobe_pkts = 0;
620
621 rate = ieee80211_ra_get_txrate(mcs,
622 ieee80211_node_supports_ht_chan40(ni),
623 ieee80211_ra_use_ht_sgi(ni));
624
625 g->loss = sfer * 100;
626 g->measured = RA_FP_MUL(RA_FP_1 - sfer, rate);
627 g->average = RA_FP_MUL(RA_FP_1 - alpha, g->average);
628 g->average += RA_FP_MUL(alpha, g->measured);
629
630 g->stddeviation = RA_FP_MUL(RA_FP_1 - beta, g->stddeviation);
631 if (g->average > g->measured)
632 delta = g->average - g->measured;
633 else
634 delta = g->measured - g->average;
635 g->stddeviation += RA_FP_MUL(beta, delta);
636
637 splx(s);
638 }
639
640 void
ieee80211_ra_choose(struct ieee80211_ra_node * rn,struct ieee80211com * ic,struct ieee80211_node * ni)641 ieee80211_ra_choose(struct ieee80211_ra_node *rn, struct ieee80211com *ic,
642 struct ieee80211_node *ni)
643 {
644 struct ieee80211_ra_goodput_stats *g = &rn->g[ni->ni_txmcs];
645 int s;
646 int chan40 = ieee80211_node_supports_ht_chan40(ni);
647 int sgi = ieee80211_ra_use_ht_sgi(ni);
648 const struct ieee80211_ht_rateset *rs, *rsnext;
649
650 s = splnet();
651
652 if (rn->valid_rates == 0)
653 rn->valid_rates = ieee80211_ra_valid_rates(ic, ni);
654
655 if (rn->probing) {
656 /* Probe another rate or settle at the best rate. */
657 if (!(rn->valid_probes & (1UL << ni->ni_txmcs))) {
658 splx(s);
659 return;
660 }
661 ieee80211_ra_probe_clear(rn, ni);
662 if (!ieee80211_ra_intra_mode_ra_finished(rn, ni)) {
663 ieee80211_ra_probe_next_rate(rn, ni);
664 DPRINTFN(3, ("probing MCS %d\n", ni->ni_txmcs));
665 } else if (ieee80211_ra_inter_mode_ra_finished(rn, ni)) {
666 rn->best_mcs = ieee80211_ra_best_rate(rn, ni);
667 ni->ni_txmcs = rn->best_mcs;
668 ieee80211_ra_probe_done(rn);
669 }
670
671 splx(s);
672 return;
673 } else {
674 rn->valid_probes = 0;
675 }
676
677 rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, chan40, sgi);
678 if ((g->measured >> RA_FP_SHIFT) == 0LL ||
679 (g->average >= 3 * g->stddeviation &&
680 g->measured < g->average - 3 * g->stddeviation)) {
681 /* Channel becomes bad. Probe downwards. */
682 rn->probing = IEEE80211_RA_PROBING_DOWN;
683 rn->probed_rates = 0;
684 if (ni->ni_txmcs == rs->min_mcs) {
685 rsnext = ieee80211_ra_next_rateset(rn, ni);
686 if (rsnext) {
687 ieee80211_ra_probe_next_rateset(rn, ni,
688 rsnext);
689 } else {
690 /* Cannot probe further down. */
691 rn->probing = IEEE80211_RA_NOT_PROBING;
692 }
693 } else {
694 ni->ni_txmcs = ieee80211_ra_next_mcs(rn, ni);
695 rn->candidate_rates = (1 << ni->ni_txmcs);
696 }
697 } else if (g->loss < 2 * RA_FP_1 ||
698 g->measured > g->average + 3 * g->stddeviation) {
699 /* Channel becomes good. */
700 rn->probing = IEEE80211_RA_PROBING_UP;
701 rn->probed_rates = 0;
702 if (ni->ni_txmcs == rs->max_mcs) {
703 rsnext = ieee80211_ra_next_rateset(rn, ni);
704 if (rsnext) {
705 ieee80211_ra_probe_next_rateset(rn, ni,
706 rsnext);
707 } else {
708 /* Cannot probe further up. */
709 rn->probing = IEEE80211_RA_NOT_PROBING;
710 }
711 } else {
712 ni->ni_txmcs = ieee80211_ra_next_mcs(rn, ni);
713 rn->candidate_rates = (1 << ni->ni_txmcs);
714 }
715 } else {
716 /* Remain at current rate. */
717 rn->probing = IEEE80211_RA_NOT_PROBING;
718 rn->probed_rates = 0;
719 rn->candidate_rates = 0;
720 }
721
722 splx(s);
723
724 if (rn->probing) {
725 if (rn->probing & IEEE80211_RA_PROBING_UP)
726 DPRINTFN(2, ("channel becomes good; probe up\n"));
727 else
728 DPRINTFN(2, ("channel becomes bad; probe down\n"));
729
730 DPRINTFN(3, ("measured: %s Mbit/s\n",
731 ra_fp_sprintf(g->measured)));
732 DPRINTFN(3, ("average: %s Mbit/s\n",
733 ra_fp_sprintf(g->average)));
734 DPRINTFN(3, ("stddeviation: %s\n",
735 ra_fp_sprintf(g->stddeviation)));
736 DPRINTFN(3, ("loss: %s%%\n", ra_fp_sprintf(g->loss)));
737 }
738 }
739
740 void
ieee80211_ra_node_init(struct ieee80211_ra_node * rn)741 ieee80211_ra_node_init(struct ieee80211_ra_node *rn)
742 {
743 memset(rn, 0, sizeof(*rn));
744 }
745