[patch 0/9] Rate control rework

[patch 0/9] Rate control rework

[mattias.nissler]

Hi,

this patchset is the result of my recent joint-venture with Stefano. It
introduces a new rate control algorithm based on a PID controller. First
tests show it works much better than the old simple rate control
algorithm.

We think the current patch set is clean enough so we can push it into
2.6.25. However, there are some issues that need some more work:

* The algorithm parameters need more tuning. The current defaults are
  sane, but we hope to get a larger testing audience once this is in the
  tree. Once there are more test results, tuning should be easier.

* It seems mac80211 fails to clean up the rate control algorithm. This
  results in the debugfs entries created by patch 9 not being removed.

* Patch number 8 is actually a change to the debugfs code so I can add
  files for signed variables. I've sent it to Greg KH and LKML, let's
  see what happens. If it doesn't make 2.6.25, we could add similar
  infrastructure locally.

Hm, anything I forgot? Stefano?

Mattias

[patch 5/9] mac80211: Introduce rate behaviour learning algorithm

[mattias.nissler]

From: Stefano Brivio <stefano.brivio@polimi.it>

This patch introduces a learning algorithm in order for the PID controller
to learn how to map adjustment values to rates. This is better described in
code comments.


Signed-off-by: Stefano Brivio <stefano.brivio@polimi.it>

---

Index: rt2x00/net/mac80211/rc80211_pid.c
===================================================================
--- rt2x00.orig/net/mac80211/rc80211_pid.c
+++ rt2x00/net/mac80211/rc80211_pid.c
@@ -2,6 +2,7 @@
  * Copyright 2002-2005, Instant802 Networks, Inc.
  * Copyright 2005, Devicescape Software, Inc.
  * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de>
+ * Copyright 2007, Stefano Brivio <stefano.brivio@polimi.it>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
@@ -39,12 +40,18 @@
  * an actual sliding window. The advantage is that we don't need to keep an
  * array of the last N error values and computation is easier.
  *
- * Once we have the adj value, we need to map it to a TX rate to be selected.
- * For now, we depend on the rates to be ordered in a way such that more robust
- * rates (i.e. such that exhibit a lower framed failed percentage) come first.
- * E.g. for the 802.11b/g case, we first have the b rates in ascending order,
- * then the g rates. The adj simply decides the index of the TX rate in the list
- * to switch to (relative to the current TX rate entry).
+ * Once we have the adj value, we map it to a rate by means of a learning
+ * algorithm. This algorithm keeps the state of the percentual failed frames
+ * difference between rates. The behaviour of the lowest available rate is kept
+ * as a reference value, and every time we switch between two rates, we compute
+ * the difference between the failed frames each rate exhibited. By doing so,
+ * we compare behaviours which different rates exhibited in adjacent timeslices,
+ * thus the comparison is minimally affected by external conditions. This
+ * difference gets propagated to the whole set of measurements, so that the
+ * reference is always the same. Periodically, we normalize this set so that
+ * recent events weigh the most. By comparing the adj value with this set, we
+ * avoid pejorative switches to lower rates and allow for switches to higher
+ * rates if they behaved well.
  *
  * Note that for the computations we use a fixed-point representation to avoid
  * floating point arithmetic. Hence, all values are shifted left by
@@ -78,6 +85,16 @@
  */
 #define RC_PID_TARGET_PF (20 << RC_PID_ARITH_SHIFT)
 
