1 /* $OpenBSD: ieee80211_amrr.c,v 1.1 2006/06/17 19:07:19 damien Exp $ */
2
3 /*-
4 * Copyright (c) 2010 Rui Paulo <rpaulo@FreeBSD.org>
5 * Copyright (c) 2006
6 * Damien Bergamini <damien.bergamini@free.fr>
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/cdefs.h>
22 /*-
23 * Naive implementation of the Adaptive Multi Rate Retry algorithm:
24 *
25 * "IEEE 802.11 Rate Adaptation: A Practical Approach"
26 * Mathieu Lacage, Hossein Manshaei, Thierry Turletti
27 * INRIA Sophia - Projet Planete
28 * http://www-sop.inria.fr/rapports/sophia/RR-5208.html
29 */
30 #include "opt_wlan.h"
31
32 #include <sys/param.h>
33 #include <sys/kernel.h>
34 #include <sys/malloc.h>
35 #include <sys/module.h>
36 #include <sys/sbuf.h>
37 #include <sys/socket.h>
38 #include <sys/sysctl.h>
39
40 #include <net/if.h>
41 #include <net/if_var.h>
42 #include <net/if_media.h>
43 #include <net/ethernet.h>
44
45 #ifdef INET
46 #include <netinet/in.h>
47 #include <netinet/if_ether.h>
48 #endif
49
50 #include <net80211/ieee80211_var.h>
51 #include <net80211/ieee80211_ht.h>
52 #include <net80211/ieee80211_amrr.h>
53 #include <net80211/ieee80211_ratectl.h>
54
55 #define is_success(amn) \
56 ((amn)->amn_retrycnt < (amn)->amn_txcnt / 10)
57 #define is_failure(amn) \
58 ((amn)->amn_retrycnt > (amn)->amn_txcnt / 3)
59 #define is_enough(amn) \
60 ((amn)->amn_txcnt > 10)
61
62 static void amrr_setinterval(const struct ieee80211vap *, int);
63 static void amrr_init(struct ieee80211vap *);
64 static void amrr_deinit(struct ieee80211vap *);
65 static void amrr_node_init(struct ieee80211_node *);
66 static void amrr_node_deinit(struct ieee80211_node *);
67 static int amrr_update(struct ieee80211_amrr *,
68 struct ieee80211_amrr_node *, struct ieee80211_node *);
69 static int amrr_rate(struct ieee80211_node *, void *, uint32_t);
70 static void amrr_tx_complete(const struct ieee80211_node *,
71 const struct ieee80211_ratectl_tx_status *);
72 static void amrr_tx_update_cb(void *, struct ieee80211_node *);
73 static void amrr_tx_update(struct ieee80211vap *vap,
74 struct ieee80211_ratectl_tx_stats *);
75 static void amrr_sysctlattach(struct ieee80211vap *,
76 struct sysctl_ctx_list *, struct sysctl_oid *);
77 static void amrr_node_stats(struct ieee80211_node *ni, struct sbuf *s);
78
79 /* number of references from net80211 layer */
80 static int nrefs = 0;
81
82 static const struct ieee80211_ratectl amrr = {
83 .ir_name = "amrr",
84 .ir_attach = NULL,
85 .ir_detach = NULL,
86 .ir_init = amrr_init,
87 .ir_deinit = amrr_deinit,
88 .ir_node_init = amrr_node_init,
89 .ir_node_deinit = amrr_node_deinit,
90 .ir_rate = amrr_rate,
91 .ir_tx_complete = amrr_tx_complete,
92 .ir_tx_update = amrr_tx_update,
93 .ir_setinterval = amrr_setinterval,
94 .ir_node_stats = amrr_node_stats,
95 };
96 IEEE80211_RATECTL_MODULE(amrr, 1);
97 IEEE80211_RATECTL_ALG(amrr, IEEE80211_RATECTL_AMRR, amrr);
98
99 static void
amrr_setinterval(const struct ieee80211vap * vap,int msecs)100 amrr_setinterval(const struct ieee80211vap *vap, int msecs)
101 {
102 struct ieee80211_amrr *amrr = vap->iv_rs;
103
104 if (!amrr)
105 return;
106
107 if (msecs < 100)
108 msecs = 100;
109 amrr->amrr_interval = msecs_to_ticks(msecs);
110 }
111
112 static void
amrr_init(struct ieee80211vap * vap)113 amrr_init(struct ieee80211vap *vap)
114 {
115 struct ieee80211_amrr *amrr;
116
117 KASSERT(vap->iv_rs == NULL, ("%s called multiple times", __func__));
118
119 nrefs++; /* XXX locking */
120 amrr = vap->iv_rs = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr),
121 M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
122 if (amrr == NULL) {
123 if_printf(vap->iv_ifp, "couldn't alloc ratectl structure\n");
124 return;
125 }
126 amrr->amrr_min_success_threshold = IEEE80211_AMRR_MIN_SUCCESS_THRESHOLD;
127 amrr->amrr_max_success_threshold = IEEE80211_AMRR_MAX_SUCCESS_THRESHOLD;
128 amrr_setinterval(vap, 500 /* ms */);
129 amrr_sysctlattach(vap, vap->iv_sysctl, vap->iv_oid);
130 }
131
132 static void
amrr_deinit(struct ieee80211vap * vap)133 amrr_deinit(struct ieee80211vap *vap)
134 {
135 KASSERT(nrefs > 0, ("imbalanced attach/detach"));
136 IEEE80211_FREE(vap->iv_rs, M_80211_RATECTL);
137 vap->iv_rs = NULL; /* guard */
138 nrefs--; /* XXX locking */
139 }
140
141 static void
amrr_node_init(struct ieee80211_node * ni)142 amrr_node_init(struct ieee80211_node *ni)
143 {
144 const struct ieee80211_rateset *rs = NULL;
145 struct ieee80211vap *vap = ni->ni_vap;
146 struct ieee80211_amrr *amrr = vap->iv_rs;
147 struct ieee80211_amrr_node *amn;
148 uint8_t rate;
149
150 if (!amrr) {
151 if_printf(vap->iv_ifp, "ratectl structure was not allocated, "
152 "per-node structure allocation skipped\n");
153 return;
154 }
155
156 if (ni->ni_rctls == NULL) {
157 ni->ni_rctls = amn = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr_node),
158 M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
159 if (amn == NULL) {
160 if_printf(vap->iv_ifp, "couldn't alloc per-node ratectl "
161 "structure\n");
162 return;
163 }
164 } else
165 amn = ni->ni_rctls;
166 amn->amn_amrr = amrr;
167 amn->amn_success = 0;
168 amn->amn_recovery = 0;
169 amn->amn_txcnt = amn->amn_retrycnt = 0;
170 amn->amn_success_threshold = amrr->amrr_min_success_threshold;
171
172 /* 11n or not? Pick the right rateset */
173 if (ieee80211_ht_check_tx_ht(ni)) {
174 /* XXX ew */
175 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
176 "%s: 11n node", __func__);
177 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
178 } else {
179 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
180 "%s: non-11n node", __func__);
181 rs = &ni->ni_rates;
182 }
183
184 /* Initial rate - lowest */
185 rate = rs->rs_rates[0];
186
187 /* XXX clear the basic rate flag if it's not 11n */
188 if (! ieee80211_ht_check_tx_ht(ni))
189 rate &= IEEE80211_RATE_VAL;
190
191 /* pick initial rate from the rateset - HT or otherwise */
192 /* Pick something low that's likely to succeed */
193 for (amn->amn_rix = rs->rs_nrates - 1; amn->amn_rix > 0;
194 amn->amn_rix--) {
195 /* legacy - anything < 36mbit, stop searching */
196 /* 11n - stop at MCS4 */
197 if (ieee80211_ht_check_tx_ht(ni)) {
198 if ((rs->rs_rates[amn->amn_rix] & 0x1f) < 4)
199 break;
200 } else if ((rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL) <= 72)
201 break;
202 }
203 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
204
205 /* if the rate is an 11n rate, ensure the MCS bit is set */
206 if (ieee80211_ht_check_tx_ht(ni))
207 rate |= IEEE80211_RATE_MCS;
208
209 /* Assign initial rate from the rateset */
210 ni->ni_txrate = rate;
211 amn->amn_ticks = ticks;
212
213 /* XXX TODO: we really need a rate-to-string method */
214 /* XXX TODO: non-11n rate should be divided by two.. */
215 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
216 "AMRR: nrates=%d, initial rate %s%d",
217 rs->rs_nrates,
218 ieee80211_ht_check_tx_ht(ni) ? "MCS " : "",
219 rate & IEEE80211_RATE_VAL);
220 }
221
222 static void
amrr_node_deinit(struct ieee80211_node * ni)223 amrr_node_deinit(struct ieee80211_node *ni)
224 {
225 IEEE80211_FREE(ni->ni_rctls, M_80211_RATECTL);
226 }
227
228 static int
amrr_update(struct ieee80211_amrr * amrr,struct ieee80211_amrr_node * amn,struct ieee80211_node * ni)229 amrr_update(struct ieee80211_amrr *amrr, struct ieee80211_amrr_node *amn,
230 struct ieee80211_node *ni)
231 {
232 int rix = amn->amn_rix;
233 const struct ieee80211_rateset *rs = NULL;
234
235 KASSERT(is_enough(amn), ("txcnt %d", amn->amn_txcnt));
236
237 /* 11n or not? Pick the right rateset */
238 if (ieee80211_ht_check_tx_ht(ni)) {
239 /* XXX ew */
240 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
241 } else {
242 rs = &ni->ni_rates;
243 }
244
245 /* XXX TODO: we really need a rate-to-string method */
246 /* XXX TODO: non-11n rate should be divided by two.. */
247 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
248 "AMRR: current rate %d, txcnt=%d, retrycnt=%d",
249 rs->rs_rates[rix] & IEEE80211_RATE_VAL,
250 amn->amn_txcnt,
251 amn->amn_retrycnt);
252
253 /*
254 * XXX This is totally bogus for 11n, as although high MCS
255 * rates for each stream may be failing, the next stream
256 * should be checked.
257 *
258 * Eg, if MCS5 is ok but MCS6/7 isn't, and we can go up to
259 * MCS23, we should skip 6/7 and try 8 onwards.
260 */
261 if (is_success(amn)) {
262 amn->amn_success++;
263 if (amn->amn_success >= amn->amn_success_threshold &&
264 rix + 1 < rs->rs_nrates) {
265 amn->amn_recovery = 1;
266 amn->amn_success = 0;
267 rix++;
268 /* XXX TODO: we really need a rate-to-string method */
269 /* XXX TODO: non-11n rate should be divided by two.. */
270 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
271 "AMRR increasing rate %d (txcnt=%d retrycnt=%d)",
272 rs->rs_rates[rix] & IEEE80211_RATE_VAL,
273 amn->amn_txcnt, amn->amn_retrycnt);
274 } else {
275 amn->amn_recovery = 0;
276 }
277 } else if (is_failure(amn)) {
278 amn->amn_success = 0;
279 if (rix > 0) {
280 if (amn->amn_recovery) {
281 amn->amn_success_threshold *= 2;
282 if (amn->amn_success_threshold >
283 amrr->amrr_max_success_threshold)
284 amn->amn_success_threshold =
285 amrr->amrr_max_success_threshold;
286 } else {
287 amn->amn_success_threshold =
288 amrr->amrr_min_success_threshold;
289 }
290 rix--;
291 /* XXX TODO: we really need a rate-to-string method */
292 /* XXX TODO: non-11n rate should be divided by two.. */
293 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
294 "AMRR decreasing rate %d (txcnt=%d retrycnt=%d)",
295 rs->rs_rates[rix] & IEEE80211_RATE_VAL,
296 amn->amn_txcnt, amn->amn_retrycnt);
297 }
298 amn->amn_recovery = 0;
299 }
300
301 /* reset counters */
302 amn->amn_txcnt = 0;
303 amn->amn_retrycnt = 0;
304
305 return rix;
306 }
307
308 /*
309 * Return the rate index to use in sending a data frame.
310 * Update our internal state if it's been long enough.
311 * If the rate changes we also update ni_txrate to match.
312 */
313 static int
amrr_rate(struct ieee80211_node * ni,void * arg __unused,uint32_t iarg __unused)314 amrr_rate(struct ieee80211_node *ni, void *arg __unused, uint32_t iarg __unused)
315 {
316 struct ieee80211_amrr_node *amn = ni->ni_rctls;
317 struct ieee80211_amrr *amrr;
318 const struct ieee80211_rateset *rs = NULL;
319 int rix;
320
321 /* XXX should return -1 here, but drivers may not expect this... */
322 if (!amn)
323 {
324 ni->ni_txrate = ni->ni_rates.rs_rates[0];
325 return 0;
326 }
327
328 amrr = amn->amn_amrr;
329
330 /* 11n or not? Pick the right rateset */
331 if (ieee80211_ht_check_tx_ht(ni)) {
332 /* XXX ew */
333 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
334 } else {
335 rs = &ni->ni_rates;
336 }
337
338 if (is_enough(amn) && (ticks - amn->amn_ticks) > amrr->amrr_interval) {
339 rix = amrr_update(amrr, amn, ni);
340 if (rix != amn->amn_rix) {
341 /* update public rate */
342 ni->ni_txrate = rs->rs_rates[rix];
343 /* XXX strip basic rate flag from txrate, if non-11n */
344 if (ieee80211_ht_check_tx_ht(ni))
345 ni->ni_txrate |= IEEE80211_RATE_MCS;
346 else
347 ni->ni_txrate &= IEEE80211_RATE_VAL;
348 amn->amn_rix = rix;
349 }
350 amn->amn_ticks = ticks;
351 } else
352 rix = amn->amn_rix;
353 return rix;
354 }
355
356 /*
357 * Update statistics with tx complete status. Ok is non-zero
358 * if the packet is known to be ACK'd. Retries has the number
359 * retransmissions (i.e. xmit attempts - 1).
360 */
361 static void
amrr_tx_complete(const struct ieee80211_node * ni,const struct ieee80211_ratectl_tx_status * status)362 amrr_tx_complete(const struct ieee80211_node *ni,
363 const struct ieee80211_ratectl_tx_status *status)
364 {
365 struct ieee80211_amrr_node *amn = ni->ni_rctls;
366 int retries;
367
368 if (!amn)
369 return;
370
371 retries = 0;
372 if (status->flags & IEEE80211_RATECTL_STATUS_LONG_RETRY)
373 retries = status->long_retries;
374
375 amn->amn_txcnt++;
376 if (status->status == IEEE80211_RATECTL_TX_SUCCESS)
377 amn->amn_success++;
378 amn->amn_retrycnt += retries;
379 }
380
381 static void
amrr_tx_update_cb(void * arg,struct ieee80211_node * ni)382 amrr_tx_update_cb(void *arg, struct ieee80211_node *ni)
383 {
384 struct ieee80211_ratectl_tx_stats *stats = arg;
385 struct ieee80211_amrr_node *amn = ni->ni_rctls;
386 int txcnt, success, retrycnt;
387
388 if (!amn)
389 return;
390
391 txcnt = stats->nframes;
392 success = stats->nsuccess;
393 retrycnt = 0;
394 if (stats->flags & IEEE80211_RATECTL_TX_STATS_RETRIES)
395 retrycnt = stats->nretries;
396
397 amn->amn_txcnt += txcnt;
398 amn->amn_success += success;
399 amn->amn_retrycnt += retrycnt;
400 }
401
402 /*
403 * Set tx count/retry statistics explicitly. Intended for
404 * drivers that poll the device for statistics maintained
405 * in the device.
406 */
407 static void
amrr_tx_update(struct ieee80211vap * vap,struct ieee80211_ratectl_tx_stats * stats)408 amrr_tx_update(struct ieee80211vap *vap,
409 struct ieee80211_ratectl_tx_stats *stats)
410 {
411
412 if (stats->flags & IEEE80211_RATECTL_TX_STATS_NODE)
413 amrr_tx_update_cb(stats, stats->ni);
414 else {
415 ieee80211_iterate_nodes_vap(&vap->iv_ic->ic_sta, vap,
416 amrr_tx_update_cb, stats);
417 }
418 }
419
420 static int
amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)421 amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)
422 {
423 struct ieee80211vap *vap = arg1;
424 struct ieee80211_amrr *amrr = vap->iv_rs;
425 int msecs, error;
426
427 if (!amrr)
428 return ENOMEM;
429
430 msecs = ticks_to_msecs(amrr->amrr_interval);
431 error = sysctl_handle_int(oidp, &msecs, 0, req);
432 if (error || !req->newptr)
433 return error;
434 amrr_setinterval(vap, msecs);
435 return 0;
436 }
437
438 static void
amrr_sysctlattach(struct ieee80211vap * vap,struct sysctl_ctx_list * ctx,struct sysctl_oid * tree)439 amrr_sysctlattach(struct ieee80211vap *vap,
440 struct sysctl_ctx_list *ctx, struct sysctl_oid *tree)
441 {
442 struct ieee80211_amrr *amrr = vap->iv_rs;
443
444 if (!amrr)
445 return;
446
447 SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
448 "amrr_rate_interval", CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
449 vap, 0, amrr_sysctl_interval, "I", "amrr operation interval (ms)");
450 /* XXX bounds check values */
451 SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
452 "amrr_max_sucess_threshold", CTLFLAG_RW,
453 &amrr->amrr_max_success_threshold, 0, "");
454 SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
455 "amrr_min_sucess_threshold", CTLFLAG_RW,
456 &amrr->amrr_min_success_threshold, 0, "");
457 }
458
459 static void
amrr_print_node_rate(struct ieee80211_amrr_node * amn,struct ieee80211_node * ni,struct sbuf * s)460 amrr_print_node_rate(struct ieee80211_amrr_node *amn,
461 struct ieee80211_node *ni, struct sbuf *s)
462 {
463 int rate;
464 struct ieee80211_rateset *rs;
465
466 if (ieee80211_ht_check_tx_ht(ni)) {
467 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
468 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
469 sbuf_printf(s, "rate: MCS %d\n", rate);
470 } else {
471 rs = &ni->ni_rates;
472 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
473 sbuf_printf(s, "rate: %d Mbit\n", rate / 2);
474 }
475 }
476
477 static void
amrr_node_stats(struct ieee80211_node * ni,struct sbuf * s)478 amrr_node_stats(struct ieee80211_node *ni, struct sbuf *s)
479 {
480 struct ieee80211_amrr_node *amn = ni->ni_rctls;
481
482 /* XXX TODO: check locking? */
483
484 if (!amn)
485 return;
486
487 amrr_print_node_rate(amn, ni, s);
488 sbuf_printf(s, "ticks: %d\n", amn->amn_ticks);
489 sbuf_printf(s, "txcnt: %u\n", amn->amn_txcnt);
490 sbuf_printf(s, "success: %u\n", amn->amn_success);
491 sbuf_printf(s, "success_threshold: %u\n", amn->amn_success_threshold);
492 sbuf_printf(s, "recovery: %u\n", amn->amn_recovery);
493 sbuf_printf(s, "retry_cnt: %u\n", amn->amn_retrycnt);
494 }
495