sys/netproto/802_11/wlan_ratectl/sample/ieee80211_ratectl_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  * $FreeBSD: src/sys/dev/ath/ath_rate/sample/sample.c,v 1.8.2.3 2006/03/14 23:22:27 sam Exp $
  37  * $DragonFly: src/sys/netproto/802_11/wlan_ratectl/sample/ieee80211_ratectl_sample.c,v 1.4 2008/01/15 09:01:13 sephe Exp $
  38  */
  39
  40 /*
  41  * John Bicket's SampleRate control algorithm.
  42  */
  43
  44 #include <sys/param.h>
  45 #include <sys/kernel.h>
  46 #include <sys/malloc.h>
  47 #include <sys/module.h>
  48 #include <sys/sysctl.h>
  49
  50 #include <net/if.h>
  51 #include <net/if_media.h>
  52 #include <net/if_arp.h>
  53
  54 #include <netproto/802_11/ieee80211_var.h>
  55 #include <netproto/802_11/wlan_ratectl/sample/ieee80211_sample_param.h>
  56
  57 #define SAMPLE_DEBUG
  58
  59 #ifdef SAMPLE_DEBUG
  60 #define DPRINTF(ssc, lv, fmt, ...) do {         \
  61         if (ssc->param->sample_debug >= lv)     \
  62                 kprintf(fmt, __VA_ARGS__);      \
  63 } while (0)
  64 #else
  65 #define DPRINTF(ssc, lv, fmt, ...)
  66 #endif
  67
  68 struct sample_softc {
  69         struct ieee80211com     *ic;
  70
  71         struct sysctl_ctx_list  sysctl_ctx;
  72         struct sysctl_oid       *sysctl_oid;
  73
  74         struct ieee80211_sample_param *param;
  75 #define smoothing_rate  param->sample_smoothing_rate
  76 };
  77
  78 struct rate_stats {
  79         unsigned average_tx_time;
  80         int successive_failures;
  81         int tries;
  82         int total_packets;
  83         int packets_acked;
  84         unsigned perfect_tx_time; /* transmit time for 0 retries */
  85         int last_tx;
  86 };
  87
  88 #define NUM_PACKET_SIZE_BINS    3
  89
  90 struct sample_data {
  91         int started;
  92         int static_rate_ndx;
  93
  94         struct rate_stats stats[NUM_PACKET_SIZE_BINS][IEEE80211_RATE_MAXSIZE];
  95         int last_sample_ndx[NUM_PACKET_SIZE_BINS];
  96
  97         int current_sample_ndx[NUM_PACKET_SIZE_BINS];
  98         int packets_sent[NUM_PACKET_SIZE_BINS];
  99
 100         int current_rate[NUM_PACKET_SIZE_BINS];
 101         int packets_since_switch[NUM_PACKET_SIZE_BINS];
 102         unsigned ticks_since_switch[NUM_PACKET_SIZE_BINS];
 103
 104         int packets_since_sample[NUM_PACKET_SIZE_BINS];
 105         unsigned sample_tt[NUM_PACKET_SIZE_BINS];
 106 };
 107
 108 /*
 109  * This file is an implementation of the SampleRate algorithm
 110  * in "Bit-rate Selection in Wireless Networks"
 111  * (http://www.pdos.lcs.mit.edu/papers/jbicket-ms.ps)
 112  *
 113  * SampleRate chooses the bit-rate it predicts will provide the most
 114  * throughput based on estimates of the expected per-packet
 115  * transmission time for each bit-rate.  SampleRate periodically sends
 116  * packets at bit-rates other than the current one to estimate when
 117  * another bit-rate will provide better performance. SampleRate
 118  * switches to another bit-rate when its estimated per-packet
 119  * transmission time becomes smaller than the current bit-rate's.
 120  * SampleRate reduces the number of bit-rates it must sample by
 121  * eliminating those that could not perform better than the one
 122  * currently being used.  SampleRate also stops probing at a bit-rate
 123  * if it experiences several successive losses.
 124  *
 125  * The difference between the algorithm in the thesis and the one in this
 126  * file is that the one in this file uses a ewma instead of a window.
 127  *
 128  * Also, this implementation tracks the average transmission time for
 129  * a few different packet sizes independently for each link.
 130  */
 131
 132 #define STALE_FAILURE_TIMEOUT_MS        10000
 133 #define MIN_SWITCH_MS                   1000
 134
 135 static void     *sample_attach(struct ieee80211com *);
 136 static void     sample_detach(void *);
 137 static void     sample_data_alloc(struct ieee80211_node *);
 138 static void     sample_data_free(struct ieee80211_node *);
 139 static void     sample_data_dup(const struct ieee80211_node *,
 140                                 struct ieee80211_node *);
 141 static void     sample_newstate(void *, enum ieee80211_state);
 142 static void     sample_tx_complete(void *, struct ieee80211_node *, int,
 143                                    const struct ieee80211_ratectl_res[],
 144                                    int, int, int, int);
 145 static void     sample_newassoc(void *, struct ieee80211_node *, int);
 146 static int      sample_findrate(void *, struct ieee80211_node *, int,
 147                                 int[], int);
 148
 149 static void     sample_sysctl_attach(struct sample_softc *);
 150 static void     sample_start(struct sample_softc *, struct ieee80211_node *);
 151 static void     sample_update_stats(struct sample_softc *,
 152                                     struct ieee80211_node *, int, int,
 153                                     const struct ieee80211_ratectl_res [], int,
 154                                     int, int);
 155
 156 static const struct ieee80211_ratectl sample = {
 157         .rc_name        = "sample",
 158         .rc_ratectl     = IEEE80211_RATECTL_SAMPLE,
 159         .rc_attach      = sample_attach,
 160         .rc_detach      = sample_detach,
 161         .rc_data_alloc  = sample_data_alloc,
 162         .rc_data_free   = sample_data_free,
 163         .rc_data_dup    = sample_data_dup,
 164         .rc_newstate    = sample_newstate,
 165         .rc_tx_complete = sample_tx_complete,
 166         .rc_newassoc    = sample_newassoc,
 167         .rc_findrate    = sample_findrate
 168 };
 169
 170 static u_int    sample_nrefs;
 171
 172 /*
 173  * for now, we track performance for three different packet
 174  * size buckets
 175  */
 176 static int      packet_size_bins[NUM_PACKET_SIZE_BINS] = { 250, 1600, 3000 };
 177
 178 MALLOC_DEFINE(M_SAMPLE_RATECTL_DATA, "sample_ratectl_data",
 179               "sample rate control data");
 180
 181 static __inline int
 182 size_to_bin(int size)
 183 {
 184         int x;
 185
 186         for (x = 0; x < NUM_PACKET_SIZE_BINS; x++) {
 187                 if (size <= packet_size_bins[x])
 188                         return x;
 189         }
 190         return NUM_PACKET_SIZE_BINS - 1;
 191 }
 192
 193 static __inline int
 194 bin_to_size(int index)
 195 {
 196         return packet_size_bins[index];
 197 }
 198
 199 static __inline int
 200 rate_to_ndx(struct ieee80211_node *ni, int rate)
 201 {
 202         int x = 0;
 203
 204         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 205                 if (IEEE80211_RS_RATE(&ni->ni_rates, x) == rate)
 206                         return x;
 207         }
 208         return -1;
 209 }
 210
 211 static __inline int
 212 unicast_pkt_time(struct sample_softc *ssc, struct ieee80211_node *ni,
 213                  int rate, int len, int data_tries, int rts_tries,
 214                  int *cw0)
 215 {
 216         struct ieee80211com *ic = ssc->ic;
 217         int sifs, difs, slot;
 218         int ack_dur, data_dur, cw;
 219         int tt = 0;
 220         int i;
 221
 222         ack_dur = ieee80211_txtime(ni,
 223                         sizeof(struct ieee80211_frame_ack) + IEEE80211_CRC_LEN,
 224                         ieee80211_ack_rate(ni, rate), ic->ic_flags);
 225         data_dur = ieee80211_txtime(ni, len, rate, ic->ic_flags);
 226
 227         if (IEEE80211_IS_CHAN_5GHZ(ni->ni_chan)) {
 228                 cw = IEEE80211_CW_MIN_1;
 229                 sifs = IEEE80211_DUR_OFDM_SIFS;
 230                 slot = IEEE80211_DUR_OFDM_SLOT;
 231         } else {
 232                 /* XXX should base on characteristic rate set */
 233                 cw = IEEE80211_CW_MIN_0;
 234                 sifs = IEEE80211_DUR_SIFS;
 235                 slot = (ic->ic_flags & IEEE80211_F_SHSLOT)
 236                         ? IEEE80211_DUR_SHSLOT
 237                         : IEEE80211_DUR_SLOT;
 238         }
 239         if (cw0 != NULL && *cw0 != 0)
 240                 cw = *cw0;
 241         difs = IEEE80211_DUR_DIFS(sifs, slot);
 242
 243         if (rts_tries > 0 && (ic->ic_flags & IEEE80211_F_USEPROT) &&
 244             ieee80211_rate2modtype(rate) == IEEE80211_MODTYPE_OFDM) {
 245                 if (ic->ic_protmode == IEEE80211_PROT_RTSCTS) {
 246                         uint8_t rts_rate;
 247                         int rts_dur, cts_dur;
 248
 249                         /* Assume RTS is sent at 2Mbits/s */
 250                         rts_rate = 4;
 251
 252                         rts_dur = ieee80211_txtime(ni,
 253                                         sizeof(struct ieee80211_frame_rts) +
 254                                         IEEE80211_CRC_LEN,
 255                                         rts_rate, ic->ic_flags);
 256                         cts_dur = ieee80211_txtime(ni,
 257                                         sizeof(struct ieee80211_frame_cts) +
 258                                         IEEE80211_CRC_LEN,
 259                                         ieee80211_ack_rate(ni, rts_rate),
 260                                         ic->ic_flags);
 261
 262                         tt += rts_tries * (rts_dur + sifs + cts_dur);
 263
 264                         /*
 265                          * Immediate data transmission does not perform backoff
 266                          * procedure.
 267                          *
 268                          * XXX not correct, if RTS retries (short retry count)
 269                          * reaches dot11ShortRetryLimit, which should be rare.
 270                          */
 271                         tt += sifs;
 272                         --rts_tries;
 273                 } else if (ic->ic_protmode == IEEE80211_PROT_CTSONLY) {
 274                         /* Assume CTS is sent at 2Mbits/s */
 275                         tt += ieee80211_txtime(ni,
 276                                 sizeof(struct ieee80211_frame_cts) +
 277                                 IEEE80211_CRC_LEN,
 278                                 4, ic->ic_flags);
 279                         tt += sifs;
 280                         rts_tries = 0;
 281                 }
 282         } else {
 283                 rts_tries = 0;
 284         }
 285
 286         tt += data_tries * (data_dur + sifs + ack_dur);
 287
 288         /* Average time consumed by backoff procedure */
 289         for (i = 0; i < (data_tries + rts_tries); ++i) {
 290                 tt += difs + (slot * cw / 2);
 291                 cw = MIN(IEEE80211_CW_MAX + 1, (cw + 1) * 2) - 1;
 292         }
 293         if (cw0 != NULL)
 294                 *cw0 = cw;
 295         return tt;
 296 }
 297
 298 /*
 299  * returns the ndx with the lowest average_tx_time,
 300  * or -1 if all the average_tx_times are 0.
 301  */
 302 static __inline int
 303 best_rate_ndx(struct ieee80211_node *ni, int size_bin,
 304               int require_acked_before)
 305 {
 306         int x, best_rate_ndx = 0, best_rate_tt = 0;
 307         struct sample_data *sd = ni->ni_rate_data;
 308
 309         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 310                 int tt = sd->stats[size_bin][x].average_tx_time;
 311
 312                 if (tt <= 0 ||
 313                     (require_acked_before &&
 314                      !sd->stats[size_bin][x].packets_acked))
 315                         continue;
 316
 317                 /* 9 megabits never works better than 12 */
 318                 if (IEEE80211_RS_RATE(&ni->ni_rates, x) == 18)
 319                         continue;
 320
 321                 /* don't use a bit-rate that has been failing */
 322                 if (sd->stats[size_bin][x].successive_failures > 3)
 323                         continue;
 324
 325                 if (!best_rate_tt || best_rate_tt > tt) {
 326                         best_rate_tt = tt;
 327                         best_rate_ndx = x;
 328                 }
 329         }
 330         return (best_rate_tt) ? best_rate_ndx : -1;
 331 }
 332
 333 /*
 334  * pick a good "random" bit-rate to sample other than the current one
 335  */
 336 static __inline int
 337 pick_sample_ndx(struct ieee80211_node *ni, int size_bin)
 338 {
 339         int x = 0;
 340         int current_ndx = 0;
 341         unsigned current_tt = 0;
 342         struct sample_data *sd = ni->ni_rate_data;
 343
 344         current_ndx = sd->current_rate[size_bin];
 345         if (current_ndx < 0) {
 346                 /* no successes yet, send at the lowest bit-rate */
 347                 return 0;
 348         }
 349
 350         current_tt = sd->stats[size_bin][current_ndx].average_tx_time;
 351
 352         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 353                 int ndx = (sd->last_sample_ndx[size_bin] + 1 + x) %
 354                           ni->ni_rates.rs_nrates;
 355
 356                 /* don't sample the current bit-rate */
 357                 if (ndx == current_ndx)
 358                         continue;
 359
 360                 /* this bit-rate is always worse than the current one */
 361                 if (sd->stats[size_bin][ndx].perfect_tx_time > current_tt)
 362                         continue;
 363
 364                 /* rarely sample bit-rates that fail a lot */
 365                 if (ticks - sd->stats[size_bin][ndx].last_tx < ((hz * STALE_FAILURE_TIMEOUT_MS) / 1000) &&
 366                     sd->stats[size_bin][ndx].successive_failures > 3)
 367                         continue;
 368
 369                 /*
 370                  * don't sample more than 2 indexes higher
 371                  * for rates higher than 11 megabits
 372                  */
 373                 if (IEEE80211_RS_RATE(&ni->ni_rates, ndx) > 22 &&
 374                     ndx > current_ndx + 2)
 375                         continue;
 376
 377                 /* 9 megabits never works better than 12 */
 378                 if (IEEE80211_RS_RATE(&ni->ni_rates, ndx) == 18)
 379                         continue;
 380
 381                 /*
 382                  * if we're using 11 megabits, only sample up to 12 megabits
 383                  */
 384                 if (IEEE80211_RS_RATE(&ni->ni_rates, current_ndx) == 22 &&
 385                     ndx > current_ndx + 1)
 386                         continue;
 387
 388                 sd->last_sample_ndx[size_bin] = ndx;
 389                 return ndx;
 390         }
 391         return current_ndx;
 392 }
 393
 394 static int
 395 sample_findrate(void *arg, struct ieee80211_node *ni, int frame_len,
 396                 int rateidx[], int rateidx_len)
 397 {
 398         struct sample_softc *ssc = arg;
 399         struct sample_data *sd = ni->ni_rate_data;
 400         struct ieee80211com *ic = ssc->ic;
 401         struct ieee80211_ratectl_state *rc_st = &ic->ic_ratectl;
 402         int ndx, size_bin, best_ndx, change_rates, ack_before, cur_ndx, i;
 403         unsigned average_tx_time;
 404
 405         if (sd == NULL) {
 406                 /*
 407                  * XXX
 408                  * This could happen on a "reclaimed" node, which will
 409                  * vanish soon, so don't bother to call sample_start()
 410                  * here.
 411                  */
 412                 rateidx[0] = 0;
 413                 return 1;
 414         } else {
 415                 for (i = 0; i < NUM_PACKET_SIZE_BINS; ++i) {
 416                         if (sd->current_rate[i] >= ni->ni_rates.rs_nrates) {
 417                                 DPRINTF(ssc, 5, "%s: number of rates changed, "
 418                                         "restart\n", __func__);
 419                                 sample_start(ssc, ni);
 420                                 break;
 421                         }
 422                 }
 423         }
 424
 425         KKASSERT(frame_len > 0);
 426         size_bin = size_to_bin(frame_len);
 427
 428         ack_before = (!(rc_st->rc_st_flags & IEEE80211_RATECTL_F_MRR) ||
 429                       (ic->ic_flags & IEEE80211_F_USEPROT));
 430         best_ndx = best_rate_ndx(ni, size_bin, ack_before);
 431         if (best_ndx >= 0)
 432                 average_tx_time = sd->stats[size_bin][best_ndx].average_tx_time;
 433         else
 434                 average_tx_time = 0;
 435
 436         if (sd->static_rate_ndx != -1) {
 437                 ndx = sd->static_rate_ndx;
 438         } else {
 439                 if (sd->sample_tt[size_bin] <
 440                     average_tx_time * (sd->packets_since_sample[size_bin] * ssc->param->sample_rate / 100)) {
 441                         /*
 442                          * We want to limit the time measuring the
 443                          * performance of other bit-rates to sample_rate%
 444                          * of the total transmission time.
 445                          */
 446                         ndx = pick_sample_ndx(ni, size_bin);
 447                         if (ndx != sd->current_rate[size_bin])
 448                                 sd->current_sample_ndx[size_bin] = ndx;
 449                         else
 450                                 sd->current_sample_ndx[size_bin] = -1;
 451                         sd->packets_since_sample[size_bin] = 0;
 452                 } else {
 453                         change_rates = 0;
 454                         if (!sd->packets_sent[size_bin] || best_ndx == -1) {
 455                                 /* no packet has been sent successfully yet */
 456                                 for (ndx = ni->ni_rates.rs_nrates - 1; ndx > 0; ndx--) {
 457                                         /*
 458                                          * pick the highest rate <= 36 Mbps
 459                                          * that hasn't failed.
 460                                          */
 461                                         if (IEEE80211_RS_RATE(&ni->ni_rates, ndx) <= 72 &&
 462                                             sd->stats[size_bin][ndx].successive_failures == 0)
 463                                                 break;
 464                                 }
 465                                 change_rates = 1;
 466                                 best_ndx = ndx;
 467                         } else if (sd->packets_sent[size_bin] < 20) {
 468                                 /* let the bit-rate switch quickly during the first few packets */
 469                                 change_rates = 1;
 470                         } else if (ticks - ((hz * MIN_SWITCH_MS) / 1000) > sd->ticks_since_switch[size_bin]) {
 471                                 /* 2 seconds have gone by */
 472                                 change_rates = 1;
 473                         } else if (average_tx_time * 2 < sd->stats[size_bin][sd->current_rate[size_bin]].average_tx_time) {
 474                                 /* the current bit-rate is twice as slow as the best one */
 475                                 change_rates = 1;
 476                         }
 477
 478                         sd->packets_since_sample[size_bin]++;
 479
 480                         if (change_rates) {
 481                                 if (best_ndx != sd->current_rate[size_bin]) {
 482                                         DPRINTF(ssc, 5, "%s: %6D size %d "
 483                                                 "switch rate "
 484                                                 "%d (%d/%d) -> %d (%d/%d) "
 485                                                 "after %d packets\n",
 486                                                 __func__,
 487                                                 ni->ni_macaddr, ":",
 488                                                 packet_size_bins[size_bin],
 489                                                 IEEE80211_RS_RATE(&ni->ni_rates, sd->current_rate[size_bin]),
 490                                                 sd->stats[size_bin][sd->current_rate[size_bin]].average_tx_time,
 491                                                 sd->stats[size_bin][sd->current_rate[size_bin]].perfect_tx_time,
 492                                                 IEEE80211_RS_RATE(&ni->ni_rates, best_ndx),
 493                                                 sd->stats[size_bin][best_ndx].average_tx_time,
 494                                                 sd->stats[size_bin][best_ndx].perfect_tx_time,
 495                                                 sd->packets_since_switch[size_bin]);
 496                                 }
 497                                 sd->packets_since_switch[size_bin] = 0;
 498                                 sd->current_rate[size_bin] = best_ndx;
 499                                 sd->ticks_since_switch[size_bin] = ticks;
 500                         }
 501                         ndx = sd->current_rate[size_bin];
 502                         sd->packets_since_switch[size_bin]++;
 503                         if (size_bin == 0) {
 504                                 /*
 505                                  * set the visible txrate for this node
 506                                  * to the rate of small packets
 507                                  */
 508                                 ni->ni_txrate = ndx;
 509                         }
 510                 }
 511         }
 512
 513         KASSERT(ndx >= 0 && ndx < ni->ni_rates.rs_nrates, ("ndx is %d", ndx));
 514
 515         sd->packets_sent[size_bin]++;
 516
 517         cur_ndx = sd->current_rate[size_bin];
 518         if (sd->stats[size_bin][cur_ndx].packets_acked == 0)
 519                 cur_ndx = 0;
 520
 521         rateidx[0] = ndx;
 522         i = 1;
 523         if (rateidx_len > 2) {
 524                 if ((rc_st->rc_st_flags & IEEE80211_RATECTL_F_RSDESC) == 0 ||
 525                     cur_ndx < ndx)
 526                         rateidx[i++] = cur_ndx;
 527                 else if (ndx > 0)
 528                         rateidx[i++] = ndx - 1;
 529         }
 530         if (i < rateidx_len && rateidx[i] != 0)
 531                 rateidx[i++] = 0;
 532         return i;
 533 }
 534
 535 static void
 536 sample_update_stats(struct sample_softc *ssc, struct ieee80211_node *ni,
 537                     int size, int size_bin,
 538                     const struct ieee80211_ratectl_res res[], int res_len,
 539                     int rts_tries, int is_fail)
 540 {
 541         struct sample_data *sd = ni->ni_rate_data;
 542         int tt, rate, i, ndx, cw = 0, data_tries;
 543
 544         cw = 0;
 545         ndx = res[0].rc_res_rateidx;
 546
 547         rate = IEEE80211_RS_RATE(&ni->ni_rates, ndx);
 548         tt = unicast_pkt_time(ssc, ni, rate, size,
 549                               res[0].rc_res_tries, rts_tries, &cw);
 550         data_tries = res[0].rc_res_tries;
 551
 552         for (i = 1; i < res_len; ++i) {
 553                 rate = IEEE80211_RS_RATE(&ni->ni_rates, res[i].rc_res_rateidx);
 554                 tt += unicast_pkt_time(ssc, ni, rate, size,
 555                                        res[i].rc_res_tries, 0, &cw);
 556                 data_tries += res[i].rc_res_tries;
 557         }
 558
 559         if (sd->stats[size_bin][ndx].total_packets < (100 / (100 - ssc->smoothing_rate))) {
 560                 int avg_tx = sd->stats[size_bin][ndx].average_tx_time;
 561                 int packets = sd->stats[size_bin][ndx].total_packets;
 562
 563                 /* Average the first few packets. */
 564                 sd->stats[size_bin][ndx].average_tx_time =
 565                         (tt + (avg_tx * packets)) / (packets + 1);
 566         } else {
 567                 /* Use EWMA */
 568                 sd->stats[size_bin][ndx].average_tx_time =
 569                         ((sd->stats[size_bin][ndx].average_tx_time * ssc->smoothing_rate) +
 570                          (tt * (100 - ssc->smoothing_rate))) / 100;
 571         }
 572
 573         if (is_fail) {
 574                 int y;
 575
 576                 sd->stats[size_bin][ndx].successive_failures++;
 577                 for (y = size_bin + 1; y < NUM_PACKET_SIZE_BINS; y++) {
 578                         /*
 579                          * also say larger packets failed since we
 580                          * assume if a small packet fails at a lower
 581                          * bit-rate then a larger one will also.
 582                          */
 583                         sd->stats[y][ndx].successive_failures++;
 584                         sd->stats[y][ndx].last_tx = ticks;
 585                         sd->stats[y][ndx].tries += data_tries;
 586                         sd->stats[y][ndx].total_packets++;
 587                 }
 588         } else {
 589                 sd->stats[size_bin][ndx].packets_acked++;
 590                 sd->stats[size_bin][ndx].successive_failures = 0;
 591         }
 592         sd->stats[size_bin][ndx].last_tx = ticks;
 593         sd->stats[size_bin][ndx].tries += data_tries;
 594         sd->stats[size_bin][ndx].total_packets++;
 595
 596         if (ndx == sd->current_sample_ndx[size_bin]) {
 597                 DPRINTF(ssc, 10, "%s: %6D size %d sample rate %d "
 598                         "tries (d%d/r%d) tt %d avg_tt (%d/%d)%s\n",
 599                         __func__, ni->ni_macaddr, ":",
 600                         size, IEEE80211_RS_RATE(&ni->ni_rates, ndx),
 601                         data_tries, rts_tries, tt,
 602                         sd->stats[size_bin][ndx].average_tx_time,
 603                         sd->stats[size_bin][ndx].perfect_tx_time,
 604                         is_fail ? " fail" : "");
 605                 sd->sample_tt[size_bin] = tt;
 606                 sd->current_sample_ndx[size_bin] = -1;
 607         }
 608 }
 609
 610 static void
 611 sample_tx_complete(void *arg, struct ieee80211_node *ni, int frame_len,
 612                    const struct ieee80211_ratectl_res res[], int res_len,
 613                    int data_retry, int rts_retry, int is_fail0)
 614 {
 615         struct sample_softc *ssc = arg;
 616         struct sample_data *sd = ni->ni_rate_data;
 617         int i, size_bin, size;
 618
 619         KKASSERT(frame_len > 0);
 620         size_bin = size_to_bin(frame_len);
 621         size = bin_to_size(size_bin);
 622
 623         if (sd == NULL || !sd->started) {
 624                 DPRINTF(ssc, 10, "%s: %6D size %d retries (d%d/r%d) "
 625                         "no rates yet\n", __func__,
 626                         ni->ni_macaddr, ":",
 627                         size, data_retry, rts_retry);
 628                 return;
 629         }
 630
 631         for (i = 0; i < res_len; ++i) {
 632                 if (res[i].rc_res_rateidx >= ni->ni_rates.rs_nrates) {
 633                         DPRINTF(ssc, 5, "%s: number of rates changed, "
 634                                 "restart\n", __func__);
 635                         sample_start(ssc, ni);
 636                         return;
 637                 }
 638         }
 639
 640         DPRINTF(ssc, 20, "%s: %6D size %d retries (d%d/r%d)\n",
 641                 __func__, ni->ni_macaddr, ":",
 642                 size, data_retry, rts_retry);
 643         for (i = 0; i < res_len; ++i) {
 644                 int is_fail = is_fail0;
 645
 646                 if (i == 0 && (data_retry + 1) > res[0].rc_res_tries &&
 647                     res[0].rc_res_rateidx == sd->current_sample_ndx[size_bin])
 648                         is_fail = 1;
 649
 650                 sample_update_stats(ssc, ni, size, size_bin,
 651                                     &res[i], res_len - i,
 652                                     rts_retry + 1, is_fail);
 653         }
 654 }
 655
 656 static void
 657 sample_newassoc(void *arg, struct ieee80211_node *ni, int isnew)
 658 {
 659         struct sample_softc *ssc = arg;
 660
 661         DPRINTF(ssc, 5, "%s: %6D isnew %d\n", __func__,
 662                 ni->ni_macaddr, ":", isnew);
 663
 664         if (isnew)
 665                 sample_start(ssc, ni);
 666 }
 667
 668 /*
 669  * Initialize the tables for a node.
 670  */
 671 static void
 672 sample_start(struct sample_softc *ssc, struct ieee80211_node *ni)
 673 {
 674 #define RATE(_ix)       IEEE80211_RS_RATE(&ni->ni_rates, (_ix))
 675         struct ieee80211com *ic = ssc->ic;
 676         struct sample_data *sd = ni->ni_rate_data;
 677         int x, y, srate;
 678
 679         if (sd == NULL) {
 680                 sample_data_alloc(ni);
 681
 682                 sd = ni->ni_rate_data;
 683                 if (sd == NULL)
 684                         return;
 685         }
 686
 687         sd->static_rate_ndx = -1;
 688         if (ic->ic_fixed_rate != IEEE80211_FIXED_RATE_NONE) {
 689                 /*
 690                  * A fixed rate is to be used; ic_fixed_rate is an
 691                  * index into the supported rate set.  Convert this
 692                  * to the index into the negotiated rate set for
 693                  * the node.
 694                  */
 695                 const struct ieee80211_rateset *rs =
 696                         &ic->ic_sup_rates[ic->ic_curmode];
 697                 int r = IEEE80211_RS_RATE(rs, ic->ic_fixed_rate);
 698
 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                 sd->static_rate_ndx = srate;
 706         }
 707
 708 #ifdef SAMPLE_DEBUG
 709         DPRINTF(ssc, 1, "%s: %6D size 1600 rate/tt", __func__,
 710                 ni->ni_macaddr, ":");
 711         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 712                 DPRINTF(ssc, 1, " %d/%d", RATE(x),
 713                         unicast_pkt_time(ssc, ni, RATE(x), 1600, 1, 1, NULL));
 714         }
 715         DPRINTF(ssc, 1, "%s\n", "");
 716 #endif
 717
 718         /* Set the visible bit-rate to the lowest one available */
 719         ni->ni_txrate = 0;
 720
 721         for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) {
 722                 int size = bin_to_size(y);
 723                 int ndx = 0;
 724
 725                 sd->packets_sent[y] = 0;
 726                 sd->current_sample_ndx[y] = -1;
 727                 sd->last_sample_ndx[y] = 0;
 728
 729                 DPRINTF(ssc, 1, "%s: %6D size %d rate/tt", __func__,
 730                         ni->ni_macaddr, ":", size);
 731                 for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
 732                         sd->stats[y][x].successive_failures = 0;
 733                         sd->stats[y][x].tries = 0;
 734                         sd->stats[y][x].total_packets = 0;
 735                         sd->stats[y][x].packets_acked = 0;
 736                         sd->stats[y][x].last_tx = 0;
 737
 738                         sd->stats[y][x].perfect_tx_time =
 739                                 unicast_pkt_time(ssc, ni, RATE(x), size,
 740                                                  1, 1, NULL);
 741
 742                         DPRINTF(ssc, 1, " %d/%d", RATE(x),
 743                                 sd->stats[y][x].perfect_tx_time);
 744
 745                         sd->stats[y][x].average_tx_time =
 746                                 sd->stats[y][x].perfect_tx_time;
 747                 }
 748                 DPRINTF(ssc, 1, "%s\n", "");
 749
 750                 /* Set the initial rate */
 751                 for (ndx = ni->ni_rates.rs_nrates - 1; ndx > 0; ndx--) {
 752                         if (RATE(ndx) <= 72)
 753                                 break;
 754                 }
 755                 sd->current_rate[y] = ndx;
 756         }
 757
 758         DPRINTF(ssc, 1, "%s: %6D %d rates %d%sMbps (%dus)- %d%sMbps (%dus)\n",
 759                 __func__, ni->ni_macaddr, ":",
 760                 ni->ni_rates.rs_nrates,
 761                 RATE(0) / 2, RATE(0) % 2 ? ".5" : "",
 762                 sd->stats[1][0].perfect_tx_time,
 763                 RATE(ni->ni_rates.rs_nrates - 1) / 2,
 764                 RATE(ni->ni_rates.rs_nrates - 1) % 2 ? ".5" : "",
 765                 sd->stats[1][ni->ni_rates.rs_nrates - 1].perfect_tx_time);
 766
 767         if (sd->static_rate_ndx != -1)
 768                 ni->ni_txrate = sd->static_rate_ndx;
 769         else
 770                 ni->ni_txrate = sd->current_rate[0];
 771 #undef RATE
 772
 773         sd->started = 1;
 774 }
 775
 776 static void
 777 sample_rate_cb(void *arg, struct ieee80211_node *ni)
 778 {
 779         sample_newassoc(arg, ni, 1);
 780 }
 781
 782 /*
 783  * Reset the rate control state for each 802.11 state transition.
 784  */
 785 static void
 786 sample_newstate(void *arg, enum ieee80211_state state)
 787 {
 788         struct sample_softc *ssc = arg;
 789
 790         if (state == IEEE80211_S_RUN) {
 791                 struct ieee80211com *ic = ssc->ic;
 792
 793                 if (ic->ic_opmode != IEEE80211_M_STA) {
 794                         /*
 795                          * Sync rates for associated stations and neighbors.
 796                          */
 797                         ieee80211_iterate_nodes(&ic->ic_sta, sample_rate_cb,
 798                                                 ssc);
 799                 }
 800                 sample_newassoc(ssc, ic->ic_bss, 1);
 801         }
 802 }
 803
 804 static void
 805 sample_sysctl_attach(struct sample_softc *ssc)
 806 {
 807         sysctl_ctx_init(&ssc->sysctl_ctx);
 808         ssc->sysctl_oid = SYSCTL_ADD_NODE(&ssc->sysctl_ctx,
 809                 SYSCTL_CHILDREN(ssc->ic->ic_sysctl_oid),
 810                 OID_AUTO, "sample_ratectl", CTLFLAG_RD, 0, "");
 811         if (ssc->sysctl_oid == NULL) {
 812                 kprintf("wlan_ratectl_sample: create sysctl tree failed\n");
 813                 return;
 814         }
 815
 816         /* XXX bounds check [0..100] */
 817         SYSCTL_ADD_INT(&ssc->sysctl_ctx, SYSCTL_CHILDREN(ssc->sysctl_oid),
 818                        OID_AUTO, "smoothing_rate", CTLFLAG_RW,
 819                        &ssc->param->sample_smoothing_rate, 0,
 820                        "rate control: "
 821                        "retry threshold to credit rate raise (%%)");
 822
 823         /* XXX bounds check [2..100] */
 824         SYSCTL_ADD_INT(&ssc->sysctl_ctx, SYSCTL_CHILDREN(ssc->sysctl_oid),
 825                        OID_AUTO, "sample_rate", CTLFLAG_RW,
 826                        &ssc->param->sample_rate, 0,
 827                        "rate control: "
 828                        "# good periods before raising rate");
 829
 830         SYSCTL_ADD_INT(&ssc->sysctl_ctx, SYSCTL_CHILDREN(ssc->sysctl_oid),
 831                        OID_AUTO, "debug", CTLFLAG_RW,
 832                        &ssc->param->sample_debug, 0,
 833                        "rate control: debug level");
 834 }
 835
 836 static void *
 837 sample_attach(struct ieee80211com *ic)
 838 {
 839         struct sample_softc *ssc;
 840
 841         sample_nrefs++;
 842
 843         ssc = kmalloc(sizeof(struct sample_softc), M_DEVBUF, M_WAITOK | M_ZERO);
 844
 845         ssc->ic = ic;
 846         ssc->param = ic->ic_ratectl.rc_st_attach(ic, IEEE80211_RATECTL_SAMPLE);
 847
 848         sample_sysctl_attach(ssc);
 849
 850         sample_newstate(ssc, ic->ic_state);
 851
 852         return ssc;
 853 }
 854
 855 static void
 856 _sample_data_free(void *arg __unused, struct ieee80211_node *ni)
 857 {
 858         sample_data_free(ni);
 859 }
 860
 861 static void
 862 sample_detach(void *arg)
 863 {
 864         struct sample_softc *ssc = arg;
 865         struct ieee80211com *ic = ssc->ic;
 866
 867         sample_newstate(ssc, IEEE80211_S_INIT);
 868
 869         ieee80211_iterate_nodes(&ic->ic_sta, _sample_data_free, NULL);
 870         ieee80211_iterate_nodes(&ic->ic_scan, _sample_data_free, NULL);
 871
 872         if (ssc->sysctl_oid != NULL)
 873                 sysctl_ctx_free(&ssc->sysctl_ctx);
 874         kfree(ssc, M_DEVBUF);
 875
 876         sample_nrefs--;
 877 }
 878
 879 static void
 880 sample_data_alloc(struct ieee80211_node *ni)
 881 {
 882         KKASSERT(ni->ni_rate_data == NULL);
 883         ni->ni_rate_data = kmalloc(sizeof(struct sample_data),
 884                                    M_SAMPLE_RATECTL_DATA, M_NOWAIT | M_ZERO);
 885 }
 886
 887 static void
 888 sample_data_free(struct ieee80211_node *ni)
 889 {
 890         if (ni->ni_rate_data != NULL) {
 891                 kfree(ni->ni_rate_data, M_SAMPLE_RATECTL_DATA);
 892                 ni->ni_rate_data = NULL;
 893         }
 894 }
 895
 896 static void
 897 sample_data_dup(const struct ieee80211_node *oni, struct ieee80211_node *nni)
 898 {
 899         if (oni->ni_rate_data == NULL || nni->ni_rate_data == NULL)
 900                 return;
 901
 902         bcopy(oni->ni_rate_data, nni->ni_rate_data,
 903               sizeof(struct sample_data));
 904 }
 905
 906 /*
 907  * Module glue.
 908  */
 909 static int
 910 sample_modevent(module_t mod, int type, void *unused)
 911 {
 912         switch (type) {
 913         case MOD_LOAD:
 914                 ieee80211_ratectl_register(&sample);
 915                 return 0;
 916         case MOD_UNLOAD:
 917                 if (sample_nrefs) {
 918                         kprintf("wlan_ratectl_sample: still in use "
 919                                 "(%u dynamic refs)\n", sample_nrefs);
 920                         return EBUSY;
 921                 }
 922                 ieee80211_ratectl_unregister(&sample);
 923                 return 0;
 924         }
 925         return EINVAL;
 926 }
 927
 928 static moduledata_t sample_mod = {
 929         "wlan_ratectl_sample",
 930         sample_modevent,
 931         0
 932 };
 933 DECLARE_MODULE(wlan_ratectl_sample, sample_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
 934 MODULE_VERSION(wlan_ratectl_sample, 1);
 935 MODULE_DEPEND(wlan_ratectl_sample, wlan, 1, 1, 1);