[PATCH] cfg80211: merge in beacon ies of hidden bss.

[PATCH] cfg80211: merge in beacon ies of hidden bss.

[Dmitry Tarnyagin]

The problem with PSM when a hidden SSID was used was originally
reported by Juuso Oikarinen.

 - When generally scanning, the AP is getting a bss entry with
   a zero SSID.
 - When associationg, a probe-req is sent to the AP with the SSID,
   and as a result a probe-responseis received with the hidden
   SSID in place. As a consequence, a second bss entry is created
   for the AP, now with the real SSID.
 - After association, mac80211 executes ieee80211_recalc_ps(),
   but does not switch to powersave becuse the beacon-ies are missing.

As result, the STA does not ever enter PSM.

The patch merges in beacon ies of hidden bss from beacon to the probe
response, creating a consistant set of ies in place.

Signed-off-by: Dmitry Tarnyagin <dmitry.tarnyagin@stericsson.com>
---
 net/wireless/scan.c |   97 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 94 insertions(+), 3 deletions(-)

diff --git a/net/wireless/scan.c b/net/wireless/scan.c
index dd0d4c5..237e9ed 100644
--- a/net/wireless/scan.c
+++ b/net/wireless/scan.c
@@ -325,8 +325,8 @@ static bool is_mesh(struct cfg80211_bss *a,
 	    sizeof(struct ieee80211_meshconf_ie) - 2) == 0;
 }

-static int cmp_bss(struct cfg80211_bss *a,
-		   struct cfg80211_bss *b)
+static int cmp_bss_core(struct cfg80211_bss *a,
+			struct cfg80211_bss *b)
 {
 	int r;

@@ -348,7 +348,15 @@ static int cmp_bss(struct cfg80211_bss *a,
 			       b->len_information_elements);
 	}

-	r = memcmp(a->bssid, b->bssid, ETH_ALEN);
+	return memcmp(a->bssid, b->bssid, ETH_ALEN);
+}
+
+static int cmp_bss(struct cfg80211_bss *a,
+		   struct cfg80211_bss *b)
+{
+	int r;
+
+	r = cmp_bss_core(a, b);
 	if (r)
 		return r;

@@ -359,6 +367,38 @@ static int cmp_bss(struct cfg80211_bss *a,
 		       b->len_information_elements);
 }

