From 7611cb38512c61cc20d6799ca9f13cb7524a33a6 Mon Sep 17 00:00:00 2001 From: stsp Date: Fri, 12 Mar 2021 16:26:27 +0000 Subject: [PATCH] Add RA, a new 11n Tx rate adaptation module for net80211. Written by Christian Ehrhardt and myself, based on ieee80211_mira.c but with significant changes. The main difference is that RA does not attempt to precisely measure actual throughput but simply deducts a loss percentage from the theoretical throughput which can be achieved by a given MCS. Unlike MiRa, RA does not use timeouts to trigger probing. Probing is triggered only by changes in measured throughput. Unlike MiRA, RA doesn't care whether a frame was part of an A-MPDU. RA simply collects statistics for individual subframes. This makes reporting very easy for drivers and seems to work well enough in practice. Another difference is that drivers can report multi-rate retries properly via ieee80211_ra_add_stats_ht(mcs, total, fail) which can be called several times before ieee80211_ra_choose() selects a new Tx rate. There is no reason any issues could not be fixed in ieee8011_mira.c but I felt it was a good moment to burn the house down and start over. And since this code diverges from how MiRA is described in the research paper applying the "MiRA" label becomes inappropriate. --- sys/conf/files | 3 +- sys/net80211/ieee80211_ra.c | 704 ++++++++++++++++++++++++++++++++++++ sys/net80211/ieee80211_ra.h | 79 ++++ 3 files changed, 785 insertions(+), 1 deletion(-) create mode 100644 sys/net80211/ieee80211_ra.c create mode 100644 sys/net80211/ieee80211_ra.h diff --git a/sys/conf/files b/sys/conf/files index ba16d783d77..557bce4468e 100644 --- a/sys/conf/files +++ b/sys/conf/files @@ -1,4 +1,4 @@ -# $OpenBSD: files,v 1.698 2021/02/23 03:30:04 dlg Exp $ +# $OpenBSD: files,v 1.699 2021/03/12 16:26:27 stsp Exp $ # $NetBSD: files,v 1.87 1996/05/19 17:17:50 jonathan Exp $ # @(#)files.newconf 7.5 (Berkeley) 5/10/93 @@ -861,6 +861,7 @@ file net80211/ieee80211_output.c wlan file net80211/ieee80211_pae_input.c wlan file net80211/ieee80211_pae_output.c wlan file net80211/ieee80211_proto.c wlan +file net80211/ieee80211_ra.c wlan file net80211/ieee80211_rssadapt.c wlan file net80211/ieee80211_regdomain.c wlan file netinet/if_ether.c ether diff --git a/sys/net80211/ieee80211_ra.c b/sys/net80211/ieee80211_ra.c new file mode 100644 index 00000000000..924e3008cf5 --- /dev/null +++ b/sys/net80211/ieee80211_ra.c @@ -0,0 +1,704 @@ +/* $OpenBSD: ieee80211_ra.c,v 1.1 2021/03/12 16:26:27 stsp Exp $ */ + +/* + * Copyright (c) 2021 Christian Ehrhardt + * Copyright (c) 2016, 2021 Stefan Sperling + * Copyright (c) 2016 Theo Buehler + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include +#include + +#include +#include + +#include +#include + +#include +#include + +int ieee80211_ra_next_intra_rate(struct ieee80211_ra_node *, + struct ieee80211_node *); +const struct ieee80211_ht_rateset * ieee80211_ra_next_rateset( + struct ieee80211_ra_node *, struct ieee80211_node *); +int ieee80211_ra_best_mcs_in_rateset(struct ieee80211_ra_node *, + const struct ieee80211_ht_rateset *); +void ieee80211_ra_probe_next_rateset(struct ieee80211_ra_node *, + struct ieee80211_node *, const struct ieee80211_ht_rateset *); +int ieee80211_ra_next_mcs(struct ieee80211_ra_node *, + struct ieee80211_node *); +int ieee80211_ra_probe_valid(struct ieee80211_ra_node *, + struct ieee80211_node *); +void ieee80211_ra_probe_done(struct ieee80211_ra_node *); +int ieee80211_ra_intra_mode_ra_finished( + struct ieee80211_ra_node *, struct ieee80211_node *); +void ieee80211_ra_trigger_next_rateset(struct ieee80211_ra_node *, + struct ieee80211_node *); +int ieee80211_ra_inter_mode_ra_finished( + struct ieee80211_ra_node *, struct ieee80211_node *); +int ieee80211_ra_best_rate(struct ieee80211_ra_node *, + struct ieee80211_node *); +void ieee80211_ra_probe_next_rate(struct ieee80211_ra_node *, + struct ieee80211_node *); +int ieee80211_ra_valid_tx_mcs(struct ieee80211com *, int); +uint32_t ieee80211_ra_valid_rates(struct ieee80211com *, + struct ieee80211_node *); + +/* We use fixed point arithmetic with 64 bit integers. */ +#define RA_FP_SHIFT 21 +#define RA_FP_INT(x) (x ## ULL << RA_FP_SHIFT) /* the integer x */ +#define RA_FP_1 RA_FP_INT(1) + +/* Multiply two fixed point numbers. */ +#define RA_FP_MUL(a, b) \ + (((a) * (b)) >> RA_FP_SHIFT) + +/* Divide two fixed point numbers. */ +#define RA_FP_DIV(a, b) \ + (b == 0 ? (uint64_t)-1 : (((a) << RA_FP_SHIFT) / (b))) + +#define RA_DEBUG +#ifdef RA_DEBUG +#define DPRINTF(x) do { if (ra_debug > 0) printf x; } while (0) +#define DPRINTFN(n, x) do { if (ra_debug >= (n)) printf x; } while (0) +int ra_debug = 0; +#else +#define DPRINTF(x) do { ; } while (0) +#define DPRINTFN(n, x) do { ; } while (0) +#endif + +#ifdef RA_DEBUG +void +ra_fixedp_split(uint32_t *i, uint32_t *f, uint64_t fp) +{ + uint64_t tmp; + + /* integer part */ + *i = (fp >> RA_FP_SHIFT); + + /* fractional part */ + tmp = (fp & ((uint64_t)-1 >> (64 - RA_FP_SHIFT))); + tmp *= 100; + *f = (uint32_t)(tmp >> RA_FP_SHIFT); +} + +char * +ra_fp_sprintf(uint64_t fp) +{ + uint32_t i, f; + static char buf[64]; + int ret; + + ra_fixedp_split(&i, &f, fp); + ret = snprintf(buf, sizeof(buf), "%u.%02u", i, f); + if (ret == -1 || ret >= sizeof(buf)) + return "ERR"; + + return buf; +} +#endif /* RA_DEBUG */ + +const struct ieee80211_ht_rateset * +ieee80211_ra_get_ht_rateset(int mcs, int sgi20) +{ + const struct ieee80211_ht_rateset *rs; + int i; + + for (i = 0; i < IEEE80211_HT_NUM_RATESETS; i++) { + rs = &ieee80211_std_ratesets_11n[i]; + if (sgi20 != rs->sgi) + continue; + if (mcs >= rs->min_mcs && mcs <= rs->max_mcs) + return rs; + } + + panic("MCS %d is not part of any rateset", mcs); +} + +/* + * Update goodput statistics. + */ + +uint64_t +ieee80211_ra_get_txrate(int mcs, int sgi20) +{ + const struct ieee80211_ht_rateset *rs; + uint64_t txrate; + + rs = ieee80211_ra_get_ht_rateset(mcs, sgi20); + txrate = rs->rates[mcs - rs->min_mcs]; + txrate <<= RA_FP_SHIFT; /* convert to fixed-point */ + txrate *= 500; /* convert to kbit/s */ + txrate /= 1000; /* convert to mbit/s */ + + return txrate; +} + +/* + * Rate selection. + */ + +/* A rate's goodput has to be at least this much larger to be "better". */ +#define IEEE80211_RA_RATE_THRESHOLD (RA_FP_1 / 64) /* ~ 0.015 */ + +/* Number of (sub-)frames which render a probe valid. */ +#define IEEE80211_RA_MIN_PROBE_FRAMES 8 + +/* Number of Tx retries which, alternatively, render a probe valid. */ +#define IEEE80211_RA_MAX_PROBE_RETRIES 4 + +int +ieee80211_ra_next_lower_intra_rate(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + const struct ieee80211_ht_rateset *rs; + int i, next; + int sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + + rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, sgi20); + if (ni->ni_txmcs == rs->min_mcs) + return rs->min_mcs; + + next = ni->ni_txmcs; + for (i = rs->nrates - 1; i >= 0; i--) { + if ((rn->valid_rates & (1 << (i + rs->min_mcs))) == 0) + continue; + if (i + rs->min_mcs < ni->ni_txmcs) { + next = i + rs->min_mcs; + break; + } + } + + return next; +} + +int +ieee80211_ra_next_intra_rate(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + const struct ieee80211_ht_rateset *rs; + int i, next; + int sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + + rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, sgi20); + if (ni->ni_txmcs == rs->max_mcs) + return rs->max_mcs; + + next = ni->ni_txmcs; + for (i = 0; i < rs->nrates; i++) { + if ((rn->valid_rates & (1 << (i + rs->min_mcs))) == 0) + continue; + if (i + rs->min_mcs > ni->ni_txmcs) { + next = i + rs->min_mcs; + break; + } + } + + return next; +} + +const struct ieee80211_ht_rateset * +ieee80211_ra_next_rateset(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + const struct ieee80211_ht_rateset *rs, *rsnext; + int next; + int mcs = ni->ni_txmcs; + int sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + + rs = ieee80211_ra_get_ht_rateset(mcs, sgi20); + if (rn->probing & IEEE80211_RA_PROBING_UP) { + if (rs->max_mcs == 7) /* MCS 0-7 */ + next = sgi20 ? IEEE80211_HT_RATESET_MIMO2_SGI : + IEEE80211_HT_RATESET_MIMO2; + else if (rs->max_mcs == 15) /* MCS 8-15 */ + next = sgi20 ? IEEE80211_HT_RATESET_MIMO3_SGI : + IEEE80211_HT_RATESET_MIMO3; + else if (rs->max_mcs == 23) /* MCS 16-23 */ + next = sgi20 ? IEEE80211_HT_RATESET_MIMO4_SGI : + IEEE80211_HT_RATESET_MIMO4; + else /* MCS 24-31 */ + return NULL; + } else if (rn->probing & IEEE80211_RA_PROBING_DOWN) { + if (rs->min_mcs == 24) /* MCS 24-31 */ + next = sgi20 ? IEEE80211_HT_RATESET_MIMO3_SGI : + IEEE80211_HT_RATESET_MIMO3; + else if (rs->min_mcs == 16) /* MCS 16-23 */ + next = sgi20 ? IEEE80211_HT_RATESET_MIMO2_SGI : + IEEE80211_HT_RATESET_MIMO2; + else if (rs->min_mcs == 8) /* MCS 8-15 */ + next = sgi20 ? IEEE80211_HT_RATESET_SISO_SGI : + IEEE80211_HT_RATESET_SISO; + else /* MCS 0-7 */ + return NULL; + } else + panic("%s: invalid probing mode %d", __func__, rn->probing); + + rsnext = &ieee80211_std_ratesets_11n[next]; + if ((rsnext->mcs_mask & rn->valid_rates) == 0) + return NULL; + + return rsnext; +} + +int +ieee80211_ra_best_mcs_in_rateset(struct ieee80211_ra_node *rn, + const struct ieee80211_ht_rateset *rs) +{ + uint64_t gmax = 0; + int i, best_mcs = rs->min_mcs; + + for (i = 0; i < rs->nrates; i++) { + int mcs = rs->min_mcs + i; + struct ieee80211_ra_goodput_stats *g = &rn->g[mcs]; + if (((1 << mcs) & rn->valid_rates) == 0) + continue; + if (g->measured > gmax + IEEE80211_RA_RATE_THRESHOLD) { + gmax = g->measured; + best_mcs = mcs; + } + } + + return best_mcs; +} + +void +ieee80211_ra_probe_next_rateset(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni, const struct ieee80211_ht_rateset *rsnext) +{ + const struct ieee80211_ht_rateset *rs; + struct ieee80211_ra_goodput_stats *g; + int best_mcs, i; + int sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + + /* Find most recently measured best MCS from the current rateset. */ + rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, sgi20); + best_mcs = ieee80211_ra_best_mcs_in_rateset(rn, rs); + + /* Switch to the next rateset. */ + ni->ni_txmcs = rsnext->min_mcs; + if ((rn->valid_rates & (1 << rsnext->min_mcs)) == 0) + ni->ni_txmcs = ieee80211_ra_next_intra_rate(rn, ni); + + /* Select the lowest rate from the next rateset with loss-free + * goodput close to the current best measurement. */ + g = &rn->g[best_mcs]; + for (i = 0; i < rsnext->nrates; i++) { + int mcs = rsnext->min_mcs + i; + uint64_t txrate = rsnext->rates[i]; + + if ((rn->valid_rates & (1 << mcs)) == 0) + continue; + + txrate = txrate * 500; /* convert to kbit/s */ + txrate <<= RA_FP_SHIFT; /* convert to fixed-point */ + txrate /= 1000; /* convert to mbit/s */ + + if (txrate > g->measured + IEEE80211_RA_RATE_THRESHOLD) { + ni->ni_txmcs = mcs; + break; + } + } + /* If all rates are lower the maximum rate is the closest match. */ + if (i == rsnext->nrates) + ni->ni_txmcs = rsnext->max_mcs; + + /* Add rates from the next rateset as candidates. */ + rn->candidate_rates |= (1 << ni->ni_txmcs); + if (rn->probing & IEEE80211_RA_PROBING_UP) { + rn->candidate_rates |= + (1 << ieee80211_ra_next_intra_rate(rn, ni)); + } else if (rn->probing & IEEE80211_RA_PROBING_DOWN) { + rn->candidate_rates |= + (1 << ieee80211_ra_next_lower_intra_rate(rn, ni)); + } else + panic("%s: invalid probing mode %d", __func__, rn->probing); +} + +int +ieee80211_ra_next_mcs(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + int next; + + if (rn->probing & IEEE80211_RA_PROBING_DOWN) + next = ieee80211_ra_next_lower_intra_rate(rn, ni); + else if (rn->probing & IEEE80211_RA_PROBING_UP) + next = ieee80211_ra_next_intra_rate(rn, ni); + else + panic("%s: invalid probing mode %d", __func__, rn->probing); + + return next; +} + +int +ieee80211_ra_probe_valid(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + return rn->valid_probes & (1UL << ni->ni_txmcs); +} + +void +ieee80211_ra_probe_clear(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + struct ieee80211_ra_goodput_stats *g = &rn->g[ni->ni_txmcs]; + + g->nprobe_pkts = 0; + g->nprobe_fail = 0; +} + +void +ieee80211_ra_probe_done(struct ieee80211_ra_node *rn) +{ + rn->probing = IEEE80211_RA_NOT_PROBING; + rn->probed_rates = 0; + rn->valid_probes = 0; + rn->candidate_rates = 0; +} + +int +ieee80211_ra_intra_mode_ra_finished(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + const struct ieee80211_ht_rateset *rs; + struct ieee80211_ra_goodput_stats *g = &rn->g[ni->ni_txmcs]; + int next_mcs, best_mcs; + uint64_t next_rate; + int sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + + rn->probed_rates = (rn->probed_rates | (1 << ni->ni_txmcs)); + + /* Check if the min/max MCS in this rateset has been probed. */ + rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, sgi20); + if (rn->probing & IEEE80211_RA_PROBING_DOWN) { + if (ni->ni_txmcs == rs->min_mcs || + rn->probed_rates & (1 << rs->min_mcs)) { + ieee80211_ra_trigger_next_rateset(rn, ni); + return 1; + } + } else if (rn->probing & IEEE80211_RA_PROBING_UP) { + if (ni->ni_txmcs == rs->max_mcs || + rn->probed_rates & (1 << rs->max_mcs)) { + ieee80211_ra_trigger_next_rateset(rn, ni); + return 1; + } + } + + /* + * Check if the measured goodput is loss-free and better than the + * loss-free goodput of the candidate rate. + */ + next_mcs = ieee80211_ra_next_mcs(rn, ni); + if (next_mcs == ni->ni_txmcs) { + ieee80211_ra_trigger_next_rateset(rn, ni); + return 1; + } + next_rate = ieee80211_ra_get_txrate(next_mcs, sgi20); + if (g->loss == 0 && + g->measured >= next_rate + IEEE80211_RA_RATE_THRESHOLD) { + ieee80211_ra_trigger_next_rateset(rn, ni); + return 1; + } + + /* Check if we had a better measurement at a previously probed MCS. */ + best_mcs = ieee80211_ra_best_mcs_in_rateset(rn, rs); + if (best_mcs != ni->ni_txmcs && (rn->probed_rates & (1 << best_mcs))) { + if ((rn->probing & IEEE80211_RA_PROBING_UP) && + best_mcs < ni->ni_txmcs) { + ieee80211_ra_trigger_next_rateset(rn, ni); + return 1; + } + if ((rn->probing & IEEE80211_RA_PROBING_DOWN) && + best_mcs > ni->ni_txmcs) { + ieee80211_ra_trigger_next_rateset(rn, ni); + return 1; + } + } + + /* Check if all rates in the set of candidate rates have been probed. */ + if ((rn->candidate_rates & rn->probed_rates) == rn->candidate_rates) { + /* Remain in the current rateset until above checks trigger. */ + rn->probing &= ~IEEE80211_RA_PROBING_INTER; + return 1; + } + + return 0; +} + +void +ieee80211_ra_trigger_next_rateset(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + const struct ieee80211_ht_rateset *rsnext; + + rsnext = ieee80211_ra_next_rateset(rn, ni); + if (rsnext) { + ieee80211_ra_probe_next_rateset(rn, ni, rsnext); + rn->probing |= IEEE80211_RA_PROBING_INTER; + } else + rn->probing &= ~IEEE80211_RA_PROBING_INTER; +} + +int +ieee80211_ra_inter_mode_ra_finished(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + return ((rn->probing & IEEE80211_RA_PROBING_INTER) == 0); +} + +int +ieee80211_ra_best_rate(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + int i, best = rn->best_mcs; + uint64_t gmax = rn->g[rn->best_mcs].measured; + + for (i = 0; i < nitems(rn->g); i++) { + struct ieee80211_ra_goodput_stats *g = &rn->g[i]; + if (((1 << i) & rn->valid_rates) == 0) + continue; + if (g->measured > gmax + IEEE80211_RA_RATE_THRESHOLD) { + gmax = g->measured; + best = i; + } + } + +#ifdef RA_DEBUG + if (rn->best_mcs != best) { + DPRINTF(("MCS %d is best; MCS{cur|avg|loss}:", best)); + for (i = 0; i < IEEE80211_HT_RATESET_NUM_MCS; i++) { + struct ieee80211_ra_goodput_stats *g = &rn->g[i]; + if ((rn->valid_rates & (1 << i)) == 0) + continue; + DPRINTF((" %d{%s|", i, ra_fp_sprintf(g->measured))); + DPRINTF(("%s|", ra_fp_sprintf(g->average))); + DPRINTF(("%s%%}", ra_fp_sprintf(g->loss))); + } + DPRINTF(("\n")); + } +#endif + return best; +} + +void +ieee80211_ra_probe_next_rate(struct ieee80211_ra_node *rn, + struct ieee80211_node *ni) +{ + /* Select the next rate to probe. */ + rn->probed_rates |= (1 << ni->ni_txmcs); + ni->ni_txmcs = ieee80211_ra_next_mcs(rn, ni); +} + +int +ieee80211_ra_valid_tx_mcs(struct ieee80211com *ic, int mcs) +{ + uint32_t ntxstreams = 1; + static const int max_mcs[] = { 7, 15, 23, 31 }; + + if ((ic->ic_tx_mcs_set & IEEE80211_TX_RX_MCS_NOT_EQUAL) == 0) + return isset(ic->ic_sup_mcs, mcs); + + ntxstreams += ((ic->ic_tx_mcs_set & IEEE80211_TX_SPATIAL_STREAMS) >> 2); + if (ntxstreams < 1 || ntxstreams > 4) + panic("invalid number of Tx streams: %u", ntxstreams); + return (mcs <= max_mcs[ntxstreams - 1] && isset(ic->ic_sup_mcs, mcs)); +} + +uint32_t +ieee80211_ra_valid_rates(struct ieee80211com *ic, struct ieee80211_node *ni) +{ + uint32_t valid_mcs = 0; + int i; + + for (i = 0; i < IEEE80211_HT_RATESET_NUM_MCS; i++) { + if (!isset(ni->ni_rxmcs, i)) + continue; + if (!ieee80211_ra_valid_tx_mcs(ic, i)) + continue; + valid_mcs |= (1 << i); + } + + return valid_mcs; +} + +void +ieee80211_ra_add_stats_ht(struct ieee80211_ra_node *rn, + struct ieee80211com *ic, struct ieee80211_node *ni, + int mcs, uint32_t total, uint32_t fail) +{ + static const uint64_t alpha = RA_FP_1 / 8; /* 1/8 = 0.125 */ + static const uint64_t beta = RA_FP_1 / 4; /* 1/4 = 0.25 */ + int s, sgi20; + struct ieee80211_ra_goodput_stats *g = &rn->g[mcs]; + uint64_t sfer, rate, delta; + + /* + * Ignore invalid values. These values may come from hardware + * so asserting valid values via panic is not appropriate. + */ + if (mcs < 0 || mcs >= IEEE80211_HT_RATESET_NUM_MCS) + return; + if (total == 0) + return; + + s = splnet(); + + g->nprobe_pkts += total; + g->nprobe_fail += fail; + + if (g->nprobe_pkts < IEEE80211_RA_MIN_PROBE_FRAMES && + g->nprobe_fail < IEEE80211_RA_MAX_PROBE_RETRIES) { + splx(s); + return; + } + + if (g->nprobe_fail > g->nprobe_pkts) { + DPRINTF(("%s fail %u > pkts %u\n", + ether_sprintf(ni->ni_macaddr), + g->nprobe_fail, g->nprobe_pkts)); + g->nprobe_fail = g->nprobe_pkts; + } + + sfer = g->nprobe_fail << RA_FP_SHIFT; + sfer /= g->nprobe_pkts; + rn->valid_probes |= 1U << mcs; + g->nprobe_fail = 0; + g->nprobe_pkts = 0; + + sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + rate = ieee80211_ra_get_txrate(mcs, sgi20); + + g->loss = sfer * 100; + g->measured = RA_FP_MUL(RA_FP_1 - sfer, rate); + g->average = RA_FP_MUL(RA_FP_1 - alpha, g->average); + g->average += RA_FP_MUL(alpha, g->measured); + + g->stddeviation = RA_FP_MUL(RA_FP_1 - beta, g->stddeviation); + if (g->average > g->measured) + delta = g->average - g->measured; + else + delta = g->measured - g->average; + g->stddeviation += RA_FP_MUL(beta, delta); + + splx(s); +} + +void +ieee80211_ra_choose(struct ieee80211_ra_node *rn, struct ieee80211com *ic, + struct ieee80211_node *ni) +{ + struct ieee80211_ra_goodput_stats *g = &rn->g[ni->ni_txmcs]; + int s; + int sgi20 = (ni->ni_flags & IEEE80211_NODE_HT_SGI20) ? 1 : 0; + const struct ieee80211_ht_rateset *rs, *rsnext; + + s = splnet(); + + if (rn->valid_rates == 0) + rn->valid_rates = ieee80211_ra_valid_rates(ic, ni); + + if (rn->probing) { + /* Probe another rate or settle at the best rate. */ + if (!ieee80211_ra_probe_valid(rn, ni)) { + splx(s); + return; + } + ieee80211_ra_probe_clear(rn, ni); + if (!ieee80211_ra_intra_mode_ra_finished(rn, ni)) { + ieee80211_ra_probe_next_rate(rn, ni); + DPRINTFN(3, ("probing MCS %d\n", ni->ni_txmcs)); + } else if (ieee80211_ra_inter_mode_ra_finished(rn, ni)) { + rn->best_mcs = ieee80211_ra_best_rate(rn, ni); + ni->ni_txmcs = rn->best_mcs; + ieee80211_ra_probe_done(rn); + } + + splx(s); + return; + } else { + rn->valid_probes = 0; + } + + rs = ieee80211_ra_get_ht_rateset(ni->ni_txmcs, sgi20); + if ((g->measured >> RA_FP_SHIFT) == 0LL || + (g->average >= 3 * g->stddeviation && + g->measured < g->average - 3 * g->stddeviation)) { + /* Channel becomes bad. Probe downwards. */ + rn->probing = IEEE80211_RA_PROBING_DOWN; + rn->probed_rates = 0; + if (ni->ni_txmcs == rs->min_mcs) { + rsnext = ieee80211_ra_next_rateset(rn, ni); + if (rsnext) { + ieee80211_ra_probe_next_rateset(rn, ni, + rsnext); + } else { + /* Cannot probe further down. */ + rn->probing = IEEE80211_RA_NOT_PROBING; + } + } else { + ni->ni_txmcs = ieee80211_ra_next_mcs(rn, ni); + rn->candidate_rates = (1 << ni->ni_txmcs); + } + } else if (g->loss < 2 * RA_FP_1 || + g->measured > g->average + 3 * g->stddeviation) { + /* Channel becomes good. */ + rn->probing = IEEE80211_RA_PROBING_UP; + rn->probed_rates = 0; + if (ni->ni_txmcs == rs->max_mcs) { + rsnext = ieee80211_ra_next_rateset(rn, ni); + if (rsnext) { + ieee80211_ra_probe_next_rateset(rn, ni, + rsnext); + } else { + /* Cannot probe further up. */ + rn->probing = IEEE80211_RA_NOT_PROBING; + } + } else { + ni->ni_txmcs = ieee80211_ra_next_mcs(rn, ni); + rn->candidate_rates = (1 << ni->ni_txmcs); + } + } else { + /* Remain at current rate. */ + rn->probing = IEEE80211_RA_NOT_PROBING; + rn->probed_rates = 0; + rn->candidate_rates = 0; + } + + splx(s); + + if (rn->probing) { + if (rn->probing & IEEE80211_RA_PROBING_UP) + DPRINTFN(2, ("channel becomes good; probe up\n")); + else + DPRINTFN(2, ("channel becomes bad; probe down\n")); + + DPRINTFN(3, ("measured: %s Mbit/s\n", + ra_fp_sprintf(g->measured))); + DPRINTFN(3, ("average: %s Mbit/s\n", + ra_fp_sprintf(g->average))); + DPRINTFN(3, ("stddeviation: %s\n", + ra_fp_sprintf(g->stddeviation))); + DPRINTFN(3, ("loss: %s%%\n", ra_fp_sprintf(g->loss))); + } +} + +void +ieee80211_ra_node_init(struct ieee80211_ra_node *rn) +{ + memset(rn, 0, sizeof(*rn)); +} diff --git a/sys/net80211/ieee80211_ra.h b/sys/net80211/ieee80211_ra.h new file mode 100644 index 00000000000..8c40b304598 --- /dev/null +++ b/sys/net80211/ieee80211_ra.h @@ -0,0 +1,79 @@ +/* $OpenBSD: ieee80211_ra.h,v 1.1 2021/03/12 16:26:27 stsp Exp $ */ + +/* + * Copyright (c) 2021 Christian Ehrhardt + * Copyright (c) 2021 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * Goodput statistics struct. Measures the effective data rate of an MCS. + * All uint64_t numbers in this struct use fixed-point arithmetic. + */ +struct ieee80211_ra_goodput_stats { + uint64_t measured; /* Most recently measured goodput. */ + uint64_t average; /* Average measured goodput. */ + uint64_t stddeviation; /* Goodput standard deviation. */ + uint64_t loss; /* This rate's loss percentage SFER. */ + uint32_t nprobe_pkts; /* Number of packets in current probe. */ + uint32_t nprobe_fail; /* Number of failed packets. */ +}; + +/* + * Rate adaptation state. + * + * Drivers should not modify any fields of this structure directly. + * Use ieee80211_ra_init() and ieee80211_ra_add_stats() only. + */ +struct ieee80211_ra_node { + /* Bitmaps MCS 0-31. */ + uint32_t valid_probes; + uint32_t valid_rates; + uint32_t candidate_rates; + uint32_t probed_rates; + + /* Probing state. */ + int probing; +#define IEEE80211_RA_NOT_PROBING 0x0 +#define IEEE80211_RA_PROBING_DOWN 0x1 +#define IEEE80211_RA_PROBING_UP 0x2 +#define IEEE80211_RA_PROBING_INTER 0x4 /* combined with UP or DOWN */ + + /* The current best MCS found by probing. */ + int best_mcs; + + /* Goodput statistics for each MCS. */ + struct ieee80211_ra_goodput_stats g[IEEE80211_HT_RATESET_NUM_MCS]; +}; + +/* Initialize rate adaptation state. */ +void ieee80211_ra_node_init(struct ieee80211_ra_node *); + +/* + * Drivers report information about 802.11n/HT Tx attempts here. + * mcs: The HT MCS used during this Tx attempt. + * total: How many Tx attempts (initial attempt + any retries) were made? + * fail: How many of these Tx attempts failed? + */ +void ieee80211_ra_add_stats_ht(struct ieee80211_ra_node *, + struct ieee80211com *, struct ieee80211_node *, + int mcs, unsigned int total, unsigned int fail); + +/* Drivers call this function to update ni->ni_txmcs. */ +void ieee80211_ra_choose(struct ieee80211_ra_node *, + struct ieee80211com *, struct ieee80211_node *); + +/* Get the HT rateset for a particular HT MCS with SGI20 on/off. */ +const struct ieee80211_ht_rateset * ieee80211_ra_get_ht_rateset(int mcs, + int sgi20); -- 2.20.1