[PATCH v4] mac80211: Optimize sta lookup for many VIFs

[PATCH v4] mac80211: Optimize sta lookup for many VIFs

[greearb]

From: Ben Greear <greearb@candelatech.com>

The sta_info hash is designed to deal with an AP
with lots of stations associated, or a station interface
connected to a single AP.

However, when you have lots of station VIFs connected
to the same AP, the sta_info hash becomes worthless
as there is a single hash bucket that contains all the
entries in a linked list.

So, have the sdata object cache one of its station
interfaces.  If we are a station VIF with a single
sta_info, then this means we can ignore the sta_info
hash entirely.

On a test case with 128 stations and 50 TCP streams,
tx performance went from around 80Mbps to 124Mbps.

Signed-off-by: Ben Greear <greearb@candelatech.com>
---

v4:  Use rcu_dereference_protected as designed, passing a mutex
     as the second argument instead of hard-coding it to 1.

:100644 100644 a618bda... a7e7f5d... M	net/mac80211/cfg.c
:100644 100644 493e2e8... c6386c7... M	net/mac80211/ieee80211_i.h
:100644 100644 415f9c6... d87a76d... M	net/mac80211/sta_info.c
 net/mac80211/cfg.c         |    6 ++++++
 net/mac80211/ieee80211_i.h |    6 ++++++
 net/mac80211/sta_info.c    |   23 ++++++++++++++++++++++-
 3 files changed, 34 insertions(+), 1 deletions(-)

diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c
index a618bda..a7e7f5d 100644
--- a/net/mac80211/cfg.c
+++ b/net/mac80211/cfg.c
@@ -1287,6 +1287,7 @@ static int ieee80211_change_station(struct wiphy *wiphy,
 	if (params->vlan && params->vlan != sta->sdata->dev) {
 		bool prev_4addr = false;
 		bool new_4addr = false;
+		struct sta_info *some_sta;
 
 		vlansdata = IEEE80211_DEV_TO_SUB_IF(params->vlan);
 
@@ -1312,7 +1313,12 @@ static int ieee80211_change_station(struct wiphy *wiphy,
 			prev_4addr = true;
 		}
 
+		some_sta = rcu_dereference_protected(sta->sdata->some_sta,
+					lockdep_is_held(&local->sta_mtx));
+		if (some_sta == sta)
+			rcu_assign_pointer(sta->sdata->some_sta, NULL);
 		sta->sdata = vlansdata;
+		rcu_assign_pointer(sta->sdata->some_sta, sta);
 
 		if (sta->sta_state == IEEE80211_STA_AUTHORIZED &&
 		    prev_4addr != new_4addr) {
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index 493e2e8..c6386c7 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -669,6 +669,12 @@ struct ieee80211_sub_if_data {
 	/* count for keys needing tailroom space allocation */
 	int crypto_tx_tailroom_needed_cnt;
 
+	/* A pointer to some station associated with this interface, or
+	 * NULL.  This allows opportunistic lookup for sta_info objects when
+	 * sdata is a station with a single sta_info.
+	 */
+	struct sta_info __rcu *some_sta;
+
 	struct net_device *dev;
 	struct ieee80211_local *local;
 
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index 415f9c6..d87a76d 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -67,7 +67,12 @@
 static int sta_info_hash_del(struct ieee80211_local *local,
 			     struct sta_info *sta)
 {
-	struct sta_info *s;
+	struct sta_info *s, *some_sta;
+
+	some_sta = rcu_dereference_protected(sta->sdata->some_sta,
+					     lockdep_is_held(&local->sta_mtx));
+	if (some_sta == sta)
+		rcu_assign_pointer(sta->sdata->some_sta, NULL);
 
 	s = rcu_dereference_protected(local->sta_hash[STA_HASH(sta->sta.addr)],
 				      lockdep_is_held(&local->sta_mtx));
@@ -195,6 +200,20 @@ struct sta_info *sta_info_get(struct ieee80211_sub_if_data *sdata,
 	struct ieee80211_local *local = sdata->local;
 	struct sta_info *sta;
 
+	if (sdata->vif.type == NL80211_IFTYPE_STATION) {
+		struct sta_info *some_sta;
+
+		/* Shortcut for finding station entries for STATION VIFs */
+		some_sta = rcu_dereference(sdata->some_sta);
+		if (some_sta) {
+			if (WARN_ON(some_sta->sdata != sdata))
+				rcu_assign_pointer(sdata->some_sta, NULL);
+			else
+				if (ether_addr_equal(some_sta->sta.addr, addr))
+					return some_sta;
+		}
+	}
+
 	sta = rcu_dereference_check(local->sta_hash[STA_HASH(addr)],
 				    lockdep_is_held(&local->sta_mtx));
 	while (sta) {
@@ -278,6 +297,8 @@ static void sta_info_hash_add(struct ieee80211_local *local,
 	lockdep_assert_held(&local->sta_mtx);
 	sta->hnext = local->sta_hash[STA_HASH(sta->sta.addr)];
 	rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)], sta);
+
+	rcu_assign_pointer(sta->sdata->some_sta, sta);
 }
 
 static void sta_unblock(struct work_struct *wk)
-- 
1.7.3.4

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Johannes Berg]

On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:

> --- a/net/mac80211/cfg.c
> +++ b/net/mac80211/cfg.c
> @@ -1287,6 +1287,7 @@ static int ieee80211_change_station(struct wiphy *wiphy,
>  	if (params->vlan && params->vlan != sta->sdata->dev) {
>  		bool prev_4addr = false;
>  		bool new_4addr = false;
> +		struct sta_info *some_sta;
>  
>  		vlansdata = IEEE80211_DEV_TO_SUB_IF(params->vlan);
>  
> @@ -1312,7 +1313,12 @@ static int ieee80211_change_station(struct wiphy *wiphy,
>  			prev_4addr = true;
>  		}
>  
> +		some_sta = rcu_dereference_protected(sta->sdata->some_sta,
> +					lockdep_is_held(&local->sta_mtx));
> +		if (some_sta == sta)
> +			rcu_assign_pointer(sta->sdata->some_sta, NULL);
>  		sta->sdata = vlansdata;
> +		rcu_assign_pointer(sta->sdata->some_sta, sta);
>  
>  		if (sta->sta_state == IEEE80211_STA_AUTHORIZED &&
>  		    prev_4addr != new_4addr) {

I think you can drop all this code since you don't allow this for
non-station interfaces, and stations here can only be reassigned between
AP/AP_VLAN, no?


> @@ -278,6 +297,8 @@ static void sta_info_hash_add(struct ieee80211_local *local,
>  	lockdep_assert_held(&local->sta_mtx);
>  	sta->hnext = local->sta_hash[STA_HASH(sta->sta.addr)];
>  	rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)], sta);
> +
> +	rcu_assign_pointer(sta->sdata->some_sta, sta);

Maybe also assign it only for station to start with?

johannes

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Ben Greear]

On 04/03/2013 05:58 AM, Johannes Berg wrote:
> On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:
>
>> --- a/net/mac80211/cfg.c
>> +++ b/net/mac80211/cfg.c
>> @@ -1287,6 +1287,7 @@ static int ieee80211_change_station(struct wiphy *wiphy,
>>   	if (params->vlan && params->vlan != sta->sdata->dev) {
>>   		bool prev_4addr = false;
>>   		bool new_4addr = false;
>> +		struct sta_info *some_sta;
>>
>>   		vlansdata = IEEE80211_DEV_TO_SUB_IF(params->vlan);
>>
>> @@ -1312,7 +1313,12 @@ static int ieee80211_change_station(struct wiphy *wiphy,
>>   			prev_4addr = true;
>>   		}
>>
>> +		some_sta = rcu_dereference_protected(sta->sdata->some_sta,
>> +					lockdep_is_held(&local->sta_mtx));
>> +		if (some_sta == sta)
>> +			rcu_assign_pointer(sta->sdata->some_sta, NULL);
>>   		sta->sdata = vlansdata;
>> +		rcu_assign_pointer(sta->sdata->some_sta, sta);
>>
>>   		if (sta->sta_state == IEEE80211_STA_AUTHORIZED &&
>>   		    prev_4addr != new_4addr) {
>
> I think you can drop all this code since you don't allow this for
> non-station interfaces, and stations here can only be reassigned between
> AP/AP_VLAN, no?

Well, it seems more fragile to skip this code.  If someone ever changes
how reassignment can happen it may be a while before anyone notices
the bug.  This code is not in any sort of hot path, so there isn't much
overhead...

But, if you still prefer this code removed then I'll make the change.

>> @@ -278,6 +297,8 @@ static void sta_info_hash_add(struct ieee80211_local *local,
>>   	lockdep_assert_held(&local->sta_mtx);
>>   	sta->hnext = local->sta_hash[STA_HASH(sta->sta.addr)];
>>   	rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)], sta);
>> +
>> +	rcu_assign_pointer(sta->sdata->some_sta, sta);
>
> Maybe also assign it only for station to start with?

That sounds fine, though I doubt it matters any performance wise.

Let me know on the point above and I'll re-spin the patch.

Thanks,
Ben

>
> johannes
>


-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Johannes Berg]

On Wed, 2013-04-03 at 06:18 -0700, Ben Greear wrote:
> On 04/03/2013 05:58 AM, Johannes Berg wrote:
> > On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:
> >
> >> --- a/net/mac80211/cfg.c
> >> +++ b/net/mac80211/cfg.c
> >> @@ -1287,6 +1287,7 @@ static int ieee80211_change_station(struct wiphy *wiphy,
> >>   	if (params->vlan && params->vlan != sta->sdata->dev) {
> >>   		bool prev_4addr = false;
> >>   		bool new_4addr = false;
> >> +		struct sta_info *some_sta;
> >>
> >>   		vlansdata = IEEE80211_DEV_TO_SUB_IF(params->vlan);
> >>
> >> @@ -1312,7 +1313,12 @@ static int ieee80211_change_station(struct wiphy *wiphy,
> >>   			prev_4addr = true;
> >>   		}
> >>
> >> +		some_sta = rcu_dereference_protected(sta->sdata->some_sta,
> >> +					lockdep_is_held(&local->sta_mtx));
> >> +		if (some_sta == sta)
> >> +			rcu_assign_pointer(sta->sdata->some_sta, NULL);
> >>   		sta->sdata = vlansdata;
> >> +		rcu_assign_pointer(sta->sdata->some_sta, sta);
> >>
> >>   		if (sta->sta_state == IEEE80211_STA_AUTHORIZED &&
> >>   		    prev_4addr != new_4addr) {
> >
> > I think you can drop all this code since you don't allow this for
> > non-station interfaces, and stations here can only be reassigned between
> > AP/AP_VLAN, no?
> 
> Well, it seems more fragile to skip this code.  If someone ever changes
> how reassignment can happen it may be a while before anyone notices
> the bug.  This code is not in any sort of hot path, so there isn't much
> overhead...

True.

> But, if you still prefer this code removed then I'll make the change.

No, mostly just wondering.

> >> @@ -278,6 +297,8 @@ static void sta_info_hash_add(struct ieee80211_local *local,
> >>   	lockdep_assert_held(&local->sta_mtx);
> >>   	sta->hnext = local->sta_hash[STA_HASH(sta->sta.addr)];
> >>   	rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)], sta);
> >> +
> >> +	rcu_assign_pointer(sta->sdata->some_sta, sta);
> >
> > Maybe also assign it only for station to start with?
> 
> That sounds fine, though I doubt it matters any performance wise.

It won't, it's really not used for lookup anyway.

I'll just apply it as is.

johannes

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Johannes Berg]

On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:
> From: Ben Greear <greearb@candelatech.com>
> 
> The sta_info hash is designed to deal with an AP
> with lots of stations associated, or a station interface
> connected to a single AP.

Given your other hash patches, does this even make sense still?

johannes

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Ben Greear]

On 04/09/2013 02:50 AM, Johannes Berg wrote:
> On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:
>> From: Ben Greear <greearb@candelatech.com>
>>
>> The sta_info hash is designed to deal with an AP
>> with lots of stations associated, or a station interface
>> connected to a single AP.
>
> Given your other hash patches, does this even make sense still?

This handles the TX side for station VIFs.  The more complicated
hashing handles the rx logic.  I could use the hash
for the tx side, though performance is likely a small bit
worse since you have to deal with the hash logic.

And, if the more complicated RFC hashing patch has no upstream
chance anyway, then if the 'some-sta' patch is acceptable,
I'd still be interested in seeing it upstream.

Thanks,
Ben

-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Johannes Berg]

On Tue, 2013-04-09 at 10:35 -0700, Ben Greear wrote:
> On 04/09/2013 02:50 AM, Johannes Berg wrote:
> > On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:
> >> From: Ben Greear <greearb@candelatech.com>
> >>
> >> The sta_info hash is designed to deal with an AP
> >> with lots of stations associated, or a station interface
> >> connected to a single AP.
> >
> > Given your other hash patches, does this even make sense still?
> 
> This handles the TX side for station VIFs.  The more complicated
> hashing handles the rx logic.  I could use the hash
> for the tx side, though performance is likely a small bit
> worse since you have to deal with the hash logic.

Well, for the TX side in your particular case the vhash should always
just find the right station first, so basically it's the same, no? I
mean, if you used the new hash in the TX code, it would basically do the
same the some_sta thing does, assuming your hash spreads well, no?

> And, if the more complicated RFC hashing patch has no upstream
> chance anyway, then if the 'some-sta' patch is acceptable,
> I'd still be interested in seeing it upstream.

Well I'm debating (with myself mostly) ... The some_sta seems
reasonable, but still a big ugly and like a special case. I'd rather not
merge the vhash because of the various overheads, so you'd probably want
to maintain that out of tree anyway. It seems to me that the vhash
should address your other case pretty much just as well, so then if you
maintain that anyway I wouldn't have to merge the some_sta patch ... I
guess I'd kinda prefer that :-)

johannes

Re: [PATCH v4] mac80211: Optimize sta lookup for many VIFs

[Ben Greear]

On 04/11/2013 02:15 AM, Johannes Berg wrote:
> On Tue, 2013-04-09 at 10:35 -0700, Ben Greear wrote:
>> On 04/09/2013 02:50 AM, Johannes Berg wrote:
>>> On Fri, 2013-03-29 at 09:00 -0700, greearb@candelatech.com wrote:
>>>> From: Ben Greear <greearb@candelatech.com>
>>>>
>>>> The sta_info hash is designed to deal with an AP
>>>> with lots of stations associated, or a station interface
>>>> connected to a single AP.
>>>
>>> Given your other hash patches, does this even make sense still?
>>
>> This handles the TX side for station VIFs.  The more complicated
>> hashing handles the rx logic.  I could use the hash
>> for the tx side, though performance is likely a small bit
>> worse since you have to deal with the hash logic.
>
> Well, for the TX side in your particular case the vhash should always
> just find the right station first, so basically it's the same, no? I
> mean, if you used the new hash in the TX code, it would basically do the
> same the some_sta thing does, assuming your hash spreads well, no?

Yes, assuming good spread.  The hash spread does fail catastrophically
if the lowest MAC octet doesn't change, however.  A cure for that might
just be a smarter hash method, however.

>> And, if the more complicated RFC hashing patch has no upstream
>> chance anyway, then if the 'some-sta' patch is acceptable,
>> I'd still be interested in seeing it upstream.
>
> Well I'm debating (with myself mostly) ... The some_sta seems
> reasonable, but still a big ugly and like a special case. I'd rather not
> merge the vhash because of the various overheads, so you'd probably want
> to maintain that out of tree anyway. It seems to me that the vhash
> should address your other case pretty much just as well, so then if you
> maintain that anyway I wouldn't have to merge the some_sta patch ... I
> guess I'd kinda prefer that :-)

Well, with regard to vhash overhead, it's not that much extra code or
memory, and in the hot paths it should be no worse than the current
code as far as I can tell.

In multi-VAP cases, if we do the per-sdata vhash, you might actually see
some improvements on tx side due to less hash collisions (in real word
cases not quite as strange as mine!).

Thanks,
Ben


-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com