From: Felix Fietkau <nbd@nbd.name>
To: linux-wireless@vger.kernel.org
Cc: johannes@sipsolutions.net, thomas.huehn@evernet-eg.de
Subject: [PATCH 07/10] mac80211: minstrel: store probability variance instead of standard deviation
Date: Wed, 14 Dec 2016 20:47:00 +0100 [thread overview]
Message-ID: <20161214194703.33429-7-nbd@nbd.name> (raw)
In-Reply-To: <20161214194703.33429-1-nbd@nbd.name>
This avoids the costly int_sqrt calls in the statistics update and moves
it to the debugfs code instead.
This also fixes an overflow in the previous standard deviation
calculation.
Signed-off-by: Thomas Huehn <thomas.huehn@evernet-eg.de>
Signed-off-by: Felix Fietkau <nbd@nbd.name>
---
net/mac80211/rc80211_minstrel.c | 8 ++++----
net/mac80211/rc80211_minstrel.h | 25 ++++++++++++++-----------
net/mac80211/rc80211_minstrel_debugfs.c | 8 ++++++--
net/mac80211/rc80211_minstrel_ht_debugfs.c | 8 ++++++--
4 files changed, 30 insertions(+), 19 deletions(-)
diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index a284ea0..11a4cc3 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -168,10 +168,10 @@ minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs)
mrs->prob_ewma = cur_prob;
} else {
/* update exponential weighted moving variance */
- mrs->prob_ewmsd = minstrel_ewmsd(mrs->prob_ewmsd,
- cur_prob,
- mrs->prob_ewma,
- EWMA_LEVEL);
+ mrs->prob_ewmv = minstrel_ewmv(mrs->prob_ewmv,
+ cur_prob,
+ mrs->prob_ewma,
+ EWMA_LEVEL);
/*update exponential weighted moving avarage */
mrs->prob_ewma = minstrel_ewma(mrs->prob_ewma,
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 03716fd..ea86e67 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -36,21 +36,16 @@ minstrel_ewma(int old, int new, int weight)
}
/*
- * Perform EWMSD (Exponentially Weighted Moving Standard Deviation) calculation
+ * Perform EWMV (Exponentially Weighted Moving Variance) calculation
*/
static inline int
-minstrel_ewmsd(int old_ewmsd, int cur_prob, int prob_ewma, int weight)
+minstrel_ewmv(int old_ewmv, int cur_prob, int prob_ewma, int weight)
{
- int diff, incr, tmp_var;
+ int diff, incr;
- /* calculate exponential weighted moving variance */
- diff = MINSTREL_TRUNC((cur_prob - prob_ewma) * 1000000);
+ diff = cur_prob - prob_ewma;
incr = (EWMA_DIV - weight) * diff / EWMA_DIV;
- tmp_var = old_ewmsd * old_ewmsd;
- tmp_var = weight * (tmp_var + diff * incr / 1000000) / EWMA_DIV;
-
- /* return standard deviation */
- return (u16) int_sqrt(tmp_var);
+ return weight * (old_ewmv + MINSTREL_TRUNC(diff * incr)) / EWMA_DIV;
}
struct minstrel_rate_stats {
@@ -65,7 +60,7 @@ struct minstrel_rate_stats {
* prob_ewma - exponential weighted moving average of prob
* prob_ewmsd - exp. weighted moving standard deviation of prob */
unsigned int prob_ewma;
- u16 prob_ewmsd;
+ u16 prob_ewmv;
/* maximum retry counts */
u8 retry_count;
@@ -151,6 +146,14 @@ struct minstrel_debugfs_info {
char buf[];
};
+/* Get EWMSD (Exponentially Weighted Moving Standard Deviation) * 10 */
+static inline int
+minstrel_get_ewmsd10(struct minstrel_rate_stats *mrs)
+{
+ unsigned int ewmv = mrs->prob_ewmv;
+ return int_sqrt(MINSTREL_TRUNC(ewmv * 1000 * 1000));
+}
+
extern const struct rate_control_ops mac80211_minstrel;
void minstrel_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);
void minstrel_remove_sta_debugfs(void *priv, void *priv_sta);
diff --git a/net/mac80211/rc80211_minstrel_debugfs.c b/net/mac80211/rc80211_minstrel_debugfs.c
index ca0bafd..36fc971 100644
--- a/net/mac80211/rc80211_minstrel_debugfs.c
+++ b/net/mac80211/rc80211_minstrel_debugfs.c
@@ -93,6 +93,7 @@ minstrel_stats_open(struct inode *inode, struct file *file)
for (i = 0; i < mi->n_rates; i++) {
struct minstrel_rate *mr = &mi->r[i];
struct minstrel_rate_stats *mrs = &mi->r[i].stats;
+ unsigned int prob_ewmsd;
*(p++) = (i == mi->max_tp_rate[0]) ? 'A' : ' ';
*(p++) = (i == mi->max_tp_rate[1]) ? 'B' : ' ';
@@ -108,6 +109,7 @@ minstrel_stats_open(struct inode *inode, struct file *file)
tp_max = minstrel_get_tp_avg(mr, MINSTREL_FRAC(100,100));
tp_avg = minstrel_get_tp_avg(mr, mrs->prob_ewma);
eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
+ prob_ewmsd = minstrel_get_ewmsd10(mrs);
p += sprintf(p, "%4u.%1u %4u.%1u %3u.%1u %3u.%1u"
" %3u %3u %-3u "
@@ -115,7 +117,7 @@ minstrel_stats_open(struct inode *inode, struct file *file)
tp_max / 10, tp_max % 10,
tp_avg / 10, tp_avg % 10,
eprob / 10, eprob % 10,
- mrs->prob_ewmsd / 10, mrs->prob_ewmsd % 10,
+ prob_ewmsd / 10, prob_ewmsd % 10,
mrs->retry_count,
mrs->last_success,
mrs->last_attempts,
@@ -159,6 +161,7 @@ minstrel_stats_csv_open(struct inode *inode, struct file *file)
for (i = 0; i < mi->n_rates; i++) {
struct minstrel_rate *mr = &mi->r[i];
struct minstrel_rate_stats *mrs = &mi->r[i].stats;
+ unsigned int prob_ewmsd;
p += sprintf(p, "%s" ,((i == mi->max_tp_rate[0]) ? "A" : ""));
p += sprintf(p, "%s" ,((i == mi->max_tp_rate[1]) ? "B" : ""));
@@ -174,13 +177,14 @@ minstrel_stats_csv_open(struct inode *inode, struct file *file)
tp_max = minstrel_get_tp_avg(mr, MINSTREL_FRAC(100,100));
tp_avg = minstrel_get_tp_avg(mr, mrs->prob_ewma);
eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
+ prob_ewmsd = minstrel_get_ewmsd10(mrs);
p += sprintf(p, "%u.%u,%u.%u,%u.%u,%u.%u,%u,%u,%u,"
"%llu,%llu,%d,%d\n",
tp_max / 10, tp_max % 10,
tp_avg / 10, tp_avg % 10,
eprob / 10, eprob % 10,
- mrs->prob_ewmsd / 10, mrs->prob_ewmsd % 10,
+ prob_ewmsd / 10, prob_ewmsd % 10,
mrs->retry_count,
mrs->last_success,
mrs->last_attempts,
diff --git a/net/mac80211/rc80211_minstrel_ht_debugfs.c b/net/mac80211/rc80211_minstrel_ht_debugfs.c
index 0cecd23..7d969e3 100644
--- a/net/mac80211/rc80211_minstrel_ht_debugfs.c
+++ b/net/mac80211/rc80211_minstrel_ht_debugfs.c
@@ -41,6 +41,7 @@ minstrel_ht_stats_dump(struct minstrel_ht_sta *mi, int i, char *p)
struct minstrel_rate_stats *mrs = &mi->groups[i].rates[j];
static const int bitrates[4] = { 10, 20, 55, 110 };
int idx = i * MCS_GROUP_RATES + j;
+ unsigned int prob_ewmsd;
if (!(mi->supported[i] & BIT(j)))
continue;
@@ -84,6 +85,7 @@ minstrel_ht_stats_dump(struct minstrel_ht_sta *mi, int i, char *p)
tp_max = minstrel_ht_get_tp_avg(mi, i, j, MINSTREL_FRAC(100, 100));
tp_avg = minstrel_ht_get_tp_avg(mi, i, j, mrs->prob_ewma);
eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
+ prob_ewmsd = minstrel_get_ewmsd10(mrs);
p += sprintf(p, "%4u.%1u %4u.%1u %3u.%1u %3u.%1u"
" %3u %3u %-3u "
@@ -91,7 +93,7 @@ minstrel_ht_stats_dump(struct minstrel_ht_sta *mi, int i, char *p)
tp_max / 10, tp_max % 10,
tp_avg / 10, tp_avg % 10,
eprob / 10, eprob % 10,
- mrs->prob_ewmsd / 10, mrs->prob_ewmsd % 10,
+ prob_ewmsd / 10, prob_ewmsd % 10,
mrs->retry_count,
mrs->last_success,
mrs->last_attempts,
@@ -185,6 +187,7 @@ minstrel_ht_stats_csv_dump(struct minstrel_ht_sta *mi, int i, char *p)
struct minstrel_rate_stats *mrs = &mi->groups[i].rates[j];
static const int bitrates[4] = { 10, 20, 55, 110 };
int idx = i * MCS_GROUP_RATES + j;
+ unsigned int prob_ewmsd;
if (!(mi->supported[i] & BIT(j)))
continue;
@@ -225,13 +228,14 @@ minstrel_ht_stats_csv_dump(struct minstrel_ht_sta *mi, int i, char *p)
tp_max = minstrel_ht_get_tp_avg(mi, i, j, MINSTREL_FRAC(100, 100));
tp_avg = minstrel_ht_get_tp_avg(mi, i, j, mrs->prob_ewma);
eprob = MINSTREL_TRUNC(mrs->prob_ewma * 1000);
+ prob_ewmsd = minstrel_get_ewmsd10(mrs);
p += sprintf(p, "%u.%u,%u.%u,%u.%u,%u.%u,%u,%u,"
"%u,%llu,%llu,",
tp_max / 10, tp_max % 10,
tp_avg / 10, tp_avg % 10,
eprob / 10, eprob % 10,
- mrs->prob_ewmsd / 10, mrs->prob_ewmsd % 10,
+ prob_ewmsd / 10, prob_ewmsd % 10,
mrs->retry_count,
mrs->last_success,
mrs->last_attempts,
--
2.10.1
next prev parent reply other threads:[~2016-12-14 19:47 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-14 19:46 [PATCH 01/10] mac80211: minstrel_ht: move supported bitrate mask out of group data Felix Fietkau
2016-12-14 19:46 ` [PATCH 02/10] mac80211: minstrel_ht: move short preamble check out of get_rate Felix Fietkau
2016-12-14 19:46 ` [PATCH 03/10] mac80211: minstrel_ht: make att_hist and succ_hist u32 instead of u64 Felix Fietkau
2016-12-14 19:46 ` [PATCH 04/10] mac80211: check for MCS in ieee80211_duration before fetching chanctx Felix Fietkau
2016-12-14 19:46 ` [PATCH 05/10] mac80211: minstrel: remove cur_prob from debugfs Felix Fietkau
2016-12-14 19:46 ` [PATCH 06/10] mac80211: minstrel: reduce MINSTREL_SCALE Felix Fietkau
2016-12-14 19:47 ` Felix Fietkau [this message]
2016-12-14 19:47 ` [PATCH 08/10] mac80211: minstrel: make prob_ewma u16 instead of u32 Felix Fietkau
2016-12-14 19:47 ` [PATCH 09/10] mac80211: minstrel_ht: remove obsolete #if for >= 3 streams Felix Fietkau
2016-12-14 19:47 ` [PATCH 10/10] mac80211: minstrel: avoid port control frames for sampling Felix Fietkau
2016-12-15 10:08 ` [PATCH 01/10] mac80211: minstrel_ht: move supported bitrate mask out of group data Johannes Berg
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20161214194703.33429-7-nbd@nbd.name \
--to=nbd@nbd.name \
--cc=johannes@sipsolutions.net \
--cc=linux-wireless@vger.kernel.org \
--cc=thomas.huehn@evernet-eg.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).