git.librecmc.org Git - oweals/openwrt.git/blob

   1 From: Felix Fietkau <nbd@nbd.name>
   2 Date: Sat, 28 Sep 2019 15:46:06 +0200
   3 Subject: [PATCH] mac80211: minstrel_ht: replace rate stats ewma with a
   4  better moving average
   5
   6 Rate success probability usually fluctuates a lot under normal conditions.
   7 With a simple EWMA, noise and fluctuation can be reduced by increasing the
   8 window length, but that comes at the cost of introducing lag on sudden
   9 changes.
  10
  11 This change replaces the EWMA implementation with a moving average that's
  12 designed to significantly reduce lag while keeping a bigger window size
  13 by being better at filtering out noise.
  14
  15 It is only slightly more expensive than the simple EWMA and still avoids
  16 divisions in its calculation.
  17
  18 The algorithm is adapted from an implementation intended for a completely
  19 different field (stock market trading), where the tradeoff of lag vs
  20 noise filtering is equally important.
  21
  22 The algorithm works in the same way as the "smoothing filter" from
  23 http://www.stockspotter.com/files/PredictiveIndicators.pdf adapted for
  24 fixed-point math with some constants, using only addition, bit shifts
  25 and multiplication
  26
  27 To better make use of the filtering and bigger window size, the update
  28 interval is cut in half.
  29
  30 For testing, the algorithm can be reverted to the older one via debugfs
  31
  32 Signed-off-by: Felix Fietkau <nbd@nbd.name>
  33 ---
  34
  35 --- a/net/mac80211/rc80211_minstrel.c
  36 +++ b/net/mac80211/rc80211_minstrel.c
  37 @@ -157,14 +157,18 @@ minstrel_update_rates(struct minstrel_pr
  38  * Recalculate statistics and counters of a given rate
  39  */
  40  void
  41 -minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs)
  42 +minstrel_calc_rate_stats(struct minstrel_priv *mp,
  43 +                        struct minstrel_rate_stats *mrs)
  44  {
  45         unsigned int cur_prob;
  46
  47         if (unlikely(mrs->attempts > 0)) {
  48                 mrs->sample_skipped = 0;
  49                 cur_prob = MINSTREL_FRAC(mrs->success, mrs->attempts);
  50 -               if (unlikely(!mrs->att_hist)) {
  51 +               if (mp->new_avg) {
  52 +                       mrs->prob_ewma = minstrel_filter_avg_add(&mrs->avg,
  53 +                                                                cur_prob);
  54 +               } else if (unlikely(!mrs->att_hist)) {
  55                         mrs->prob_ewma = cur_prob;
  56                 } else {
  57                         /*update exponential weighted moving avarage */
  58 @@ -200,7 +204,7 @@ minstrel_update_stats(struct minstrel_pr
  59                 struct minstrel_rate_stats *tmp_mrs = &mi->r[tmp_prob_rate].stats;
  60
  61                 /* Update statistics of success probability per rate */
  62 -               minstrel_calc_rate_stats(mrs);
  63 +               minstrel_calc_rate_stats(mp, mrs);
  64
  65                 /* Sample less often below the 10% chance of success.
  66                  * Sample less often above the 95% chance of success. */
  67 @@ -289,7 +293,8 @@ minstrel_tx_status(void *priv, struct ie
  68         if (mi->sample_deferred > 0)
  69                 mi->sample_deferred--;
  70
  71 -       if (time_after(jiffies, mi->last_stats_update + mp->update_interval))
  72 +       if (time_after(jiffies, mi->last_stats_update +
  73 +                               mp->update_interval / (mp->new_avg ? 2 : 1)))
  74                 minstrel_update_stats(mp, mi);
  75  }
  76
  77 --- a/net/mac80211/rc80211_minstrel.h
  78 +++ b/net/mac80211/rc80211_minstrel.h
  79 @@ -19,6 +19,21 @@
  80  #define MAX_THR_RATES 4
  81
  82  /*
  83 + * Coefficients for moving average with noise filter (period=16),
  84 + * scaled by 10 bits
  85 + *
  86 + * a1 = exp(-pi * sqrt(2) / period)
  87 + * coeff2 = 2 * a1 * cos(sqrt(2) * 2 * pi / period)
  88 + * coeff3 = -sqr(a1)
  89 + * coeff1 = 1 - coeff2 - coeff3
  90 + */
  91 +#define MINSTREL_AVG_COEFF1            (MINSTREL_FRAC(1, 1) - \
  92 +                                        MINSTREL_AVG_COEFF2 - \
  93 +                                        MINSTREL_AVG_COEFF3)
  94 +#define MINSTREL_AVG_COEFF2            0x00001499
  95 +#define MINSTREL_AVG_COEFF3            -0x0000092e
  96 +
  97 +/*
  98   * Perform EWMA (Exponentially Weighted Moving Average) calculation
  99   */
 100  static inline int
 101 @@ -32,6 +47,41 @@ minstrel_ewma(int old, int new, int weig
 102         return old + incr;
 103  }
 104
 105 +struct minstrel_avg_ctx {
 106 +       s32 prev[2];
 107 +};
 108 +
 109 +static inline int minstrel_filter_avg_add(struct minstrel_avg_ctx *ctx, s32 in)
 110 +{
 111 +       s32 out_1 = ctx->prev[0];
 112 +       s32 out_2 = ctx->prev[1];
 113 +       s32 val;
 114 +
 115 +       if (!in)
 116 +               in += 1;
 117 +
 118 +       if (!out_1) {
 119 +               val = out_1 = in;
 120 +               goto out;
 121 +       }
 122 +
 123 +       val = MINSTREL_AVG_COEFF1 * in;
 124 +       val += MINSTREL_AVG_COEFF2 * out_1;
 125 +       val += MINSTREL_AVG_COEFF3 * out_2;
 126 +       val >>= MINSTREL_SCALE;
 127 +
 128 +       if (val > 1 << MINSTREL_SCALE)
 129 +               val = 1 << MINSTREL_SCALE;
 130 +       if (val < 0)
 131 +               val = 1;
 132 +
 133 +out:
 134 +       ctx->prev[1] = out_1;
 135 +       ctx->prev[0] = val;
 136 +
 137 +       return val;
 138 +}
 139 +
 140  struct minstrel_rate_stats {
 141         /* current / last sampling period attempts/success counters */
 142         u16 attempts, last_attempts;
 143 @@ -40,6 +90,8 @@ struct minstrel_rate_stats {
 144         /* total attempts/success counters */
 145         u32 att_hist, succ_hist;
 146
 147 +       struct minstrel_avg_ctx avg;
 148 +
 149         /* prob_ewma - exponential weighted moving average of prob */
 150         u16 prob_ewma;
 151
 152 @@ -95,6 +147,7 @@ struct minstrel_sta_info {
 153  struct minstrel_priv {
 154         struct ieee80211_hw *hw;
 155         bool has_mrr;
 156 +       bool new_avg;
 157         u32 sample_switch;
 158         unsigned int cw_min;
 159         unsigned int cw_max;
 160 @@ -126,7 +179,8 @@ extern const struct rate_control_ops mac
 161  void minstrel_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);
 162
 163  /* Recalculate success probabilities and counters for a given rate using EWMA */
 164 -void minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs);
 165 +void minstrel_calc_rate_stats(struct minstrel_priv *mp,
 166 +                             struct minstrel_rate_stats *mrs);
 167  int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_ewma);
 168
 169  /* debugfs */
 170 --- a/net/mac80211/rc80211_minstrel_ht.c
 171 +++ b/net/mac80211/rc80211_minstrel_ht.c
 172 @@ -737,7 +737,7 @@ minstrel_ht_update_stats(struct minstrel
 173
 174                         mrs = &mg->rates[i];
 175                         mrs->retry_updated = false;
 176 -                       minstrel_calc_rate_stats(mrs);
 177 +                       minstrel_calc_rate_stats(mp, mrs);
 178                         cur_prob = mrs->prob_ewma;
 179
 180                         if (minstrel_ht_get_tp_avg(mi, group, i, cur_prob) == 0)
 181 @@ -773,6 +773,8 @@ minstrel_ht_update_stats(struct minstrel
 182
 183         /* try to sample all available rates during each interval */
 184         mi->sample_count *= 8;
 185 +       if (mp->new_avg)
 186 +               mi->sample_count /= 2;
 187
 188         if (sample)
 189                 minstrel_ht_rate_sample_switch(mp, mi);
 190 @@ -889,6 +891,7 @@ minstrel_ht_tx_status(void *priv, struct
 191         struct ieee80211_tx_rate *ar = info->status.rates;
 192         struct minstrel_rate_stats *rate, *rate2, *rate_sample = NULL;
 193         struct minstrel_priv *mp = priv;
 194 +       u32 update_interval = mp->update_interval / 2;
 195         bool last, update = false;
 196         bool sample_status = false;
 197         int i;
 198 @@ -943,6 +946,10 @@ minstrel_ht_tx_status(void *priv, struct
 199
 200         switch (mi->sample_mode) {
 201         case MINSTREL_SAMPLE_IDLE:
 202 +               if (mp->new_avg &&
 203 +                   (mp->hw->max_rates > 1 ||
 204 +                    mi->total_packets_cur < SAMPLE_SWITCH_THR))
 205 +                       update_interval /= 2;
 206                 break;
 207
 208         case MINSTREL_SAMPLE_ACTIVE:
 209 @@ -983,8 +990,7 @@ minstrel_ht_tx_status(void *priv, struct
 210                 }
 211         }
 212
 213 -       if (time_after(jiffies, mi->last_stats_update +
 214 -                               mp->update_interval / 2)) {
 215 +       if (time_after(jiffies, mi->last_stats_update + update_interval)) {
 216                 update = true;
 217                 minstrel_ht_update_stats(mp, mi, true);
 218         }
 219 @@ -1665,6 +1671,7 @@ minstrel_ht_alloc(struct ieee80211_hw *h
 220
 221         mp->hw = hw;
 222         mp->update_interval = HZ / 10;
 223 +       mp->new_avg = true;
 224
 225         minstrel_ht_init_cck_rates(mp);
 226
 227 @@ -1682,6 +1689,8 @@ static void minstrel_ht_add_debugfs(stru
 228                            &mp->fixed_rate_idx);
 229         debugfs_create_u32("sample_switch", S_IRUGO | S_IWUSR, debugfsdir,
 230                            &mp->sample_switch);
 231 +       debugfs_create_bool("new_avg", S_IRUGO | S_IWUSR, debugfsdir,
 232 +                          &mp->new_avg);
 233  }
 234  #endif
 235