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