sys/net80211/ieee80211_amrr.c

   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
 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
 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
 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 /*
 142  * Return whether 11n rates are possible.
 143  *
 144  * Some 11n devices may return HT information but no HT rates.
 145  * Thus, we shouldn't treat them as an 11n node.
 146  */
 147 static int
 148 amrr_node_is_11n(struct ieee80211_node *ni)
 149 {
 150
 151         if (ni->ni_chan == NULL)
 152                 return (0);
 153         if (ni->ni_chan == IEEE80211_CHAN_ANYC)
 154                 return (0);
 155         if (IEEE80211_IS_CHAN_HT(ni->ni_chan) && ni->ni_htrates.rs_nrates == 0)
 156                 return (0);
 157         return (IEEE80211_IS_CHAN_HT(ni->ni_chan));
 158 }
 159
 160 static void
 161 amrr_node_init(struct ieee80211_node *ni)
 162 {
 163         const struct ieee80211_rateset *rs = NULL;
 164         struct ieee80211vap *vap = ni->ni_vap;
 165         struct ieee80211_amrr *amrr = vap->iv_rs;
 166         struct ieee80211_amrr_node *amn;
 167         uint8_t rate;
 168
 169         if (!amrr) {
 170                 if_printf(vap->iv_ifp, "ratectl structure was not allocated, "
 171                     "per-node structure allocation skipped\n");
 172                 return;
 173         }
 174
 175         if (ni->ni_rctls == NULL) {
 176                 ni->ni_rctls = amn = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr_node),
 177                     M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
 178                 if (amn == NULL) {
 179                         if_printf(vap->iv_ifp, "couldn't alloc per-node ratectl "
 180                             "structure\n");
 181                         return;
 182                 }
 183         } else
 184                 amn = ni->ni_rctls;
 185         amn->amn_amrr = amrr;
 186         amn->amn_success = 0;
 187         amn->amn_recovery = 0;
 188         amn->amn_txcnt = amn->amn_retrycnt = 0;
 189         amn->amn_success_threshold = amrr->amrr_min_success_threshold;
 190
 191         /* 11n or not? Pick the right rateset */
 192         if (amrr_node_is_11n(ni)) {
 193                 /* XXX ew */
 194                 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 195                     "%s: 11n node", __func__);
 196                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 197         } else {
 198                 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 199                     "%s: non-11n node", __func__);
 200                 rs = &ni->ni_rates;
 201         }
 202
 203         /* Initial rate - lowest */
 204         rate = rs->rs_rates[0];
 205
 206         /* XXX clear the basic rate flag if it's not 11n */
 207         if (! amrr_node_is_11n(ni))
 208                 rate &= IEEE80211_RATE_VAL;
 209
 210         /* pick initial rate from the rateset - HT or otherwise */
 211         /* Pick something low that's likely to succeed */
 212         for (amn->amn_rix = rs->rs_nrates - 1; amn->amn_rix > 0;
 213             amn->amn_rix--) {
 214                 /* legacy - anything < 36mbit, stop searching */
 215                 /* 11n - stop at MCS4 */
 216                 if (amrr_node_is_11n(ni)) {
 217                         if ((rs->rs_rates[amn->amn_rix] & 0x1f) < 4)
 218                                 break;
 219                 } else if ((rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL) <= 72)
 220                         break;
 221         }
 222         rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
 223
 224         /* if the rate is an 11n rate, ensure the MCS bit is set */
 225         if (amrr_node_is_11n(ni))
 226                 rate |= IEEE80211_RATE_MCS;
 227
 228         /* Assign initial rate from the rateset */
 229         ni->ni_txrate = rate;
 230         amn->amn_ticks = ticks;
 231
 232         /* XXX TODO: we really need a rate-to-string method */
 233         /* XXX TODO: non-11n rate should be divided by two.. */
 234         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 235             "AMRR: nrates=%d, initial rate %s%d",
 236             rs->rs_nrates,
 237             amrr_node_is_11n(ni) ? "MCS " : "",
 238             rate & IEEE80211_RATE_VAL);
 239 }
 240
 241 static void
 242 amrr_node_deinit(struct ieee80211_node *ni)
 243 {
 244         IEEE80211_FREE(ni->ni_rctls, M_80211_RATECTL);
 245 }
 246
 247 static int
 248 amrr_update(struct ieee80211_amrr *amrr, struct ieee80211_amrr_node *amn,
 249     struct ieee80211_node *ni)
 250 {
 251         int rix = amn->amn_rix;
 252         const struct ieee80211_rateset *rs = NULL;
 253
 254         KASSERT(is_enough(amn), ("txcnt %d", amn->amn_txcnt));
 255
 256         /* 11n or not? Pick the right rateset */
 257         if (amrr_node_is_11n(ni)) {
 258                 /* XXX ew */
 259                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 260         } else {
 261                 rs = &ni->ni_rates;
 262         }
 263
 264         /* XXX TODO: we really need a rate-to-string method */
 265         /* XXX TODO: non-11n rate should be divided by two.. */
 266         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 267             "AMRR: current rate %d, txcnt=%d, retrycnt=%d",
 268             rs->rs_rates[rix] & IEEE80211_RATE_VAL,
 269             amn->amn_txcnt,
 270             amn->amn_retrycnt);
 271
 272         /*
 273          * XXX This is totally bogus for 11n, as although high MCS
 274          * rates for each stream may be failing, the next stream
 275          * should be checked.
 276          *
 277          * Eg, if MCS5 is ok but MCS6/7 isn't, and we can go up to
 278          * MCS23, we should skip 6/7 and try 8 onwards.
 279          */
 280         if (is_success(amn)) {
 281                 amn->amn_success++;
 282                 if (amn->amn_success >= amn->amn_success_threshold &&
 283                     rix + 1 < rs->rs_nrates) {
 284                         amn->amn_recovery = 1;
 285                         amn->amn_success = 0;
 286                         rix++;
 287                         /* XXX TODO: we really need a rate-to-string method */
 288                         /* XXX TODO: non-11n rate should be divided by two.. */
 289                         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 290                             "AMRR increasing rate %d (txcnt=%d retrycnt=%d)",
 291                             rs->rs_rates[rix] & IEEE80211_RATE_VAL,
 292                             amn->amn_txcnt, amn->amn_retrycnt);
 293                 } else {
 294                         amn->amn_recovery = 0;
 295                 }
 296         } else if (is_failure(amn)) {
 297                 amn->amn_success = 0;
 298                 if (rix > 0) {
 299                         if (amn->amn_recovery) {
 300                                 amn->amn_success_threshold *= 2;
 301                                 if (amn->amn_success_threshold >
 302                                     amrr->amrr_max_success_threshold)
 303                                         amn->amn_success_threshold =
 304                                             amrr->amrr_max_success_threshold;
 305                         } else {
 306                                 amn->amn_success_threshold =
 307                                     amrr->amrr_min_success_threshold;
 308                         }
 309                         rix--;
 310                         /* XXX TODO: we really need a rate-to-string method */
 311                         /* XXX TODO: non-11n rate should be divided by two.. */
 312                         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 313                             "AMRR decreasing rate %d (txcnt=%d retrycnt=%d)",
 314                             rs->rs_rates[rix] & IEEE80211_RATE_VAL,
 315                             amn->amn_txcnt, amn->amn_retrycnt);
 316                 }
 317                 amn->amn_recovery = 0;
 318         }
 319
 320         /* reset counters */
 321         amn->amn_txcnt = 0;
 322         amn->amn_retrycnt = 0;
 323
 324         return rix;
 325 }
 326
 327 /*
 328  * Return the rate index to use in sending a data frame.
 329  * Update our internal state if it's been long enough.
 330  * If the rate changes we also update ni_txrate to match.
 331  */
 332 static int
 333 amrr_rate(struct ieee80211_node *ni, void *arg __unused, uint32_t iarg __unused)
 334 {
 335         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 336         struct ieee80211_amrr *amrr;
 337         const struct ieee80211_rateset *rs = NULL;
 338         int rix;
 339
 340         /* XXX should return -1 here, but drivers may not expect this... */
 341         if (!amn)
 342         {
 343                 ni->ni_txrate = ni->ni_rates.rs_rates[0];
 344                 return 0;
 345         }
 346
 347         amrr = amn->amn_amrr;
 348
 349         /* 11n or not? Pick the right rateset */
 350         if (amrr_node_is_11n(ni)) {
 351                 /* XXX ew */
 352                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 353         } else {
 354                 rs = &ni->ni_rates;
 355         }
 356
 357         if (is_enough(amn) && (ticks - amn->amn_ticks) > amrr->amrr_interval) {
 358                 rix = amrr_update(amrr, amn, ni);
 359                 if (rix != amn->amn_rix) {
 360                         /* update public rate */
 361                         ni->ni_txrate = rs->rs_rates[rix];
 362                         /* XXX strip basic rate flag from txrate, if non-11n */
 363                         if (amrr_node_is_11n(ni))
 364                                 ni->ni_txrate |= IEEE80211_RATE_MCS;
 365                         else
 366                                 ni->ni_txrate &= IEEE80211_RATE_VAL;
 367                         amn->amn_rix = rix;
 368                 }
 369                 amn->amn_ticks = ticks;
 370         } else
 371                 rix = amn->amn_rix;
 372         return rix;
 373 }
 374
 375 /*
 376  * Update statistics with tx complete status.  Ok is non-zero
 377  * if the packet is known to be ACK'd.  Retries has the number
 378  * retransmissions (i.e. xmit attempts - 1).
 379  */
 380 static void
 381 amrr_tx_complete(const struct ieee80211_node *ni,
 382     const struct ieee80211_ratectl_tx_status *status)
 383 {
 384         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 385         int retries;
 386
 387         if (!amn)
 388                 return;
 389
 390         retries = 0;
 391         if (status->flags & IEEE80211_RATECTL_STATUS_LONG_RETRY)
 392                 retries = status->long_retries;
 393
 394         amn->amn_txcnt++;
 395         if (status->status == IEEE80211_RATECTL_TX_SUCCESS)
 396                 amn->amn_success++;
 397         amn->amn_retrycnt += retries;
 398 }
 399
 400 static void
 401 amrr_tx_update_cb(void *arg, struct ieee80211_node *ni)
 402 {
 403         struct ieee80211_ratectl_tx_stats *stats = arg;
 404         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 405         int txcnt, success, retrycnt;
 406
 407         if (!amn)
 408                 return;
 409
 410         txcnt = stats->nframes;
 411         success = stats->nsuccess;
 412         retrycnt = 0;
 413         if (stats->flags & IEEE80211_RATECTL_TX_STATS_RETRIES)
 414                 retrycnt = stats->nretries;
 415
 416         amn->amn_txcnt += txcnt;
 417         amn->amn_success += success;
 418         amn->amn_retrycnt += retrycnt;
 419 }
 420
 421 /*
 422  * Set tx count/retry statistics explicitly.  Intended for
 423  * drivers that poll the device for statistics maintained
 424  * in the device.
 425  */
 426 static void
 427 amrr_tx_update(struct ieee80211vap *vap,
 428     struct ieee80211_ratectl_tx_stats *stats)
 429 {
 430
 431         if (stats->flags & IEEE80211_RATECTL_TX_STATS_NODE)
 432                 amrr_tx_update_cb(stats, stats->ni);
 433         else {
 434                 ieee80211_iterate_nodes_vap(&vap->iv_ic->ic_sta, vap,
 435                     amrr_tx_update_cb, stats);
 436         }
 437 }
 438
 439 static int
 440 amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)
 441 {
 442         struct ieee80211vap *vap = arg1;
 443         struct ieee80211_amrr *amrr = vap->iv_rs;
 444         int msecs, error;
 445
 446         if (!amrr)
 447                 return ENOMEM;
 448
 449         msecs = ticks_to_msecs(amrr->amrr_interval);
 450         error = sysctl_handle_int(oidp, &msecs, 0, req);
 451         if (error || !req->newptr)
 452                 return error;
 453         amrr_setinterval(vap, msecs);
 454         return 0;
 455 }
 456
 457 static void
 458 amrr_sysctlattach(struct ieee80211vap *vap,
 459     struct sysctl_ctx_list *ctx, struct sysctl_oid *tree)
 460 {
 461         struct ieee80211_amrr *amrr = vap->iv_rs;
 462
 463         if (!amrr)
 464                 return;
 465
 466         SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 467             "amrr_rate_interval", CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 468             vap, 0, amrr_sysctl_interval, "I", "amrr operation interval (ms)");
 469         /* XXX bounds check values */
 470         SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 471             "amrr_max_sucess_threshold", CTLFLAG_RW,
 472             &amrr->amrr_max_success_threshold, 0, "");
 473         SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 474             "amrr_min_sucess_threshold", CTLFLAG_RW,
 475             &amrr->amrr_min_success_threshold, 0, "");
 476 }
 477
 478 static void
 479 amrr_print_node_rate(struct ieee80211_amrr_node *amn,
 480     struct ieee80211_node *ni, struct sbuf *s)
 481 {
 482         int rate;
 483         struct ieee80211_rateset *rs;
 484
 485         if (amrr_node_is_11n(ni)) {
 486                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 487                 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
 488                 sbuf_printf(s, "rate: MCS %d\n", rate);
 489         } else {
 490                 rs = &ni->ni_rates;
 491                 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
 492                 sbuf_printf(s, "rate: %d Mbit\n", rate / 2);
 493         }
 494 }
 495
 496 static void
 497 amrr_node_stats(struct ieee80211_node *ni, struct sbuf *s)
 498 {
 499         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 500
 501         /* XXX TODO: check locking? */
 502
 503         if (!amn)
 504                 return;
 505
 506         amrr_print_node_rate(amn, ni, s);
 507         sbuf_printf(s, "ticks: %d\n", amn->amn_ticks);
 508         sbuf_printf(s, "txcnt: %u\n", amn->amn_txcnt);
 509         sbuf_printf(s, "success: %u\n", amn->amn_success);
 510         sbuf_printf(s, "success_threshold: %u\n", amn->amn_success_threshold);
 511         sbuf_printf(s, "recovery: %u\n", amn->amn_recovery);
 512         sbuf_printf(s, "retry_cnt: %u\n", amn->amn_retrycnt);
 513 }