sample.c revision 185490
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 185490 2008-11-30 21:59:44Z 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#ifdef Q 409#undef Q /* sun4v bogosity */ 410#endif 411#define Q(_r) \ 412 (((_r) == 1.5) ? 0 : (((_r) ==2.25) ? 1 : (((_r) == 3) ? 2 : \ 413 (((_r) == 4.5) ? 3 : (((_r) == 6) ? 4 : (((_r) == 9) ? 5 : \ 414 (((_r) == 12) ? 6 : (((_r) == 13.5)? 7 : 0)))))))) 415static const struct txschedule series_quarter[] = { 416 { 3,Q( 1.5),3,Q(1.5), 0,Q(1.5), 0,Q(1.5) }, /* 1.5Mb/s */ 417 { 4,Q(2.25),3,Q(1.5), 4,Q(1.5), 0,Q(1.5) }, /*2.25Mb/s */ 418 { 4,Q( 3),3,Q(1.5), 4,Q(1.5), 0,Q(1.5) }, /* 3Mb/s */ 419 { 4,Q( 4.5),3,Q( 3), 4,Q(1.5), 2,Q(1.5) }, /* 4.5Mb/s */ 420 { 4,Q( 6),3,Q(4.5), 4,Q( 3), 2,Q(1.5) }, /* 6Mb/s */ 421 { 4,Q( 9),3,Q( 6), 4,Q(4.5), 2,Q(1.5) }, /* 9Mb/s */ 422 { 4,Q( 12),3,Q( 9), 4,Q( 6), 2,Q( 3) }, /* 12Mb/s */ 423 { 4,Q(13.5),3,Q( 12), 4,Q( 9), 2,Q( 6) } /*13.5Mb/s */ 424}; 425#undef Q 426 427void 428ath_rate_setupxtxdesc(struct ath_softc *sc, struct ath_node *an, 429 struct ath_desc *ds, int shortPreamble, u_int8_t rix) 430{ 431 struct sample_node *sn = ATH_NODE_SAMPLE(an); 432 const struct txschedule *sched = &sn->sched[rix]; 433 const HAL_RATE_TABLE *rt = sc->sc_currates; 434 uint8_t rix1, s1code, rix2, s2code, rix3, s3code; 435 436 /* XXX precalculate short preamble tables */ 437 rix1 = sched->r1; 438 s1code = rt->info[rix1].rateCode 439 | (shortPreamble ? rt->info[rix1].shortPreamble : 0); 440 rix2 = sched->r2; 441 s2code = rt->info[rix2].rateCode 442 | (shortPreamble ? rt->info[rix2].shortPreamble : 0); 443 rix3 = sched->r3; 444 s3code = rt->info[rix3].rateCode 445 | (shortPreamble ? rt->info[rix3].shortPreamble : 0); 446 ath_hal_setupxtxdesc(sc->sc_ah, ds, 447 s1code, sched->t1, /* series 1 */ 448 s2code, sched->t2, /* series 2 */ 449 s3code, sched->t3); /* series 3 */ 450} 451 452static void 453update_stats(struct ath_softc *sc, struct ath_node *an, 454 int frame_size, 455 int rix0, int tries0, 456 int rix1, int tries1, 457 int rix2, int tries2, 458 int rix3, int tries3, 459 int short_tries, int tries, int status) 460{ 461 struct sample_node *sn = ATH_NODE_SAMPLE(an); 462 struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc); 463 const int size_bin = size_to_bin(frame_size); 464 const int size = bin_to_size(size_bin); 465 int tt, tries_so_far; 466 467 if (!IS_RATE_DEFINED(sn, rix0)) 468 return; 469 tt = calc_usecs_unicast_packet(sc, size, rix0, short_tries, 470 MIN(tries0, tries) - 1); 471 tries_so_far = tries0; 472 473 if (tries1 && tries_so_far < tries) { 474 if (!IS_RATE_DEFINED(sn, rix1)) 475 return; 476 tt += calc_usecs_unicast_packet(sc, size, rix1, short_tries, 477 MIN(tries1 + tries_so_far, tries) - tries_so_far - 1); 478 tries_so_far += tries1; 479 } 480 481 if (tries2 && tries_so_far < tries) { 482 if (!IS_RATE_DEFINED(sn, rix2)) 483 return; 484 tt += calc_usecs_unicast_packet(sc, size, rix2, short_tries, 485 MIN(tries2 + tries_so_far, tries) - tries_so_far - 1); 486 tries_so_far += tries2; 487 } 488 489 if (tries3 && tries_so_far < tries) { 490 if (!IS_RATE_DEFINED(sn, rix3)) 491 return; 492 tt += calc_usecs_unicast_packet(sc, size, rix3, short_tries, 493 MIN(tries3 + tries_so_far, tries) - tries_so_far - 1); 494 } 495 496 if (sn->stats[size_bin][rix0].total_packets < ssc->smoothing_minpackets) { 497 /* just average the first few packets */ 498 int avg_tx = sn->stats[size_bin][rix0].average_tx_time; 499 int packets = sn->stats[size_bin][rix0].total_packets; 500 sn->stats[size_bin][rix0].average_tx_time = (tt+(avg_tx*packets))/(packets+1); 501 } else { 502 /* use a ewma */ 503 sn->stats[size_bin][rix0].average_tx_time = 504 ((sn->stats[size_bin][rix0].average_tx_time * ssc->smoothing_rate) + 505 (tt * (100 - ssc->smoothing_rate))) / 100; 506 } 507 508 if (status != 0) { 509 int y; 510 sn->stats[size_bin][rix0].successive_failures++; 511 for (y = size_bin+1; y < NUM_PACKET_SIZE_BINS; y++) { 512 /* 513 * Also say larger packets failed since we 514 * assume if a small packet fails at a 515 * bit-rate then a larger one will also. 516 */ 517 sn->stats[y][rix0].successive_failures++; 518 sn->stats[y][rix0].last_tx = ticks; 519 sn->stats[y][rix0].tries += tries; 520 sn->stats[y][rix0].total_packets++; 521 } 522 } else { 523 sn->stats[size_bin][rix0].packets_acked++; 524 sn->stats[size_bin][rix0].successive_failures = 0; 525 } 526 sn->stats[size_bin][rix0].tries += tries; 527 sn->stats[size_bin][rix0].last_tx = ticks; 528 sn->stats[size_bin][rix0].total_packets++; 529 530 if (rix0 == sn->current_sample_rix[size_bin]) { 531 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL, 532 &an->an_node, 533"%s: size %d %s sample rate %d tries (%d/%d) tt %d avg_tt (%d/%d)", 534 __func__, 535 size, 536 status ? "FAIL" : "OK", 537 rix0, short_tries, tries, tt, 538 sn->stats[size_bin][rix0].average_tx_time, 539 sn->stats[size_bin][rix0].perfect_tx_time); 540 sn->sample_tt[size_bin] = tt; 541 sn->current_sample_rix[size_bin] = -1; 542 } 543} 544 545static void 546badrate(struct ifnet *ifp, int series, int hwrate, int tries, int status) 547{ 548 if_printf(ifp, "bad series%d hwrate 0x%x, tries %u ts_status 0x%x\n", 549 series, hwrate, tries, status); 550} 551 552void 553ath_rate_tx_complete(struct ath_softc *sc, struct ath_node *an, 554 const struct ath_buf *bf) 555{ 556 struct ifnet *ifp = sc->sc_ifp; 557 struct ieee80211com *ic = ifp->if_l2com; 558 struct sample_node *sn = ATH_NODE_SAMPLE(an); 559 const struct ath_tx_status *ts = &bf->bf_status.ds_txstat; 560 const struct ath_desc *ds0 = &bf->bf_desc[0]; 561 int final_rix, short_tries, long_tries, frame_size; 562 const HAL_RATE_TABLE *rt = sc->sc_currates; 563 int mrr; 564 565 final_rix = rt->rateCodeToIndex[ts->ts_rate &~ HAL_TXSTAT_ALTRATE]; 566 short_tries = ts->ts_shortretry; 567 long_tries = ts->ts_longretry + 1; 568 frame_size = ds0->ds_ctl0 & 0x0fff; /* low-order 12 bits of ds_ctl0 */ 569 if (frame_size == 0) /* NB: should not happen */ 570 frame_size = 1500; 571 572 if (sn->ratemask == 0) { 573 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL, 574 &an->an_node, 575 "%s: size %d %s rate/try %d/%d no rates yet", 576 __func__, 577 bin_to_size(size_to_bin(frame_size)), 578 ts->ts_status ? "FAIL" : "OK", 579 short_tries, long_tries); 580 return; 581 } 582 mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT); 583 if (!mrr || !(ts->ts_rate & HAL_TXSTAT_ALTRATE)) { 584 if (!IS_RATE_DEFINED(sn, final_rix)) { 585 badrate(ifp, 0, ts->ts_rate, long_tries, ts->ts_status); 586 return; 587 } 588 /* 589 * Only one rate was used; optimize work. 590 */ 591 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL, 592 &an->an_node, "%s: size %d %s rate/try %d/%d/%d", 593 __func__, 594 bin_to_size(size_to_bin(frame_size)), 595 ts->ts_status ? "FAIL" : "OK", 596 final_rix, short_tries, long_tries); 597 update_stats(sc, an, frame_size, 598 final_rix, long_tries, 599 0, 0, 600 0, 0, 601 0, 0, 602 short_tries, long_tries, ts->ts_status); 603 } else { 604 int hwrate0, rix0, tries0; 605 int hwrate1, rix1, tries1; 606 int hwrate2, rix2, tries2; 607 int hwrate3, rix3, tries3; 608 int finalTSIdx = ts->ts_finaltsi; 609 610 /* 611 * Process intermediate rates that failed. 612 */ 613 if (sc->sc_ah->ah_magic != 0x20065416) { 614 hwrate0 = MS(ds0->ds_ctl3, AR_XmitRate0); 615 hwrate1 = MS(ds0->ds_ctl3, AR_XmitRate1); 616 hwrate2 = MS(ds0->ds_ctl3, AR_XmitRate2); 617 hwrate3 = MS(ds0->ds_ctl3, AR_XmitRate3); 618 } else { 619 hwrate0 = MS(ds0->ds_ctl3, AR5416_XmitRate0); 620 hwrate1 = MS(ds0->ds_ctl3, AR5416_XmitRate1); 621 hwrate2 = MS(ds0->ds_ctl3, AR5416_XmitRate2); 622 hwrate3 = MS(ds0->ds_ctl3, AR5416_XmitRate3); 623 } 624 625 rix0 = rt->rateCodeToIndex[hwrate0]; 626 tries0 = MS(ds0->ds_ctl2, AR_XmitDataTries0); 627 628 rix1 = rt->rateCodeToIndex[hwrate1]; 629 tries1 = MS(ds0->ds_ctl2, AR_XmitDataTries1); 630 631 rix2 = rt->rateCodeToIndex[hwrate2]; 632 tries2 = MS(ds0->ds_ctl2, AR_XmitDataTries2); 633 634 rix3 = rt->rateCodeToIndex[hwrate3]; 635 tries3 = MS(ds0->ds_ctl2, AR_XmitDataTries3); 636 637 IEEE80211_NOTE(an->an_node.ni_vap, IEEE80211_MSG_RATECTL, 638 &an->an_node, 639"%s: size %d finaltsidx %d tries %d %s rate/try [%d/%d %d/%d %d/%d %d/%d]", 640 __func__, 641 bin_to_size(size_to_bin(frame_size)), 642 finalTSIdx, 643 long_tries, 644 ts->ts_status ? "FAIL" : "OK", 645 rix0, tries0, 646 rix1, tries1, 647 rix2, tries2, 648 rix3, tries3); 649 650 if (tries0 && !IS_RATE_DEFINED(sn, rix0)) 651 badrate(ifp, 0, hwrate0, tries0, ts->ts_status); 652 if (tries1 && !IS_RATE_DEFINED(sn, rix1)) 653 badrate(ifp, 1, hwrate1, tries1, ts->ts_status); 654 if (tries2 && !IS_RATE_DEFINED(sn, rix2)) 655 badrate(ifp, 2, hwrate2, tries2, ts->ts_status); 656 if (tries3 && !IS_RATE_DEFINED(sn, rix3)) 657 badrate(ifp, 3, hwrate3, tries3, ts->ts_status); 658 659 /* 660 * NB: series > 0 are not penalized for failure 661 * based on the try counts under the assumption 662 * that losses are often bursty and since we 663 * sample higher rates 1 try at a time doing so 664 * may unfairly penalize them. 665 */ 666 if (tries0) { 667 update_stats(sc, an, frame_size, 668 rix0, tries0, 669 rix1, tries1, 670 rix2, tries2, 671 rix3, tries3, 672 short_tries, long_tries, 673 long_tries > tries0); 674 long_tries -= tries0; 675 } 676 677 if (tries1 && finalTSIdx > 0) { 678 update_stats(sc, an, frame_size, 679 rix1, tries1, 680 rix2, tries2, 681 rix3, tries3, 682 0, 0, 683 short_tries, long_tries, 684 ts->ts_status); 685 long_tries -= tries1; 686 } 687 688 if (tries2 && finalTSIdx > 1) { 689 update_stats(sc, an, frame_size, 690 rix2, tries2, 691 rix3, tries3, 692 0, 0, 693 0, 0, 694 short_tries, long_tries, 695 ts->ts_status); 696 long_tries -= tries2; 697 } 698 699 if (tries3 && finalTSIdx > 2) { 700 update_stats(sc, an, frame_size, 701 rix3, tries3, 702 0, 0, 703 0, 0, 704 0, 0, 705 short_tries, long_tries, 706 ts->ts_status); 707 } 708 } 709} 710 711void 712ath_rate_newassoc(struct ath_softc *sc, struct ath_node *an, int isnew) 713{ 714 if (isnew) 715 ath_rate_ctl_reset(sc, &an->an_node); 716} 717 718static const struct txschedule *mrr_schedules[IEEE80211_MODE_MAX+2] = { 719 NULL, /* IEEE80211_MODE_AUTO */ 720 series_11a, /* IEEE80211_MODE_11A */ 721 series_11g, /* IEEE80211_MODE_11B */ 722 series_11g, /* IEEE80211_MODE_11G */ 723 NULL, /* IEEE80211_MODE_FH */ 724 series_11a, /* IEEE80211_MODE_TURBO_A */ 725 series_11g, /* IEEE80211_MODE_TURBO_G */ 726 series_11a, /* IEEE80211_MODE_STURBO_A */ 727 series_11a, /* IEEE80211_MODE_11NA */ 728 series_11g, /* IEEE80211_MODE_11NG */ 729 series_half, /* IEEE80211_MODE_HALF */ 730 series_quarter, /* IEEE80211_MODE_QUARTER */ 731}; 732 733/* 734 * Initialize the tables for a node. 735 */ 736static void 737ath_rate_ctl_reset(struct ath_softc *sc, struct ieee80211_node *ni) 738{ 739#define RATE(_ix) (ni->ni_rates.rs_rates[(_ix)] & IEEE80211_RATE_VAL) 740#define DOT11RATE(_ix) (rt->info[(_ix)].dot11Rate & IEEE80211_RATE_VAL) 741 struct ath_node *an = ATH_NODE(ni); 742 const struct ieee80211_txparam *tp = ni->ni_txparms; 743 struct sample_node *sn = ATH_NODE_SAMPLE(an); 744 const HAL_RATE_TABLE *rt = sc->sc_currates; 745 int x, y, srate, rix; 746 747 KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode)); 748 749 KASSERT(sc->sc_curmode < IEEE80211_MODE_MAX+2, 750 ("curmode %u", sc->sc_curmode)); 751 sn->sched = mrr_schedules[sc->sc_curmode]; 752 KASSERT(sn->sched != NULL, 753 ("no mrr schedule for mode %u", sc->sc_curmode)); 754 755 sn->static_rix = -1; 756 if (tp != NULL && tp->ucastrate != IEEE80211_FIXED_RATE_NONE) { 757 /* 758 * A fixed rate is to be used; ic_fixed_rate is the 759 * IEEE code for this rate (sans basic bit). Convert this 760 * to the index into the negotiated rate set for 761 * the node. 762 */ 763 /* NB: the rate set is assumed sorted */ 764 srate = ni->ni_rates.rs_nrates - 1; 765 for (; srate >= 0 && RATE(srate) != tp->ucastrate; srate--) 766 ; 767 /* 768 * The fixed rate may not be available due to races 769 * and mode settings. Also orphaned nodes created in 770 * adhoc mode may not have any rate set so this lookup 771 * can fail. 772 */ 773 if (srate >= 0) 774 sn->static_rix = sc->sc_rixmap[srate]; 775 } 776 777 /* 778 * Construct a bitmask of usable rates. This has all 779 * negotiated rates minus those marked by the hal as 780 * to be ignored for doing rate control. 781 */ 782 sn->ratemask = 0; 783 for (x = 0; x < ni->ni_rates.rs_nrates; x++) { 784 rix = sc->sc_rixmap[RATE(x)]; 785 if (rix == 0xff) 786 continue; 787 /* skip rates marked broken by hal */ 788 if (!rt->info[rix].valid) 789 continue; 790 KASSERT(rix < SAMPLE_MAXRATES, 791 ("rate %u has rix %d", RATE(x), rix)); 792 sn->ratemask |= 1<<rix; 793 } 794#ifdef IEEE80211_DEBUG 795 if (ieee80211_msg(ni->ni_vap, IEEE80211_MSG_RATECTL)) { 796 uint32_t mask; 797 798 ieee80211_note(ni->ni_vap, "[%6D] %s: size 1600 rate/tt", 799 ni->ni_macaddr, ":", __func__); 800 for (mask = sn->ratemask, rix = 0; mask != 0; mask >>= 1, rix++) { 801 if ((mask & 1) == 0) 802 continue; 803 printf(" %d/%d", DOT11RATE(rix) / 2, 804 calc_usecs_unicast_packet(sc, 1600, rix, 0,0)); 805 } 806 printf("\n"); 807 } 808#endif 809 for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) { 810 int size = bin_to_size(y); 811 uint32_t mask; 812 813 sn->packets_sent[y] = 0; 814 sn->current_sample_rix[y] = -1; 815 sn->last_sample_rix[y] = 0; 816 /* XXX start with first valid rate */ 817 sn->current_rix[y] = ffs(sn->ratemask)-1; 818 819 /* 820 * Initialize the statistics buckets; these are 821 * indexed by the rate code index. 822 */ 823 for (rix = 0, mask = sn->ratemask; mask != 0; rix++, mask >>= 1) { 824 if ((mask & 1) == 0) /* not a valid rate */ 825 continue; 826 sn->stats[y][rix].successive_failures = 0; 827 sn->stats[y][rix].tries = 0; 828 sn->stats[y][rix].total_packets = 0; 829 sn->stats[y][rix].packets_acked = 0; 830 sn->stats[y][rix].last_tx = 0; 831 832 sn->stats[y][rix].perfect_tx_time = 833 calc_usecs_unicast_packet(sc, size, rix, 0, 0); 834 sn->stats[y][rix].average_tx_time = 835 sn->stats[y][rix].perfect_tx_time; 836 } 837 } 838#if 0 839 /* XXX 0, num_rates-1 are wrong */ 840 IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni, 841 "%s: %d rates %d%sMbps (%dus)- %d%sMbps (%dus)", __func__, 842 sn->num_rates, 843 DOT11RATE(0)/2, DOT11RATE(0) % 1 ? ".5" : "", 844 sn->stats[1][0].perfect_tx_time, 845 DOT11RATE(sn->num_rates-1)/2, DOT11RATE(sn->num_rates-1) % 1 ? ".5" : "", 846 sn->stats[1][sn->num_rates-1].perfect_tx_time 847 ); 848#endif 849 /* set the visible bit-rate */ 850 if (sn->static_rix != -1) 851 ni->ni_txrate = DOT11RATE(sn->static_rix); 852 else 853 ni->ni_txrate = RATE(0); 854#undef RATE 855#undef DOT11RATE 856} 857 858static void 859sample_stats(void *arg, struct ieee80211_node *ni) 860{ 861 struct ath_softc *sc = arg; 862 const HAL_RATE_TABLE *rt = sc->sc_currates; 863 struct sample_node *sn = ATH_NODE_SAMPLE(ATH_NODE(ni)); 864 uint32_t mask; 865 int rix, y; 866 867 printf("\n[%s] refcnt %d static_rix %d ratemask 0x%x\n", 868 ether_sprintf(ni->ni_macaddr), ieee80211_node_refcnt(ni), 869 sn->static_rix, sn->ratemask); 870 for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) { 871 printf("[%4u] cur rix %d since switch: packets %d ticks %u\n", 872 bin_to_size(y), sn->current_rix[y], 873 sn->packets_since_switch[y], sn->ticks_since_switch[y]); 874 printf("[%4u] last sample %d cur sample %d packets sent %d\n", 875 bin_to_size(y), sn->last_sample_rix[y], 876 sn->current_sample_rix[y], sn->packets_sent[y]); 877 printf("[%4u] packets since sample %d sample tt %u\n", 878 bin_to_size(y), sn->packets_since_sample[y], 879 sn->sample_tt[y]); 880 } 881 for (mask = sn->ratemask, rix = 0; mask != 0; mask >>= 1, rix++) { 882 if ((mask & 1) == 0) 883 continue; 884 for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) { 885 if (sn->stats[y][rix].total_packets == 0) 886 continue; 887 printf("[%2u:%4u] %8d:%-8d (%3d%%) T %8d F %4d avg %5u last %u\n", 888 (rt->info[rix].dot11Rate & IEEE80211_RATE_VAL)/2, 889 bin_to_size(y), 890 sn->stats[y][rix].total_packets, 891 sn->stats[y][rix].packets_acked, 892 (100*sn->stats[y][rix].packets_acked)/sn->stats[y][rix].total_packets, 893 sn->stats[y][rix].tries, 894 sn->stats[y][rix].successive_failures, 895 sn->stats[y][rix].average_tx_time, 896 ticks - sn->stats[y][rix].last_tx); 897 } 898 } 899} 900 901static int 902ath_rate_sysctl_stats(SYSCTL_HANDLER_ARGS) 903{ 904 struct ath_softc *sc = arg1; 905 struct ifnet *ifp = sc->sc_ifp; 906 struct ieee80211com *ic = ifp->if_l2com; 907 int error, v; 908 909 v = 0; 910 error = sysctl_handle_int(oidp, &v, 0, req); 911 if (error || !req->newptr) 912 return error; 913 ieee80211_iterate_nodes(&ic->ic_sta, sample_stats, sc); 914 return 0; 915} 916 917static int 918ath_rate_sysctl_smoothing_rate(SYSCTL_HANDLER_ARGS) 919{ 920 struct sample_softc *ssc = arg1; 921 int rate, error; 922 923 rate = ssc->smoothing_rate; 924 error = sysctl_handle_int(oidp, &rate, 0, req); 925 if (error || !req->newptr) 926 return error; 927 if (!(0 <= rate && rate < 100)) 928 return EINVAL; 929 ssc->smoothing_rate = rate; 930 ssc->smoothing_minpackets = 100 / (100 - rate); 931 return 0; 932} 933 934static int 935ath_rate_sysctl_sample_rate(SYSCTL_HANDLER_ARGS) 936{ 937 struct sample_softc *ssc = arg1; 938 int rate, error; 939 940 rate = ssc->sample_rate; 941 error = sysctl_handle_int(oidp, &rate, 0, req); 942 if (error || !req->newptr) 943 return error; 944 if (!(2 <= rate && rate <= 100)) 945 return EINVAL; 946 ssc->sample_rate = rate; 947 return 0; 948} 949 950static void 951ath_rate_sysctlattach(struct ath_softc *sc, struct sample_softc *ssc) 952{ 953 struct sysctl_ctx_list *ctx = device_get_sysctl_ctx(sc->sc_dev); 954 struct sysctl_oid *tree = device_get_sysctl_tree(sc->sc_dev); 955 956 SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO, 957 "smoothing_rate", CTLTYPE_INT | CTLFLAG_RW, ssc, 0, 958 ath_rate_sysctl_smoothing_rate, "I", 959 "sample: smoothing rate for avg tx time (%%)"); 960 SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO, 961 "sample_rate", CTLTYPE_INT | CTLFLAG_RW, ssc, 0, 962 ath_rate_sysctl_sample_rate, "I", 963 "sample: percent air time devoted to sampling new rates (%%)"); 964 /* XXX max_successive_failures, stale_failure_timeout, min_switch */ 965 SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO, 966 "sample_stats", CTLTYPE_INT | CTLFLAG_RW, sc, 0, 967 ath_rate_sysctl_stats, "I", "sample: print statistics"); 968} 969 970struct ath_ratectrl * 971ath_rate_attach(struct ath_softc *sc) 972{ 973 struct sample_softc *ssc; 974 975 ssc = malloc(sizeof(struct sample_softc), M_DEVBUF, M_NOWAIT|M_ZERO); 976 if (ssc == NULL) 977 return NULL; 978 ssc->arc.arc_space = sizeof(struct sample_node); 979 ssc->smoothing_rate = 95; /* ewma percentage ([0..99]) */ 980 ssc->smoothing_minpackets = 100 / (100 - ssc->smoothing_rate); 981 ssc->sample_rate = 10; /* %time to try diff tx rates */ 982 ssc->max_successive_failures = 3; /* threshold for rate sampling*/ 983 ssc->stale_failure_timeout = 10 * hz; /* 10 seconds */ 984 ssc->min_switch = hz; /* 1 second */ 985 ath_rate_sysctlattach(sc, ssc); 986 return &ssc->arc; 987} 988 989void 990ath_rate_detach(struct ath_ratectrl *arc) 991{ 992 struct sample_softc *ssc = (struct sample_softc *) arc; 993 994 free(ssc, M_DEVBUF); 995} 996 997/* 998 * Module glue. 999 */ 1000static int 1001sample_modevent(module_t mod, int type, void *unused) 1002{ 1003 switch (type) { 1004 case MOD_LOAD: 1005 if (bootverbose) 1006 printf("ath_rate: version 1.9 <SampleRate bit-rate selection algorithm>\n"); 1007 return 0; 1008 case MOD_UNLOAD: 1009 return 0; 1010 } 1011 return EINVAL; 1012} 1013 1014static moduledata_t sample_mod = { 1015 "ath_rate", 1016 sample_modevent, 1017 0 1018}; 1019DECLARE_MODULE(ath_rate, sample_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST); 1020MODULE_VERSION(ath_rate, 1); 1021MODULE_DEPEND(ath_rate, ath_hal, 1, 1, 1); /* Atheros HAL */ 1022MODULE_DEPEND(ath_rate, wlan, 1, 1, 1); 1023