Skip to contentSkip to conversation

mac80211: Add vif hash for multi-station RX performance.

RFC In review [email protected] 2 participants 9 messages Apr 3, 2013 – Apr 24, 2013 mac80211

lore
Share & tools
lore
#0 lore raw

RFC 1/2 mac80211: Add vif hash for multi-station RX performance.

From: Ben Greear <[email protected]>

When one has multiple station VIFS all connected to the same AP, the rx logic becomes a linear walk of all stations. To improve performance in this case, hash the station VIFs on the VIF MAC. This significantly improves performance: 70Mbps without the patch, 190Mbps with patch, when using 50 stations receiving TCP traffic.

Probably not many people doing this, so not worth pushing upstream at this time.

---

Think I fixed the station matching issues Johannes mentioned.

:100644 100644 b985722... 84f1b73... M net/mac80211/ieee80211_i.h
:100644 100644 c6844ad... a23a103... M net/mac80211/rx.c
:100644 100644 c465b1d... 34351dd... M net/mac80211/sta_info.c
:100644 100644 4947341... 227fce7... M net/mac80211/sta_info.h

 net/mac80211/ieee80211_i.h |    3 +-
 net/mac80211/rx.c          |   15 +++++++++++++
 net/mac80211/sta_info.c    |   51 +++++++++++++++++++++++++++++++++++++++++--
 net/mac80211/sta_info.h    |    7 +++++-
 4 files changed, 71 insertions(+), 5 deletions(-)
