1 files changed, 114 insertions, 90 deletions

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index eea45a2c7c35..1c36c9b4fa4a 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -55,7 +55,6 @@
 #include "rate.h"
 #include "rc80211_minstrel.h"
 
-#define SAMPLE_COLUMNS  10
 #define SAMPLE_TBL(_mi, _idx, _col) \
                 _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col]
 
@@ -70,16 +69,31 @@ rix_to_ndx(struct minstrel_sta_info *mi, int rix)
         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_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];
 
@@ -87,27 +101,32 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
                 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;
@@ -118,35 +137,30 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
                 }
                 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];
-
-                if (i == index_max_tp)
-                        continue;
+        /* 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 (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;
+        /* Reset update timer */
+        mi->stats_update = jiffies;
 }
 
 static void
@@ -207,10 +221,10 @@ static int
 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;
@@ -228,31 +242,37 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *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;
+        bool mrr_capable;
+        bool indirect_rate_sampling = false;
+        bool rate_sampling = false;
         int i, delta;
         int mrr_ndx[3];
-        int sample_rate;
+        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;
+
+        /* init rateindex [ndx] with max throughput rate */
+        ndx = mi->max_tp_rate[0];
 
+        /* 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)) {
+        if ((delta > 0) && (mrr_capable || !mi->prev_sample)) {
                 struct minstrel_rate *msr;
                 if (mi->packet_count >= 10000) {
                         mi->sample_deferred = 0;
@@ -271,21 +291,28 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
                         mi->sample_count += (delta - mi->n_rates * 2);
                 }
 
+                /* get next random rate sample */
                 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) {
+                rate_sampling = true;
+
+                /* 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 > mi->r[ndx].perfect_tx_time &&
+                    msr->sample_skipped < 20)
+                                indirect_rate_sampling = true;
+
+                if (!indirect_rate_sampling) {
                         if (msr->sample_limit != 0) {
                                 ndx = sample_ndx;
                                 mi->sample_count++;
                                 if (msr->sample_limit > 0)
                                         msr->sample_limit--;
-                        } else {
-                                sample = false;
-                        }
+                        } else
+                                rate_sampling = false;
                 } else {
                         /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark
                          * packets that have the sampling rate deferred to the
@@ -297,34 +324,39 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta,
                         mi->sample_deferred++;
                 }
         }
-        mi->prev_sample = sample;
+        mi->prev_sample = rate_sampling;
 
         /* 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;
+        if (!mrr_capable && rate_sampling &&
+           (mi->r[ndx].probability > MINSTREL_FRAC(95, 100)))
+                ndx = mi->max_tp_rate[0];
 
+        /* mrr setup for 1st stage */
         ar[0].idx = mi->r[ndx].rix;
         ar[0].count = minstrel_get_retry_count(&mi->r[ndx], info);
 
-        if (!mrr) {
-                if (!sample)
+        /* non mrr setup for 2nd stage */
+        if (!mrr_capable) {
+                if (!rate_sampling)
                         ar[0].count = mp->max_retry;
                 ar[1].idx = mi->lowest_rix;
                 ar[1].count = mp->max_retry;
                 return;
         }
 
-        /* MRR setup */
-        if (sample) {
-                if (sample_slower)
+        /* mrr setup for 2nd stage */
+        if (rate_sampling) {
+                if (indirect_rate_sampling)
                         mrr_ndx[0] = sample_ndx;
                 else
-                        mrr_ndx[0] = mi->max_tp_rate;
+                        mrr_ndx[0] = mi->max_tp_rate[0];
         } else {
-                mrr_ndx[0] = mi->max_tp_rate2;
+                mrr_ndx[0] = mi->max_tp_rate[1];
         }
+
+        /* mrr setup for 3rd & 4th stage */
         mrr_ndx[1] = mi->max_prob_rate;
         mrr_ndx[2] = 0;
         for (i = 1; i < 4; i++) {
@@ -351,26 +383,21 @@ static void
 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;
                 }
         }
 }
@@ -542,9 +569,6 @@ minstrel_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
         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;