[RFC 1/2] mac80211: Add debugfs file to show station-hash counts.

[RFC 1/2] mac80211: Add debugfs file to show station-hash counts.

[greearb]

From: Ben Greear <greearb@candelatech.com>

Helps debug bad hash spreads, like when you have lots of
station interfaces all connected to the same AP.

Signed-off-by: Ben Greear <greearb@candelatech.com>
---
:100644 100644 466f4b4... 07885cb... 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 466f4b4..07885cb 100644
--- a/net/mac80211/debugfs.c
+++ b/net/mac80211/debugfs.c
@@ -177,8 +177,44 @@ static ssize_t queues_read(struct file *file, char __user *user_buf,
 	return simple_read_from_buffer(user_buf, count, ppos, buf, res);
 }
 
+static ssize_t sta_hash_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_hash[q];
+		while (sta) {
+			cnt++;
+			sta = sta->hnext;
+		}
+		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);
 
 /* statistics stuff */
 
@@ -247,6 +283,7 @@ void debugfs_hw_add(struct ieee80211_local *local)
 	DEBUGFS_ADD(total_ps_buffered);
 	DEBUGFS_ADD(wep_iv);
 	DEBUGFS_ADD(queues);
+	DEBUGFS_ADD(sta_hash);
 #ifdef CONFIG_PM
 	DEBUGFS_ADD_MODE(reset, 0200);
 #endif
-- 
1.7.3.4

[RFC 2/2] mac80211: Optimize sta lookup for many VIFs

[greearb]

From: Ben Greear <greearb@candelatech.com>

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 it's 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.

Signed-off-by: Ben Greear <greearb@candelatech.com>
---
:100644 100644 a618bda... 5288a4f... M	net/mac80211/cfg.c
:100644 100644 493e2e8... fe5d35b... M	net/mac80211/ieee80211_i.h
:100644 100644 415f9c6... 74d58f4... M	net/mac80211/sta_info.c
 net/mac80211/cfg.c         |    5 +++++
 net/mac80211/ieee80211_i.h |    6 ++++++
 net/mac80211/sta_info.c    |   18 +++++++++++++++++-
 3 files changed, 28 insertions(+), 1 deletions(-)

diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c
index a618bda..5288a4f 100644
--- a/net/mac80211/cfg.c
+++ b/net/mac80211/cfg.c
@@ -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,11 @@ static int ieee80211_change_station(struct wiphy *wiphy,
 			prev_4addr = true;
 		}
 
