mac80211: merge upstream legacy minstrel improvements
authorFelix Fietkau <nbd@openwrt.org>
Mon, 15 Apr 2013 13:54:42 +0000 (13:54 +0000)
committerFelix Fietkau <nbd@openwrt.org>
Mon, 15 Apr 2013 13:54:42 +0000 (13:54 +0000)
Signed-off-by: Felix Fietkau <nbd@openwrt.org>
SVN-Revision: 36334

package/mac80211/patches/300-pending_work.patch

index a609c9a5e74f3c5da5cb3d8880254450cfa68936..a4bfb99b422e3a1c4f5015eddc19cf6e0f7519a7 100644 (file)
        rt2x00dev->hw->wiphy->flags |= WIPHY_FLAG_IBSS_RSN;
 --- a/net/mac80211/rc80211_minstrel_ht.c
 +++ b/net/mac80211/rc80211_minstrel_ht.c
-@@ -26,11 +26,11 @@
+@@ -17,8 +17,6 @@
+ #include "rc80211_minstrel_ht.h"
+ #define AVG_PKT_SIZE  1200
+-#define SAMPLE_COLUMNS        10
+-#define EWMA_LEVEL            75
+ /* Number of bits for an average sized packet */
+ #define MCS_NBITS (AVG_PKT_SIZE << 3)
+@@ -26,11 +24,11 @@
  /* Number of symbols for a packet with (bps) bits per symbol */
  #define MCS_NSYMS(bps) ((MCS_NBITS + (bps) - 1) / (bps))
  
        )
  
  /* Transmit duration for the raw data part of an average sized packet */
