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
  38 #include <sys/cdefs.h>
  39 __FBSDID("$FreeBSD$");
  40
  41 /*
  42  * John Bicket's SampleRate control algorithm.
  43  */
  44 #include "opt_inet.h"
  45 #include "opt_wlan.h"
  46
  47 #include <sys/param.h>
  48 #include <sys/systm.h>
  49 #include <sys/sysctl.h>
  50 #include <sys/kernel.h>
  51 #include <sys/lock.h>
  52 #include <sys/mutex.h>
  53 #include <sys/errno.h>
  54
  55 #include <machine/bus.h>
  56 #include <machine/resource.h>
  57 #include <sys/bus.h>
  58
  59 #include <sys/socket.h>
  60
  61 #include <net/if.h>
  62 #include <net/if_media.h>
  63 #include <net/if_arp.h>
  64 #include <net/ethernet.h>               /* XXX for ether_sprintf */
  65
  66 #include <net80211/ieee80211_var.h>
  67
  68 #include <net/bpf.h>
  69
  70 #ifdef INET
  71 #include <netinet/in.h>
  72 #include <netinet/if_ether.h>
  73 #endif
  74
  75 #include <dev/ath/if_athvar.h>
  76 #include <dev/ath/ath_rate/sample/sample.h>
  77 #include <dev/ath/ath_hal/ah_desc.h>
  78 #include <dev/ath/ath_rate/sample/tx_schedules.h>
  79
  80 /*
  81  * This file is an implementation of the SampleRate algorithm
  82  * in "Bit-rate Selection in Wireless Networks"
  83  * (http://www.pdos.lcs.mit.edu/papers/jbicket-ms.ps)
  84  *
  85  * SampleRate chooses the bit-rate it predicts will provide the most
  86  * throughput based on estimates of the expected per-packet
  87  * transmission time for each bit-rate.  SampleRate periodically sends
  88  * packets at bit-rates other than the current one to estimate when
  89  * another bit-rate will provide better performance. SampleRate
  90  * switches to another bit-rate when its estimated per-packet
  91  * transmission time becomes smaller than the current bit-rate's.
  92  * SampleRate reduces the number of bit-rates it must sample by
  93  * eliminating those that could not perform better than the one
  94  * currently being used.  SampleRate also stops probing at a bit-rate
  95  * if it experiences several successive losses.
  96  *
  97  * The difference between the algorithm in the thesis and the one in this
  98  * file is that the one in this file uses a ewma instead of a window.
  99  *
 100  * Also, this implementation tracks the average transmission time for
 101  * a few different packet sizes independently for each link.
 102  */
 103
 104 static void     ath_rate_ctl_reset(struct ath_softc *, struct ieee80211_node *);
 105
 106 static const int packet_size_bins[NUM_PACKET_SIZE_BINS] = { 250, 1600 };
 107
 108 static __inline int
 109 size_to_bin(int size)
 110 {
 111 #if NUM_PACKET_SIZE_BINS > 1
 112         if (size <= packet_size_bins[0])
 113                 return 0;
 114 #endif
 115 #if NUM_PACKET_SIZE_BINS > 2
 116         if (size <= packet_size_bins[1])
 117                 return 1;
 118 #endif
 119 #if NUM_PACKET_SIZE_BINS > 3
 120         if (size <= packet_size_bins[2])
 121                 return 2;
 122 #endif
 123 #if NUM_PACKET_SIZE_BINS > 4
 124 #error "add support for more packet sizes"
 125 #endif
 126         return NUM_PACKET_SIZE_BINS-1;
 127 }
 128
 129 static __inline int
 130 bin_to_size(int index)
 131 {
 132         return packet_size_bins[index];
 133 }
 134
 135 void
 136 ath_rate_node_init(struct ath_softc *sc, struct ath_node *an)
 137 {
 138         /* NB: assumed to be zero'd by caller */
 139 }
 140
 141 void
 142 ath_rate_node_cleanup(struct ath_softc *sc, struct ath_node *an)
 143 {
 144 }
 145
 146 static int
 147 dot11rate(const HAL_RATE_TABLE *rt, int rix)
 148 {
 149         return rt->info[rix].phy == IEEE80211_T_HT ?
 150             rt->info[rix].dot11Rate : (rt->info[rix].dot11Rate & IEEE80211_RATE_VAL) / 2;
 151 }
 152
 153 /*
 154  * Return the rix with the lowest average_tx_time,
 155  * or -1 if all the average_tx_times are 0.
 156  */
 157 static __inline int
 158 pick_best_rate(struct sample_node *sn, const HAL_RATE_TABLE *rt,
 159     int size_bin, int require_acked_before)
 160 {
 161         int best_rate_rix, best_rate_tt;
 162         uint32_t mask;
 163         int rix, tt;
 164
 165         best_rate_rix = 0;
 166         best_rate_tt = 0;
 167         for (mask = sn->ratemask, rix = 0; mask != 0; mask >>= 1, rix++) {
 168                 if ((mask & 1) == 0)            /* not a supported rate */
 169                         continue;
 170
 171                 tt = sn->stats[size_bin][rix].average_tx_time;
 172                 if (tt <= 0 ||
 173                     (require_acked_before &&
 174                      !sn->stats[size_bin][rix].packets_acked))
 175                         continue;
 176
 177                 /* don't use a bit-rate that has been failing */
 178                 if (sn->stats[size_bin][rix].successive_failures > 3)
 179                         continue;
 180
 181                 if (best_rate_tt == 0 || tt < best_rate_tt) {
 182                         best_rate_tt = tt;
 183                         best_rate_rix = rix;
 184                 }
 185         }
 186         return (best_rate_tt ? best_rate_rix : -1);
 187 }
 188
 189 /*
 190  * Pick a good "random" bit-rate to sample other than the current one.
 191  */
 192 static __inline int
 193 pick_sample_rate(struct sample_softc *ssc , struct sample_node *sn,
 194     const HAL_RATE_TABLE *rt, int size_bin)
 195 {
 196 #define DOT11RATE(ix)   (rt->info[ix].dot11Rate & IEEE80211_RATE_VAL)
 197 #define MCS(ix)         (rt->info[ix].dot11Rate | IEEE80211_RATE_MCS)
 198         int current_rix, rix;
 199         unsigned current_tt;
 200         uint32_t mask;
 201
 202         current_rix = sn->current_rix[size_bin];
 203         if (current_rix < 0) {
 204                 /* no successes yet, send at the lowest bit-rate */
 205                 return 0;
 206         }
 207
 208         current_tt = sn->stats[size_bin][current_rix].average_tx_time;
 209
 210         rix = sn->last_sample_rix[size_bin]+1;  /* next sample rate */
 211         mask = sn->ratemask &~ (1<<current_rix);/* don't sample current rate */
 212         while (mask != 0) {
 213                 if ((mask & (1<<rix)) == 0) {   /* not a supported rate */
 214         nextrate:
 215                         if (++rix >= rt->rateCount)
 216                                 rix = 0;
 217                         continue;
 218                 }
 219
 220                 /* this bit-rate is always worse than the current one */
 221                 if (sn->stats[size_bin][rix].perfect_tx_time > current_tt) {
 222                         mask &= ~(1<<rix);
 223                         goto nextrate;
 224                 }
 225
 226                 /* rarely sample bit-rates that fail a lot */
 227                 if (sn->stats[size_bin][rix].successive_failures > ssc->max_successive_failures &&
 228                     ticks - sn->stats[size_bin][rix].last_tx < ssc->stale_failure_timeout) {
 229                         mask &= ~(1<<rix);
 230                         goto nextrate;
 231                 }
 232
 233                 /* don't sample more than 2 rates higher for rates > 11M */
 234                 if (DOT11RATE(rix) > 2*11 && rix > current_rix + 2) {
 235                         mask &= ~(1<<rix);
 236                         goto nextrate;
 237                 }
 238
 239                 sn->last_sample_rix[size_bin] = rix;
 240                 return rix;
 241         }
 242         return current_rix;
 243 #undef DOT11RATE
 244 #undef  MCS
 245 }
 246
 247 void
 248 ath_rate_findrate(struct ath_softc *sc, struct ath_node *an,
 249                   int shortPreamble, size_t frameLen,
 250                   u_int8_t *rix0, int *try0, u_int8_t *txrate)
 251 {
 252 #define DOT11RATE(ix)   (rt->info[ix].dot11Rate & IEEE80211_RATE_VAL)
 253 #define MCS(ix)         (rt->info[ix].dot11Rate | IEEE80211_RATE_MCS)
 254 #define RATE(ix)        (DOT11RATE(ix) / 2)
 255         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 256         struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc);
 257         struct ifnet *ifp = sc->sc_ifp;
 258         struct ieee80211com *ic = ifp->if_l2com;
 259         const HAL_RATE_TABLE *rt = sc->sc_currates;
 260         const int size_bin = size_to_bin(frameLen);
 261         int rix, mrr, best_rix, change_rates;
 262         unsigned average_tx_time;
 263
 264         if (sn->static_rix != -1) {
 265                 rix = sn->static_rix;
 266                 *try0 = ATH_TXMAXTRY;
 267                 goto done;
 268         }
 269
 270         mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT);
 271
 272         best_rix = pick_best_rate(sn, rt, size_bin, !mrr);
 273         if (best_rix >= 0) {
 274                 average_tx_time = sn->stats[size_bin][best_rix].average_tx_time;
 275         } else {
 276                 average_tx_time = 0;
 277         }
 278         /*
 279          * Limit the time measuring the performance of other tx
 280          * rates to sample_rate% of the total transmission time.
 281          */
 282         if (sn->sample_tt[size_bin] < average_tx_time * (sn->packets_since_sample[size_bin]*ssc->sample_rate/100)) {
 283                 rix = pick_sample_rate(ssc, sn, rt, size_bin);
 284                 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL,
 285                      &an->an_node, "size %u sample rate %d current rate %d",
 286                      bin_to_size(size_bin), RATE(rix),
 287                      RATE(sn->current_rix[size_bin]));
 288                 if (rix != sn->current_rix[size_bin]) {
 289                         sn->current_sample_rix[size_bin] = rix;
 290                 } else {
 291                         sn->current_sample_rix[size_bin] = -1;
 292                 }
 293                 sn->packets_since_sample[size_bin] = 0;
 294         } else {
 295                 change_rates = 0;
 296                 if (!sn->packets_sent[size_bin] || best_rix == -1) {
 297                         /* no packet has been sent successfully yet */
 298                         for (rix = rt->rateCount-1; rix > 0; rix--) {
 299                                 if ((sn->ratemask & (1<<rix)) == 0)
 300                                         continue;
 301                                 /*
 302                                  * Pick the highest rate <= 36 Mbps
 303                                  * that hasn't failed.
 304                                  */
 305                                 if (DOT11RATE(rix) <= 72 &&
 306                                     sn->stats[size_bin][rix].successive_failures == 0) {
 307                                         break;
 308                                 }
 309                         }
 310                         change_rates = 1;
 311                         best_rix = rix;
 312                 } else if (sn->packets_sent[size_bin] < 20) {
 313                         /* let the bit-rate switch quickly during the first few packets */
 314                         change_rates = 1;
 315                 } else if (ticks - ssc->min_switch > sn->ticks_since_switch[size_bin]) {
 316                         /* min_switch seconds have gone by */
 317                         change_rates = 1;
 318                 } else if (2*average_tx_time < sn->stats[size_bin][sn->current_rix[size_bin]].average_tx_time) {
 319                         /* the current bit-rate is twice as slow as the best one */
 320                         change_rates = 1;
 321                 }
 322
 323                 sn->packets_since_sample[size_bin]++;
 324
 325                 if (change_rates) {
 326                         if (best_rix != sn->current_rix[size_bin]) {
 327                                 IEEE80211_NOTE(an->an_node.ni_vap,
 328                                     IEEE80211_MSG_RATECTL,
 329                                     &an->an_node,
 330 "%s: size %d switch rate %d (%d/%d) -> %d (%d/%d) after %d packets mrr %d",
 331                                     __func__,
 332                                     bin_to_size(size_bin),
 333                                     RATE(sn->current_rix[size_bin]),
 334                                     sn->stats[size_bin][sn->current_rix[size_bin]].average_tx_time,
 335                                     sn->stats[size_bin][sn->current_rix[size_bin]].perfect_tx_time,
 336                                     RATE(best_rix),
 337                                     sn->stats[size_bin][best_rix].average_tx_time,
 338                                     sn->stats[size_bin][best_rix].perfect_tx_time,
 339                                     sn->packets_since_switch[size_bin],
 340                                     mrr);
 341                         }
 342                         sn->packets_since_switch[size_bin] = 0;
 343                         sn->current_rix[size_bin] = best_rix;
 344                         sn->ticks_since_switch[size_bin] = ticks;
 345                         /*
 346                          * Set the visible txrate for this node.
 347                          */
 348                         an->an_node.ni_txrate = (rt->info[best_rix].phy == IEEE80211_T_HT) ?  MCS(best_rix) : DOT11RATE(best_rix);
 349                 }
 350                 rix = sn->current_rix[size_bin];
 351                 sn->packets_since_switch[size_bin]++;
 352         }
 353         *try0 = mrr ? sn->sched[rix].t0 : ATH_TXMAXTRY;
 354 done:
 355         KASSERT(rix >= 0 && rix < rt->rateCount, ("rix is %d", rix));
 356
 357         *rix0 = rix;
 358         *txrate = rt->info[rix].rateCode
 359                 | (shortPreamble ? rt->info[rix].shortPreamble : 0);
 360         sn->packets_sent[size_bin]++;
 361 #undef DOT11RATE
 362 #undef MCS
 363 #undef RATE
 364 }
 365
 366 /*
 367  * Get the TX rates. Don't fiddle with short preamble flags for them;
 368  * the caller can do that.
 369  */
 370 void
 371 ath_rate_getxtxrates(struct ath_softc *sc, struct ath_node *an,
 372     uint8_t rix0, uint8_t *rix, uint8_t *try)
 373 {
 374         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 375         const struct txschedule *sched = &sn->sched[rix0];
 376
 377         KASSERT(rix0 == sched->r0, ("rix0 (%x) != sched->r0 (%x)!\n", rix0, sched->r0));
 378
 379 /*      rix[0] = sched->r0; */
 380         rix[1] = sched->r1;
 381         rix[2] = sched->r2;
 382         rix[3] = sched->r3;
 383
 384         try[0] = sched->t0;
 385         try[1] = sched->t1;
 386         try[2] = sched->t2;
 387         try[3] = sched->t3;
 388 }
 389
 390 void
 391 ath_rate_setupxtxdesc(struct ath_softc *sc, struct ath_node *an,
 392                       struct ath_desc *ds, int shortPreamble, u_int8_t rix)
 393 {
 394         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 395         const struct txschedule *sched = &sn->sched[rix];
 396         const HAL_RATE_TABLE *rt = sc->sc_currates;
 397         uint8_t rix1, s1code, rix2, s2code, rix3, s3code;
 398
 399         /* XXX precalculate short preamble tables */
 400         rix1 = sched->r1;
 401         s1code = rt->info[rix1].rateCode
 402                | (shortPreamble ? rt->info[rix1].shortPreamble : 0);
 403         rix2 = sched->r2;
 404         s2code = rt->info[rix2].rateCode
 405                | (shortPreamble ? rt->info[rix2].shortPreamble : 0);
 406         rix3 = sched->r3;
 407         s3code = rt->info[rix3].rateCode
 408                | (shortPreamble ? rt->info[rix3].shortPreamble : 0);
 409         ath_hal_setupxtxdesc(sc->sc_ah, ds,
 410             s1code, sched->t1,          /* series 1 */
 411             s2code, sched->t2,          /* series 2 */
 412             s3code, sched->t3);         /* series 3 */
 413 }
 414
 415 static void
 416 update_stats(struct ath_softc *sc, struct ath_node *an,
 417                   int frame_size,
 418                   int rix0, int tries0,
 419                   int rix1, int tries1,
 420                   int rix2, int tries2,
 421                   int rix3, int tries3,
 422                   int short_tries, int tries, int status)
 423 {
 424         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 425         struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc);
 426         const int size_bin = size_to_bin(frame_size);
 427         const int size = bin_to_size(size_bin);
 428         int tt, tries_so_far;
 429         int is_ht40 = (an->an_node.ni_htcap & IEEE80211_HTCAP_CHWIDTH40);
 430
 431         if (!IS_RATE_DEFINED(sn, rix0))
 432                 return;
 433         tt = calc_usecs_unicast_packet(sc, size, rix0, short_tries,
 434                 MIN(tries0, tries) - 1, is_ht40);
 435         tries_so_far = tries0;
 436
 437         if (tries1 && tries_so_far < tries) {
 438                 if (!IS_RATE_DEFINED(sn, rix1))
 439                         return;
 440                 tt += calc_usecs_unicast_packet(sc, size, rix1, short_tries,
 441                         MIN(tries1 + tries_so_far, tries) - tries_so_far - 1, is_ht40);
 442                 tries_so_far += tries1;
 443         }
 444
 445         if (tries2 && tries_so_far < tries) {
 446                 if (!IS_RATE_DEFINED(sn, rix2))
 447                         return;
 448                 tt += calc_usecs_unicast_packet(sc, size, rix2, short_tries,
 449                         MIN(tries2 + tries_so_far, tries) - tries_so_far - 1, is_ht40);
 450                 tries_so_far += tries2;
 451         }
 452
 453         if (tries3 && tries_so_far < tries) {
 454                 if (!IS_RATE_DEFINED(sn, rix3))
 455                         return;
 456                 tt += calc_usecs_unicast_packet(sc, size, rix3, short_tries,
 457                         MIN(tries3 + tries_so_far, tries) - tries_so_far - 1, is_ht40);
 458         }
 459
 460         if (sn->stats[size_bin][rix0].total_packets < ssc->smoothing_minpackets) {
 461                 /* just average the first few packets */
 462                 int avg_tx = sn->stats[size_bin][rix0].average_tx_time;
 463                 int packets = sn->stats[size_bin][rix0].total_packets;
 464                 sn->stats[size_bin][rix0].average_tx_time = (tt+(avg_tx*packets))/(packets+1);
 465         } else {
 466                 /* use a ewma */
 467                 sn->stats[size_bin][rix0].average_tx_time =
 468                         ((sn->stats[size_bin][rix0].average_tx_time * ssc->smoothing_rate) +
 469                          (tt * (100 - ssc->smoothing_rate))) / 100;
 470         }
 471
 472         if (status != 0) {
 473                 int y;
 474                 sn->stats[size_bin][rix0].successive_failures++;
 475                 for (y = size_bin+1; y < NUM_PACKET_SIZE_BINS; y++) {
 476                         /*
 477                          * Also say larger packets failed since we
 478                          * assume if a small packet fails at a
 479                          * bit-rate then a larger one will also.
 480                          */
 481                         sn->stats[y][rix0].successive_failures++;
 482                         sn->stats[y][rix0].last_tx = ticks;
 483                         sn->stats[y][rix0].tries += tries;
 484                         sn->stats[y][rix0].total_packets++;
 485                 }
 486         } else {
 487                 sn->stats[size_bin][rix0].packets_acked++;
 488                 sn->stats[size_bin][rix0].successive_failures = 0;
 489         }
 490         sn->stats[size_bin][rix0].tries += tries;
 491         sn->stats[size_bin][rix0].last_tx = ticks;
 492         sn->stats[size_bin][rix0].total_packets++;
 493
 494         if (rix0 == sn->current_sample_rix[size_bin]) {
 495                 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL,
 496                    &an->an_node,
 497 "%s: size %d %s sample rate %d tries (%d/%d) tt %d avg_tt (%d/%d)",
 498                     __func__,
 499                     size,
 500                     status ? "FAIL" : "OK",
 501                     rix0, short_tries, tries, tt,
 502                     sn->stats[size_bin][rix0].average_tx_time,
 503                     sn->stats[size_bin][rix0].perfect_tx_time);
 504                 sn->sample_tt[size_bin] = tt;
 505                 sn->current_sample_rix[size_bin] = -1;
 506         }
 507 }
 508
 509 static void
 510 badrate(struct ifnet *ifp, int series, int hwrate, int tries, int status)
 511 {
 512         if_printf(ifp, "bad series%d hwrate 0x%x, tries %u ts_status 0x%x\n",
 513             series, hwrate, tries, status);
 514 }
 515
 516 void
 517 ath_rate_tx_complete(struct ath_softc *sc, struct ath_node *an,
 518         const struct ath_buf *bf)
 519 {
 520         struct ifnet *ifp = sc->sc_ifp;
 521         struct ieee80211com *ic = ifp->if_l2com;
 522         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 523         const struct ath_tx_status *ts = &bf->bf_status.ds_txstat;
 524         const struct ath_desc *ds0 = &bf->bf_desc[0];
 525         int final_rix, short_tries, long_tries, frame_size;
 526         const HAL_RATE_TABLE *rt = sc->sc_currates;
 527         int mrr;
 528
 529         final_rix = rt->rateCodeToIndex[ts->ts_rate];
 530         short_tries = ts->ts_shortretry;
 531         long_tries = ts->ts_longretry + 1;
 532         frame_size = ds0->ds_ctl0 & 0x0fff; /* low-order 12 bits of ds_ctl0 */
 533         if (frame_size == 0)                /* NB: should not happen */
 534                 frame_size = 1500;
 535
 536         if (sn->ratemask == 0) {
 537                 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL,
 538                     &an->an_node,
 539                     "%s: size %d %s rate/try %d/%d no rates yet",
 540                     __func__,
 541                     bin_to_size(size_to_bin(frame_size)),
 542                     ts->ts_status ? "FAIL" : "OK",
 543                     short_tries, long_tries);
 544                 return;
 545         }
 546         mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT);
 547         if (!mrr || ts->ts_finaltsi == 0) {
 548                 if (!IS_RATE_DEFINED(sn, final_rix)) {
 549                         badrate(ifp, 0, ts->ts_rate, long_tries, ts->ts_status);
 550                         return;
 551                 }
 552                 /*
 553                  * Only one rate was used; optimize work.
 554                  */
 555                 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL,
 556                      &an->an_node, "%s: size %d %s rate/try %d/%d/%d",
 557                      __func__,
 558                      bin_to_size(size_to_bin(frame_size)),
 559                      ts->ts_status ? "FAIL" : "OK",
 560                      dot11rate(rt, final_rix), short_tries, long_tries);
 561                 update_stats(sc, an, frame_size,
 562                              final_rix, long_tries,
 563                              0, 0,
 564                              0, 0,
 565                              0, 0,
 566                              short_tries, long_tries, ts->ts_status);
 567         } else {
 568                 int hwrates[4], tries[4], rix[4];
 569                 int finalTSIdx = ts->ts_finaltsi;
 570                 int i;
 571
 572                 /*
 573                  * Process intermediate rates that failed.
 574                  */
 575                 ath_hal_gettxcompletionrates(sc->sc_ah, ds0, hwrates, tries);
 576
 577                 for (i = 0; i < 4; i++) {
 578                         rix[i] = rt->rateCodeToIndex[hwrates[i]];
 579                 }
 580
 581                 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL,
 582                     &an->an_node,
 583 "%s: size %d finaltsidx %d tries %d %s rate/try [%d/%d %d/%d %d/%d %d/%d]",
 584                      __func__,
 585                      bin_to_size(size_to_bin(frame_size)),
 586                      finalTSIdx,
 587                      long_tries,
 588                      ts->ts_status ? "FAIL" : "OK",
 589                      dot11rate(rt, rix[0]), tries[0],
 590                      dot11rate(rt, rix[1]), tries[1],
 591                      dot11rate(rt, rix[2]), tries[2],
 592                      dot11rate(rt, rix[3]), tries[3]);
 593
 594                 for (i = 0; i < 4; i++) {
 595                         if (tries[i] && !IS_RATE_DEFINED(sn, rix[i]))
 596                                 badrate(ifp, 0, hwrates[i], tries[i], ts->ts_status);
 597                 }
 598
 599                 /*
 600                  * NB: series > 0 are not penalized for failure
 601                  * based on the try counts under the assumption
 602                  * that losses are often bursty and since we
 603                  * sample higher rates 1 try at a time doing so
 604                  * may unfairly penalize them.
 605                  */
 606                 if (tries[0]) {
 607                         update_stats(sc, an, frame_size,
 608                                      rix[0], tries[0],
 609                                      rix[1], tries[1],
 610                                      rix[2], tries[2],
 611                                      rix[3], tries[3],
 612                                      short_tries, long_tries,
 613                                      long_tries > tries[0]);
 614                         long_tries -= tries[0];
 615                 }
 616
 617                 if (tries[1] && finalTSIdx > 0) {
 618                         update_stats(sc, an, frame_size,
 619                                      rix[1], tries[1],
 620                                      rix[2], tries[2],
 621                                      rix[3], tries[3],
 622                                      0, 0,
 623                                      short_tries, long_tries,
 624                                      ts->ts_status);
 625                         long_tries -= tries[1];
 626                 }
 627
 628                 if (tries[2] && finalTSIdx > 1) {
 629                         update_stats(sc, an, frame_size,
 630                                      rix[2], tries[2],
 631                                      rix[3], tries[3],
 632                                      0, 0,
 633                                      0, 0,
 634                                      short_tries, long_tries,
 635                                      ts->ts_status);
 636                         long_tries -= tries[2];
 637                 }
 638
 639                 if (tries[3] && finalTSIdx > 2) {
 640                         update_stats(sc, an, frame_size,
 641                                      rix[3], tries[3],
 642                                      0, 0,
 643                                      0, 0,
 644                                      0, 0,
 645                                      short_tries, long_tries,
 646                                      ts->ts_status);
 647                 }
 648         }
 649 }
 650
 651 void
 652 ath_rate_newassoc(struct ath_softc *sc, struct ath_node *an, int isnew)
 653 {
 654         if (isnew)
 655                 ath_rate_ctl_reset(sc, &an->an_node);
 656 }
 657
 658 static const struct txschedule *mrr_schedules[IEEE80211_MODE_MAX+2] = {
 659         NULL,           /* IEEE80211_MODE_AUTO */
 660         series_11a,     /* IEEE80211_MODE_11A */
 661         series_11g,     /* IEEE80211_MODE_11B */
 662         series_11g,     /* IEEE80211_MODE_11G */
 663         NULL,           /* IEEE80211_MODE_FH */
 664         series_11a,     /* IEEE80211_MODE_TURBO_A */
 665         series_11g,     /* IEEE80211_MODE_TURBO_G */
 666         series_11a,     /* IEEE80211_MODE_STURBO_A */
 667         series_11na,    /* IEEE80211_MODE_11NA */
 668         series_11ng,    /* IEEE80211_MODE_11NG */
 669         series_half,    /* IEEE80211_MODE_HALF */
 670         series_quarter, /* IEEE80211_MODE_QUARTER */
 671 };
 672
 673 /*
 674  * Initialize the tables for a node.
 675  */
 676 static void
 677 ath_rate_ctl_reset(struct ath_softc *sc, struct ieee80211_node *ni)
 678 {
 679 #define RATE(_ix)       (ni->ni_rates.rs_rates[(_ix)] & IEEE80211_RATE_VAL)
 680 #define DOT11RATE(_ix)  (rt->info[(_ix)].dot11Rate & IEEE80211_RATE_VAL)
 681 #define MCS(_ix)        (ni->ni_htrates.rs_rates[_ix] | IEEE80211_RATE_MCS)
 682
 683         struct ath_node *an = ATH_NODE(ni);
 684         const struct ieee80211_txparam *tp = ni->ni_txparms;
 685         struct sample_node *sn = ATH_NODE_SAMPLE(an);
 686         const HAL_RATE_TABLE *rt = sc->sc_currates;
 687         int x, y, srate, rix;
 688
 689         KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode));
 690
 691         KASSERT(sc->sc_curmode < IEEE80211_MODE_MAX+2,
 692             ("curmode %u", sc->sc_curmode));
 693         sn->sched = mrr_schedules[sc->sc_curmode];
 694         KASSERT(sn->sched != NULL,
 695             ("no mrr schedule for mode %u", sc->sc_curmode));
 696
 697         sn->static_rix = -1;
 698         if (tp != NULL && tp->ucastrate != IEEE80211_FIXED_RATE_NONE) {
 699                 /*
 700                  * A fixed rate is to be used; ucastrate is the IEEE code
 701                  * for this rate (sans basic bit).  Check this against the
 702                  * negotiated rate set for the node.  Note the fixed rate
 703                  * may not be available for various reasons so we only
 704                  * setup the static rate index if the lookup is successful.
 705                  */
 706
 707                 /* XXX todo: check MCS rates */
 708
 709                 /* Check legacy rates */
 710                 for (srate = ni->ni_rates.rs_nrates - 1; srate >= 0; srate--)
 711                         if (RATE(srate) == tp->ucastrate) {
 712                                 sn->static_rix = sc->sc_rixmap[tp->ucastrate];
 713                                 break;
 714                         }
 715 #ifdef IEEE80211_DEBUG
 716                         if (sn->static_rix == -1) {
 717                                 IEEE80211_NOTE(ni->ni_vap,
 718                                     IEEE80211_MSG_RATECTL, ni,
 719                                     "%s: ucastrate %u not found, nrates %u",
 720                                     __func__, tp->ucastrate,
 721                                     ni->ni_rates.rs_nrates);
 722                         }
 723 #endif
 724         }
 725
 726         /*
 727          * Construct a bitmask of usable rates.  This has all
 728          * negotiated rates minus those marked by the hal as
 729          * to be ignored for doing rate control.
 730          */
 731         sn->ratemask = 0;
 732         /* MCS rates */
 733         if (ni->ni_flags & IEEE80211_NODE_HT) {
 734                 for (x = 0; x < ni->ni_htrates.rs_nrates; x++) {
 735                         rix = sc->sc_rixmap[MCS(x)];
 736                         if (rix == 0xff)
 737                                 continue;
 738                         /* skip rates marked broken by hal */
 739                         if (!rt->info[rix].valid)
 740                                 continue;
 741                         KASSERT(rix < SAMPLE_MAXRATES,
 742                             ("mcs %u has rix %d", MCS(x), rix));
 743                         sn->ratemask |= 1<<rix;
 744                 }
 745         }
 746
 747         /* Legacy rates */
 748         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 749                 rix = sc->sc_rixmap[RATE(x)];
 750                 if (rix == 0xff)
 751                         continue;
 752                 /* skip rates marked broken by hal */
 753                 if (!rt->info[rix].valid)
 754                         continue;
 755                 KASSERT(rix < SAMPLE_MAXRATES,
 756                     ("rate %u has rix %d", RATE(x), rix));
 757                 sn->ratemask |= 1<<rix;
 758         }
 759 #ifdef IEEE80211_DEBUG
 760         if (ieee80211_msg(ni->ni_vap, IEEE80211_MSG_RATECTL)) {
 761                 uint32_t mask;
 762
 763                 ieee80211_note(ni->ni_vap, "[%6D] %s: size 1600 rate/tt",
 764                     ni->ni_macaddr, ":", __func__);
 765                 for (mask = sn->ratemask, rix = 0; mask != 0; mask >>= 1, rix++) {
 766                         if ((mask & 1) == 0)
 767                                 continue;
 768                         printf(" %d/%d", dot11rate(rt, rix),
 769                             calc_usecs_unicast_packet(sc, 1600, rix, 0,0,
 770                                 (ni->ni_htcap & IEEE80211_HTCAP_CHWIDTH40)));
 771                 }
 772                 printf("\n");
 773         }
 774 #endif
 775         for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) {
 776                 int size = bin_to_size(y);
 777                 uint32_t mask;
 778
 779                 sn->packets_sent[y] = 0;
 780                 sn->current_sample_rix[y] = -1;
 781                 sn->last_sample_rix[y] = 0;
 782                 /* XXX start with first valid rate */
 783                 sn->current_rix[y] = ffs(sn->ratemask)-1;
 784
 785                 /*
 786                  * Initialize the statistics buckets; these are
 787                  * indexed by the rate code index.
 788                  */
 789                 for (rix = 0, mask = sn->ratemask; mask != 0; rix++, mask >>= 1) {
 790                         if ((mask & 1) == 0)            /* not a valid rate */
 791                                 continue;
 792                         sn->stats[y][rix].successive_failures = 0;
 793                         sn->stats[y][rix].tries = 0;
 794                         sn->stats[y][rix].total_packets = 0;
 795                         sn->stats[y][rix].packets_acked = 0;
 796                         sn->stats[y][rix].last_tx = 0;
 797
 798                         sn->stats[y][rix].perfect_tx_time =
 799                             calc_usecs_unicast_packet(sc, size, rix, 0, 0,
 800                             (ni->ni_htcap & IEEE80211_HTCAP_CHWIDTH40));
 801                         sn->stats[y][rix].average_tx_time =
 802                             sn->stats[y][rix].perfect_tx_time;
 803                 }
 804         }
 805 #if 0
 806         /* XXX 0, num_rates-1 are wrong */
 807         IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
 808             "%s: %d rates %d%sMbps (%dus)- %d%sMbps (%dus)", __func__,
 809             sn->num_rates,
 810             DOT11RATE(0)/2, DOT11RATE(0) % 1 ? ".5" : "",
 811             sn->stats[1][0].perfect_tx_time,
 812             DOT11RATE(sn->num_rates-1)/2, DOT11RATE(sn->num_rates-1) % 1 ? ".5" : "",
 813             sn->stats[1][sn->num_rates-1].perfect_tx_time
 814         );
 815 #endif
 816         /* set the visible bit-rate */
 817         if (sn->static_rix != -1)
 818                 ni->ni_txrate = DOT11RATE(sn->static_rix);
 819         else
 820                 ni->ni_txrate = RATE(0);
 821 #undef RATE
 822 #undef DOT11RATE
 823 }
 824
 825 static void
 826 sample_stats(void *arg, struct ieee80211_node *ni)
 827 {
 828         struct ath_softc *sc = arg;
 829         const HAL_RATE_TABLE *rt = sc->sc_currates;
 830         struct sample_node *sn = ATH_NODE_SAMPLE(ATH_NODE(ni));
 831         uint32_t mask;
 832         int rix, y;
 833
 834         printf("\n[%s] refcnt %d static_rix %d ratemask 0x%x\n",
 835             ether_sprintf(ni->ni_macaddr), ieee80211_node_refcnt(ni),
 836             sn->static_rix, sn->ratemask);
 837         for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) {
 838                 printf("[%4u] cur rix %d since switch: packets %d ticks %u\n",
 839                     bin_to_size(y), sn->current_rix[y],
 840                     sn->packets_since_switch[y], sn->ticks_since_switch[y]);
 841                 printf("[%4u] last sample %d cur sample %d packets sent %d\n",
 842                     bin_to_size(y), sn->last_sample_rix[y],
 843                     sn->current_sample_rix[y], sn->packets_sent[y]);
 844                 printf("[%4u] packets since sample %d sample tt %u\n",
 845                     bin_to_size(y), sn->packets_since_sample[y],
 846                     sn->sample_tt[y]);
 847         }
 848         for (mask = sn->ratemask, rix = 0; mask != 0; mask >>= 1, rix++) {
 849                 if ((mask & 1) == 0)
 850                                 continue;
 851                 for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) {
 852                         if (sn->stats[y][rix].total_packets == 0)
 853                                 continue;
 854                         printf("[%2u:%4u] %8d:%-8d (%3d%%) T %8d F %4d avg %5u last %u\n",
 855                             dot11rate(rt, rix),
 856                             bin_to_size(y),
 857                             sn->stats[y][rix].total_packets,
 858                             sn->stats[y][rix].packets_acked,
 859                             (100*sn->stats[y][rix].packets_acked)/sn->stats[y][rix].total_packets,
 860                             sn->stats[y][rix].tries,
 861                             sn->stats[y][rix].successive_failures,
 862                             sn->stats[y][rix].average_tx_time,
 863                             ticks - sn->stats[y][rix].last_tx);
 864                 }
 865         }
 866 }
 867
 868 static int
 869 ath_rate_sysctl_stats(SYSCTL_HANDLER_ARGS)
 870 {
 871         struct ath_softc *sc = arg1;
 872         struct ifnet *ifp = sc->sc_ifp;
 873         struct ieee80211com *ic = ifp->if_l2com;
 874         int error, v;
 875
 876         v = 0;
 877         error = sysctl_handle_int(oidp, &v, 0, req);
 878         if (error || !req->newptr)
 879                 return error;
 880         ieee80211_iterate_nodes(&ic->ic_sta, sample_stats, sc);
 881         return 0;
 882 }
 883
 884 static int
 885 ath_rate_sysctl_smoothing_rate(SYSCTL_HANDLER_ARGS)
 886 {
 887         struct sample_softc *ssc = arg1;
 888         int rate, error;
 889
 890         rate = ssc->smoothing_rate;
 891         error = sysctl_handle_int(oidp, &rate, 0, req);
 892         if (error || !req->newptr)
 893                 return error;
 894         if (!(0 <= rate && rate < 100))
 895                 return EINVAL;
 896         ssc->smoothing_rate = rate;
 897         ssc->smoothing_minpackets = 100 / (100 - rate);
 898         return 0;
 899 }
 900
 901 static int
 902 ath_rate_sysctl_sample_rate(SYSCTL_HANDLER_ARGS)
 903 {
 904         struct sample_softc *ssc = arg1;
 905         int rate, error;
 906
 907         rate = ssc->sample_rate;
 908         error = sysctl_handle_int(oidp, &rate, 0, req);
 909         if (error || !req->newptr)
 910                 return error;
 911         if (!(2 <= rate && rate <= 100))
 912                 return EINVAL;
 913         ssc->sample_rate = rate;
 914         return 0;
 915 }
 916
 917 static void
 918 ath_rate_sysctlattach(struct ath_softc *sc, struct sample_softc *ssc)
 919 {
 920         struct sysctl_ctx_list *ctx = device_get_sysctl_ctx(sc->sc_dev);
 921         struct sysctl_oid *tree = device_get_sysctl_tree(sc->sc_dev);
 922
 923         SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 924             "smoothing_rate", CTLTYPE_INT | CTLFLAG_RW, ssc, 0,
 925             ath_rate_sysctl_smoothing_rate, "I",
 926             "sample: smoothing rate for avg tx time (%%)");
 927         SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 928             "sample_rate", CTLTYPE_INT | CTLFLAG_RW, ssc, 0,
 929             ath_rate_sysctl_sample_rate, "I",
 930             "sample: percent air time devoted to sampling new rates (%%)");
 931         /* XXX max_successive_failures, stale_failure_timeout, min_switch */
 932         SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
 933             "sample_stats", CTLTYPE_INT | CTLFLAG_RW, sc, 0,
 934             ath_rate_sysctl_stats, "I", "sample: print statistics");
 935 }
 936
 937 struct ath_ratectrl *
 938 ath_rate_attach(struct ath_softc *sc)
 939 {
 940         struct sample_softc *ssc;
 941
 942         ssc = malloc(sizeof(struct sample_softc), M_DEVBUF, M_NOWAIT|M_ZERO);
 943         if (ssc == NULL)
 944                 return NULL;
 945         ssc->arc.arc_space = sizeof(struct sample_node);
 946         ssc->smoothing_rate = 95;               /* ewma percentage ([0..99]) */
 947         ssc->smoothing_minpackets = 100 / (100 - ssc->smoothing_rate);
 948         ssc->sample_rate = 10;                  /* %time to try diff tx rates */
 949         ssc->max_successive_failures = 3;       /* threshold for rate sampling*/
 950         ssc->stale_failure_timeout = 10 * hz;   /* 10 seconds */
 951         ssc->min_switch = hz;                   /* 1 second */
 952         ath_rate_sysctlattach(sc, ssc);
 953         return &ssc->arc;
 954 }
 955
 956 void
 957 ath_rate_detach(struct ath_ratectrl *arc)
 958 {
 959         struct sample_softc *ssc = (struct sample_softc *) arc;
 960
 961         free(ssc, M_DEVBUF);
 962 }