summaryrefslogtreecommitdiff
path: root/net/mac80211/sta_info.c
diff options
context:
space:
mode:
authorJohannes Berg <johannes.berg@intel.com>2015-02-13 21:55:15 +0100
committerJohannes Berg <johannes.berg@intel.com>2015-04-01 10:06:26 +0200
commit7bedd0cfad4e122bc0ddaf3fc955a38c88c95d35 (patch)
treef156540ff672dec031e81a64fc60796dd34ea867 /net/mac80211/sta_info.c
parent9911674fcf1f239ff3c87e56177c4826e33dfd95 (diff)
mac80211: use rhashtable for station table
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. Use a specialised hash function (using jhash, but with fixed length) to achieve better compiler optimisation as suggested by Sergey Ryazanov. Signed-off-by: Johannes Berg <johannes.berg@intel.com>
Diffstat (limited to 'net/mac80211/sta_info.c')
-rw-r--r--net/mac80211/sta_info.c103
1 files changed, 52 insertions, 51 deletions
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index aacaa1a85e63..81cc499fa4a9 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -64,32 +64,20 @@
* freed before they are done using it.
*/
+static const struct rhashtable_params sta_rht_params = {
+ .nelem_hint = 3, /* start small */
+ .head_offset = offsetof(struct sta_info, hash_node),
+ .key_offset = offsetof(struct sta_info, sta.addr),
+ .key_len = ETH_ALEN,
+ .hashfn = sta_addr_hash,
+};
+
/* Caller must hold local->sta_mtx */
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_fast(&local->sta_hash, &sta->hash_node,
+ sta_rht_params);
}
static void __cleanup_single_sta(struct sta_info *sta)
@@ -159,18 +147,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_fast(&local->sta_hash, addr, sta_rht_params);
}
/*
@@ -182,18 +160,24 @@ struct sta_info *sta_info_get_bss(struct ieee80211_sub_if_data *sdata,
{
struct ieee80211_local *local = sdata->local;
struct sta_info *sta;
+ struct rhash_head *tmp;
+ const struct bucket_table *tbl;
- 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));
+ rcu_read_lock();
+ tbl = rht_dereference_rcu(local->sta_hash.tbl, &local->sta_hash);
+
+ for_each_sta_info(local, tbl, addr, sta, tmp) {
+ if (sta->sdata == sdata ||
+ (sta->sdata->bss && sta->sdata->bss == sdata->bss)) {
+ rcu_read_unlock();
+ /* this is safe as the caller must already hold
+ * another rcu read section or the mutex
+ */
+ return sta;
+ }
}
- return sta;
+ rcu_read_unlock();
+ return NULL;
}
struct sta_info *sta_info_get_by_idx(struct ieee80211_sub_if_data *sdata,
@@ -242,9 +226,8 @@ 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_fast(&local->sta_hash, &sta->hash_node,
+ sta_rht_params);
}
static void sta_deliver_ps_frames(struct work_struct *wk)
@@ -948,19 +931,32 @@ static void sta_info_cleanup(unsigned long data)
round_jiffies(jiffies + STA_INFO_CLEANUP_INTERVAL));
}
-void sta_info_init(struct ieee80211_local *local)
+u32 sta_addr_hash(const void *key, u32 length, u32 seed)
+{
+ return jhash(key, ETH_ALEN, seed);
+}
+
+int sta_info_init(struct ieee80211_local *local)
{
+ int err;
+
+ err = rhashtable_init(&local->sta_hash, &sta_rht_params);
+ 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);
}
@@ -1024,16 +1020,21 @@ void ieee80211_sta_expire(struct ieee80211_sub_if_data *sdata,
}
struct ieee80211_sta *ieee80211_find_sta_by_ifaddr(struct ieee80211_hw *hw,
- const u8 *addr,
- const u8 *localaddr)
+ const u8 *addr,
+ const u8 *localaddr)
{
- struct sta_info *sta, *nxt;
+ struct ieee80211_local *local = hw_to_local(hw);
+ struct sta_info *sta;
+ struct rhash_head *tmp;
+ const struct bucket_table *tbl;
+
+ tbl = rht_dereference_rcu(local->sta_hash.tbl, &local->sta_hash);
/*
* 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(local, tbl, addr, sta, tmp) {
if (localaddr &&
!ether_addr_equal(sta->sdata->vif.addr, localaddr))
continue;