[PATCH] mac80211: fix aggregation frame release during timeout

[PATCH] mac80211: fix aggregation frame release during timeout

[Daniel Halperin]

Suppose the aggregation reorder buffer looks like this:

x-T-R1-y-R2,

where x and y are frames that have not been received, T is a received
frame that has timed out, and R1,R2 are received frames that have not
yet timed out. The proper behavior in this scenario is to move the
window past x (skipping it), release T and R1, and leave the window at y
until y is received or R2 times out.

As written, this code will instead leave the window at R1, because it
has not yet timed out. Fix this by exiting the reorder loop only when
the frame that has not timed out AND there are skipped frames earlier in
the current valid window.

Signed-off-by: Daniel Halperin <dhalperi@cs.washington.edu>
---
 net/mac80211/rx.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/net/mac80211/rx.c b/net/mac80211/rx.c
index a6701ed..d466bee 100644
--- a/net/mac80211/rx.c
+++ b/net/mac80211/rx.c
@@ -605,7 +605,7 @@ static void ieee80211_sta_reorder_release(struct ieee80211_hw *hw,
 				continue;
 			}
 			if (!time_after(jiffies, tid_agg_rx->reorder_time[j] +
-					HT_RX_REORDER_BUF_TIMEOUT))
+					HT_RX_REORDER_BUF_TIMEOUT) && skipped)
 				goto set_release_timer;
 
 #ifdef CONFIG_MAC80211_HT_DEBUG
-- 
1.7.0.4

Re: [PATCH] mac80211: fix aggregation frame release during timeout

[Johannes Berg]

On Tue, 2011-03-15 at 16:49 -0700, Daniel Halperin wrote:

> x-T-R1-y-R2,

>  			if (!time_after(jiffies, tid_agg_rx->reorder_time[j] +
> -					HT_RX_REORDER_BUF_TIMEOUT))
> +					HT_RX_REORDER_BUF_TIMEOUT) && skipped)

Wait, your previous example of xT---R worked fine, but if you say x-T-
this patch won't work I think? Basically you're saying if we received
frames 2 and 4 after 3, and 3 times out, we can release 2 through 4. I
agree, but your code won't do that since skipped starts out at 1 due to
the first x. Or am I misreading this?

johannes

Re: [PATCH] mac80211: fix aggregation frame release during timeout

[Daniel Halperin]

On Wed, Mar 16, 2011 at 1:21 AM, Johannes Berg
<johannes@sipsolutions.net> wrote:
> On Tue, 2011-03-15 at 16:49 -0700, Daniel Halperin wrote:
>
>> x-T-R1-y-R2,
>
>>                       if (!time_after(jiffies, tid_agg_rx->reorder_time[j] +
>> -                                     HT_RX_REORDER_BUF_TIMEOUT))
>> +                                     HT_RX_REORDER_BUF_TIMEOUT) && skipped)
>
> Wait, your previous example of xT---R worked fine, but if you say x-T-
> this patch won't work I think? Basically you're saying if we received
> frames 2 and 4 after 3, and 3 times out, we can release 2 through 4. I
> agree, but your code won't do that since skipped starts out at 1 due to
> the first x. Or am I misreading this?
>

The syntax I used in our private mail was confusing and I tried to
simplify. Here, hyphens are just separators between frames (since R1,
R2 have two-letter identifiers). Does that clear it up?

Dan

Re: [PATCH] mac80211: fix aggregation frame release during timeout

[Johannes Berg]

On Wed, 2011-03-16 at 01:44 -0700, Daniel Halperin wrote:
> On Wed, Mar 16, 2011 at 1:21 AM, Johannes Berg
> <johannes@sipsolutions.net> wrote:
> > On Tue, 2011-03-15 at 16:49 -0700, Daniel Halperin wrote:
> >
> >> x-T-R1-y-R2,
> >
> >>                       if (!time_after(jiffies, tid_agg_rx->reorder_time[j] +
> >> -                                     HT_RX_REORDER_BUF_TIMEOUT))
> >> +                                     HT_RX_REORDER_BUF_TIMEOUT) && skipped)
> >
> > Wait, your previous example of xT---R worked fine, but if you say x-T-
> > this patch won't work I think? Basically you're saying if we received
> > frames 2 and 4 after 3, and 3 times out, we can release 2 through 4. I
> > agree, but your code won't do that since skipped starts out at 1 due to
> > the first x. Or am I misreading this?
> >
> 
> The syntax I used in our private mail was confusing and I tried to
> simplify. Here, hyphens are just separators between frames (since R1,
> R2 have two-letter identifiers). Does that clear it up?

Oh. Right. Still though, what if it is x-R1-T-R2-y-...? This fixes
x-T-R1-...-y-..., but shouldn't some release be possible in the other
case as well?

