mac80211: Add vif hash for multi-station RX performance.
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
@@ -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
@@ -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
@@ -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
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
@@ -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
Johannes Berg
maintainerQuoted 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.cnet/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
-0if (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
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.cnet/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 bercu_dereference_protected(). Seeinclude/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
Johannes Berg
maintainerQuoted 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 bercu_dereference_protected(). Seeinclude/linux/rcupdate.h:)
Quoted 4 lines
Now this, I'm not so sure of. That
rcu_dereference_protectedseems 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_infoaround 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
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) -> stationBut 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
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 bercu_dereference_protected(). Seeinclude/linux/rcupdate.h:)Quoted 4 lines
Now this, I'm not so sure of. That
rcu_dereference_protectedseems 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 thesta_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_infoaround 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) -> stationBut 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
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) -> stationBut 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_statusmethod 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
Johannes Berg
maintainerQuoted 4 lines · Ben Greear
Quoted 4 lines
This idea suddenly looks a lot more interesting. The
ieee80211_tx_statusmethod 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_bsscall 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_bsswith one that just searched the newsdata->sta_hashhash table...
I have no idea how my answer affects this :)
johannes