]> git.karo-electronics.de Git - karo-tx-linux.git/blob - net/mac80211/rc80211_minstrel.c
c9b9902379913ffb668e71ea482efb796bb283e8
[karo-tx-linux.git] / net / mac80211 / rc80211_minstrel.c
1 /*
2  * Copyright (C) 2008 Felix Fietkau <nbd@openwrt.org>
3  *
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.
7  *
8  * Based on minstrel.c:
9  *   Copyright (C) 2005-2007 Derek Smithies <derek@indranet.co.nz>
10  *   Sponsored by Indranet Technologies Ltd
11  *
12  * Based on sample.c:
13  *   Copyright (c) 2005 John Bicket
14  *   All rights reserved.
15  *
16  *   Redistribution and use in source and binary forms, with or without
17  *   modification, are permitted provided that the following conditions
18  *   are met:
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.
29  *
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.
33  *
34  *   NO WARRANTY
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.
46  */
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>
55 #include "rate.h"
56 #include "rc80211_minstrel.h"
57
58 #define SAMPLE_COLUMNS  10
59 #define SAMPLE_TBL(_mi, _idx, _col) \
60                 _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
61
62 /* convert mac80211 rate index to local array index */
63 static inline int
64 rix_to_ndx(struct minstrel_sta_info *mi, int rix)
65 {
66         int i = rix;
67         for (i = rix; i >= 0; i--)
68                 if (mi->r[i].rix == rix)
69                         break;
70         return i;
71 }
72
73 static void
74 minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
75 {
76         u32 max_tp = 0, index_max_tp = 0, index_max_tp2 = 0;
77         u32 max_prob = 0, index_max_prob = 0;
78         u32 usecs;
79         int i;
80
81         mi->stats_update = jiffies;
82         for (i = 0; i < mi->n_rates; i++) {
83                 struct minstrel_rate *mr = &mi->r[i];
84
85                 usecs = mr->perfect_tx_time;
86                 if (!usecs)
87                         usecs = 1000000;
88
89                 if (mr->attempts) {
90                         mr->cur_prob = MINSTREL_FRAC(mr->success, mr->attempts);
91                         mr->succ_hist += mr->success;
92                         mr->att_hist += mr->attempts;
93                         mr->probability = minstrel_ewma(mr->probability,
94                                                         mr->cur_prob,
95                                                         EWMA_LEVEL);
96                         mr->cur_tp = mr->probability * (1000000 / usecs);
97                 }
98
99                 mr->last_success = mr->success;
100                 mr->last_attempts = mr->attempts;
101                 mr->success = 0;
102                 mr->attempts = 0;
103
104                 /* Sample less often below the 10% chance of success.
105                  * Sample less often above the 95% chance of success. */
106                 if (mr->probability > MINSTREL_FRAC(95, 100) ||
107                     mr->probability < MINSTREL_FRAC(10, 100)) {
108                         mr->adjusted_retry_count = mr->retry_count >> 1;
109                         if (mr->adjusted_retry_count > 2)
110                                 mr->adjusted_retry_count = 2;
111                         mr->sample_limit = 4;
112                 } else {
113                         mr->sample_limit = -1;
114                         mr->adjusted_retry_count = mr->retry_count;
115                 }
116                 if (!mr->adjusted_retry_count)
117                         mr->adjusted_retry_count = 2;
118         }
119
120         for (i = 0; i < mi->n_rates; i++) {
121                 struct minstrel_rate *mr = &mi->r[i];
122                 if (max_tp < mr->cur_tp) {
123                         index_max_tp = i;
124                         max_tp = mr->cur_tp;
125                 }
126                 if (max_prob < mr->probability) {
127                         index_max_prob = i;
128                         max_prob = mr->probability;
129                 }
130         }
131
132         max_tp = 0;
133         for (i = 0; i < mi->n_rates; i++) {
134                 struct minstrel_rate *mr = &mi->r[i];
135
136                 if (i == index_max_tp)
137                         continue;
138
139                 if (max_tp < mr->cur_tp) {
140                         index_max_tp2 = i;
141                         max_tp = mr->cur_tp;
142                 }
143         }
144         mi->max_tp_rate = index_max_tp;
145         mi->max_tp_rate2 = index_max_tp2;
146         mi->max_prob_rate = index_max_prob;
147 }
148
149 static void
150 minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband,
151                    struct ieee80211_sta *sta, void *priv_sta,
152                    struct sk_buff *skb)
153 {
154         struct minstrel_priv *mp = priv;
155         struct minstrel_sta_info *mi = priv_sta;
156         struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
157         struct ieee80211_tx_rate *ar = info->status.rates;
158         int i, ndx;
159         int success;
160
161         success = !!(info->flags & IEEE80211_TX_STAT_ACK);
162
163         for (i = 0; i < IEEE80211_TX_MAX_RATES; i++) {
164                 if (ar[i].idx < 0)
165                         break;
166
167                 ndx = rix_to_ndx(mi, ar[i].idx);
168                 if (ndx < 0)
169                         continue;
170
171                 mi->r[ndx].attempts += ar[i].count;
172
173                 if ((i != IEEE80211_TX_MAX_RATES - 1) && (ar[i + 1].idx < 0))
174                         mi->r[ndx].success += success;
175         }
176
177         if ((info->flags & IEEE80211_TX_CTL_RATE_CTRL_PROBE) && (i >= 0))
178                 mi->sample_count++;
179
180         if (mi->sample_deferred > 0)
181                 mi->sample_deferred--;
182
183         if (time_after(jiffies, mi->stats_update +
184                                 (mp->update_interval * HZ) / 1000))
185                 minstrel_update_stats(mp, mi);
186 }
187
188
189 static inline unsigned int
190 minstrel_get_retry_count(struct minstrel_rate *mr,
191                          struct ieee80211_tx_info *info)
192 {
193         unsigned int retry = mr->adjusted_retry_count;
194
195         if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_RTS_CTS)
196                 retry = max(2U, min(mr->retry_count_rtscts, retry));
197         else if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_CTS_PROTECT)
198                 retry = max(2U, min(mr->retry_count_cts, retry));
199         return retry;
200 }
201
202
203 static int
204 minstrel_get_next_sample(struct minstrel_sta_info *mi)
205 {
206         unsigned int sample_ndx;
207         sample_ndx = SAMPLE_TBL(mi, mi->sample_idx, mi->sample_column);
208         mi->sample_idx++;
209         if ((int) mi->sample_idx > (mi->n_rates - 2)) {
210                 mi->sample_idx = 0;
211                 mi->sample_column++;
212                 if (mi->sample_column >= SAMPLE_COLUMNS)
213                         mi->sample_column = 0;
214         }
215         return sample_ndx;
216 }
217
218 static void
219 minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
220                   void *priv_sta, struct ieee80211_tx_rate_control *txrc)
221 {
222         struct sk_buff *skb = txrc->skb;
223         struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
224         struct minstrel_sta_info *mi = priv_sta;
225         struct minstrel_priv *mp = priv;
226         struct ieee80211_tx_rate *ar = info->control.rates;
227         unsigned int ndx, sample_ndx = 0;
228         bool mrr;
229         bool sample_slower = false;
230         bool sample = false;
231         int i, delta;
232         int mrr_ndx[3];
233         int sample_rate;
234
235         if (rate_control_send_low(sta, priv_sta, txrc))
236                 return;
237
238         mrr = mp->has_mrr && !txrc->rts && !txrc->bss_conf->use_cts_prot;
239
240         ndx = mi->max_tp_rate;
241
242         if (mrr)
243                 sample_rate = mp->lookaround_rate_mrr;
244         else
245                 sample_rate = mp->lookaround_rate;
246
247         mi->packet_count++;
248         delta = (mi->packet_count * sample_rate / 100) -
249                         (mi->sample_count + mi->sample_deferred / 2);
250
251         /* delta > 0: sampling required */
252         if ((delta > 0) && (mrr || !mi->prev_sample)) {
253                 struct minstrel_rate *msr;
254                 if (mi->packet_count >= 10000) {
255                         mi->sample_deferred = 0;
256                         mi->sample_count = 0;
257                         mi->packet_count = 0;
258                 } else if (delta > mi->n_rates * 2) {
259                         /* With multi-rate retry, not every planned sample
260                          * attempt actually gets used, due to the way the retry
261                          * chain is set up - [max_tp,sample,prob,lowest] for
262                          * sample_rate < max_tp.
263                          *
264                          * If there's too much sampling backlog and the link
265                          * starts getting worse, minstrel would start bursting
266                          * out lots of sampling frames, which would result
267                          * in a large throughput loss. */
268                         mi->sample_count += (delta - mi->n_rates * 2);
269                 }
270
271                 sample_ndx = minstrel_get_next_sample(mi);
272                 msr = &mi->r[sample_ndx];
273                 sample = true;
274                 sample_slower = mrr && (msr->perfect_tx_time >
275                         mi->r[ndx].perfect_tx_time);
276
277                 if (!sample_slower) {
278                         if (msr->sample_limit != 0) {
279                                 ndx = sample_ndx;
280                                 mi->sample_count++;
281                                 if (msr->sample_limit > 0)
282                                         msr->sample_limit--;
283                         } else {
284                                 sample = false;
285                         }
286                 } else {
287                         /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
288                          * packets that have the sampling rate deferred to the
289                          * second MRR stage. Increase the sample counter only
290                          * if the deferred sample rate was actually used.
291                          * Use the sample_deferred counter to make sure that
292                          * the sampling is not done in large bursts */
293                         info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE;
294                         mi->sample_deferred++;
295                 }
296         }
297         mi->prev_sample = sample;
298
299         /* If we're not using MRR and the sampling rate already
300          * has a probability of >95%, we shouldn't be attempting
301          * to use it, as this only wastes precious airtime */
302         if (!mrr && sample && (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
303                 ndx = mi->max_tp_rate;
304
305         ar[0].idx = mi->r[ndx].rix;
306         ar[0].count = minstrel_get_retry_count(&mi->r[ndx], info);
307
308         if (!mrr) {
309                 if (!sample)
310                         ar[0].count = mp->max_retry;
311                 ar[1].idx = mi->lowest_rix;
312                 ar[1].count = mp->max_retry;
313                 return;
314         }
315
316         /* MRR setup */
317         if (sample) {
318                 if (sample_slower)
319                         mrr_ndx[0] = sample_ndx;
320                 else
321                         mrr_ndx[0] = mi->max_tp_rate;
322         } else {
323                 mrr_ndx[0] = mi->max_tp_rate2;
324         }
325         mrr_ndx[1] = mi->max_prob_rate;
326         mrr_ndx[2] = 0;
327         for (i = 1; i < 4; i++) {
328                 ar[i].idx = mi->r[mrr_ndx[i - 1]].rix;
329                 ar[i].count = mi->r[mrr_ndx[i - 1]].adjusted_retry_count;
330         }
331 }
332
333
334 static void
335 calc_rate_durations(enum ieee80211_band band,
336                     struct minstrel_rate *d,
337                     struct ieee80211_rate *rate)
338 {
339         int erp = !!(rate->flags & IEEE80211_RATE_ERP_G);
340
341         d->perfect_tx_time = ieee80211_frame_duration(band, 1200,
342                         rate->bitrate, erp, 1);
343         d->ack_time = ieee80211_frame_duration(band, 10,
344                         rate->bitrate, erp, 1);
345 }
346
347 static void
348 init_sample_table(struct minstrel_sta_info *mi)
349 {
350         unsigned int i, col, new_idx;
351         unsigned int n_srates = mi->n_rates - 1;
352         u8 rnd[8];
353
354         mi->sample_column = 0;
355         mi->sample_idx = 0;
356         memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates);
357
358         for (col = 0; col < SAMPLE_COLUMNS; col++) {
359                 for (i = 0; i < n_srates; i++) {
360                         get_random_bytes(rnd, sizeof(rnd));
361                         new_idx = (i + rnd[i & 7]) % n_srates;
362
363                         while (SAMPLE_TBL(mi, new_idx, col) != 0)
364                                 new_idx = (new_idx + 1) % n_srates;
365
366                         /* Don't sample the slowest rate (i.e. slowest base
367                          * rate). We must presume that the slowest rate works
368                          * fine, or else other management frames will also be
369                          * failing and the link will break */
370                         SAMPLE_TBL(mi, new_idx, col) = i + 1;
371                 }
372         }
373 }
374
375 static void
376 minstrel_rate_init(void *priv, struct ieee80211_supported_band *sband,
377                struct ieee80211_sta *sta, void *priv_sta)
378 {
379         struct minstrel_sta_info *mi = priv_sta;
380         struct minstrel_priv *mp = priv;
381         struct ieee80211_rate *ctl_rate;
382         unsigned int i, n = 0;
383         unsigned int t_slot = 9; /* FIXME: get real slot time */
384
385         mi->lowest_rix = rate_lowest_index(sband, sta);
386         ctl_rate = &sband->bitrates[mi->lowest_rix];
387         mi->sp_ack_dur = ieee80211_frame_duration(sband->band, 10,
388                                 ctl_rate->bitrate,
389                                 !!(ctl_rate->flags & IEEE80211_RATE_ERP_G), 1);
390
391         for (i = 0; i < sband->n_bitrates; i++) {
392                 struct minstrel_rate *mr = &mi->r[n];
393                 unsigned int tx_time = 0, tx_time_cts = 0, tx_time_rtscts = 0;
394                 unsigned int tx_time_single;
395                 unsigned int cw = mp->cw_min;
396
397                 if (!rate_supported(sta, sband->band, i))
398                         continue;
399                 n++;
400                 memset(mr, 0, sizeof(*mr));
401
402                 mr->rix = i;
403                 mr->bitrate = sband->bitrates[i].bitrate / 5;
404                 calc_rate_durations(sband->band, mr, &sband->bitrates[i]);
405
406                 /* calculate maximum number of retransmissions before
407                  * fallback (based on maximum segment size) */
408                 mr->sample_limit = -1;
409                 mr->retry_count = 1;
410                 mr->retry_count_cts = 1;
411                 mr->retry_count_rtscts = 1;
412                 tx_time = mr->perfect_tx_time + mi->sp_ack_dur;
413                 do {
414                         /* add one retransmission */
415                         tx_time_single = mr->ack_time + mr->perfect_tx_time;
416
417                         /* contention window */
418                         tx_time_single += (t_slot * cw) >> 1;
419                         cw = min((cw << 1) | 1, mp->cw_max);
420
421                         tx_time += tx_time_single;
422                         tx_time_cts += tx_time_single + mi->sp_ack_dur;
423                         tx_time_rtscts += tx_time_single + 2 * mi->sp_ack_dur;
424                         if ((tx_time_cts < mp->segment_size) &&
425                                 (mr->retry_count_cts < mp->max_retry))
426                                 mr->retry_count_cts++;
427                         if ((tx_time_rtscts < mp->segment_size) &&
428                                 (mr->retry_count_rtscts < mp->max_retry))
429                                 mr->retry_count_rtscts++;
430                 } while ((tx_time < mp->segment_size) &&
431                                 (++mr->retry_count < mp->max_retry));
432                 mr->adjusted_retry_count = mr->retry_count;
433         }
434
435         for (i = n; i < sband->n_bitrates; i++) {
436                 struct minstrel_rate *mr = &mi->r[i];
437                 mr->rix = -1;
438         }
439
440         mi->n_rates = n;
441         mi->stats_update = jiffies;
442
443         init_sample_table(mi);
444 }
445
446 static void *
447 minstrel_alloc_sta(void *priv, struct ieee80211_sta *sta, gfp_t gfp)
448 {
449         struct ieee80211_supported_band *sband;
450         struct minstrel_sta_info *mi;
451         struct minstrel_priv *mp = priv;
452         struct ieee80211_hw *hw = mp->hw;
453         int max_rates = 0;
454         int i;
455
456         mi = kzalloc(sizeof(struct minstrel_sta_info), gfp);
457         if (!mi)
458                 return NULL;
459
460         for (i = 0; i < IEEE80211_NUM_BANDS; i++) {
461                 sband = hw->wiphy->bands[i];
462                 if (sband && sband->n_bitrates > max_rates)
463                         max_rates = sband->n_bitrates;
464         }
465
466         mi->r = kzalloc(sizeof(struct minstrel_rate) * max_rates, gfp);
467         if (!mi->r)
468                 goto error;
469
470         mi->sample_table = kmalloc(SAMPLE_COLUMNS * max_rates, gfp);
471         if (!mi->sample_table)
472                 goto error1;
473
474         mi->stats_update = jiffies;
475         return mi;
476
477 error1:
478         kfree(mi->r);
479 error:
480         kfree(mi);
481         return NULL;
482 }
483
484 static void
485 minstrel_free_sta(void *priv, struct ieee80211_sta *sta, void *priv_sta)
486 {
487         struct minstrel_sta_info *mi = priv_sta;
488
489         kfree(mi->sample_table);
490         kfree(mi->r);
491         kfree(mi);
492 }
493
494 static void
495 minstrel_init_cck_rates(struct minstrel_priv *mp)
496 {
497         static const int bitrates[4] = { 10, 20, 55, 110 };
498         struct ieee80211_supported_band *sband;
499         int i, j;
500
501         sband = mp->hw->wiphy->bands[IEEE80211_BAND_2GHZ];
502         if (!sband)
503                 return;
504
505         for (i = 0, j = 0; i < sband->n_bitrates; i++) {
506                 struct ieee80211_rate *rate = &sband->bitrates[i];
507
508                 if (rate->flags & IEEE80211_RATE_ERP_G)
509                         continue;
510
511                 for (j = 0; j < ARRAY_SIZE(bitrates); j++) {
512                         if (rate->bitrate != bitrates[j])
513                                 continue;
514
515                         mp->cck_rates[j] = i;
516                         break;
517                 }
518         }
519 }
520
521 static void *
522 minstrel_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
523 {
524         struct minstrel_priv *mp;
525
526         mp = kzalloc(sizeof(struct minstrel_priv), GFP_ATOMIC);
527         if (!mp)
528                 return NULL;
529
530         /* contention window settings
531          * Just an approximation. Using the per-queue values would complicate
532          * the calculations and is probably unnecessary */
533         mp->cw_min = 15;
534         mp->cw_max = 1023;
535
536         /* number of packets (in %) to use for sampling other rates
537          * sample less often for non-mrr packets, because the overhead
538          * is much higher than with mrr */
539         mp->lookaround_rate = 5;
540         mp->lookaround_rate_mrr = 10;
541
542         /* maximum time that the hw is allowed to stay in one MRR segment */
543         mp->segment_size = 6000;
544
545         if (hw->max_rate_tries > 0)
546                 mp->max_retry = hw->max_rate_tries;
547         else
548                 /* safe default, does not necessarily have to match hw properties */
549                 mp->max_retry = 7;
550
551         if (hw->max_rates >= 4)
552                 mp->has_mrr = true;
553
554         mp->hw = hw;
555         mp->update_interval = 100;
556
557 #ifdef CONFIG_MAC80211_DEBUGFS
558         mp->fixed_rate_idx = (u32) -1;
559         mp->dbg_fixed_rate = debugfs_create_u32("fixed_rate_idx",
560                         S_IRUGO | S_IWUGO, debugfsdir, &mp->fixed_rate_idx);
561 #endif
562
563         minstrel_init_cck_rates(mp);
564
565         return mp;
566 }
567
568 static void
569 minstrel_free(void *priv)
570 {
571 #ifdef CONFIG_MAC80211_DEBUGFS
572         debugfs_remove(((struct minstrel_priv *)priv)->dbg_fixed_rate);
573 #endif
574         kfree(priv);
575 }
576
577 struct rate_control_ops mac80211_minstrel = {
578         .name = "minstrel",
579         .tx_status = minstrel_tx_status,
580         .get_rate = minstrel_get_rate,
581         .rate_init = minstrel_rate_init,
582         .alloc = minstrel_alloc,
583         .free = minstrel_free,
584         .alloc_sta = minstrel_alloc_sta,
585         .free_sta = minstrel_free_sta,
586 #ifdef CONFIG_MAC80211_DEBUGFS
587         .add_sta_debugfs = minstrel_add_sta_debugfs,
588         .remove_sta_debugfs = minstrel_remove_sta_debugfs,
589 #endif
590 };
591
592 int __init
593 rc80211_minstrel_init(void)
594 {
595         return ieee80211_rate_control_register(&mac80211_minstrel);
596 }
597
598 void
599 rc80211_minstrel_exit(void)
600 {
601         ieee80211_rate_control_unregister(&mac80211_minstrel);
602 }
603