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