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

   1 From: Felix Fietkau <nbd@nbd.name>
   2 Date: Fri, 14 Jun 2019 21:15:47 +0200
   3 Subject: [PATCH] mac80211: minstrel_ht: improve rate probing for devices
   4  with static fallback
   5
   6 On some devices that only support static rate fallback tables sending rate
   7 control probing packets can be really expensive.
   8 Probing lower rates can already hurt throughput quite a bit. What hurts even
   9 more is the fact that on mt76x0/mt76x2, single probing packets can only be
  10 forced by directing packets at a different internal hardware queue, which
  11 causes some heavy reordering and extra latency.
  12 The reordering issue is mainly problematic while pushing lots of packets to
  13 a particular station. If there is little activity, the overhead of probing is
  14 neglegible.
  15
  16 The static fallback behavior is designed to pretty much only handle rate
  17 control algorithms that use only a very limited set of rates on which the
  18 algorithm switches up/down based on packet error rate.
  19
  20 In order to better support that kind of hardware, this patch implements a
  21 different approach to rate probing where it switches to a slightly higher rate,
  22 waits for tx status feedback, then updates the stats and switches back to
  23 the new max throughput rate. This only triggers above a packet rate of 100
  24 per stats interval (~50ms).
  25 For that kind of probing, the code has to reduce the set of probing rates
  26 a lot more compared to single packet probing, so it uses only one packet
  27 per MCS group which is either slightly faster, or as close as possible to
  28 the max throughput rate.
  29 This allows switching between similar rates with different numbers of
  30 streams. The algorithm assumes that the hardware will work its way lower
  31 within an MCS group in case of retransmissions, so that lower rates don't
  32 have to be probed by the high packets per second rate probing code.
  33
  34 To further reduce the search space, it also does not probe rates with lower
  35 channel bandwidth than the max throughput rate.
  36
  37 At the moment, these changes will only affect mt76x0/mt76x2.
  38
  39 Signed-off-by: Felix Fietkau <nbd@nbd.name>
  40 ---
  41
  42 --- a/net/mac80211/rc80211_minstrel.h
  43 +++ b/net/mac80211/rc80211_minstrel.h
  44 @@ -114,6 +114,7 @@ struct minstrel_sta_info {
  45  struct minstrel_priv {
  46         struct ieee80211_hw *hw;
  47         bool has_mrr;
  48 +       u32 sample_switch;
  49         unsigned int cw_min;
  50         unsigned int cw_max;
  51         unsigned int max_retry;
  52 --- a/net/mac80211/rc80211_minstrel_ht.c
  53 +++ b/net/mac80211/rc80211_minstrel_ht.c
  54 @@ -21,6 +21,8 @@
  55  #define AVG_AMPDU_SIZE 16
  56  #define AVG_PKT_SIZE   1200
  57
  58 +#define SAMPLE_SWITCH_THR      100
  59 +
  60  /* Number of bits for an average sized packet */
  61  #define MCS_NBITS ((AVG_PKT_SIZE * AVG_AMPDU_SIZE) << 3)
  62
  63 @@ -59,6 +61,7 @@
  64         [GROUP_IDX(_streams, _sgi, _ht40)] = {                          \
  65         .streams = _streams,                                            \
  66         .shift = _s,                                                    \
  67 +       .bw = _ht40,                                                    \
  68         .flags =                                                        \
  69                 IEEE80211_TX_RC_MCS |                                   \
  70                 (_sgi ? IEEE80211_TX_RC_SHORT_GI : 0) |                 \
  71 @@ -95,6 +98,7 @@
  72         [VHT_GROUP_IDX(_streams, _sgi, _bw)] = {                        \
  73         .streams = _streams,                                            \
  74         .shift = _s,                                                    \
  75 +       .bw = _bw,                                                      \
  76         .flags =                                                        \
  77                 IEEE80211_TX_RC_VHT_MCS |                               \
  78                 (_sgi ? IEEE80211_TX_RC_SHORT_GI : 0) |                 \
  79 @@ -527,6 +531,133 @@ minstrel_ht_prob_rate_reduce_streams(str
  80         }
  81  }
  82
  83 +static inline int
  84 +minstrel_get_duration(int index)
  85 +{
  86 +       const struct mcs_group *group = &minstrel_mcs_groups[index / MCS_GROUP_RATES];
  87 +       unsigned int duration = group->duration[index % MCS_GROUP_RATES];
  88 +       return duration << group->shift;
  89 +}
  90 +
  91 +static bool
  92 +minstrel_ht_probe_group(struct minstrel_ht_sta *mi, const struct mcs_group *tp_group,
  93 +                                               int tp_idx, const struct mcs_group *group)
  94 +{
  95 +       if (group->bw < tp_group->bw)
  96 +               return false;
  97 +
  98 +       if (group->streams == tp_group->streams)
  99 +               return true;
 100 +
 101 +       if (tp_idx < 4 && group->streams == tp_group->streams - 1)
 102 +               return true;
 103 +
 104 +       return group->streams == tp_group->streams + 1;
 105 +}
 106 +
 107 +static void
 108 +minstrel_ht_find_probe_rates(struct minstrel_ht_sta *mi, u16 *rates, int *n_rates,
 109 +                            bool faster_rate)
 110 +{
 111 +       const struct mcs_group *group, *tp_group;
 112 +       int i, g, max_dur;
 113 +       int tp_idx;
 114 +
 115 +       tp_group = &minstrel_mcs_groups[mi->max_tp_rate[0] / MCS_GROUP_RATES];
 116 +       tp_idx = mi->max_tp_rate[0] % MCS_GROUP_RATES;
 117 +
 118 +       max_dur = minstrel_get_duration(mi->max_tp_rate[0]);
 119 +       if (faster_rate)
 120 +               max_dur -= max_dur / 16;
 121 +
 122 +       for (g = 0; g < MINSTREL_GROUPS_NB; g++) {
 123 +               u16 supported = mi->supported[g];
 124 +
 125 +               if (!supported)
 126 +                       continue;
 127 +
 128 +               group = &minstrel_mcs_groups[g];
 129 +               if (!minstrel_ht_probe_group(mi, tp_group, tp_idx, group))
 130 +                       continue;
 131 +
 132 +               for (i = 0; supported; supported >>= 1, i++) {
 133 +                       int idx;
 134 +
 135 +                       if (!(supported & 1))
 136 +                               continue;
 137 +
 138 +                       if ((group->duration[i] << group->shift) > max_dur)
 139 +                               continue;
 140 +
 141 +                       idx = g * MCS_GROUP_RATES + i;
 142 +                       if (idx == mi->max_tp_rate[0])
 143 +                               continue;
 144 +
 145 +                       rates[(*n_rates)++] = idx;
 146 +                       break;
 147 +               }
 148 +       }
 149 +}
 150 +
 151 +static void
 152 +minstrel_ht_rate_sample_switch(struct minstrel_priv *mp,
 153 +                              struct minstrel_ht_sta *mi)
 154 +{
 155 +       struct minstrel_rate_stats *mrs;
 156 +       u16 rates[MINSTREL_GROUPS_NB];
 157 +       int n_rates = 0;
 158 +       int probe_rate = 0;
 159 +       bool faster_rate;
 160 +       int i;
 161 +       u8 random;
 162 +
 163 +       /*
 164 +        * Use rate switching instead of probing packets for devices with
 165 +        * little control over retry fallback behavior
 166 +        */
 167 +       if (mp->hw->max_rates > 1)
 168 +               return;
 169 +
 170 +       /*
 171 +        * If the current EWMA prob is >75%, look for a rate that's 6.25%
 172 +        * faster than the max tp rate.
 173 +        * If that fails, look again for a rate that is at least as fast
 174 +        */
 175 +       mrs = minstrel_get_ratestats(mi, mi->max_tp_rate[0]);
 176 +       faster_rate = mrs->prob_ewma > MINSTREL_FRAC(75, 100);
 177 +       minstrel_ht_find_probe_rates(mi, rates, &n_rates, faster_rate);
 178 +       if (!n_rates && faster_rate)
 179 +               minstrel_ht_find_probe_rates(mi, rates, &n_rates, false);
 180 +
 181 +       /* If no suitable rate was found, try to pick the next one in the group */
 182 +       if (!n_rates) {
 183 +               int g_idx = mi->max_tp_rate[0] / MCS_GROUP_RATES;
 184 +               u16 supported = mi->supported[g_idx];
 185 +
 186 +               supported >>= mi->max_tp_rate[0] % MCS_GROUP_RATES;
 187 +               for (i = 0; supported; i++) {
 188 +                       if (!(supported & 1))
 189 +                               continue;
 190 +
 191 +                       probe_rate = mi->max_tp_rate[0] + i;
 192 +                       goto out;
 193 +               }
 194 +
 195 +               return;
 196 +       }
 197 +
 198 +       i = 0;
 199 +       if (n_rates > 1) {
 200 +               random = prandom_u32();
 201 +               i = random % n_rates;
 202 +       }
 203 +       probe_rate = rates[i];
 204 +
 205 +out:
 206 +       mi->sample_rate = probe_rate;
 207 +       mi->sample_mode = MINSTREL_SAMPLE_ACTIVE;
 208 +}
 209 +
 210  /*
 211   * Update rate statistics and select new primary rates
 212   *
 213 @@ -537,7 +668,8 @@ minstrel_ht_prob_rate_reduce_streams(str
 214   *    higher throughput rates, even if the probablity is a bit lower
 215   */
 216  static void
 217 -minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi)
 218 +minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
 219 +                        bool sample)
 220  {
 221         struct minstrel_mcs_group_data *mg;
 222         struct minstrel_rate_stats *mrs;
 223 @@ -545,6 +677,18 @@ minstrel_ht_update_stats(struct minstrel
 224         u16 tmp_mcs_tp_rate[MAX_THR_RATES], tmp_group_tp_rate[MAX_THR_RATES];
 225         u16 tmp_cck_tp_rate[MAX_THR_RATES], index;
 226
 227 +       mi->sample_mode = MINSTREL_SAMPLE_IDLE;
 228 +
 229 +       if (sample) {
 230 +               mi->total_packets_cur = mi->total_packets -
 231 +                                       mi->total_packets_last;
 232 +               mi->total_packets_last = mi->total_packets;
 233 +       }
 234 +       if (!mp->sample_switch)
 235 +               sample = false;
 236 +       if (mi->total_packets_cur < SAMPLE_SWITCH_THR && mp->sample_switch != 1)
 237 +           sample = false;
 238 +
 239         if (mi->ampdu_packets > 0) {
 240                 if (!ieee80211_hw_check(mp->hw, TX_STATUS_NO_AMPDU_LEN))
 241                         mi->avg_ampdu_len = minstrel_ewma(mi->avg_ampdu_len,
 242 @@ -631,12 +775,16 @@ minstrel_ht_update_stats(struct minstrel
 243         /* try to sample all available rates during each interval */
 244         mi->sample_count *= 8;
 245
 246 +       if (sample)
 247 +               minstrel_ht_rate_sample_switch(mp, mi);
 248 +
 249  #ifdef CPTCFG_MAC80211_DEBUGFS
 250         /* use fixed index if set */
 251         if (mp->fixed_rate_idx != -1) {
 252                 for (i = 0; i < 4; i++)
 253                         mi->max_tp_rate[i] = mp->fixed_rate_idx;
 254                 mi->max_prob_rate = mp->fixed_rate_idx;
 255 +               mi->sample_mode = MINSTREL_SAMPLE_IDLE;
 256         }
 257  #endif
 258
 259 @@ -740,15 +888,17 @@ minstrel_ht_tx_status(void *priv, struct
 260         struct minstrel_ht_sta_priv *msp = priv_sta;
 261         struct minstrel_ht_sta *mi = &msp->ht;
 262         struct ieee80211_tx_rate *ar = info->status.rates;
 263 -       struct minstrel_rate_stats *rate, *rate2;
 264 +       struct minstrel_rate_stats *rate, *rate2, *rate_sample = NULL;
 265         struct minstrel_priv *mp = priv;
 266         bool last, update = false;
 267 +       bool sample_status = false;
 268         int i;
 269
 270         if (!msp->is_ht)
 271                 return mac80211_minstrel.tx_status_ext(priv, sband,
 272                                                        &msp->legacy, st);
 273
 274 +
 275         /* This packet was aggregated but doesn't carry status info */
 276         if ((info->flags & IEEE80211_TX_CTL_AMPDU) &&
 277             !(info->flags & IEEE80211_TX_STAT_AMPDU))
 278 @@ -774,12 +924,17 @@ minstrel_ht_tx_status(void *priv, struct
 279         if (info->flags & IEEE80211_TX_CTL_RATE_CTRL_PROBE)
 280                 mi->sample_packets += info->status.ampdu_len;
 281
 282 +       if (mi->sample_mode != MINSTREL_SAMPLE_IDLE)
 283 +               rate_sample = minstrel_get_ratestats(mi, mi->sample_rate);
 284 +
 285         last = !minstrel_ht_txstat_valid(mp, &ar[0]);
 286         for (i = 0; !last; i++) {
 287                 last = (i == IEEE80211_TX_MAX_RATES - 1) ||
 288                        !minstrel_ht_txstat_valid(mp, &ar[i + 1]);
 289
 290                 rate = minstrel_ht_get_stats(mp, mi, &ar[i]);
 291 +               if (rate == rate_sample)
 292 +                       sample_status = true;
 293
 294                 if (last)
 295                         rate->success += info->status.ampdu_ack_len;
 296 @@ -787,44 +942,60 @@ minstrel_ht_tx_status(void *priv, struct
 297                 rate->attempts += ar[i].count * info->status.ampdu_len;
 298         }
 299
 300 -       /*
 301 -        * check for sudden death of spatial multiplexing,
 302 -        * downgrade to a lower number of streams if necessary.
 303 -        */
 304 -       rate = minstrel_get_ratestats(mi, mi->max_tp_rate[0]);
 305 -       if (rate->attempts > 30 &&
 306 -           MINSTREL_FRAC(rate->success, rate->attempts) <
 307 -           MINSTREL_FRAC(20, 100)) {
 308 -               minstrel_downgrade_rate(mi, &mi->max_tp_rate[0], true);
 309 +       switch (mi->sample_mode) {
 310 +       case MINSTREL_SAMPLE_IDLE:
 311 +               break;
 312 +
 313 +       case MINSTREL_SAMPLE_ACTIVE:
 314 +               if (!sample_status)
 315 +                       break;
 316 +
 317 +               mi->sample_mode = MINSTREL_SAMPLE_PENDING;
 318                 update = true;
 319 -       }
 320 +               break;
 321 +
 322 +       case MINSTREL_SAMPLE_PENDING:
 323 +               if (sample_status)
 324 +                       break;
 325
 326 -       rate2 = minstrel_get_ratestats(mi, mi->max_tp_rate[1]);
 327 -       if (rate2->attempts > 30 &&
 328 -           MINSTREL_FRAC(rate2->success, rate2->attempts) <
 329 -           MINSTREL_FRAC(20, 100)) {
 330 -               minstrel_downgrade_rate(mi, &mi->max_tp_rate[1], false);
 331                 update = true;
 332 +               minstrel_ht_update_stats(mp, mi, false);
 333 +               break;
 334 +       }
 335 +
 336 +
 337 +       if (mp->hw->max_rates > 1) {
 338 +               /*
 339 +                * check for sudden death of spatial multiplexing,
 340 +                * downgrade to a lower number of streams if necessary.
 341 +                */
 342 +               rate = minstrel_get_ratestats(mi, mi->max_tp_rate[0]);
 343 +               if (rate->attempts > 30 &&
 344 +                   MINSTREL_FRAC(rate->success, rate->attempts) <
 345 +                   MINSTREL_FRAC(20, 100)) {
 346 +                       minstrel_downgrade_rate(mi, &mi->max_tp_rate[0], true);
 347 +                       update = true;
 348 +               }
 349 +
 350 +               rate2 = minstrel_get_ratestats(mi, mi->max_tp_rate[1]);
 351 +               if (rate2->attempts > 30 &&
 352 +                   MINSTREL_FRAC(rate2->success, rate2->attempts) <
 353 +                   MINSTREL_FRAC(20, 100)) {
 354 +                       minstrel_downgrade_rate(mi, &mi->max_tp_rate[1], false);
 355 +                       update = true;
 356 +               }
 357         }
 358
 359         if (time_after(jiffies, mi->last_stats_update +
 360                                 (mp->update_interval / 2 * HZ) / 1000)) {
 361                 update = true;
 362 -               minstrel_ht_update_stats(mp, mi);
 363 +               minstrel_ht_update_stats(mp, mi, true);
 364         }
 365
 366         if (update)
 367                 minstrel_ht_update_rates(mp, mi);
 368  }
 369
 370 -static inline int
 371 -minstrel_get_duration(int index)
 372 -{
 373 -       const struct mcs_group *group = &minstrel_mcs_groups[index / MCS_GROUP_RATES];
 374 -       unsigned int duration = group->duration[index % MCS_GROUP_RATES];
 375 -       return duration << group->shift;
 376 -}
 377 -
 378  static void
 379  minstrel_calc_retransmit(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
 380                           int index)
 381 @@ -989,14 +1160,18 @@ static void
 382  minstrel_ht_update_rates(struct minstrel_priv *mp, struct minstrel_ht_sta *mi)
 383  {
 384         struct ieee80211_sta_rates *rates;
 385 +       u16 first_rate = mi->max_tp_rate[0];
 386         int i = 0;
 387
 388 +       if (mi->sample_mode == MINSTREL_SAMPLE_ACTIVE)
 389 +               first_rate = mi->sample_rate;
 390 +
 391         rates = kzalloc(sizeof(*rates), GFP_ATOMIC);
 392         if (!rates)
 393                 return;
 394
 395         /* Start with max_tp_rate[0] */
 396 -       minstrel_ht_set_rate(mp, mi, rates, i++, mi->max_tp_rate[0]);
 397 +       minstrel_ht_set_rate(mp, mi, rates, i++, first_rate);
 398
 399         if (mp->hw->max_rates >= 3) {
 400                 /* At least 3 tx rates supported, use max_tp_rate[1] next */
 401 @@ -1023,6 +1198,11 @@ minstrel_get_sample_rate(struct minstrel
 402         int tp_rate1, tp_rate2;
 403         int sample_idx = 0;
 404
 405 +       if (mp->hw->max_rates == 1 && mp->sample_switch &&
 406 +           (mi->total_packets_cur >= SAMPLE_SWITCH_THR ||
 407 +            mp->sample_switch == 1))
 408 +               return -1;
 409 +
 410         if (mi->sample_wait > 0) {
 411                 mi->sample_wait--;
 412                 return -1;
 413 @@ -1349,7 +1529,7 @@ minstrel_ht_update_caps(void *priv, stru
 414         mi->supported[MINSTREL_CCK_GROUP] |= mi->cck_supported_short << 4;
 415
 416         /* create an initial rate table with the lowest supported rates */
 417 -       minstrel_ht_update_stats(mp, mi);
 418 +       minstrel_ht_update_stats(mp, mi, true);
 419         minstrel_ht_update_rates(mp, mi);
 420
 421         return;
 422 @@ -1467,6 +1647,8 @@ minstrel_ht_alloc(struct ieee80211_hw *h
 423         if (!mp)
 424                 return NULL;
 425
 426 +       mp->sample_switch = -1;
 427 +
 428         /* contention window settings
 429          * Just an approximation. Using the per-queue values would complicate
 430          * the calculations and is probably unnecessary */
 431 @@ -1498,6 +1680,8 @@ minstrel_ht_alloc(struct ieee80211_hw *h
 432         mp->fixed_rate_idx = (u32) -1;
 433         debugfs_create_u32("fixed_rate_idx", S_IRUGO | S_IWUGO, debugfsdir,
 434                            &mp->fixed_rate_idx);
 435 +       debugfs_create_u32("sample_switch", S_IRUGO | S_IWUSR, debugfsdir,
 436 +                          &mp->sample_switch);
 437  #endif
 438
 439         minstrel_ht_init_cck_rates(mp);
 440 --- a/net/mac80211/rc80211_minstrel_ht.h
 441 +++ b/net/mac80211/rc80211_minstrel_ht.h
 442 @@ -36,6 +36,7 @@ struct mcs_group {
 443         u16 flags;
 444         u8 streams;
 445         u8 shift;
 446 +       u8 bw;
 447         u16 duration[MCS_GROUP_RATES];
 448  };
 449
 450 @@ -53,6 +54,12 @@ struct minstrel_mcs_group_data {
 451         struct minstrel_rate_stats rates[MCS_GROUP_RATES];
 452  };
 453
 454 +enum minstrel_sample_mode {
 455 +       MINSTREL_SAMPLE_IDLE,
 456 +       MINSTREL_SAMPLE_ACTIVE,
 457 +       MINSTREL_SAMPLE_PENDING,
 458 +};
 459 +
 460  struct minstrel_ht_sta {
 461         struct ieee80211_sta *sta;
 462
 463 @@ -74,6 +81,8 @@ struct minstrel_ht_sta {
 464         unsigned int overhead;
 465         unsigned int overhead_rtscts;
 466
 467 +       unsigned int total_packets_last;
 468 +       unsigned int total_packets_cur;
 469         unsigned int total_packets;
 470         unsigned int sample_packets;
 471
 472 @@ -85,6 +94,9 @@ struct minstrel_ht_sta {
 473         u8 sample_count;
 474         u8 sample_slow;
 475
 476 +       enum minstrel_sample_mode sample_mode;
 477 +       u16 sample_rate;
 478 +
 479         /* current MCS group to be sampled */
 480         u8 sample_group;
 481