-@@ -64,9 +64,9 @@
+@@ -64,9 +62,9 @@
  }
  
  #define CCK_DURATION(_bitrate, _short, _len)          \
  
  #define CCK_ACK_DURATION(_bitrate, _short)                    \
        (CCK_DURATION((_bitrate > 10 ? 20 : 10), false, 60) +   \
-@@ -211,20 +211,32 @@ static void
+@@ -129,15 +127,6 @@ const struct mcs_group minstrel_mcs_grou
+ static u8 sample_table[SAMPLE_COLUMNS][MCS_GROUP_RATES];
+ /*
+- * Perform EWMA (Exponentially Weighted Moving Average) calculation
+- */
+-static int
+-minstrel_ewma(int old, int new, int weight)
+-{
+-      return (new * (100 - weight) + old * weight) / 100;
+-}
+-
+-/*
+  * Look up an MCS group index based on mac80211 rate information
+  */
+ static int
+@@ -211,20 +200,32 @@ static void
  minstrel_ht_calc_tp(struct minstrel_ht_sta *mi, int group, int rate)
  {
        struct minstrel_rate_stats *mr;
        if (group != MINSTREL_CCK_GROUP)
 -              usecs = mi->overhead / MINSTREL_TRUNC(mi->avg_ampdu_len);
 +              nsecs = 1000 * mi->overhead / MINSTREL_TRUNC(mi->avg_ampdu_len);
++
++      nsecs += minstrel_mcs_groups[group].duration[rate];
++      tp = 1000000 * ((mr->probability * 1000) / nsecs);
  
 -      usecs += minstrel_mcs_groups[group].duration[rate];
 -      mr->cur_tp = MINSTREL_TRUNC((1000000 / usecs) * mr->probability);
-+      nsecs += minstrel_mcs_groups[group].duration[rate];
-+      tp = 1000000 * ((mr->probability * 1000) / nsecs);
-+
 +      mr->cur_tp = MINSTREL_TRUNC(tp);
  }
  
  /*
-@@ -308,8 +320,8 @@ minstrel_ht_update_stats(struct minstrel
+@@ -308,8 +309,8 @@ minstrel_ht_update_stats(struct minstrel
                }
        }
  
  
        cur_prob = 0;
        cur_prob_tp = 0;
-@@ -320,20 +332,13 @@ minstrel_ht_update_stats(struct minstrel
+@@ -320,20 +321,13 @@ minstrel_ht_update_stats(struct minstrel
                if (!mg->supported)
                        continue;
  
                }
  
                mr = minstrel_get_ratestats(mi, mg->max_tp_rate2);
-@@ -343,6 +348,23 @@ minstrel_ht_update_stats(struct minstrel
+@@ -343,6 +337,23 @@ minstrel_ht_update_stats(struct minstrel
                }
        }
  
        mi->stats_update = jiffies;
  }
  
-@@ -467,7 +489,7 @@ minstrel_ht_tx_status(void *priv, struct
+@@ -467,7 +478,7 @@ minstrel_ht_tx_status(void *priv, struct
  
        if (!mi->sample_wait && !mi->sample_tries && mi->sample_count > 0) {
                mi->sample_wait = 16 + 2 * MINSTREL_TRUNC(mi->avg_ampdu_len);
                mi->sample_count--;
        }
  
-@@ -536,7 +558,7 @@ minstrel_calc_retransmit(struct minstrel
+@@ -536,7 +547,7 @@ minstrel_calc_retransmit(struct minstrel
        mr->retry_updated = true;
  
        group = &minstrel_mcs_groups[index / MCS_GROUP_RATES];
  
        /* Contention time for first 2 tries */
        ctime = (t_slot * cw) >> 1;
-@@ -616,6 +638,7 @@ minstrel_get_sample_rate(struct minstrel
+@@ -616,6 +627,7 @@ minstrel_get_sample_rate(struct minstrel
  {
        struct minstrel_rate_stats *mr;
        struct minstrel_mcs_group_data *mg;
        int sample_idx = 0;
  
        if (mi->sample_wait > 0) {
-@@ -626,39 +649,46 @@ minstrel_get_sample_rate(struct minstrel
+@@ -626,39 +638,46 @@ minstrel_get_sample_rate(struct minstrel
        if (!mi->sample_tries)
                return -1;
  
  }
 --- a/net/mac80211/rc80211_minstrel_ht.h
 +++ b/net/mac80211/rc80211_minstrel_ht.h
-@@ -85,6 +85,7 @@ struct minstrel_ht_sta {
+@@ -16,11 +16,6 @@
+ #define MINSTREL_MAX_STREAMS  3
+ #define MINSTREL_STREAM_GROUPS        4
+-/* scaled fraction values */
+-#define MINSTREL_SCALE        16
+-#define MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
+-#define MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
+-
+ #define MCS_GROUP_RATES       8
+ struct mcs_group {
+@@ -85,6 +80,7 @@ struct minstrel_ht_sta {
  
        /* best probability rate */
        unsigned int max_prob_rate;
  
        if (ifmgd->auth_data && !ifmgd->auth_data->done) {
                err = -EBUSY;
+--- 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,
+       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_pr
+               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_pr
+               }
+               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 iee
+       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 iee
+                       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);
++              rate_sampling = true;
+-              if (!sample_slower) {
++              /* 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 iee
+                       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, 
+       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;
+--- a/net/mac80211/rc80211_minstrel.h
++++ b/net/mac80211/rc80211_minstrel.h
+@@ -9,6 +9,28 @@
+ #ifndef __RC_MINSTREL_H
+ #define __RC_MINSTREL_H
++#define EWMA_LEVEL    75      /* ewma weighting factor [%] */
++#define SAMPLE_COLUMNS        10      /* number of columns in sample table */
++
++
++/* scaled fraction values */
++#define MINSTREL_SCALE  16
++#define MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
++#define MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
++
++/* number of highest throughput rates to consider*/
++#define MAX_THR_RATES 4
++
++/*
++ * Perform EWMA (Exponentially Weighted Moving Average) calculation
++  */
++static inline int
++minstrel_ewma(int old, int new, int weight)
++{
++      return (new * (100 - weight) + old * weight) / 100;
++}
++
++
+ struct minstrel_rate {
+       int bitrate;
+       int rix;
+@@ -26,6 +48,7 @@ struct minstrel_rate {
+       u32 attempts;
+       u32 last_attempts;
+       u32 last_success;
++      u8 sample_skipped;
+       /* parts per thousand */
+       u32 cur_prob;
+@@ -45,14 +68,13 @@ struct minstrel_sta_info {
+       unsigned int lowest_rix;
+-      unsigned int max_tp_rate;
+-      unsigned int max_tp_rate2;
+-      unsigned int max_prob_rate;
++      u8 max_tp_rate[MAX_THR_RATES];
++      u8 max_prob_rate;
+       unsigned int packet_count;
+       unsigned int sample_count;
+       int sample_deferred;
+-      unsigned int sample_idx;
++      unsigned int sample_row;
+       unsigned int sample_column;
+       int n_rates;
+@@ -73,7 +95,6 @@ struct minstrel_priv {
+       unsigned int cw_min;
+       unsigned int cw_max;
+       unsigned int max_retry;
+-      unsigned int ewma_level;
+       unsigned int segment_size;
+       unsigned int update_interval;
+       unsigned int lookaround_rate;
+--- a/net/mac80211/rc80211_minstrel_debugfs.c
++++ b/net/mac80211/rc80211_minstrel_debugfs.c
+@@ -73,15 +73,17 @@ minstrel_stats_open(struct inode *inode,
+       for (i = 0; i < mi->n_rates; i++) {
+               struct minstrel_rate *mr = &mi->r[i];
+-              *(p++) = (i == mi->max_tp_rate) ? 'T' : ' ';
+-              *(p++) = (i == mi->max_tp_rate2) ? 't' : ' ';
++              *(p++) = (i == mi->max_tp_rate[0]) ? 'A' : ' ';
++              *(p++) = (i == mi->max_tp_rate[1]) ? 'B' : ' ';
++              *(p++) = (i == mi->max_tp_rate[2]) ? 'C' : ' ';
++              *(p++) = (i == mi->max_tp_rate[3]) ? 'D' : ' ';
+               *(p++) = (i == mi->max_prob_rate) ? 'P' : ' ';
+               p += sprintf(p, "%3u%s", mr->bitrate / 2,
+                               (mr->bitrate & 1 ? ".5" : "  "));
+-              tp = mr->cur_tp / ((18000 << 10) / 96);
+-              prob = mr->cur_prob / 18;
+-              eprob = mr->probability / 18;
++              tp = MINSTREL_TRUNC(mr->cur_tp / 10);
++              prob = MINSTREL_TRUNC(mr->cur_prob * 1000);
++              eprob = MINSTREL_TRUNC(mr->probability * 1000);
+               p += sprintf(p, "  %6u.%1u   %6u.%1u   %6u.%1u        "
+                               "%3u(%3u)   %8llu    %8llu\n",