johannes

Re: [PATCH] mac80211: fix aggregation frame release during timeout

[Daniel Halperin]

On Wed, Mar 16, 2011 at 1:49 AM, Johannes Berg
<johannes@sipsolutions.net> wrote:
> On Wed, 2011-03-16 at 01:44 -0700, Daniel Halperin wrote:
>> On Wed, Mar 16, 2011 at 1:21 AM, Johannes Berg
>> <johannes@sipsolutions.net> wrote:
>> > On Tue, 2011-03-15 at 16:49 -0700, Daniel Halperin wrote:
>> >
>> >> x-T-R1-y-R2,
>> >
>> >>                       if (!time_after(jiffies, tid_agg_rx->reorder_time[j] +
>> >> -                                     HT_RX_REORDER_BUF_TIMEOUT))
>> >> +                                     HT_RX_REORDER_BUF_TIMEOUT) && skipped)
>> >
>> > Wait, your previous example of xT---R worked fine, but if you say x-T-
>> > this patch won't work I think? Basically you're saying if we received
>> > frames 2 and 4 after 3, and 3 times out, we can release 2 through 4. I
>> > agree, but your code won't do that since skipped starts out at 1 due to
>> > the first x. Or am I misreading this?
>> >
>>
>> The syntax I used in our private mail was confusing and I tried to
>> simplify. Here, hyphens are just separators between frames (since R1,
>> R2 have two-letter identifiers). Does that clear it up?
>
> Oh. Right. Still though, what if it is x-R1-T-R2-y-...? This fixes
> x-T-R1-...-y-..., but shouldn't some release be possible in the other
> case as well?
>

Hmm -- you've got a point. That case wasn't handled by the original
code and my change only picks up my example but not yours.

One fix maybe is to also store the sequence of the frame that set the
timer when the buffer fires, and make sure to release up to that seq?
Or maybe the reception of an earlier frame SHOULD override the the
later frame's timeout, because it says the early part of the window is
"still alive".

I just don't see a good way to handle all cases (e.g.,
x-R3-R1-y-T-z-R2-w-T) without looping over the whole buffer.  (Here,
xyzw are skipped frames and R3 was received last.)  Again, long MAC
delays like BT could make this false, but I have to expect in most
cases R1/2/3 will be received pretty close to when T is.

Dan

Re: [PATCH] mac80211: fix aggregation frame release during timeout

[Johannes Berg]

On Wed, 2011-03-16 at 02:00 -0700, Daniel Halperin wrote:

> >> The syntax I used in our private mail was confusing and I tried to
> >> simplify. Here, hyphens are just separators between frames (since R1,
> >> R2 have two-letter identifiers). Does that clear it up?
> >
> > Oh. Right. Still though, what if it is x-R1-T-R2-y-...? This fixes
> > x-T-R1-...-y-..., but shouldn't some release be possible in the other
> > case as well?
> >
> 
> Hmm -- you've got a point. That case wasn't handled by the original
> code and my change only picks up my example but not yours.

Right. I'm happy with your change anyhow, but I think I'd prefer if you
moved the skipped test to the front (i.e. skipped && time...) since it's
much cheaper. Then again I guess it doesn't really matter here...

> One fix maybe is to also store the sequence of the frame that set the
> timer when the buffer fires, and make sure to release up to that seq?
> Or maybe the reception of an earlier frame SHOULD override the the
> later frame's timeout, because it says the early part of the window is
> "still alive".

Yeah I was thinking the same a minute ago, if we get an earlier frame
then the sender is definitely still aware that we're missing something
there, so the timeout probably shouldn't hit.

> I just don't see a good way to handle all cases (e.g.,
> x-R3-R1-y-T-z-R2-w-T) without looping over the whole buffer.  (Here,
> xyzw are skipped frames and R3 was received last.)  Again, long MAC
> delays like BT could make this false, but I have to expect in most
> cases R1/2/3 will be received pretty close to when T is.

Right. Let's just leave it as is (plus your patch that we're
discussing). It's a corner case anyway, and no good throughput can be
expected from it.

Did you ever get data on the window moving thing? Like maybe in your
earlier message where you had

> enqueued frame 31
> <got compressed block-ack only missing frame 2>

I'll go to your other email now.

johannes

Re: [PATCH] mac80211: fix aggregation frame release during timeout

[Daniel Halperin]

On Wed, Mar 16, 2011 at 2:08 AM, Johannes Berg
<johannes@sipsolutions.net> wrote:
> Right. I'm happy with your change anyhow, but I think I'd prefer if you
> moved the skipped test to the front (i.e. skipped && time...) since it's
> much cheaper. Then again I guess it doesn't really matter here...

I think this wasn't picked up by John.  I'm about to re-send with the
skipped test moved.

Dan