2 * Copyright (C) 2008 Felix Fietkau <nbd@openwrt.org>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation.
9 * Copyright (C) 2005-2007 Derek Smithies <derek@indranet.co.nz>
10 * Sponsored by Indranet Technologies Ltd
13 * Copyright (c) 2005 John Bicket
14 * All rights reserved.
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
19 * 1. Redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer,
21 * without modification.
22 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
23 * similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
24 * redistribution must be conditioned upon including a substantially
25 * similar Disclaimer requirement for further binary redistribution.
26 * 3. Neither the names of the above-listed copyright holders nor the names
27 * of any contributors may be used to endorse or promote products derived
28 * from this software without specific prior written permission.
30 * Alternatively, this software may be distributed under the terms of the
31 * GNU General Public License ("GPL") version 2 as published by the Free
32 * Software Foundation.
35 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37 * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
38 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
39 * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
40 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
41 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
42 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
43 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
44 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
45 * THE POSSIBILITY OF SUCH DAMAGES.
47 #include <linux/netdevice.h>
48 #include <linux/types.h>
49 #include <linux/skbuff.h>
50 #include <linux/debugfs.h>
51 #include <linux/random.h>
52 #include <linux/ieee80211.h>
53 #include <linux/slab.h>
54 #include <net/mac80211.h>
56 #include "rc80211_minstrel.h"
58 #define SAMPLE_TBL(_mi, _idx, _col) \
59 _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
61 /* convert mac80211 rate index to local array index */
63 rix_to_ndx(struct minstrel_sta_info
*mi
, int rix
)
66 for (i
= rix
; i
>= 0; i
--)
67 if (mi
->r
[i
].rix
== rix
)
72 /* find & sort topmost throughput rates */
74 minstrel_sort_best_tp_rates(struct minstrel_sta_info
*mi
, int i
, u8
*tp_list
)
76 int j
= MAX_THR_RATES
;
78 while (j
> 0 && mi
->r
[i
].cur_tp
> mi
->r
[tp_list
[j
- 1]].cur_tp
)
80 if (j
< MAX_THR_RATES
- 1)
81 memmove(&tp_list
[j
+ 1], &tp_list
[j
], MAX_THR_RATES
- (j
+ 1));
82 if (j
< MAX_THR_RATES
)
87 minstrel_update_stats(struct minstrel_priv
*mp
, struct minstrel_sta_info
*mi
)
89 u8 tmp_tp_rate
[MAX_THR_RATES
];
94 for (i
=0; i
< MAX_THR_RATES
; i
++)
97 for (i
= 0; i
< mi
->n_rates
; i
++) {
98 struct minstrel_rate
*mr
= &mi
->r
[i
];
100 usecs
= mr
->perfect_tx_time
;
104 if (unlikely(mr
->attempts
> 0)) {
105 mr
->sample_skipped
= 0;
106 mr
->cur_prob
= MINSTREL_FRAC(mr
->success
, mr
->attempts
);
107 mr
->succ_hist
+= mr
->success
;
108 mr
->att_hist
+= mr
->attempts
;
109 mr
->probability
= minstrel_ewma(mr
->probability
,
113 mr
->sample_skipped
++;
115 mr
->last_success
= mr
->success
;
116 mr
->last_attempts
= mr
->attempts
;
120 /* Update throughput per rate, reset thr. below 10% success */
121 if (mr
->probability
< MINSTREL_FRAC(10, 100))
124 mr
->cur_tp
= mr
->probability
* (1000000 / usecs
);
126 /* Sample less often below the 10% chance of success.
127 * Sample less often above the 95% chance of success. */
128 if (mr
->probability
> MINSTREL_FRAC(95, 100) ||
129 mr
->probability
< MINSTREL_FRAC(10, 100)) {
130 mr
->adjusted_retry_count
= mr
->retry_count
>> 1;
131 if (mr
->adjusted_retry_count
> 2)
132 mr
->adjusted_retry_count
= 2;
133 mr
->sample_limit
= 4;
135 mr
->sample_limit
= -1;
136 mr
->adjusted_retry_count
= mr
->retry_count
;
138 if (!mr
->adjusted_retry_count
)
139 mr
->adjusted_retry_count
= 2;
141 minstrel_sort_best_tp_rates(mi
, i
, tmp_tp_rate
);
143 /* To determine the most robust rate (max_prob_rate) used at
144 * 3rd mmr stage we distinct between two cases:
145 * (1) if any success probabilitiy >= 95%, out of those rates
146 * choose the maximum throughput rate as max_prob_rate
147 * (2) if all success probabilities < 95%, the rate with
148 * highest success probability is choosen as max_prob_rate */
149 if (mr
->probability
>= MINSTREL_FRAC(95,100)) {
150 if (mr
->cur_tp
>= mi
->r
[tmp_prob_rate
].cur_tp
)
153 if (mr
->probability
>= mi
->r
[tmp_prob_rate
].probability
)
158 /* Assign the new rate set */
159 memcpy(mi
->max_tp_rate
, tmp_tp_rate
, sizeof(mi
->max_tp_rate
));
160 mi
->max_prob_rate
= tmp_prob_rate
;
162 /* Reset update timer */
163 mi
->stats_update
= jiffies
;
167 minstrel_tx_status(void *priv
, struct ieee80211_supported_band
*sband
,
168 struct ieee80211_sta
*sta
, void *priv_sta
,
171 struct minstrel_priv
*mp
= priv
;
172 struct minstrel_sta_info
*mi
= priv_sta
;
173 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
174 struct ieee80211_tx_rate
*ar
= info
->status
.rates
;
178 success
= !!(info
->flags
& IEEE80211_TX_STAT_ACK
);
180 for (i
= 0; i
< IEEE80211_TX_MAX_RATES
; i
++) {
184 ndx
= rix_to_ndx(mi
, ar
[i
].idx
);
188 mi
->r
[ndx
].attempts
+= ar
[i
].count
;
190 if ((i
!= IEEE80211_TX_MAX_RATES
- 1) && (ar
[i
+ 1].idx
< 0))
191 mi
->r
[ndx
].success
+= success
;
194 if ((info
->flags
& IEEE80211_TX_CTL_RATE_CTRL_PROBE
) && (i
>= 0))
197 if (mi
->sample_deferred
> 0)
198 mi
->sample_deferred
--;
200 if (time_after(jiffies
, mi
->stats_update
+
201 (mp
->update_interval
* HZ
) / 1000))
202 minstrel_update_stats(mp
, mi
);
206 static inline unsigned int
207 minstrel_get_retry_count(struct minstrel_rate
*mr
,
208 struct ieee80211_tx_info
*info
)
210 unsigned int retry
= mr
->adjusted_retry_count
;
212 if (info
->control
.use_rts
)
213 retry
= max(2U, min(mr
->retry_count_rtscts
, retry
));
214 else if (info
->control
.use_cts_prot
)
215 retry
= max(2U, min(mr
->retry_count_cts
, retry
));
221 minstrel_get_next_sample(struct minstrel_sta_info
*mi
)
223 unsigned int sample_ndx
;
224 sample_ndx
= SAMPLE_TBL(mi
, mi
->sample_row
, mi
->sample_column
);
226 if ((int) mi
->sample_row
>= mi
->n_rates
) {
229 if (mi
->sample_column
>= SAMPLE_COLUMNS
)
230 mi
->sample_column
= 0;
236 minstrel_get_rate(void *priv
, struct ieee80211_sta
*sta
,
237 void *priv_sta
, struct ieee80211_tx_rate_control
*txrc
)
239 struct sk_buff
*skb
= txrc
->skb
;
240 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
241 struct minstrel_sta_info
*mi
= priv_sta
;
242 struct minstrel_priv
*mp
= priv
;
243 struct ieee80211_tx_rate
*ar
= info
->control
.rates
;
244 unsigned int ndx
, sample_ndx
= 0;
246 bool indirect_rate_sampling
= false;
247 bool rate_sampling
= false;
252 /* management/no-ack frames do not use rate control */
253 if (rate_control_send_low(sta
, priv_sta
, txrc
))
256 /* check multi-rate-retry capabilities & adjust lookaround_rate */
257 mrr_capable
= mp
->has_mrr
&&
259 !txrc
->bss_conf
->use_cts_prot
;
261 sampling_ratio
= mp
->lookaround_rate_mrr
;
263 sampling_ratio
= mp
->lookaround_rate
;
265 /* init rateindex [ndx] with max throughput rate */
266 ndx
= mi
->max_tp_rate
[0];
268 /* increase sum packet counter */
271 delta
= (mi
->packet_count
* sampling_ratio
/ 100) -
272 (mi
->sample_count
+ mi
->sample_deferred
/ 2);
274 /* delta > 0: sampling required */
275 if ((delta
> 0) && (mrr_capable
|| !mi
->prev_sample
)) {
276 struct minstrel_rate
*msr
;
277 if (mi
->packet_count
>= 10000) {
278 mi
->sample_deferred
= 0;
279 mi
->sample_count
= 0;
280 mi
->packet_count
= 0;
281 } else if (delta
> mi
->n_rates
* 2) {
282 /* With multi-rate retry, not every planned sample
283 * attempt actually gets used, due to the way the retry
284 * chain is set up - [max_tp,sample,prob,lowest] for
285 * sample_rate < max_tp.
287 * If there's too much sampling backlog and the link
288 * starts getting worse, minstrel would start bursting
289 * out lots of sampling frames, which would result
290 * in a large throughput loss. */
291 mi
->sample_count
+= (delta
- mi
->n_rates
* 2);
294 /* get next random rate sample */
295 sample_ndx
= minstrel_get_next_sample(mi
);
296 msr
= &mi
->r
[sample_ndx
];
297 rate_sampling
= true;
299 /* Decide if direct ( 1st mrr stage) or indirect (2nd mrr stage)
300 * rate sampling method should be used.
301 * Respect such rates that are not sampled for 20 interations.
304 msr
->perfect_tx_time
> mi
->r
[ndx
].perfect_tx_time
&&
305 msr
->sample_skipped
< 20)
306 indirect_rate_sampling
= true;
308 if (!indirect_rate_sampling
) {
309 if (msr
->sample_limit
!= 0) {
312 if (msr
->sample_limit
> 0)
315 rate_sampling
= false;
317 /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
318 * packets that have the sampling rate deferred to the
319 * second MRR stage. Increase the sample counter only
320 * if the deferred sample rate was actually used.
321 * Use the sample_deferred counter to make sure that
322 * the sampling is not done in large bursts */
323 info
->flags
|= IEEE80211_TX_CTL_RATE_CTRL_PROBE
;
324 mi
->sample_deferred
++;
327 mi
->prev_sample
= rate_sampling
;
329 /* If we're not using MRR and the sampling rate already
330 * has a probability of >95%, we shouldn't be attempting
331 * to use it, as this only wastes precious airtime */
332 if (!mrr_capable
&& rate_sampling
&&
333 (mi
->r
[ndx
].probability
> MINSTREL_FRAC(95, 100)))
334 ndx
= mi
->max_tp_rate
[0];
336 /* mrr setup for 1st stage */
337 ar
[0].idx
= mi
->r
[ndx
].rix
;
338 ar
[0].count
= minstrel_get_retry_count(&mi
->r
[ndx
], info
);
340 /* non mrr setup for 2nd stage */
343 ar
[0].count
= mp
->max_retry
;
344 ar
[1].idx
= mi
->lowest_rix
;
345 ar
[1].count
= mp
->max_retry
;
349 /* mrr setup for 2nd stage */
351 if (indirect_rate_sampling
)
352 mrr_ndx
[0] = sample_ndx
;
354 mrr_ndx
[0] = mi
->max_tp_rate
[0];
356 mrr_ndx
[0] = mi
->max_tp_rate
[1];
359 /* mrr setup for 3rd & 4th stage */
360 mrr_ndx
[1] = mi
->max_prob_rate
;
362 for (i
= 1; i
< 4; i
++) {
363 ar
[i
].idx
= mi
->r
[mrr_ndx
[i
- 1]].rix
;
364 ar
[i
].count
= mi
->r
[mrr_ndx
[i
- 1]].adjusted_retry_count
;
370 calc_rate_durations(enum ieee80211_band band
,
371 struct minstrel_rate
*d
,
372 struct ieee80211_rate
*rate
)
374 int erp
= !!(rate
->flags
& IEEE80211_RATE_ERP_G
);
376 d
->perfect_tx_time
= ieee80211_frame_duration(band
, 1200,
377 rate
->bitrate
, erp
, 1);
378 d
->ack_time
= ieee80211_frame_duration(band
, 10,
379 rate
->bitrate
, erp
, 1);
383 init_sample_table(struct minstrel_sta_info
*mi
)
385 unsigned int i
, col
, new_idx
;
388 mi
->sample_column
= 0;
390 memset(mi
->sample_table
, 0xff, SAMPLE_COLUMNS
* mi
->n_rates
);
392 for (col
= 0; col
< SAMPLE_COLUMNS
; col
++) {
393 for (i
= 0; i
< mi
->n_rates
; i
++) {
394 get_random_bytes(rnd
, sizeof(rnd
));
395 new_idx
= (i
+ rnd
[i
& 7]) % mi
->n_rates
;
397 while (SAMPLE_TBL(mi
, new_idx
, col
) != 0xff)
398 new_idx
= (new_idx
+ 1) % mi
->n_rates
;
400 SAMPLE_TBL(mi
, new_idx
, col
) = i
;
406 minstrel_rate_init(void *priv
, struct ieee80211_supported_band
*sband
,
407 struct ieee80211_sta
*sta
, void *priv_sta
)
409 struct minstrel_sta_info
*mi
= priv_sta
;
410 struct minstrel_priv
*mp
= priv
;
411 struct ieee80211_rate
*ctl_rate
;
412 unsigned int i
, n
= 0;
413 unsigned int t_slot
= 9; /* FIXME: get real slot time */
415 mi
->lowest_rix
= rate_lowest_index(sband
, sta
);
416 ctl_rate
= &sband
->bitrates
[mi
->lowest_rix
];
417 mi
->sp_ack_dur
= ieee80211_frame_duration(sband
->band
, 10,
419 !!(ctl_rate
->flags
& IEEE80211_RATE_ERP_G
), 1);
421 for (i
= 0; i
< sband
->n_bitrates
; i
++) {
422 struct minstrel_rate
*mr
= &mi
->r
[n
];
423 unsigned int tx_time
= 0, tx_time_cts
= 0, tx_time_rtscts
= 0;
424 unsigned int tx_time_single
;
425 unsigned int cw
= mp
->cw_min
;
427 if (!rate_supported(sta
, sband
->band
, i
))
430 memset(mr
, 0, sizeof(*mr
));
433 mr
->bitrate
= sband
->bitrates
[i
].bitrate
/ 5;
434 calc_rate_durations(sband
->band
, mr
, &sband
->bitrates
[i
]);
436 /* calculate maximum number of retransmissions before
437 * fallback (based on maximum segment size) */
438 mr
->sample_limit
= -1;
440 mr
->retry_count_cts
= 1;
441 mr
->retry_count_rtscts
= 1;
442 tx_time
= mr
->perfect_tx_time
+ mi
->sp_ack_dur
;
444 /* add one retransmission */
445 tx_time_single
= mr
->ack_time
+ mr
->perfect_tx_time
;
447 /* contention window */
448 tx_time_single
+= (t_slot
* cw
) >> 1;
449 cw
= min((cw
<< 1) | 1, mp
->cw_max
);
451 tx_time
+= tx_time_single
;
452 tx_time_cts
+= tx_time_single
+ mi
->sp_ack_dur
;
453 tx_time_rtscts
+= tx_time_single
+ 2 * mi
->sp_ack_dur
;
454 if ((tx_time_cts
< mp
->segment_size
) &&
455 (mr
->retry_count_cts
< mp
->max_retry
))
456 mr
->retry_count_cts
++;
457 if ((tx_time_rtscts
< mp
->segment_size
) &&
458 (mr
->retry_count_rtscts
< mp
->max_retry
))
459 mr
->retry_count_rtscts
++;
460 } while ((tx_time
< mp
->segment_size
) &&
461 (++mr
->retry_count
< mp
->max_retry
));
462 mr
->adjusted_retry_count
= mr
->retry_count
;
463 if (!(sband
->bitrates
[i
].flags
& IEEE80211_RATE_ERP_G
))
464 mr
->retry_count_cts
= mr
->retry_count
;
467 for (i
= n
; i
< sband
->n_bitrates
; i
++) {
468 struct minstrel_rate
*mr
= &mi
->r
[i
];
473 mi
->stats_update
= jiffies
;
475 init_sample_table(mi
);
479 minstrel_alloc_sta(void *priv
, struct ieee80211_sta
*sta
, gfp_t gfp
)
481 struct ieee80211_supported_band
*sband
;
482 struct minstrel_sta_info
*mi
;
483 struct minstrel_priv
*mp
= priv
;
484 struct ieee80211_hw
*hw
= mp
->hw
;
488 mi
= kzalloc(sizeof(struct minstrel_sta_info
), gfp
);
492 for (i
= 0; i
< IEEE80211_NUM_BANDS
; i
++) {
493 sband
= hw
->wiphy
->bands
[i
];
494 if (sband
&& sband
->n_bitrates
> max_rates
)
495 max_rates
= sband
->n_bitrates
;
498 mi
->r
= kzalloc(sizeof(struct minstrel_rate
) * max_rates
, gfp
);
502 mi
->sample_table
= kmalloc(SAMPLE_COLUMNS
* max_rates
, gfp
);
503 if (!mi
->sample_table
)
506 mi
->stats_update
= jiffies
;
517 minstrel_free_sta(void *priv
, struct ieee80211_sta
*sta
, void *priv_sta
)
519 struct minstrel_sta_info
*mi
= priv_sta
;
521 kfree(mi
->sample_table
);
527 minstrel_init_cck_rates(struct minstrel_priv
*mp
)
529 static const int bitrates
[4] = { 10, 20, 55, 110 };
530 struct ieee80211_supported_band
*sband
;
533 sband
= mp
->hw
->wiphy
->bands
[IEEE80211_BAND_2GHZ
];
537 for (i
= 0, j
= 0; i
< sband
->n_bitrates
; i
++) {
538 struct ieee80211_rate
*rate
= &sband
->bitrates
[i
];
540 if (rate
->flags
& IEEE80211_RATE_ERP_G
)
543 for (j
= 0; j
< ARRAY_SIZE(bitrates
); j
++) {
544 if (rate
->bitrate
!= bitrates
[j
])
547 mp
->cck_rates
[j
] = i
;
554 minstrel_alloc(struct ieee80211_hw
*hw
, struct dentry
*debugfsdir
)
556 struct minstrel_priv
*mp
;
558 mp
= kzalloc(sizeof(struct minstrel_priv
), GFP_ATOMIC
);
562 /* contention window settings
563 * Just an approximation. Using the per-queue values would complicate
564 * the calculations and is probably unnecessary */
568 /* number of packets (in %) to use for sampling other rates
569 * sample less often for non-mrr packets, because the overhead
570 * is much higher than with mrr */
571 mp
->lookaround_rate
= 5;
572 mp
->lookaround_rate_mrr
= 10;
574 /* maximum time that the hw is allowed to stay in one MRR segment */
575 mp
->segment_size
= 6000;
577 if (hw
->max_rate_tries
> 0)
578 mp
->max_retry
= hw
->max_rate_tries
;
580 /* safe default, does not necessarily have to match hw properties */
583 if (hw
->max_rates
>= 4)
587 mp
->update_interval
= 100;
589 #ifdef CONFIG_MAC80211_DEBUGFS
590 mp
->fixed_rate_idx
= (u32
) -1;
591 mp
->dbg_fixed_rate
= debugfs_create_u32("fixed_rate_idx",
592 S_IRUGO
| S_IWUGO
, debugfsdir
, &mp
->fixed_rate_idx
);
595 minstrel_init_cck_rates(mp
);
601 minstrel_free(void *priv
)
603 #ifdef CONFIG_MAC80211_DEBUGFS
604 debugfs_remove(((struct minstrel_priv
*)priv
)->dbg_fixed_rate
);
609 struct rate_control_ops mac80211_minstrel
= {
611 .tx_status
= minstrel_tx_status
,
612 .get_rate
= minstrel_get_rate
,
613 .rate_init
= minstrel_rate_init
,
614 .alloc
= minstrel_alloc
,
615 .free
= minstrel_free
,
616 .alloc_sta
= minstrel_alloc_sta
,
617 .free_sta
= minstrel_free_sta
,
618 #ifdef CONFIG_MAC80211_DEBUGFS
619 .add_sta_debugfs
= minstrel_add_sta_debugfs
,
620 .remove_sta_debugfs
= minstrel_remove_sta_debugfs
,
625 rc80211_minstrel_init(void)
627 return ieee80211_rate_control_register(&mac80211_minstrel
);
631 rc80211_minstrel_exit(void)
633 ieee80211_rate_control_unregister(&mac80211_minstrel
);