00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047 #include <linux/netdevice.h>
00048 #include <linux/types.h>
00049 #include <linux/skbuff.h>
00050 #include <linux/debugfs.h>
00051 #include <linux/random.h>
00052 #include <linux/ieee80211.h>
00053 #include <linux/slab.h>
00054 #include <net/mac80211.h>
00055 #include "rate.h"
00056 #include "rc80211_minstrel.h"
00057
00058 #define SAMPLE_COLUMNS 10
00059 #define SAMPLE_TBL(_mi, _idx, _col) \
00060 _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
00061
00062
00063 static inline int
00064 rix_to_ndx(struct minstrel_sta_info *mi, int rix)
00065 {
00066 int i = rix;
00067 for (i = rix; i >= 0; i--)
00068 if (mi->r[i].rix == rix)
00069 break;
00070 return i;
00071 }
00072
00073 static void
00074 minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
00075 {
00076 u32 max_tp = 0, index_max_tp = 0, index_max_tp2 = 0;
00077 u32 max_prob = 0, index_max_prob = 0;
00078 u32 usecs;
00079 u32 p;
00080 int i;
00081
00082 mi->stats_update = jiffies;
00083 for (i = 0; i < mi->n_rates; i++) {
00084 struct minstrel_rate *mr = &mi->r[i];
00085
00086 usecs = mr->perfect_tx_time;
00087 if (!usecs)
00088 usecs = 1000000;
00089
00090
00091
00092 if (mr->attempts) {
00093 p = (mr->success * 18000) / mr->attempts;
00094 mr->succ_hist += mr->success;
00095 mr->att_hist += mr->attempts;
00096 mr->cur_prob = p;
00097 p = ((p * (100 - mp->ewma_level)) + (mr->probability *
00098 mp->ewma_level)) / 100;
00099 mr->probability = p;
00100 mr->cur_tp = p * (1000000 / usecs);
00101 }
00102
00103 mr->last_success = mr->success;
00104 mr->last_attempts = mr->attempts;
00105 mr->success = 0;
00106 mr->attempts = 0;
00107
00108
00109
00110 if ((mr->probability > 17100) || (mr->probability < 1800)) {
00111 mr->adjusted_retry_count = mr->retry_count >> 1;
00112 if (mr->adjusted_retry_count > 2)
00113 mr->adjusted_retry_count = 2;
00114 mr->sample_limit = 4;
00115 } else {
00116 mr->sample_limit = -1;
00117 mr->adjusted_retry_count = mr->retry_count;
00118 }
00119 if (!mr->adjusted_retry_count)
00120 mr->adjusted_retry_count = 2;
00121 }
00122
00123 for (i = 0; i < mi->n_rates; i++) {
00124 struct minstrel_rate *mr = &mi->r[i];
00125 if (max_tp < mr->cur_tp) {
00126 index_max_tp = i;
00127 max_tp = mr->cur_tp;
00128 }
00129 if (max_prob < mr->probability) {
00130 index_max_prob = i;
00131 max_prob = mr->probability;
00132 }
00133 }
00134
00135 max_tp = 0;
00136 for (i = 0; i < mi->n_rates; i++) {
00137 struct minstrel_rate *mr = &mi->r[i];
00138
00139 if (i == index_max_tp)
00140 continue;
00141
00142 if (max_tp < mr->cur_tp) {
00143 index_max_tp2 = i;
00144 max_tp = mr->cur_tp;
00145 }
00146 }
00147 mi->max_tp_rate = index_max_tp;
00148 mi->max_tp_rate2 = index_max_tp2;
00149 mi->max_prob_rate = index_max_prob;
00150 }
00151
00152 static void
00153 minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband,
00154 struct ieee80211_sta *sta, void *priv_sta,
00155 struct sk_buff *skb)
00156 {
00157 struct minstrel_sta_info *mi = priv_sta;
00158 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
00159 struct ieee80211_tx_rate *ar = info->status.rates;
00160 int i, ndx;
00161 int success;
00162
00163 success = !!(info->flags & IEEE80211_TX_STAT_ACK);
00164
00165 for (i = 0; i < IEEE80211_TX_MAX_RATES; i++) {
00166 if (ar[i].idx < 0)
00167 break;
00168
00169 ndx = rix_to_ndx(mi, ar[i].idx);
00170 if (ndx < 0)
00171 continue;
00172
00173 mi->r[ndx].attempts += ar[i].count;
00174
00175 if ((i != IEEE80211_TX_MAX_RATES - 1) && (ar[i + 1].idx < 0))
00176 mi->r[ndx].success += success;
00177 }
00178
00179 if ((info->flags & IEEE80211_TX_CTL_RATE_CTRL_PROBE) && (i >= 0))
00180 mi->sample_count++;
00181
00182 if (mi->sample_deferred > 0)
00183 mi->sample_deferred--;
00184 }
00185
00186
00187 static inline unsigned int
00188 minstrel_get_retry_count(struct minstrel_rate *mr,
00189 struct ieee80211_tx_info *info)
00190 {
00191 unsigned int retry = mr->adjusted_retry_count;
00192
00193 if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_RTS_CTS)
00194 retry = max(2U, min(mr->retry_count_rtscts, retry));
00195 else if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_CTS_PROTECT)
00196 retry = max(2U, min(mr->retry_count_cts, retry));
00197 return retry;
00198 }
00199
00200
00201 static int
00202 minstrel_get_next_sample(struct minstrel_sta_info *mi)
00203 {
00204 unsigned int sample_ndx;
00205 sample_ndx = SAMPLE_TBL(mi, mi->sample_idx, mi->sample_column);
00206 mi->sample_idx++;
00207 if ((int) mi->sample_idx > (mi->n_rates - 2)) {
00208 mi->sample_idx = 0;
00209 mi->sample_column++;
00210 if (mi->sample_column >= SAMPLE_COLUMNS)
00211 mi->sample_column = 0;
00212 }
00213 return sample_ndx;
00214 }
00215
00216 static void
00217 minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
00218 void *priv_sta, struct ieee80211_tx_rate_control *txrc)
00219 {
00220 struct sk_buff *skb = txrc->skb;
00221 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
00222 struct minstrel_sta_info *mi = priv_sta;
00223 struct minstrel_priv *mp = priv;
00224 struct ieee80211_tx_rate *ar = info->control.rates;
00225 unsigned int ndx, sample_ndx = 0;
00226 bool mrr;
00227 bool sample_slower = false;
00228 bool sample = false;
00229 int i, delta;
00230 int mrr_ndx[3];
00231 int sample_rate;
00232
00233 if (rate_control_send_low(sta, priv_sta, txrc))
00234 return;
00235
00236 mrr = mp->has_mrr && !txrc->rts && !txrc->bss_conf->use_cts_prot;
00237
00238 if (time_after(jiffies, mi->stats_update + (mp->update_interval *
00239 HZ) / 1000))
00240 minstrel_update_stats(mp, mi);
00241
00242 ndx = mi->max_tp_rate;
00243
00244 if (mrr)
00245 sample_rate = mp->lookaround_rate_mrr;
00246 else
00247 sample_rate = mp->lookaround_rate;
00248
00249 mi->packet_count++;
00250 delta = (mi->packet_count * sample_rate / 100) -
00251 (mi->sample_count + mi->sample_deferred / 2);
00252
00253
00254 if ((delta > 0) && (mrr || !mi->prev_sample)) {
00255 struct minstrel_rate *msr;
00256 if (mi->packet_count >= 10000) {
00257 mi->sample_deferred = 0;
00258 mi->sample_count = 0;
00259 mi->packet_count = 0;
00260 } else if (delta > mi->n_rates * 2) {
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270 mi->sample_count += (delta - mi->n_rates * 2);
00271 }
00272
00273 sample_ndx = minstrel_get_next_sample(mi);
00274 msr = &mi->r[sample_ndx];
00275 sample = true;
00276 sample_slower = mrr && (msr->perfect_tx_time >
00277 mi->r[ndx].perfect_tx_time);
00278
00279 if (!sample_slower) {
00280 if (msr->sample_limit != 0) {
00281 ndx = sample_ndx;
00282 mi->sample_count++;
00283 if (msr->sample_limit > 0)
00284 msr->sample_limit--;
00285 } else {
00286 sample = false;
00287 }
00288 } else {
00289
00290
00291
00292
00293
00294
00295 info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE;
00296 mi->sample_deferred++;
00297 }
00298 }
00299 mi->prev_sample = sample;
00300
00301
00302
00303
00304 if (!mrr && sample && (mi->r[ndx].probability > 17100))
00305 ndx = mi->max_tp_rate;
00306
00307 ar[0].idx = mi->r[ndx].rix;
00308 ar[0].count = minstrel_get_retry_count(&mi->r[ndx], info);
00309
00310 if (!mrr) {
00311 if (!sample)
00312 ar[0].count = mp->max_retry;
00313 ar[1].idx = mi->lowest_rix;
00314 ar[1].count = mp->max_retry;
00315 return;
00316 }
00317
00318
00319 if (sample) {
00320 if (sample_slower)
00321 mrr_ndx[0] = sample_ndx;
00322 else
00323 mrr_ndx[0] = mi->max_tp_rate;
00324 } else {
00325 mrr_ndx[0] = mi->max_tp_rate2;
00326 }
00327 mrr_ndx[1] = mi->max_prob_rate;
00328 mrr_ndx[2] = 0;
00329 for (i = 1; i < 4; i++) {
00330 ar[i].idx = mi->r[mrr_ndx[i - 1]].rix;
00331 ar[i].count = mi->r[mrr_ndx[i - 1]].adjusted_retry_count;
00332 }
00333 }
00334
00335
00336 static void
00337 calc_rate_durations(enum ieee80211_band band,
00338 struct minstrel_rate *d,
00339 struct ieee80211_rate *rate)
00340 {
00341 int erp = !!(rate->flags & IEEE80211_RATE_ERP_G);
00342
00343 d->perfect_tx_time = ieee80211_frame_duration(band, 1200,
00344 rate->bitrate, erp, 1);
00345 d->ack_time = ieee80211_frame_duration(band, 10,
00346 rate->bitrate, erp, 1);
00347 }
00348
00349 static void
00350 init_sample_table(struct minstrel_sta_info *mi)
00351 {
00352 unsigned int i, col, new_idx;
00353 unsigned int n_srates = mi->n_rates - 1;
00354 u8 rnd[8];
00355
00356 mi->sample_column = 0;
00357 mi->sample_idx = 0;
00358 memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates);
00359
00360 for (col = 0; col < SAMPLE_COLUMNS; col++) {
00361 for (i = 0; i < n_srates; i++) {
00362 get_random_bytes(rnd, sizeof(rnd));
00363 new_idx = (i + rnd[i & 7]) % n_srates;
00364
00365 while (SAMPLE_TBL(mi, new_idx, col) != 0)
00366 new_idx = (new_idx + 1) % n_srates;
00367
00368
00369
00370
00371
00372 SAMPLE_TBL(mi, new_idx, col) = i + 1;
00373 }
00374 }
00375 }
00376
00377 static void
00378 minstrel_rate_init(void *priv, struct ieee80211_supported_band *sband,
00379 struct ieee80211_sta *sta, void *priv_sta)
00380 {
00381 struct minstrel_sta_info *mi = priv_sta;
00382 struct minstrel_priv *mp = priv;
00383 struct ieee80211_rate *ctl_rate;
00384 unsigned int i, n = 0;
00385 unsigned int t_slot = 9;
00386
00387 mi->lowest_rix = rate_lowest_index(sband, sta);
00388 ctl_rate = &sband->bitrates[mi->lowest_rix];
00389 mi->sp_ack_dur = ieee80211_frame_duration(sband->band, 10,
00390 ctl_rate->bitrate,
00391 !!(ctl_rate->flags & IEEE80211_RATE_ERP_G), 1);
00392
00393 for (i = 0; i < sband->n_bitrates; i++) {
00394 struct minstrel_rate *mr = &mi->r[n];
00395 unsigned int tx_time = 0, tx_time_cts = 0, tx_time_rtscts = 0;
00396 unsigned int tx_time_single;
00397 unsigned int cw = mp->cw_min;
00398
00399 if (!rate_supported(sta, sband->band, i))
00400 continue;
00401 n++;
00402 memset(mr, 0, sizeof(*mr));
00403
00404 mr->rix = i;
00405 mr->bitrate = sband->bitrates[i].bitrate / 5;
00406 calc_rate_durations(sband->band, mr, &sband->bitrates[i]);
00407
00408
00409
00410 mr->sample_limit = -1;
00411 mr->retry_count = 1;
00412 mr->retry_count_cts = 1;
00413 mr->retry_count_rtscts = 1;
00414 tx_time = mr->perfect_tx_time + mi->sp_ack_dur;
00415 do {
00416
00417 tx_time_single = mr->ack_time + mr->perfect_tx_time;
00418
00419
00420 tx_time_single += (t_slot * cw) >> 1;
00421 cw = min((cw << 1) | 1, mp->cw_max);
00422
00423 tx_time += tx_time_single;
00424 tx_time_cts += tx_time_single + mi->sp_ack_dur;
00425 tx_time_rtscts += tx_time_single + 2 * mi->sp_ack_dur;
00426 if ((tx_time_cts < mp->segment_size) &&
00427 (mr->retry_count_cts < mp->max_retry))
00428 mr->retry_count_cts++;
00429 if ((tx_time_rtscts < mp->segment_size) &&
00430 (mr->retry_count_rtscts < mp->max_retry))
00431 mr->retry_count_rtscts++;
00432 } while ((tx_time < mp->segment_size) &&
00433 (++mr->retry_count < mp->max_retry));
00434 mr->adjusted_retry_count = mr->retry_count;
00435 }
00436
00437 for (i = n; i < sband->n_bitrates; i++) {
00438 struct minstrel_rate *mr = &mi->r[i];
00439 mr->rix = -1;
00440 }
00441
00442 mi->n_rates = n;
00443 mi->stats_update = jiffies;
00444
00445 init_sample_table(mi);
00446 }
00447
00448 static void *
00449 minstrel_alloc_sta(void *priv, struct ieee80211_sta *sta, gfp_t gfp)
00450 {
00451 struct ieee80211_supported_band *sband;
00452 struct minstrel_sta_info *mi;
00453 struct minstrel_priv *mp = priv;
00454 struct ieee80211_hw *hw = mp->hw;
00455 int max_rates = 0;
00456 int i;
00457
00458 mi = kzalloc(sizeof(struct minstrel_sta_info), gfp);
00459 if (!mi)
00460 return NULL;
00461
00462 for (i = 0; i < IEEE80211_NUM_BANDS; i++) {
00463 sband = hw->wiphy->bands[i];
00464 if (sband && sband->n_bitrates > max_rates)
00465 max_rates = sband->n_bitrates;
00466 }
00467
00468 mi->r = kzalloc(sizeof(struct minstrel_rate) * max_rates, gfp);
00469 if (!mi->r)
00470 goto error;
00471
00472 mi->sample_table = kmalloc(SAMPLE_COLUMNS * max_rates, gfp);
00473 if (!mi->sample_table)
00474 goto error1;
00475
00476 mi->stats_update = jiffies;
00477 return mi;
00478
00479 error1:
00480 kfree(mi->r);
00481 error:
00482 kfree(mi);
00483 return NULL;
00484 }
00485
00486 static void
00487 minstrel_free_sta(void *priv, struct ieee80211_sta *sta, void *priv_sta)
00488 {
00489 struct minstrel_sta_info *mi = priv_sta;
00490
00491 kfree(mi->sample_table);
00492 kfree(mi->r);
00493 kfree(mi);
00494 }
00495
00496 static void *
00497 minstrel_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
00498 {
00499 struct minstrel_priv *mp;
00500
00501 mp = kzalloc(sizeof(struct minstrel_priv), GFP_ATOMIC);
00502 if (!mp)
00503 return NULL;
00504
00505
00506
00507
00508 mp->cw_min = 15;
00509 mp->cw_max = 1023;
00510
00511
00512
00513
00514 mp->lookaround_rate = 5;
00515 mp->lookaround_rate_mrr = 10;
00516
00517
00518 mp->ewma_level = 75;
00519
00520
00521 mp->segment_size = 6000;
00522
00523 if (hw->max_rate_tries > 0)
00524 mp->max_retry = hw->max_rate_tries;
00525 else
00526
00527 mp->max_retry = 7;
00528
00529 if (hw->max_rates >= 4)
00530 mp->has_mrr = true;
00531
00532 mp->hw = hw;
00533 mp->update_interval = 100;
00534
00535 #ifdef CONFIG_MAC80211_DEBUGFS
00536 mp->fixed_rate_idx = (u32) -1;
00537 mp->dbg_fixed_rate = debugfs_create_u32("fixed_rate_idx",
00538 S_IRUGO | S_IWUGO, debugfsdir, &mp->fixed_rate_idx);
00539 #endif
00540
00541 return mp;
00542 }
00543
00544 static void
00545 minstrel_free(void *priv)
00546 {
00547 #ifdef CONFIG_MAC80211_DEBUGFS
00548 debugfs_remove(((struct minstrel_priv *)priv)->dbg_fixed_rate);
00549 #endif
00550 kfree(priv);
00551 }
00552
00553 struct rate_control_ops mac80211_minstrel = {
00554 .name = "minstrel",
00555 .tx_status = minstrel_tx_status,
00556 .get_rate = minstrel_get_rate,
00557 .rate_init = minstrel_rate_init,
00558 .alloc = minstrel_alloc,
00559 .free = minstrel_free,
00560 .alloc_sta = minstrel_alloc_sta,
00561 .free_sta = minstrel_free_sta,
00562 #ifdef CONFIG_MAC80211_DEBUGFS
00563 .add_sta_debugfs = minstrel_add_sta_debugfs,
00564 .remove_sta_debugfs = minstrel_remove_sta_debugfs,
00565 #endif
00566 };
00567
00568 int __init
00569 rc80211_minstrel_init(void)
00570 {
00571 return ieee80211_rate_control_register(&mac80211_minstrel);
00572 }
00573
00574 void
00575 rc80211_minstrel_exit(void)
00576 {
00577 ieee80211_rate_control_unregister(&mac80211_minstrel);
00578 }
00579