+		some_sta = rcu_dereference(sta->sdata->some_sta);
+		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) {
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index 493e2e8..fe5d35b 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -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 aids oportunistic 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;
 
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index 415f9c6..74d58f4 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -193,7 +193,17 @@ struct sta_info *sta_info_get(struct ieee80211_sub_if_data *sdata,
 			      const u8 *addr)
 {
 	struct ieee80211_local *local = sdata->local;
-	struct sta_info *sta;
+	struct sta_info *sta, *some_sta;
+
+	/* Shortcut for finding station entries when sdata is a station */
+	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));
@@ -263,10 +273,14 @@ struct sta_info *sta_info_get_by_idx(struct ieee80211_sub_if_data *sdata,
  */
 void sta_info_free(struct ieee80211_local *local, struct sta_info *sta)
 {
+	struct sta_info* some_sta;
 	if (sta->rate_ctrl)
 		rate_control_free_sta(sta);
 
 	sta_dbg(sta->sdata, "Destroyed STA %pM\n", sta->sta.addr);
+	some_sta = rcu_dereference(sta->sdata->some_sta);
+	if (some_sta == sta)
+		rcu_assign_pointer(sta->sdata->some_sta, NULL);
 
 	kfree(sta);
 }
@@ -373,6 +387,8 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
 	for (i = 0; i < NUM_RX_DATA_QUEUES; i++)
 		sta->last_seq_ctrl[i] = cpu_to_le16(USHRT_MAX);
 
+	rcu_assign_pointer(sta->sdata->some_sta, sta);
+
 	sta_dbg(sdata, "Allocated STA %pM\n", sta->sta.addr);
 
 #ifdef CONFIG_MAC80211_MESH
-- 
1.7.3.4

Re: [RFC 2/2] mac80211: Optimize sta lookup for many VIFs

[Johannes Berg]

On Fri, 2013-03-15 at 14:13 -0700, greearb@candelatech.com wrote:
 
> --- a/net/mac80211/ieee80211_i.h
> +++ b/net/mac80211/ieee80211_i.h
> @@ -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 aids oportunistic lookup for sta_info objects when

typo: opportunistic. Also it should probably say "allows opportunistic
lookup" :-)

> +	/* Shortcut for finding station entries when sdata is a station */
> +	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;

I worry a little bit about the overhead in the "always cache miss" case.
Is this really helpful for AP interfaces? Maybe it should be limited to
managed virtual interfaces.

>  
>  	sta = rcu_dereference_check(local->sta_hash[STA_HASH(addr)],
>  				    lockdep_is_held(&local->sta_mtx));
> @@ -263,10 +273,14 @@ struct sta_info *sta_info_get_by_idx(struct ieee80211_sub_if_data *sdata,
>   */
>  void sta_info_free(struct ieee80211_local *local, struct sta_info *sta)
>  {
> +	struct sta_info* some_sta;
>  	if (sta->rate_ctrl)

missing blank line

>  		rate_control_free_sta(sta);
>  
>  	sta_dbg(sta->sdata, "Destroyed STA %pM\n", sta->sta.addr);
> +	some_sta = rcu_dereference(sta->sdata->some_sta);
> +	if (some_sta == sta)
> +		rcu_assign_pointer(sta->sdata->some_sta, NULL);

This clearing is WAY too late. You can look up the station way after you
must be allowed to, this will invariably crash eventually. It absolutely
must be when the station is unhashed, not when it's freed.

> @@ -373,6 +387,8 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
>  	for (i = 0; i < NUM_RX_DATA_QUEUES; i++)
>  		sta->last_seq_ctrl[i] = cpu_to_le16(USHRT_MAX);
>  
> +	rcu_assign_pointer(sta->sdata->some_sta, sta);

This is too early, the station might not even be used, this must only be
done when the station is hashed.

johannes

Re: [RFC 2/2] mac80211: Optimize sta lookup for many VIFs

[Ben Greear]

On 03/19/2013 01:12 PM, Johannes Berg wrote:
> On Fri, 2013-03-15 at 14:13 -0700, greearb@candelatech.com wrote:
>
>> --- a/net/mac80211/ieee80211_i.h
>> +++ b/net/mac80211/ieee80211_i.h
>> @@ -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 aids oportunistic lookup for sta_info objects when
>
> typo: opportunistic. Also it should probably say "allows opportunistic
> lookup" :-)
>
>> +	/* Shortcut for finding station entries when sdata is a station */
>> +	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;
>
> I worry a little bit about the overhead in the "always cache miss" case.
> Is this really helpful for AP interfaces? Maybe it should be limited to
> managed virtual interfaces.

This was a quick fix that resolved the issue I was seeing, but
I am now thinking that maybe a full hash based on local MAC instead
of remote MAC should be added.  In some code (station TX) we can use
that hash, and we could also use it on RX when trying to find the
sdata that a non-multicast packet is destined for.

For other uses, the existing hash on the remote MAC address would
remain the preferred lookup.

The RX logic might still be tricky...not sure if we really need to pass
all packets to PROMISC interfaces, nor sure when we could safely not
fan-out non-data packets.

>>   	sta_dbg(sta->sdata, "Destroyed STA %pM\n", sta->sta.addr);
>> +	some_sta = rcu_dereference(sta->sdata->some_sta);
>> +	if (some_sta == sta)
>> +		rcu_assign_pointer(sta->sdata->some_sta, NULL);
>
> This clearing is WAY too late. You can look up the station way after you
> must be allowed to, this will invariably crash eventually. It absolutely
> must be when the station is unhashed, not when it's freed.
>
>> @@ -373,6 +387,8 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
>>   	for (i = 0; i < NUM_RX_DATA_QUEUES; i++)
>>   		sta->last_seq_ctrl[i] = cpu_to_le16(USHRT_MAX);
>>
>> +	rcu_assign_pointer(sta->sdata->some_sta, sta);
>
> This is too early, the station might not even be used, this must only be
> done when the station is hashed.

Ok, I'll work on that.

Thanks,
Ben

>
> johannes
>


-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com