net/mac80211/ieee80211_i.h +2 -1
index b985722..84f1b73 100644
@@ -985,7 +985,8 @@ struct ieee80211_local {
 	spinlock_t tim_lock;
 	unsigned long num_sta;
 	struct list_head sta_list;
-	struct sta_info __rcu *sta_hash[STA_HASH_SIZE];
+	struct sta_info __rcu *sta_hash[STA_HASH_SIZE]; /* By station addr */
+	struct sta_info __rcu *sta_vhash[STA_HASH_SIZE]; /* By VIF mac addr */
 	struct timer_list sta_cleanup;
 	int sta_generation;
 
net/mac80211/rx.c +15 -0
index c6844ad..a23a103 100644
@@ -3152,6 +3152,20 @@ static void __ieee80211_rx_handle_packet(struct ieee80211_hw *hw,
 	if (ieee80211_is_data(fc)) {
 		prev_sta = NULL;
 
+		/* Check for Station VIFS by hashing on the destination MAC
+		 * (ie, local sdata MAC).  This changes 'promisc' behaviour,
+		 * but not sure that is a bad thing.
+		 */
+		if ((!is_multicast_ether_addr(hdr->addr1)) &&
+		    (local->monitors == 0) && (local->cooked_mntrs == 0)) {
+			sta = sta_info_get_by_vif(local, hdr->addr1, hdr->addr2);
+			if (sta) {
+				rx.sta = sta;
+				rx.sdata = sta->sdata;
+				goto rx_and_done;
+			}
+		}
+
 		for_each_sta_info(local, hdr->addr2, sta, tmp) {
 			if (!prev_sta) {
 				prev_sta = sta;
@@ -3169,6 +3183,7 @@ static void __ieee80211_rx_handle_packet(struct ieee80211_hw *hw,
 			rx.sta = prev_sta;
 			rx.sdata = prev_sta->sdata;
 
+		rx_and_done:
 			if (ieee80211_prepare_and_rx_handle(&rx, skb, true))
 				return;
 			goto out;
net/mac80211/sta_info.c +48 -3

79 lines not on this page · raw message

net/mac80211/sta_info.h +6 -1
index 4947341..227fce7 100644
@@ -227,7 +227,8 @@ struct sta_ampdu_mlme {
  * mac80211 is communicating with.
  *
  * @list: global linked list entry
- * @hnext: hash table linked list pointer
+ * @hnext: hash table linked list pointer, by (remote) station MAC
+ * @vnext: hash table linked list pointer, by VIF MAC
  * @local: pointer to the global information
  * @sdata: virtual interface this station belongs to
  * @ptk: peer key negotiated with this station, if any
@@ -304,6 +305,7 @@ struct sta_info {
 	struct list_head list;
 	struct rcu_head rcu_head;
 	struct sta_info __rcu *hnext;
+	struct sta_info __rcu *vnext;
 	struct ieee80211_local *local;
 	struct ieee80211_sub_if_data *sdata;
 	struct ieee80211_key __rcu *gtk[NUM_DEFAULT_KEYS + NUM_DEFAULT_MGMT_KEYS];
@@ -507,6 +509,9 @@ struct sta_info *sta_info_get(struct ieee80211_sub_if_data *sdata,
 struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata,
 				  const u8 *addr);
 
+struct sta_info *sta_info_get_by_vif(struct ieee80211_local *local,
+				     const u8 *vif_addr, const u8 *sta_addr);
+
 static inline
 void for_each_sta_info_type_check(struct ieee80211_local *local,
 				  const u8 *addr,
Signature · 1 line
1.7.3.4
#1 lore raw

RFC 2/2 mac80211: Add vhash to debugfs.

From: Ben Greear <[email protected]>

---
:100644 100644 2bbe377... b89b885... M net/mac80211/debugfs.c

 net/mac80211/debugfs.c |   37 +++++++++++++++++++++++++++++++++++++
 1 files changed, 37 insertions(+), 0 deletions(-)
net/mac80211/debugfs.c +37 -0
index 2bbe377..b89b885 100644
@@ -210,9 +210,45 @@ static ssize_t sta_hash_read(struct file *file, char __user *user_buf,
 	return q;
 }
 
+static ssize_t sta_lhash_read(struct file *file, char __user *user_buf,
+			      size_t count, loff_t *ppos)
+{
+	struct ieee80211_local *local = file->private_data;
+	int mxln = STA_HASH_SIZE * 10;
+	char *buf = kzalloc(mxln, GFP_KERNEL);
+	int q, res = 0;
+	struct sta_info *sta;
+
+	if (!buf)
+		return 0;
+	
+	mutex_lock(&local->sta_mtx);
+	for (q = 0; q < STA_HASH_SIZE; q++) {
+		int cnt = 0;
+		sta = local->sta_vhash[q];
+		while (sta) {
+			cnt++;
+			sta = sta->vnext;
+		}
+		if (cnt) {
+			res += sprintf(buf + res, "%i: %i\n", q, cnt);
+			if (res >= (STA_HASH_SIZE * 10)) {
+				res = STA_HASH_SIZE * 10;
+				break;
+			}
+		}
+	}
+	mutex_unlock(&local->sta_mtx);
+
+	q = simple_read_from_buffer(user_buf, count, ppos, buf, res);
+	kfree(buf);
+	return q;
+}
+
 DEBUGFS_READONLY_FILE_OPS(hwflags);
 DEBUGFS_READONLY_FILE_OPS(queues);
 DEBUGFS_READONLY_FILE_OPS(sta_hash);
+DEBUGFS_READONLY_FILE_OPS(sta_lhash);
 
 /* statistics stuff */
 
@@ -282,6 +318,7 @@ void debugfs_hw_add(struct ieee80211_local *local)
 	DEBUGFS_ADD(wep_iv);
 	DEBUGFS_ADD(queues);
 	DEBUGFS_ADD(sta_hash);
+	DEBUGFS_ADD(sta_lhash);
 #ifdef CONFIG_PM
 	DEBUGFS_ADD_MODE(reset, 0200);
 #endif
Signature · 1 line
1.7.3.4
maintainer
#2 lore raw
In reply to [email protected]
Quoted 11 lines · On Wed, 2013-04-03 at 09:48 -0700, [email protected] wrote:

From: Ben Greear <[email protected]>

When one has multiple station VIFS all connected to the same AP, the rx logic becomes a linear walk of all stations. To improve performance in this case, hash the station VIFs on the VIF MAC. This significantly improves performance: 70Mbps without the patch, 190Mbps with patch, when using 50 stations receiving TCP traffic.

Probably not many people doing this, so not worth pushing upstream at this time.

I tend to agree.

net/mac80211/sta_info.c static int sta_info_hash_del(struct ieee80211_local *local, · line 80

Quoted 7 lines

+++ b/net/mac80211/sta_info.c

net/mac80211/sta_info.c +1 -1
@@ -77,19 +77,42 @@ static int sta_info_hash_del(struct ieee80211_local *local,
 	s = rcu_dereference_protected(local->sta_hash[STA_HASH(sta->sta.addr)],
 				      lockdep_is_held(&local->sta_mtx));
 	if (!s)
-		return -ENOENT;
+		goto try_lhash;

Does this make sense? If the station doesn't exist in the regular hash, it really shouldn't be in the vif hash either, no?

net/mac80211/sta_info.c static int sta_info_hash_del(struct ieee80211_local *local, · line 98

Quoted 7 lines
net/mac80211/sta_info.c +5 -0
 	if (rcu_access_pointer(s->hnext)) {
 		rcu_assign_pointer(s->hnext, sta->hnext);
+		goto try_lhash;
+	}
+
+	/* Remove from the local VIF addr hash */
+try_lhash:

That last goto there seems a bit pointless :)

net/mac80211/sta_info.c static int sta_info_hash_del(struct ieee80211_local *local, · line 102

Quoted 4 lines
net/mac80211/sta_info.c +4 -0
+	s = rcu_dereference_protected(local->sta_vhash[STA_HASH(sta->sdata->vif.addr)],
+				      lockdep_is_held(&local->sta_mtx));
+	if (!s)
+		return -ENONET;

You probably want -ENOENT, not -ENONET.

net/mac80211/sta_info.c struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata, · line 288

Quoted 12 lines
net/mac80211/sta_info.c +12 -0
+struct sta_info *sta_info_get_by_vif(struct ieee80211_local *local,
+				     const u8 *vif_addr, const u8 * sta_addr) {
+	struct sta_info *sta;
+
+	sta = rcu_dereference_check(local->sta_vhash[STA_HASH(vif_addr)],
+				    lockdep_is_held(&local->sta_mtx));
+	while (sta) {
+		if (ether_addr_equal(sta->sdata->vif.addr, vif_addr) &&
+		    ether_addr_equal(sta->sta.addr, sta_addr))
+			break;
+		sta = rcu_dereference_check(sta->vnext,
+					    lockdep_is_held(&local->sta_mtx));

Almost all of your rcu_dereference_check() invocations should be rcu_dereference_protected(). See include/linux/rcupdate.h :)

johannes

author
#3 lore raw
Quoted 12 lines · Johannes Berg

net/mac80211/sta_info.c static int sta_info_hash_del(struct ieee80211_local *local, · line 80

Quoted 7 lines · On Wed, 2013-04-03 at 09:48 -0700, [email protected] wrote:

+++ b/net/mac80211/sta_info.c

net/mac80211/sta_info.c +1 -1
@@ -77,19 +77,42 @@ static int sta_info_hash_del(struct ieee80211_local *local,
  	s = rcu_dereference_protected(local->sta_hash[STA_HASH(sta->sta.addr)],
  				      lockdep_is_held(&local->sta_mtx));
  	if (!s)
-		return -ENOENT;
+		goto try_lhash;

Does this make sense? If the station doesn't exist in the regular hash, it really shouldn't be in the vif hash either, no?

It shouldn't be in the new vif hash, so I could add a short-cut as you suggest. I had left it in for reasons of paranoia.

Quoted 6 lines

net/mac80211/sta_info.c static int sta_info_hash_del(struct ieee80211_local *local, · line 102

Quoted 4 lines
net/mac80211/sta_info.c +4 -0
+	s = rcu_dereference_protected(local->sta_vhash[STA_HASH(sta->sdata->vif.addr)],
+				      lockdep_is_held(&local->sta_mtx));
+	if (!s)
+		return -ENONET;

You probably want -ENOENT, not -ENONET.

Yes, and in fact, I need to return just the rv from the old hash logic since otherwise we get false failure results since the new hash only has vifs. This was the cause of that splat I posted a week or two ago...

Quoted 7 lines
Quoted 7 lines
net/mac80211/sta_info.c +7 -0
+struct sta_info *sta_info_get_by_vif(struct ieee80211_local *local,
+				     const u8 *vif_addr, const u8 * sta_addr) {
+	struct sta_info *sta;
+
+	sta = rcu_dereference_check(local->sta_vhash[STA_HASH(vif_addr)],
+				    lockdep_is_held(&local->sta_mtx));
+	while (sta) {
Quoted 8 lines

net/mac80211/sta_info.c struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata, · line 288

Quoted 5 lines
net/mac80211/sta_info.c +5 -0
+		if (ether_addr_equal(sta->sdata->vif.addr, vif_addr) &&
+		    ether_addr_equal(sta->sta.addr, sta_addr))
+			break;
+		sta = rcu_dereference_check(sta->vnext,
+					    lockdep_is_held(&local->sta_mtx));

Almost all of your rcu_dereference_check() invocations should be rcu_dereference_protected(). See include/linux/rcupdate.h :)

Now this, I'm not so sure of. That rcu_dereference_protected seems to be only used for the 'update-side' use. I was under the impression that when the mac80211 rx logic is called we are only protected by rcu, not the update mutex.

I also struggle to understand RCU properly...so maybe I'm just wrong about all that...

The other methods to get sta_info around that code use the _check() variant, by the way...

Thanks,
Ben

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com
maintainer
#4 lore raw
Quoted 16 lines · Ben Greear
Quoted 7 lines
Quoted 7 lines
net/mac80211/sta_info.c +7 -0
+struct sta_info *sta_info_get_by_vif(struct ieee80211_local *local,
+				     const u8 *vif_addr, const u8 * sta_addr) {
+	struct sta_info *sta;
+
+	sta = rcu_dereference_check(local->sta_vhash[STA_HASH(vif_addr)],
+				    lockdep_is_held(&local->sta_mtx));
+	while (sta) {
Quoted 8 lines

net/mac80211/sta_info.c struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata, · line 288

Quoted 5 lines
net/mac80211/sta_info.c +5 -0
+		if (ether_addr_equal(sta->sdata->vif.addr, vif_addr) &&
+		    ether_addr_equal(sta->sta.addr, sta_addr))
+			break;
+		sta = rcu_dereference_check(sta->vnext,
+					    lockdep_is_held(&local->sta_mtx));

Almost all of your rcu_dereference_check() invocations should be rcu_dereference_protected(). See include/linux/rcupdate.h :)

Quoted 4 lines

Now this, I'm not so sure of. That rcu_dereference_protected seems to be only used for the 'update-side' use. I was under the impression that when the mac80211 rx logic is called we are only protected by rcu, not the update mutex.

Ah, yes, I was reading this the wrong way, sorry. Here the _check() is correct of course -- you want to be either under RCU protection or hold the sta_mtx.

Quoted 5 lines

I also struggle to understand RCU properly...so maybe I'm just wrong about all that...

The other methods to get sta_info around that code use the _check() variant, by the way...

Yeah ... :)

Another question: Have you thought about hashing the virtual interfaces instead of the stations, and then hashing the stations inside each virtual interface? That would make it a bit of a two-level thing:

A1 (in the frame) -> virtual interface

    A2 (frame) -> station

But it would address the TX side efficiently without "some_sta" since you know the virtual interface there already, and could potentially have less impact on the code? On TX it'd actually even be more efficient if you have more than 1 station per interface (right now you don't though)

johannes

author
#5 lore raw
Quoted 6 lines · Johannes Berg

On Tue, 2013-04-09 at 10:54 -0700, Ben Greear wrote:

Another question: Have you thought about hashing the virtual interfaces instead of the stations, and then hashing the stations inside each virtual interface? That would make it a bit of a two-level thing:

Quoted 7 lines

A1 (in the frame) -> virtual interface

     A2 (frame) -> station

But it would address the TX side efficiently without "some_sta" since you know the virtual interface there already, and could potentially have less impact on the code? On TX it'd actually even be more efficient if you have more than 1 station per interface (right now you don't though)

A two-level hash might be helpful, but it might complicate the rx logic a bit because at least in many cases you have to walk all sta in all sdata, so would be some sort of double-loop. Not that bad though, and performance wise it should be similar. Doing per-sdata hash should also fix bad vhash collisions (such as if stations change a high-order part of their MAC and leave the lowest octet the same).

On tx, if we assume good hash spread, then it should also have good performance, and there is no case I can think of where having multiple sta per station VIF would be needed, so very unlikely to have bad hash performance.

But a question on all of this: Are you assuming the current sta_hash on the wiphy stays the same, or would you want it moved into the sdata as well?

I'd be willing to try it if you think it might be worth pushing the result upstream. If it's not going upstream anyway, then I'll probably just stick with my some-sta and vhash patches at least until they start conflicting bad enough with upstream to be worth re-visiting.

Thanks,
Ben

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com
author
#6 lore raw
In reply to Johannes Berg
Quoted 39 lines · Johannes Berg
Quoted 16 lines · Ben Greear
Quoted 7 lines
Quoted 7 lines
net/mac80211/sta_info.c +7 -0
+struct sta_info *sta_info_get_by_vif(struct ieee80211_local *local,
+				     const u8 *vif_addr, const u8 * sta_addr) {
+	struct sta_info *sta;
+
+	sta = rcu_dereference_check(local->sta_vhash[STA_HASH(vif_addr)],
+				    lockdep_is_held(&local->sta_mtx));
+	while (sta) {
Quoted 8 lines

net/mac80211/sta_info.c struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata, · line 288

Quoted 5 lines
net/mac80211/sta_info.c +5 -0
+		if (ether_addr_equal(sta->sdata->vif.addr, vif_addr) &&
+		    ether_addr_equal(sta->sta.addr, sta_addr))
+			break;
+		sta = rcu_dereference_check(sta->vnext,
+					    lockdep_is_held(&local->sta_mtx));

Almost all of your rcu_dereference_check() invocations should be rcu_dereference_protected(). See include/linux/rcupdate.h :)

Quoted 4 lines

Now this, I'm not so sure of. That rcu_dereference_protected seems to be only used for the 'update-side' use. I was under the impression that when the mac80211 rx logic is called we are only protected by rcu, not the update mutex.

Ah, yes, I was reading this the wrong way, sorry. Here the _check() is correct of course -- you want to be either under RCU protection or hold the sta_mtx.

Quoted 5 lines

I also struggle to understand RCU properly...so maybe I'm just wrong about all that...

The other methods to get sta_info around that code use the _check() variant, by the way...

Yeah ... :)

Another question: Have you thought about hashing the virtual interfaces instead of the stations, and then hashing the stations inside each virtual interface? That would make it a bit of a two-level thing:

Quoted 7 lines

A1 (in the frame) -> virtual interface

     A2 (frame) -> station

But it would address the TX side efficiently without "some_sta" since you know the virtual interface there already, and could potentially have less impact on the code? On TX it'd actually even be more efficient if you have more than 1 station per interface (right now you don't though)

This idea suddenly looks a lot more interesting. The ieee80211_tx_status method needs to find the remote station & sdata, but in the AP case, the station hash works best, and in my many-sta-vif case, the VIF hash works best. I don't see any way to guess which hash to use in this case.

But, if we first hashed to find sdata, and then had a vif hash in the sdata object, the lookup should be fast for cases where the hash function works well.

I'll give this a try...

Thanks,
Ben

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com
author
#7 lore raw
Quoted 19 lines · Ben Greear
Quoted 11 lines · Johannes Berg

Another question: Have you thought about hashing the virtual interfaces instead of the stations, and then hashing the stations inside each virtual interface? That would make it a bit of a two-level thing:

A1 (in the frame) -> virtual interface

     A2 (frame) -> station

But it would address the TX side efficiently without "some_sta" since you know the virtual interface there already, and could potentially have less impact on the code? On TX it'd actually even be more efficient if you have more than 1 station per interface (right now you don't though)

This idea suddenly looks a lot more interesting. The ieee80211_tx_status method needs to find the remote station & sdata, but in the AP case, the station hash works best, and in my many-sta-vif case, the VIF hash works best. I don't see any way to guess which hash to use in this case.

Quoted 5 lines

But, if we first hashed to find sdata, and then had a vif hash in the sdata object, the lookup should be fast for cases where the hash function works well.

I'll give this a try...

Seems to mostly be working, but I've a few questions.

First, if we are hashing sdata on sdata->vif.addr, then we must assume that everything in that hash has a unique MAC. I'm thinking that I would just never put monitor devices in the hash. Is there anything else that would cause problems with this?

Second, the sta_info_get_bss call is found fairly often. It talks about finding a station on sdata or associated vlan. Does this indicate that the there are VLAN sdata objects with duplicate MACs?

I was hoping I could replace at least most calls to sta_info_get_bss with one that just searched the new sdata->sta_hash hash table...

Thanks,
Ben

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com
maintainer
#8 lore raw
Quoted 4 lines · Ben Greear
Quoted 4 lines

This idea suddenly looks a lot more interesting. The ieee80211_tx_status method needs to find the remote station & sdata, but in the AP case, the station hash works best, and in my many-sta-vif case, the VIF hash works best. I don't see any way to guess which hash to use in this case.

Indeed, that'd be tricky.

Quoted 6 lines
Quoted 5 lines

But, if we first hashed to find sdata, and then had a vif hash in the sdata object, the lookup should be fast for cases where the hash function works well.

I'll give this a try...

Quoted 7 lines

Seems to mostly be working, but I've a few questions.

First, if we are hashing sdata on sdata->vif.addr, then we must assume that everything in that hash has a unique MAC. I'm thinking that I would just never put monitor devices in the hash. Is there anything else that would cause problems with this?

Monitor interfaces won't have stations, so they're not needed anyway.

Quoted 4 lines

Second, the sta_info_get_bss call is found fairly often. It talks about finding a station on sdata or associated vlan. Does this indicate that the there are VLAN sdata objects with duplicate MACs?

Yes. See net/mac80211/iface.c identical_mac_addr_allowed().

Quoted 2 lines

I was hoping I could replace at least most calls to sta_info_get_bss with one that just searched the new sdata->sta_hash hash table...

I have no idea how my answer affects this :)

johannes