Do proper locking in the callout functions.
[dragonfly.git] / sys / netproto / 802_11 / wlan_ratectl / amrr / ieee80211_ratectl_amrr.c
1 /*
2  * Copyright (c) 2004 INRIA
3  * Copyright (c) 2002-2005 Sam Leffler, Errno Consulting
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer,
11  *    without modification.
12  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
13  *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
14  *    redistribution must be conditioned upon including a substantially
15  *    similar Disclaimer requirement for further binary redistribution.
16  * 3. Neither the names of the above-listed copyright holders nor the names
17  *    of any contributors may be used to endorse or promote products derived
18  *    from this software without specific prior written permission.
19  *
20  * Alternatively, this software may be distributed under the terms of the
21  * GNU General Public License ("GPL") version 2 as published by the Free
22  * Software Foundation.
23  *
24  * NO WARRANTY
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
28  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
29  * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
30  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
33  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35  * THE POSSIBILITY OF SUCH DAMAGES.
36  *
37  * $FreeBSD: src/sys/dev/ath/ath_rate/amrr/amrr.c,v 1.8.2.3 2006/02/24 19:51:11 sam Exp $
38  * $DragonFly: src/sys/netproto/802_11/wlan_ratectl/amrr/ieee80211_ratectl_amrr.c,v 1.11 2008/01/15 09:01:13 sephe Exp $
39  */
40
41 /*
42  * AMRR rate control. See:
43  * http://www-sop.inria.fr/rapports/sophia/RR-5208.html
44  * "IEEE 802.11 Rate Adaptation: A Practical Approach" by
45  *    Mathieu Lacage, Hossein Manshaei, Thierry Turletti
46  */
47
48 #include <sys/param.h>
49 #include <sys/kernel.h>
50 #include <sys/malloc.h>
51 #include <sys/module.h>
52 #include <sys/sysctl.h>
53 #include <sys/serialize.h>
54
55 #include <net/if.h>
56 #include <net/if_media.h>
57 #include <net/if_arp.h>
58
59 #include <netproto/802_11/ieee80211_var.h>
60 #include <netproto/802_11/wlan_ratectl/amrr/ieee80211_amrr_param.h>
61
62 #define AMRR_DEBUG
63 #ifdef AMRR_DEBUG
64 #define DPRINTF(asc, lv, fmt, ...) do {         \
65         if ((asc)->param->amrr_debug >= lv)     \
66                 kprintf(fmt, __VA_ARGS__);      \
67 } while (0)
68 #else
69 #define DPRINTF(asc, lv, fmt, ...)
70 #endif
71
72 struct amrr_softc {
73         struct ieee80211vap     *vap;
74         struct callout          timer;          /* periodic timer */
75         struct sysctl_ctx_list  sysctl_ctx;
76         struct sysctl_oid       *sysctl_oid;
77
78         struct ieee80211_amrr_param *param;
79 #define max_success_threshold   param->amrr_max_success_threshold
80 #define min_success_threshold   param->amrr_min_success_threshold
81 };
82
83 struct amrr_data {
84         /* AMRR statistics for this node */
85         u_int   ad_tx_cnt;
86         u_int   ad_tx_failure_cnt;
87
88         /* AMRR algorithm state for this node */
89         u_int   ad_success_threshold;
90         u_int   ad_success;
91         u_int   ad_recovery;
92 };
93
94 static void     *amrr_attach(struct ieee80211vap *);
95 static void     amrr_detach(void *);
96 static void     amrr_data_alloc(struct ieee80211_node *);
97 static void     amrr_data_free(struct ieee80211_node *);
98 static void     amrr_data_dup(const struct ieee80211_node *,
99                               struct ieee80211_node *);
100 static void     amrr_newstate(void *, enum ieee80211_state);
101 static void     amrr_tx_complete(void *, struct ieee80211_node *, int,
102                                  const struct ieee80211_ratectl_res[],
103                                  int, int, int, int);
104 static void     amrr_newassoc(void *, struct ieee80211_node *, int);
105 static int      amrr_findrate(void *, struct ieee80211_node *, int,
106                               int[], int);
107
108 static void     amrr_sysctl_attach(struct amrr_softc *);
109 static void     amrr_update(struct amrr_softc *, struct ieee80211_node *, int);
110 static void     amrr_start(struct amrr_softc *, struct ieee80211_node *);
111 static void     amrr_tick(void *);
112 static void     amrr_ratectl(void *, struct ieee80211_node *);
113 static void     amrr_gather_stats(struct amrr_softc *, struct ieee80211_node *);
114
115 static const struct ieee80211_ratectl amrr = {
116         .rc_name        = "amrr",
117         .rc_ratectl     = IEEE80211_RATECTL_AMRR,
118         .rc_attach      = amrr_attach,
119         .rc_detach      = amrr_detach,
120         .rc_data_alloc  = amrr_data_alloc,
121         .rc_data_free   = amrr_data_free,
122         .rc_data_dup    = amrr_data_dup,
123         .rc_newstate    = amrr_newstate,
124         .rc_tx_complete = amrr_tx_complete,
125         .rc_newassoc    = amrr_newassoc,
126         .rc_findrate    = amrr_findrate
127 };
128
129 static u_int    amrr_nrefs;
130
131 MALLOC_DEFINE(M_AMRR_RATECTL_DATA, "amrr_ratectl_data",
132               "amrr rate control data");
133
134 static int
135 amrr_findrate(void *arg, struct ieee80211_node *ni,
136               int frame_len __unused, int rateidx[], int rateidx_len)
137 {
138         struct amrr_softc *asc = arg;
139         int i, rate_idx;
140
141         if (ni->ni_txrate >= ni->ni_rates.rs_nrates) {
142                 DPRINTF(asc, 5, "%s: number of rates changed, restart\n",
143                         __func__);
144                 amrr_start(asc, ni);
145         }
146         rate_idx = ni->ni_txrate;
147
148         for (i = 0; i < rateidx_len; ++i) {
149                 if (rate_idx < 0)
150                         break;
151                 rateidx[i] = rate_idx--;
152         }
153         if (rateidx_len > 1)
154                 rateidx[rateidx_len - 1] = 0;
155         return i;
156 }
157
158 static void
159 amrr_tx_complete(void *arg __unused, struct ieee80211_node *ni,
160                  int frame_len __unused,
161                  const struct ieee80211_ratectl_res res[],
162                  int res_len, int data_retries __unused,
163                  int rts_retries __unused, int is_fail)
164 {
165         struct amrr_data *ad = ni->ni_rate_data;
166         u_int total_tries;
167         int i;
168
169         if (ad == NULL)
170                 return;
171
172         total_tries = 0;
173         for (i = 0; i < res_len; ++i)
174                 total_tries += res[i].rc_res_tries;
175         ad->ad_tx_cnt += total_tries;
176
177         ad->ad_tx_failure_cnt += total_tries;
178         if (res_len == 1 && !is_fail) {
179                 KKASSERT(ad->ad_tx_failure_cnt != 0);
180                 /* One packet is successfully transmitted at desired rate */
181                 ad->ad_tx_failure_cnt--;
182         }
183 }
184
185 static void
186 amrr_newassoc(void *arg, struct ieee80211_node *ni, int isnew)
187 {
188         if (isnew)
189                 amrr_start(arg, ni);
190 }
191
192 /*
193  * The code below assumes that we are dealing with hardware multi rate retry
194  * I have no idea what will happen if you try to use this module with another
195  * type of hardware. Your machine might catch fire or it might work with
196  * horrible performance...
197  */
198 static void
199 amrr_update(struct amrr_softc *asc, struct ieee80211_node *ni, int rate)
200 {
201         struct amrr_data *ad = ni->ni_rate_data;
202
203         DPRINTF(asc, 5, "%s: set xmit rate for %6D to %dM\n",
204                 __func__, ni->ni_macaddr, ":",
205                 ni->ni_rates.rs_nrates > 0 ?
206                 IEEE80211_RS_RATE(&ni->ni_rates, rate) / 2 : 0);
207
208         ni->ni_txrate = rate;
209
210         if (ad == NULL) {
211                 amrr_data_alloc(ni);
212                 ad = ni->ni_rate_data;
213                 if (ad == NULL)
214                         return;
215         }
216
217         ad->ad_tx_cnt = 0;
218         ad->ad_tx_failure_cnt = 0;
219         ad->ad_success = 0;
220         ad->ad_recovery = 0;
221         ad->ad_success_threshold = asc->min_success_threshold;
222 }
223
224 /*
225  * Set the starting transmit rate for a node.
226  */
227 static void
228 amrr_start(struct amrr_softc *asc, struct ieee80211_node *ni)
229 {
230 #define RATE(_ix)       IEEE80211_RS_RATE(&ni->ni_rates, (_ix))
231         struct ieee80211vap *vap = asc->vap;
232         int srate;
233         const struct ieee80211_txparam *tp = ni->ni_txparms;
234         enum ieee80211_phymode mode =
235             ieee80211_chan2mode(vap->iv_ic->ic_curchan);
236
237         KASSERT(ni->ni_rates.rs_nrates > 0, ("no rates"));
238
239         if (tp == NULL || tp->ucastrate == IEEE80211_FIXED_RATE_NONE) {
240                 /*
241                  * For adhoc or ibss mode, start from the lowest rate.
242                  */
243                 if (vap->iv_opmode == IEEE80211_M_AHDEMO ||
244                     vap->iv_opmode == IEEE80211_M_IBSS) {
245                         amrr_update(asc, ni, 0);
246                         return;
247                 }
248
249                 /*
250                  * No fixed rate is requested. For 11b start with
251                  * the highest negotiated rate; otherwise, for 11g
252                  * and 11a, we start "in the middle" at 24Mb or 36Mb.
253                  */
254                 srate = ni->ni_rates.rs_nrates - 1;
255                 if (mode != IEEE80211_MODE_11B) {
256                         /*
257                          * Scan the negotiated rate set to find the
258                          * closest rate.
259                          */
260                         /* NB: the rate set is assumed sorted */
261                         for (; srate >= 0 && RATE(srate) > 72; srate--)
262                                 ;
263                         KASSERT(srate >= 0, ("bogus rate set"));
264                 }
265         } else {
266                 /*
267                  * A fixed rate is to be used; ucastrate is an
268                  * index into the supported rate set.  Convert this
269                  * to the index into the negotiated rate set for
270                  * the node.  We know the rate is there because the
271                  * rate set is checked when the station associates.
272                  */
273                 const struct ieee80211_rateset *rs =
274                         &vap->iv_ic->ic_sup_rates[vap->iv_ic->ic_curmode];
275                 int r = IEEE80211_RS_RATE(rs, vap->iv_txparms[mode].ucastrate);
276
277                 /* NB: the rate set is assumed sorted */
278                 srate = ni->ni_rates.rs_nrates - 1;
279                 for (; srate >= 0 && RATE(srate) != r; srate--)
280                         ;
281                 KASSERT(srate >= 0,
282                         ("fixed rate %d not in rate set", tp->ucastrate));
283         }
284         amrr_update(asc, ni, srate);
285 #undef RATE
286 }
287
288 static void
289 amrr_rate_cb(void *arg, struct ieee80211_node *ni)
290 {
291         amrr_update(arg, ni, 0);
292 }
293
294 /*
295  * Reset the rate control state for each 802.11 state transition.
296  */
297 static void
298 amrr_newstate(void *arg, enum ieee80211_state state)
299 {
300         struct amrr_softc *asc = arg;
301         struct ieee80211vap *vap = asc->vap;
302         struct ieee80211_node *ni;
303         const struct ieee80211_txparam *tp = NULL;
304
305         if (state == IEEE80211_S_INIT) {
306                 callout_stop(&asc->timer);
307                 return;
308         }
309
310         if (vap->iv_opmode == IEEE80211_M_STA) {
311                 /*
312                  * Reset local xmit state; this is really only
313                  * meaningful when operating in station mode.
314                  */
315                 ni = vap->iv_bss;
316                 tp = ni->ni_txparms;
317                 if (state == IEEE80211_S_RUN)
318                         amrr_start(asc, ni);
319                 else
320                         amrr_update(asc, ni, 0);
321         } else {
322                 /*
323                  * When operating as a station the node table holds
324                  * the AP's that were discovered during scanning.
325                  * For any other operating mode we want to reset the
326                  * tx rate state of each node.
327                  */
328                 ieee80211_iterate_nodes(&vap->iv_ic->ic_sta, amrr_rate_cb, asc);
329                 amrr_update(asc, vap->iv_bss, 0);
330         }
331         if ((tp == NULL || tp->ucastrate == IEEE80211_FIXED_RATE_NONE) &&
332             state == IEEE80211_S_RUN) {
333                 int interval;
334
335                 /*
336                  * Start the background rate control thread if we
337                  * are not configured to use a fixed xmit rate.
338                  */
339                 interval = asc->param->amrr_interval;
340                 if (vap->iv_opmode == IEEE80211_M_STA)
341                         interval /= 2;
342                 callout_reset(&asc->timer, (interval * hz) / 1000,
343                               amrr_tick, asc);
344         }
345 }
346
347 static void
348 amrr_gather_stats(struct amrr_softc *asc, struct ieee80211_node *ni)
349 {
350         struct ieee80211vap *vap = asc->vap;
351         const struct ieee80211_ratectl_state *st = &vap->iv_ratectl;
352         struct amrr_data *ad = ni->ni_rate_data;
353         struct ieee80211_ratectl_stats stats;
354         u_int total_tries = 0;
355
356         st->rc_st_stats(vap, ni, &stats);
357
358         total_tries = stats.stats_pkt_ok +
359                       stats.stats_pkt_err +
360                       stats.stats_retries;
361
362         ad->ad_tx_cnt += total_tries;
363         ad->ad_tx_failure_cnt += (total_tries - stats.stats_pkt_noretry);
364 }
365
366 /* 
367  * Examine and potentially adjust the transmit rate.
368  */
369 static void
370 amrr_ratectl(void *arg, struct ieee80211_node *ni)
371 {
372         struct amrr_softc *asc = arg;
373         const struct ieee80211_ratectl_state *st = &asc->vap->iv_ratectl;
374         struct amrr_data *ad = ni->ni_rate_data;
375         int old_rate;
376
377         if (ad == NULL) {
378                 /* We are not ready to go, set TX rate to lowest one */
379                 ni->ni_txrate = 0;
380                 return;
381         }
382
383 #define is_success(ad)  (ad->ad_tx_failure_cnt < (ad->ad_tx_cnt / 10))
384 #define is_enough(ad)   (ad->ad_tx_cnt > 10)
385 #define is_failure(ad)  (ad->ad_tx_failure_cnt > (ad->ad_tx_cnt / 3))
386 #define is_max_rate(ni) ((ni->ni_txrate + 1) >= ni->ni_rates.rs_nrates)
387 #define is_min_rate(ni) (ni->ni_txrate == 0)
388
389         old_rate = ni->ni_txrate;
390
391         if (st->rc_st_stats != NULL)
392                 amrr_gather_stats(asc, ni);
393   
394         DPRINTF(asc, 10, "tx_cnt: %u tx_failure_cnt: %u -- "
395                 "threshold: %d\n",
396                 ad->ad_tx_cnt, ad->ad_tx_failure_cnt,
397                 ad->ad_success_threshold);
398
399         if (is_success(ad) && is_enough(ad)) {
400                 ad->ad_success++;
401                 if (ad->ad_success == ad->ad_success_threshold &&
402                     !is_max_rate(ni)) {
403                         ad->ad_recovery = 1;
404                         ad->ad_success = 0;
405                         ni->ni_txrate++;
406                         DPRINTF(asc, 5, "increase rate to %d\n", ni->ni_txrate);
407                 } else {
408                         ad->ad_recovery = 0;
409                 }
410         } else if (is_failure(ad)) {
411                 ad->ad_success = 0;
412                 if (!is_min_rate(ni)) {
413                         if (ad->ad_recovery) {
414                                 /* recovery failure. */
415                                 ad->ad_success_threshold *= 2;
416                                 ad->ad_success_threshold =
417                                         min(ad->ad_success_threshold,
418                                             (u_int)asc->max_success_threshold);
419                                 DPRINTF(asc, 5, "decrease rate recovery thr: "
420                                         "%d\n", ad->ad_success_threshold);
421                         } else {
422                                 /* simple failure. */
423                                 ad->ad_success_threshold =
424                                         asc->min_success_threshold;
425                                 DPRINTF(asc, 5, "decrease rate normal thr: "
426                                         "%d\n", ad->ad_success_threshold);
427                         }
428                         ad->ad_recovery = 0;
429                         ni->ni_txrate--;
430                 } else {
431                         ad->ad_recovery = 0;
432                 }
433         }
434         if (is_enough(ad) || old_rate != ni->ni_txrate) {
435                 /* reset counters. */
436                 ad->ad_tx_cnt = 0;
437                 ad->ad_tx_failure_cnt = 0;
438         }
439         if (old_rate != ni->ni_txrate)
440                 amrr_update(asc, ni, ni->ni_txrate);
441 }
442
443 static void
444 amrr_tick(void *arg)
445 {
446         struct amrr_softc *asc = arg;
447         struct ieee80211vap *vap = asc->vap;
448         struct ifnet *ifp = vap->iv_ifp;
449         int interval;
450
451         ifnet_serialize_all(ifp);
452
453         if (ifp->if_flags & IFF_RUNNING) {
454                 if (vap->iv_opmode == IEEE80211_M_STA)
455                         amrr_ratectl(asc, vap->iv_bss); /* NB: no reference */
456                 else
457                         ieee80211_iterate_nodes(&vap->iv_ic->ic_sta,
458                             amrr_ratectl, asc);
459         }
460         interval = asc->param->amrr_interval;
461         if (vap->iv_opmode == IEEE80211_M_STA)
462                 interval /= 2;
463         callout_reset(&asc->timer, (interval * hz) / 1000, amrr_tick, asc);
464
465         ifnet_deserialize_all(ifp);
466 }
467
468 static void
469 amrr_sysctl_attach(struct amrr_softc *asc)
470 {
471         sysctl_ctx_init(&asc->sysctl_ctx);
472         asc->sysctl_oid = SYSCTL_ADD_NODE(&asc->sysctl_ctx,
473                 SYSCTL_CHILDREN(asc->vap->iv_oid),
474                 OID_AUTO, "amrr_ratectl", CTLFLAG_RD, 0, "");
475         if (asc->sysctl_oid == NULL) {
476                 kprintf("wlan_ratectl_amrr: create sysctl tree failed\n");
477                 return;
478         }
479
480         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
481                        OID_AUTO, "interval", CTLFLAG_RW,
482                        &asc->param->amrr_interval, 0,
483                        "rate control: operation interval (ms)");
484
485         /* XXX bounds check values */
486         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
487                        OID_AUTO, "max_sucess_threshold", CTLFLAG_RW,
488                        &asc->param->amrr_max_success_threshold, 0, "");
489
490         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
491                        OID_AUTO, "min_sucess_threshold", CTLFLAG_RW,
492                        &asc->param->amrr_min_success_threshold, 0, "");
493
494         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
495                        OID_AUTO, "debug", CTLFLAG_RW,
496                        &asc->param->amrr_debug, 0, "debug level");
497 }
498
499 static void *
500 amrr_attach(struct ieee80211vap *vap)
501 {
502         struct amrr_softc *asc;
503
504         amrr_nrefs++;
505
506         asc = kmalloc(sizeof(struct amrr_softc), M_DEVBUF, M_WAITOK | M_ZERO);
507
508         asc->vap = vap;
509         callout_init(&asc->timer);
510         asc->param = vap->iv_ratectl.rc_st_attach(vap, IEEE80211_RATECTL_AMRR);
511
512         amrr_sysctl_attach(asc);
513
514         amrr_newstate(asc, vap->iv_state);
515
516         return asc;
517 }
518
519 static void
520 _amrr_data_free(void *arg __unused, struct ieee80211_node *ni)
521 {
522         amrr_data_free(ni);
523 }
524
525 void
526 amrr_detach(void *arg)
527 {
528         struct amrr_softc *asc = arg;
529         struct ieee80211vap *vap = asc->vap;
530
531         amrr_newstate(asc, IEEE80211_S_INIT);
532
533         ieee80211_iterate_nodes(&vap->iv_ic->ic_sta, _amrr_data_free, NULL);
534
535         if (asc->sysctl_oid != NULL)
536                 sysctl_ctx_free(&asc->sysctl_ctx);
537         kfree(asc, M_DEVBUF);
538
539         amrr_nrefs--;
540 }
541
542 static void
543 amrr_data_free(struct ieee80211_node *ni)
544 {
545         if (ni->ni_rate_data != NULL) {
546                 kfree(ni->ni_rate_data, M_AMRR_RATECTL_DATA);
547                 ni->ni_rate_data = NULL;
548         }
549 }
550
551 static void
552 amrr_data_alloc(struct ieee80211_node *ni)
553 {
554         KKASSERT(ni->ni_rate_data == NULL);
555         ni->ni_rate_data = kmalloc(sizeof(struct amrr_data),
556                                   M_AMRR_RATECTL_DATA, M_NOWAIT | M_ZERO);
557 }
558
559 static void
560 amrr_data_dup(const struct ieee80211_node *oni, struct ieee80211_node *nni)
561 {
562         if (oni->ni_rate_data == NULL || nni->ni_rate_data == NULL)
563                 return;
564
565         bcopy(oni->ni_rate_data, nni->ni_rate_data, sizeof(struct amrr_data));
566 }
567
568 /*
569  * Module glue.
570  */
571 static int
572 amrr_modevent(module_t mod, int type, void *unused)
573 {
574         switch (type) {
575         case MOD_LOAD:
576                 ieee80211_ratectl_register(&amrr);
577                 return 0;
578         case MOD_UNLOAD:
579                 if (amrr_nrefs) {
580                         kprintf("wlan_ratectl_amrr: still in use "
581                                "(%u dynamic refs)\n", amrr_nrefs);
582                         return EBUSY;
583                 }
584                 ieee80211_ratectl_unregister(&amrr);
585                 return 0;
586         }
587         return EINVAL;
588 }
589
590 static moduledata_t amrr_mod = {
591         "wlan_ratectl_amrr",
592         amrr_modevent,
593         0
594 };
595 DECLARE_MODULE(wlan_ratectl_amrr, amrr_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
596 MODULE_VERSION(wlan_ratectl_amrr, 1);
597 MODULE_DEPEND(wlan_ratectl_amrr, wlan, 1, 1, 1);