+static int cmp_hidden_bss(struct cfg80211_bss *a,
+		   struct cfg80211_bss *b)
+{
+	const u8 *ie1;
+	const u8 *ie2;
+	size_t ielen;
+	int i;
+	int r;
+
+	r = cmp_bss_core(a, b);
+	if (r)
+		return r;
+
+	ie1 = cfg80211_find_ie(WLAN_EID_SSID,
+			a->information_elements,
+			a->len_information_elements);
+	ie2 = cfg80211_find_ie(WLAN_EID_SSID,
+			b->information_elements,
+			b->len_information_elements);
+	if (!ie1 && !ie2)
+		return 0;
+	if (!ie1 || !ie2)
+		return -1;
+
+	ielen = min(ie1[1], ie2[1]);
+	for (i = 0; i < ielen; ++i)
+		if (ie2[i + 2])
+			return -1;
+
+	return ie2[1] - ie1[1];
+}
+
 struct cfg80211_bss *cfg80211_get_bss(struct wiphy *wiphy,
 				      struct ieee80211_channel *channel,
 				      const u8 *bssid,
@@ -475,6 +515,50 @@ rb_find_bss(struct cfg80211_registered_device *dev,
 }

 static struct cfg80211_internal_bss *
+rb_find_hidden_bss(struct cfg80211_registered_device *dev,
+	    struct cfg80211_internal_bss *res)
+{
+	struct rb_node *n = dev->bss_tree.rb_node;
+	struct cfg80211_internal_bss *bss;
+	int r;
+
+	while (n) {
+		bss = rb_entry(n, struct cfg80211_internal_bss, rbn);
+		r = cmp_hidden_bss(&res->pub, &bss->pub);
+
+		if (r == 0)
+			return bss;
+		else if (r < 0)
+			n = n->rb_left;
+		else
+			n = n->rb_right;
+	}
+
+	return NULL;
+}
+
+static int
+merge_hidden_ies(struct cfg80211_internal_bss *res,
+		 struct cfg80211_internal_bss *hidden)
+{
+	if (unlikely(res->pub.beacon_ies))
+		return -EALREADY;
+	if (WARN_ON(!hidden->pub.beacon_ies))
+		return -EINVAL;
+
+	res->pub.beacon_ies = kmalloc(hidden->pub.len_beacon_ies, GFP_ATOMIC);
+	if (unlikely(!res->pub.beacon_ies))
+		return -ENOMEM;
+
+	res->beacon_ies_allocated = true;
+	res->pub.len_beacon_ies = hidden->pub.len_beacon_ies;
+	memcpy(res->pub.beacon_ies, hidden->pub.beacon_ies,
+			res->pub.len_beacon_ies);
+
+	return 0;
+}
+
+static struct cfg80211_internal_bss *
 cfg80211_bss_update(struct cfg80211_registered_device *dev,
 		    struct cfg80211_internal_bss *res)
 {
@@ -494,6 +578,13 @@ cfg80211_bss_update(struct cfg80211_registered_device *dev,
 	spin_lock_bh(&dev->bss_lock);

 	found = rb_find_bss(dev, res);
+	if (!found) {
+		struct cfg80211_internal_bss *hidden;
+
+		hidden = rb_find_hidden_bss(dev, res);
+		if (hidden)
+			merge_hidden_ies(res, hidden);
+	}

 	if (found) {
 		found->pub.beacon_interval = res->pub.beacon_interval;
-- 
With best regards,
Dmitry Tarnyagin

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Johannes Berg]

On Wed, 2011-11-02 at 19:19 +0100, Dmitry Tarnyagin wrote:

> +static int cmp_hidden_bss(struct cfg80211_bss *a,
> +		   struct cfg80211_bss *b)
> +{
> +	const u8 *ie1;
> +	const u8 *ie2;
> +	size_t ielen;
> +	int i;
> +	int r;
> +
> +	r = cmp_bss_core(a, b);
> +	if (r)
> +		return r;
> +
> +	ie1 = cfg80211_find_ie(WLAN_EID_SSID,
> +			a->information_elements,
> +			a->len_information_elements);
> +	ie2 = cfg80211_find_ie(WLAN_EID_SSID,
> +			b->information_elements,
> +			b->len_information_elements);
> +	if (!ie1 && !ie2)
> +		return 0;

I don't think it's valid to leave out the SSID IE, so I'd rather not
have that test here. It might interact badly with other uses (mesh?)

> +	if (!ie1 || !ie2)
> +		return -1;
> +
> +	ielen = min(ie1[1], ie2[1]);
> +	for (i = 0; i < ielen; ++i)

++i here is a bit atypical code style.

> +		if (ie2[i + 2])
> +			return -1;

I don't understand this loop. Why check that ie2 is zeroed, but check
only to the minlen of ie1, ie2?

> +	return ie2[1] - ie1[1];

I'd error out much earlier if the length is different instead of
comparing to the minlen first.

> +static int
> +merge_hidden_ies(struct cfg80211_internal_bss *res,
> +		 struct cfg80211_internal_bss *hidden)

There seems little use for the return value.

> +{
> +	if (unlikely(res->pub.beacon_ies))
> +		return -EALREADY;
> +	if (WARN_ON(!hidden->pub.beacon_ies))
> +		return -EINVAL;
> +
> +	res->pub.beacon_ies = kmalloc(hidden->pub.len_beacon_ies, GFP_ATOMIC);
> +	if (unlikely(!res->pub.beacon_ies))
> +		return -ENOMEM;
> +
> +	res->beacon_ies_allocated = true;
> +	res->pub.len_beacon_ies = hidden->pub.len_beacon_ies;
> +	memcpy(res->pub.beacon_ies, hidden->pub.beacon_ies,
> +			res->pub.len_beacon_ies);
> +
> +	return 0;
> +}
> +
> +static struct cfg80211_internal_bss *
>  cfg80211_bss_update(struct cfg80211_registered_device *dev,
>  		    struct cfg80211_internal_bss *res)
>  {
> @@ -494,6 +578,13 @@ cfg80211_bss_update(struct cfg80211_registered_device *dev,
>  	spin_lock_bh(&dev->bss_lock);
> 
>  	found = rb_find_bss(dev, res);
> +	if (!found) {
> +		struct cfg80211_internal_bss *hidden;
> +
> +		hidden = rb_find_hidden_bss(dev, res);
> +		if (hidden)
> +			merge_hidden_ies(res, hidden);
> +	}

I was going to complain that I don't understand why this works -- but
then I think now I do. If you move the code down into the else branch
it'll be much easier to follow.

johannes

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Dmitry Tarnyagin]

Hi Johannes,

On Thu, Nov 3, 2011 at 9:55 AM, Johannes Berg <johannes@sipsolutions.net> wrote:

>> +     if (!ie1 && !ie2)
>> +             return 0;
> I don't think it's valid to leave out the SSID IE, so I'd rather not
> have that test here. It might interact badly with other uses (mesh?)
>
ie1 and ie2 could not NULL at the same time, otherwise the bss
would be found in the first search attempt. However, I would prefer
to have some water-proof check here. WARN_ON? BUG_ON?

>> +     for (i = 0; i < ielen; ++i)
> ++i here is a bit atypical code style.
>
Ok.

>> +             if (ie2[i + 2])
>> +                     return -1;
> I don't understand this loop. Why check that ie2 is zeroed, but check
> only to the minlen of ie1, ie2?
>
Check that ie2 is zeroed is a check for hidden SSID.
Check only to minlent to be in-line with cmp_ies().

>> +     return ie2[1] - ie1[1];
> I'd error out much earlier if the length is different instead of
> comparing to the minlen first.
>
Key comparator must use same algorithm in any rb-tree search function
(order is important), otherwise ordering of items in the tree is broken
and search gives incorrect results.
This code uses same order as cmp_ies() does.

>
>> +static int
>> +merge_hidden_ies(struct cfg80211_internal_bss *res,
>> +              struct cfg80211_internal_bss *hidden)
> There seems little use for the return value.
>
Agree. int -> void

>> @@ -494,6 +578,13 @@ cfg80211_bss_update(struct cfg80211_registered_device *dev,
>>       spin_lock_bh(&dev->bss_lock);
>>
>>       found = rb_find_bss(dev, res);
>> +     if (!found) {
>> +             struct cfg80211_internal_bss *hidden;
>> +
>> +             hidden = rb_find_hidden_bss(dev, res);
>> +             if (hidden)
>> +                     merge_hidden_ies(res, hidden);
>> +     }
> I was going to complain that I don't understand why this works -- but
> then I think now I do. If you move the code down into the else branch
> it'll be much easier to follow.
>
Ok.

Thank you for review!

With best regards,
Dmitry

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Johannes Berg]

Hi Dmitry,

> >> +     if (!ie1 && !ie2)
> >> +             return 0;
> > I don't think it's valid to leave out the SSID IE, so I'd rather not
> > have that test here. It might interact badly with other uses (mesh?)
> >
> ie1 and ie2 could not NULL at the same time, otherwise the bss
> would be found in the first search attempt. However, I would prefer
> to have some water-proof check here. WARN_ON? BUG_ON?

Maybe a warning? But I don't see why it'll just fall through to the next
line and return -1 if one of them is missing.

> >> +             if (ie2[i + 2])
> >> +                     return -1;
> > I don't understand this loop. Why check that ie2 is zeroed, but check
> > only to the minlen of ie1, ie2?
> >
> Check that ie2 is zeroed is a check for hidden SSID.
> Check only to minlent to be in-line with cmp_ies().
> 
> >> +     return ie2[1] - ie1[1];
> > I'd error out much earlier if the length is different instead of
> > comparing to the minlen first.
> >
> Key comparator must use same algorithm in any rb-tree search function
> (order is important), otherwise ordering of items in the tree is broken
> and search gives incorrect results.
> This code uses same order as cmp_ies() does.

Oh. Good point. Add a comment?

> >> @@ -494,6 +578,13 @@ cfg80211_bss_update(struct cfg80211_registered_device *dev,
> >>       spin_lock_bh(&dev->bss_lock);
> >>
> >>       found = rb_find_bss(dev, res);
> >> +     if (!found) {
> >> +             struct cfg80211_internal_bss *hidden;
> >> +
> >> +             hidden = rb_find_hidden_bss(dev, res);
> >> +             if (hidden)
> >> +                     merge_hidden_ies(res, hidden);
> >> +     }
> > I was going to complain that I don't understand why this works -- but
> > then I think now I do. If you move the code down into the else branch
> > it'll be much easier to follow.
> >
> Ok.
> 
> Thank you for review!

Eliad pointed out another thing: It is possible to have multiple SSIDs
hidden behind a single hidden SSID. Therefore, this should update all of
those BSS structs. Also, I'm a tad confused about the matching code
here, this code path executes for both received beacons and probe
responses, but probe responses would typically have found the BSS
already? But what if we only have a beacon and then receive a probe
response? Or vice versa? Some comments would be good outlining how that
works.

johannes

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Dmitry Tarnyagin]

Hi Johannes,

On Thu, Nov 3, 2011 at 10:39 AM, Johannes Berg
<johannes@sipsolutions.net> wrote:
> Hi Dmitry,
>
>> >> +     if (!ie1 && !ie2)
>> >> +             return 0;
>> > I don't think it's valid to leave out the SSID IE, so I'd rather not
>> > have that test here. It might interact badly with other uses (mesh?)
>> ie1 and ie2 could not NULL at the same time, otherwise the bss
>> would be found in the first search attempt. However, I would prefer
>> to have some water-proof check here. WARN_ON? BUG_ON?
> Maybe a warning? But I don't see why it'll just fall through to the next
> line and return -1 if one of them is missing.
>
-1 means "lesser", which is not true if both of ies are absent.
0 means "equal", which is correct (but logically impossible with the
current usage of the comparator). Now I think even WARN_ON is a bad
idea, the comparator can be reused for other purposes when both
SSID ies are missing.

>> Key comparator must use same algorithm in any rb-tree search function
>> (order is important), otherwise ordering of items in the tree is broken
>> and search gives incorrect results.
>> This code uses same order as cmp_ies() does.
> Oh. Good point. Add a comment?
>
Yes, I will.

> Eliad pointed out another thing: It is possible to have multiple SSIDs
> hidden behind a single hidden SSID. Therefore, this should update all of
> those BSS structs. Also, I'm a tad confused about the matching code
> here, this code path executes for both received beacons and probe
> responses, but probe responses would typically have found the BSS
> already? But what if we only have a beacon and then receive a probe
> response? Or vice versa? Some comments would be good outlining how that
> works.
>
I will add some comments in the code. Is a word, the code searches for a beacon
of the hidden BSS and copies beacon IEs (with nullified SSID) into the probe
response bss entry (with real SSID). It works fine in case of multi-SSID hidden
BSS too.

> what if we only have a beacon and then receive a probe response?
It's the typical usecase for association with hidden BSS.  The probe
response will
be updated with beacon IEs.

> Or vice versa?
It will not work. Update of beacon IEs of probe response is not implemented.
The code is not trying to update existing probe response bss entries when beacon
IEs are getting changed. Technically it's possible to update them, but
I think it's a bit
overkill, I'm addressing only PSM in this commit.

Thank you and with best regards,
Dmitry

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Johannes Berg]

Hi,

> -1 means "lesser", which is not true if both of ies are absent.
> 0 means "equal", which is correct (but logically impossible with the
> current usage of the comparator). Now I think even WARN_ON is a bad
> idea, the comparator can be reused for other purposes when both
> SSID ies are missing.

Fair enough. Maybe a comment along the lines of
/* can't really happen, but they're the same then */

would be useful.

> > Eliad pointed out another thing: It is possible to have multiple SSIDs
> > hidden behind a single hidden SSID. Therefore, this should update all of
> > those BSS structs. Also, I'm a tad confused about the matching code
> > here, this code path executes for both received beacons and probe
> > responses, but probe responses would typically have found the BSS
> > already? But what if we only have a beacon and then receive a probe
> > response? Or vice versa? Some comments would be good outlining how that
> > works.
> >
> I will add some comments in the code. Is a word, the code searches for a beacon
> of the hidden BSS and copies beacon IEs (with nullified SSID) into the probe
> response bss entry (with real SSID). It works fine in case of multi-SSID hidden
> BSS too.

Right, that should work.

> > Or vice versa?
> It will not work. Update of beacon IEs of probe response is not implemented.
> The code is not trying to update existing probe response bss entries when beacon
> IEs are getting changed. Technically it's possible to update them, but
> I think it's a bit
> overkill, I'm addressing only PSM in this commit.

I think that would actually be useful too since userspace may obtain
this data from scan results at any point in time, and might expect
up-to-date information? Could be a separate patch though.

Anyway, comments indicating what happens and which case this handles
would be great.

Thanks!

johannes

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Eliad Peller]

hi Dmitry,

On Wed, Nov 2, 2011 at 8:19 PM, Dmitry Tarnyagin <abi.dmitryt@gmail.com> wrote:
> The problem with PSM when a hidden SSID was used was originally
> reported by Juuso Oikarinen.
>
>  - When generally scanning, the AP is getting a bss entry with
>   a zero SSID.
>  - When associationg, a probe-req is sent to the AP with the SSID,
>   and as a result a probe-responseis received with the hidden
>   SSID in place. As a consequence, a second bss entry is created
>   for the AP, now with the real SSID.
>  - After association, mac80211 executes ieee80211_recalc_ps(),
>   but does not switch to powersave becuse the beacon-ies are missing.
>
> As result, the STA does not ever enter PSM.
>
> The patch merges in beacon ies of hidden bss from beacon to the probe
> response, creating a consistant set of ies in place.
>
> Signed-off-by: Dmitry Tarnyagin <dmitry.tarnyagin@stericsson.com>
> ---
[...]
> +static int cmp_hidden_bss(struct cfg80211_bss *a,
> +                  struct cfg80211_bss *b)
> +{
> +       const u8 *ie1;
> +       const u8 *ie2;
> +       size_t ielen;
> +       int i;
> +       int r;
> +
> +       r = cmp_bss_core(a, b);
> +       if (r)
> +               return r;
> +
> +       ie1 = cfg80211_find_ie(WLAN_EID_SSID,
> +                       a->information_elements,
> +                       a->len_information_elements);
> +       ie2 = cfg80211_find_ie(WLAN_EID_SSID,
> +                       b->information_elements,
> +                       b->len_information_elements);
> +       if (!ie1 && !ie2)
> +               return 0;
> +       if (!ie1 || !ie2)
> +               return -1;
> +
> +       ielen = min(ie1[1], ie2[1]);
> +       for (i = 0; i < ielen; ++i)
> +               if (ie2[i + 2])
> +                       return -1;
> +
> +       return ie2[1] - ie1[1];

you don't account for the ssid = "" case.


> +static int
> +merge_hidden_ies(struct cfg80211_internal_bss *res,
> +                struct cfg80211_internal_bss *hidden)
> +{
> +       if (unlikely(res->pub.beacon_ies))
> +               return -EALREADY;
> +       if (WARN_ON(!hidden->pub.beacon_ies))
> +               return -EINVAL;
> +
> +       res->pub.beacon_ies = kmalloc(hidden->pub.len_beacon_ies, GFP_ATOMIC);
> +       if (unlikely(!res->pub.beacon_ies))
> +               return -ENOMEM;
> +
> +       res->beacon_ies_allocated = true;
> +       res->pub.len_beacon_ies = hidden->pub.len_beacon_ies;
> +       memcpy(res->pub.beacon_ies, hidden->pub.beacon_ies,
> +                       res->pub.len_beacon_ies);
> +
> +       return 0;
> +}
> +
i think the "merge" here is a bit misleading - there is no actual merge.
you copy the beacon_ies from the beacon, but we still end up with 2 bss nodes.
your solution does workaround the specific psm problem, but we still
end up with a duplicate bss conf node that will never get updated
(because the beacons will update the "original" bss node).

i guess this problem already exists with the current code.
not sure what is the correct way solve it, though.
maybe check for both the hidden name and the actual name?

Eliad.

Re: [PATCH] cfg80211: merge in beacon ies of hidden bss.

[Dmitry Tarnyagin]

Hi Eliad,

>> +       if (!ie1 && !ie2)
>> +               return 0;
>> +       if (!ie1 || !ie2)
>> +               return -1;
>> +       ielen = min(ie1[1], ie2[1]);
>> +       for (i = 0; i < ielen; ++i)
>> +               if (ie2[i + 2])
>> +                       return -1;
>> +       return ie2[1] - ie1[1];
>
> you don't account for the ssid = "" case.
>
Yes, true. And also incorrectly handle !ie2 case. I'll fix it.

>> +static int
>> +merge_hidden_ies(struct cfg80211_internal_bss *res,
[...]
>
> i think the "merge" here is a bit misleading - there is no actual merge.
> you copy the beacon_ies from the beacon, but we still end up with 2 bss nodes.
> your solution does workaround the specific psm problem, but we still
> end up with a duplicate bss conf node that will never get updated
> (because the beacons will update the "original" bss node).
>
Yes, correct. I'm addressing only the obvious PSM problem now.
Further implementation is a subject of a discussion.

> i guess this problem already exists with the current code.
> not sure what is the correct way solve it, though.
> maybe check for both the hidden name and the actual name?
>
The whole idea of multi-ssid list of bss'es is a bit unclear for me.
That is the benefit of having ssid ie as a part of the key in the tree?
Are there multi-ssid APs which broadcasts different ies (apart form ssid)
on the same bssid in real live?
If not, I'm thinking about a separate refcounted list of bss ies keeping
all bss information except ssid. But it is a quite big change, definitely
not for this commit.

Thank you and with best regards,
Dmitry