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 __FBSDID("$FreeBSD$");
  23
  24 /*-
  25  * Naive implementation of the Adaptive Multi Rate Retry algorithm:
  26  *
  27  * "IEEE 802.11 Rate Adaptation: A Practical Approach"
  28  *  Mathieu Lacage, Hossein Manshaei, Thierry Turletti
  29  *  INRIA Sophia - Projet Planete
  30  *  http://www-sop.inria.fr/rapports/sophia/RR-5208.html
  31  */
  32 #include "opt_wlan.h"
  33
  34 #include <sys/param.h>
  35 #include <sys/kernel.h>
  36 #include <sys/malloc.h>
  37 #include <sys/module.h>
  38 #include <sys/sbuf.h>
  39 #include <sys/socket.h>
  40 #include <sys/sysctl.h>
  41
  42 #include <net/if.h>
  43 #include <net/if_var.h>
  44 #include <net/if_media.h>
  45 #include <net/ethernet.h>
  46
  47 #ifdef INET
  48 #include <netinet/in.h>
  49 #include <netinet/if_ether.h>
  50 #endif
  51
  52 #include <net80211/ieee80211_var.h>
  53 #include <net80211/ieee80211_ht.h>
  54 #include <net80211/ieee80211_amrr.h>
  55 #include <net80211/ieee80211_ratectl.h>
  56
  57 #define is_success(amn) \
  58         ((amn)->amn_retrycnt < (amn)->amn_txcnt / 10)
  59 #define is_failure(amn) \
  60         ((amn)->amn_retrycnt > (amn)->amn_txcnt / 3)
  61 #define is_enough(amn)          \
  62         ((amn)->amn_txcnt > 10)
  63
  64 static void     amrr_setinterval(const struct ieee80211vap *, int);
  65 static void     amrr_init(struct ieee80211vap *);
  66 static void     amrr_deinit(struct ieee80211vap *);
  67 static void     amrr_node_init(struct ieee80211_node *);
  68 static void     amrr_node_deinit(struct ieee80211_node *);
  69 static int      amrr_update(struct ieee80211_amrr *,
  70                         struct ieee80211_amrr_node *, struct ieee80211_node *);
  71 static int      amrr_rate(struct ieee80211_node *, void *, uint32_t);
  72 static void     amrr_tx_complete(const struct ieee80211vap *,
  73                         const struct ieee80211_node *, int,
  74                         void *, void *);
  75 static void     amrr_tx_update(const struct ieee80211vap *vap,
  76                         const struct ieee80211_node *, void *, void *, void *);
  77 static void     amrr_sysctlattach(struct ieee80211vap *,
  78                         struct sysctl_ctx_list *, struct sysctl_oid *);
  79 static void     amrr_node_stats(struct ieee80211_node *ni, struct sbuf *s);
  80
  81 /* number of references from net80211 layer */
  82 static  int nrefs = 0;
  83
  84 static const struct ieee80211_ratectl amrr = {
  85         .ir_name        = "amrr",
  86         .ir_attach      = NULL,
  87         .ir_detach      = NULL,
  88         .ir_init        = amrr_init,
  89         .ir_deinit      = amrr_deinit,
  90         .ir_node_init   = amrr_node_init,
  91         .ir_node_deinit = amrr_node_deinit,
  92         .ir_rate        = amrr_rate,
  93         .ir_tx_complete = amrr_tx_complete,
  94         .ir_tx_update   = amrr_tx_update,
  95         .ir_setinterval = amrr_setinterval,
  96         .ir_node_stats  = amrr_node_stats,
  97 };
  98 IEEE80211_RATECTL_MODULE(amrr, 1);
  99 IEEE80211_RATECTL_ALG(amrr, IEEE80211_RATECTL_AMRR, amrr);
 100
 101 static void
 102 amrr_setinterval(const struct ieee80211vap *vap, int msecs)
 103 {
 104         struct ieee80211_amrr *amrr = vap->iv_rs;
 105         int t;
 106
 107         if (!amrr)
 108                 return;
 109
 110         if (msecs < 100)
 111                 msecs = 100;
 112         t = msecs_to_ticks(msecs);
 113         amrr->amrr_interval = (t < 1) ? 1 : t;
 114 }
 115
 116 static void
 117 amrr_init(struct ieee80211vap *vap)
 118 {
 119         struct ieee80211_amrr *amrr;
 120
 121         KASSERT(vap->iv_rs == NULL, ("%s called multiple times", __func__));
 122
 123         nrefs++;                /* XXX locking */
 124         amrr = vap->iv_rs = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr),
 125             M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
 126         if (amrr == NULL) {
 127                 if_printf(vap->iv_ifp, "couldn't alloc ratectl structure\n");
 128                 return;
 129         }
 130         amrr->amrr_min_success_threshold = IEEE80211_AMRR_MIN_SUCCESS_THRESHOLD;
 131         amrr->amrr_max_success_threshold = IEEE80211_AMRR_MAX_SUCCESS_THRESHOLD;
 132         amrr_setinterval(vap, 500 /* ms */);
 133         amrr_sysctlattach(vap, vap->iv_sysctl, vap->iv_oid);
 134 }
 135
 136 static void
 137 amrr_deinit(struct ieee80211vap *vap)
 138 {
 139         IEEE80211_FREE(vap->iv_rs, M_80211_RATECTL);
 140         KASSERT(nrefs > 0, ("imbalanced attach/detach"));
 141         nrefs--;                /* XXX locking */
 142 }
 143
 144 /*
 145  * Return whether 11n rates are possible.
 146  *
 147  * Some 11n devices may return HT information but no HT rates.
 148  * Thus, we shouldn't treat them as an 11n node.
 149  */
 150 static int
 151 amrr_node_is_11n(struct ieee80211_node *ni)
 152 {
 153
 154         if (ni->ni_chan == NULL)
 155                 return (0);
 156         if (ni->ni_chan == IEEE80211_CHAN_ANYC)
 157                 return (0);
 158         if (IEEE80211_IS_CHAN_HT(ni->ni_chan) && ni->ni_htrates.rs_nrates == 0)
 159                 return (0);
 160         return (IEEE80211_IS_CHAN_HT(ni->ni_chan));
 161 }
 162
 163 static void
 164 amrr_node_init(struct ieee80211_node *ni)
 165 {
 166         const struct ieee80211_rateset *rs = NULL;
 167         struct ieee80211vap *vap = ni->ni_vap;
 168         struct ieee80211_amrr *amrr = vap->iv_rs;
 169         struct ieee80211_amrr_node *amn;
 170         uint8_t rate;
 171
 172         if (!amrr) {
 173                 if_printf(vap->iv_ifp, "ratectl structure was not allocated, "
 174                     "per-node structure allocation skipped\n");
 175                 return;
 176         }
 177
 178         if (ni->ni_rctls == NULL) {
 179                 ni->ni_rctls = amn = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr_node),
 180                     M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
 181                 if (amn == NULL) {
 182                         if_printf(vap->iv_ifp, "couldn't alloc per-node ratectl "
 183                             "structure\n");
 184                         return;
 185                 }
 186         } else
 187                 amn = ni->ni_rctls;
 188         amn->amn_amrr = amrr;
 189         amn->amn_success = 0;
 190         amn->amn_recovery = 0;
 191         amn->amn_txcnt = amn->amn_retrycnt = 0;
 192         amn->amn_success_threshold = amrr->amrr_min_success_threshold;
 193
 194         /* 11n or not? Pick the right rateset */
 195         if (amrr_node_is_11n(ni)) {
 196                 /* XXX ew */
 197                 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 198                     "%s: 11n node", __func__);
 199                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 200         } else {
 201                 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 202                     "%s: non-11n node", __func__);
 203                 rs = &ni->ni_rates;
 204         }
 205
 206         /* Initial rate - lowest */
 207         rate = rs->rs_rates[0];
 208
 209         /* XXX clear the basic rate flag if it's not 11n */
 210         if (! amrr_node_is_11n(ni))
 211                 rate &= IEEE80211_RATE_VAL;
 212
 213         /* pick initial rate from the rateset - HT or otherwise */
 214         /* Pick something low that's likely to succeed */
 215         for (amn->amn_rix = rs->rs_nrates - 1; amn->amn_rix > 0;
 216             amn->amn_rix--) {
 217                 /* legacy - anything < 36mbit, stop searching */
 218                 /* 11n - stop at MCS4 */
 219                 if (amrr_node_is_11n(ni)) {
 220                         if ((rs->rs_rates[amn->amn_rix] & 0x1f) < 4)
 221                                 break;
 222                 } else if ((rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL) <= 72)
 223                         break;
 224         }
 225         rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
 226
 227         /* if the rate is an 11n rate, ensure the MCS bit is set */
 228         if (amrr_node_is_11n(ni))
 229                 rate |= IEEE80211_RATE_MCS;
 230
 231         /* Assign initial rate from the rateset */
 232         ni->ni_txrate = rate;
 233         amn->amn_ticks = ticks;
 234
 235         /* XXX TODO: we really need a rate-to-string method */
 236         /* XXX TODO: non-11n rate should be divided by two.. */
 237         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 238             "AMRR: nrates=%d, initial rate %s%d",
 239             rs->rs_nrates,
 240             amrr_node_is_11n(ni) ? "MCS " : "",
 241             rate & IEEE80211_RATE_VAL);
 242 }
 243
 244 static void
 245 amrr_node_deinit(struct ieee80211_node *ni)
 246 {
 247         IEEE80211_FREE(ni->ni_rctls, M_80211_RATECTL);
 248 }
 249
 250 static int
 251 amrr_update(struct ieee80211_amrr *amrr, struct ieee80211_amrr_node *amn,
 252     struct ieee80211_node *ni)
 253 {
 254         int rix = amn->amn_rix;
 255         const struct ieee80211_rateset *rs = NULL;
 256
 257         KASSERT(is_enough(amn), ("txcnt %d", amn->amn_txcnt));
 258
 259         /* 11n or not? Pick the right rateset */
 260         if (amrr_node_is_11n(ni)) {
 261                 /* XXX ew */
 262                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 263         } else {
 264                 rs = &ni->ni_rates;
 265         }
 266
 267         /* XXX TODO: we really need a rate-to-string method */
 268         /* XXX TODO: non-11n rate should be divided by two.. */
 269         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 270             "AMRR: current rate %d, txcnt=%d, retrycnt=%d",
 271             rs->rs_rates[rix] & IEEE80211_RATE_VAL,
 272             amn->amn_txcnt,
 273             amn->amn_retrycnt);
 274
 275         /*
 276          * XXX This is totally bogus for 11n, as although high MCS
 277          * rates for each stream may be failing, the next stream
 278          * should be checked.
 279          *
 280          * Eg, if MCS5 is ok but MCS6/7 isn't, and we can go up to
 281          * MCS23, we should skip 6/7 and try 8 onwards.
 282          */
 283         if (is_success(amn)) {
 284                 amn->amn_success++;
 285                 if (amn->amn_success >= amn->amn_success_threshold &&
 286                     rix + 1 < rs->rs_nrates) {
 287                         amn->amn_recovery = 1;
 288                         amn->amn_success = 0;
 289                         rix++;
 290                         /* XXX TODO: we really need a rate-to-string method */
 291                         /* XXX TODO: non-11n rate should be divided by two.. */
 292                         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 293                             "AMRR increasing rate %d (txcnt=%d retrycnt=%d)",
 294                             rs->rs_rates[rix] & IEEE80211_RATE_VAL,
 295                             amn->amn_txcnt, amn->amn_retrycnt);
 296                 } else {
 297                         amn->amn_recovery = 0;
 298                 }
 299         } else if (is_failure(amn)) {
 300                 amn->amn_success = 0;
 301                 if (rix > 0) {
 302                         if (amn->amn_recovery) {
 303                                 amn->amn_success_threshold *= 2;
 304                                 if (amn->amn_success_threshold >
 305                                     amrr->amrr_max_success_threshold)
 306                                         amn->amn_success_threshold =
 307                                             amrr->amrr_max_success_threshold;
 308                         } else {
 309                                 amn->amn_success_threshold =
 310                                     amrr->amrr_min_success_threshold;
 311                         }
 312                         rix--;
 313                         /* XXX TODO: we really need a rate-to-string method */
 314                         /* XXX TODO: non-11n rate should be divided by two.. */
 315                         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 316                             "AMRR decreasing rate %d (txcnt=%d retrycnt=%d)",
 317                             rs->rs_rates[rix] & IEEE80211_RATE_VAL,
 318                             amn->amn_txcnt, amn->amn_retrycnt);
 319                 }
 320                 amn->amn_recovery = 0;
 321         }
 322
 323         /* reset counters */
 324         amn->amn_txcnt = 0;
 325         amn->amn_retrycnt = 0;
 326
 327         return rix;
 328 }
 329
 330 /*
 331  * Return the rate index to use in sending a data frame.
 332  * Update our internal state if it's been long enough.
 333  * If the rate changes we also update ni_txrate to match.
 334  */
 335 static int
 336 amrr_rate(struct ieee80211_node *ni, void *arg __unused, uint32_t iarg __unused)
 337 {
 338         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 339         struct ieee80211_amrr *amrr;
 340         const struct ieee80211_rateset *rs = NULL;
 341         int rix;
 342
 343         /* XXX should return -1 here, but drivers may not expect this... */
 344         if (!amn)
 345         {
 346                 ni->ni_txrate = ni->ni_rates.rs_rates[0];
 347                 return 0;
 348         }
 349
 350         amrr = amn->amn_amrr;
 351
 352         /* 11n or not? Pick the right rateset */
 353         if (amrr_node_is_11n(ni)) {
 354                 /* XXX ew */
 355                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 356         } else {
 357                 rs = &ni->ni_rates;
 358         }
 359
 360         if (is_enough(amn) && (ticks - amn->amn_ticks) > amrr->amrr_interval) {
 361                 rix = amrr_update(amrr, amn, ni);
 362                 if (rix != amn->amn_rix) {
 363                         /* update public rate */
 364                         ni->ni_txrate = rs->rs_rates[rix];
 365                         /* XXX strip basic rate flag from txrate, if non-11n */
 366                         if (amrr_node_is_11n(ni))
 367                                 ni->ni_txrate |= IEEE80211_RATE_MCS;
 368                         else
 369                                 ni->ni_txrate &= IEEE80211_RATE_VAL;
 370                         amn->amn_rix = rix;
 371                 }
 372                 amn->amn_ticks = ticks;
 373         } else
 374                 rix = amn->amn_rix;
 375         return rix;
 376 }
 377
 378 /*
 379  * Update statistics with tx complete status.  Ok is non-zero
 380  * if the packet is known to be ACK'd.  Retries has the number
 381  * retransmissions (i.e. xmit attempts - 1).
 382  */
 383 static void
 384 amrr_tx_complete(const struct ieee80211vap *vap,
 385     const struct ieee80211_node *ni, int ok,
 386     void *arg1, void *arg2 __unused)
 387 {
 388         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 389         int retries = *(int *)arg1;
 390
 391         if (!amn)
 392                 return;
 393
 394         amn->amn_txcnt++;
 395         if (ok)
 396                 amn->amn_success++;
 397         amn->amn_retrycnt += retries;
 398 }
 399
 400 /*
 401  * Set tx count/retry statistics explicitly.  Intended for
 402  * drivers that poll the device for statistics maintained
 403  * in the device.
 404  */
 405 static void
 406 amrr_tx_update(const struct ieee80211vap *vap, const struct ieee80211_node *ni,
 407     void *arg1, void *arg2, void *arg3)
 408 {
 409         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 410         int txcnt = *(int *)arg1, success = *(int *)arg2, retrycnt = *(int *)arg3;
 411
 412         amn->amn_txcnt = txcnt;
 413         amn->amn_success = success;
 414         amn->amn_retrycnt = retrycnt;
 415 }
 416
 417 static int
 418 amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)
 419 {
 420         struct ieee80211vap *vap = arg1;
 421         struct ieee80211_amrr *amrr = vap->iv_rs;
 422         int msecs, error;
 423
 424         if (!amrr)
 425                 return ENOMEM;
 426
 427         msecs = ticks_to_msecs(amrr->amrr_interval);
 428         error = sysctl_handle_int(oidp, &msecs, 0, req);
 429         if (error || !req->newptr)
 430                 return error;
 431         amrr_setinterval(vap, msecs);
 432         return 0;
 433 }
 434
 435 static void
 436 amrr_sysctlattach(struct ieee80211vap *vap,
 437     struct sysctl_ctx_list *ctx, struct sysctl_oid *tree)
 438 {
 439         struct ieee80211_amrr *amrr = vap->iv_rs;
 440
 441         if (!amrr)
 442                 return;
 443
 444         SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 445             "amrr_rate_interval", CTLTYPE_INT | CTLFLAG_RW, vap,
 446             0, amrr_sysctl_interval, "I", "amrr operation interval (ms)");
 447         /* XXX bounds check values */
 448         SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 449             "amrr_max_sucess_threshold", CTLFLAG_RW,
 450             &amrr->amrr_max_success_threshold, 0, "");
 451         SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 452             "amrr_min_sucess_threshold", CTLFLAG_RW,
 453             &amrr->amrr_min_success_threshold, 0, "");
 454 }
 455
 456 static void
 457 amrr_node_stats(struct ieee80211_node *ni, struct sbuf *s)
 458 {
 459         int rate;
 460         struct ieee80211_amrr_node *amn = ni->ni_rctls;
 461         struct ieee80211_rateset *rs;
 462
 463         /* XXX TODO: check locking? */
 464
 465         if (!amn)
 466                 return;
 467
 468         /* XXX TODO: this should be a method */
 469         if (amrr_node_is_11n(ni)) {
 470                 rs = (struct ieee80211_rateset *) &ni->ni_htrates;
 471                 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
 472                 sbuf_printf(s, "rate: MCS %d\n", rate);
 473         } else {
 474                 rs = &ni->ni_rates;
 475                 rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
 476                 sbuf_printf(s, "rate: %d Mbit\n", rate / 2);
 477         }
 478
 479         sbuf_printf(s, "ticks: %d\n", amn->amn_ticks);
 480         sbuf_printf(s, "txcnt: %u\n", amn->amn_txcnt);
 481         sbuf_printf(s, "success: %u\n", amn->amn_success);
 482         sbuf_printf(s, "success_threshold: %u\n", amn->amn_success_threshold);
 483         sbuf_printf(s, "recovery: %u\n", amn->amn_recovery);
 484         sbuf_printf(s, "retry_cnt: %u\n", amn->amn_retrycnt);
 485 }