Message ID | 1365007698-25295-1-git-send-email-greearb@candelatech.com (mailing list archive) |
---|---|
State | Not Applicable, archived |
Headers | show |
On Wed, 2013-04-03 at 09:48 -0700, greearb@candelatech.com wrote: > From: Ben Greear <greearb@candelatech.com> > > 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 -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 04/09/2013 02:57 AM, Johannes Berg wrote: > On Wed, 2013-04-03 at 09:48 -0700, greearb@candelatech.com 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
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 -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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
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
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
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 -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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,