[RFT] [PATCH] rc80211-pid: fix rate adjusting

[RFT] [PATCH] rc80211-pid: fix rate adjusting

[Stefano Brivio]

Merge rate_control_pid_shift_adjust() to rate_control_pid_adjust_rate()
in order to make the learning algorithm aware of constraints on rates. Also
add some comments and rename variables.

This fixes a bug which prevented 802.11b/g non-AP STAs from working with
802.11b only AP STAs.

Signed-off-by: Stefano Brivio <stefano.brivio@polimi.it>
---
John, this should supersede the previously posted patches 1/2 and 2/2. This
needs further testing anyway.

Larry, Lars, please test this. It works for me, both with 802.11b only and
802.11b/g settings on my AP.

Index: wireless-2.6/net/mac80211/rc80211_pid_algo.c
===================================================================
--- wireless-2.6.orig/net/mac80211/rc80211_pid_algo.c
+++ wireless-2.6/net/mac80211/rc80211_pid_algo.c
@@ -2,7 +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>
+ * Copyright 2007-2008, 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
@@ -64,71 +64,66 @@
  */
 
 
-/* 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;
-
-	j = r[cur].rev_index;
-	i = j + adj;
-
-	if (i < 0)
-		return r[0].index;
-	if (i >= l - 1)
-		return r[l - 1].index;
-
-	tmp = i;
-
-	if (adj < 0) {
-		for (k = j; k >= i; k--)
-			if (r[k].diff <= r[j].diff)
-				tmp = k;
-	} else {
-		for (k = i + 1; k + i < l; k++)
-			if (r[k].diff <= r[i].diff)
-				tmp = k;
-	}
-
-	return r[tmp].index;
-}
-
+/* Adjust the rate while ensuring 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 new rate is valid. */
 static void rate_control_pid_adjust_rate(struct ieee80211_local *local,
 					 struct sta_info *sta, int adj,
 					 struct rc_pid_rateinfo *rinfo)
 {
 	struct ieee80211_sub_if_data *sdata;
 	struct ieee80211_supported_band *sband;
-	int newidx;
-	int maxrate;
-	int back = (adj > 0) ? 1 : -1;
+	int cur_sorted, new_sorted, probe, tmp, n_bitrates, band;
+	int cur = sta->txrate_idx;
 
 	sdata = IEEE80211_DEV_TO_SUB_IF(sta->dev);
-
 	sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
-	maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1;
+	band = sband->band;
+	n_bitrates = sband->n_bitrates;
 
-	newidx = rate_control_pid_shift_adjust(rinfo, adj, sta->txrate_idx,
-					       sband->n_bitrates);
+	/* Map passed arguments to sorted values. */
+	cur_sorted = rinfo[cur].rev_index;
+	new_sorted = cur_sorted + adj;
+
+	/* Check limits. */
+	if (new_sorted < 0)
+		new_sorted = rinfo[0].rev_index;
+	else if (new_sorted >= n_bitrates)
+		new_sorted = rinfo[n_bitrates - 1].rev_index;
 
-	while (newidx != sta->txrate_idx) {
-		if (rate_supported(sta, sband->band, newidx) &&
-		    (maxrate < 0 || newidx <= maxrate)) {
-			sta->txrate_idx = newidx;
-			break;
-		}
+	tmp = new_sorted;
 
-		newidx += back;
+	if (adj < 0) {
+		/* Ensure that the rate decrease isn't disadvantageous. */
+		for (probe = cur_sorted; probe >= new_sorted; probe--)
+			if (rinfo[probe].diff <= rinfo[cur_sorted].diff &&
+			    rate_supported(sta, band, rinfo[probe].index))
+				tmp = probe;
+	} else {
+		/* Look for rate increase with zero (or below) cost. */
+		for (probe = new_sorted + 1; probe < n_bitrates; probe++)
+			if (rinfo[probe].diff <= rinfo[new_sorted].diff &&
+			    rate_supported(sta, band, rinfo[probe].index))
+				tmp = probe;
 	}
 
+	/* Fit the rate found to the nearest supported rate. */
+	do {
+		if (rate_supported(sta, band, rinfo[tmp].index)) {
+			sta->txrate_idx = rinfo[tmp].index;
+			break;
+		}
+		if (adj < 0)
+			tmp--;
+		else
+			tmp++;
+	} while (tmp < n_bitrates && tmp >= 0);
+
 #ifdef CONFIG_MAC80211_DEBUGFS
 	rate_control_pid_event_rate_change(
 		&((struct rc_pid_sta_info *)sta->rate_ctrl_priv)->events,
-		newidx, sband->bitrates[newidx].bitrate);
+		cur, sband->bitrates[cur].bitrate);
 #endif
 }
 


