Skip to contentSkip to conversation

mac80211: Optimize sta lookup for many VIFs

PATCH In review [email protected] 2 participants 8 messages Mar 29, 2013 – Apr 11, 2013 mac80211

lore
Share & tools
lore
#0 lore raw

PATCH v4 1/1 mac80211: Optimize sta lookup for many VIFs

From: Ben Greear <[email protected]>

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.

---

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(-)
net/mac80211/cfg.c +6 -0
index a618bda..a7e7f5d 100644
@@ -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) {
net/mac80211/ieee80211_i.h +6 -0
index 493e2e8..c6386c7 100644
@@ -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;
 
net/mac80211/sta_info.c +22 -1
index 415f9c6..d87a76d 100644
@@ -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)
Signature · 1 line
1.7.3.4
maintainer
#1 lore raw
Quoted 13 lines · On Fri, 2013-03-29 at 09:00 -0700, [email protected] wrote:
net/mac80211/cfg.c +1 -0
@@ -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;
 		}

net/mac80211/cfg.c static int ieee80211_change_station(struct wiphy *wiphy, · line 1324

Quoted 10 lines
net/mac80211/cfg.c +5 -0
 
+		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?

net/mac80211/cfg.c static void sta_info_hash_add(struct ieee80211_local *local, · line 301

Quoted 6 lines
net/mac80211/cfg.c +2 -0
@@ -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

author
#2 lore raw
Quoted 23 lines · Johannes Berg
Quoted 21 lines · On Fri, 2013-03-29 at 09:00 -0700, [email protected] wrote:
net/mac80211/cfg.c +6 -0
@@ -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);
 
Quoted 6 lines

net/mac80211/cfg.c static int ieee80211_change_station(struct wiphy *wiphy, · line 1324

Quoted 2 lines
net/mac80211/cfg.c +0 -0
  		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.

Quoted 8 lines

net/mac80211/cfg.c static void sta_info_hash_add(struct ieee80211_local *local, · line 301

Quoted 6 lines
net/mac80211/cfg.c +2 -0
@@ -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

Quoted 3 lines

johannes

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com
maintainer
#3 lore raw
Quoted 31 lines · Ben Greear
Quoted 23 lines · Johannes Berg
Quoted 21 lines · On Fri, 2013-03-29 at 09:00 -0700, [email protected] wrote:
net/mac80211/cfg.c +6 -0
@@ -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);
 
Quoted 6 lines

net/mac80211/cfg.c static int ieee80211_change_station(struct wiphy *wiphy, · line 1324

Quoted 2 lines
net/mac80211/cfg.c +0 -0
  		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?

Quoted 4 lines

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.

Quoted 1 line

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

No, mostly just wondering.

Quoted 10 lines
Quoted 8 lines

net/mac80211/cfg.c static void sta_info_hash_add(struct ieee80211_local *local, · line 301

Quoted 6 lines
net/mac80211/cfg.c +2 -0
@@ -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

author
#5 lore raw
Quoted 8 lines · Johannes Berg
Quoted 5 lines · On Fri, 2013-03-29 at 09:00 -0700, [email protected] wrote:

From: Ben Greear <[email protected]>

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

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com
maintainer
#6 lore raw
Quoted 8 lines · Ben Greear
Quoted 7 lines · Johannes Berg
Quoted 5 lines · On Fri, 2013-03-29 at 09:00 -0700, [email protected] wrote:

From: Ben Greear <[email protected]>

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.

Quoted 6 lines
Quoted 1 line

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?

Quoted 3 lines

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

author
#7 lore raw
Quoted 16 lines · Johannes Berg
Quoted 8 lines · Ben Greear
Quoted 7 lines · Johannes Berg
Quoted 5 lines · On Fri, 2013-03-29 at 09:00 -0700, [email protected] wrote:

From: Ben Greear <[email protected]>

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.

Quoted 6 lines
Quoted 1 line

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.

Quoted 4 lines

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.

Quoted 11 lines
Quoted 3 lines

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

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com