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.3 2006/09/05 03:48:13 dillon 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_ratectl_onoe.h>
  57
  58 #define ONOE_DEBUG
  59
  60 #ifdef ONOE_DEBUG
  61 #define DPRINTF(osc, lv, fmt, ...) do {         \
  62         if ((osc)->debug >= lv)                 \
  63                 printf(fmt, __VA_ARGS__);       \
  64 } while (0)
  65 #else
  66 #define DPRINTF(osc, lv, fmt, ...)
  67 #endif
  68
  69 /*
  70  * Default parameters for the rate control algorithm.  These are
  71  * all tunable with sysctls.  The rate controller runs periodically
  72  * (each ath_rateinterval ms) analyzing transmit statistics for each
  73  * neighbor/station (when operating in station mode this is only the AP).
  74  * If transmits look to be working well over a sampling period then
  75  * it gives a "raise rate credit".  If transmits look to not be working
  76  * well than it deducts a credit.  If the credits cross a threshold then
  77  * the transmit rate is raised.  Various error conditions force the
  78  * the transmit rate to be dropped.
  79  *
  80  * The decision to issue/deduct a credit is based on the errors and
  81  * retries accumulated over the sampling period.  ath_rate_raise defines
  82  * the percent of retransmits for which a credit is issued/deducted.
  83  * ath_rate_raise_threshold defines the threshold on credits at which
  84  * the transmit rate is increased.
  85  *
  86  * XXX this algorithm is flawed.
  87  */
  88
  89 static void     *onoe_attach(struct ieee80211com *);
  90 static void     onoe_detach(void *);
  91 static void     onoe_data_free(struct ieee80211_node *);
  92 static void     onoe_data_alloc(struct ieee80211_node *);
  93 static void     onoe_data_dup(const struct ieee80211_node *,
  94                               struct ieee80211_node *);
  95 static void     onoe_newstate(void *, enum ieee80211_state);
  96 static void     onoe_tx_complete(void *, struct ieee80211_node *, int,
  97                                  const struct ieee80211_ratectl_res[],
  98                                  int, int, int, int);
  99 static void     onoe_newassoc(void *, struct ieee80211_node *, int);
 100 static int      onoe_findrate(void *, struct ieee80211_node *, int,
 101                               int[], int);
 102
 103 static void     onoe_sysctl_attach(struct onoe_softc *);
 104 static void     onoe_update(struct onoe_softc *, struct ieee80211_node *, int);
 105 static void     onoe_start(struct onoe_softc *, struct ieee80211_node *);
 106 static void     onoe_tick(void *);
 107 static void     onoe_ratectl(void *, struct ieee80211_node *);
 108
 109 static const struct ieee80211_ratectl onoe = {
 110         .rc_name        = "onoe",
 111         .rc_ratectl     = IEEE80211_RATECTL_ONOE,
 112         .rc_attach      = onoe_attach,
 113         .rc_detach      = onoe_detach,
 114         .rc_data_alloc  = onoe_data_alloc,
 115         .rc_data_free   = onoe_data_free,
 116         .rc_data_dup    = onoe_data_dup,
 117         .rc_newstate    = onoe_newstate,
 118         .rc_tx_complete = onoe_tx_complete,
 119         .rc_newassoc    = onoe_newassoc,
 120         .rc_findrate    = onoe_findrate
 121 };
 122
 123 static u_int    onoe_nrefs;
 124
 125 MALLOC_DEFINE(M_ONOE_RATECTL_DATA, "onoe_ratectl_data",
 126               "onoe rate control data");
 127
 128 static void
 129 onoe_tx_complete(void *arg __unused, struct ieee80211_node *ni,
 130                  int frame_len __unused,
 131                  const struct ieee80211_ratectl_res res[] __unused,
 132                  int res_len __unused,
 133                  int short_retries, int long_retries, int is_fail)
 134 {
 135         struct onoe_data *od = ni->ni_rate_data;
 136
 137         if (od == NULL)
 138                 return;
 139
 140         if (is_fail)
 141                 od->od_tx_err++;
 142         else
 143                 od->od_tx_ok++;
 144
 145         od->od_tx_retr += long_retries + short_retries;
 146 }
 147
 148 static void
 149 onoe_newassoc(void *arg, struct ieee80211_node *ni, int is_new)
 150 {
 151         if (is_new)
 152                 onoe_start(arg, ni);
 153 }
 154
 155 static int
 156 onoe_findrate(void *arg __unused, struct ieee80211_node *ni,
 157               int frame_len __unused, int rateidx[], int rateidx_len)
 158 {
 159         int i, rate_idx = ni->ni_txrate;
 160
 161         for (i = 0; i < rateidx_len; ++i) {
 162                 if (rate_idx < 0)
 163                         break;
 164                 rateidx[i] = rate_idx--;
 165         }
 166         if (rateidx_len > 1)
 167                 rateidx[rateidx_len - 1] = 0;
 168         return i;
 169 }
 170
 171 static void
 172 onoe_update(struct onoe_softc *osc, struct ieee80211_node *ni, int nrate)
 173 {
 174         struct onoe_data *od = ni->ni_rate_data;
 175
 176         DPRINTF(osc, 1, "%s: set xmit rate for %6D to %dM\n", __func__,
 177                 ni->ni_macaddr, ":",
 178                 ni->ni_rates.rs_nrates > 0 ?
 179                 IEEE80211_RS_RATE(&ni->ni_rates, nrate) / 2 : 0);
 180
 181         ni->ni_txrate = nrate;
 182
 183         if (od == NULL) {
 184                 onoe_data_alloc(ni);
 185         } else {
 186                 od->od_tx_ok = 0;
 187                 od->od_tx_err = 0;
 188                 od->od_tx_retr = 0;
 189                 od->od_tx_upper = 0;
 190         }
 191 }
 192
 193 /*
 194  * Set the starting transmit rate for a node.
 195  */
 196 static void
 197 onoe_start(struct onoe_softc *osc, struct ieee80211_node *ni)
 198 {
 199 #define RATE(_ix)       IEEE80211_RS_RATE(&ni->ni_rates, (_ix))
 200         struct ieee80211com *ic = osc->ic;
 201         int srate;
 202
 203         KASSERT(ni->ni_rates.rs_nrates > 0, ("no rates"));
 204         if (ic->ic_fixed_rate == IEEE80211_FIXED_RATE_NONE) {
 205                 /*
 206                  * For adhoc or ibss mode, start from the lowest rate.
 207                  */
 208                 if (ic->ic_opmode == IEEE80211_M_AHDEMO ||
 209                     ic->ic_opmode == IEEE80211_M_IBSS) {
 210                         onoe_update(osc, ni, 0);
 211                         return;
 212                 }
 213
 214                 /*
 215                  * No fixed rate is requested. For 11b start with
 216                  * the highest negotiated rate; otherwise, for 11g
 217                  * and 11a, we start "in the middle" at 24Mb or 36Mb.
 218                  */
 219                 srate = ni->ni_rates.rs_nrates - 1;
 220                 if (ic->ic_curmode != IEEE80211_MODE_11B) {
 221                         /*
 222                          * Scan the negotiated rate set to find the
 223                          * closest rate.
 224                          */
 225                         /* NB: the rate set is assumed sorted */
 226                         for (; srate >= 0 && RATE(srate) > 72; srate--)
 227                                 ;
 228                         KASSERT(srate >= 0, ("bogus rate set"));
 229                 }
 230         } else {
 231                 /*
 232                  * A fixed rate is to be used; ic_fixed_rate is an
 233                  * index into the supported rate set.  Convert this
 234                  * to the index into the negotiated rate set for
 235                  * the node.  We know the rate is there because the
 236                  * rate set is checked when the station associates.
 237                  */
 238                 const struct ieee80211_rateset *rs =
 239                         &ic->ic_sup_rates[ic->ic_curmode];
 240                 int r = IEEE80211_RS_RATE(rs, ic->ic_fixed_rate);
 241
 242                 /* NB: the rate set is assumed sorted */
 243                 srate = ni->ni_rates.rs_nrates - 1;
 244                 for (; srate >= 0 && RATE(srate) != r; srate--)
 245                         ;
 246                 KASSERT(srate >= 0,
 247                         ("fixed rate %d not in rate set", ic->ic_fixed_rate));
 248         }
 249         onoe_update(osc, ni, srate);
 250 #undef RATE
 251 }
 252
 253 static void
 254 onoe_rate_cb(void *arg, struct ieee80211_node *ni)
 255 {
 256         onoe_update(arg, ni, 0);
 257 }
 258
 259 static void
 260 onoe_newstate(void *arg, enum ieee80211_state state)
 261 {
 262         struct onoe_softc *osc = arg;
 263         struct ieee80211com *ic = osc->ic;
 264         struct ieee80211_node *ni;
 265
 266         if (state == IEEE80211_S_INIT) {
 267                 callout_stop(&osc->timer);
 268                 return;
 269         }
 270
 271         if (ic->ic_opmode == IEEE80211_M_STA) {
 272                 /*
 273                  * Reset local xmit state; this is really only
 274                  * meaningful when operating in station mode.
 275                  */
 276                 ni = ic->ic_bss;
 277                 if (state == IEEE80211_S_RUN)
 278                         onoe_start(osc, ni);
 279                 else
 280                         onoe_update(osc, ni, 0);
 281         } else {
 282                 /*
 283                  * When operating as a station the node table holds
 284                  * the AP's that were discovered during scanning.
 285                  * For any other operating mode we want to reset the
 286                  * tx rate state of each node.
 287                  */
 288                 ieee80211_iterate_nodes(&ic->ic_sta, onoe_rate_cb, osc);
 289                 onoe_update(osc, ic->ic_bss, 0);
 290         }
 291
 292         if (ic->ic_fixed_rate == IEEE80211_FIXED_RATE_NONE &&
 293             state == IEEE80211_S_RUN) {
 294                 int interval;
 295
 296                 /*
 297                  * Start the background rate control thread if we
 298                  * are not configured to use a fixed xmit rate.
 299                  */
 300                 interval = osc->interval;
 301                 if (ic->ic_opmode == IEEE80211_M_STA)
 302                         interval /= 2;
 303                 callout_reset(&osc->timer, (interval * hz) / 1000,
 304                               onoe_tick, osc);
 305         }
 306 }
 307
 308 static void
 309 onoe_ratectl(void *arg, struct ieee80211_node *ni)
 310 {
 311         struct onoe_softc *osc = arg;
 312         struct onoe_data *od = ni->ni_rate_data;
 313         struct ieee80211_rateset *rs = &ni->ni_rates;
 314         int dir = 0, nrate, enough;
 315
 316         if (od == NULL) {
 317                 /* We are no ready to go, set TX rate to lowest one */
 318                 ni->ni_txrate = 0;
 319                 return;
 320         }
 321
 322         /*
 323          * Rate control
 324          * XXX: very primitive version.
 325          */
 326         enough = (od->od_tx_ok + od->od_tx_err >= 10);
 327
 328         /* no packet reached -> down */
 329         if (od->od_tx_err > 0 && od->od_tx_ok == 0)
 330                 dir = -1;
 331
 332         /* all packets needs retry in average -> down */
 333         if (enough && od->od_tx_ok < od->od_tx_retr)
 334                 dir = -1;
 335
 336         /* no error and less than rate_raise% of packets need retry -> up */
 337         if (enough && od->od_tx_err == 0 &&
 338             od->od_tx_retr < (od->od_tx_ok * osc->raise) / 100)
 339                 dir = 1;
 340
 341         DPRINTF(osc, 10, "%6D: ok %d err %d retr %d upper %d dir %d\n",
 342                 ni->ni_macaddr, ":",
 343                 od->od_tx_ok, od->od_tx_err, od->od_tx_retr,
 344                 od->od_tx_upper, dir);
 345
 346         nrate = ni->ni_txrate;
 347         switch (dir) {
 348         case 0:
 349                 if (enough && od->od_tx_upper > 0)
 350                         od->od_tx_upper--;
 351                 break;
 352         case -1:
 353                 if (nrate > 0)
 354                         nrate--;
 355                 od->od_tx_upper = 0;
 356                 break;
 357         case 1:
 358                 /* raise rate if we hit rate_raise_threshold */
 359                 if (++od->od_tx_upper < osc->raise_threshold)
 360                         break;
 361                 od->od_tx_upper = 0;
 362                 if (nrate + 1 < rs->rs_nrates)
 363                         nrate++;
 364                 break;
 365         }
 366
 367         if (nrate != ni->ni_txrate) {
 368                 DPRINTF(osc, 5, "%s: %dM -> %dM (%d ok, %d err, %d retr)\n",
 369                         __func__,
 370                         IEEE80211_RS_RATE(rs, ni->ni_txrate) / 2,
 371                         IEEE80211_RS_RATE(rs, nrate) / 2,
 372                         od->od_tx_ok, od->od_tx_err, od->od_tx_retr);
 373                 onoe_update(osc, ni, nrate);
 374         } else if (enough) {
 375                 od->od_tx_ok = od->od_tx_err = od->od_tx_retr = 0;
 376         }
 377 }
 378
 379 static void
 380 onoe_tick(void *arg)
 381 {
 382         struct onoe_softc *osc = arg;
 383         struct ieee80211com *ic = osc->ic;
 384         struct ifnet *ifp = &ic->ic_if;
 385         int interval;
 386
 387         lwkt_serialize_enter(ifp->if_serializer);
 388
 389         if (ifp->if_flags & IFF_RUNNING) {
 390                 if (ic->ic_opmode == IEEE80211_M_STA)
 391                         onoe_ratectl(osc, ic->ic_bss);  /* NB: no reference */
 392                 else
 393                         ieee80211_iterate_nodes(&ic->ic_sta, onoe_ratectl, osc);
 394         }
 395
 396         interval = osc->interval;
 397         if (ic->ic_opmode == IEEE80211_M_STA)
 398                 interval /= 2;
 399         callout_reset(&osc->timer, (interval * hz) / 1000, onoe_tick, osc);
 400
 401         lwkt_serialize_exit(ifp->if_serializer);
 402 }
 403
 404 static void
 405 onoe_sysctl_attach(struct onoe_softc *osc)
 406 {
 407         osc->interval = 1000;
 408         osc->raise = 10;
 409         osc->raise_threshold = 10;
 410         osc->debug = 0;
 411
 412         sysctl_ctx_init(&osc->sysctl_ctx);
 413         osc->sysctl_oid = SYSCTL_ADD_NODE(&osc->sysctl_ctx,
 414                 SYSCTL_CHILDREN(osc->ic->ic_sysctl_oid),
 415                 OID_AUTO, "onoe_ratectl", CTLFLAG_RD, 0, "");
 416         if (osc->sysctl_oid == NULL) {
 417                 printf("wlan_ratectl_onoe: create sysctl tree failed\n");
 418                 return;
 419         }
 420
 421         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
 422                        OID_AUTO, "interval", CTLFLAG_RW, &osc->interval, 0,
 423                        "rate control: operation interval (ms)");
 424
 425         /* XXX bounds check values */
 426         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
 427                        OID_AUTO, "raise", CTLFLAG_RW, &osc->raise, 0,
 428                        "rate control: "
 429                        "retry threshold to credit rate raise (%%)");
 430
 431         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
 432                        OID_AUTO, "raise_threshold", CTLFLAG_RW,
 433                        &osc->raise_threshold, 0,
 434                        "rate control: # good periods before raising rate");
 435
 436         SYSCTL_ADD_INT(&osc->sysctl_ctx, SYSCTL_CHILDREN(osc->sysctl_oid),
 437                        OID_AUTO, "debug", CTLFLAG_RW, &osc->debug, 0,
 438                        "rate control: debug level");
 439 }
 440
 441 static void *
 442 onoe_attach(struct ieee80211com *ic)
 443 {
 444         struct onoe_softc *osc;
 445
 446         onoe_nrefs++;
 447
 448         osc = kmalloc(sizeof(struct onoe_softc), M_DEVBUF, M_WAITOK | M_ZERO);
 449
 450         osc->ic = ic;
 451         callout_init(&osc->timer);
 452         onoe_sysctl_attach(osc);
 453
 454         onoe_newstate(osc, ic->ic_state);
 455
 456         return osc;
 457 }
 458
 459 static void
 460 _onoe_data_free(void *arg __unused, struct ieee80211_node *ni)
 461 {
 462         onoe_data_free(ni);
 463 }
 464
 465 static void
 466 onoe_detach(void *arg)
 467 {
 468         struct onoe_softc *osc = arg;
 469         struct ieee80211com *ic = osc->ic;
 470
 471         onoe_newstate(osc, IEEE80211_S_INIT);
 472
 473         ieee80211_iterate_nodes(&ic->ic_sta, _onoe_data_free, NULL);
 474         ieee80211_iterate_nodes(&ic->ic_scan, _onoe_data_free, NULL);
 475
 476         if (osc->sysctl_oid != NULL)
 477                 sysctl_ctx_free(&osc->sysctl_ctx);
 478         kfree(osc, M_DEVBUF);
 479
 480         onoe_nrefs--;
 481 }
 482
 483 static void
 484 onoe_data_free(struct ieee80211_node *ni)
 485 {
 486         if (ni->ni_rate_data != NULL) {
 487                 kfree(ni->ni_rate_data, M_ONOE_RATECTL_DATA);
 488                 ni->ni_rate_data = NULL;
 489         }
 490 }
 491
 492 static void
 493 onoe_data_alloc(struct ieee80211_node *ni)
 494 {
 495         KKASSERT(ni->ni_rate_data == NULL);
 496         ni->ni_rate_data = kmalloc(sizeof(struct onoe_data),
 497                                   M_ONOE_RATECTL_DATA, M_NOWAIT | M_ZERO);
 498 }
 499
 500 static void
 501 onoe_data_dup(const struct ieee80211_node *oni, struct ieee80211_node *nni)
 502 {
 503         if (oni->ni_rate_data == NULL || nni->ni_rate_data == NULL)
 504                 return;
 505
 506         bcopy(oni->ni_rate_data, nni->ni_rate_data, sizeof(struct onoe_data));
 507 }
 508
 509 static int
 510 onoe_modevent(module_t mod, int type, void *unused)
 511 {
 512         switch (type) {
 513         case MOD_LOAD:
 514                 ieee80211_ratectl_register(&onoe);
 515                 return 0;
 516         case MOD_UNLOAD:
 517                 if (onoe_nrefs) {
 518                         printf("wlan_ratectl_onoe: still in use "
 519                                "(%u dynamic refs)\n", onoe_nrefs);
 520                         return EBUSY;
 521                 }
 522                 ieee80211_ratectl_unregister(&onoe);
 523                 return 0;
 524         }
 525         return EINVAL;
 526 }
 527
 528 static moduledata_t onoe_mod = {
 529         "wlan_ratectl_onoe",
 530         onoe_modevent,
 531         0
 532 };
 533 DECLARE_MODULE(wlan_ratectl_onoe, onoe_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
 534 MODULE_VERSION(wlan_ratectl_onoe, 1);
 535 MODULE_DEPEND(wlan_ratectl_onoe, wlan, 1, 1, 1);