Merge from vendor branch LIBPCAP:
[dragonfly.git] / sys / netproto / 802_11 / wlan_ratectl / onoe / ieee80211_ratectl_onoe.c
1 /*
2  * Copyright (c) 2002-2005 Sam Leffler, Errno Consulting
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer,
10  *    without modification.
11  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
12  *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
13  *    redistribution must be conditioned upon including a substantially
14  *    similar Disclaimer requirement for further binary redistribution.
15  * 3. Neither the names of the above-listed copyright holders nor the names
16  *    of any contributors may be used to endorse or promote products derived
17  *    from this software without specific prior written permission.
18  *
19  * Alternatively, this software may be distributed under the terms of the
20  * GNU General Public License ("GPL") version 2 as published by the Free
21  * Software Foundation.
22  *
23  * NO WARRANTY
24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26  * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
27  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
28  * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
29  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
32  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
34  * THE POSSIBILITY OF SUCH DAMAGES.
35  *
36  * $FreeBSD: src/sys/dev/ath/ath_rate/onoe/onoe.c,v 1.8.2.3 2006/02/24 19:51:11 sam Exp $
37  * $DragonFly: src/sys/netproto/802_11/wlan_ratectl/onoe/ieee80211_ratectl_onoe.c,v 1.8 2007/03/19 13:38:43 sephe Exp $
38  */
39
40 /*
41  * Atsushi Onoe's rate control algorithm.
42  */
43
44 #include <sys/param.h>
45 #include <sys/kernel.h>
46 #include <sys/malloc.h>
47 #include <sys/module.h>
48 #include <sys/sysctl.h>
49 #include <sys/serialize.h>
50  
51 #include <net/if.h>
52 #include <net/if_media.h>
53 #include <net/if_arp.h>
54
55 #include <netproto/802_11/ieee80211_var.h>
56 #include <netproto/802_11/wlan_ratectl/onoe/ieee80211_onoe_param.h>
57 #include <netproto/802_11/wlan_ratectl/onoe/ieee80211_ratectl_onoe.h>
58
59 #define ONOE_DEBUG
60
61 #ifdef ONOE_DEBUG
62 #define DPRINTF(osc, lv, fmt, ...) do {         \
63         if ((osc)->debug >= lv)                 \
64                 kprintf(fmt, __VA_ARGS__);      \
65 } while (0)
66 #else
67 #define DPRINTF(osc, lv, fmt, ...)
68 #endif
69
70 #define ONOE_REQUIRE_STATS      (IEEE80211_RATECTL_STATS_PKT_OK |       \
71                                  IEEE80211_RATECTL_STATS_PKT_ERR |      \
72                                  IEEE80211_RATECTL_STATS_RETRIES)
73 #define ONOE_MEET_REQUIRE_STATS(stats_mask)     \
74         (((stats_mask) & ONOE_REQUIRE_STATS) == ONOE_REQUIRE_STATS)
75
76 /*
77  * Default parameters for the rate control algorithm.  These are
78  * all tunable with sysctls.  The rate controller runs periodically
79  * (each ath_rateinterval ms) analyzing transmit statistics for each
80  * neighbor/station (when operating in station mode this is only the AP).
81  * If transmits look to be working well over a sampling period then
82  * it gives a "raise rate credit".  If transmits look to not be working
83  * well than it deducts a credit.  If the credits cross a threshold then
84  * the transmit rate is raised.  Various error conditions force the
85  * the transmit rate to be dropped.
86  *
87  * The decision to issue/deduct a credit is based on the errors and
88  * retries accumulated over the sampling period.  ath_rate_raise defines
89  * the percent of retransmits for which a credit is issued/deducted.
90  * ath_rate_raise_threshold defines the threshold on credits at which
91  * the transmit rate is increased.
92  *
93  * XXX this algorithm is flawed.
94  */
95
96 static void     *onoe_attach(struct ieee80211com *);
97 static void     onoe_detach(void *);
98 static void     onoe_data_free(struct ieee80211_node *);
99 static void     onoe_data_alloc(struct ieee80211_node *);
100 static void     onoe_data_dup(const struct ieee80211_node *,
101                               struct ieee80211_node *);
102 static void     onoe_newstate(void *, enum ieee80211_state);
103 static void     onoe_tx_complete(void *, struct ieee80211_node *, int,
104                                  const struct ieee80211_ratectl_res[],
105                                  int, int, int, int);
106 static void     onoe_newassoc(void *, struct ieee80211_node *, int);
107 static int      onoe_findrate(void *, struct ieee80211_node *, int,
108                               int[], int);
109
110 static void     onoe_sysctl_attach(struct onoe_softc *);
111 static void     onoe_update(struct onoe_softc *, struct ieee80211_node *, int);
112 static void     onoe_start(struct onoe_softc *, struct ieee80211_node *);
113 static void     onoe_tick(void *);
114 static void     onoe_ratectl(void *, struct ieee80211_node *);
115 static void     onoe_gather_stats(struct onoe_softc *, struct ieee80211_node *);
116
117 static const struct ieee80211_ratectl onoe = {
118         .rc_name        = "onoe",
119         .rc_ratectl     = IEEE80211_RATECTL_ONOE,
120         .rc_attach      = onoe_attach,
121         .rc_detach      = onoe_detach,
122         .rc_data_alloc  = onoe_data_alloc,
123         .rc_data_free   = onoe_data_free,
124         .rc_data_dup    = onoe_data_dup,
125         .rc_newstate    = onoe_newstate,
126         .rc_tx_complete = onoe_tx_complete,
127         .rc_newassoc    = onoe_newassoc,
128         .rc_findrate    = onoe_findrate
129 };
130
131 static u_int    onoe_nrefs;
132
133 MALLOC_DEFINE(M_ONOE_RATECTL_DATA, "onoe_ratectl_data",
134               "onoe rate control data");
135
136 static void
137 onoe_tx_complete(void *arg __unused, struct ieee80211_node *ni,
138                  int frame_len __unused,
139                  const struct ieee80211_ratectl_res res[] __unused,
140                  int res_len __unused,
141                  int data_retries, int rts_retries __unused, int is_fail)
142 {
143         struct onoe_data *od = ni->ni_rate_data;
144
145         if (od == NULL)
146                 return;
147
148         if (is_fail)
149                 od->od_tx_err++;
150         else
151                 od->od_tx_ok++;
152
153         od->od_tx_retr += data_retries;
154 }
155
156 static void
157 onoe_newassoc(void *arg, struct ieee80211_node *ni, int is_new)
158 {
159         if (is_new)
160                 onoe_start(arg, ni);
161 }
162
163 static int
164 onoe_findrate(void *arg, struct ieee80211_node *ni,
165               int frame_len __unused, int rateidx[], int rateidx_len)
166 {
167         struct onoe_softc *osc = arg;
168         int i, rate_idx;
169
170         if (ni->ni_txrate >= ni->ni_rates.rs_nrates) {
171                 DPRINTF(osc, 5, "%s: number of rates changed, restart\n",
172                         __func__);
173                 onoe_start(osc, ni);
174         }
175         rate_idx = ni->ni_txrate;
176
177         for (i = 0; i < rateidx_len; ++i) {
178                 if (rate_idx < 0)
179                         break;
180                 rateidx[i] = rate_idx--;
181         }
182         if (rateidx_len > 1)
183                 rateidx[rateidx_len - 1] = 0;
184         return i;
185 }
186
187 static void
188 onoe_update(struct onoe_softc *osc, struct ieee80211_node *ni, int nrate)
189 {
190         struct onoe_data *od = ni->ni_rate_data;
191
192         DPRINTF(osc, 1, "%s: set xmit rate for %6D to %dM\n", __func__,
193                 ni->ni_macaddr, ":",
194                 ni->ni_rates.rs_nrates > 0 ?
195                 IEEE80211_RS_RATE(&ni->ni_rates, nrate) / 2 : 0);
196
197         ni->ni_txrate = nrate;
198
199         if (od == NULL) {
200                 onoe_data_alloc(ni);
201         } else {
202                 od->od_tx_ok = 0;
203                 od->od_tx_err = 0;
204                 od->od_tx_retr = 0;
205                 od->od_tx_upper = 0;
206         }
207 }
208
209 /*
210  * Set the starting transmit rate for a node.
211  */
212 static void
213 onoe_start(struct onoe_softc *osc, struct ieee80211_node *ni)
214 {
215 #define RATE(_ix)       IEEE80211_RS_RATE(&ni->ni_rates, (_ix))
216         struct ieee80211com *ic = osc->ic;
217         int srate;
218
219         KASSERT(ni->ni_rates.rs_nrates > 0, ("no rates"));
220         if (ic->ic_fixed_rate == IEEE80211_FIXED_RATE_NONE) {
221                 /*
222                  * For adhoc or ibss mode, start from the lowest rate.
223                  */
224                 if (ic->ic_opmode == IEEE80211_M_AHDEMO ||
225                     ic->ic_opmode == IEEE80211_M_IBSS) {
226                         onoe_update(osc, ni, 0);
227                         return;
228                 }
229
230                 /*
231                  * No fixed rate is requested. For 11b start with
232                  * the highest negotiated rate; otherwise, for 11g
233                  * and 11a, we start "in the middle" at 24Mb or 36Mb.
234                  */
235                 srate = ni->ni_rates.rs_nrates - 1;
236                 if (ic->ic_curmode != IEEE80211_MODE_11B) {
237                         /*
238                          * Scan the negotiated rate set to find the
239                          * closest rate.
240                          */
241                         /* NB: the rate set is assumed sorted */
242                         for (; srate >= 0 && RATE(srate) > 72; srate--)
243                                 ;
244                         KASSERT(srate >= 0, ("bogus rate set"));
245                 }
246         } else {
247                 /*
248                  * A fixed rate is to be used; ic_fixed_rate is an
249                  * index into the supported rate set.  Convert this
250                  * to the index into the negotiated rate set for
251                  * the node.  We know the rate is there because the
252                  * rate set is checked when the station associates.
253                  */
254                 const struct ieee80211_rateset *rs =
255                         &ic->ic_sup_rates[ic->ic_curmode];
256                 int r = IEEE80211_RS_RATE(rs, ic->ic_fixed_rate);
257
258                 /* NB: the rate set is assumed sorted */
259                 srate = ni->ni_rates.rs_nrates - 1;
260                 for (; srate >= 0 && RATE(srate) != r; srate--)
261                         ;
262                 KASSERT(srate >= 0,
263                         ("fixed rate %d not in rate set", ic->ic_fixed_rate));
264         }
265         onoe_update(osc, ni, srate);
266 #undef RATE
267 }
268
269 static void
270 onoe_rate_cb(void *arg, struct ieee80211_node *ni)
271 {
272         onoe_update(arg, ni, 0);
273 }
274
275 static void
276 onoe_newstate(void *arg, enum ieee80211_state state)
277 {
278         struct onoe_softc *osc = arg;
279         struct ieee80211com *ic = osc->ic;
280         struct ieee80211_node *ni;
281
282         if (state == IEEE80211_S_INIT) {
283                 callout_stop(&osc->timer);
284                 return;
285         }
286
287         if (ic->ic_opmode == IEEE80211_M_STA) {
288                 /*
289                  * Reset local xmit state; this is really only
290                  * meaningful when operating in station mode.
291                  */
292                 ni = ic->ic_bss;
293                 if (state == IEEE80211_S_RUN)
294                         onoe_start(osc, ni);
295                 else
296                         onoe_update(osc, ni, 0);
297         } else {
298                 /*
299                  * When operating as a station the node table holds
300                  * the AP's that were discovered during scanning.
301                  * For any other operating mode we want to reset the
302                  * tx rate state of each node.
303                  */
304                 ieee80211_iterate_nodes(&ic->ic_sta, onoe_rate_cb, osc);
305                 onoe_update(osc, ic->ic_bss, 0);
306         }
307
308         if (ic->ic_fixed_rate == IEEE80211_FIXED_RATE_NONE &&
309             state == IEEE80211_S_RUN) {
310                 int interval;
311
312                 /*
313                  * Start the background rate control thread if we
314                  * are not configured to use a fixed xmit rate.
315                  */
316                 interval = osc->interval;
317                 if (ic->ic_opmode == IEEE80211_M_STA)
318                         interval /= 2;
319                 callout_reset(&osc->timer, (interval * hz) / 1000,
320                               onoe_tick, osc);
321         }
322 }
323
324 static void
325 onoe_gather_stats(struct onoe_softc *osc, struct ieee80211_node *ni)
326 {
327         struct onoe_data *od = ni->ni_rate_data;
328         struct ieee80211com *ic = osc->ic;
329         const struct ieee80211_ratectl_state *st = &ic->ic_ratectl;
330         struct ieee80211_ratectl_stats stats;
331
332         st->rc_st_stats(ic, ni, &stats);
333
334         od->od_tx_ok += stats.stats_pkt_ok;
335         od->od_tx_err += stats.stats_pkt_err;
336         od->od_tx_retr += stats.stats_retries;
337 }
338
339 static void
340 onoe_ratectl(void *arg, struct ieee80211_node *ni)
341 {
342         struct onoe_softc *osc = arg;
343         struct onoe_data *od = ni->ni_rate_data;
344         const struct ieee80211_ratectl_state *st = &osc->ic->ic_ratectl;
345         struct ieee80211_rateset *rs = &ni->ni_rates;
346         int dir = 0, nrate, enough;
347
348         if (od == NULL) {
349                 /* We are no ready to go, set TX rate to lowest one */
350                 ni->ni_txrate = 0;
351                 return;
352         }
353
354         if (st->rc_st_stats != NULL) {
355                 if (!ONOE_MEET_REQUIRE_STATS(st->rc_st_valid_stats))
356                         return;
357                 onoe_gather_stats(osc, ni);
358         }
359
360         /*
361          * Rate control
362          * XXX: very primitive version.
363          */
364         enough = (od->od_tx_ok + od->od_tx_err >= 10);
365
366         /* no packet reached -> down */
367         if (od->od_tx_err > 0 && od->od_tx_ok == 0)
368                 dir = -1;
369
370         /* all packets needs retry in average -> down */
371         if (enough && od->od_tx_ok < od->od_tx_retr)
372                 dir = -1;
373
374         /* no error and less than rate_raise% of packets need retry -> up */
375         if (enough && od->od_tx_err == 0 &&
376             od->od_tx_retr < (od->od_tx_ok * osc->raise) / 100)
377                 dir = 1;
378
379         DPRINTF(osc, 10, "%6D: ok %d err %d retr %d upper %d dir %d\n",
380                 ni->ni_macaddr, ":",
381                 od->od_tx_ok, od->od_tx_err, od->od_tx_retr,
382                 od->od_tx_upper, dir);
383
384         nrate = ni->ni_txrate;
385         switch (dir) {
386         case 0:
387                 if (enough && od->od_tx_upper > 0)
388                         od->od_tx_upper--;
389                 break;
390         case -1:
391                 if (nrate > 0)
392                         nrate--;
393                 od->od_tx_upper = 0;
394                 break;
395         case 1:
396                 /* raise rate if we hit rate_raise_threshold */
397                 if (++od->od_tx_upper < osc->raise_threshold)
398                         break;
399                 od->od_tx_upper = 0;
400                 if (nrate + 1 < rs->rs_nrates)
401                         nrate++;
402                 break;
403         }
404
405         if (nrate != ni->ni_txrate) {
406                 DPRINTF(osc, 5, "%s: %dM -> %dM (%d ok, %d err, %d retr)\n",
407                         __func__,
408                         IEEE80211_RS_RATE(rs, ni->ni_txrate) / 2,
409                         IEEE80211_RS_RATE(rs, nrate) / 2,
410                         od->od_tx_ok, od->od_tx_err, od->od_tx_retr);
411                 onoe_update(osc, ni, nrate);
412         } else if (enough) {
413                 od->od_tx_ok = od->od_tx_err = od->od_tx_retr = 0;
414         }
415 }
416
417 static void
418 onoe_tick(void *arg)
419 {
420         struct onoe_softc *osc = arg;
421         struct ieee80211com *ic = osc->ic;
422         struct ifnet *ifp = &ic->ic_if;
423         int interval;
424
425         lwkt_serialize_enter(ifp->if_serializer);
426
427         if (ifp->if_flags & IFF_RUNNING) {
428                 if (ic->ic_opmode == IEEE80211_M_STA)
429                         onoe_ratectl(osc, ic->ic_bss);  /* NB: no reference */
430                 else
431                         ieee80211_iterate_nodes(&ic->ic_sta, onoe_ratectl, osc);
432         }
433
434         interval = osc->interval;
435         if (ic->ic_opmode == IEEE80211_M_STA)
436                 interval /= 2;
437         callout_reset(&osc->timer, (interval * hz) / 1000, onoe_tick, osc);
438
439         lwkt_serialize_exit(ifp->if_serializer);
440 }
441
442 static void
443 onoe_sysctl_attach(struct onoe_softc *osc)
444 {
445         struct ieee80211com *ic = osc->ic;
446         struct ieee80211_onoe_param *param;
447
448         param = ic->ic_ratectl.rc_st_param;
449         if (param != NULL) {
450                 osc->interval = param->onoe_interval;
451                 osc->raise = param->onoe_raise;
452                 osc->raise_threshold = param->onoe_raise_threshold;
453         } else {
454                 osc->interval = IEEE80211_ONOE_INTERVAL;
455                 osc->raise = IEEE80211_ONOE_RAISE;
456                 osc->raise_threshold = IEEE80211_ONOE_RAISE_THR;
457         }
458         osc->debug = 0;
459
460         sysctl_ctx_init(&osc->sysctl_ctx);
461         osc->sysctl_oid = SYSCTL_ADD_NODE(&osc->sysctl_ctx,
462                 SYSCTL_CHILDREN(osc->ic->ic_sysctl_oid),
463                 OID_AUTO, "onoe_ratectl", CTLFLAG_RD, 0, "");
464         if (osc->sysctl_oid == NULL) {
465                 kprintf("wlan_ratectl_onoe: create sysctl tree failed\n");
466                 return;
467         }
468
469         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
470                        OID_AUTO, "interval", CTLFLAG_RW, &osc->interval, 0,
471                        "rate control: operation interval (ms)");
472
473         /* XXX bounds check values */
474         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
475                        OID_AUTO, "raise", CTLFLAG_RW, &osc->raise, 0,
476                        "rate control: "
477                        "retry threshold to credit rate raise (%%)");
478
479         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
480                        OID_AUTO, "raise_threshold", CTLFLAG_RW,
481                        &osc->raise_threshold, 0,
482                        "rate control: # good periods before raising rate");
483
484         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
485                        OID_AUTO, "debug", CTLFLAG_RW, &osc->debug, 0,
486                        "rate control: debug level");
487 }
488
489 static void *
490 onoe_attach(struct ieee80211com *ic)
491 {
492         const struct ieee80211_ratectl_state *st = &ic->ic_ratectl;
493         struct onoe_softc *osc;
494
495         if (st->rc_st_stats != NULL &&
496             !ONOE_MEET_REQUIRE_STATS(st->rc_st_valid_stats)) {
497                 if_printf(&ic->ic_if, "WARNING: %s needs more average "
498                           "statistics to work properly\n", onoe.rc_name);
499         }
500
501         onoe_nrefs++;
502
503         osc = kmalloc(sizeof(struct onoe_softc), M_DEVBUF, M_WAITOK | M_ZERO);
504
505         osc->ic = ic;
506         callout_init(&osc->timer);
507         onoe_sysctl_attach(osc);
508
509         onoe_newstate(osc, ic->ic_state);
510
511         return osc;
512 }
513
514 static void
515 _onoe_data_free(void *arg __unused, struct ieee80211_node *ni)
516 {
517         onoe_data_free(ni);
518 }
519
520 static void
521 onoe_detach(void *arg)
522 {
523         struct onoe_softc *osc = arg;
524         struct ieee80211com *ic = osc->ic;
525
526         onoe_newstate(osc, IEEE80211_S_INIT);
527
528         ieee80211_iterate_nodes(&ic->ic_sta, _onoe_data_free, NULL);
529         ieee80211_iterate_nodes(&ic->ic_scan, _onoe_data_free, NULL);
530
531         if (osc->sysctl_oid != NULL)
532                 sysctl_ctx_free(&osc->sysctl_ctx);
533         kfree(osc, M_DEVBUF);
534
535         onoe_nrefs--;
536 }
537
538 static void
539 onoe_data_free(struct ieee80211_node *ni)
540 {
541         if (ni->ni_rate_data != NULL) {
542                 kfree(ni->ni_rate_data, M_ONOE_RATECTL_DATA);
543                 ni->ni_rate_data = NULL;
544         }
545 }
546
547 static void
548 onoe_data_alloc(struct ieee80211_node *ni)
549 {
550         KKASSERT(ni->ni_rate_data == NULL);
551         ni->ni_rate_data = kmalloc(sizeof(struct onoe_data),
552                                   M_ONOE_RATECTL_DATA, M_NOWAIT | M_ZERO);
553 }
554
555 static void
556 onoe_data_dup(const struct ieee80211_node *oni, struct ieee80211_node *nni)
557 {
558         if (oni->ni_rate_data == NULL || nni->ni_rate_data == NULL)
559                 return;
560
561         bcopy(oni->ni_rate_data, nni->ni_rate_data, sizeof(struct onoe_data));
562 }
563
564 static int
565 onoe_modevent(module_t mod, int type, void *unused)
566 {
567         switch (type) {
568         case MOD_LOAD:
569                 ieee80211_ratectl_register(&onoe);
570                 return 0;
571         case MOD_UNLOAD:
572                 if (onoe_nrefs) {
573                         kprintf("wlan_ratectl_onoe: still in use "
574                                "(%u dynamic refs)\n", onoe_nrefs);
575                         return EBUSY;
576                 }
577                 ieee80211_ratectl_unregister(&onoe);
578                 return 0;
579         }
580         return EINVAL;
581 }
582
583 static moduledata_t onoe_mod = {
584         "wlan_ratectl_onoe",
585         onoe_modevent,
586         0
587 };
588 DECLARE_MODULE(wlan_ratectl_onoe, onoe_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
589 MODULE_VERSION(wlan_ratectl_onoe, 1);
590 MODULE_DEPEND(wlan_ratectl_onoe, wlan, 1, 1, 1);