#include "rate.h"
#include "rc80211_minstrel.h"
-#define SAMPLE_COLUMNS 10
#define SAMPLE_TBL(_mi, _idx, _col) \
_mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
return i;
}
+/* find & sort topmost throughput rates */
+static inline void
+minstrel_sort_best_tp_rates(struct minstrel_sta_info *mi, int i, u8 *tp_list)
+{
+ int j = MAX_THR_RATES;
+
+ while (j > 0 && mi->r[i].cur_tp > mi->r[tp_list[j - 1]].cur_tp)
+ j--;
+ if (j < MAX_THR_RATES - 1)
+ memmove(&tp_list[j + 1], &tp_list[j], MAX_THR_RATES - (j + 1));
+ if (j < MAX_THR_RATES)
+ tp_list[j] = i;
+}
+
+static void
+minstrel_set_rate(struct minstrel_sta_info *mi, struct ieee80211_sta_rates *ratetbl,
+ int offset, int idx)
+{
+ struct minstrel_rate *r = &mi->r[idx];
+
+ ratetbl->rate[offset].idx = r->rix;
+ ratetbl->rate[offset].count = r->adjusted_retry_count;
+ ratetbl->rate[offset].count_cts = r->retry_count_cts;
+ ratetbl->rate[offset].count_rts = r->retry_count_rtscts;
+}
+
+static void
+minstrel_update_rates(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
+{
+ struct ieee80211_sta_rates *ratetbl;
+ int i = 0;
+
+ ratetbl = kzalloc(sizeof(*ratetbl), GFP_ATOMIC);
+ if (!ratetbl)
+ return;
+
+ /* Start with max_tp_rate */
+ minstrel_set_rate(mi, ratetbl, i++, mi->max_tp_rate[0]);
+
+ if (mp->hw->max_rates >= 3) {
+ /* At least 3 tx rates supported, use max_tp_rate2 next */
+ minstrel_set_rate(mi, ratetbl, i++, mi->max_tp_rate[1]);
+ }
+
+ if (mp->hw->max_rates >= 2) {
+ /* At least 2 tx rates supported, use max_prob_rate next */
+ minstrel_set_rate(mi, ratetbl, i++, mi->max_prob_rate);
+ }
+
+ /* Use lowest rate last */
+ ratetbl->rate[i].idx = mi->lowest_rix;
+ ratetbl->rate[i].count = mp->max_retry;
+ ratetbl->rate[i].count_cts = mp->max_retry;
+ ratetbl->rate[i].count_rts = mp->max_retry;
+
+ rate_control_set_rates(mp->hw, mi->sta, ratetbl);
+}
+
static void
minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
{
- u32 max_tp = 0, index_max_tp = 0, index_max_tp2 = 0;
- u32 max_prob = 0, index_max_prob = 0;
+ u8 tmp_tp_rate[MAX_THR_RATES];
+ u8 tmp_prob_rate = 0;
u32 usecs;
- u32 p;
int i;
- mi->stats_update = jiffies;
+ for (i=0; i < MAX_THR_RATES; i++)
+ tmp_tp_rate[i] = 0;
+
for (i = 0; i < mi->n_rates; i++) {
struct minstrel_rate *mr = &mi->r[i];
if (!usecs)
usecs = 1000000;
- /* To avoid rounding issues, probabilities scale from 0 (0%)
- * to 18000 (100%) */
- if (mr->attempts) {
- p = (mr->success * 18000) / mr->attempts;
+ if (unlikely(mr->attempts > 0)) {
+ mr->sample_skipped = 0;
+ mr->cur_prob = MINSTREL_FRAC(mr->success, mr->attempts);
mr->succ_hist += mr->success;
mr->att_hist += mr->attempts;
- mr->cur_prob = p;
- p = ((p * (100 - mp->ewma_level)) + (mr->probability *
- mp->ewma_level)) / 100;
- mr->probability = p;
- mr->cur_tp = p * (1000000 / usecs);
- }
+ mr->probability = minstrel_ewma(mr->probability,
+ mr->cur_prob,
+ EWMA_LEVEL);
+ } else
+ mr->sample_skipped++;
mr->last_success = mr->success;
mr->last_attempts = mr->attempts;
mr->success = 0;
mr->attempts = 0;
+ /* Update throughput per rate, reset thr. below 10% success */
+ if (mr->probability < MINSTREL_FRAC(10, 100))
+ mr->cur_tp = 0;
+ else
+ mr->cur_tp = mr->probability * (1000000 / usecs);
+
/* Sample less often below the 10% chance of success.
* Sample less often above the 95% chance of success. */
- if ((mr->probability > 17100) || (mr->probability < 1800)) {
+ if (mr->probability > MINSTREL_FRAC(95, 100) ||
+ mr->probability < MINSTREL_FRAC(10, 100)) {
mr->adjusted_retry_count = mr->retry_count >> 1;
if (mr->adjusted_retry_count > 2)
mr->adjusted_retry_count = 2;
}
if (!mr->adjusted_retry_count)
mr->adjusted_retry_count = 2;
- }
- for (i = 0; i < mi->n_rates; i++) {
- struct minstrel_rate *mr = &mi->r[i];
- if (max_tp < mr->cur_tp) {
- index_max_tp = i;
- max_tp = mr->cur_tp;
- }
- if (max_prob < mr->probability) {
- index_max_prob = i;
- max_prob = mr->probability;
+ minstrel_sort_best_tp_rates(mi, i, tmp_tp_rate);
+
+ /* To determine the most robust rate (max_prob_rate) used at
+ * 3rd mmr stage we distinct between two cases:
+ * (1) if any success probabilitiy >= 95%, out of those rates
+ * choose the maximum throughput rate as max_prob_rate
+ * (2) if all success probabilities < 95%, the rate with
+ * highest success probability is choosen as max_prob_rate */
+ if (mr->probability >= MINSTREL_FRAC(95,100)) {
+ if (mr->cur_tp >= mi->r[tmp_prob_rate].cur_tp)
+ tmp_prob_rate = i;
+ } else {
+ if (mr->probability >= mi->r[tmp_prob_rate].probability)
+ tmp_prob_rate = i;
}
}
- max_tp = 0;
- for (i = 0; i < mi->n_rates; i++) {
- struct minstrel_rate *mr = &mi->r[i];
+ /* Assign the new rate set */
+ memcpy(mi->max_tp_rate, tmp_tp_rate, sizeof(mi->max_tp_rate));
+ mi->max_prob_rate = tmp_prob_rate;
- if (i == index_max_tp)
- continue;
+ /* Reset update timer */
+ mi->stats_update = jiffies;
- if (max_tp < mr->cur_tp) {
- index_max_tp2 = i;
- max_tp = mr->cur_tp;
- }
- }
- mi->max_tp_rate = index_max_tp;
- mi->max_tp_rate2 = index_max_tp2;
- mi->max_prob_rate = index_max_prob;
+ minstrel_update_rates(mp, mi);
}
static void
{
unsigned int retry = mr->adjusted_retry_count;
- if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_RTS_CTS)
+ if (info->control.use_rts)
retry = max(2U, min(mr->retry_count_rtscts, retry));
- else if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_CTS_PROTECT)
+ else if (info->control.use_cts_prot)
retry = max(2U, min(mr->retry_count_cts, retry));
return retry;
}
minstrel_get_next_sample(struct minstrel_sta_info *mi)
{
unsigned int sample_ndx;
- sample_ndx = SAMPLE_TBL(mi, mi->sample_idx, mi->sample_column);
- mi->sample_idx++;
- if ((int) mi->sample_idx > (mi->n_rates - 2)) {
- mi->sample_idx = 0;
+ sample_ndx = SAMPLE_TBL(mi, mi->sample_row, mi->sample_column);
+ mi->sample_row++;
+ if ((int) mi->sample_row >= mi->n_rates) {
+ mi->sample_row = 0;
mi->sample_column++;
if (mi->sample_column >= SAMPLE_COLUMNS)
mi->sample_column = 0;
struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
struct minstrel_sta_info *mi = priv_sta;
struct minstrel_priv *mp = priv;
- struct ieee80211_tx_rate *ar = info->control.rates;
- unsigned int ndx, sample_ndx = 0;
- bool mrr;
- bool sample_slower = false;
- bool sample = false;
- int i, delta;
- int mrr_ndx[3];
- int sample_rate;
-
+ struct ieee80211_tx_rate *rate = &info->control.rates[0];
+ struct minstrel_rate *msr, *mr;
+ unsigned int ndx;
+ bool mrr_capable;
+ bool prev_sample = mi->prev_sample;
+ int delta;
+ int sampling_ratio;
+
+ /* management/no-ack frames do not use rate control */
if (rate_control_send_low(sta, priv_sta, txrc))
return;
- mrr = mp->has_mrr && !txrc->rts && !txrc->bss_conf->use_cts_prot;
-
- ndx = mi->max_tp_rate;
-
- if (mrr)
- sample_rate = mp->lookaround_rate_mrr;
+ /* check multi-rate-retry capabilities & adjust lookaround_rate */
+ mrr_capable = mp->has_mrr &&
+ !txrc->rts &&
+ !txrc->bss_conf->use_cts_prot;
+ if (mrr_capable)
+ sampling_ratio = mp->lookaround_rate_mrr;
else
- sample_rate = mp->lookaround_rate;
+ sampling_ratio = mp->lookaround_rate;
+ /* increase sum packet counter */
mi->packet_count++;
- delta = (mi->packet_count * sample_rate / 100) -
+
+ delta = (mi->packet_count * sampling_ratio / 100) -
(mi->sample_count + mi->sample_deferred / 2);
- /* delta > 0: sampling required */
- if ((delta > 0) && (mrr || !mi->prev_sample)) {
- struct minstrel_rate *msr;
- if (mi->packet_count >= 10000) {
- mi->sample_deferred = 0;
- mi->sample_count = 0;
- mi->packet_count = 0;
- } else if (delta > mi->n_rates * 2) {
- /* With multi-rate retry, not every planned sample
- * attempt actually gets used, due to the way the retry
- * chain is set up - [max_tp,sample,prob,lowest] for
- * sample_rate < max_tp.
- *
- * If there's too much sampling backlog and the link
- * starts getting worse, minstrel would start bursting
- * out lots of sampling frames, which would result
- * in a large throughput loss. */
- mi->sample_count += (delta - mi->n_rates * 2);
- }
+ /* delta < 0: no sampling required */
+ mi->prev_sample = false;
+ if (delta < 0 || (!mrr_capable && prev_sample))
+ return;
- sample_ndx = minstrel_get_next_sample(mi);
- msr = &mi->r[sample_ndx];
- sample = true;
- sample_slower = mrr && (msr->perfect_tx_time >
- mi->r[ndx].perfect_tx_time);
-
- if (!sample_slower) {
- if (msr->sample_limit != 0) {
- ndx = sample_ndx;
- mi->sample_count++;
- if (msr->sample_limit > 0)
- msr->sample_limit--;
- } else {
- sample = false;
- }
- } else {
- /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
- * packets that have the sampling rate deferred to the
- * second MRR stage. Increase the sample counter only
- * if the deferred sample rate was actually used.
- * Use the sample_deferred counter to make sure that
- * the sampling is not done in large bursts */
- info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE;
- mi->sample_deferred++;
- }
+ if (mi->packet_count >= 10000) {
+ mi->sample_deferred = 0;
+ mi->sample_count = 0;
+ mi->packet_count = 0;
+ } else if (delta > mi->n_rates * 2) {
+ /* With multi-rate retry, not every planned sample
+ * attempt actually gets used, due to the way the retry
+ * chain is set up - [max_tp,sample,prob,lowest] for
+ * sample_rate < max_tp.
+ *
+ * If there's too much sampling backlog and the link
+ * starts getting worse, minstrel would start bursting
+ * out lots of sampling frames, which would result
+ * in a large throughput loss. */
+ mi->sample_count += (delta - mi->n_rates * 2);
+ }
+
+ /* get next random rate sample */
+ ndx = minstrel_get_next_sample(mi);
+ msr = &mi->r[ndx];
+ mr = &mi->r[mi->max_tp_rate[0]];
+
+ /* Decide if direct ( 1st mrr stage) or indirect (2nd mrr stage)
+ * rate sampling method should be used.
+ * Respect such rates that are not sampled for 20 interations.
+ */
+ if (mrr_capable &&
+ msr->perfect_tx_time > mr->perfect_tx_time &&
+ msr->sample_skipped < 20) {
+ /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
+ * packets that have the sampling rate deferred to the
+ * second MRR stage. Increase the sample counter only
+ * if the deferred sample rate was actually used.
+ * Use the sample_deferred counter to make sure that
+ * the sampling is not done in large bursts */
+ info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE;
+ rate++;
+ mi->sample_deferred++;
+ } else {
+ if (!msr->sample_limit != 0)
+ return;
+
+ mi->sample_count++;
+ if (msr->sample_limit > 0)
+ msr->sample_limit--;
}
- mi->prev_sample = sample;
/* If we're not using MRR and the sampling rate already
* has a probability of >95%, we shouldn't be attempting
* to use it, as this only wastes precious airtime */
- if (!mrr && sample && (mi->r[ndx].probability > 17100))
- ndx = mi->max_tp_rate;
-
- ar[0].idx = mi->r[ndx].rix;
- ar[0].count = minstrel_get_retry_count(&mi->r[ndx], info);
-
- if (!mrr) {
- if (!sample)
- ar[0].count = mp->max_retry;
- ar[1].idx = mi->lowest_rix;
- ar[1].count = mp->max_retry;
+ if (!mrr_capable &&
+ (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
return;
- }
- /* MRR setup */
- if (sample) {
- if (sample_slower)
- mrr_ndx[0] = sample_ndx;
- else
- mrr_ndx[0] = mi->max_tp_rate;
- } else {
- mrr_ndx[0] = mi->max_tp_rate2;
- }
- mrr_ndx[1] = mi->max_prob_rate;
- mrr_ndx[2] = 0;
- for (i = 1; i < 4; i++) {
- ar[i].idx = mi->r[mrr_ndx[i - 1]].rix;
- ar[i].count = mi->r[mrr_ndx[i - 1]].adjusted_retry_count;
- }
+ mi->prev_sample = true;
+
+ rate->idx = mi->r[ndx].rix;
+ rate->count = minstrel_get_retry_count(&mi->r[ndx], info);
}
init_sample_table(struct minstrel_sta_info *mi)
{
unsigned int i, col, new_idx;
- unsigned int n_srates = mi->n_rates - 1;
u8 rnd[8];
mi->sample_column = 0;
- mi->sample_idx = 0;
- memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates);
+ mi->sample_row = 0;
+ memset(mi->sample_table, 0xff, SAMPLE_COLUMNS * mi->n_rates);
for (col = 0; col < SAMPLE_COLUMNS; col++) {
- for (i = 0; i < n_srates; i++) {
+ for (i = 0; i < mi->n_rates; i++) {
get_random_bytes(rnd, sizeof(rnd));
- new_idx = (i + rnd[i & 7]) % n_srates;
+ new_idx = (i + rnd[i & 7]) % mi->n_rates;
- while (SAMPLE_TBL(mi, new_idx, col) != 0)
- new_idx = (new_idx + 1) % n_srates;
+ while (SAMPLE_TBL(mi, new_idx, col) != 0xff)
+ new_idx = (new_idx + 1) % mi->n_rates;
- /* Don't sample the slowest rate (i.e. slowest base
- * rate). We must presume that the slowest rate works
- * fine, or else other management frames will also be
- * failing and the link will break */
- SAMPLE_TBL(mi, new_idx, col) = i + 1;
+ SAMPLE_TBL(mi, new_idx, col) = i;
}
}
}
unsigned int i, n = 0;
unsigned int t_slot = 9; /* FIXME: get real slot time */
+ mi->sta = sta;
mi->lowest_rix = rate_lowest_index(sband, sta);
ctl_rate = &sband->bitrates[mi->lowest_rix];
mi->sp_ack_dur = ieee80211_frame_duration(sband->band, 10,
ctl_rate->bitrate,
!!(ctl_rate->flags & IEEE80211_RATE_ERP_G), 1);
+ memset(mi->max_tp_rate, 0, sizeof(mi->max_tp_rate));
+ mi->max_prob_rate = 0;
+
for (i = 0; i < sband->n_bitrates; i++) {
struct minstrel_rate *mr = &mi->r[n];
unsigned int tx_time = 0, tx_time_cts = 0, tx_time_rtscts = 0;
} while ((tx_time < mp->segment_size) &&
(++mr->retry_count < mp->max_retry));
mr->adjusted_retry_count = mr->retry_count;
+ if (!(sband->bitrates[i].flags & IEEE80211_RATE_ERP_G))
+ mr->retry_count_cts = mr->retry_count;
}
for (i = n; i < sband->n_bitrates; i++) {
mi->stats_update = jiffies;
init_sample_table(mi);
+ minstrel_update_rates(mp, mi);
}
static void *
mp->lookaround_rate = 5;
mp->lookaround_rate_mrr = 10;
- /* moving average weight for EWMA */
- mp->ewma_level = 75;
-
/* maximum time that the hw is allowed to stay in one MRR segment */
mp->segment_size = 6000;
git.openpandora.org / pandora-kernel.git / blobdiff