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.
Signed-off-by: Ben Greear <[email protected]>
---
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(-)
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index b985722..84f1b73 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -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;
diff --git a/net/mac80211/rx.c b/net/mac80211/rx.c
index c6844ad..a23a103 100644
--- a/net/mac80211/rx.c
+++ b/net/mac80211/rx.c
@@ -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;
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index c465b1d..34351dd 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -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;
+
if (s == sta) {
rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)],
s->hnext);
- return 0;
+ goto try_lhash;
}
while (rcu_access_pointer(s->hnext) &&
rcu_access_pointer(s->hnext) != sta)
s = rcu_dereference_protected(s->hnext,
- lockdep_is_held(&local->sta_mtx));
+ lockdep_is_held(&local->sta_mtx));
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:
+ s = rcu_dereference_protected(local->sta_vhash[STA_HASH(sta->sdata->vif.addr)],
+ lockdep_is_held(&local->sta_mtx));
+ if (!s)
+ return -ENONET;
+
+ if (s == sta) {
+ rcu_assign_pointer(local->sta_vhash[STA_HASH(sta->sdata->vif.addr)],
+ s->vnext);
+ return 0;
+ }
+
+ while (rcu_access_pointer(s->vnext) &&
+ rcu_access_pointer(s->vnext) != sta)
+ s = rcu_dereference_protected(s->vnext,
+ lockdep_is_held(&local->sta_mtx));
+ if (rcu_access_pointer(s->vnext)) {
+ rcu_assign_pointer(s->vnext, sta->vnext);
return 0;
}
@@ -251,6 +274,23 @@ struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata,
return sta;
}
+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));
+ }
+ return sta;
+}
+
+
struct sta_info *sta_info_get_by_idx(struct ieee80211_sub_if_data *sdata,
int idx)
{
@@ -300,6 +340,11 @@ static void sta_info_hash_add(struct ieee80211_local *local,
sta->hnext = local->sta_hash[STA_HASH(sta->sta.addr)];
rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)], sta);
+ if (sta->sdata->vif.type == NL80211_IFTYPE_STATION) {
+ sta->vnext = local->sta_vhash[STA_HASH(sta->sdata->vif.addr)];
+ rcu_assign_pointer(local->sta_vhash[STA_HASH(sta->sdata->vif.addr)], sta);
+ }
+
rcu_assign_pointer(sta->sdata->some_sta, sta);
}
diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
index 4947341..227fce7 100644
--- a/net/mac80211/sta_info.h
+++ b/net/mac80211/sta_info.h
@@ -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,
--
1.7.3.4
On Tue, 2013-04-23 at 15:06 -0700, Ben Greear wrote:
> > 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.
> > 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?
Monitor interfaces won't have stations, so they're not needed anyway.
> 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().
> 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
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.
> +++ b/net/mac80211/sta_info.c
> @@ -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?
> 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 :)
> + 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.
> +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
On Tue, 2013-04-09 at 10:54 -0700, Ben Greear wrote:
> >> +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 :)
>
> 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.
> 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
On 04/11/2013 02:19 AM, Johannes Berg wrote:
> On Tue, 2013-04-09 at 10:54 -0700, Ben Greear wrote:
>
>>>> +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 :)
>>
>> 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.
>
>> 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)
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
--
Ben Greear <[email protected]>
Candela Technologies Inc http://www.candelatech.com
On 04/23/2013 12:42 PM, Ben Greear wrote:
> On 04/11/2013 02:19 AM, Johannes Berg 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:
>>
>> 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...
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
--
Ben Greear <[email protected]>
Candela Technologies Inc http://www.candelatech.com
On 04/11/2013 02:19 AM, Johannes Berg wrote:
> 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:
>
> 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
--
Ben Greear <[email protected]>
Candela Technologies Inc http://www.candelatech.com
On 04/09/2013 02:57 AM, Johannes Berg wrote:
> On Wed, 2013-04-03 at 09:48 -0700, [email protected] wrote:
>> +++ b/net/mac80211/sta_info.c
>> @@ -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.
>> + 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...
>> +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 :)
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
--
Ben Greear <[email protected]>
Candela Technologies Inc http://www.candelatech.com
From: Ben Greear <[email protected]>
Signed-off-by: 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(-)
diff --git a/net/mac80211/debugfs.c b/net/mac80211/debugfs.c
index 2bbe377..b89b885 100644
--- a/net/mac80211/debugfs.c
+++ b/net/mac80211/debugfs.c
@@ -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
--
1.7.3.4