--
Ciao
Stefano

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Larry Finger]

Stefano Brivio wrote:
> Merge rate_control_pid_shift_adjust() to rate_control_pid_adjust_rate()
> in order to make the learning algorithm aware of constraints on rates. Also
> add some comments and rename variables.
> 
> This fixes a bug which prevented 802.11b/g non-AP STAs from working with
> 802.11b only AP STAs.
> 
> Signed-off-by: Stefano Brivio <stefano.brivio@polimi.it>
> ---
> John, this should supersede the previously posted patches 1/2 and 2/2. This
> needs further testing anyway.
> 
> Larry, Lars, please test this. It works for me, both with 802.11b only and
> 802.11b/g settings on my AP.

Now that ieee80211_sta_work() no longer crashes on my machine, I have been able to test this patch. 
So far, it seems to work.

Larry

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Jory A. Pratt]

Larry Finger wrote:
> Stefano Brivio wrote:
>> Merge rate_control_pid_shift_adjust() to rate_control_pid_adjust_rate()
>> in order to make the learning algorithm aware of constraints on 
>> rates. Also
>> add some comments and rename variables.
>>
>> This fixes a bug which prevented 802.11b/g non-AP STAs from working with
>> 802.11b only AP STAs.
>>
>> Signed-off-by: Stefano Brivio <stefano.brivio@polimi.it>
>> ---
>> John, this should supersede the previously posted patches 1/2 and 
>> 2/2. This
>> needs further testing anyway.
>>
>> Larry, Lars, please test this. It works for me, both with 802.11b 
>> only and
>> 802.11b/g settings on my AP.
>
> Now that ieee80211_sta_work() no longer crashes on my machine, I have 
> been able to test this patch. So far, it seems to work.
>
> Larry

Works just fine here as well.

-Jory

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Stefano Brivio]

On Mon, 28 Jan 2008 20:33:33 +0100
"Lars Ericsson" <Lars_Ericsson@telia.com> wrote:

> Hi,
> 
> Sorry, it took me some time to start testing.
> I was using a rt2x00 kernel, which did not compile the patch.
> Am using a RT61 minPCI as the STA.
> 
> Have build a new wireless kernel and made some initial test.
> 
> Findings so far:
> 1) It does not select 11g speeds on 11b AP, fine.
> 2) It does not use 11g speeds on 11g AP, not so good.

What happens if you force an 802.11g rate?


--
Ciao
Stefano

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Larry Finger]

Lars Ericsson wrote:
> Hi,
> 
> Sorry, it took me some time to start testing.
> I was using a rt2x00 kernel, which did not compile the patch.
> Am using a RT61 minPCI as the STA.
> 
> Have build a new wireless kernel and made some initial test.
> 
> Findings so far:
> 1) It does not select 11g speeds on 11b AP, fine.
> 2) It does not use 11g speeds on 11g AP, not so good.
> 3) It takes some time before the speed is adjusted.
>    I think that may be configurable, but have not spent any time on that.

I cannot confirm either 2) or 3). When I connected to a nearby 802.11g AP, it had adjusted the speed 
to 54 Mbs by the time I got the output of an iwconfig.

Larry

RE: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Lars Ericsson]

Hi,

My test system is broken. 

I was using a kernel build a couple of days ago while I was doing the
initial test with the new rate control function.

Since I was getting deviant result, I decided to build a fresh kernel 
before I continue my test. I also had added some debugging to see what 
actually happens.

Unfortunately the rt2x00/rt61pci driver is broken in current git. I'm using
http://www.kernel.org/pub/scm/linux/kernel/git/linville/wireless-2.6.git, 
and the 'everything' branch. 

