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