+/* Rate behaviour normalization quantity over time. */
+#define RC_PID_NORM_OFFSET 3
+
+/* Push high rates right after loading. */
+#define RC_PID_FAST_START 0
+
+/* Arithmetic right shift for positive and negative values for ISO C. */
+#define RC_PID_DO_ARITH_RIGHT_SHIFT(x, y) \
+	(x) < 0 ? -((-(x)) >> (y)) : (x) >> (y)
+
 struct rc_pid_sta_info {
 	unsigned long last_change;
 	unsigned long last_sample;
@@ -121,6 +138,21 @@ struct rc_pid_sta_info {
 /* Algorithm parameters. We keep them on a per-algorithm approach, so they can
  * be tuned individually for each interface.
  */
+struct rc_pid_rateinfo {
+
+	/* Map sorted rates to rates in ieee80211_hw_mode. */
+	int index;
+
+	/* Map rates in ieee80211_hw_mode to sorted rates. */
+	int rev_index;
+
+	/* Did we do any measurement on this rate? */
+	bool valid;
+
+	/* Comparison with the lowest rate. */
+	int diff;
+};
+
 struct rc_pid_info {
 
 	/* The failed frames percentage target. */
@@ -130,15 +162,59 @@ struct rc_pid_info {
 	s32 coeff_p;
 	s32 coeff_i;
 	s32 coeff_d;
+
+	/* Rates information. */
+	struct rc_pid_rateinfo *rinfo;
+
+	/* Index of the last used rate. */
+	int oldrate;
 };
 
+/* Shift the adjustment so that we won't switch to a lower rate if it exhibited
+ * a worse failed frames behaviour and we'll choose the highest rate whose
+ * failed frames behaviour is not worse than the one of the original rate
+ * target. While at it, check that the adjustment is within the ranges. Then,
+ * provide the new rate index. */
+static int rate_control_pid_shift_adjust(struct rc_pid_rateinfo *r,
+					 int adj, int cur, int l)
+{
+	int i, j, k, tmp;
+
+	if (cur + adj < 0)
+		return 0;
+	if (cur + adj >= l)
+		return l - 1;
+
+	i = r[cur + adj].rev_index;
+
+	if (unlikely(!r[i].valid))
+		return cur + adj;
+
+	j = r[cur].rev_index;
+
+	if (adj < 0 && r[j].valid) {
+			tmp = i;
+			for (k = j; k >= i; k--)
+				if (r[k].valid && r[k].diff <= r[j].diff)
+					tmp = k;
+			return r[tmp].index;
+	} else if (adj > 0) {
+			tmp = i;
+			for (k = i + 1; k + i < l; k++)
+				if (r[k].valid && r[k].diff <= r[i].diff)
+					tmp = k;
+			return r[tmp].index;
+	}
+	return cur + adj;
+}
 
 static void rate_control_pid_adjust_rate(struct ieee80211_local *local,
-					 struct sta_info *sta, int adj)
+					 struct sta_info *sta, int adj,
+					 struct rc_pid_rateinfo *rinfo)
 {
 	struct ieee80211_sub_if_data *sdata;
 	struct ieee80211_hw_mode *mode;
-	int newidx = sta->txrate + adj;
+	int newidx;
 	int maxrate;
 	int back = (adj > 0) ? 1 : -1;
 
@@ -151,10 +227,8 @@ static void rate_control_pid_adjust_rate
 	mode = local->oper_hw_mode;
 	maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1;
 
-	if (newidx < 0)
-		newidx = 0;
-	else if (newidx >= mode->num_rates)
-		newidx = mode->num_rates - 1;
+	newidx = rate_control_pid_shift_adjust(rinfo, adj, sta->txrate,
+					       mode->num_rates);
 
 	while (newidx != sta->txrate) {
 		if (rate_supported(sta, mode, newidx) &&
@@ -167,18 +241,39 @@ static void rate_control_pid_adjust_rate
 	}
 }
 
+/* Normalize the failed frames per-rate differences. */
+static void rate_control_pid_normalize(struct rc_pid_rateinfo *r, int l)
+{
+	int i;
+
+	if (r[0].diff > RC_PID_NORM_OFFSET)
+		r[0].diff -= RC_PID_NORM_OFFSET;
+	else if (r[0].diff < -RC_PID_NORM_OFFSET)
+		r[0].diff += RC_PID_NORM_OFFSET;
+	for (i = 0; i < l - 1; i++)
+		if (likely(r[i + 1].valid)) {
+			if (r[i + 1].diff > r[i].diff + RC_PID_NORM_OFFSET)
+				r[i + 1].diff -= RC_PID_NORM_OFFSET;
+			else if (r[i + 1].diff <= r[i].diff)
+				r[i + 1].diff += RC_PID_NORM_OFFSET;
+		}
+}
+
 static void rate_control_pid_sample(struct rc_pid_info *pinfo,
 				    struct ieee80211_local *local,
 				    struct sta_info *sta)
 {
 	struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv;
+	struct rc_pid_rateinfo *rinfo = pinfo->rinfo;
+	struct ieee80211_hw_mode *mode;
 	u32 pf;
 	s32 err_avg;
 	s32 err_prop;
 	s32 err_int;
 	s32 err_der;
-	int adj;
+	int adj, i, j, tmp;
 
+	mode = local->oper_hw_mode;
 	spinfo = sta->rate_ctrl_priv;
 	spinfo->last_sample = jiffies;
 
@@ -194,6 +289,23 @@ static void rate_control_pid_sample(stru
 		spinfo->tx_num_failed = 0;
 	}
 
+	/* If we just switched rate, update the rate behaviour info. */
+	if (pinfo->oldrate != sta->txrate) {
+
+		i = rinfo[pinfo->oldrate].rev_index;
+		j = rinfo[sta->txrate].rev_index;
+
+		rinfo[j].valid = 1;
+
+		tmp = (pf - spinfo->last_pf);
+		tmp = RC_PID_DO_ARITH_RIGHT_SHIFT(tmp, RC_PID_ARITH_SHIFT);
+
+		rinfo[j].diff = rinfo[i].diff + tmp;
+		rinfo[j].valid = 1;
+		pinfo->oldrate = sta->txrate;
+	}
+	rate_control_pid_normalize(rinfo, mode->num_rates);
+
 	/* Compute the proportional, integral and derivative errors. */
 	err_prop = RC_PID_TARGET_PF - pf;
 
@@ -207,16 +319,11 @@ static void rate_control_pid_sample(stru
 	/* Compute the controller output. */
 	adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i
 	      + err_der * pinfo->coeff_d);
-
-	/* We need to do an arithmetic right shift. ISO C says this is
-	 * implementation defined for negative left operands. Hence, be
-	 * careful to get it right, also for negative values. */
-	adj = (adj < 0) ? -((-adj) >> (2 * RC_PID_ARITH_SHIFT)) :
-			  adj >> (2 * RC_PID_ARITH_SHIFT);
+	adj = RC_PID_DO_ARITH_RIGHT_SHIFT(adj, 2 * RC_PID_ARITH_SHIFT);
 
 	/* Change rate. */
 	if (adj)
-		rate_control_pid_adjust_rate(local, sta, adj);
+		rate_control_pid_adjust_rate(local, sta, adj, rinfo);
 }
 
 static void rate_control_pid_tx_status(void *priv, struct net_device *dev,
@@ -316,13 +423,61 @@ static void rate_control_pid_rate_init(v
 static void *rate_control_pid_alloc(struct ieee80211_local *local)
 {
 	struct rc_pid_info *pinfo;
+	struct rc_pid_rateinfo *rinfo;
+	struct ieee80211_hw_mode *mode;
+	int i, j, tmp;
+	bool s;
 
 	pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC);
+	if (!pinfo)
+		return NULL;
+
+	/* We can safely assume that oper_hw_mode won't change unless we get
+	 * reinitialized. */
+	mode = local->oper_hw_mode;
+	rinfo = kmalloc(sizeof(*rinfo) * mode->num_rates, GFP_ATOMIC);
+	if (!rinfo) {
+		kfree(pinfo);
+		return NULL;
+	}
+
+	/* Sort the rates. This is optimized for the most common case (i.e.
+	 * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed
+	 * mapping too. */
+	for (i = 0; i < mode->num_rates; i++) {
+		rinfo[i].index = i;
+		rinfo[i].rev_index = i;
+		if (RC_PID_FAST_START) {
+			rinfo[i].valid = 1;
+			rinfo[i].diff = 0;
+		} else
+			rinfo[i].valid = 0;
+	}
+	for (i = 1; i < mode->num_rates; i++) {
+		s = 0;
+		for (j = 0; j < mode->num_rates - i; j++)
+			if (unlikely(mode->rates[rinfo[j].index].rate >
+				     mode->rates[rinfo[j + 1].index].rate)) {
+				tmp = rinfo[j].index;
+				rinfo[j].index = rinfo[j + 1].index;
+				rinfo[j + 1].index = tmp;
+				rinfo[rinfo[j].index].rev_index = j;
+				rinfo[rinfo[j + 1].index].rev_index = j + 1;
+				s = 1;
+			}
+		if (!s)
+			break;
+	}
+
+	rinfo[0].diff = 0;
+	rinfo[0].valid = 1;
 
 	pinfo->target = RC_PID_TARGET_PF;
 	pinfo->coeff_p = RC_PID_COEFF_P;
 	pinfo->coeff_i = RC_PID_COEFF_I;
 	pinfo->coeff_d = RC_PID_COEFF_D;
+	pinfo->rinfo = rinfo;
+	pinfo->oldrate = 0;
 
 	return pinfo;
 }
@@ -330,6 +485,7 @@ static void *rate_control_pid_alloc(stru
 static void rate_control_pid_free(void *priv)
 {
 	struct rc_pid_info *pinfo = priv;
+	kfree(pinfo->rinfo);
 	kfree(pinfo);
 }
 

-- 

[patch 9/9] mac80211: Publish rc80211_pid parameters in debugfs

[mattias.nissler]

This adds all the tuneable parameters used by rc80211_pid to debugfs for easy
testing and tuning.

Signed-off-by: Mattias Nissler <mattias.nissler@gmx.de>
---
 net/mac80211/rc80211_pid.c |   77 +++++++++++++++++++++++++++++++++++++-------
 1 files changed, 65 insertions(+), 12 deletions(-)

Index: rt2x00/net/mac80211/rc80211_pid.c
===================================================================
--- rt2x00.orig/net/mac80211/rc80211_pid.c
+++ rt2x00/net/mac80211/rc80211_pid.c
@@ -66,16 +66,16 @@
  * RC_PID_ARITH_SHIFT.
  */
 
-/* Sampling period for measuring percentage of failed frames. */
-#define RC_PID_INTERVAL (HZ / 1)
+/* Sampling period for measuring percentage of failed frames in 0.001s. */
+#define RC_PID_INTERVAL 1000
 
 /* Exponential averaging smoothness (used for I part of PID controller) */
 #define RC_PID_SMOOTHING_SHIFT 3
 #define RC_PID_SMOOTHING (1 << RC_PID_SMOOTHING_SHIFT)
 
 /* Sharpening factor (used for D part of PID controller) */
-#define RC_PID_SHARPENING_FACTOR 2
-#define RC_PID_SHARPENING_DURATION 1
+#define RC_PID_SHARPENING_FACTOR 0
+#define RC_PID_SHARPENING_DURATION 0
 
 /* Fixed point arithmetic shifting amount. */
 #define RC_PID_ARITH_SHIFT 8
@@ -84,11 +84,11 @@
 #define RC_PID_ARITH_FACTOR (1 << RC_PID_ARITH_SHIFT)
 
 /* Proportional PID component coefficient. */
-#define RC_PID_COEFF_P 15
+#define RC_PID_COEFF_P 20
 /* Integral PID component coefficient. */
 #define RC_PID_COEFF_I 10
 /* Derivative PID component coefficient. */
-#define RC_PID_COEFF_D 15
+#define RC_PID_COEFF_D 0
 
 /* Target failed frames rate for the PID controller. NB: This effectively gives
  * maximum failed frames percentage we're willing to accept. If the wireless
@@ -185,20 +185,21 @@ static void rate_control_pid_adjust_rate
 }
 
 /* Normalize the failed frames per-rate differences. */
-static void rate_control_pid_normalize(struct rc_pid_rateinfo *r, int l)
+static void rate_control_pid_normalize(struct rc_pid_info *pinfo, int l)
 {
-	int i;
+	int i, norm_offset = pinfo->norm_offset;
+	struct rc_pid_rateinfo *r = pinfo->rinfo;
 
-	if (r[0].diff > RC_PID_NORM_OFFSET)
-		r[0].diff -= RC_PID_NORM_OFFSET;
-	else if (r[0].diff < -RC_PID_NORM_OFFSET)
-		r[0].diff += RC_PID_NORM_OFFSET;
+	if (r[0].diff > norm_offset)
+		r[0].diff -= norm_offset;
+	else if (r[0].diff < -norm_offset)
+		r[0].diff += norm_offset;
 	for (i = 0; i < l - 1; i++)
 		if (likely(r[i + 1].valid)) {
-			if (r[i + 1].diff > r[i].diff + RC_PID_NORM_OFFSET)
-				r[i + 1].diff -= RC_PID_NORM_OFFSET;
+			if (r[i + 1].diff > r[i].diff + norm_offset)
+				r[i + 1].diff -= norm_offset;
 			else if (r[i + 1].diff <= r[i].diff)
-				r[i + 1].diff += RC_PID_NORM_OFFSET;
+				r[i + 1].diff += norm_offset;
 		}
 }
 
@@ -215,14 +216,16 @@ static void rate_control_pid_sample(stru
 	s32 err_int;
 	s32 err_der;
 	int adj, i, j, tmp;
+	unsigned long period;
 
 	mode = local->oper_hw_mode;
 	spinfo = sta->rate_ctrl_priv;
 
 	/* In case nothing happened during the previous control interval, turn
 	 * the sharpening factor on. */
-	if (jiffies - spinfo->last_sample > 2 * RC_PID_INTERVAL)
-		spinfo->sharp_cnt = RC_PID_SHARPENING_DURATION;
+	period = (HZ / 1000) * pinfo->sampling_period;
+	if (jiffies - spinfo->last_sample > 2 * period)
+		spinfo->sharp_cnt = pinfo->sharpen_duration;
 
 	spinfo->last_sample = jiffies;
 
@@ -253,17 +256,17 @@ static void rate_control_pid_sample(stru
 		rinfo[j].valid = 1;
 		pinfo->oldrate = sta->txrate;
 	}
-	rate_control_pid_normalize(rinfo, mode->num_rates);
+	rate_control_pid_normalize(pinfo, mode->num_rates);
 
 	/* Compute the proportional, integral and derivative errors. */
-	err_prop = RC_PID_TARGET_PF - pf;
+	err_prop = pinfo->target - pf;
 
-	err_avg = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT;
+	err_avg = spinfo->err_avg_sc >> pinfo->smoothing_shift;
 	spinfo->err_avg_sc = spinfo->err_avg_sc - err_avg + err_prop;
-	err_int = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT;
+	err_int = spinfo->err_avg_sc >> pinfo->smoothing_shift;
 
-	err_der = pf - spinfo->last_pf
-		  * (1 + RC_PID_SHARPENING_FACTOR * spinfo->sharp_cnt);
+	err_der = (pf - spinfo->last_pf) *
+		  (1 + pinfo->sharpen_factor * spinfo->sharp_cnt);
 	spinfo->last_pf = pf;
 	if (spinfo->sharp_cnt)
 			spinfo->sharp_cnt--;
@@ -292,6 +295,7 @@ static void rate_control_pid_tx_status(v
 	struct rc_pid_info *pinfo = priv;
 	struct sta_info *sta;
 	struct rc_pid_sta_info *spinfo;
+	unsigned long period;
 
 	sta = sta_info_get(local, hdr->addr1);
 
@@ -336,7 +340,8 @@ static void rate_control_pid_tx_status(v
 	sta->tx_num_mpdu_fail += status->retry_count;
 
 	/* Update PID controller state. */
-	if (time_after(jiffies, spinfo->last_sample + RC_PID_INTERVAL))
+	period = (HZ / 1000) * pinfo->sampling_period;
+	if (time_after(jiffies, spinfo->last_sample + period))
 		rate_control_pid_sample(pinfo, local, sta);
 
 	sta_info_put(sta);
@@ -394,6 +399,9 @@ static void *rate_control_pid_alloc(stru
 	struct ieee80211_hw_mode *mode;
 	int i, j, tmp;
 	bool s;
+#ifdef CONFIG_MAC80211_DEBUGFS
+	struct rc_pid_debugfs_entries *de;
+#endif
 
 	pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC);
 	if (!pinfo)
@@ -414,7 +422,7 @@ static void *rate_control_pid_alloc(stru
 	for (i = 0; i < mode->num_rates; i++) {
 		rinfo[i].index = i;
 		rinfo[i].rev_index = i;
-		if (RC_PID_FAST_START) {
+		if (pinfo->fast_start) {
 			rinfo[i].valid = 1;
 			rinfo[i].diff = 0;
 		} else
@@ -440,18 +448,72 @@ static void *rate_control_pid_alloc(stru
 	rinfo[0].valid = 1;
 
 	pinfo->target = RC_PID_TARGET_PF;
+	pinfo->sampling_period = RC_PID_INTERVAL;
 	pinfo->coeff_p = RC_PID_COEFF_P;
 	pinfo->coeff_i = RC_PID_COEFF_I;
 	pinfo->coeff_d = RC_PID_COEFF_D;
+	pinfo->smoothing_shift = RC_PID_SMOOTHING_SHIFT;
+	pinfo->sharpen_factor = RC_PID_SHARPENING_FACTOR;
+	pinfo->sharpen_duration = RC_PID_SHARPENING_DURATION;
+	pinfo->norm_offset = RC_PID_NORM_OFFSET;
+	pinfo->fast_start = RC_PID_FAST_START;
 	pinfo->rinfo = rinfo;
 	pinfo->oldrate = 0;
 
+#ifdef CONFIG_MAC80211_DEBUGFS
+	de = &pinfo->dentries;
+	de->dir = debugfs_create_dir("rc80211_pid",
+				     local->hw.wiphy->debugfsdir);
+	de->target = debugfs_create_u32("target_pf", S_IRUSR | S_IWUSR,
+					de->dir, &pinfo->target);
+	de->sampling_period = debugfs_create_u32("sampling_period",
+						 S_IRUSR | S_IWUSR, de->dir,
+						 &pinfo->sampling_period);
+	de->coeff_p = debugfs_create_s32("coeff_p", S_IRUSR | S_IWUSR,
+					 de->dir, &pinfo->coeff_p);
+	de->coeff_i = debugfs_create_s32("coeff_i", S_IRUSR | S_IWUSR,
+					 de->dir, &pinfo->coeff_i);
+	de->coeff_d = debugfs_create_s32("coeff_d", S_IRUSR | S_IWUSR,
+					 de->dir, &pinfo->coeff_d);
+	de->smoothing_shift = debugfs_create_u32("smoothing_shift",
+						 S_IRUSR | S_IWUSR, de->dir,
+						 &pinfo->smoothing_shift);
+	de->sharpen_factor = debugfs_create_u32("sharpen_factor",
+					       S_IRUSR | S_IWUSR, de->dir,
+					       &pinfo->sharpen_factor);
+	de->sharpen_duration = debugfs_create_u32("sharpen_duration",
+						  S_IRUSR | S_IWUSR, de->dir,
+						  &pinfo->sharpen_duration);
+	de->norm_offset = debugfs_create_u32("norm_offset",
+					     S_IRUSR | S_IWUSR, de->dir,
+					     &pinfo->norm_offset);
+	de->fast_start = debugfs_create_bool("fast_start",
+					     S_IRUSR | S_IWUSR, de->dir,
+					     &pinfo->fast_start);
+#endif
+
 	return pinfo;
 }
 
 static void rate_control_pid_free(void *priv)
 {
 	struct rc_pid_info *pinfo = priv;
+#ifdef CONFIG_MAC80211_DEBUGFS
+	struct rc_pid_debugfs_entries *de = &pinfo->dentries;
+
+	debugfs_remove(de->fast_start);
+	debugfs_remove(de->norm_offset);
+	debugfs_remove(de->sharpen_duration);
+	debugfs_remove(de->sharpen_factor);
+	debugfs_remove(de->smoothing_shift);
+	debugfs_remove(de->coeff_d);
+	debugfs_remove(de->coeff_i);
+	debugfs_remove(de->coeff_p);
+	debugfs_remove(de->sampling_period);
+	debugfs_remove(de->target);
+	debugfs_remove(de->dir);
+#endif
+
 	kfree(pinfo->rinfo);
 	kfree(pinfo);
 }
Index: rt2x00/net/mac80211/rc80211_pid_debugfs.h
===================================================================
--- rt2x00.orig/net/mac80211/rc80211_pid_debugfs.h
+++ rt2x00/net/mac80211/rc80211_pid_debugfs.h
@@ -9,6 +9,20 @@
 #ifndef RC80211_PID_DEBUGFS_H
 #define RC80211_PID_DEBUGFS_H
 
+struct rc_pid_debugfs_entries {
+	struct dentry *dir;
+	struct dentry *target;
+	struct dentry *sampling_period;
+	struct dentry *coeff_p;
+	struct dentry *coeff_i;
+	struct dentry *coeff_d;
+	struct dentry *smoothing_shift;
+	struct dentry *sharpen_factor;
+	struct dentry *sharpen_duration;
+	struct dentry *norm_offset;
+	struct dentry *fast_start;
+};
+
 enum rc_pid_event_type {
 	RC_PID_EVENT_TYPE_TX_STATUS,
 	RC_PID_EVENT_TYPE_RATE_CHANGE,
Index: rt2x00/net/mac80211/rc80211_pid.h
===================================================================
--- rt2x00.orig/net/mac80211/rc80211_pid.h
+++ rt2x00/net/mac80211/rc80211_pid.h
@@ -94,8 +94,8 @@ struct rc_pid_info {
 	/* Exponential averaging shift. */
 	unsigned int smoothing_shift;
 
-	/* Sharpening shift and duration. */
-	unsigned int sharpen_shift;
+	/* Sharpening factor and duration. */
+	unsigned int sharpen_factor;
 	unsigned int sharpen_duration;
 
 	/* Normalization offset. */
@@ -109,6 +109,11 @@ struct rc_pid_info {
 
 	/* Index of the last used rate. */
 	int oldrate;
+
+#ifdef CONFIG_MAC80211_DEBUGFS
+	/* Debugfs entries created for the parameters above. */
+	struct rc_pid_debugfs_entries dentries;
+#endif
 };
 
 #endif /* RC80211_PID_H */

-- 

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 698 bytes --]


> -What:	iee80211 softmac wireless networking component
> +What:	ieee80211 softmac wireless networking component


Unrelated change, please separate.

> +
> +What:	rc80211-simple rate control algorithm for mac80211
> +When:	2.6.26
> +Files:	net/mac80211/rc80211-simple.c
> +Why:	This algorithm was provided for reference but always exhibited bad
> +	responsiveness and performance and has some serious flaws. It has been
> +	replaced by rc80211-pid.
> +Who:	Stefano Brivio <stefano.brivio@polimi.it>

I don't think we really want to do this. We can't even change the
algorithm anyway except by recompiling with a different default.

Will do a code review tomorrow.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Stefano Brivio]

On Mon, 17 Dec 2007 01:49:06 +0100
Johannes Berg <johannes@sipsolutions.net> wrote:

> > -What:	iee80211 softmac wireless networking component
> > +What:	ieee80211 softmac wireless networking component
> 
> 
> Unrelated change, please separate.

Will do.
 
> > +
> > +What:	rc80211-simple rate control algorithm for mac80211
> > +When:	2.6.26
> > +Files:	net/mac80211/rc80211-simple.c
> > +Why:	This algorithm was provided for reference but always exhibited bad
> > +	responsiveness and performance and has some serious flaws. It has been
> > +	replaced by rc80211-pid.
> > +Who:	Stefano Brivio <stefano.brivio@polimi.it>
> 
> I don't think we really want to do this. We can't even change the
> algorithm anyway except by recompiling with a different default.

What do you suggest instead?


--
Ciao
Stefano

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 609 bytes --]


> > > +What:	rc80211-simple rate control algorithm for mac80211
> > > +When:	2.6.26
> > > +Files:	net/mac80211/rc80211-simple.c
> > > +Why:	This algorithm was provided for reference but always exhibited bad
> > > +	responsiveness and performance and has some serious flaws. It has been
> > > +	replaced by rc80211-pid.
> > > +Who:	Stefano Brivio <stefano.brivio@polimi.it>
> > 
> > I don't think we really want to do this. We can't even change the
> > algorithm anyway except by recompiling with a different default.
> 
> What do you suggest instead?

Just kick it out right away.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Stefano Brivio]

On Mon, 17 Dec 2007 01:54:33 +0100
Johannes Berg <johannes@sipsolutions.net> wrote:

> 
> > > > +What:	rc80211-simple rate control algorithm for mac80211
> > > > +When:	2.6.26
> > > > +Files:	net/mac80211/rc80211-simple.c
> > > > +Why:	This algorithm was provided for reference but always exhibited bad
> > > > +	responsiveness and performance and has some serious flaws. It has been
> > > > +	replaced by rc80211-pid.
> > > > +Who:	Stefano Brivio <stefano.brivio@polimi.it>
> > > 
> > > I don't think we really want to do this. We can't even change the
> > > algorithm anyway except by recompiling with a different default.
> > 
> > What do you suggest instead?
> 
> Just kick it out right away.

That was my original proposal, but during a recent discussion John
suggested not to remove rc80211-simple right now, as it's currently
almost working for a lot of people. John, any suggestions?


-- 
Ciao
Stefano

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 349 bytes --]


> That was my original proposal, but during a recent discussion John
> suggested not to remove rc80211-simple right now, as it's currently
> almost working for a lot of people. John, any suggestions?

Those people can fix the bitrate at 1M if the pid algorithm becomes
problematic, that's what simple currently does in practice.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Mattias Nissler]

On Mon, 2007-12-17 at 02:09 +0100, Johannes Berg wrote:
> > That was my original proposal, but during a recent discussion John
> > suggested not to remove rc80211-simple right now, as it's currently
> > almost working for a lot of people. John, any suggestions?
> 
> Those people can fix the bitrate at 1M if the pid algorithm becomes
> problematic, that's what simple currently does in practice.

Agreed. So what flavour of this patch do you want? John?

Mattias

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[John W. Linville]

On Mon, Dec 17, 2007 at 10:56:14AM +0100, Mattias Nissler wrote:
> 
> On Mon, 2007-12-17 at 02:09 +0100, Johannes Berg wrote:
> > > That was my original proposal, but during a recent discussion John
> > > suggested not to remove rc80211-simple right now, as it's currently
> > > almost working for a lot of people. John, any suggestions?
> > 
> > Those people can fix the bitrate at 1M if the pid algorithm becomes
> > problematic, that's what simple currently does in practice.
> 
> Agreed. So what flavour of this patch do you want? John?

My "Spidey sense" tells me it would be good to keep the old one around
for a little while... :-)

Besides, as we have seen recently people often get quite upset when
you remove a feature that they perceive to be working for them --
no matter how much better the alternative may be.  It would be better
to give them some warning.

John
-- 
John W. Linville
linville@tuxdriver.com

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 491 bytes --]


> My "Spidey sense" tells me it would be good to keep the old one around
> for a little while... :-)
> 
> Besides, as we have seen recently people often get quite upset when
> you remove a feature that they perceive to be working for them --
> no matter how much better the alternative may be.  It would be better
> to give them some warning.

Then we need to introduce a Kconfig option for making the simple one
default because we don't have run-time switching yet.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 4/9] mac80211: Make PID rate control algorithm the default

[Mattias Nissler]

On Mon, 2007-12-17 at 01:50 +0100, Stefano Brivio wrote:
> On Mon, 17 Dec 2007 01:49:06 +0100
> Johannes Berg <johannes@sipsolutions.net> wrote:
> 
> > > -What:	iee80211 softmac wireless networking component
> > > +What:	ieee80211 softmac wireless networking component
> > 
> > 
> > Unrelated change, please separate.
> 
> Will do.

Done so :-)

Re: [patch 0/9] Rate control rework

[Mattias Nissler]

Hi,

I'm sorry most of my mails didn't make it to the list. I'll resubmit
tonight, also correcting issues that you (those that got the complete
original set via PM, you know who you are) find until then.

Mattias

Re: [patch 0/9] Rate control rework

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 878 bytes --]

> * It seems mac80211 fails to clean up the rate control algorithm. This
>   results in the debugfs entries created by patch 9 not being removed.

Probably a bug then, though I can't find it right now, the references
all look balanced and if they weren't then we'd not have been able to
rmmod rc80211_simple when it was still around. Not sure, can you try to
see what the problem is and maybe even fix it?

It does, however, look like the whole rate control code needs a revamp.
Looks like Jiri got busy there with krefs too without giving it too much
thought... It looks like all that can be converted to RCU just as well
as all the other stuff I already converted, I don't see a reason to keep
a reference count of the rate control algorithm for each sta.

If you fix the free problem I'll take a look at fixing the locking/refs
stuff there later.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 0/9] Rate control rework

[Mattias Nissler]

On Mon, 2007-12-17 at 15:05 +0100, Johannes Berg wrote:
> > * It seems mac80211 fails to clean up the rate control algorithm. This
> >   results in the debugfs entries created by patch 9 not being removed.
> 
> Probably a bug then, though I can't find it right now, the references
> all look balanced and if they weren't then we'd not have been able to
> rmmod rc80211_simple when it was still around. Not sure, can you try to
> see what the problem is and maybe even fix it?

Will do, after I've addressed the other issues.

> 
> It does, however, look like the whole rate control code needs a revamp.
> Looks like Jiri got busy there with krefs too without giving it too much
> thought... It looks like all that can be converted to RCU just as well
> as all the other stuff I already converted, I don't see a reason to keep
> a reference count of the rate control algorithm for each sta.

What bothers me most is the fact that we have several ways to refer to a
rate: Either we use struct ieee80211_rate pointers or indices into
local->oper_hw_mode->rates[]. This is not very consistent. Furthermore,
there is oper_hw_mode vs scan_hw_mode. So potentially even to rates[].
That sucks.

> 
> If you fix the free problem I'll take a look at fixing the locking/refs
> stuff there later.

I'll happily leave that to you, I don't have much spare time.

Mattias

Re: [patch 0/9] Rate control rework

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 794 bytes --]


> > It does, however, look like the whole rate control code needs a revamp.
> > Looks like Jiri got busy there with krefs too without giving it too much
> > thought... It looks like all that can be converted to RCU just as well
> > as all the other stuff I already converted, I don't see a reason to keep
> > a reference count of the rate control algorithm for each sta.
> 
> What bothers me most is the fact that we have several ways to refer to a
> rate: Either we use struct ieee80211_rate pointers or indices into
> local->oper_hw_mode->rates[]. This is not very consistent. Furthermore,
> there is oper_hw_mode vs scan_hw_mode. So potentially even to rates[].
> That sucks.

Yeah. That cfg80211 rate/channel stuff I had addressed some of it, but
not all, iirc.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 8/9] debugfs: Revamp debugfs_create_{u,x,s}{8,16,32,64} to support signed integers

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 897 bytes --]

