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.3 2006/09/05 03:48:12 dillon 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_ratectl_amrr.h>
  61
  62 #define AMRR_DEBUG
  63 #ifdef AMRR_DEBUG
  64 #define DPRINTF(asc, lv, fmt, ...) do {         \
  65         if ((asc)->debug >= lv)                 \
  66                 printf(fmt, __VA_ARGS__);       \
  67 } while (0)
  68 #else
  69 #define DPRINTF(asc, lv, fmt, ...)
  70 #endif
  71
  72 static void     *amrr_attach(struct ieee80211com *);
  73 static void     amrr_detach(void *);
  74 static void     amrr_data_alloc(struct ieee80211_node *);
  75 static void     amrr_data_free(struct ieee80211_node *);
  76 static void     amrr_data_dup(const struct ieee80211_node *,
  77                               struct ieee80211_node *);
  78 static void     amrr_newstate(void *, enum ieee80211_state);
  79 static void     amrr_tx_complete(void *, struct ieee80211_node *, int,
  80                                  const struct ieee80211_ratectl_res[],
  81                                  int, int, int, int);
  82 static void     amrr_newassoc(void *, struct ieee80211_node *, int);
  83 static int      amrr_findrate(void *, struct ieee80211_node *, int,
  84                               int[], int);
  85
  86 static void     amrr_sysctl_attach(struct amrr_softc *);
  87 static void     amrr_update(struct amrr_softc *, struct ieee80211_node *, int);
  88 static void     amrr_start(struct amrr_softc *, struct ieee80211_node *);
  89 static void     amrr_tick(void *);
  90 static void     amrr_ratectl(void *, struct ieee80211_node *);
  91
  92 static const struct ieee80211_ratectl amrr = {
  93         .rc_name        = "amrr",
  94         .rc_ratectl     = IEEE80211_RATECTL_AMRR,
  95         .rc_attach      = amrr_attach,
  96         .rc_detach      = amrr_detach,
  97         .rc_data_alloc  = amrr_data_alloc,
  98         .rc_data_free   = amrr_data_free,
  99         .rc_data_dup    = amrr_data_dup,
 100         .rc_newstate    = amrr_newstate,
 101         .rc_tx_complete = amrr_tx_complete,
 102         .rc_newassoc    = amrr_newassoc,
 103         .rc_findrate    = amrr_findrate
 104 };
 105
 106 static u_int    amrr_nrefs;
 107
 108 MALLOC_DEFINE(M_AMRR_RATECTL_DATA, "amrr_ratectl_data",
 109               "amrr rate control data");
 110
 111 static int
 112 amrr_findrate(void *arg __unused, struct ieee80211_node *ni,
 113               int frame_len __unused, int rateidx[], int rateidx_len)
 114 {
 115         int i, rate_idx = ni->ni_txrate;
 116
 117         for (i = 0; i < rateidx_len && i < IEEE80211_AMRR_RATEIDX_MAX; ++i) {
 118                 if (rate_idx < 0)
 119                         break;
 120                 rateidx[i] = rate_idx--;
 121         }
 122         if (rateidx_len > 1)
 123                 rateidx[rateidx_len - 1] = 0;
 124         return i;
 125 }
 126
 127 static void
 128 amrr_tx_complete(void *arg __unused, struct ieee80211_node *ni,
 129                  int frame_len __unused,
 130                  const struct ieee80211_ratectl_res res[],
 131                  int res_len, int short_retries __unused,
 132                  int long_retries __unused, int is_fail)
 133 {
 134         struct amrr_data *ad = ni->ni_rate_data;
 135         int i;
 136
 137         if (ad == NULL)
 138                 return;
 139
 140         for (i = 0; i < res_len && i < IEEE80211_AMRR_RATEIDX_MAX; ++i)
 141                 ad->ad_tx_try_cnt[i]++;
 142         if (is_fail)
 143                 ad->ad_tx_failure_cnt++;
 144 }
 145
 146 static void
 147 amrr_newassoc(void *arg, struct ieee80211_node *ni, int isnew)
 148 {
 149         if (isnew)
 150                 amrr_start(arg, ni);
 151 }
 152
 153 /*
 154  * The code below assumes that we are dealing with hardware multi rate retry
 155  * I have no idea what will happen if you try to use this module with another
 156  * type of hardware. Your machine might catch fire or it might work with
 157  * horrible performance...
 158  */
 159 static void
 160 amrr_update(struct amrr_softc *asc, struct ieee80211_node *ni, int rate)
 161 {
 162         struct amrr_data *ad = ni->ni_rate_data;
 163
 164         DPRINTF(asc, 5, "%s: set xmit rate for %6D to %dM\n",
 165                 __func__, ni->ni_macaddr, ":",
 166                 ni->ni_rates.rs_nrates > 0 ?
 167                 IEEE80211_RS_RATE(&ni->ni_rates, rate) / 2 : 0);
 168
 169         ni->ni_txrate = rate;
 170
 171         if (ad == NULL) {
 172                 amrr_data_alloc(ni);
 173                 ad = ni->ni_rate_data;
 174                 if (ad == NULL)
 175                         return;
 176         }
 177
 178         ad->ad_tx_try_cnt[0] = 0;
 179         ad->ad_tx_try_cnt[1] = 0;
 180         ad->ad_tx_try_cnt[2] = 0;
 181         ad->ad_tx_try_cnt[3] = 0;
 182         ad->ad_tx_failure_cnt = 0;
 183         ad->ad_success = 0;
 184         ad->ad_recovery = 0;
 185         ad->ad_success_threshold = asc->min_success_threshold;
 186 }
 187
 188 /*
 189  * Set the starting transmit rate for a node.
 190  */
 191 static void
 192 amrr_start(struct amrr_softc *asc, struct ieee80211_node *ni)
 193 {
 194 #define RATE(_ix)       IEEE80211_RS_RATE(&ni->ni_rates, (_ix))
 195         struct ieee80211com *ic = asc->ic;
 196         int srate;
 197
 198         KASSERT(ni->ni_rates.rs_nrates > 0, ("no rates"));
 199
 200         if (ic->ic_fixed_rate == IEEE80211_FIXED_RATE_NONE) {
 201                 /*
 202                  * For adhoc or ibss mode, start from the lowest rate.
 203                  */
 204                 if (ic->ic_opmode == IEEE80211_M_AHDEMO ||
 205                     ic->ic_opmode == IEEE80211_M_IBSS) {
 206                         amrr_update(asc, ni, 0);
 207                         return;
 208                 }
 209
 210                 /*
 211                  * No fixed rate is requested. For 11b start with
 212                  * the highest negotiated rate; otherwise, for 11g
 213                  * and 11a, we start "in the middle" at 24Mb or 36Mb.
 214                  */
 215                 srate = ni->ni_rates.rs_nrates - 1;
 216                 if (ic->ic_curmode != IEEE80211_MODE_11B) {
 217                         /*
 218                          * Scan the negotiated rate set to find the
 219                          * closest rate.
 220                          */
 221                         /* NB: the rate set is assumed sorted */
 222                         for (; srate >= 0 && RATE(srate) > 72; srate--)
 223                                 ;
 224                         KASSERT(srate >= 0, ("bogus rate set"));
 225                 }
 226         } else {
 227                 /*
 228                  * A fixed rate is to be used; ic_fixed_rate is an
 229                  * index into the supported rate set.  Convert this
 230                  * to the index into the negotiated rate set for
 231                  * the node.  We know the rate is there because the
 232                  * rate set is checked when the station associates.
 233                  */
 234                 const struct ieee80211_rateset *rs =
 235                         &ic->ic_sup_rates[ic->ic_curmode];
 236                 int r = IEEE80211_RS_RATE(rs, ic->ic_fixed_rate);
 237
 238                 /* NB: the rate set is assumed sorted */
 239                 srate = ni->ni_rates.rs_nrates - 1;
 240                 for (; srate >= 0 && RATE(srate) != r; srate--)
 241                         ;
 242                 KASSERT(srate >= 0,
 243                         ("fixed rate %d not in rate set", ic->ic_fixed_rate));
 244         }
 245         amrr_update(asc, ni, srate);
 246 #undef RATE
 247 }
 248
 249 static void
 250 amrr_rate_cb(void *arg, struct ieee80211_node *ni)
 251 {
 252         amrr_update(arg, ni, 0);
 253 }
 254
 255 /*
 256  * Reset the rate control state for each 802.11 state transition.
 257  */
 258 static void
 259 amrr_newstate(void *arg, enum ieee80211_state state)
 260 {
 261         struct amrr_softc *asc = arg;
 262         struct ieee80211com *ic = asc->ic;
 263         struct ieee80211_node *ni;
 264
 265         if (state == IEEE80211_S_INIT) {
 266                 callout_stop(&asc->timer);
 267                 return;
 268         }
 269
 270         if (ic->ic_opmode == IEEE80211_M_STA) {
 271                 /*
 272                  * Reset local xmit state; this is really only
 273                  * meaningful when operating in station mode.
 274                  */
 275                 ni = ic->ic_bss;
 276                 if (state == IEEE80211_S_RUN)
 277                         amrr_start(asc, ni);
 278                 else
 279                         amrr_update(asc, ni, 0);
 280         } else {
 281                 /*
 282                  * When operating as a station the node table holds
 283                  * the AP's that were discovered during scanning.
 284                  * For any other operating mode we want to reset the
 285                  * tx rate state of each node.
 286                  */
 287                 ieee80211_iterate_nodes(&ic->ic_sta, amrr_rate_cb, asc);
 288                 amrr_update(asc, ic->ic_bss, 0);
 289         }
 290         if (ic->ic_fixed_rate == IEEE80211_FIXED_RATE_NONE &&
 291             state == IEEE80211_S_RUN) {
 292                 int interval;
 293
 294                 /*
 295                  * Start the background rate control thread if we
 296                  * are not configured to use a fixed xmit rate.
 297                  */
 298                 interval = asc->interval;
 299                 if (ic->ic_opmode == IEEE80211_M_STA)
 300                         interval /= 2;
 301                 callout_reset(&asc->timer, (interval * hz) / 1000,
 302                               amrr_tick, asc);
 303         }
 304 }
 305
 306 /*
 307  * Examine and potentially adjust the transmit rate.
 308  */
 309 static void
 310 amrr_ratectl(void *arg, struct ieee80211_node *ni)
 311 {
 312         struct amrr_softc *asc = arg;
 313         struct amrr_data *ad = ni->ni_rate_data;
 314         int old_rate;
 315
 316         if (ad == NULL) {
 317                 /* We are not ready to go, set TX rate to lowest one */
 318                 ni->ni_txrate = 0;
 319                 return;
 320         }
 321
 322 #define is_success(ad) \
 323 (ad->ad_tx_try_cnt[1]  < (ad->ad_tx_try_cnt[0] / 10))
 324 #define is_enough(ad) \
 325 (ad->ad_tx_try_cnt[0] > 10)
 326 #define is_failure(ad) \
 327 (ad->ad_tx_try_cnt[1] > (ad->ad_tx_try_cnt[0] / 3))
 328 #define is_max_rate(ni) \
 329 ((ni->ni_txrate + 1) >= ni->ni_rates.rs_nrates)
 330 #define is_min_rate(ni) \
 331 (ni->ni_txrate == 0)
 332
 333         old_rate = ni->ni_txrate;
 334
 335         DPRINTF(asc, 10, "cnt0: %d cnt1: %d cnt2: %d cnt3: %d -- "
 336                 "threshold: %d\n",
 337                 ad->ad_tx_try_cnt[0],
 338                 ad->ad_tx_try_cnt[1],
 339                 ad->ad_tx_try_cnt[2],
 340                 ad->ad_tx_try_cnt[3],
 341                 ad->ad_success_threshold);
 342
 343         if (is_success(ad) && is_enough(ad)) {
 344                 ad->ad_success++;
 345                 if (ad->ad_success == ad->ad_success_threshold &&
 346                     !is_max_rate(ni)) {
 347                         ad->ad_recovery = 1;
 348                         ad->ad_success = 0;
 349                         ni->ni_txrate++;
 350                         DPRINTF(asc, 5, "increase rate to %d\n", ni->ni_txrate);
 351                 } else {
 352                         ad->ad_recovery = 0;
 353                 }
 354         } else if (is_failure(ad)) {
 355                 ad->ad_success = 0;
 356                 if (!is_min_rate(ni)) {
 357                         if (ad->ad_recovery) {
 358                                 /* recovery failure. */
 359                                 ad->ad_success_threshold *= 2;
 360                                 ad->ad_success_threshold =
 361                                         min(ad->ad_success_threshold,
 362                                             (u_int)asc->max_success_threshold);
 363                                 DPRINTF(asc, 5, "decrease rate recovery thr: "
 364                                         "%d\n", ad->ad_success_threshold);
 365                         } else {
 366                                 /* simple failure. */
 367                                 ad->ad_success_threshold =
 368                                         asc->min_success_threshold;
 369                                 DPRINTF(asc, 5, "decrease rate normal thr: "
 370                                         "%d\n", ad->ad_success_threshold);
 371                         }
 372                         ad->ad_recovery = 0;
 373                         ni->ni_txrate--;
 374                 } else {
 375                         ad->ad_recovery = 0;
 376                 }
 377         }
 378         if (is_enough(ad) || old_rate != ni->ni_txrate) {
 379                 /* reset counters. */
 380                 ad->ad_tx_try_cnt[0] = 0;
 381                 ad->ad_tx_try_cnt[1] = 0;
 382                 ad->ad_tx_try_cnt[2] = 0;
 383                 ad->ad_tx_try_cnt[3] = 0;
 384                 ad->ad_tx_failure_cnt = 0;
 385         }
 386         if (old_rate != ni->ni_txrate)
 387                 amrr_update(asc, ni, ni->ni_txrate);
 388 }
 389
 390 static void
 391 amrr_tick(void *arg)
 392 {
 393         struct amrr_softc *asc = arg;
 394         struct ieee80211com *ic = asc->ic;
 395         struct ifnet *ifp = &ic->ic_if;
 396         int interval;
 397
 398         lwkt_serialize_enter(ifp->if_serializer);
 399
 400         if (ifp->if_flags & IFF_RUNNING) {
 401                 if (ic->ic_opmode == IEEE80211_M_STA)
 402                         amrr_ratectl(asc, ic->ic_bss);  /* NB: no reference */
 403                 else
 404                         ieee80211_iterate_nodes(&ic->ic_sta, amrr_ratectl, asc);
 405         }
 406         interval = asc->interval;
 407         if (ic->ic_opmode == IEEE80211_M_STA)
 408                 interval /= 2;
 409         callout_reset(&asc->timer, (interval * hz) / 1000, amrr_tick, asc);
 410
 411         lwkt_serialize_exit(ifp->if_serializer);
 412 }
 413
 414 static void
 415 amrr_sysctl_attach(struct amrr_softc *asc)
 416 {
 417         asc->debug = 0;
 418         asc->interval = 1000;
 419         asc->max_success_threshold = 10;
 420         asc->min_success_threshold = 1;
 421
 422         sysctl_ctx_init(&asc->sysctl_ctx);
 423         asc->sysctl_oid = SYSCTL_ADD_NODE(&asc->sysctl_ctx,
 424                 SYSCTL_CHILDREN(asc->ic->ic_sysctl_oid),
 425                 OID_AUTO, "amrr_ratectl", CTLFLAG_RD, 0, "");
 426         if (asc->sysctl_oid == NULL) {
 427                 printf("wlan_ratectl_amrr: create sysctl tree failed\n");
 428                 return;
 429         }
 430
 431         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
 432                        OID_AUTO, "interval", CTLFLAG_RW,
 433                        &asc->interval, 0,
 434                        "rate control: operation interval (ms)");
 435
 436         /* XXX bounds check values */
 437         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
 438                        OID_AUTO, "max_sucess_threshold", CTLFLAG_RW,
 439                        &asc->max_success_threshold, 0, "");
 440
 441         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
 442                        OID_AUTO, "min_sucess_threshold", CTLFLAG_RW,
 443                        &asc->min_success_threshold, 0, "");
 444
 445         SYSCTL_ADD_INT(&asc->sysctl_ctx, SYSCTL_CHILDREN(asc->sysctl_oid),
 446                        OID_AUTO, "debug", CTLFLAG_RW,
 447                        &asc->debug, 0, "debug level");
 448 }
 449
 450 static void *
 451 amrr_attach(struct ieee80211com *ic)
 452 {
 453         struct amrr_softc *asc;
 454
 455         amrr_nrefs++;
 456
 457         asc = kmalloc(sizeof(struct amrr_softc), M_DEVBUF, M_WAITOK | M_ZERO);
 458
 459         asc->ic = ic;
 460         callout_init(&asc->timer);
 461         amrr_sysctl_attach(asc);
 462
 463         amrr_newstate(asc, ic->ic_state);
 464
 465         return asc;
 466 }
 467
 468 static void
 469 _amrr_data_free(void *arg __unused, struct ieee80211_node *ni)
 470 {
 471         amrr_data_free(ni);
 472 }
 473
 474 void
 475 amrr_detach(void *arg)
 476 {
 477         struct amrr_softc *asc = arg;
 478         struct ieee80211com *ic = asc->ic;
 479
 480         amrr_newstate(asc, IEEE80211_S_INIT);
 481
 482         ieee80211_iterate_nodes(&ic->ic_sta, _amrr_data_free, NULL);
 483         ieee80211_iterate_nodes(&ic->ic_scan, _amrr_data_free, NULL);
 484
 485         if (asc->sysctl_oid != NULL)
 486                 sysctl_ctx_free(&asc->sysctl_ctx);
 487         kfree(asc, M_DEVBUF);
 488
 489         amrr_nrefs--;
 490 }
 491
 492 static void
 493 amrr_data_free(struct ieee80211_node *ni)
 494 {
 495         if (ni->ni_rate_data != NULL) {
 496                 kfree(ni->ni_rate_data, M_AMRR_RATECTL_DATA);
 497                 ni->ni_rate_data = NULL;
 498         }
 499 }
 500
 501 static void
 502 amrr_data_alloc(struct ieee80211_node *ni)
 503 {
 504         KKASSERT(ni->ni_rate_data == NULL);
 505         ni->ni_rate_data = kmalloc(sizeof(struct amrr_data),
 506                                   M_AMRR_RATECTL_DATA, M_NOWAIT | M_ZERO);
 507 }
 508
 509 static void
 510 amrr_data_dup(const struct ieee80211_node *oni, struct ieee80211_node *nni)
 511 {
 512         if (oni->ni_rate_data == NULL || nni->ni_rate_data == NULL)
 513                 return;
 514
 515         bcopy(oni->ni_rate_data, nni->ni_rate_data, sizeof(struct amrr_data));
 516 }
 517
 518 /*
 519  * Module glue.
 520  */
 521 static int
 522 amrr_modevent(module_t mod, int type, void *unused)
 523 {
 524         switch (type) {
 525         case MOD_LOAD:
 526                 ieee80211_ratectl_register(&amrr);
 527                 return 0;
 528         case MOD_UNLOAD:
 529                 if (amrr_nrefs) {
 530                         printf("wlan_ratectl_amrr: still in use "
 531                                "(%u dynamic refs)\n", amrr_nrefs);
 532                         return EBUSY;
 533                 }
 534                 ieee80211_ratectl_unregister(&amrr);
 535                 return 0;
 536         }
 537         return EINVAL;
 538 }
 539
 540 static moduledata_t amrr_mod = {
 541         "wlan_ratectl_amrr",
 542         amrr_modevent,
 543         0
 544 };
 545 DECLARE_MODULE(wlan_ratectl_amrr, amrr_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
 546 MODULE_VERSION(wlan_ratectl_amrr, 1);
 547 MODULE_DEPEND(wlan_ratectl_amrr, wlan, 1, 1, 1);