6/sys/dev/ath/ath_rate/sample/sample.c

   1 /*-
   2  * Copyright (c) 2005 John Bicket
   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
  37 #include <sys/cdefs.h>
  38 __FBSDID("$FreeBSD$");
  39
  40 /*
  41  * John Bicket's SampleRate control algorithm.
  42  */
  43 #include "opt_inet.h"
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/sysctl.h>
  48 #include <sys/module.h>
  49 #include <sys/kernel.h>
  50 #include <sys/lock.h>
  51 #include <sys/mutex.h>
  52 #include <sys/errno.h>
  53
  54 #include <machine/bus.h>
  55 #include <machine/resource.h>
  56 #include <sys/bus.h>
  57
  58 #include <sys/socket.h>
  59
  60 #include <net/if.h>
  61 #include <net/if_media.h>
  62 #include <net/if_arp.h>
  63 #include <net/ethernet.h>               /* XXX for ether_sprintf */
  64
  65 #include <net80211/ieee80211_var.h>
  66
  67 #include <net/bpf.h>
  68
  69 #ifdef INET
  70 #include <netinet/in.h>
  71 #include <netinet/if_ether.h>
  72 #endif
  73
  74 #include <dev/ath/if_athvar.h>
  75 #include <dev/ath/ath_rate/sample/sample.h>
  76 #include <contrib/dev/ath/ah_desc.h>
  77
  78 #define SAMPLE_DEBUG
  79 #ifdef SAMPLE_DEBUG
  80 enum {
  81         ATH_DEBUG_NODE          = 0x00080000,   /* node management */
  82         ATH_DEBUG_RATE          = 0x00000010,   /* rate control */
  83         ATH_DEBUG_ANY           = 0xffffffff
  84 };
  85 #define DPRINTF(sc, m, fmt, ...) do {                           \
  86         if (sc->sc_debug & (m))                                 \
  87                 printf(fmt, __VA_ARGS__);                       \
  88 } while (0)
  89 #else
  90 #define DPRINTF(sc, m, fmt, ...) do {                           \
  91         (void) sc;                                              \
  92 } while (0)
  93 #endif
  94
  95 /*
  96  * This file is an implementation of the SampleRate algorithm
  97  * in "Bit-rate Selection in Wireless Networks"
  98  * (http://www.pdos.lcs.mit.edu/papers/jbicket-ms.ps)
  99  *
 100  * SampleRate chooses the bit-rate it predicts will provide the most
 101  * throughput based on estimates of the expected per-packet
 102  * transmission time for each bit-rate.  SampleRate periodically sends
 103  * packets at bit-rates other than the current one to estimate when
 104  * another bit-rate will provide better performance. SampleRate
 105  * switches to another bit-rate when its estimated per-packet
 106  * transmission time becomes smaller than the current bit-rate's.
 107  * SampleRate reduces the number of bit-rates it must sample by
 108  * eliminating those that could not perform better than the one
 109  * currently being used.  SampleRate also stops probing at a bit-rate
 110  * if it experiences several successive losses.
 111  *
 112  * The difference between the algorithm in the thesis and the one in this
 113  * file is that the one in this file uses a ewma instead of a window.
 114  *
 115  * Also, this implementation tracks the average transmission time for
 116  * a few different packet sizes independently for each link.
 117  */
 118
 119 #define STALE_FAILURE_TIMEOUT_MS 10000
 120 #define MIN_SWITCH_MS 1000
 121
 122 static void     ath_rate_ctl_reset(struct ath_softc *, struct ieee80211_node *);
 123
 124 static __inline int
 125 size_to_bin(int size)
 126 {
 127         int x = 0;
 128         for (x = 0; x < NUM_PACKET_SIZE_BINS; x++) {
 129                 if (size <= packet_size_bins[x]) {
 130                         return x;
 131                 }
 132         }
 133         return NUM_PACKET_SIZE_BINS-1;
 134 }
 135 static __inline int
 136 bin_to_size(int index) {
 137         return packet_size_bins[index];
 138 }
 139
 140 static __inline int
 141 rate_to_ndx(struct sample_node *sn, int rate) {
 142         int x = 0;
 143         for (x = 0; x < sn->num_rates; x++) {
 144                 if (sn->rates[x].rate == rate) {
 145                         return x;
 146                 }
 147         }
 148         return -1;
 149 }
 150
 151 void
 152 ath_rate_node_init(struct ath_softc *sc, struct ath_node *an)
 153 {
 154         DPRINTF(sc, ATH_DEBUG_NODE, "%s:\n", __func__);
 155         /* NB: assumed to be zero'd by caller */
 156 }
 157
 158 void
 159 ath_rate_node_cleanup(struct ath_softc *sc, struct ath_node *an)
 160 {
 161         DPRINTF(sc, ATH_DEBUG_NODE, "%s:\n", __func__);
 162 }
 163
 164
 165 /*
 166  * returns the ndx with the lowest average_tx_time,
 167  * or -1 if all the average_tx_times are 0.
 168  */
 169 static __inline int best_rate_ndx(struct sample_node *sn, int size_bin,
 170                                   int require_acked_before)
 171 {
 172         int x = 0;
 173         int best_rate_ndx = 0;
 174         int best_rate_tt = 0;
 175         for (x = 0; x < sn->num_rates; x++) {
 176                 int tt = sn->stats[size_bin][x].average_tx_time;
 177                 if (tt <= 0 || (require_acked_before &&
 178                                 !sn->stats[size_bin][x].packets_acked)) {
 179                         continue;
 180                 }
 181
 182                 /* 9 megabits never works better than 12 */
 183                 if (sn->rates[x].rate == 18)
 184                         continue;
 185
 186                 /* don't use a bit-rate that has been failing */
 187                 if (sn->stats[size_bin][x].successive_failures > 3)
 188                         continue;
 189
 190                 if (!best_rate_tt || best_rate_tt > tt) {
 191                         best_rate_tt = tt;
 192                         best_rate_ndx = x;
 193                 }
 194         }
 195         return (best_rate_tt) ? best_rate_ndx : -1;
 196 }
 197
 198 /*
 199  * pick a good "random" bit-rate to sample other than the current one
 200  */
 201 static __inline int
 202 pick_sample_ndx(struct sample_node *sn, int size_bin)
 203 {
 204         int x = 0;
 205         int current_ndx = 0;
 206         unsigned current_tt = 0;
 207
 208         current_ndx = sn->current_rate[size_bin];
 209         if (current_ndx < 0) {
 210                 /* no successes yet, send at the lowest bit-rate */
 211                 return 0;
 212         }
 213
 214         current_tt = sn->stats[size_bin][current_ndx].average_tx_time;
 215
 216         for (x = 0; x < sn->num_rates; x++) {
 217                 int ndx = (sn->last_sample_ndx[size_bin]+1+x) % sn->num_rates;
 218
 219                 /* don't sample the current bit-rate */
 220                 if (ndx == current_ndx)
 221                         continue;
 222
 223                 /* this bit-rate is always worse than the current one */
 224                 if (sn->stats[size_bin][ndx].perfect_tx_time > current_tt)
 225                         continue;
 226
 227                 /* rarely sample bit-rates that fail a lot */
 228                 if (ticks - sn->stats[size_bin][ndx].last_tx < ((hz * STALE_FAILURE_TIMEOUT_MS)/1000) &&
 229                     sn->stats[size_bin][ndx].successive_failures > 3)
 230                         continue;
 231
 232                 /* don't sample more than 2 indexes higher
 233                  * for rates higher than 11 megabits
 234                  */
 235                 if (sn->rates[ndx].rate > 22 && ndx > current_ndx + 2)
 236                         continue;
 237
 238                 /* 9 megabits never works better than 12 */
 239                 if (sn->rates[ndx].rate == 18)
 240                         continue;
 241
 242                 /* if we're using 11 megabits, only sample up to 12 megabits
 243                  */
 244                 if (sn->rates[current_ndx].rate == 22 && ndx > current_ndx + 1)
 245                         continue;
 246
 247                 sn->last_sample_ndx[size_bin] = ndx;
 248                 return ndx;
 249         }
 250         return current_ndx;
 251 }
 252
 253 void
 254 ath_rate_findrate(struct ath_softc *sc, struct ath_node *an,
 255                   int shortPreamble, size_t frameLen,
 256                   u_int8_t *rix, int *try0, u_int8_t *txrate)
 257 {
 258         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 259         struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc);
 260         struct ieee80211com *ic = &sc->sc_ic;
 261         int ndx, size_bin, mrr, best_ndx, change_rates;
 262         unsigned average_tx_time;
 263
 264         mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT);
 265         size_bin = size_to_bin(frameLen);
 266         best_ndx = best_rate_ndx(sn, size_bin, !mrr);
 267
 268         if (best_ndx >= 0) {
 269                 average_tx_time = sn->stats[size_bin][best_ndx].average_tx_time;
 270         } else {
 271                 average_tx_time = 0;
 272         }
 273
 274         if (sn->static_rate_ndx != -1) {
 275                 ndx = sn->static_rate_ndx;
 276                 *try0 = ATH_TXMAXTRY;
 277         } else {
 278                 *try0 = mrr ? 2 : ATH_TXMAXTRY;
 279
 280                 if (sn->sample_tt[size_bin] < average_tx_time * (sn->packets_since_sample[size_bin]*ssc->ath_sample_rate/100)) {
 281                         /*
 282                          * we want to limit the time measuring the performance
 283                          * of other bit-rates to ath_sample_rate% of the
 284                          * total transmission time.
 285                          */
 286                         ndx = pick_sample_ndx(sn, size_bin);
 287                         if (ndx != sn->current_rate[size_bin]) {
 288                                 sn->current_sample_ndx[size_bin] = ndx;
 289                         } else {
 290                                 sn->current_sample_ndx[size_bin] = -1;
 291                         }
 292                         sn->packets_since_sample[size_bin] = 0;
 293
 294                 } else {
 295                         change_rates = 0;
 296                         if (!sn->packets_sent[size_bin] || best_ndx == -1) {
 297                                 /* no packet has been sent successfully yet */
 298                                 for (ndx = sn->num_rates-1; ndx > 0; ndx--) {
 299                                         /*
 300                                          * pick the highest rate <= 36 Mbps
 301                                          * that hasn't failed.
 302                                          */
 303                                         if (sn->rates[ndx].rate <= 72 &&
 304                                             sn->stats[size_bin][ndx].successive_failures == 0) {
 305                                                 break;
 306                                         }
 307                                 }
 308                                 change_rates = 1;
 309                                 best_ndx = ndx;
 310                         } else if (sn->packets_sent[size_bin] < 20) {
 311                                 /* let the bit-rate switch quickly during the first few packets */
 312                                 change_rates = 1;
 313                         } else if (ticks - ((hz*MIN_SWITCH_MS)/1000) > sn->ticks_since_switch[size_bin]) {
 314                                 /* 2 seconds have gone by */
 315                                 change_rates = 1;
 316                         } else if (average_tx_time * 2 < sn->stats[size_bin][sn->current_rate[size_bin]].average_tx_time) {
 317                                 /* the current bit-rate is twice as slow as the best one */
 318                                 change_rates = 1;
 319                         }
 320
 321                         sn->packets_since_sample[size_bin]++;
 322
 323                         if (change_rates) {
 324                                 if (best_ndx != sn->current_rate[size_bin]) {
 325                                         DPRINTF(sc, ATH_DEBUG_RATE,
 326 "%s: %s size %d switch rate %d (%d/%d) -> %d (%d/%d) after %d packets mrr %d\n",
 327                                             __func__,
 328                                             ether_sprintf(an->an_node.ni_macaddr),
 329                                             packet_size_bins[size_bin],
 330                                             sn->rates[sn->current_rate[size_bin]].rate,
 331                                             sn->stats[size_bin][sn->current_rate[size_bin]].average_tx_time,
 332                                             sn->stats[size_bin][sn->current_rate[size_bin]].perfect_tx_time,
 333                                             sn->rates[best_ndx].rate,
 334                                             sn->stats[size_bin][best_ndx].average_tx_time,
 335                                             sn->stats[size_bin][best_ndx].perfect_tx_time,
 336                                             sn->packets_since_switch[size_bin],
 337                                             mrr);
 338                                 }
 339                                 sn->packets_since_switch[size_bin] = 0;
 340                                 sn->current_rate[size_bin] = best_ndx;
 341                                 sn->ticks_since_switch[size_bin] = ticks;
 342                         }
 343                         ndx = sn->current_rate[size_bin];
 344                         sn->packets_since_switch[size_bin]++;
 345                         if (size_bin == 0) {
 346                                 /*
 347                                  * set the visible txrate for this node
 348                                  * to the rate of small packets
 349                                  */
 350                                 an->an_node.ni_txrate = ndx;
 351                         }
 352                 }
 353         }
 354
 355         KASSERT(ndx >= 0 && ndx < sn->num_rates, ("ndx is %d", ndx));
 356
 357         *rix = sn->rates[ndx].rix;
 358         if (shortPreamble) {
 359                 *txrate = sn->rates[ndx].shortPreambleRateCode;
 360         } else {
 361                 *txrate = sn->rates[ndx].rateCode;
 362         }
 363         sn->packets_sent[size_bin]++;
 364 }
 365
 366 void
 367 ath_rate_setupxtxdesc(struct ath_softc *sc, struct ath_node *an,
 368                       struct ath_desc *ds, int shortPreamble, u_int8_t rix)
 369 {
 370         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 371         int rateCode = -1;
 372         int frame_size = 0;
 373         int size_bin = 0;
 374         int ndx = 0;
 375
 376         size_bin = size_to_bin(frame_size);     // TODO: it's correct that frame_size alway 0 ?
 377         ndx = sn->current_rate[size_bin]; /* retry at the current bit-rate */
 378
 379         if (!sn->stats[size_bin][ndx].packets_acked) {
 380                 ndx = 0;  /* use the lowest bit-rate */
 381         }
 382
 383         if (shortPreamble) {
 384                 rateCode = sn->rates[ndx].shortPreambleRateCode;
 385         } else {
 386                 rateCode = sn->rates[ndx].rateCode;
 387         }
 388         ath_hal_setupxtxdesc(sc->sc_ah, ds
 389                              , rateCode, 3              /* series 1 */
 390                              , sn->rates[0].rateCode, 3 /* series 2 */
 391                              , 0, 0                     /* series 3 */
 392                              );
 393 }
 394
 395 static void
 396 update_stats(struct ath_softc *sc, struct ath_node *an,
 397                   int frame_size,
 398                   int ndx0, int tries0,
 399                   int ndx1, int tries1,
 400                   int ndx2, int tries2,
 401                   int ndx3, int tries3,
 402                   int short_tries, int tries, int status)
 403 {
 404         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 405         struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc);
 406         int tt = 0;
 407         int tries_so_far = 0;
 408         int size_bin = 0;
 409         int size = 0;
 410         int rate = 0;
 411
 412         size_bin = size_to_bin(frame_size);
 413         size = bin_to_size(size_bin);
 414
 415         if (!(0 <= ndx0 && ndx0 < sn->num_rates)) {
 416                 printf("%s: bogus ndx0 %d, max %u, mode %u\n",
 417                     __func__, ndx0, sn->num_rates, sc->sc_curmode);
 418                 return;
 419         }
 420         rate = sn->rates[ndx0].rate;
 421
 422         tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx0].rix,
 423                                         short_tries,
 424                                         MIN(tries0, tries) - 1);
 425         tries_so_far += tries0;
 426         if (tries1 && tries0 < tries) {
 427                 if (!(0 <= ndx1 && ndx1 < sn->num_rates)) {
 428                         printf("%s: bogus ndx1 %d, max %u, mode %u\n",
 429                             __func__, ndx1, sn->num_rates, sc->sc_curmode);
 430                         return;
 431                 }
 432                 tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx1].rix,
 433                                                 short_tries,
 434                                                 MIN(tries1 + tries_so_far, tries) - tries_so_far - 1);
 435         }
 436         tries_so_far += tries1;
 437
 438         if (tries2 && tries0 + tries1 < tries) {
 439                 if (!(0 <= ndx2 && ndx2 < sn->num_rates)) {
 440                         printf("%s: bogus ndx2 %d, max %u, mode %u\n",
 441                             __func__, ndx2, sn->num_rates, sc->sc_curmode);
 442                         return;
 443                 }
 444                 tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx2].rix,
 445                                                short_tries,
 446                                                 MIN(tries2 + tries_so_far, tries) - tries_so_far - 1);
 447         }
 448
 449         tries_so_far += tries2;
 450
 451         if (tries3 && tries0 + tries1 + tries2 < tries) {
 452                 if (!(0 <= ndx3 && ndx3 < sn->num_rates)) {
 453                         printf("%s: bogus ndx3 %d, max %u, mode %u\n",
 454                             __func__, ndx3, sn->num_rates, sc->sc_curmode);
 455                         return;
 456                 }
 457                 tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx3].rix,
 458                                                 short_tries,
 459                                                 MIN(tries3 + tries_so_far, tries) - tries_so_far - 1);
 460         }
 461         if (sn->stats[size_bin][ndx0].total_packets < (100 / (100 - ssc->ath_smoothing_rate))) {
 462                 /* just average the first few packets */
 463                 int avg_tx = sn->stats[size_bin][ndx0].average_tx_time;
 464                 int packets = sn->stats[size_bin][ndx0].total_packets;
 465                 sn->stats[size_bin][ndx0].average_tx_time = (tt+(avg_tx*packets))/(packets+1);
 466         } else {
 467                 /* use a ewma */
 468                 sn->stats[size_bin][ndx0].average_tx_time =
 469                         ((sn->stats[size_bin][ndx0].average_tx_time * ssc->ath_smoothing_rate) +
 470                          (tt * (100 - ssc->ath_smoothing_rate))) / 100;
 471         }
 472
 473         if (status) {
 474                 int y;
 475                 sn->stats[size_bin][ndx0].successive_failures++;
 476                 for (y = size_bin+1; y < NUM_PACKET_SIZE_BINS; y++) {
 477                         /* also say larger packets failed since we
 478                          * assume if a small packet fails at a lower
 479                          * bit-rate then a larger one will also.
 480                          */
 481                         sn->stats[y][ndx0].successive_failures++;
 482                         sn->stats[y][ndx0].last_tx = ticks;
 483                         sn->stats[y][ndx0].tries += tries;
 484                         sn->stats[y][ndx0].total_packets++;
 485                 }
 486         } else {
 487                 sn->stats[size_bin][ndx0].packets_acked++;
 488                 sn->stats[size_bin][ndx0].successive_failures = 0;
 489         }
 490         sn->stats[size_bin][ndx0].tries += tries;
 491         sn->stats[size_bin][ndx0].last_tx = ticks;
 492         sn->stats[size_bin][ndx0].total_packets++;
 493
 494
 495         if (ndx0 == sn->current_sample_ndx[size_bin]) {
 496                 DPRINTF(sc, ATH_DEBUG_RATE,
 497 "%s: %s size %d %s sample rate %d tries (%d/%d) tt %d avg_tt (%d/%d)\n",
 498                     __func__, ether_sprintf(an->an_node.ni_macaddr),
 499                     size,
 500                     status ? "FAIL" : "OK",
 501                     rate, short_tries, tries, tt,
 502                     sn->stats[size_bin][ndx0].average_tx_time,
 503                     sn->stats[size_bin][ndx0].perfect_tx_time);
 504                 sn->sample_tt[size_bin] = tt;
 505                 sn->current_sample_ndx[size_bin] = -1;
 506         }
 507 }
 508
 509 void
 510 ath_rate_tx_complete(struct ath_softc *sc, struct ath_node *an,
 511         const struct ath_buf *bf)
 512 {
 513         struct ieee80211com *ic = &sc->sc_ic;
 514         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 515         const struct ath_tx_status *ts = &bf->bf_status.ds_txstat;
 516         const struct ath_desc *ds0 = &bf->bf_desc[0];
 517         int final_rate, short_tries, long_tries, frame_size;
 518         int mrr;
 519
 520         final_rate = sc->sc_hwmap[ts->ts_rate &~ HAL_TXSTAT_ALTRATE].ieeerate;
 521         short_tries = ts->ts_shortretry;
 522         long_tries = ts->ts_longretry + 1;
 523         frame_size = ds0->ds_ctl0 & 0x0fff; /* low-order 12 bits of ds_ctl0 */
 524         if (frame_size == 0)                /* NB: should not happen */
 525                 frame_size = 1500;
 526
 527         if (sn->num_rates <= 0) {
 528                 DPRINTF(sc, ATH_DEBUG_RATE,
 529                     "%s: %s size %d %s rate/try %d/%d no rates yet\n",
 530                     __func__, ether_sprintf(an->an_node.ni_macaddr),
 531                     bin_to_size(size_to_bin(frame_size)),
 532                     ts->ts_status ? "FAIL" : "OK",
 533                     short_tries, long_tries);
 534                 return;
 535         }
 536
 537         if (ts->ts_status) {            /* this packet failed */
 538                 DPRINTF(sc, ATH_DEBUG_RATE,
 539 "%s: %s size %d rate/try [%d/%d %d/%d %d/%d %d/%d] FAIL tries [%d/%d]\n",
 540                     __func__,
 541                     ether_sprintf(an->an_node.ni_macaddr),
 542                     bin_to_size(size_to_bin(frame_size)),
 543                     sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate0)].ieeerate,
 544                         MS(ds0->ds_ctl2, AR_XmitDataTries0),
 545                     sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate1)].ieeerate,
 546                         MS(ds0->ds_ctl2, AR_XmitDataTries1),
 547                     sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate2)].ieeerate,
 548                         MS(ds0->ds_ctl2, AR_XmitDataTries2),
 549                     sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate3)].ieeerate,
 550                         MS(ds0->ds_ctl2, AR_XmitDataTries3),
 551                     short_tries, long_tries);
 552         }
 553
 554         mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT);
 555         if (!mrr || !(ts->ts_rate & HAL_TXSTAT_ALTRATE)) {
 556                 int ndx = rate_to_ndx(sn, final_rate);
 557
 558                 /*
 559                  * Only one rate was used; optimize work.
 560                  */
 561                 DPRINTF(sc, ATH_DEBUG_RATE,
 562                     "%s: %s size %d %s rate/try %d/%d/%d\n",
 563                      __func__, ether_sprintf(an->an_node.ni_macaddr),
 564                      bin_to_size(size_to_bin(frame_size)),
 565                      ts->ts_status ? "FAIL" : "OK",
 566                      final_rate, short_tries, long_tries);
 567                 update_stats(sc, an, frame_size,
 568                              ndx, long_tries,
 569                              0, 0,
 570                              0, 0,
 571                              0, 0,
 572                              short_tries, long_tries, ts->ts_status);
 573         } else {
 574                 int rate0, tries0, ndx0;
 575                 int rate1, tries1, ndx1;
 576                 int rate2, tries2, ndx2;
 577                 int rate3, tries3, ndx3;
 578                 int finalTSIdx = ts->ts_finaltsi;
 579
 580                 /*
 581                  * Process intermediate rates that failed.
 582                  */
 583                 rate0 = sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate0)].ieeerate;
 584                 tries0 = MS(ds0->ds_ctl2, AR_XmitDataTries0);
 585                 ndx0 = rate_to_ndx(sn, rate0);
 586
 587                 rate1 = sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate1)].ieeerate;
 588                 tries1 = MS(ds0->ds_ctl2, AR_XmitDataTries1);
 589                 ndx1 = rate_to_ndx(sn, rate1);
 590
 591                 rate2 = sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate2)].ieeerate;
 592                 tries2 = MS(ds0->ds_ctl2, AR_XmitDataTries2);
 593                 ndx2 = rate_to_ndx(sn, rate2);
 594
 595                 rate3 = sc->sc_hwmap[MS(ds0->ds_ctl3, AR_XmitRate3)].ieeerate;
 596                 tries3 = MS(ds0->ds_ctl2, AR_XmitDataTries3);
 597                 ndx3 = rate_to_ndx(sn, rate3);
 598
 599 #if 1
 600                 DPRINTF(sc, ATH_DEBUG_RATE,
 601 "%s: %s size %d finaltsidx %d tries %d %s rate/try [%d/%d %d/%d %d/%d %d/%d]\n",
 602                      __func__, ether_sprintf(an->an_node.ni_macaddr),
 603                      bin_to_size(size_to_bin(frame_size)),
 604                      finalTSIdx,
 605                      long_tries,
 606                      ts->ts_status ? "FAIL" : "OK",
 607                      rate0, tries0,
 608                      rate1, tries1,
 609                      rate2, tries2,
 610                      rate3, tries3);
 611 #endif
 612
 613                 /*
 614                  * NB: series > 0 are not penalized for failure
 615                  * based on the try counts under the assumption
 616                  * that losses are often bursty and since we
 617                  * sample higher rates 1 try at a time doing so
 618                  * may unfairly penalize them.
 619                  */
 620                 if (tries0) {
 621                         update_stats(sc, an, frame_size,
 622                                      ndx0, tries0,
 623                                      ndx1, tries1,
 624                                      ndx2, tries2,
 625                                      ndx3, tries3,
 626                                      short_tries, long_tries,
 627                                      long_tries > tries0);
 628                         long_tries -= tries0;
 629                 }
 630
 631                 if (tries1 && finalTSIdx > 0) {
 632                         update_stats(sc, an, frame_size,
 633                                      ndx1, tries1,
 634                                      ndx2, tries2,
 635                                      ndx3, tries3,
 636                                      0, 0,
 637                                      short_tries, long_tries,
 638                                      ts->ts_status);
 639                         long_tries -= tries1;
 640                 }
 641
 642                 if (tries2 && finalTSIdx > 1) {
 643                         update_stats(sc, an, frame_size,
 644                                      ndx2, tries2,
 645                                      ndx3, tries3,
 646                                      0, 0,
 647                                      0, 0,
 648                                      short_tries, long_tries,
 649                                      ts->ts_status);
 650                         long_tries -= tries2;
 651                 }
 652
 653                 if (tries3 && finalTSIdx > 2) {
 654                         update_stats(sc, an, frame_size,
 655                                      ndx3, tries3,
 656                                      0, 0,
 657                                      0, 0,
 658                                      0, 0,
 659                                      short_tries, long_tries,
 660                                      ts->ts_status);
 661                 }
 662         }
 663 }
 664
 665 void
 666 ath_rate_newassoc(struct ath_softc *sc, struct ath_node *an, int isnew)
 667 {
 668         DPRINTF(sc, ATH_DEBUG_NODE, "%s: %s isnew %d\n", __func__,
 669              ether_sprintf(an->an_node.ni_macaddr), isnew);
 670         if (isnew)
 671                 ath_rate_ctl_reset(sc, &an->an_node);
 672 }
 673
 674 /*
 675  * Initialize the tables for a node.
 676  */
 677 static void
 678 ath_rate_ctl_reset(struct ath_softc *sc, struct ieee80211_node *ni)
 679 {
 680 #define RATE(_ix)       (ni->ni_rates.rs_rates[(_ix)] & IEEE80211_RATE_VAL)
 681         struct ieee80211com *ic = &sc->sc_ic;
 682         struct ath_node *an = ATH_NODE(ni);
 683         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 684         const HAL_RATE_TABLE *rt = sc->sc_currates;
 685         int x, y, srate;
 686
 687         KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode));
 688         sn->static_rate_ndx = -1;
 689         if (ic->ic_fixed_rate != IEEE80211_FIXED_RATE_NONE) {
 690                 /*
 691                  * A fixed rate is to be used; ic_fixed_rate is an
 692                  * index into the supported rate set.  Convert this
 693                  * to the index into the negotiated rate set for
 694                  * the node.
 695                  */
 696                 const struct ieee80211_rateset *rs =
 697                         &ic->ic_sup_rates[ic->ic_curmode];
 698                 int r = rs->rs_rates[ic->ic_fixed_rate] & IEEE80211_RATE_VAL;
 699                 /* NB: the rate set is assumed sorted */
 700                 srate = ni->ni_rates.rs_nrates - 1;
 701                 for (; srate >= 0 && RATE(srate) != r; srate--)
 702                         ;
 703                 KASSERT(srate >= 0,
 704                         ("fixed rate %d not in rate set", ic->ic_fixed_rate));
 705                 sn->static_rate_ndx = srate;
 706         }
 707
 708         DPRINTF(sc, ATH_DEBUG_RATE, "%s: %s size 1600 rate/tt",
 709             __func__, ether_sprintf(ni->ni_macaddr));
 710
 711         sn->num_rates = ni->ni_rates.rs_nrates;
 712         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 713                 sn->rates[x].rate = ni->ni_rates.rs_rates[x] & IEEE80211_RATE_VAL;
 714                 sn->rates[x].rix = sc->sc_rixmap[sn->rates[x].rate];
 715                 if (sn->rates[x].rix == 0xff) {
 716                         DPRINTF(sc, ATH_DEBUG_RATE,
 717                             "%s: ignore bogus rix at %d\n", __func__, x);
 718                         continue;
 719                 }
 720                 sn->rates[x].rateCode = rt->info[sn->rates[x].rix].rateCode;
 721                 sn->rates[x].shortPreambleRateCode =
 722                         rt->info[sn->rates[x].rix].rateCode |
 723                         rt->info[sn->rates[x].rix].shortPreamble;
 724
 725                 DPRINTF(sc, ATH_DEBUG_RATE, " %d/%d", sn->rates[x].rate,
 726                     calc_usecs_unicast_packet(sc, 1600, sn->rates[x].rix, 0,0));
 727         }
 728         DPRINTF(sc, ATH_DEBUG_RATE, "%s\n", "");
 729
 730         /* set the visible bit-rate to the lowest one available */
 731         ni->ni_txrate = 0;
 732         sn->num_rates = ni->ni_rates.rs_nrates;
 733
 734         for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) {
 735                 int size = bin_to_size(y);
 736                 int ndx = 0;
 737                 sn->packets_sent[y] = 0;
 738                 sn->current_sample_ndx[y] = -1;
 739                 sn->last_sample_ndx[y] = 0;
 740
 741                 for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 742                         sn->stats[y][x].successive_failures = 0;
 743                         sn->stats[y][x].tries = 0;
 744                         sn->stats[y][x].total_packets = 0;
 745                         sn->stats[y][x].packets_acked = 0;
 746                         sn->stats[y][x].last_tx = 0;
 747
 748                         sn->stats[y][x].perfect_tx_time =
 749                                 calc_usecs_unicast_packet(sc, size,
 750                                                           sn->rates[x].rix,
 751                                                           0, 0);
 752                         sn->stats[y][x].average_tx_time = sn->stats[y][x].perfect_tx_time;
 753                 }
 754
 755                 /* set the initial rate */
 756                 for (ndx = sn->num_rates-1; ndx > 0; ndx--) {
 757                         if (sn->rates[ndx].rate <= 72) {
 758                                 break;
 759                         }
 760                 }
 761                 sn->current_rate[y] = ndx;
 762         }
 763
 764         DPRINTF(sc, ATH_DEBUG_RATE,
 765             "%s: %s %d rates %d%sMbps (%dus)- %d%sMbps (%dus)\n",
 766             __func__, ether_sprintf(ni->ni_macaddr),
 767             sn->num_rates,
 768             sn->rates[0].rate/2, sn->rates[0].rate % 0x1 ? ".5" : "",
 769             sn->stats[1][0].perfect_tx_time,
 770             sn->rates[sn->num_rates-1].rate/2,
 771                 sn->rates[sn->num_rates-1].rate % 0x1 ? ".5" : "",
 772             sn->stats[1][sn->num_rates-1].perfect_tx_time
 773         );
 774
 775         if (sn->static_rate_ndx != -1)
 776                 ni->ni_txrate = sn->static_rate_ndx;
 777         else
 778                 ni->ni_txrate = sn->current_rate[0];
 779 #undef RATE
 780 }
 781
 782 static void
 783 rate_cb(void *arg, struct ieee80211_node *ni)
 784 {
 785         struct ath_softc *sc = arg;
 786
 787         ath_rate_newassoc(sc, ATH_NODE(ni), 1);
 788 }
 789
 790 /*
 791  * Reset the rate control state for each 802.11 state transition.
 792  */
 793 void
 794 ath_rate_newstate(struct ath_softc *sc, enum ieee80211_state state)
 795 {
 796         struct ieee80211com *ic = &sc->sc_ic;
 797
 798         if (state == IEEE80211_S_RUN) {
 799                 if (ic->ic_opmode != IEEE80211_M_STA) {
 800                         /*
 801                          * Sync rates for associated stations and neighbors.
 802                          */
 803                         ieee80211_iterate_nodes(&ic->ic_sta, rate_cb, sc);
 804                 }
 805                 ath_rate_newassoc(sc, ATH_NODE(ic->ic_bss), 1);
 806         }
 807 }
 808
 809 static void
 810 ath_rate_sysctlattach(struct ath_softc *sc, struct sample_softc *osc)
 811 {
 812         struct sysctl_ctx_list *ctx = device_get_sysctl_ctx(sc->sc_dev);
 813         struct sysctl_oid *tree = device_get_sysctl_tree(sc->sc_dev);
 814
 815         /* XXX bounds check [0..100] */
 816         SYSCTL_ADD_INT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 817                 "smoothing_rate", CTLFLAG_RW, &osc->ath_smoothing_rate, 0,
 818                 "rate control: retry threshold to credit rate raise (%%)");
 819         /* XXX bounds check [2..100] */
 820         SYSCTL_ADD_INT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 821                 "sample_rate", CTLFLAG_RW, &osc->ath_sample_rate,0,
 822                 "rate control: # good periods before raising rate");
 823 }
 824
 825 struct ath_ratectrl *
 826 ath_rate_attach(struct ath_softc *sc)
 827 {
 828         struct sample_softc *osc;
 829
 830         DPRINTF(sc, ATH_DEBUG_ANY, "%s:\n", __func__);
 831         osc = malloc(sizeof(struct sample_softc), M_DEVBUF, M_NOWAIT|M_ZERO);
 832         if (osc == NULL)
 833                 return NULL;
 834         osc->arc.arc_space = sizeof(struct sample_node);
 835         osc->ath_smoothing_rate = 95;   /* ewma percentage (out of 100) */
 836         osc->ath_sample_rate = 10;      /* send a different bit-rate 1/X packets */
 837         ath_rate_sysctlattach(sc, osc);
 838         return &osc->arc;
 839 }
 840
 841 void
 842 ath_rate_detach(struct ath_ratectrl *arc)
 843 {
 844         struct sample_softc *osc = (struct sample_softc *) arc;
 845
 846         free(osc, M_DEVBUF);
 847 }
 848
 849 /*
 850  * Module glue.
 851  */
 852 static int
 853 sample_modevent(module_t mod, int type, void *unused)
 854 {
 855         switch (type) {
 856         case MOD_LOAD:
 857                 if (bootverbose)
 858                         printf("ath_rate: version 1.2 <SampleRate bit-rate selection algorithm>\n");
 859                 return 0;
 860         case MOD_UNLOAD:
 861                 return 0;
 862         }
 863         return EINVAL;
 864 }
 865
 866 static moduledata_t sample_mod = {
 867         "ath_rate",
 868         sample_modevent,
 869         0
 870 };
 871 DECLARE_MODULE(ath_rate, sample_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
 872 MODULE_VERSION(ath_rate, 1);
 873 MODULE_DEPEND(ath_rate, ath_hal, 1, 1, 1);      /* Atheros HAL */
 874 MODULE_DEPEND(ath_rate, wlan, 1, 1, 1);