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_TBL(_mi, _idx, _col) \ 59 _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col] 60 61/* convert mac80211 rate index to local array index */ 62static inline int 63rix_to_ndx(struct minstrel_sta_info *mi, int rix) 64{ 65 int i = rix; 66 for (i = rix; i >= 0; i--) 67 if (mi->r[i].rix == rix) 68 break; 69 return i; 70} 71 72/* return current EMWA throughput */ 73int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_avg) 74{ 75 int usecs; 76 77 usecs = mr->perfect_tx_time; 78 if (!usecs) 79 usecs = 1000000; 80 81 /* reset thr. below 10% success */ 82 if (mr->stats.prob_avg < MINSTREL_FRAC(10, 100)) 83 return 0; 84 85 if (prob_avg > MINSTREL_FRAC(90, 100)) 86 return MINSTREL_TRUNC(100000 * (MINSTREL_FRAC(90, 100) / usecs)); 87 else 88 return MINSTREL_TRUNC(100000 * (prob_avg / usecs)); 89} 90 91/* find & sort topmost throughput rates */ 92static inline void 93minstrel_sort_best_tp_rates(struct minstrel_sta_info *mi, int i, u8 *tp_list) 94{ 95 int j; 96 struct minstrel_rate_stats *tmp_mrs; 97 struct minstrel_rate_stats *cur_mrs = &mi->r[i].stats; 98 99 for (j = MAX_THR_RATES; j > 0; --j) { 100 tmp_mrs = &mi->r[tp_list[j - 1]].stats; 101 if (minstrel_get_tp_avg(&mi->r[i], cur_mrs->prob_avg) <= 102 minstrel_get_tp_avg(&mi->r[tp_list[j - 1]], tmp_mrs->prob_avg)) 103 break; 104 } 105 106 if (j < MAX_THR_RATES - 1) 107 memmove(&tp_list[j + 1], &tp_list[j], MAX_THR_RATES - (j + 1)); 108 if (j < MAX_THR_RATES) 109 tp_list[j] = i; 110} 111 112static void 113minstrel_set_rate(struct minstrel_sta_info *mi, struct ieee80211_sta_rates *ratetbl, 114 int offset, int idx) 115{ 116 struct minstrel_rate *r = &mi->r[idx]; 117 118 ratetbl->rate[offset].idx = r->rix; 119 ratetbl->rate[offset].count = r->adjusted_retry_count; 120 ratetbl->rate[offset].count_cts = r->retry_count_cts; 121 ratetbl->rate[offset].count_rts = r->stats.retry_count_rtscts; 122} 123 124static void 125minstrel_update_rates(struct minstrel_priv *mp, struct minstrel_sta_info *mi) 126{ 127 struct ieee80211_sta_rates *ratetbl; 128 int i = 0; 129 130 ratetbl = kzalloc(sizeof(*ratetbl), GFP_ATOMIC); 131 if (!ratetbl) 132 return; 133 134 /* Start with max_tp_rate */ 135 minstrel_set_rate(mi, ratetbl, i++, mi->max_tp_rate[0]); 136 137 if (mp->hw->max_rates >= 3) { 138 /* At least 3 tx rates supported, use max_tp_rate2 next */ 139 minstrel_set_rate(mi, ratetbl, i++, mi->max_tp_rate[1]); 140 } 141 142 if (mp->hw->max_rates >= 2) { 143 /* At least 2 tx rates supported, use max_prob_rate next */ 144 minstrel_set_rate(mi, ratetbl, i++, mi->max_prob_rate); 145 } 146 147 /* Use lowest rate last */ 148 ratetbl->rate[i].idx = mi->lowest_rix; 149 ratetbl->rate[i].count = mp->max_retry; 150 ratetbl->rate[i].count_cts = mp->max_retry; 151 ratetbl->rate[i].count_rts = mp->max_retry; 152 153 rate_control_set_rates(mp->hw, mi->sta, ratetbl); 154} 155 156/* 157* Recalculate statistics and counters of a given rate 158*/ 159void 160minstrel_calc_rate_stats(struct minstrel_priv *mp, 161 struct minstrel_rate_stats *mrs) 162{ 163 unsigned int cur_prob; 164 165 if (unlikely(mrs->attempts > 0)) { 166 mrs->sample_skipped = 0; 167 cur_prob = MINSTREL_FRAC(mrs->success, mrs->attempts); 168 if (mp->new_avg) { 169 minstrel_filter_avg_add(&mrs->prob_avg, 170 &mrs->prob_avg_1, cur_prob); 171 } else if (unlikely(!mrs->att_hist)) { 172 mrs->prob_avg = cur_prob; 173 } else { 174 /*update exponential weighted moving avarage */ 175 mrs->prob_avg = minstrel_ewma(mrs->prob_avg, 176 cur_prob, 177 EWMA_LEVEL); 178 } 179 mrs->att_hist += mrs->attempts; 180 mrs->succ_hist += mrs->success; 181 } else { 182 mrs->sample_skipped++; 183 } 184 185 mrs->last_success = mrs->success; 186 mrs->last_attempts = mrs->attempts; 187 mrs->success = 0; 188 mrs->attempts = 0; 189} 190 191static void 192minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi) 193{ 194 u8 tmp_tp_rate[MAX_THR_RATES]; 195 u8 tmp_prob_rate = 0; 196 int i, tmp_cur_tp, tmp_prob_tp; 197 198 for (i = 0; i < MAX_THR_RATES; i++) 199 tmp_tp_rate[i] = 0; 200 201 for (i = 0; i < mi->n_rates; i++) { 202 struct minstrel_rate *mr = &mi->r[i]; 203 struct minstrel_rate_stats *mrs = &mi->r[i].stats; 204 struct minstrel_rate_stats *tmp_mrs = &mi->r[tmp_prob_rate].stats; 205 206 /* Update statistics of success probability per rate */ 207 minstrel_calc_rate_stats(mp, mrs); 208 209 /* Sample less often below the 10% chance of success. 210 * Sample less often above the 95% chance of success. */ 211 if (mrs->prob_avg > MINSTREL_FRAC(95, 100) || 212 mrs->prob_avg < MINSTREL_FRAC(10, 100)) { 213 mr->adjusted_retry_count = mrs->retry_count >> 1; 214 if (mr->adjusted_retry_count > 2) 215 mr->adjusted_retry_count = 2; 216 mr->sample_limit = 4; 217 } else { 218 mr->sample_limit = -1; 219 mr->adjusted_retry_count = mrs->retry_count; 220 } 221 if (!mr->adjusted_retry_count) 222 mr->adjusted_retry_count = 2; 223 224 minstrel_sort_best_tp_rates(mi, i, tmp_tp_rate); 225 226 /* To determine the most robust rate (max_prob_rate) used at 227 * 3rd mmr stage we distinct between two cases: 228 * (1) if any success probabilitiy >= 95%, out of those rates 229 * choose the maximum throughput rate as max_prob_rate 230 * (2) if all success probabilities < 95%, the rate with 231 * highest success probability is chosen as max_prob_rate */ 232 if (mrs->prob_avg >= MINSTREL_FRAC(95, 100)) { 233 tmp_cur_tp = minstrel_get_tp_avg(mr, mrs->prob_avg); 234 tmp_prob_tp = minstrel_get_tp_avg(&mi->r[tmp_prob_rate], 235 tmp_mrs->prob_avg); 236 if (tmp_cur_tp >= tmp_prob_tp) 237 tmp_prob_rate = i; 238 } else { 239 if (mrs->prob_avg >= tmp_mrs->prob_avg) 240 tmp_prob_rate = i; 241 } 242 } 243 244 /* Assign the new rate set */ 245 memcpy(mi->max_tp_rate, tmp_tp_rate, sizeof(mi->max_tp_rate)); 246 mi->max_prob_rate = tmp_prob_rate; 247 248#ifdef CONFIG_MAC80211_DEBUGFS 249 /* use fixed index if set */ 250 if (mp->fixed_rate_idx != -1) { 251 mi->max_tp_rate[0] = mp->fixed_rate_idx; 252 mi->max_tp_rate[1] = mp->fixed_rate_idx; 253 mi->max_prob_rate = mp->fixed_rate_idx; 254 } 255#endif 256 257 /* Reset update timer */ 258 mi->last_stats_update = jiffies; 259 260 minstrel_update_rates(mp, mi); 261} 262 263static void 264minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband, 265 void *priv_sta, struct ieee80211_tx_status *st) 266{ 267 struct ieee80211_tx_info *info = st->info; 268 struct minstrel_priv *mp = priv; 269 struct minstrel_sta_info *mi = priv_sta; 270 struct ieee80211_tx_rate *ar = info->status.rates; 271 int i, ndx; 272 int success; 273 274 success = !!(info->flags & IEEE80211_TX_STAT_ACK); 275 276 for (i = 0; i < IEEE80211_TX_MAX_RATES; i++) { 277 if (ar[i].idx < 0 || !ar[i].count) 278 break; 279 280 ndx = rix_to_ndx(mi, ar[i].idx); 281 if (ndx < 0) 282 continue; 283 284 mi->r[ndx].stats.attempts += ar[i].count; 285 286 if ((i != IEEE80211_TX_MAX_RATES - 1) && (ar[i + 1].idx < 0)) 287 mi->r[ndx].stats.success += success; 288 } 289 290 if (time_after(jiffies, mi->last_stats_update + 291 mp->update_interval / (mp->new_avg ? 2 : 1))) 292 minstrel_update_stats(mp, mi); 293} 294 295 296static inline unsigned int 297minstrel_get_retry_count(struct minstrel_rate *mr, 298 struct ieee80211_tx_info *info) 299{ 300 u8 retry = mr->adjusted_retry_count; 301 302 if (info->control.use_rts) 303 retry = max_t(u8, 2, min(mr->stats.retry_count_rtscts, retry)); 304 else if (info->control.use_cts_prot) 305 retry = max_t(u8, 2, min(mr->retry_count_cts, retry)); 306 return retry; 307} 308 309 310static int 311minstrel_get_next_sample(struct minstrel_sta_info *mi) 312{ 313 unsigned int sample_ndx; 314 sample_ndx = SAMPLE_TBL(mi, mi->sample_row, mi->sample_column); 315 mi->sample_row++; 316 if ((int) mi->sample_row >= mi->n_rates) { 317 mi->sample_row = 0; 318 mi->sample_column++; 319 if (mi->sample_column >= SAMPLE_COLUMNS) 320 mi->sample_column = 0; 321 } 322 return sample_ndx; 323} 324 325static void 326minstrel_get_rate(void *priv, struct ieee80211_sta *sta, 327 void *priv_sta, struct ieee80211_tx_rate_control *txrc) 328{ 329 struct sk_buff *skb = txrc->skb; 330 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb); 331 struct minstrel_sta_info *mi = priv_sta; 332 struct minstrel_priv *mp = priv; 333 struct ieee80211_tx_rate *rate = &info->control.rates[0]; 334 struct minstrel_rate *msr, *mr; 335 unsigned int ndx; 336 bool mrr_capable; 337 bool prev_sample; 338 int delta; 339 int sampling_ratio; 340 341 /* check multi-rate-retry capabilities & adjust lookaround_rate */ 342 mrr_capable = mp->has_mrr && 343 !txrc->rts && 344 !txrc->bss_conf->use_cts_prot; 345 if (mrr_capable) 346 sampling_ratio = mp->lookaround_rate_mrr; 347 else 348 sampling_ratio = mp->lookaround_rate; 349 350 /* increase sum packet counter */ 351 mi->total_packets++; 352 353#ifdef CONFIG_MAC80211_DEBUGFS 354 if (mp->fixed_rate_idx != -1) 355 return; 356#endif 357 358 /* Don't use EAPOL frames for sampling on non-mrr hw */ 359 if (mp->hw->max_rates == 1 && 360 (info->control.flags & IEEE80211_TX_CTRL_PORT_CTRL_PROTO)) 361 return; 362 363 delta = (mi->total_packets * sampling_ratio / 100) - 364 mi->sample_packets; 365 366 /* delta < 0: no sampling required */ 367 prev_sample = mi->prev_sample; 368 mi->prev_sample = false; 369 if (delta < 0 || (!mrr_capable && prev_sample)) 370 return; 371 372 if (mi->total_packets >= 10000) { 373 mi->sample_packets = 0; 374 mi->total_packets = 0; 375 } else if (delta > mi->n_rates * 2) { 376 /* With multi-rate retry, not every planned sample 377 * attempt actually gets used, due to the way the retry 378 * chain is set up - [max_tp,sample,prob,lowest] for 379 * sample_rate < max_tp. 380 * 381 * If there's too much sampling backlog and the link 382 * starts getting worse, minstrel would start bursting 383 * out lots of sampling frames, which would result 384 * in a large throughput loss. */ 385 mi->sample_packets += (delta - mi->n_rates * 2); 386 } 387 388 /* get next random rate sample */ 389 ndx = minstrel_get_next_sample(mi); 390 msr = &mi->r[ndx]; 391 mr = &mi->r[mi->max_tp_rate[0]]; 392 393 /* Decide if direct ( 1st mrr stage) or indirect (2nd mrr stage) 394 * rate sampling method should be used. 395 * Respect such rates that are not sampled for 20 interations. 396 */ 397 if (msr->perfect_tx_time < mr->perfect_tx_time || 398 msr->stats.sample_skipped >= 20) { 399 if (!msr->sample_limit) 400 return; 401 402 mi->sample_packets++; 403 if (msr->sample_limit > 0) 404 msr->sample_limit--; 405 } 406 407 /* If we're not using MRR and the sampling rate already 408 * has a probability of >95%, we shouldn't be attempting 409 * to use it, as this only wastes precious airtime */ 410 if (!mrr_capable && 411 (mi->r[ndx].stats.prob_avg > MINSTREL_FRAC(95, 100))) 412 return; 413 414 mi->prev_sample = true; 415 416 rate->idx = mi->r[ndx].rix; 417 rate->count = minstrel_get_retry_count(&mi->r[ndx], info); 418 info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE; 419} 420 421 422static void 423calc_rate_durations(enum nl80211_band band, 424 struct minstrel_rate *d, 425 struct ieee80211_rate *rate, 426 struct cfg80211_chan_def *chandef) 427{ 428 int erp = !!(rate->flags & IEEE80211_RATE_ERP_G); 429 int shift = ieee80211_chandef_get_shift(chandef); 430 431 d->perfect_tx_time = ieee80211_frame_duration(band, 1200, 432 DIV_ROUND_UP(rate->bitrate, 1 << shift), erp, 1, 433 shift); 434 d->ack_time = ieee80211_frame_duration(band, 10, 435 DIV_ROUND_UP(rate->bitrate, 1 << shift), erp, 1, 436 shift); 437} 438 439static void 440init_sample_table(struct minstrel_sta_info *mi) 441{ 442 unsigned int i, col, new_idx; 443 u8 rnd[8]; 444 445 mi->sample_column = 0; 446 mi->sample_row = 0; 447 memset(mi->sample_table, 0xff, SAMPLE_COLUMNS * mi->n_rates); 448 449 for (col = 0; col < SAMPLE_COLUMNS; col++) { 450 prandom_bytes(rnd, sizeof(rnd)); 451 for (i = 0; i < mi->n_rates; i++) { 452 new_idx = (i + rnd[i & 7]) % mi->n_rates; 453 while (SAMPLE_TBL(mi, new_idx, col) != 0xff) 454 new_idx = (new_idx + 1) % mi->n_rates; 455 456 SAMPLE_TBL(mi, new_idx, col) = i; 457 } 458 } 459} 460 461static void 462minstrel_rate_init(void *priv, struct ieee80211_supported_band *sband, 463 struct cfg80211_chan_def *chandef, 464 struct ieee80211_sta *sta, void *priv_sta) 465{ 466 struct minstrel_sta_info *mi = priv_sta; 467 struct minstrel_priv *mp = priv; 468 struct ieee80211_rate *ctl_rate; 469 unsigned int i, n = 0; 470 unsigned int t_slot = 9; /* FIXME: get real slot time */ 471 u32 rate_flags; 472 473 mi->sta = sta; 474 mi->lowest_rix = rate_lowest_index(sband, sta); 475 ctl_rate = &sband->bitrates[mi->lowest_rix]; 476 mi->sp_ack_dur = ieee80211_frame_duration(sband->band, 10, 477 ctl_rate->bitrate, 478 !!(ctl_rate->flags & IEEE80211_RATE_ERP_G), 1, 479 ieee80211_chandef_get_shift(chandef)); 480 481 rate_flags = ieee80211_chandef_rate_flags(&mp->hw->conf.chandef); 482 memset(mi->max_tp_rate, 0, sizeof(mi->max_tp_rate)); 483 mi->max_prob_rate = 0; 484 485 for (i = 0; i < sband->n_bitrates; i++) { 486 struct minstrel_rate *mr = &mi->r[n]; 487 struct minstrel_rate_stats *mrs = &mi->r[n].stats; 488 unsigned int tx_time = 0, tx_time_cts = 0, tx_time_rtscts = 0; 489 unsigned int tx_time_single; 490 unsigned int cw = mp->cw_min; 491 int shift; 492 493 if (!rate_supported(sta, sband->band, i)) 494 continue; 495 if ((rate_flags & sband->bitrates[i].flags) != rate_flags) 496 continue; 497 498 n++; 499 memset(mr, 0, sizeof(*mr)); 500 memset(mrs, 0, sizeof(*mrs)); 501 502 mr->rix = i; 503 shift = ieee80211_chandef_get_shift(chandef); 504 mr->bitrate = DIV_ROUND_UP(sband->bitrates[i].bitrate, 505 (1 << shift) * 5); 506 calc_rate_durations(sband->band, mr, &sband->bitrates[i], 507 chandef); 508 509 /* calculate maximum number of retransmissions before 510 * fallback (based on maximum segment size) */ 511 mr->sample_limit = -1; 512 mrs->retry_count = 1; 513 mr->retry_count_cts = 1; 514 mrs->retry_count_rtscts = 1; 515 tx_time = mr->perfect_tx_time + mi->sp_ack_dur; 516 do { 517 /* add one retransmission */ 518 tx_time_single = mr->ack_time + mr->perfect_tx_time; 519 520 /* contention window */ 521 tx_time_single += (t_slot * cw) >> 1; 522 cw = min((cw << 1) | 1, mp->cw_max); 523 524 tx_time += tx_time_single; 525 tx_time_cts += tx_time_single + mi->sp_ack_dur; 526 tx_time_rtscts += tx_time_single + 2 * mi->sp_ack_dur; 527 if ((tx_time_cts < mp->segment_size) && 528 (mr->retry_count_cts < mp->max_retry)) 529 mr->retry_count_cts++; 530 if ((tx_time_rtscts < mp->segment_size) && 531 (mrs->retry_count_rtscts < mp->max_retry)) 532 mrs->retry_count_rtscts++; 533 } while ((tx_time < mp->segment_size) && 534 (++mr->stats.retry_count < mp->max_retry)); 535 mr->adjusted_retry_count = mrs->retry_count; 536 if (!(sband->bitrates[i].flags & IEEE80211_RATE_ERP_G)) 537 mr->retry_count_cts = mrs->retry_count; 538 } 539 540 for (i = n; i < sband->n_bitrates; i++) { 541 struct minstrel_rate *mr = &mi->r[i]; 542 mr->rix = -1; 543 } 544 545 mi->n_rates = n; 546 mi->last_stats_update = jiffies; 547 548 init_sample_table(mi); 549 minstrel_update_rates(mp, mi); 550} 551 552static u32 minstrel_get_expected_throughput(void *priv_sta) 553{ 554 struct minstrel_sta_info *mi = priv_sta; 555 struct minstrel_rate_stats *tmp_mrs; 556 int idx = mi->max_tp_rate[0]; 557 int tmp_cur_tp; 558 559 /* convert pkt per sec in kbps (1200 is the average pkt size used for 560 * computing cur_tp 561 */ 562 tmp_mrs = &mi->r[idx].stats; 563 tmp_cur_tp = minstrel_get_tp_avg(&mi->r[idx], tmp_mrs->prob_avg) * 10; 564 tmp_cur_tp = tmp_cur_tp * 1200 * 8 / 1024; 565 566 return tmp_cur_tp; 567} 568 569const struct rate_control_ops mac80211_minstrel = { 570 .tx_status_ext = minstrel_tx_status, 571 .get_rate = minstrel_get_rate, 572 .rate_init = minstrel_rate_init, 573 .get_expected_throughput = minstrel_get_expected_throughput, 574}; 575