On Mon, 2007-12-17 at 01:20 +0100, mattias.nissler@gmx.de wrote:
> This makes debugfs use its own file_operations for the value accessor files
> created by debugfs_create_XXX. Having that, we can also have proper versions
> for signed integers.

I think I'd probably prefer if this didn't duplicate all the fs/libfs.c
simple attribute functionality but extended libfs instead to define
attributes that can have their own print/scan functions. Or something
like that.

As far as I can tell, the only reason you're doing this huge amount of
code duplication is the "(unsigned long long)" cast in fs/libfs.c, or am
I missing something?

You might even be able to get around that: define the get() function in
simple_attr to return unsigned long long (rather than u64 as it does
now) and then remove the cast. Then, %lld will still print a negative
number if applicable.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 828 bytes --]

Re: [patch 8/9] debugfs: Revamp debugfs_create_{u,x,s}{8,16,32,64} to support signed integers

[Mattias Nissler]

On Mon, 2007-12-17 at 17:43 +0100, Johannes Berg wrote:
> On Mon, 2007-12-17 at 01:20 +0100, mattias.nissler@gmx.de wrote:
> > This makes debugfs use its own file_operations for the value accessor files
> > created by debugfs_create_XXX. Having that, we can also have proper versions
> > for signed integers.
> 
> I think I'd probably prefer if this didn't duplicate all the fs/libfs.c
> simple attribute functionality but extended libfs instead to define
> attributes that can have their own print/scan functions. Or something
> like that.

Yeah, I actually tried that. See this thread:
http://lkml.org/lkml/2007/12/16/78

As far as I understand, your point is the same what Greg said.

> 
> As far as I can tell, the only reason you're doing this huge amount of
> code duplication is the "(unsigned long long)" cast in fs/libfs.c, or am
> I missing something?

Yes. Moreover, conceptually it's much cleaner to use the correct data
type.

> 
> You might even be able to get around that: define the get() function in
> simple_attr to return unsigned long long (rather than u64 as it does
> now) and then remove the cast. Then, %lld will still print a negative
> number if applicable.

And the compiler doesn't even complain. That's a cool hack ;-) But
still, it's a hack.

Mattias