From: Johannes Berg <[email protected]>
We currently have a hand-rolled table with 256 entries and are
using the last byte of the MAC address as the hash. This hash
is obviously very fast, but collisions are easily created and
we waste a lot of space in the common case of just connecting
as a client to an AP where we just have a single station. The
other common case of an AP is also suboptimal due to the size
of the hash table and the ease of causing collisions.
Convert all of this to use rhashtable with jhash, which gives
us the advantage of a far better hash function (with random
perturbation to avoid hash collision attacks) and of course
that the hash table grows and shrinks dynamically with chain
length, improving both cases above.
Signed-off-by: Johannes Berg <[email protected]>
---
net/mac80211/ieee80211_i.h | 3 +-
net/mac80211/main.c | 9 +++--
net/mac80211/rx.c | 4 +--
net/mac80211/sta_info.c | 87 ++++++++++++++++++++--------------------------
net/mac80211/sta_info.h | 37 ++++++--------------
net/mac80211/status.c | 4 +--
6 files changed, 59 insertions(+), 85 deletions(-)
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index 3afe36824703..798392398ab5 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -26,6 +26,7 @@
#include <linux/etherdevice.h>
#include <linux/leds.h>
#include <linux/idr.h>
+#include <linux/rhashtable.h>
#include <net/ieee80211_radiotap.h>
#include <net/cfg80211.h>
#include <net/mac80211.h>
@@ -1195,7 +1196,7 @@ 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 rhashtable sta_hash;
struct timer_list sta_cleanup;
int sta_generation;
diff --git a/net/mac80211/main.c b/net/mac80211/main.c
index 5e09d354c5a5..95d59d24b271 100644
--- a/net/mac80211/main.c
+++ b/net/mac80211/main.c
@@ -557,6 +557,9 @@ struct ieee80211_hw *ieee80211_alloc_hw_nm(size_t priv_data_len,
local = wiphy_priv(wiphy);
+ if (sta_info_init(local))
+ goto err_free;
+
local->hw.wiphy = wiphy;
local->hw.priv = (char *)local + ALIGN(sizeof(*local), NETDEV_ALIGN);
@@ -629,8 +632,6 @@ struct ieee80211_hw *ieee80211_alloc_hw_nm(size_t priv_data_len,
spin_lock_init(&local->ack_status_lock);
idr_init(&local->ack_status_frames);
- sta_info_init(local);
-
for (i = 0; i < IEEE80211_MAX_QUEUES; i++) {
skb_queue_head_init(&local->pending[i]);
atomic_set(&local->agg_queue_stop[i], 0);
@@ -650,6 +651,9 @@ struct ieee80211_hw *ieee80211_alloc_hw_nm(size_t priv_data_len,
ieee80211_roc_setup(local);
return &local->hw;
+ err_free:
+ wiphy_free(wiphy);
+ return NULL;
}
EXPORT_SYMBOL(ieee80211_alloc_hw_nm);
@@ -1173,7 +1177,6 @@ void ieee80211_unregister_hw(struct ieee80211_hw *hw)
destroy_workqueue(local->workqueue);
wiphy_unregister(local->hw.wiphy);
- sta_info_stop(local);
ieee80211_wep_free(local);
ieee80211_led_exit(local);
kfree(local->int_scan_req);
diff --git a/net/mac80211/rx.c b/net/mac80211/rx.c
index ed38d8302659..aa238a66ae2e 100644
--- a/net/mac80211/rx.c
+++ b/net/mac80211/rx.c
@@ -3417,7 +3417,7 @@ static void __ieee80211_rx_handle_packet(struct ieee80211_hw *hw,
__le16 fc;
struct ieee80211_rx_data rx;
struct ieee80211_sub_if_data *prev;
- struct sta_info *sta, *tmp, *prev_sta;
+ struct sta_info *sta, *prev_sta;
int err = 0;
fc = ((struct ieee80211_hdr *)skb->data)->frame_control;
@@ -3454,7 +3454,7 @@ static void __ieee80211_rx_handle_packet(struct ieee80211_hw *hw,
if (ieee80211_is_data(fc)) {
prev_sta = NULL;
- for_each_sta_info(local, hdr->addr2, sta, tmp) {
+ for_each_sta_info(local, hdr->addr2, sta) {
if (!prev_sta) {
prev_sta = sta;
continue;
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index 00ca8dcc2bcf..0535bf89e115 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -68,28 +68,7 @@
static int sta_info_hash_del(struct ieee80211_local *local,
struct sta_info *sta)
{
- struct sta_info *s;
-
- s = rcu_dereference_protected(local->sta_hash[STA_HASH(sta->sta.addr)],
- lockdep_is_held(&local->sta_mtx));
- if (!s)
- return -ENOENT;
- if (s == sta) {
- rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)],
- s->hnext);
- return 0;
- }
-
- while (rcu_access_pointer(s->hnext) &&
- rcu_access_pointer(s->hnext) != sta)
- s = rcu_dereference_protected(s->hnext,
- lockdep_is_held(&local->sta_mtx));
- if (rcu_access_pointer(s->hnext)) {
- rcu_assign_pointer(s->hnext, sta->hnext);
- return 0;
- }
-
- return -ENOENT;
+ return rhashtable_remove(&local->sta_hash, &sta->hash_node) ? 0 : -ENOENT;
}
static void __cleanup_single_sta(struct sta_info *sta)
@@ -159,18 +138,8 @@ 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;
- sta = rcu_dereference_check(local->sta_hash[STA_HASH(addr)],
- lockdep_is_held(&local->sta_mtx));
- while (sta) {
- if (sta->sdata == sdata &&
- ether_addr_equal(sta->sta.addr, addr))
- break;
- sta = rcu_dereference_check(sta->hnext,
- lockdep_is_held(&local->sta_mtx));
- }
- return sta;
+ return rhashtable_lookup(&local->sta_hash, addr);
}
/*
@@ -183,17 +152,11 @@ struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata,
struct ieee80211_local *local = sdata->local;
struct sta_info *sta;
- sta = rcu_dereference_check(local->sta_hash[STA_HASH(addr)],
- lockdep_is_held(&local->sta_mtx));
- while (sta) {
- if ((sta->sdata == sdata ||
- (sta->sdata->bss && sta->sdata->bss == sdata->bss)) &&
- ether_addr_equal(sta->sta.addr, addr))
- break;
- sta = rcu_dereference_check(sta->hnext,
- lockdep_is_held(&local->sta_mtx));
- }
- return sta;
+ for_each_sta_info(local, addr, sta)
+ if (sta->sdata == sdata ||
+ (sta->sdata->bss && sta->sdata->bss == sdata->bss))
+ return sta;
+ return NULL;
}
struct sta_info *sta_info_get_by_idx(struct ieee80211_sub_if_data *sdata,
@@ -250,9 +213,7 @@ void sta_info_free(struct ieee80211_local *local, struct sta_info *sta)
static void sta_info_hash_add(struct ieee80211_local *local,
struct sta_info *sta)
{
- lockdep_assert_held(&local->sta_mtx);
- sta->hnext = local->sta_hash[STA_HASH(sta->sta.addr)];
- rcu_assign_pointer(local->sta_hash[STA_HASH(sta->sta.addr)], sta);
+ rhashtable_insert(&local->sta_hash, &sta->hash_node);
}
static void sta_deliver_ps_frames(struct work_struct *wk)
@@ -992,19 +953,45 @@ static void sta_info_cleanup(unsigned long data)
round_jiffies(jiffies + STA_INFO_CLEANUP_INTERVAL));
}
-void sta_info_init(struct ieee80211_local *local)
+#ifdef CONFIG_PROVE_LOCKING
+static int sta_info_mutex_is_held(void *parent)
{
+ struct ieee80211_local *local = parent;
+ return lockdep_is_held(&local->sta_mtx);
+}
+#endif
+
+int sta_info_init(struct ieee80211_local *local)
+{
+ struct rhashtable_params params = {
+ .head_offset = offsetof(struct sta_info, hash_node),
+ .key_offset = offsetof(struct sta_info, sta.addr),
+ .key_len = ETH_ALEN,
+ .hashfn = jhash,
+#ifdef CONFIG_PROVE_LOCKING
+ .mutex_is_held = sta_info_mutex_is_held,
+ .parent = local,
+#endif
+ };
+ int err;
+
+ err = rhashtable_init(&local->sta_hash, ¶ms);
+ if (err)
+ return err;
+
spin_lock_init(&local->tim_lock);
mutex_init(&local->sta_mtx);
INIT_LIST_HEAD(&local->sta_list);
setup_timer(&local->sta_cleanup, sta_info_cleanup,
(unsigned long)local);
+ return 0;
}
void sta_info_stop(struct ieee80211_local *local)
{
del_timer_sync(&local->sta_cleanup);
+ rhashtable_destroy(&local->sta_hash);
}
@@ -1071,13 +1058,13 @@ struct ieee80211_sta *ieee80211_find_sta_by_ifaddr(struct ieee80211_hw *hw,
const u8 *addr,
const u8 *localaddr)
{
- struct sta_info *sta, *nxt;
+ struct sta_info *sta;
/*
* Just return a random station if localaddr is NULL
* ... first in list.
*/
- for_each_sta_info(hw_to_local(hw), addr, sta, nxt) {
+ for_each_sta_info(hw_to_local(hw), addr, sta) {
if (localaddr &&
!ether_addr_equal(sta->sdata->vif.addr, localaddr))
continue;
diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
index 925e68fe64c7..dd8a15e6ede4 100644
--- a/net/mac80211/sta_info.h
+++ b/net/mac80211/sta_info.h
@@ -16,6 +16,7 @@
#include <linux/workqueue.h>
#include <linux/average.h>
#include <linux/etherdevice.h>
+#include <linux/rhashtable.h>
#include "key.h"
/**
@@ -265,7 +266,7 @@ struct ieee80211_tx_latency_stat {
*
* @list: global linked list entry
* @free_list: list entry for keeping track of stations to free
- * @hnext: hash table linked list pointer
+ * @hash_node: hash node for rhashtable
* @local: pointer to the global information
* @sdata: virtual interface this station belongs to
* @ptk: peer keys negotiated with this station, if any
@@ -359,7 +360,7 @@ struct sta_info {
/* General information, mostly static */
struct list_head list, free_list;
struct rcu_head rcu_head;
- struct sta_info __rcu *hnext;
+ struct rhash_head hash_node;
struct ieee80211_local *local;
struct ieee80211_sub_if_data *sdata;
struct ieee80211_key __rcu *gtk[NUM_DEFAULT_KEYS + NUM_DEFAULT_MGMT_KEYS];
@@ -557,10 +558,6 @@ rcu_dereference_protected_tid_tx(struct sta_info *sta, int tid)
lockdep_is_held(&sta->ampdu_mlme.mtx));
}
-#define STA_HASH_SIZE 256
-#define STA_HASH(sta) (sta[5])
-
-
/* Maximum number of frames to buffer per power saving station per AC */
#define STA_MAX_TX_BUFFER 64
@@ -581,28 +578,14 @@ 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);
-static inline
-void for_each_sta_info_type_check(struct ieee80211_local *local,
- const u8 *addr,
- struct sta_info *sta,
- struct sta_info *nxt)
-{
-}
+#define sta_bucket(sh, _a) \
+ rht_dereference_rcu((sh)->tbl, sh)->buckets[rhashtable_hashfn(sh, _a, ETH_ALEN)]
-#define for_each_sta_info(local, _addr, _sta, nxt) \
- for ( /* initialise loop */ \
- _sta = rcu_dereference(local->sta_hash[STA_HASH(_addr)]),\
- nxt = _sta ? rcu_dereference(_sta->hnext) : NULL; \
- /* typecheck */ \
- for_each_sta_info_type_check(local, (_addr), _sta, nxt),\
- /* continue condition */ \
- _sta; \
- /* advance loop */ \
- _sta = nxt, \
- nxt = _sta ? rcu_dereference(_sta->hnext) : NULL \
- ) \
+#define for_each_sta_info(local, _a, _sta) \
+ rht_for_each_entry_rcu(_sta, sta_bucket(&local->sta_hash, (_a)),\
+ hash_node) \
/* compare address and run code only if it matches */ \
- if (ether_addr_equal(_sta->sta.addr, (_addr)))
+ if (ether_addr_equal(_sta->sta.addr, (_a)))
/*
* Get STA info by index, BROKEN!
@@ -637,7 +620,7 @@ int sta_info_destroy_addr_bss(struct ieee80211_sub_if_data *sdata,
void sta_info_recalc_tim(struct sta_info *sta);
-void sta_info_init(struct ieee80211_local *local);
+int sta_info_init(struct ieee80211_local *local);
void sta_info_stop(struct ieee80211_local *local);
/**
diff --git a/net/mac80211/status.c b/net/mac80211/status.c
index e679b7c9b160..f8719cf55a01 100644
--- a/net/mac80211/status.c
+++ b/net/mac80211/status.c
@@ -722,7 +722,7 @@ void ieee80211_tx_status(struct ieee80211_hw *hw, struct sk_buff *skb)
struct ieee80211_supported_band *sband;
struct ieee80211_sub_if_data *sdata;
struct net_device *prev_dev = NULL;
- struct sta_info *sta, *tmp;
+ struct sta_info *sta;
int retry_count;
int rates_idx;
bool send_to_cooked;
@@ -739,7 +739,7 @@ void ieee80211_tx_status(struct ieee80211_hw *hw, struct sk_buff *skb)
sband = local->hw.wiphy->bands[info->band];
fc = hdr->frame_control;
- for_each_sta_info(local, hdr->addr1, sta, tmp) {
+ for_each_sta_info(local, hdr->addr1, sta) {
/* skip wrong virtual interface */
if (!ether_addr_equal(hdr->addr2, sta->sdata->vif.addr))
continue;
--
2.1.4
2015-02-23 19:33 GMT+03:00 Johannes Berg <[email protected]>:
> On Sat, 2015-02-14 at 05:14 +0300, Sergey Ryazanov wrote:
>
>> A nice change! Couple of years ago I did some tests with real sets of
>> MACs and jhash gives a better distribution than usage of a last octet.
>>
>> BTW, why do you use full address and generic jhash? Hashing of two
>> least significant words could be faster. Isn't it?
>
> Well - not sure what you're trying to say? First you're saying jhash()
> was clearly better and then you're saying I shouldn't use it? ;-)
>
In first case, I mean the jhash _algorithm_, which has a better
distribution, in second case I mean the _generic_ jhash() _function_
and express my doubts about its performance. See below.
> Anyway - just using the last two bytes (or even 16-bit words) won't
> cover the case where the locally administered bit is set in an otherwise
> unchanged address, which is getting more common for P2P.
>
> I also don't really see any major drawbacks to hashing it all?
>
I agree that hashing all octets is not a drawback. But the jhash()
function is tailored to the input data of variable length, while we
have a vector of fixed length and appropriate functions. Could we do
the hashing in following way:
u32 sta_info_hash(void *addr, u32 len, u32 seed)
{
u32 *k = addr + 2;
return jhash_1word(*k, seed);
}
structu rhashtable_pararms param = {
...
.hashfn = sta_info_hash,
...
}
or even (to account LA bit):
u32 sta_info_hash(void *addr, u32 len, u32 seed)
{
u32 *k = addr;
return jhash_2words(k[0], k[1], seed);
}
structu rhashtable_pararms param = {
...
.key_len = 8,
.hashfn = sta_info_hash,
...
}
This could save a couple of CPU circles and a couple of bytes in the
output image :)
--
Sergey
On Mon, 2015-02-23 at 23:01 +0100, Johannes Berg wrote:
> On Mon, 2015-02-23 at 22:52 +0100, Johannes Berg wrote:
>
> > We also can't rely on 4-byte alignment though, so perhaps we should do
> > something like
> >
> > u32 sta_info_hash(void *addr, u32 len, u32 seed)
> > {
> > u16 *a = addr;
> >
> > return jhash_3words(a[0], a[1], a[2], seed);
> > }
>
> Or better do
>
> return jhash_2words(addr[0], (addr[1] << 16) | addr[2], seed);
>
> since I have no idea how the missing high 16 bits would behave.
> (we can rely on 2-byte alignment, but not 4-byte)
Actually, we cannot rely on alignment, so we need to do this:
static u32 sta_addr_hash(const void *key, u32 length, u32 seed)
{
return jhash(key, ETH_ALEN, seed);
}
which still generates better code since the compiler can optimise based
on the fixed length.
johannes
On Mon, 2015-02-23 at 22:52 +0100, Johannes Berg wrote:
> We also can't rely on 4-byte alignment though, so perhaps we should do
> something like
>
> u32 sta_info_hash(void *addr, u32 len, u32 seed)
> {
> u16 *a = addr;
>
> return jhash_3words(a[0], a[1], a[2], seed);
> }
Or better do
return jhash_2words(addr[0], (addr[1] << 16) | addr[2], seed);
since I have no idea how the missing high 16 bits would behave.
(we can rely on 2-byte alignment, but not 4-byte)
johannes
On 02/13/2015 01:47 PM, Johannes Berg wrote:
> From: Johannes Berg <[email protected]>
>
> We currently have a hand-rolled table with 256 entries and are
> using the last byte of the MAC address as the hash. This hash
> is obviously very fast, but collisions are easily created and
> we waste a lot of space in the common case of just connecting
> as a client to an AP where we just have a single station. The
> other common case of an AP is also suboptimal due to the size
> of the hash table and the ease of causing collisions.
>
> Convert all of this to use rhashtable with jhash, which gives
> us the advantage of a far better hash function (with random
> perturbation to avoid hash collision attacks) and of course
> that the hash table grows and shrinks dynamically with chain
> length, improving both cases above.
Oooh, maybe finally time to mix local addr with peer addr to
make lots of vifs connected to same AP hash well too? :)
Thanks,
Ben
--
Ben Greear <[email protected]>
Candela Technologies Inc http://www.candelatech.com
On Sat, 2015-02-14 at 05:14 +0300, Sergey Ryazanov wrote:
> A nice change! Couple of years ago I did some tests with real sets of
> MACs and jhash gives a better distribution than usage of a last octet.
>
> BTW, why do you use full address and generic jhash? Hashing of two
> least significant words could be faster. Isn't it?
Well - not sure what you're trying to say? First you're saying jhash()
was clearly better and then you're saying I shouldn't use it? ;-)
Anyway - just using the last two bytes (or even 16-bit words) won't
cover the case where the locally administered bit is set in an otherwise
unchanged address, which is getting more common for P2P.
I also don't really see any major drawbacks to hashing it all?
johannes
On Tue, 2015-02-24 at 00:26 +0300, Sergey Ryazanov wrote:
> > Well - not sure what you're trying to say? First you're saying jhash()
> > was clearly better and then you're saying I shouldn't use it? ;-)
> >
> In first case, I mean the jhash _algorithm_, which has a better
> distribution, in second case I mean the _generic_ jhash() _function_
> and express my doubts about its performance. See below.
Ah.
> I agree that hashing all octets is not a drawback. But the jhash()
> function is tailored to the input data of variable length, while we
> have a vector of fixed length and appropriate functions. Could we do
> the hashing in following way:
>
> u32 sta_info_hash(void *addr, u32 len, u32 seed)
> {
> u32 *k = addr + 2;
> return jhash_1word(*k, seed);
> }
This would work, but without the LA bit obviously.
> or even (to account LA bit):
>
> u32 sta_info_hash(void *addr, u32 len, u32 seed)
> {
> u32 *k = addr;
> return jhash_2words(k[0], k[1], seed);
> }
This won't exactly work as there's no known padding there so that k[1]
accesses invalid data, but I get the point. It should then be
> This could save a couple of CPU circles and a couple of bytes in the
> output image :)
I don't think it would save bytes? The jhash function is common after
all. Ah, but it's an inline, so it would be generated here.
We also can't rely on 4-byte alignment though, so perhaps we should do
something like
u32 sta_info_hash(void *addr, u32 len, u32 seed)
{
u16 *a = addr;
return jhash_3words(a[0], a[1], a[2], seed);
}
instead? Not sure what effect that has on jhash though if we don't have
anything in the high 16 bits.
johannes
2015-02-14 0:47 GMT+03:00 Johannes Berg <[email protected]>:
> We currently have a hand-rolled table with 256 entries and are
> using the last byte of the MAC address as the hash. This hash
> is obviously very fast, but collisions are easily created and
> we waste a lot of space in the common case of just connecting
> as a client to an AP where we just have a single station. The
> other common case of an AP is also suboptimal due to the size
> of the hash table and the ease of causing collisions.
>
> Convert all of this to use rhashtable with jhash, which gives
> us the advantage of a far better hash function (with random
> perturbation to avoid hash collision attacks) and of course
> that the hash table grows and shrinks dynamically with chain
> length, improving both cases above.
>
A nice change! Couple of years ago I did some tests with real sets of
MACs and jhash gives a better distribution than usage of a last octet.
BTW, why do you use full address and generic jhash? Hashing of two
least significant words could be faster. Isn't it?
--
Sergey
2015-02-24 1:07 GMT+03:00 Johannes Berg <[email protected]>:
> On Mon, 2015-02-23 at 23:01 +0100, Johannes Berg wrote:
>> On Mon, 2015-02-23 at 22:52 +0100, Johannes Berg wrote:
>>
>> > We also can't rely on 4-byte alignment though, so perhaps we should do
>> > something like
>> >
>> > u32 sta_info_hash(void *addr, u32 len, u32 seed)
>> > {
>> > u16 *a = addr;
>> >
>> > return jhash_3words(a[0], a[1], a[2], seed);
>> > }
>>
>> Or better do
>>
>> return jhash_2words(addr[0], (addr[1] << 16) | addr[2], seed);
>>
>> since I have no idea how the missing high 16 bits would behave.
>> (we can rely on 2-byte alignment, but not 4-byte)
>
> Actually, we cannot rely on alignment, so we need to do this:
>
> static u32 sta_addr_hash(const void *key, u32 length, u32 seed)
> {
> return jhash(key, ETH_ALEN, seed);
> }
>
> which still generates better code since the compiler can optimise based
> on the fixed length.
>
Nice catch!
--
Sergey
On Fri, 2015-02-13 at 14:13 -0800, Ben Greear wrote:
> Oooh, maybe finally time to mix local addr with peer addr to
> make lots of vifs connected to same AP hash well too? :)
As we discussed before, mixing it in isn't actually possible. Your patch
will get easier to maintain (if you also convert it) though :)
johannes