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 <net/mac80211.h>
56 #include "rc80211_minstrel.h"
58 #define SAMPLE_COLUMNS 10
59 #define SAMPLE_TBL(_mi, _idx, _col) \
60 _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
62 /* convert mac80211 rate index to local array index */
64 rix_to_ndx(struct minstrel_sta_info
*mi
, int rix
)
67 for (i
= rix
; i
>= 0; i
--)
68 if (mi
->r
[i
].rix
== rix
)
75 minstrel_update_stats(struct minstrel_priv
*mp
, struct minstrel_sta_info
*mi
)
77 u32 max_tp
= 0, index_max_tp
= 0, index_max_tp2
= 0;
78 u32 max_prob
= 0, index_max_prob
= 0;
83 mi
->stats_update
= jiffies
;
84 for (i
= 0; i
< mi
->n_rates
; i
++) {
85 struct minstrel_rate
*mr
= &mi
->r
[i
];
87 usecs
= mr
->perfect_tx_time
;
91 /* To avoid rounding issues, probabilities scale from 0 (0%)
94 p
= (mr
->success
* 18000) / mr
->attempts
;
95 mr
->succ_hist
+= mr
->success
;
96 mr
->att_hist
+= mr
->attempts
;
98 p
= ((p
* (100 - mp
->ewma_level
)) + (mr
->probability
*
99 mp
->ewma_level
)) / 100;
101 mr
->cur_tp
= p
* (1000000 / usecs
);
104 mr
->last_success
= mr
->success
;
105 mr
->last_attempts
= mr
->attempts
;
109 /* Sample less often below the 10% chance of success.
110 * Sample less often above the 95% chance of success. */
111 if ((mr
->probability
> 17100) || (mr
->probability
< 1800)) {
112 mr
->adjusted_retry_count
= mr
->retry_count
>> 1;
113 if (mr
->adjusted_retry_count
> 2)
114 mr
->adjusted_retry_count
= 2;
115 mr
->sample_limit
= 4;
117 mr
->sample_limit
= -1;
118 mr
->adjusted_retry_count
= mr
->retry_count
;
120 if (!mr
->adjusted_retry_count
)
121 mr
->adjusted_retry_count
= 2;
124 for (i
= 0; i
< mi
->n_rates
; i
++) {
125 struct minstrel_rate
*mr
= &mi
->r
[i
];
126 if (max_tp
< mr
->cur_tp
) {
130 if (max_prob
< mr
->probability
) {
132 max_prob
= mr
->probability
;
137 for (i
= 0; i
< mi
->n_rates
; i
++) {
138 struct minstrel_rate
*mr
= &mi
->r
[i
];
140 if (i
== index_max_tp
)
143 if (max_tp
< mr
->cur_tp
) {
148 mi
->max_tp_rate
= index_max_tp
;
149 mi
->max_tp_rate2
= index_max_tp2
;
150 mi
->max_prob_rate
= index_max_prob
;
154 minstrel_tx_status(void *priv
, struct ieee80211_supported_band
*sband
,
155 struct ieee80211_sta
*sta
, void *priv_sta
,
158 struct minstrel_sta_info
*mi
= priv_sta
;
159 struct minstrel_priv
*mp
= (struct minstrel_priv
*)priv
;
160 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
161 struct ieee80211_tx_rate
*ar
= info
->status
.rates
;
162 struct ieee80211_local
*local
= hw_to_local(mp
->hw
);
167 success
= !!(info
->flags
& IEEE80211_TX_STAT_ACK
);
168 si
= sta_info_get(local
, sta
->addr
);
170 for (i
= 0; i
< IEEE80211_TX_MAX_RATES
; i
++) {
174 ndx
= rix_to_ndx(mi
, ar
[i
].idx
);
178 mi
->r
[ndx
].attempts
+= ar
[i
].count
;
180 if ((i
!= IEEE80211_TX_MAX_RATES
- 1) && (ar
[i
+ 1].idx
< 0)) {
181 mi
->r
[ndx
].success
+= success
;
183 si
->fail_avg
= (18050 - mi
->r
[ndx
].probability
)
185 WARN_ON(si
->fail_avg
> 100);
186 if (si
->fail_avg
== 100 &&
187 ieee80211_vif_is_mesh(&si
->sdata
->vif
))
188 mesh_plink_broken(si
);
193 if ((info
->flags
& IEEE80211_TX_CTL_RATE_CTRL_PROBE
) && (i
>= 0))
196 if (mi
->sample_deferred
> 0)
197 mi
->sample_deferred
--;
201 static inline unsigned int
202 minstrel_get_retry_count(struct minstrel_rate
*mr
,
203 struct ieee80211_tx_info
*info
)
205 unsigned int retry
= mr
->adjusted_retry_count
;
207 if (info
->control
.rates
[0].flags
& IEEE80211_TX_RC_USE_RTS_CTS
)
208 retry
= max(2U, min(mr
->retry_count_rtscts
, retry
));
209 else if (info
->control
.rates
[0].flags
& IEEE80211_TX_RC_USE_CTS_PROTECT
)
210 retry
= max(2U, min(mr
->retry_count_cts
, retry
));
216 minstrel_get_next_sample(struct minstrel_sta_info
*mi
)
218 unsigned int sample_ndx
;
219 sample_ndx
= SAMPLE_TBL(mi
, mi
->sample_idx
, mi
->sample_column
);
221 if ((int) mi
->sample_idx
> (mi
->n_rates
- 2)) {
224 if (mi
->sample_column
>= SAMPLE_COLUMNS
)
225 mi
->sample_column
= 0;
231 minstrel_get_rate(void *priv
, struct ieee80211_sta
*sta
,
232 void *priv_sta
, struct ieee80211_tx_rate_control
*txrc
)
234 struct sk_buff
*skb
= txrc
->skb
;
235 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
236 struct minstrel_sta_info
*mi
= priv_sta
;
237 struct minstrel_priv
*mp
= priv
;
238 struct ieee80211_tx_rate
*ar
= info
->control
.rates
;
239 unsigned int ndx
, sample_ndx
= 0;
241 bool sample_slower
= false;
247 if (rate_control_send_low(sta
, priv_sta
, txrc
))
250 mrr
= mp
->has_mrr
&& !txrc
->rts
&& !txrc
->bss_conf
->use_cts_prot
;
252 if (time_after(jiffies
, mi
->stats_update
+ (mp
->update_interval
*
254 minstrel_update_stats(mp
, mi
);
256 ndx
= mi
->max_tp_rate
;
259 sample_rate
= mp
->lookaround_rate_mrr
;
261 sample_rate
= mp
->lookaround_rate
;
264 delta
= (mi
->packet_count
* sample_rate
/ 100) -
265 (mi
->sample_count
+ mi
->sample_deferred
/ 2);
267 /* delta > 0: sampling required */
268 if ((delta
> 0) && (mrr
|| !mi
->prev_sample
)) {
269 struct minstrel_rate
*msr
;
270 if (mi
->packet_count
>= 10000) {
271 mi
->sample_deferred
= 0;
272 mi
->sample_count
= 0;
273 mi
->packet_count
= 0;
274 } else if (delta
> mi
->n_rates
* 2) {
275 /* With multi-rate retry, not every planned sample
276 * attempt actually gets used, due to the way the retry
277 * chain is set up - [max_tp,sample,prob,lowest] for
278 * sample_rate < max_tp.
280 * If there's too much sampling backlog and the link
281 * starts getting worse, minstrel would start bursting
282 * out lots of sampling frames, which would result
283 * in a large throughput loss. */
284 mi
->sample_count
+= (delta
- mi
->n_rates
* 2);
287 sample_ndx
= minstrel_get_next_sample(mi
);
288 msr
= &mi
->r
[sample_ndx
];
290 sample_slower
= mrr
&& (msr
->perfect_tx_time
>
291 mi
->r
[ndx
].perfect_tx_time
);
293 if (!sample_slower
) {
294 if (msr
->sample_limit
!= 0) {
297 if (msr
->sample_limit
> 0)
303 /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
304 * packets that have the sampling rate deferred to the
305 * second MRR stage. Increase the sample counter only
306 * if the deferred sample rate was actually used.
307 * Use the sample_deferred counter to make sure that
308 * the sampling is not done in large bursts */
309 info
->flags
|= IEEE80211_TX_CTL_RATE_CTRL_PROBE
;
310 mi
->sample_deferred
++;
313 mi
->prev_sample
= sample
;
315 /* If we're not using MRR and the sampling rate already
316 * has a probability of >95%, we shouldn't be attempting
317 * to use it, as this only wastes precious airtime */
318 if (!mrr
&& sample
&& (mi
->r
[ndx
].probability
> 17100))
319 ndx
= mi
->max_tp_rate
;
321 ar
[0].idx
= mi
->r
[ndx
].rix
;
322 ar
[0].count
= minstrel_get_retry_count(&mi
->r
[ndx
], info
);
326 ar
[0].count
= mp
->max_retry
;
327 ar
[1].idx
= mi
->lowest_rix
;
328 ar
[1].count
= mp
->max_retry
;
335 mrr_ndx
[0] = sample_ndx
;
337 mrr_ndx
[0] = mi
->max_tp_rate
;
339 mrr_ndx
[0] = mi
->max_tp_rate2
;
341 mrr_ndx
[1] = mi
->max_prob_rate
;
343 for (i
= 1; i
< 4; i
++) {
344 ar
[i
].idx
= mi
->r
[mrr_ndx
[i
- 1]].rix
;
345 ar
[i
].count
= mi
->r
[mrr_ndx
[i
- 1]].adjusted_retry_count
;
351 calc_rate_durations(struct minstrel_sta_info
*mi
, struct ieee80211_local
*local
,
352 struct minstrel_rate
*d
, struct ieee80211_rate
*rate
)
354 int erp
= !!(rate
->flags
& IEEE80211_RATE_ERP_G
);
356 d
->perfect_tx_time
= ieee80211_frame_duration(local
, 1200,
357 rate
->bitrate
, erp
, 1);
358 d
->ack_time
= ieee80211_frame_duration(local
, 10,
359 rate
->bitrate
, erp
, 1);
363 init_sample_table(struct minstrel_sta_info
*mi
)
365 unsigned int i
, col
, new_idx
;
366 unsigned int n_srates
= mi
->n_rates
- 1;
369 mi
->sample_column
= 0;
371 memset(mi
->sample_table
, 0, SAMPLE_COLUMNS
* mi
->n_rates
);
373 for (col
= 0; col
< SAMPLE_COLUMNS
; col
++) {
374 for (i
= 0; i
< n_srates
; i
++) {
375 get_random_bytes(rnd
, sizeof(rnd
));
376 new_idx
= (i
+ rnd
[i
& 7]) % n_srates
;
378 while (SAMPLE_TBL(mi
, new_idx
, col
) != 0)
379 new_idx
= (new_idx
+ 1) % n_srates
;
381 /* Don't sample the slowest rate (i.e. slowest base
382 * rate). We must presume that the slowest rate works
383 * fine, or else other management frames will also be
384 * failing and the link will break */
385 SAMPLE_TBL(mi
, new_idx
, col
) = i
+ 1;
391 minstrel_rate_init(void *priv
, struct ieee80211_supported_band
*sband
,
392 struct ieee80211_sta
*sta
, void *priv_sta
)
394 struct minstrel_sta_info
*mi
= priv_sta
;
395 struct minstrel_priv
*mp
= priv
;
396 struct ieee80211_local
*local
= hw_to_local(mp
->hw
);
397 struct ieee80211_rate
*ctl_rate
;
398 unsigned int i
, n
= 0;
399 unsigned int t_slot
= 9; /* FIXME: get real slot time */
401 mi
->lowest_rix
= rate_lowest_index(sband
, sta
);
402 ctl_rate
= &sband
->bitrates
[mi
->lowest_rix
];
403 mi
->sp_ack_dur
= ieee80211_frame_duration(local
, 10, ctl_rate
->bitrate
,
404 !!(ctl_rate
->flags
& IEEE80211_RATE_ERP_G
), 1);
406 for (i
= 0; i
< sband
->n_bitrates
; i
++) {
407 struct minstrel_rate
*mr
= &mi
->r
[n
];
408 unsigned int tx_time
= 0, tx_time_cts
= 0, tx_time_rtscts
= 0;
409 unsigned int tx_time_single
;
410 unsigned int cw
= mp
->cw_min
;
412 if (!rate_supported(sta
, sband
->band
, i
))
415 memset(mr
, 0, sizeof(*mr
));
418 mr
->bitrate
= sband
->bitrates
[i
].bitrate
/ 5;
419 calc_rate_durations(mi
, local
, mr
,
420 &sband
->bitrates
[i
]);
422 /* calculate maximum number of retransmissions before
423 * fallback (based on maximum segment size) */
424 mr
->sample_limit
= -1;
426 mr
->retry_count_cts
= 1;
427 mr
->retry_count_rtscts
= 1;
428 tx_time
= mr
->perfect_tx_time
+ mi
->sp_ack_dur
;
430 /* add one retransmission */
431 tx_time_single
= mr
->ack_time
+ mr
->perfect_tx_time
;
433 /* contention window */
434 tx_time_single
+= t_slot
+ min(cw
, mp
->cw_max
);
437 tx_time
+= tx_time_single
;
438 tx_time_cts
+= tx_time_single
+ mi
->sp_ack_dur
;
439 tx_time_rtscts
+= tx_time_single
+ 2 * mi
->sp_ack_dur
;
440 if ((tx_time_cts
< mp
->segment_size
) &&
441 (mr
->retry_count_cts
< mp
->max_retry
))
442 mr
->retry_count_cts
++;
443 if ((tx_time_rtscts
< mp
->segment_size
) &&
444 (mr
->retry_count_rtscts
< mp
->max_retry
))
445 mr
->retry_count_rtscts
++;
446 } while ((tx_time
< mp
->segment_size
) &&
447 (++mr
->retry_count
< mp
->max_retry
));
448 mr
->adjusted_retry_count
= mr
->retry_count
;
451 for (i
= n
; i
< sband
->n_bitrates
; i
++) {
452 struct minstrel_rate
*mr
= &mi
->r
[i
];
457 mi
->stats_update
= jiffies
;
459 init_sample_table(mi
);
463 minstrel_alloc_sta(void *priv
, struct ieee80211_sta
*sta
, gfp_t gfp
)
465 struct ieee80211_supported_band
*sband
;
466 struct minstrel_sta_info
*mi
;
467 struct minstrel_priv
*mp
= priv
;
468 struct ieee80211_hw
*hw
= mp
->hw
;
472 mi
= kzalloc(sizeof(struct minstrel_sta_info
), gfp
);
476 for (i
= 0; i
< IEEE80211_NUM_BANDS
; i
++) {
477 sband
= hw
->wiphy
->bands
[i
];
478 if (sband
&& sband
->n_bitrates
> max_rates
)
479 max_rates
= sband
->n_bitrates
;
482 mi
->r
= kzalloc(sizeof(struct minstrel_rate
) * max_rates
, gfp
);
486 mi
->sample_table
= kmalloc(SAMPLE_COLUMNS
* max_rates
, gfp
);
487 if (!mi
->sample_table
)
490 mi
->stats_update
= jiffies
;
501 minstrel_free_sta(void *priv
, struct ieee80211_sta
*sta
, void *priv_sta
)
503 struct minstrel_sta_info
*mi
= priv_sta
;
505 kfree(mi
->sample_table
);
511 minstrel_alloc(struct ieee80211_hw
*hw
, struct dentry
*debugfsdir
)
513 struct minstrel_priv
*mp
;
515 mp
= kzalloc(sizeof(struct minstrel_priv
), GFP_ATOMIC
);
519 /* contention window settings
520 * Just an approximation. Using the per-queue values would complicate
521 * the calculations and is probably unnecessary */
525 /* number of packets (in %) to use for sampling other rates
526 * sample less often for non-mrr packets, because the overhead
527 * is much higher than with mrr */
528 mp
->lookaround_rate
= 5;
529 mp
->lookaround_rate_mrr
= 10;
531 /* moving average weight for EWMA */
534 /* maximum time that the hw is allowed to stay in one MRR segment */
535 mp
->segment_size
= 6000;
537 if (hw
->max_rate_tries
> 0)
538 mp
->max_retry
= hw
->max_rate_tries
;
540 /* safe default, does not necessarily have to match hw properties */
543 if (hw
->max_rates
>= 4)
547 mp
->update_interval
= 100;
553 minstrel_free(void *priv
)
558 static struct rate_control_ops mac80211_minstrel
= {
560 .tx_status
= minstrel_tx_status
,
561 .get_rate
= minstrel_get_rate
,
562 .rate_init
= minstrel_rate_init
,
563 .alloc
= minstrel_alloc
,
564 .free
= minstrel_free
,
565 .alloc_sta
= minstrel_alloc_sta
,
566 .free_sta
= minstrel_free_sta
,
567 #ifdef CONFIG_MAC80211_DEBUGFS
568 .add_sta_debugfs
= minstrel_add_sta_debugfs
,
569 .remove_sta_debugfs
= minstrel_remove_sta_debugfs
,
574 rc80211_minstrel_init(void)
576 return ieee80211_rate_control_register(&mac80211_minstrel
);
580 rc80211_minstrel_exit(void)
582 ieee80211_rate_control_unregister(&mac80211_minstrel
);