xref: /freebsd/sys/dev/ath/ath_rate/sample/sample.c (revision 1e413cf93298b5b97441a21d9a50fdcd0ee9945e)
1 /*-
2  * Copyright (c) 2005 John Bicket
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer,
10  *    without modification.
11  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
12  *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
13  *    redistribution must be conditioned upon including a substantially
14  *    similar Disclaimer requirement for further binary redistribution.
15  * 3. Neither the names of the above-listed copyright holders nor the names
16  *    of any contributors may be used to endorse or promote products derived
17  *    from this software without specific prior written permission.
18  *
19  * Alternatively, this software may be distributed under the terms of the
20  * GNU General Public License ("GPL") version 2 as published by the Free
21  * Software Foundation.
22  *
23  * NO WARRANTY
24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26  * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
27  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
28  * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
29  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
32  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
34  * THE POSSIBILITY OF SUCH DAMAGES.
35  *
36  */
37 
38 #include <sys/cdefs.h>
39 __FBSDID("$FreeBSD$");
40 
41 /*
42  * John Bicket's SampleRate control algorithm.
43  */
44 #include "opt_inet.h"
45 
46 #include <sys/param.h>
47 #include <sys/systm.h>
48 #include <sys/sysctl.h>
49 #include <sys/module.h>
50 #include <sys/kernel.h>
51 #include <sys/lock.h>
52 #include <sys/mutex.h>
53 #include <sys/errno.h>
54 
55 #include <machine/bus.h>
56 #include <machine/resource.h>
57 #include <sys/bus.h>
58 
59 #include <sys/socket.h>
60 
61 #include <net/if.h>
62 #include <net/if_media.h>
63 #include <net/if_arp.h>
64 #include <net/ethernet.h>		/* XXX for ether_sprintf */
65 
66 #include <net80211/ieee80211_var.h>
67 
68 #include <net/bpf.h>
69 
70 #ifdef INET
71 #include <netinet/in.h>
72 #include <netinet/if_ether.h>
73 #endif
74 
75 #include <dev/ath/if_athvar.h>
76 #include <dev/ath/ath_rate/sample/sample.h>
77 #include <contrib/dev/ath/ah_desc.h>
78 
79 #define	SAMPLE_DEBUG
80 #ifdef SAMPLE_DEBUG
81 enum {
82 	ATH_DEBUG_NODE		= 0x00080000,	/* node management */
83 	ATH_DEBUG_RATE		= 0x00000010,	/* rate control */
84 	ATH_DEBUG_ANY		= 0xffffffff
85 };
86 #define	DPRINTF(sc, m, fmt, ...) do {				\
87 	if (sc->sc_debug & (m))					\
88 		printf(fmt, __VA_ARGS__);			\
89 } while (0)
90 #else
91 #define	DPRINTF(sc, m, fmt, ...) do {				\
92 	(void) sc;						\
93 } while (0)
94 #endif
95 
96 /*
97  * This file is an implementation of the SampleRate algorithm
98  * in "Bit-rate Selection in Wireless Networks"
99  * (http://www.pdos.lcs.mit.edu/papers/jbicket-ms.ps)
100  *
101  * SampleRate chooses the bit-rate it predicts will provide the most
102  * throughput based on estimates of the expected per-packet
103  * transmission time for each bit-rate.  SampleRate periodically sends
104  * packets at bit-rates other than the current one to estimate when
105  * another bit-rate will provide better performance. SampleRate
106  * switches to another bit-rate when its estimated per-packet
107  * transmission time becomes smaller than the current bit-rate's.
108  * SampleRate reduces the number of bit-rates it must sample by
109  * eliminating those that could not perform better than the one
110  * currently being used.  SampleRate also stops probing at a bit-rate
111  * if it experiences several successive losses.
112  *
113  * The difference between the algorithm in the thesis and the one in this
114  * file is that the one in this file uses a ewma instead of a window.
115  *
116  * Also, this implementation tracks the average transmission time for
117  * a few different packet sizes independently for each link.
118  */
119 
120 #define STALE_FAILURE_TIMEOUT_MS 10000
121 #define MIN_SWITCH_MS 1000
122 
123 static void	ath_rate_ctl_reset(struct ath_softc *, struct ieee80211_node *);
124 
125 static __inline int
126 size_to_bin(int size)
127 {
128 	int x = 0;
129 	for (x = 0; x < NUM_PACKET_SIZE_BINS; x++) {
130 		if (size <= packet_size_bins[x]) {
131 			return x;
132 		}
133 	}
134 	return NUM_PACKET_SIZE_BINS-1;
135 }
136 static __inline int
137 bin_to_size(int index) {
138 	return packet_size_bins[index];
139 }
140 
141 static __inline int
142 rate_to_ndx(struct sample_node *sn, int rate) {
143 	int x = 0;
144 	for (x = 0; x < sn->num_rates; x++) {
145 		if (sn->rates[x].rate == rate) {
146 			return x;
147 		}
148 	}
149 	return -1;
150 }
151 
152 void
153 ath_rate_node_init(struct ath_softc *sc, struct ath_node *an)
154 {
155 	DPRINTF(sc, ATH_DEBUG_NODE, "%s:\n", __func__);
156 	/* NB: assumed to be zero'd by caller */
157 }
158 
159 void
160 ath_rate_node_cleanup(struct ath_softc *sc, struct ath_node *an)
161 {
162 	DPRINTF(sc, ATH_DEBUG_NODE, "%s:\n", __func__);
163 }
164 
165 
166 /*
167  * returns the ndx with the lowest average_tx_time,
168  * or -1 if all the average_tx_times are 0.
169  */
170 static __inline int best_rate_ndx(struct sample_node *sn, int size_bin,
171 				  int require_acked_before)
172 {
173 	int x = 0;
174         int best_rate_ndx = 0;
175         int best_rate_tt = 0;
176         for (x = 0; x < sn->num_rates; x++) {
177 		int tt = sn->stats[size_bin][x].average_tx_time;
178 		if (tt <= 0 || (require_acked_before &&
179 				!sn->stats[size_bin][x].packets_acked)) {
180 			continue;
181 		}
182 
183 		/* 9 megabits never works better than 12 */
184 		if (sn->rates[x].rate == 18)
185 			continue;
186 
187 		/* don't use a bit-rate that has been failing */
188 		if (sn->stats[size_bin][x].successive_failures > 3)
189 			continue;
190 
191 		if (!best_rate_tt || best_rate_tt > tt) {
192 			best_rate_tt = tt;
193 			best_rate_ndx = x;
194 		}
195         }
196         return (best_rate_tt) ? best_rate_ndx : -1;
197 }
198 
199 /*
200  * pick a good "random" bit-rate to sample other than the current one
201  */
202 static __inline int
203 pick_sample_ndx(struct sample_node *sn, int size_bin)
204 {
205 	int x = 0;
206 	int current_ndx = 0;
207 	unsigned current_tt = 0;
208 
209 	current_ndx = sn->current_rate[size_bin];
210 	if (current_ndx < 0) {
211 		/* no successes yet, send at the lowest bit-rate */
212 		return 0;
213 	}
214 
215 	current_tt = sn->stats[size_bin][current_ndx].average_tx_time;
216 
217 	for (x = 0; x < sn->num_rates; x++) {
218 		int ndx = (sn->last_sample_ndx[size_bin]+1+x) % sn->num_rates;
219 
220 	        /* don't sample the current bit-rate */
221 		if (ndx == current_ndx)
222 			continue;
223 
224 		/* this bit-rate is always worse than the current one */
225 		if (sn->stats[size_bin][ndx].perfect_tx_time > current_tt)
226 			continue;
227 
228 		/* rarely sample bit-rates that fail a lot */
229 		if (ticks - sn->stats[size_bin][ndx].last_tx < ((hz * STALE_FAILURE_TIMEOUT_MS)/1000) &&
230 		    sn->stats[size_bin][ndx].successive_failures > 3)
231 			continue;
232 
233 		/* don't sample more than 2 indexes higher
234 		 * for rates higher than 11 megabits
235 		 */
236 		if (sn->rates[ndx].rate > 22 && ndx > current_ndx + 2)
237 			continue;
238 
239 		/* 9 megabits never works better than 12 */
240 		if (sn->rates[ndx].rate == 18)
241 			continue;
242 
243 		/* if we're using 11 megabits, only sample up to 12 megabits
244 		 */
245 		if (sn->rates[current_ndx].rate == 22 && ndx > current_ndx + 1)
246 			continue;
247 
248 		sn->last_sample_ndx[size_bin] = ndx;
249 		return ndx;
250 	}
251 	return current_ndx;
252 }
253 
254 void
255 ath_rate_findrate(struct ath_softc *sc, struct ath_node *an,
256 		  int shortPreamble, size_t frameLen,
257 		  u_int8_t *rix, int *try0, u_int8_t *txrate)
258 {
259 	struct sample_node *sn = ATH_NODE_SAMPLE(an);
260 	struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc);
261 	struct ieee80211com *ic = &sc->sc_ic;
262 	int ndx, size_bin, mrr, best_ndx, change_rates;
263 	unsigned average_tx_time;
264 
265 	mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT);
266 	size_bin = size_to_bin(frameLen);
267 	best_ndx = best_rate_ndx(sn, size_bin, !mrr);
268 
269 	if (best_ndx >= 0) {
270 		average_tx_time = sn->stats[size_bin][best_ndx].average_tx_time;
271 	} else {
272 		average_tx_time = 0;
273 	}
274 
275 	if (sn->static_rate_ndx != -1) {
276 		ndx = sn->static_rate_ndx;
277 		*try0 = ATH_TXMAXTRY;
278 	} else {
279 		*try0 = mrr ? 2 : ATH_TXMAXTRY;
280 
281 		if (sn->sample_tt[size_bin] < average_tx_time * (sn->packets_since_sample[size_bin]*ssc->ath_sample_rate/100)) {
282 			/*
283 			 * we want to limit the time measuring the performance
284 			 * of other bit-rates to ath_sample_rate% of the
285 			 * total transmission time.
286 			 */
287 			ndx = pick_sample_ndx(sn, size_bin);
288 			if (ndx != sn->current_rate[size_bin]) {
289 				sn->current_sample_ndx[size_bin] = ndx;
290 			} else {
291 				sn->current_sample_ndx[size_bin] = -1;
292 			}
293 			sn->packets_since_sample[size_bin] = 0;
294 
295 		} else {
296 			change_rates = 0;
297 			if (!sn->packets_sent[size_bin] || best_ndx == -1) {
298 				/* no packet has been sent successfully yet */
299 				for (ndx = sn->num_rates-1; ndx > 0; ndx--) {
300 					/*
301 					 * pick the highest rate <= 36 Mbps
302 					 * that hasn't failed.
303 					 */
304 					if (sn->rates[ndx].rate <= 72 &&
305 					    sn->stats[size_bin][ndx].successive_failures == 0) {
306 						break;
307 					}
308 				}
309 				change_rates = 1;
310 				best_ndx = ndx;
311 			} else if (sn->packets_sent[size_bin] < 20) {
312 				/* let the bit-rate switch quickly during the first few packets */
313 				change_rates = 1;
314 			} else if (ticks - ((hz*MIN_SWITCH_MS)/1000) > sn->ticks_since_switch[size_bin]) {
315 				/* 2 seconds have gone by */
316 				change_rates = 1;
317 			} else if (average_tx_time * 2 < sn->stats[size_bin][sn->current_rate[size_bin]].average_tx_time) {
318 				/* the current bit-rate is twice as slow as the best one */
319 				change_rates = 1;
320 			}
321 
322 			sn->packets_since_sample[size_bin]++;
323 
324 			if (change_rates) {
325 				if (best_ndx != sn->current_rate[size_bin]) {
326 					DPRINTF(sc, ATH_DEBUG_RATE,
327 "%s: %s size %d switch rate %d (%d/%d) -> %d (%d/%d) after %d packets mrr %d\n",
328 					    __func__,
329 					    ether_sprintf(an->an_node.ni_macaddr),
330 					    packet_size_bins[size_bin],
331 					    sn->rates[sn->current_rate[size_bin]].rate,
332 					    sn->stats[size_bin][sn->current_rate[size_bin]].average_tx_time,
333 					    sn->stats[size_bin][sn->current_rate[size_bin]].perfect_tx_time,
334 					    sn->rates[best_ndx].rate,
335 					    sn->stats[size_bin][best_ndx].average_tx_time,
336 					    sn->stats[size_bin][best_ndx].perfect_tx_time,
337 					    sn->packets_since_switch[size_bin],
338 					    mrr);
339 				}
340 				sn->packets_since_switch[size_bin] = 0;
341 				sn->current_rate[size_bin] = best_ndx;
342 				sn->ticks_since_switch[size_bin] = ticks;
343 			}
344 			ndx = sn->current_rate[size_bin];
345 			sn->packets_since_switch[size_bin]++;
346 			if (size_bin == 0) {
347 	    			/*
348 	    			 * set the visible txrate for this node
349 			         * to the rate of small packets
350 			         */
351 				an->an_node.ni_txrate = ndx;
352 			}
353 		}
354 	}
355 
356 	KASSERT(ndx >= 0 && ndx < sn->num_rates, ("ndx is %d", ndx));
357 
358 	*rix = sn->rates[ndx].rix;
359 	if (shortPreamble) {
360 		*txrate = sn->rates[ndx].shortPreambleRateCode;
361 	} else {
362 		*txrate = sn->rates[ndx].rateCode;
363 	}
364 	sn->packets_sent[size_bin]++;
365 }
366 
367 void
368 ath_rate_setupxtxdesc(struct ath_softc *sc, struct ath_node *an,
369 		      struct ath_desc *ds, int shortPreamble, u_int8_t rix)
370 {
371 	struct sample_node *sn = ATH_NODE_SAMPLE(an);
372 	int rateCode = -1;
373 	int frame_size = 0;
374 	int size_bin = 0;
375 	int ndx = 0;
376 
377 	size_bin = size_to_bin(frame_size);	// TODO: it's correct that frame_size alway 0 ?
378 	ndx = sn->current_rate[size_bin]; /* retry at the current bit-rate */
379 
380 	if (!sn->stats[size_bin][ndx].packets_acked) {
381 		ndx = 0;  /* use the lowest bit-rate */
382 	}
383 
384 	if (shortPreamble) {
385 		rateCode = sn->rates[ndx].shortPreambleRateCode;
386 	} else {
387 		rateCode = sn->rates[ndx].rateCode;
388 	}
389 	ath_hal_setupxtxdesc(sc->sc_ah, ds
390 			     , rateCode, 3	        /* series 1 */
391 			     , sn->rates[0].rateCode, 3	/* series 2 */
392 			     , 0, 0	                /* series 3 */
393 			     );
394 }
395 
396 static void
397 update_stats(struct ath_softc *sc, struct ath_node *an,
398 		  int frame_size,
399 		  int ndx0, int tries0,
400 		  int ndx1, int tries1,
401 		  int ndx2, int tries2,
402 		  int ndx3, int tries3,
403 		  int short_tries, int tries, int status)
404 {
405 	struct sample_node *sn = ATH_NODE_SAMPLE(an);
406 	struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc);
407 	int tt = 0;
408 	int tries_so_far = 0;
409 	int size_bin = 0;
410 	int size = 0;
411 	int rate = 0;
412 
413 	size_bin = size_to_bin(frame_size);
414 	size = bin_to_size(size_bin);
415 
416 	if (!(0 <= ndx0 && ndx0 < sn->num_rates)) {
417 		printf("%s: bogus ndx0 %d, max %u, mode %u\n",
418 		    __func__, ndx0, sn->num_rates, sc->sc_curmode);
419 		return;
420 	}
421 	rate = sn->rates[ndx0].rate;
422 
423 	tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx0].rix,
424 					short_tries,
425 					MIN(tries0, tries) - 1);
426 	tries_so_far += tries0;
427 	if (tries1 && tries0 < tries) {
428 		if (!(0 <= ndx1 && ndx1 < sn->num_rates)) {
429 			printf("%s: bogus ndx1 %d, max %u, mode %u\n",
430 			    __func__, ndx1, sn->num_rates, sc->sc_curmode);
431 			return;
432 		}
433 		tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx1].rix,
434 						short_tries,
435 						MIN(tries1 + tries_so_far, tries) - tries_so_far - 1);
436 	}
437 	tries_so_far += tries1;
438 
439 	if (tries2 && tries0 + tries1 < tries) {
440 		if (!(0 <= ndx2 && ndx2 < sn->num_rates)) {
441 			printf("%s: bogus ndx2 %d, max %u, mode %u\n",
442 			    __func__, ndx2, sn->num_rates, sc->sc_curmode);
443 			return;
444 		}
445 		tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx2].rix,
446 					       short_tries,
447 						MIN(tries2 + tries_so_far, tries) - tries_so_far - 1);
448 	}
449 
450 	tries_so_far += tries2;
451 
452 	if (tries3 && tries0 + tries1 + tries2 < tries) {
453 		if (!(0 <= ndx3 && ndx3 < sn->num_rates)) {
454 			printf("%s: bogus ndx3 %d, max %u, mode %u\n",
455 			    __func__, ndx3, sn->num_rates, sc->sc_curmode);
456 			return;
457 		}
458 		tt += calc_usecs_unicast_packet(sc, size, sn->rates[ndx3].rix,
459 						short_tries,
460 						MIN(tries3 + tries_so_far, tries) - tries_so_far - 1);
461 	}
462 	if (sn->stats[size_bin][ndx0].total_packets < (100 / (100 - ssc->ath_smoothing_rate))) {
463 		/* just average the first few packets */
464 		int avg_tx = sn->stats[size_bin][ndx0].average_tx_time;
465 		int packets = sn->stats[size_bin][ndx0].total_packets;
466 		sn->stats[size_bin][ndx0].average_tx_time = (tt+(avg_tx*packets))/(packets+1);
467 	} else {
468 		/* use a ewma */
469 		sn->stats[size_bin][ndx0].average_tx_time =
470 			((sn->stats[size_bin][ndx0].average_tx_time * ssc->ath_smoothing_rate) +
471 			 (tt * (100 - ssc->ath_smoothing_rate))) / 100;
472 	}
473 
474 	if (status) {
475 		int y;
476 		sn->stats[size_bin][ndx0].successive_failures++;
477 		for (y = size_bin+1; y < NUM_PACKET_SIZE_BINS; y++) {
478 			/* also say larger packets failed since we
479 			 * assume if a small packet fails at a lower
480 			 * bit-rate then a larger one will also.
481 			 */
482 			sn->stats[y][ndx0].successive_failures++;
483 			sn->stats[y][ndx0].last_tx = ticks;
484 			sn->stats[y][ndx0].tries += tries;
485 			sn->stats[y][ndx0].total_packets++;
486 		}
487 	} else {
488 		sn->stats[size_bin][ndx0].packets_acked++;
489 		sn->stats[size_bin][ndx0].successive_failures = 0;
490 	}
491 	sn->stats[size_bin][ndx0].tries += tries;
492 	sn->stats[size_bin][ndx0].last_tx = ticks;
493 	sn->stats[size_bin][ndx0].total_packets++;
494 
495 
496 	if (ndx0 == sn->current_sample_ndx[size_bin]) {
497 		DPRINTF(sc, ATH_DEBUG_RATE,
498 "%s: %s size %d %s sample rate %d tries (%d/%d) tt %d avg_tt (%d/%d)\n",
499 		    __func__, ether_sprintf(an->an_node.ni_macaddr),
500 		    size,
501 		    status ? "FAIL" : "OK",
502 		    rate, short_tries, tries, tt,
503 		    sn->stats[size_bin][ndx0].average_tx_time,
504 		    sn->stats[size_bin][ndx0].perfect_tx_time);
505 		sn->sample_tt[size_bin] = tt;
506 		sn->current_sample_ndx[size_bin] = -1;
507 	}
508 }
509 
510 void
511 ath_rate_tx_complete(struct ath_softc *sc, struct ath_node *an,
512 	const struct ath_buf *bf)
513 {
514 	struct ieee80211com *ic = &sc->sc_ic;
515 	struct sample_node *sn = ATH_NODE_SAMPLE(an);
516 	const struct ath_tx_status *ts = &bf->bf_status.ds_txstat;
517 	const struct ath_desc *ds0 = &bf->bf_desc[0];
518 	int final_rate, short_tries, long_tries, frame_size;
519 	int mrr;
520 
521 	final_rate = sc->sc_hwmap[ts->ts_rate &~ HAL_TXSTAT_ALTRATE].ieeerate;
522 	short_tries = ts->ts_shortretry;
523 	long_tries = ts->ts_longretry + 1;
524 	frame_size = ds0->ds_ctl0 & 0x0fff; /* low-order 12 bits of ds_ctl0 */
525 	if (frame_size == 0)		    /* NB: should not happen */
526 		frame_size = 1500;
527 
528 	if (sn->num_rates <= 0) {
529 		DPRINTF(sc, ATH_DEBUG_RATE,
530 		    "%s: %s size %d %s rate/try %d/%d no rates yet\n",
531 		    __func__, ether_sprintf(an->an_node.ni_macaddr),
532 		    bin_to_size(size_to_bin(frame_size)),
533 		    ts->ts_status ? "FAIL" : "OK",
534 		    short_tries, long_tries);
535 		return;
536 	}
537 	mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT);
538 	if (!mrr || !(ts->ts_rate & HAL_TXSTAT_ALTRATE)) {
539 		int ndx = rate_to_ndx(sn, final_rate);
540 
541 		/*
542 		 * Only one rate was used; optimize work.
543 		 */
544 		DPRINTF(sc, ATH_DEBUG_RATE,
545 		    "%s: %s size %d %s rate/try %d/%d/%d\n",
546 		     __func__, ether_sprintf(an->an_node.ni_macaddr),
547 		     bin_to_size(size_to_bin(frame_size)),
548 		     ts->ts_status ? "FAIL" : "OK",
549 		     final_rate, short_tries, long_tries);
550 		update_stats(sc, an, frame_size,
551 			     ndx, long_tries,
552 			     0, 0,
553 			     0, 0,
554 			     0, 0,
555 			     short_tries, long_tries, ts->ts_status);
556 	} else {
557 		int hwrate0, rate0, tries0, ndx0;
558 		int hwrate1, rate1, tries1, ndx1;
559 		int hwrate2, rate2, tries2, ndx2;
560 		int hwrate3, rate3, tries3, ndx3;
561 		int finalTSIdx = ts->ts_finaltsi;
562 
563 		/*
564 		 * Process intermediate rates that failed.
565 		 */
566 		if (sc->sc_ah->ah_magic != 0x20065416) {
567 			hwrate0 = MS(ds0->ds_ctl3, AR_XmitRate0);
568 			hwrate1 = MS(ds0->ds_ctl3, AR_XmitRate1);
569 			hwrate2 = MS(ds0->ds_ctl3, AR_XmitRate2);
570 			hwrate3 = MS(ds0->ds_ctl3, AR_XmitRate3);
571 		} else {
572 			hwrate0 = MS(ds0->ds_ctl3, AR5416_XmitRate0);
573 			hwrate1 = MS(ds0->ds_ctl3, AR5416_XmitRate1);
574 			hwrate2 = MS(ds0->ds_ctl3, AR5416_XmitRate2);
575 			hwrate3 = MS(ds0->ds_ctl3, AR5416_XmitRate3);
576 		}
577 
578 		rate0 = sc->sc_hwmap[hwrate0].ieeerate;
579 		tries0 = MS(ds0->ds_ctl2, AR_XmitDataTries0);
580 		ndx0 = rate_to_ndx(sn, rate0);
581 
582 		rate1 = sc->sc_hwmap[hwrate1].ieeerate;
583 		tries1 = MS(ds0->ds_ctl2, AR_XmitDataTries1);
584 		ndx1 = rate_to_ndx(sn, rate1);
585 
586 		rate2 = sc->sc_hwmap[hwrate2].ieeerate;
587 		tries2 = MS(ds0->ds_ctl2, AR_XmitDataTries2);
588 		ndx2 = rate_to_ndx(sn, rate2);
589 
590 		rate3 = sc->sc_hwmap[hwrate3].ieeerate;
591 		tries3 = MS(ds0->ds_ctl2, AR_XmitDataTries3);
592 		ndx3 = rate_to_ndx(sn, rate3);
593 
594 		DPRINTF(sc, ATH_DEBUG_RATE,
595 "%s: %s size %d finaltsidx %d tries %d %s rate/try [%d/%d %d/%d %d/%d %d/%d]\n",
596 		     __func__, ether_sprintf(an->an_node.ni_macaddr),
597 		     bin_to_size(size_to_bin(frame_size)),
598 		     finalTSIdx,
599 		     long_tries,
600 		     ts->ts_status ? "FAIL" : "OK",
601 		     rate0, tries0,
602 		     rate1, tries1,
603 		     rate2, tries2,
604 		     rate3, tries3);
605 
606 		/*
607 		 * NB: series > 0 are not penalized for failure
608 		 * based on the try counts under the assumption
609 		 * that losses are often bursty and since we
610 		 * sample higher rates 1 try at a time doing so
611 		 * may unfairly penalize them.
612 		 */
613 		if (tries0) {
614 			update_stats(sc, an, frame_size,
615 				     ndx0, tries0,
616 				     ndx1, tries1,
617 				     ndx2, tries2,
618 				     ndx3, tries3,
619 				     short_tries, long_tries,
620 				     long_tries > tries0);
621 			long_tries -= tries0;
622 		}
623 
624 		if (tries1 && finalTSIdx > 0) {
625 			update_stats(sc, an, frame_size,
626 				     ndx1, tries1,
627 				     ndx2, tries2,
628 				     ndx3, tries3,
629 				     0, 0,
630 				     short_tries, long_tries,
631 				     ts->ts_status);
632 			long_tries -= tries1;
633 		}
634 
635 		if (tries2 && finalTSIdx > 1) {
636 			update_stats(sc, an, frame_size,
637 				     ndx2, tries2,
638 				     ndx3, tries3,
639 				     0, 0,
640 				     0, 0,
641 				     short_tries, long_tries,
642 				     ts->ts_status);
643 			long_tries -= tries2;
644 		}
645 
646 		if (tries3 && finalTSIdx > 2) {
647 			update_stats(sc, an, frame_size,
648 				     ndx3, tries3,
649 				     0, 0,
650 				     0, 0,
651 				     0, 0,
652 				     short_tries, long_tries,
653 				     ts->ts_status);
654 		}
655 	}
656 }
657 
658 void
659 ath_rate_newassoc(struct ath_softc *sc, struct ath_node *an, int isnew)
660 {
661 	DPRINTF(sc, ATH_DEBUG_NODE, "%s: %s isnew %d\n", __func__,
662 	     ether_sprintf(an->an_node.ni_macaddr), isnew);
663 	if (isnew)
664 		ath_rate_ctl_reset(sc, &an->an_node);
665 }
666 
667 /*
668  * Initialize the tables for a node.
669  */
670 static void
671 ath_rate_ctl_reset(struct ath_softc *sc, struct ieee80211_node *ni)
672 {
673 #define	RATE(_ix)	(ni->ni_rates.rs_rates[(_ix)] & IEEE80211_RATE_VAL)
674 	struct ieee80211com *ic = &sc->sc_ic;
675 	struct ath_node *an = ATH_NODE(ni);
676 	struct sample_node *sn = ATH_NODE_SAMPLE(an);
677 	const HAL_RATE_TABLE *rt = sc->sc_currates;
678 	int x, y, srate;
679 
680 	KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode));
681         sn->static_rate_ndx = -1;
682 	if (ic->ic_fixed_rate != IEEE80211_FIXED_RATE_NONE) {
683 		/*
684 		 * A fixed rate is to be used; ic_fixed_rate is the
685 		 * IEEE code for this rate (sans basic bit).  Convert this
686 		 * to the index into the negotiated rate set for
687 		 * the node.
688 		 */
689 		/* NB: the rate set is assumed sorted */
690 		srate = ni->ni_rates.rs_nrates - 1;
691 		for (; srate >= 0 && RATE(srate) != ic->ic_fixed_rate; srate--)
692 			;
693 		/*
694 		 * The fixed rate may not be available due to races
695 		 * and mode settings.  Also orphaned nodes created in
696 		 * adhoc mode may not have any rate set so this lookup
697 		 * can fail.
698 		 */
699 		if (srate >= 0)
700 			sn->static_rate_ndx = srate;
701 	}
702 
703         DPRINTF(sc, ATH_DEBUG_RATE, "%s: %s size 1600 rate/tt",
704 	    __func__, ether_sprintf(ni->ni_macaddr));
705 
706 	sn->num_rates = ni->ni_rates.rs_nrates;
707         for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
708 		sn->rates[x].rate = ni->ni_rates.rs_rates[x] & IEEE80211_RATE_VAL;
709 		sn->rates[x].rix = sc->sc_rixmap[sn->rates[x].rate];
710 		if (sn->rates[x].rix == 0xff) {
711 			DPRINTF(sc, ATH_DEBUG_RATE,
712 			    "%s: ignore bogus rix at %d\n", __func__, x);
713 			continue;
714 		}
715 		sn->rates[x].rateCode = rt->info[sn->rates[x].rix].rateCode;
716 		sn->rates[x].shortPreambleRateCode =
717 			rt->info[sn->rates[x].rix].rateCode |
718 			rt->info[sn->rates[x].rix].shortPreamble;
719 
720 		DPRINTF(sc, ATH_DEBUG_RATE, " %d/%d", sn->rates[x].rate,
721 		    calc_usecs_unicast_packet(sc, 1600, sn->rates[x].rix, 0,0));
722 	}
723 	DPRINTF(sc, ATH_DEBUG_RATE, "%s\n", "");
724 
725 	/* set the visible bit-rate to the lowest one available */
726 	ni->ni_txrate = 0;
727 	sn->num_rates = ni->ni_rates.rs_nrates;
728 
729 	for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) {
730 		int size = bin_to_size(y);
731 		int ndx = 0;
732 		sn->packets_sent[y] = 0;
733 		sn->current_sample_ndx[y] = -1;
734 		sn->last_sample_ndx[y] = 0;
735 
736 		for (x = 0; x < ni->ni_rates.rs_nrates; x++) {
737 			sn->stats[y][x].successive_failures = 0;
738 			sn->stats[y][x].tries = 0;
739 			sn->stats[y][x].total_packets = 0;
740 			sn->stats[y][x].packets_acked = 0;
741 			sn->stats[y][x].last_tx = 0;
742 
743 			sn->stats[y][x].perfect_tx_time =
744 				calc_usecs_unicast_packet(sc, size,
745 							  sn->rates[x].rix,
746 							  0, 0);
747 			sn->stats[y][x].average_tx_time = sn->stats[y][x].perfect_tx_time;
748 		}
749 
750 		/* set the initial rate */
751 		for (ndx = sn->num_rates-1; ndx > 0; ndx--) {
752 			if (sn->rates[ndx].rate <= 72) {
753 				break;
754 			}
755 		}
756 		sn->current_rate[y] = ndx;
757 	}
758 
759 	DPRINTF(sc, ATH_DEBUG_RATE,
760 	    "%s: %s %d rates %d%sMbps (%dus)- %d%sMbps (%dus)\n",
761 	    __func__, ether_sprintf(ni->ni_macaddr),
762 	    sn->num_rates,
763 	    sn->rates[0].rate/2, sn->rates[0].rate % 0x1 ? ".5" : "",
764 	    sn->stats[1][0].perfect_tx_time,
765 	    sn->rates[sn->num_rates-1].rate/2,
766 		sn->rates[sn->num_rates-1].rate % 0x1 ? ".5" : "",
767 	    sn->stats[1][sn->num_rates-1].perfect_tx_time
768 	);
769 
770         if (sn->static_rate_ndx != -1)
771 		ni->ni_txrate = sn->static_rate_ndx;
772 	else
773 		ni->ni_txrate = sn->current_rate[0];
774 #undef RATE
775 }
776 
777 static void
778 rate_cb(void *arg, struct ieee80211_node *ni)
779 {
780 	struct ath_softc *sc = arg;
781 
782 	ath_rate_newassoc(sc, ATH_NODE(ni), 1);
783 }
784 
785 /*
786  * Reset the rate control state for each 802.11 state transition.
787  */
788 void
789 ath_rate_newstate(struct ath_softc *sc, enum ieee80211_state state)
790 {
791 	struct ieee80211com *ic = &sc->sc_ic;
792 
793 	if (state == IEEE80211_S_RUN) {
794 		if (ic->ic_opmode != IEEE80211_M_STA) {
795 			/*
796 			 * Sync rates for associated stations and neighbors.
797 			 */
798 			ieee80211_iterate_nodes(&ic->ic_sta, rate_cb, sc);
799 		}
800 		ath_rate_newassoc(sc, ATH_NODE(ic->ic_bss), 1);
801 	}
802 }
803 
804 static void
805 ath_rate_sysctlattach(struct ath_softc *sc, struct sample_softc *osc)
806 {
807 	struct sysctl_ctx_list *ctx = device_get_sysctl_ctx(sc->sc_dev);
808 	struct sysctl_oid *tree = device_get_sysctl_tree(sc->sc_dev);
809 
810 	/* XXX bounds check [0..100] */
811 	SYSCTL_ADD_INT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
812 		"smoothing_rate", CTLFLAG_RW, &osc->ath_smoothing_rate, 0,
813 		"rate control: retry threshold to credit rate raise (%%)");
814 	/* XXX bounds check [2..100] */
815 	SYSCTL_ADD_INT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
816 		"sample_rate", CTLFLAG_RW, &osc->ath_sample_rate,0,
817 		"rate control: # good periods before raising rate");
818 }
819 
820 struct ath_ratectrl *
821 ath_rate_attach(struct ath_softc *sc)
822 {
823 	struct sample_softc *osc;
824 
825 	DPRINTF(sc, ATH_DEBUG_ANY, "%s:\n", __func__);
826 	osc = malloc(sizeof(struct sample_softc), M_DEVBUF, M_NOWAIT|M_ZERO);
827 	if (osc == NULL)
828 		return NULL;
829 	osc->arc.arc_space = sizeof(struct sample_node);
830 	osc->ath_smoothing_rate = 95;	/* ewma percentage (out of 100) */
831 	osc->ath_sample_rate = 10;	/* send a different bit-rate 1/X packets */
832 	ath_rate_sysctlattach(sc, osc);
833 	return &osc->arc;
834 }
835 
836 void
837 ath_rate_detach(struct ath_ratectrl *arc)
838 {
839 	struct sample_softc *osc = (struct sample_softc *) arc;
840 
841 	free(osc, M_DEVBUF);
842 }
843 
844 /*
845  * Module glue.
846  */
847 static int
848 sample_modevent(module_t mod, int type, void *unused)
849 {
850 	switch (type) {
851 	case MOD_LOAD:
852 		if (bootverbose)
853 			printf("ath_rate: version 1.2 <SampleRate bit-rate selection algorithm>\n");
854 		return 0;
855 	case MOD_UNLOAD:
856 		return 0;
857 	}
858 	return EINVAL;
859 }
860 
861 static moduledata_t sample_mod = {
862 	"ath_rate",
863 	sample_modevent,
864 	0
865 };
866 DECLARE_MODULE(ath_rate, sample_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
867 MODULE_VERSION(ath_rate, 1);
868 MODULE_DEPEND(ath_rate, ath_hal, 1, 1, 1);	/* Atheros HAL */
869 MODULE_DEPEND(ath_rate, wlan, 1, 1, 1);
870