I got plenty of :
[ 2119.568376] WARNING: at net/mac80211/rx.c:2022 __ieee80211_rx()
[ 2119.574828] Pid: 0, comm: swapper Not tainted 2.6.24-rc8wireless-lae #8
[ 2119.582022]  [<c01030ea>] show_trace_log_lvl+0x1a/0x30
[ 2119.587708]  [<c0103bc2>] show_trace+0x12/0x20
[ 2119.592574]  [<c010434c>] dump_stack+0x6c/0x80
[ 2119.597484]  [<d0860138>] __ieee80211_rx+0x68/0x610 [mac80211]
[ 2119.604037]  [<d0850a0e>] ieee80211_tasklet_handler+0xae/0xe0 [mac80211]
[ 2119.611484]  [<c011bd33>] tasklet_action+0x33/0x70
[ 2119.616773]  [<c011bc64>] __do_softirq+0x54/0xb0
[ 2119.621938]  [<c011bcf5>] do_softirq+0x35/0x40
[ 2119.626822]  [<c011bf53>] irq_exit+0x43/0x50
[ 2119.631516]  [<c0104671>] do_IRQ+0x51/0xa0
[ 2119.636031]  [<c0102c43>] common_interrupt+0x23/0x28
[ 2119.641506]  [<c0100e48>] cpu_idle+0x28/0x80
[ 2119.646219]  [<c02e095c>] rest_init+0x5c/0x60
[ 2119.651010]  [<c0380b45>] start_kernel+0x205/0x290
[ 2119.656312]  [<00000000>] run_init_process+0x3fefff40/0x20


I think it has something to do with the "cfg80211 API for channels/bitrates,

mac80211 and driver conversion" commit.

I will get back as soon as my test system is up and running again.

Regards
Lars

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Stefano Brivio]

On Tue, 29 Jan 2008 21:15:49 +0100
"Lars Ericsson" <Lars_Ericsson@telia.com> wrote:

> Hi,
> 
> My test system is broken. 
> 
> I was using a kernel build a couple of days ago while I was doing the
> initial test with the new rate control function.
> 
> Since I was getting deviant result, I decided to build a fresh kernel 
> before I continue my test. I also had added some debugging to see what 
> actually happens.
> 
> Unfortunately the rt2x00/rt61pci driver is broken in current git. I'm using
> http://www.kernel.org/pub/scm/linux/kernel/git/linville/wireless-2.6.git, 
> and the 'everything' branch. 
> 
> I got plenty of :
> [ 2119.568376] WARNING: at net/mac80211/rx.c:2022 __ieee80211_rx()

Could you check which one is the condition which fails at rx.c:2022, i.e.
by inserting three separate WARN_ON(1) statements?


--
Ciao
Stefano

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Will Dyson]

On Jan 29, 2008 3:37 PM, Stefano Brivio <stefano.brivio@polimi.it> wrote:
> On Tue, 29 Jan 2008 21:15:49 +0100
> "Lars Ericsson" <Lars_Ericsson@telia.com> wrote:

> > Unfortunately the rt2x00/rt61pci driver is broken in current git. I'm using
> > http://www.kernel.org/pub/scm/linux/kernel/git/linville/wireless-2.6.git,
> > and the 'everything' branch.
> >
> > I got plenty of :
> > [ 2119.568376] WARNING: at net/mac80211/rx.c:2022 __ieee80211_rx()
>
> Could you check which one is the condition which fails at rx.c:2022, i.e.
> by inserting three separate WARN_ON(1) statements?

On my system, it is the "status->rate_idx < 0" condition.

In rt2x00lib_rxdone() we set the rate_idx to -1 because we looped
through all the rates without finding a match. This does not happen on
every frame. I am still digging.

-- 
Will Dyson

Re: [RFT] [PATCH] rc80211-pid: fix rate adjusting

[Johannes Berg]

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


> On my system, it is the "status->rate_idx < 0" condition.
> 
> In rt2x00lib_rxdone() we set the rate_idx to -1 because we looped
> through all the rates without finding a match. This does not happen on
> every frame. I am still digging.

We've already identified the problem and Ivo is working on a fix.

johannes

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