From 2bdaf386f99c4a82788812e583ff59c6714ae4d6 Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Sun, 28 Feb 2016 20:03:56 -0500 Subject: mac80211: mesh: move path tables into if_mesh The mesh path and mesh gate hashtables are global, containing all of the mpaths for every mesh interface, but the paths are all tied logically to a single interface. The common case is just a single mesh interface, so optimize for that by moving the global hashtable into the per-interface struct. Doing so allows us to drop sdata pointer comparisons inside the lookups and also saves a few bytes of BSS and data. Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/mesh_pathtbl.c | 181 +++++++++++++++++++------------------------- 1 file changed, 79 insertions(+), 102 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index 2ba7aa56b11c..0508b37b0471 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -40,36 +40,24 @@ struct mpath_node { struct mesh_path *mpath; }; -static struct mesh_table __rcu *mesh_paths; -static struct mesh_table __rcu *mpp_paths; /* Store paths for MPP&MAP */ - -int mesh_paths_generation; -int mpp_paths_generation; - -/* This lock will have the grow table function as writer and add / delete nodes - * as readers. RCU provides sufficient protection only when reading the table - * (i.e. doing lookups). Adding or adding or removing nodes requires we take - * the read lock or we risk operating on an old table. The write lock is only - * needed when modifying the number of buckets a table. - */ -static DEFINE_RWLOCK(pathtbl_resize_lock); - - static inline struct mesh_table *resize_dereference_paths( + struct ieee80211_sub_if_data *sdata, struct mesh_table __rcu *table) { return rcu_dereference_protected(table, - lockdep_is_held(&pathtbl_resize_lock)); + lockdep_is_held(&sdata->u.mesh.pathtbl_resize_lock)); } -static inline struct mesh_table *resize_dereference_mesh_paths(void) +static inline struct mesh_table *resize_dereference_mesh_paths( + struct ieee80211_sub_if_data *sdata) { - return resize_dereference_paths(mesh_paths); + return resize_dereference_paths(sdata, sdata->u.mesh.mesh_paths); } -static inline struct mesh_table *resize_dereference_mpp_paths(void) +static inline struct mesh_table *resize_dereference_mpp_paths( + struct ieee80211_sub_if_data *sdata) { - return resize_dereference_paths(mpp_paths); + return resize_dereference_paths(sdata, sdata->u.mesh.mpp_paths); } /* @@ -346,8 +334,7 @@ static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst, bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)]; hlist_for_each_entry_rcu(node, bucket, list) { mpath = node->mpath; - if (mpath->sdata == sdata && - ether_addr_equal(dst, mpath->dst)) { + if (ether_addr_equal(dst, mpath->dst)) { if (mpath_expired(mpath)) { spin_lock_bh(&mpath->state_lock); mpath->flags &= ~MESH_PATH_ACTIVE; @@ -371,13 +358,15 @@ static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst, struct mesh_path * mesh_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) { - return mpath_lookup(rcu_dereference(mesh_paths), dst, sdata); + return mpath_lookup(rcu_dereference(sdata->u.mesh.mesh_paths), dst, + sdata); } struct mesh_path * mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) { - return mpath_lookup(rcu_dereference(mpp_paths), dst, sdata); + return mpath_lookup(rcu_dereference(sdata->u.mesh.mpp_paths), dst, + sdata); } @@ -393,14 +382,12 @@ mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) struct mesh_path * mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) { - struct mesh_table *tbl = rcu_dereference(mesh_paths); + struct mesh_table *tbl = rcu_dereference(sdata->u.mesh.mesh_paths); struct mpath_node *node; int i; int j = 0; for_each_mesh_entry(tbl, node, i) { - if (sdata && node->mpath->sdata != sdata) - continue; if (j++ == idx) { if (mpath_expired(node->mpath)) { spin_lock_bh(&node->mpath->state_lock); @@ -426,14 +413,12 @@ mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) struct mesh_path * mpp_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) { - struct mesh_table *tbl = rcu_dereference(mpp_paths); + struct mesh_table *tbl = rcu_dereference(sdata->u.mesh.mpp_paths); struct mpath_node *node; int i; int j = 0; for_each_mesh_entry(tbl, node, i) { - if (sdata && node->mpath->sdata != sdata) - continue; if (j++ == idx) return node->mpath; } @@ -452,7 +437,7 @@ int mesh_path_add_gate(struct mesh_path *mpath) int err; rcu_read_lock(); - tbl = rcu_dereference(mesh_paths); + tbl = rcu_dereference(mpath->sdata->u.mesh.mesh_paths); hlist_for_each_entry_rcu(gate, tbl->known_gates, list) if (gate->mpath == mpath) { @@ -550,8 +535,8 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0) return ERR_PTR(-ENOSPC); - read_lock_bh(&pathtbl_resize_lock); - tbl = resize_dereference_mesh_paths(); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + tbl = resize_dereference_mesh_paths(sdata); hash_idx = mesh_table_hash(dst, sdata, tbl); bucket = &tbl->hash_buckets[hash_idx]; @@ -560,8 +545,7 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, hlist_for_each_entry(node, bucket, list) { mpath = node->mpath; - if (mpath->sdata == sdata && - ether_addr_equal(dst, mpath->dst)) + if (ether_addr_equal(dst, mpath->dst)) goto found; } @@ -592,7 +576,7 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, MEAN_CHAIN_LEN * (tbl->hash_mask + 1)) grow = 1; - mesh_paths_generation++; + sdata->u.mesh.mesh_paths_generation++; if (grow) { set_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags); @@ -601,7 +585,7 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, mpath = new_mpath; found: spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); return mpath; err_node_alloc: @@ -609,7 +593,7 @@ err_node_alloc: err_path_alloc: atomic_dec(&sdata->u.mesh.mpaths); spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); return ERR_PTR(err); } @@ -620,12 +604,12 @@ static void mesh_table_free_rcu(struct rcu_head *rcu) mesh_table_free(tbl, false); } -void mesh_mpath_table_grow(void) +void mesh_mpath_table_grow(struct ieee80211_sub_if_data *sdata) { struct mesh_table *oldtbl, *newtbl; - write_lock_bh(&pathtbl_resize_lock); - oldtbl = resize_dereference_mesh_paths(); + write_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + oldtbl = resize_dereference_mesh_paths(sdata); newtbl = mesh_table_alloc(oldtbl->size_order + 1); if (!newtbl) goto out; @@ -633,20 +617,20 @@ void mesh_mpath_table_grow(void) __mesh_table_free(newtbl); goto out; } - rcu_assign_pointer(mesh_paths, newtbl); + rcu_assign_pointer(sdata->u.mesh.mesh_paths, newtbl); call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu); out: - write_unlock_bh(&pathtbl_resize_lock); + write_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); } -void mesh_mpp_table_grow(void) +void mesh_mpp_table_grow(struct ieee80211_sub_if_data *sdata) { struct mesh_table *oldtbl, *newtbl; - write_lock_bh(&pathtbl_resize_lock); - oldtbl = resize_dereference_mpp_paths(); + write_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + oldtbl = resize_dereference_mpp_paths(sdata); newtbl = mesh_table_alloc(oldtbl->size_order + 1); if (!newtbl) goto out; @@ -654,11 +638,11 @@ void mesh_mpp_table_grow(void) __mesh_table_free(newtbl); goto out; } - rcu_assign_pointer(mpp_paths, newtbl); + rcu_assign_pointer(sdata->u.mesh.mpp_paths, newtbl); call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu); out: - write_unlock_bh(&pathtbl_resize_lock); + write_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); } int mpp_path_add(struct ieee80211_sub_if_data *sdata, @@ -690,7 +674,7 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, if (!new_node) goto err_node_alloc; - read_lock_bh(&pathtbl_resize_lock); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); memcpy(new_mpath->dst, dst, ETH_ALEN); memcpy(new_mpath->mpp, mpp, ETH_ALEN); new_mpath->sdata = sdata; @@ -701,7 +685,7 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, new_mpath->exp_time = jiffies; spin_lock_init(&new_mpath->state_lock); - tbl = resize_dereference_mpp_paths(); + tbl = resize_dereference_mpp_paths(sdata); hash_idx = mesh_table_hash(dst, sdata, tbl); bucket = &tbl->hash_buckets[hash_idx]; @@ -711,8 +695,7 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, err = -EEXIST; hlist_for_each_entry(node, bucket, list) { mpath = node->mpath; - if (mpath->sdata == sdata && - ether_addr_equal(dst, mpath->dst)) + if (ether_addr_equal(dst, mpath->dst)) goto err_exists; } @@ -722,9 +705,9 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, grow = 1; spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - mpp_paths_generation++; + sdata->u.mesh.mpp_paths_generation++; if (grow) { set_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags); @@ -734,7 +717,7 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, err_exists: spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); kfree(new_node); err_node_alloc: kfree(new_mpath); @@ -761,7 +744,7 @@ void mesh_plink_broken(struct sta_info *sta) int i; rcu_read_lock(); - tbl = rcu_dereference(mesh_paths); + tbl = rcu_dereference(sdata->u.mesh.mesh_paths); for_each_mesh_entry(tbl, node, i) { mpath = node->mpath; if (rcu_access_pointer(mpath->next_hop) == sta && @@ -819,14 +802,15 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node) */ void mesh_path_flush_by_nexthop(struct sta_info *sta) { + struct ieee80211_sub_if_data *sdata = sta->sdata; struct mesh_table *tbl; struct mesh_path *mpath; struct mpath_node *node; int i; rcu_read_lock(); - read_lock_bh(&pathtbl_resize_lock); - tbl = resize_dereference_mesh_paths(); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + tbl = resize_dereference_mesh_paths(sdata); for_each_mesh_entry(tbl, node, i) { mpath = node->mpath; if (rcu_access_pointer(mpath->next_hop) == sta) { @@ -835,7 +819,7 @@ void mesh_path_flush_by_nexthop(struct sta_info *sta) spin_unlock(&tbl->hashwlock[i]); } } - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); rcu_read_unlock(); } @@ -848,8 +832,8 @@ static void mpp_flush_by_proxy(struct ieee80211_sub_if_data *sdata, int i; rcu_read_lock(); - read_lock_bh(&pathtbl_resize_lock); - tbl = resize_dereference_mpp_paths(); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + tbl = resize_dereference_mpp_paths(sdata); for_each_mesh_entry(tbl, node, i) { mpp = node->mpath; if (ether_addr_equal(mpp->mpp, proxy)) { @@ -858,7 +842,7 @@ static void mpp_flush_by_proxy(struct ieee80211_sub_if_data *sdata, spin_unlock(&tbl->hashwlock[i]); } } - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); rcu_read_unlock(); } @@ -872,8 +856,6 @@ static void table_flush_by_iface(struct mesh_table *tbl, WARN_ON(!rcu_read_lock_held()); for_each_mesh_entry(tbl, node, i) { mpath = node->mpath; - if (mpath->sdata != sdata) - continue; spin_lock_bh(&tbl->hashwlock[i]); __mesh_path_del(tbl, node); spin_unlock_bh(&tbl->hashwlock[i]); @@ -893,12 +875,12 @@ void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata) struct mesh_table *tbl; rcu_read_lock(); - read_lock_bh(&pathtbl_resize_lock); - tbl = resize_dereference_mesh_paths(); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + tbl = resize_dereference_mesh_paths(sdata); table_flush_by_iface(tbl, sdata); - tbl = resize_dereference_mpp_paths(); + tbl = resize_dereference_mpp_paths(sdata); table_flush_by_iface(tbl, sdata); - read_unlock_bh(&pathtbl_resize_lock); + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); rcu_read_unlock(); } @@ -922,15 +904,14 @@ static int table_path_del(struct mesh_table __rcu *rcu_tbl, int hash_idx; int err = 0; - tbl = resize_dereference_paths(rcu_tbl); + tbl = resize_dereference_paths(sdata, rcu_tbl); hash_idx = mesh_table_hash(addr, sdata, tbl); bucket = &tbl->hash_buckets[hash_idx]; spin_lock(&tbl->hashwlock[hash_idx]); hlist_for_each_entry(node, bucket, list) { mpath = node->mpath; - if (mpath->sdata == sdata && - ether_addr_equal(addr, mpath->dst)) { + if (ether_addr_equal(addr, mpath->dst)) { __mesh_path_del(tbl, node); goto enddel; } @@ -957,10 +938,10 @@ int mesh_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr) /* flush relevant mpp entries first */ mpp_flush_by_proxy(sdata, addr); - read_lock_bh(&pathtbl_resize_lock); - err = table_path_del(mesh_paths, sdata, addr); - mesh_paths_generation++; - read_unlock_bh(&pathtbl_resize_lock); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + err = table_path_del(sdata->u.mesh.mesh_paths, sdata, addr); + sdata->u.mesh.mesh_paths_generation++; + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); return err; } @@ -977,10 +958,10 @@ static int mpp_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr) { int err = 0; - read_lock_bh(&pathtbl_resize_lock); - err = table_path_del(mpp_paths, sdata, addr); - mpp_paths_generation++; - read_unlock_bh(&pathtbl_resize_lock); + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); + err = table_path_del(sdata->u.mesh.mpp_paths, sdata, addr); + sdata->u.mesh.mpp_paths_generation++; + read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); return err; } @@ -1020,7 +1001,7 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) struct hlist_head *known_gates; rcu_read_lock(); - tbl = rcu_dereference(mesh_paths); + tbl = rcu_dereference(sdata->u.mesh.mesh_paths); known_gates = tbl->known_gates; rcu_read_unlock(); @@ -1028,9 +1009,6 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) return -EHOSTUNREACH; hlist_for_each_entry_rcu(gate, known_gates, list) { - if (gate->mpath->sdata != sdata) - continue; - if (gate->mpath->flags & MESH_PATH_ACTIVE) { mpath_dbg(sdata, "Forwarding to %pM\n", gate->mpath->dst); mesh_path_move_to_queue(gate->mpath, from_mpath, copy); @@ -1043,11 +1021,10 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) } } - hlist_for_each_entry_rcu(gate, known_gates, list) - if (gate->mpath->sdata == sdata) { - mpath_dbg(sdata, "Sending to %pM\n", gate->mpath->dst); - mesh_path_tx_pending(gate->mpath); - } + hlist_for_each_entry_rcu(gate, known_gates, list) { + mpath_dbg(sdata, "Sending to %pM\n", gate->mpath->dst); + mesh_path_tx_pending(gate->mpath); + } return (from_mpath == mpath) ? -EHOSTUNREACH : 0; } @@ -1136,7 +1113,7 @@ static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl) return 0; } -int mesh_pathtbl_init(void) +int mesh_pathtbl_init(struct ieee80211_sub_if_data *sdata) { struct mesh_table *tbl_path, *tbl_mpp; int ret; @@ -1168,9 +1145,11 @@ int mesh_pathtbl_init(void) } INIT_HLIST_HEAD(tbl_mpp->known_gates); + rwlock_init(&sdata->u.mesh.pathtbl_resize_lock); + /* Need no locking since this is during init */ - RCU_INIT_POINTER(mesh_paths, tbl_path); - RCU_INIT_POINTER(mpp_paths, tbl_mpp); + RCU_INIT_POINTER(sdata->u.mesh.mesh_paths, tbl_path); + RCU_INIT_POINTER(sdata->u.mesh.mpp_paths, tbl_mpp); return 0; @@ -1189,33 +1168,31 @@ void mesh_path_expire(struct ieee80211_sub_if_data *sdata) int i; rcu_read_lock(); - tbl = rcu_dereference(mesh_paths); + tbl = rcu_dereference(sdata->u.mesh.mesh_paths); for_each_mesh_entry(tbl, node, i) { - if (node->mpath->sdata != sdata) - continue; mpath = node->mpath; if ((!(mpath->flags & MESH_PATH_RESOLVING)) && (!(mpath->flags & MESH_PATH_FIXED)) && time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) - mesh_path_del(mpath->sdata, mpath->dst); + mesh_path_del(sdata, mpath->dst); } - tbl = rcu_dereference(mpp_paths); + tbl = rcu_dereference(sdata->u.mesh.mpp_paths); for_each_mesh_entry(tbl, node, i) { - if (node->mpath->sdata != sdata) - continue; mpath = node->mpath; if ((!(mpath->flags & MESH_PATH_FIXED)) && time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) - mpp_path_del(mpath->sdata, mpath->dst); + mpp_path_del(sdata, mpath->dst); } rcu_read_unlock(); } -void mesh_pathtbl_unregister(void) +void mesh_pathtbl_unregister(struct ieee80211_sub_if_data *sdata) { /* no need for locking during exit path */ - mesh_table_free(rcu_dereference_protected(mesh_paths, 1), true); - mesh_table_free(rcu_dereference_protected(mpp_paths, 1), true); + mesh_table_free(rcu_dereference_protected(sdata->u.mesh.mesh_paths, 1), + true); + mesh_table_free(rcu_dereference_protected(sdata->u.mesh.mpp_paths, 1), + true); } -- cgit v1.2.3 From 443954815b63b36f09623d74170520e6554f5fac Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Sun, 28 Feb 2016 20:03:57 -0500 Subject: mac80211: mesh: don't hash sdata in mpath tables Now that the sdata pointer is the same for all entries of a path table, hashing it is pointless, so hash only the address. Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/mesh_pathtbl.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index 0508b37b0471..fc3cc350df8c 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -177,12 +177,10 @@ errcopy: return -ENOMEM; } -static u32 mesh_table_hash(const u8 *addr, struct ieee80211_sub_if_data *sdata, - struct mesh_table *tbl) +static u32 mesh_table_hash(const u8 *addr, struct mesh_table *tbl) { - /* Use last four bytes of hw addr and interface index as hash index */ - return jhash_2words(*(u32 *)(addr+2), sdata->dev->ifindex, - tbl->hash_rnd) & tbl->hash_mask; + /* Use last four bytes of hw addr as hash index */ + return jhash_1word(*(u32 *)(addr+2), tbl->hash_rnd) & tbl->hash_mask; } @@ -331,7 +329,7 @@ static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst, struct hlist_head *bucket; struct mpath_node *node; - bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)]; + bucket = &tbl->hash_buckets[mesh_table_hash(dst, tbl)]; hlist_for_each_entry_rcu(node, bucket, list) { mpath = node->mpath; if (ether_addr_equal(dst, mpath->dst)) { @@ -538,7 +536,7 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); tbl = resize_dereference_mesh_paths(sdata); - hash_idx = mesh_table_hash(dst, sdata, tbl); + hash_idx = mesh_table_hash(dst, tbl); bucket = &tbl->hash_buckets[hash_idx]; spin_lock(&tbl->hashwlock[hash_idx]); @@ -687,7 +685,7 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, tbl = resize_dereference_mpp_paths(sdata); - hash_idx = mesh_table_hash(dst, sdata, tbl); + hash_idx = mesh_table_hash(dst, tbl); bucket = &tbl->hash_buckets[hash_idx]; spin_lock(&tbl->hashwlock[hash_idx]); @@ -905,7 +903,7 @@ static int table_path_del(struct mesh_table __rcu *rcu_tbl, int err = 0; tbl = resize_dereference_paths(sdata, rcu_tbl); - hash_idx = mesh_table_hash(addr, sdata, tbl); + hash_idx = mesh_table_hash(addr, tbl); bucket = &tbl->hash_buckets[hash_idx]; spin_lock(&tbl->hashwlock[hash_idx]); @@ -1107,7 +1105,7 @@ static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl) node = hlist_entry(p, struct mpath_node, list); mpath = node->mpath; new_node->mpath = mpath; - hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl); + hash_idx = mesh_table_hash(mpath->dst, newtbl); hlist_add_head(&new_node->list, &newtbl->hash_buckets[hash_idx]); return 0; -- cgit v1.2.3 From b15dc38b9817729d3d4962f8c84bbda0eccb3532 Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Sun, 28 Feb 2016 20:03:58 -0500 Subject: mac80211: mesh: factor out common mesh path allocation code Remove duplicate code to allocate and initialize a mesh path or mesh proxy path. Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/mesh_pathtbl.c | 51 +++++++++++++++++++++++++-------------------- 1 file changed, 28 insertions(+), 23 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index fc3cc350df8c..4794240e8f94 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -501,6 +501,31 @@ int mesh_gate_num(struct ieee80211_sub_if_data *sdata) return sdata->u.mesh.num_gates; } +static +struct mesh_path *mesh_path_new(struct ieee80211_sub_if_data *sdata, + const u8 *dst, gfp_t gfp_flags) +{ + struct mesh_path *new_mpath; + + new_mpath = kzalloc(sizeof(struct mesh_path), gfp_flags); + if (!new_mpath) + return NULL; + + memcpy(new_mpath->dst, dst, ETH_ALEN); + eth_broadcast_addr(new_mpath->rann_snd_addr); + new_mpath->is_root = false; + new_mpath->sdata = sdata; + new_mpath->flags = 0; + skb_queue_head_init(&new_mpath->frame_queue); + new_mpath->timer.data = (unsigned long) new_mpath; + new_mpath->timer.function = mesh_path_timer; + new_mpath->exp_time = jiffies; + spin_lock_init(&new_mpath->state_lock); + init_timer(&new_mpath->timer); + + return new_mpath; +} + /** * mesh_path_add - allocate and add a new path to the mesh path table * @dst: destination address of the path (ETH_ALEN length) @@ -548,7 +573,7 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, } err = -ENOMEM; - new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC); + new_mpath = mesh_path_new(sdata, dst, GFP_ATOMIC); if (!new_mpath) goto err_path_alloc; @@ -556,19 +581,7 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, if (!new_node) goto err_node_alloc; - memcpy(new_mpath->dst, dst, ETH_ALEN); - eth_broadcast_addr(new_mpath->rann_snd_addr); - new_mpath->is_root = false; - new_mpath->sdata = sdata; - new_mpath->flags = 0; - skb_queue_head_init(&new_mpath->frame_queue); new_node->mpath = new_mpath; - new_mpath->timer.data = (unsigned long) new_mpath; - new_mpath->timer.function = mesh_path_timer; - new_mpath->exp_time = jiffies; - spin_lock_init(&new_mpath->state_lock); - init_timer(&new_mpath->timer); - hlist_add_head_rcu(&new_node->list, bucket); if (atomic_inc_return(&tbl->entries) >= MEAN_CHAIN_LEN * (tbl->hash_mask + 1)) @@ -664,7 +677,7 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, return -ENOTSUPP; err = -ENOMEM; - new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC); + new_mpath = mesh_path_new(sdata, dst, GFP_ATOMIC); if (!new_mpath) goto err_path_alloc; @@ -672,17 +685,9 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, if (!new_node) goto err_node_alloc; - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - memcpy(new_mpath->dst, dst, ETH_ALEN); memcpy(new_mpath->mpp, mpp, ETH_ALEN); - new_mpath->sdata = sdata; - new_mpath->flags = 0; - skb_queue_head_init(&new_mpath->frame_queue); new_node->mpath = new_mpath; - init_timer(&new_mpath->timer); - new_mpath->exp_time = jiffies; - spin_lock_init(&new_mpath->state_lock); - + read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); tbl = resize_dereference_mpp_paths(sdata); hash_idx = mesh_table_hash(dst, tbl); -- cgit v1.2.3 From 947c2a0eccec29fcd30e717787e65792b1e607ed Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Sun, 28 Feb 2016 20:03:59 -0500 Subject: mac80211: mesh: embed known gates list in struct mesh_path The mesh path table uses a struct mesh_node in its hlists in order to support a resizable hash table: the mesh_node provides an indirection to the actual mesh path so that two different bucket lists can point to the same path entry. However, for the known gates list, we don't need this indirection because there is ever only one list. So we can just embed the hlist_node in the mesh path itself, which simplifies things a bit and saves a linear search whenever we need to find an item in the list. Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/mesh.h | 1 + net/mac80211/mesh_pathtbl.c | 100 +++++++++++++++++++------------------------- 2 files changed, 45 insertions(+), 56 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h index 601992b6cd8a..f3cc3917e048 100644 --- a/net/mac80211/mesh.h +++ b/net/mac80211/mesh.h @@ -105,6 +105,7 @@ enum mesh_deferred_task_flags { struct mesh_path { u8 dst[ETH_ALEN]; u8 mpp[ETH_ALEN]; /* used for MPP or MAP */ + struct hlist_node gate_list; struct ieee80211_sub_if_data *sdata; struct sta_info __rcu *next_hop; struct timer_list timer; diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index 4794240e8f94..e4daf4b94eaf 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -119,10 +119,18 @@ static void mesh_table_free(struct mesh_table *tbl, bool free_leafs) { struct hlist_head *mesh_hash; struct hlist_node *p, *q; - struct mpath_node *gate; + struct mesh_path *gate; int i; mesh_hash = tbl->hash_buckets; + if (free_leafs) { + spin_lock_bh(&tbl->gates_lock); + hlist_for_each_entry_safe(gate, q, + tbl->known_gates, gate_list) + hlist_del(&gate->gate_list); + kfree(tbl->known_gates); + spin_unlock_bh(&tbl->gates_lock); + } for (i = 0; i <= tbl->hash_mask; i++) { spin_lock_bh(&tbl->hashwlock[i]); hlist_for_each_safe(p, q, &mesh_hash[i]) { @@ -131,16 +139,6 @@ static void mesh_table_free(struct mesh_table *tbl, bool free_leafs) } spin_unlock_bh(&tbl->hashwlock[i]); } - if (free_leafs) { - spin_lock_bh(&tbl->gates_lock); - hlist_for_each_entry_safe(gate, q, - tbl->known_gates, list) { - hlist_del(&gate->list); - kfree(gate); - } - kfree(tbl->known_gates); - spin_unlock_bh(&tbl->gates_lock); - } __mesh_table_free(tbl); } @@ -431,30 +429,26 @@ mpp_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) int mesh_path_add_gate(struct mesh_path *mpath) { struct mesh_table *tbl; - struct mpath_node *gate, *new_gate; int err; rcu_read_lock(); tbl = rcu_dereference(mpath->sdata->u.mesh.mesh_paths); - hlist_for_each_entry_rcu(gate, tbl->known_gates, list) - if (gate->mpath == mpath) { - err = -EEXIST; - goto err_rcu; - } - - new_gate = kzalloc(sizeof(struct mpath_node), GFP_ATOMIC); - if (!new_gate) { - err = -ENOMEM; + spin_lock_bh(&mpath->state_lock); + if (mpath->is_gate) { + err = -EEXIST; + spin_unlock_bh(&mpath->state_lock); goto err_rcu; } - mpath->is_gate = true; mpath->sdata->u.mesh.num_gates++; - new_gate->mpath = mpath; - spin_lock_bh(&tbl->gates_lock); - hlist_add_head_rcu(&new_gate->list, tbl->known_gates); - spin_unlock_bh(&tbl->gates_lock); + + spin_lock(&tbl->gates_lock); + hlist_add_head_rcu(&mpath->gate_list, tbl->known_gates); + spin_unlock(&tbl->gates_lock); + + spin_unlock_bh(&mpath->state_lock); + mpath_dbg(mpath->sdata, "Mesh path: Recorded new gate: %pM. %d known gates\n", mpath->dst, mpath->sdata->u.mesh.num_gates); @@ -468,28 +462,22 @@ err_rcu: * mesh_gate_del - remove a mesh gate from the list of known gates * @tbl: table which holds our list of known gates * @mpath: gate mpath - * - * Locking: must be called inside rcu_read_lock() section */ static void mesh_gate_del(struct mesh_table *tbl, struct mesh_path *mpath) { - struct mpath_node *gate; - struct hlist_node *q; + lockdep_assert_held(&mpath->state_lock); + if (!mpath->is_gate) + return; - hlist_for_each_entry_safe(gate, q, tbl->known_gates, list) { - if (gate->mpath != mpath) - continue; - spin_lock_bh(&tbl->gates_lock); - hlist_del_rcu(&gate->list); - kfree_rcu(gate, rcu); - spin_unlock_bh(&tbl->gates_lock); - mpath->sdata->u.mesh.num_gates--; - mpath->is_gate = false; - mpath_dbg(mpath->sdata, - "Mesh path: Deleted gate: %pM. %d known gates\n", - mpath->dst, mpath->sdata->u.mesh.num_gates); - break; - } + mpath->is_gate = false; + spin_lock_bh(&tbl->gates_lock); + hlist_del_rcu(&mpath->gate_list); + mpath->sdata->u.mesh.num_gates--; + spin_unlock_bh(&tbl->gates_lock); + + mpath_dbg(mpath->sdata, + "Mesh path: Deleted gate: %pM. %d known gates\n", + mpath->dst, mpath->sdata->u.mesh.num_gates); } /** @@ -781,13 +769,13 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node) struct mesh_path *mpath = node->mpath; struct ieee80211_sub_if_data *sdata = node->mpath->sdata; - spin_lock(&mpath->state_lock); + spin_lock_bh(&mpath->state_lock); mpath->flags |= MESH_PATH_RESOLVING; if (mpath->is_gate) mesh_gate_del(tbl, mpath); hlist_del_rcu(&node->list); call_rcu(&node->rcu, mesh_path_node_reclaim); - spin_unlock(&mpath->state_lock); + spin_unlock_bh(&mpath->state_lock); atomic_dec(&sdata->u.mesh.mpaths); atomic_dec(&tbl->entries); } @@ -999,7 +987,7 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) struct ieee80211_sub_if_data *sdata = mpath->sdata; struct mesh_table *tbl; struct mesh_path *from_mpath = mpath; - struct mpath_node *gate = NULL; + struct mesh_path *gate = NULL; bool copy = false; struct hlist_head *known_gates; @@ -1011,22 +999,22 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) if (!known_gates) return -EHOSTUNREACH; - hlist_for_each_entry_rcu(gate, known_gates, list) { - if (gate->mpath->flags & MESH_PATH_ACTIVE) { - mpath_dbg(sdata, "Forwarding to %pM\n", gate->mpath->dst); - mesh_path_move_to_queue(gate->mpath, from_mpath, copy); - from_mpath = gate->mpath; + hlist_for_each_entry_rcu(gate, known_gates, gate_list) { + if (gate->flags & MESH_PATH_ACTIVE) { + mpath_dbg(sdata, "Forwarding to %pM\n", gate->dst); + mesh_path_move_to_queue(gate, from_mpath, copy); + from_mpath = gate; copy = true; } else { mpath_dbg(sdata, "Not forwarding to %pM (flags %#x)\n", - gate->mpath->dst, gate->mpath->flags); + gate->dst, gate->flags); } } - hlist_for_each_entry_rcu(gate, known_gates, list) { - mpath_dbg(sdata, "Sending to %pM\n", gate->mpath->dst); - mesh_path_tx_pending(gate->mpath); + hlist_for_each_entry_rcu(gate, known_gates, gate_list) { + mpath_dbg(sdata, "Sending to %pM\n", gate->dst); + mesh_path_tx_pending(gate); } return (from_mpath == mpath) ? -EHOSTUNREACH : 0; -- cgit v1.2.3 From 60854fd94573f0d3b80b55b40cf0140a0430f3ab Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Wed, 2 Mar 2016 10:09:20 -0500 Subject: mac80211: mesh: convert path table to rhashtable In the time since the mesh path table was implemented as an RCU-traversable, dynamically growing hash table, a generic RCU hashtable implementation was added to the kernel. Switch the mesh path table over to rhashtable to remove some code and also gain some features like automatic shrinking. Cc: Thomas Graf Cc: netdev@vger.kernel.org Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/ieee80211_i.h | 11 +- net/mac80211/mesh.c | 6 - net/mac80211/mesh.h | 31 +- net/mac80211/mesh_pathtbl.c | 786 ++++++++++++++------------------------------ 4 files changed, 259 insertions(+), 575 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h index db7f0dbebc4b..c8945e2d8a86 100644 --- a/net/mac80211/ieee80211_i.h +++ b/net/mac80211/ieee80211_i.h @@ -697,17 +697,10 @@ struct ieee80211_if_mesh { /* offset from skb->data while building IE */ int meshconf_offset; - struct mesh_table __rcu *mesh_paths; - struct mesh_table __rcu *mpp_paths; /* Store paths for MPP&MAP */ + struct mesh_table *mesh_paths; + struct mesh_table *mpp_paths; /* Store paths for MPP&MAP */ int mesh_paths_generation; int mpp_paths_generation; - - /* Protects assignment of the mesh_paths/mpp_paths table - * pointer for resize against reading it for add/delete - * of individual paths. Pure readers (lookups) just use - * RCU. - */ - rwlock_t pathtbl_resize_lock; }; #ifdef CONFIG_MAC80211_MESH diff --git a/net/mac80211/mesh.c b/net/mac80211/mesh.c index c92af2a7714d..a216c439b6f2 100644 --- a/net/mac80211/mesh.c +++ b/net/mac80211/mesh.c @@ -1347,12 +1347,6 @@ void ieee80211_mesh_work(struct ieee80211_sub_if_data *sdata) ifmsh->last_preq + msecs_to_jiffies(ifmsh->mshcfg.dot11MeshHWMPpreqMinInterval))) mesh_path_start_discovery(sdata); - if (test_and_clear_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags)) - mesh_mpath_table_grow(sdata); - - if (test_and_clear_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags)) - mesh_mpp_table_grow(sdata); - if (test_and_clear_bit(MESH_WORK_HOUSEKEEPING, &ifmsh->wrkq_flags)) ieee80211_mesh_housekeeping(sdata); diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h index f3cc3917e048..cc6854db156e 100644 --- a/net/mac80211/mesh.h +++ b/net/mac80211/mesh.h @@ -51,10 +51,6 @@ enum mesh_path_flags { * * * @MESH_WORK_HOUSEKEEPING: run the periodic mesh housekeeping tasks - * @MESH_WORK_GROW_MPATH_TABLE: the mesh path table is full and needs - * to grow. - * @MESH_WORK_GROW_MPP_TABLE: the mesh portals table is full and needs to - * grow * @MESH_WORK_ROOT: the mesh root station needs to send a frame * @MESH_WORK_DRIFT_ADJUST: time to compensate for clock drift relative to other * mesh nodes @@ -62,8 +58,6 @@ enum mesh_path_flags { */ enum mesh_deferred_task_flags { MESH_WORK_HOUSEKEEPING, - MESH_WORK_GROW_MPATH_TABLE, - MESH_WORK_GROW_MPP_TABLE, MESH_WORK_ROOT, MESH_WORK_DRIFT_ADJUST, MESH_WORK_MBSS_CHANGED, @@ -105,6 +99,7 @@ enum mesh_deferred_task_flags { struct mesh_path { u8 dst[ETH_ALEN]; u8 mpp[ETH_ALEN]; /* used for MPP or MAP */ + struct rhash_head rhash; struct hlist_node gate_list; struct ieee80211_sub_if_data *sdata; struct sta_info __rcu *next_hop; @@ -129,34 +124,17 @@ struct mesh_path { /** * struct mesh_table * - * @hash_buckets: array of hash buckets of the table - * @hashwlock: array of locks to protect write operations, one per bucket - * @hash_mask: 2^size_order - 1, used to compute hash idx - * @hash_rnd: random value used for hash computations * @entries: number of entries in the table - * @free_node: function to free nodes of the table - * @copy_node: function to copy nodes of the table - * @size_order: determines size of the table, there will be 2^size_order hash - * buckets * @known_gates: list of known mesh gates and their mpaths by the station. The * gate's mpath may or may not be resolved and active. - * - * rcu_head: RCU head to free the table + * @rhash: the rhashtable containing struct mesh_paths, keyed by dest addr */ struct mesh_table { - /* Number of buckets will be 2^N */ - struct hlist_head *hash_buckets; - spinlock_t *hashwlock; /* One per bucket, for add/del */ - unsigned int hash_mask; /* (2^size_order) - 1 */ - __u32 hash_rnd; /* Used for hash generation */ atomic_t entries; /* Up to MAX_MESH_NEIGHBOURS */ - void (*free_node) (struct hlist_node *p, bool free_leafs); - int (*copy_node) (struct hlist_node *p, struct mesh_table *newtbl); - int size_order; struct hlist_head *known_gates; spinlock_t gates_lock; - struct rcu_head rcu_head; + struct rhashtable rhead; }; /* Recent multicast cache */ @@ -300,9 +278,6 @@ void mesh_rx_plink_frame(struct ieee80211_sub_if_data *sdata, void mesh_sta_cleanup(struct sta_info *sta); /* Private interfaces */ -/* Mesh tables */ -void mesh_mpath_table_grow(struct ieee80211_sub_if_data *sdata); -void mesh_mpp_table_grow(struct ieee80211_sub_if_data *sdata); /* Mesh paths */ int mesh_path_error_tx(struct ieee80211_sub_if_data *sdata, u8 ttl, const u8 *target, u32 target_sn, diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index e4daf4b94eaf..7455397f8c3b 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -18,11 +18,20 @@ #include "ieee80211_i.h" #include "mesh.h" -/* There will be initially 2^INIT_PATHS_SIZE_ORDER buckets */ -#define INIT_PATHS_SIZE_ORDER 2 +static u32 mesh_table_hash(const void *addr, u32 len, u32 seed) +{ + /* Use last four bytes of hw addr as hash index */ + return jhash_1word(*(u32 *)(addr+2), seed); +} -/* Keep the mean chain length below this constant */ -#define MEAN_CHAIN_LEN 2 +static const struct rhashtable_params mesh_rht_params = { + .nelem_hint = 2, + .automatic_shrinking = true, + .key_len = ETH_ALEN, + .key_offset = offsetof(struct mesh_path, dst), + .head_offset = offsetof(struct mesh_path, rhash), + .hashfn = mesh_table_hash, +}; static inline bool mpath_expired(struct mesh_path *mpath) { @@ -31,157 +40,47 @@ static inline bool mpath_expired(struct mesh_path *mpath) !(mpath->flags & MESH_PATH_FIXED); } -struct mpath_node { - struct hlist_node list; - struct rcu_head rcu; - /* This indirection allows two different tables to point to the same - * mesh_path structure, useful when resizing - */ - struct mesh_path *mpath; -}; - -static inline struct mesh_table *resize_dereference_paths( - struct ieee80211_sub_if_data *sdata, - struct mesh_table __rcu *table) +static void mesh_path_reclaim(struct rcu_head *rp) { - return rcu_dereference_protected(table, - lockdep_is_held(&sdata->u.mesh.pathtbl_resize_lock)); -} + struct mesh_path *mpath = container_of(rp, struct mesh_path, rcu); -static inline struct mesh_table *resize_dereference_mesh_paths( - struct ieee80211_sub_if_data *sdata) -{ - return resize_dereference_paths(sdata, sdata->u.mesh.mesh_paths); + del_timer_sync(&mpath->timer); + kfree(mpath); } -static inline struct mesh_table *resize_dereference_mpp_paths( - struct ieee80211_sub_if_data *sdata) +static void mesh_path_rht_free(void *ptr, void *unused_arg) { - return resize_dereference_paths(sdata, sdata->u.mesh.mpp_paths); + struct mesh_path *mpath = ptr; + call_rcu(&mpath->rcu, mesh_path_reclaim); } -/* - * CAREFUL -- "tbl" must not be an expression, - * in particular not an rcu_dereference(), since - * it's used twice. So it is illegal to do - * for_each_mesh_entry(rcu_dereference(...), ...) - */ -#define for_each_mesh_entry(tbl, node, i) \ - for (i = 0; i <= tbl->hash_mask; i++) \ - hlist_for_each_entry_rcu(node, &tbl->hash_buckets[i], list) - - -static struct mesh_table *mesh_table_alloc(int size_order) +static struct mesh_table *mesh_table_alloc(void) { - int i; struct mesh_table *newtbl; newtbl = kmalloc(sizeof(struct mesh_table), GFP_ATOMIC); if (!newtbl) return NULL; - newtbl->hash_buckets = kzalloc(sizeof(struct hlist_head) * - (1 << size_order), GFP_ATOMIC); - - if (!newtbl->hash_buckets) { + newtbl->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC); + if (!newtbl->known_gates) { kfree(newtbl); return NULL; } - - newtbl->hashwlock = kmalloc(sizeof(spinlock_t) * - (1 << size_order), GFP_ATOMIC); - if (!newtbl->hashwlock) { - kfree(newtbl->hash_buckets); - kfree(newtbl); - return NULL; - } - - newtbl->size_order = size_order; - newtbl->hash_mask = (1 << size_order) - 1; + INIT_HLIST_HEAD(newtbl->known_gates); atomic_set(&newtbl->entries, 0); - get_random_bytes(&newtbl->hash_rnd, - sizeof(newtbl->hash_rnd)); - for (i = 0; i <= newtbl->hash_mask; i++) - spin_lock_init(&newtbl->hashwlock[i]); spin_lock_init(&newtbl->gates_lock); return newtbl; } -static void __mesh_table_free(struct mesh_table *tbl) +static void mesh_table_free(struct mesh_table *tbl) { - kfree(tbl->hash_buckets); - kfree(tbl->hashwlock); + rhashtable_free_and_destroy(&tbl->rhead, + mesh_path_rht_free, NULL); kfree(tbl); } -static void mesh_table_free(struct mesh_table *tbl, bool free_leafs) -{ - struct hlist_head *mesh_hash; - struct hlist_node *p, *q; - struct mesh_path *gate; - int i; - - mesh_hash = tbl->hash_buckets; - if (free_leafs) { - spin_lock_bh(&tbl->gates_lock); - hlist_for_each_entry_safe(gate, q, - tbl->known_gates, gate_list) - hlist_del(&gate->gate_list); - kfree(tbl->known_gates); - spin_unlock_bh(&tbl->gates_lock); - } - for (i = 0; i <= tbl->hash_mask; i++) { - spin_lock_bh(&tbl->hashwlock[i]); - hlist_for_each_safe(p, q, &mesh_hash[i]) { - tbl->free_node(p, free_leafs); - atomic_dec(&tbl->entries); - } - spin_unlock_bh(&tbl->hashwlock[i]); - } - - __mesh_table_free(tbl); -} - -static int mesh_table_grow(struct mesh_table *oldtbl, - struct mesh_table *newtbl) -{ - struct hlist_head *oldhash; - struct hlist_node *p, *q; - int i; - - if (atomic_read(&oldtbl->entries) - < MEAN_CHAIN_LEN * (oldtbl->hash_mask + 1)) - return -EAGAIN; - - newtbl->free_node = oldtbl->free_node; - newtbl->copy_node = oldtbl->copy_node; - newtbl->known_gates = oldtbl->known_gates; - atomic_set(&newtbl->entries, atomic_read(&oldtbl->entries)); - - oldhash = oldtbl->hash_buckets; - for (i = 0; i <= oldtbl->hash_mask; i++) - hlist_for_each(p, &oldhash[i]) - if (oldtbl->copy_node(p, newtbl) < 0) - goto errcopy; - - return 0; - -errcopy: - for (i = 0; i <= newtbl->hash_mask; i++) { - hlist_for_each_safe(p, q, &newtbl->hash_buckets[i]) - oldtbl->free_node(p, 0); - } - return -ENOMEM; -} - -static u32 mesh_table_hash(const u8 *addr, struct mesh_table *tbl) -{ - /* Use last four bytes of hw addr as hash index */ - return jhash_1word(*(u32 *)(addr+2), tbl->hash_rnd) & tbl->hash_mask; -} - - /** * * mesh_path_assign_nexthop - update mesh path next hop @@ -324,22 +223,15 @@ static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst, struct ieee80211_sub_if_data *sdata) { struct mesh_path *mpath; - struct hlist_head *bucket; - struct mpath_node *node; - - bucket = &tbl->hash_buckets[mesh_table_hash(dst, tbl)]; - hlist_for_each_entry_rcu(node, bucket, list) { - mpath = node->mpath; - if (ether_addr_equal(dst, mpath->dst)) { - if (mpath_expired(mpath)) { - spin_lock_bh(&mpath->state_lock); - mpath->flags &= ~MESH_PATH_ACTIVE; - spin_unlock_bh(&mpath->state_lock); - } - return mpath; - } + + mpath = rhashtable_lookup_fast(&tbl->rhead, dst, mesh_rht_params); + + if (mpath && mpath_expired(mpath)) { + spin_lock_bh(&mpath->state_lock); + mpath->flags &= ~MESH_PATH_ACTIVE; + spin_unlock_bh(&mpath->state_lock); } - return NULL; + return mpath; } /** @@ -354,17 +246,52 @@ static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst, struct mesh_path * mesh_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) { - return mpath_lookup(rcu_dereference(sdata->u.mesh.mesh_paths), dst, - sdata); + return mpath_lookup(sdata->u.mesh.mesh_paths, dst, sdata); } struct mesh_path * mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) { - return mpath_lookup(rcu_dereference(sdata->u.mesh.mpp_paths), dst, - sdata); + return mpath_lookup(sdata->u.mesh.mpp_paths, dst, sdata); } +static struct mesh_path * +__mesh_path_lookup_by_idx(struct mesh_table *tbl, int idx) +{ + int i = 0, ret; + struct mesh_path *mpath = NULL; + struct rhashtable_iter iter; + + ret = rhashtable_walk_init(&tbl->rhead, &iter, GFP_ATOMIC); + if (ret) + return NULL; + + ret = rhashtable_walk_start(&iter); + if (ret && ret != -EAGAIN) + goto err; + + while ((mpath = rhashtable_walk_next(&iter))) { + if (IS_ERR(mpath) && PTR_ERR(mpath) == -EAGAIN) + continue; + if (IS_ERR(mpath)) + break; + if (i++ == idx) + break; + } +err: + rhashtable_walk_stop(&iter); + rhashtable_walk_exit(&iter); + + if (IS_ERR(mpath) || !mpath) + return NULL; + + if (mpath_expired(mpath)) { + spin_lock_bh(&mpath->state_lock); + mpath->flags &= ~MESH_PATH_ACTIVE; + spin_unlock_bh(&mpath->state_lock); + } + return mpath; +} /** * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index @@ -378,23 +305,7 @@ mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) struct mesh_path * mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) { - struct mesh_table *tbl = rcu_dereference(sdata->u.mesh.mesh_paths); - struct mpath_node *node; - int i; - int j = 0; - - for_each_mesh_entry(tbl, node, i) { - if (j++ == idx) { - if (mpath_expired(node->mpath)) { - spin_lock_bh(&node->mpath->state_lock); - node->mpath->flags &= ~MESH_PATH_ACTIVE; - spin_unlock_bh(&node->mpath->state_lock); - } - return node->mpath; - } - } - - return NULL; + return __mesh_path_lookup_by_idx(sdata->u.mesh.mesh_paths, idx); } /** @@ -409,17 +320,7 @@ mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) struct mesh_path * mpp_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) { - struct mesh_table *tbl = rcu_dereference(sdata->u.mesh.mpp_paths); - struct mpath_node *node; - int i; - int j = 0; - - for_each_mesh_entry(tbl, node, i) { - if (j++ == idx) - return node->mpath; - } - - return NULL; + return __mesh_path_lookup_by_idx(sdata->u.mesh.mpp_paths, idx); } /** @@ -432,7 +333,7 @@ int mesh_path_add_gate(struct mesh_path *mpath) int err; rcu_read_lock(); - tbl = rcu_dereference(mpath->sdata->u.mesh.mesh_paths); + tbl = mpath->sdata->u.mesh.mesh_paths; spin_lock_bh(&mpath->state_lock); if (mpath->is_gate) { @@ -526,15 +427,9 @@ struct mesh_path *mesh_path_new(struct ieee80211_sub_if_data *sdata, struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, const u8 *dst) { - struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh; - struct ieee80211_local *local = sdata->local; struct mesh_table *tbl; struct mesh_path *mpath, *new_mpath; - struct mpath_node *node, *new_node; - struct hlist_head *bucket; - int grow = 0; - int err; - u32 hash_idx; + int ret; if (ether_addr_equal(dst, sdata->vif.addr)) /* never add ourselves as neighbours */ @@ -546,116 +441,44 @@ struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0) return ERR_PTR(-ENOSPC); - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - tbl = resize_dereference_mesh_paths(sdata); - - hash_idx = mesh_table_hash(dst, tbl); - bucket = &tbl->hash_buckets[hash_idx]; - - spin_lock(&tbl->hashwlock[hash_idx]); - - hlist_for_each_entry(node, bucket, list) { - mpath = node->mpath; - if (ether_addr_equal(dst, mpath->dst)) - goto found; - } - - err = -ENOMEM; new_mpath = mesh_path_new(sdata, dst, GFP_ATOMIC); if (!new_mpath) - goto err_path_alloc; - - new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC); - if (!new_node) - goto err_node_alloc; - - new_node->mpath = new_mpath; - hlist_add_head_rcu(&new_node->list, bucket); - if (atomic_inc_return(&tbl->entries) >= - MEAN_CHAIN_LEN * (tbl->hash_mask + 1)) - grow = 1; - - sdata->u.mesh.mesh_paths_generation++; - - if (grow) { - set_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags); - ieee80211_queue_work(&local->hw, &sdata->work); - } - mpath = new_mpath; -found: - spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - return mpath; - -err_node_alloc: - kfree(new_mpath); -err_path_alloc: - atomic_dec(&sdata->u.mesh.mpaths); - spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - return ERR_PTR(err); -} - -static void mesh_table_free_rcu(struct rcu_head *rcu) -{ - struct mesh_table *tbl = container_of(rcu, struct mesh_table, rcu_head); - - mesh_table_free(tbl, false); -} - -void mesh_mpath_table_grow(struct ieee80211_sub_if_data *sdata) -{ - struct mesh_table *oldtbl, *newtbl; + return ERR_PTR(-ENOMEM); - write_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - oldtbl = resize_dereference_mesh_paths(sdata); - newtbl = mesh_table_alloc(oldtbl->size_order + 1); - if (!newtbl) - goto out; - if (mesh_table_grow(oldtbl, newtbl) < 0) { - __mesh_table_free(newtbl); - goto out; - } - rcu_assign_pointer(sdata->u.mesh.mesh_paths, newtbl); + tbl = sdata->u.mesh.mesh_paths; + do { + ret = rhashtable_lookup_insert_fast(&tbl->rhead, + &new_mpath->rhash, + mesh_rht_params); - call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu); + if (ret == -EEXIST) + mpath = rhashtable_lookup_fast(&tbl->rhead, + dst, + mesh_rht_params); - out: - write_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); -} + } while (unlikely(ret == -EEXIST && !mpath)); -void mesh_mpp_table_grow(struct ieee80211_sub_if_data *sdata) -{ - struct mesh_table *oldtbl, *newtbl; + if (ret && ret != -EEXIST) + return ERR_PTR(ret); - write_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - oldtbl = resize_dereference_mpp_paths(sdata); - newtbl = mesh_table_alloc(oldtbl->size_order + 1); - if (!newtbl) - goto out; - if (mesh_table_grow(oldtbl, newtbl) < 0) { - __mesh_table_free(newtbl); - goto out; + /* At this point either new_mpath was added, or we found a + * matching entry already in the table; in the latter case + * free the unnecessary new entry. + */ + if (ret == -EEXIST) { + kfree(new_mpath); + new_mpath = mpath; } - rcu_assign_pointer(sdata->u.mesh.mpp_paths, newtbl); - call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu); - - out: - write_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); + sdata->u.mesh.mesh_paths_generation++; + return new_mpath; } int mpp_path_add(struct ieee80211_sub_if_data *sdata, const u8 *dst, const u8 *mpp) { - struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh; - struct ieee80211_local *local = sdata->local; struct mesh_table *tbl; - struct mesh_path *mpath, *new_mpath; - struct mpath_node *node, *new_node; - struct hlist_head *bucket; - int grow = 0; - int err = 0; - u32 hash_idx; + struct mesh_path *new_mpath; + int ret; if (ether_addr_equal(dst, sdata->vif.addr)) /* never add ourselves as neighbours */ @@ -664,56 +487,19 @@ int mpp_path_add(struct ieee80211_sub_if_data *sdata, if (is_multicast_ether_addr(dst)) return -ENOTSUPP; - err = -ENOMEM; new_mpath = mesh_path_new(sdata, dst, GFP_ATOMIC); - if (!new_mpath) - goto err_path_alloc; - new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC); - if (!new_node) - goto err_node_alloc; + if (!new_mpath) + return -ENOMEM; memcpy(new_mpath->mpp, mpp, ETH_ALEN); - new_node->mpath = new_mpath; - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - tbl = resize_dereference_mpp_paths(sdata); - - hash_idx = mesh_table_hash(dst, tbl); - bucket = &tbl->hash_buckets[hash_idx]; - - spin_lock(&tbl->hashwlock[hash_idx]); - - err = -EEXIST; - hlist_for_each_entry(node, bucket, list) { - mpath = node->mpath; - if (ether_addr_equal(dst, mpath->dst)) - goto err_exists; - } - - hlist_add_head_rcu(&new_node->list, bucket); - if (atomic_inc_return(&tbl->entries) >= - MEAN_CHAIN_LEN * (tbl->hash_mask + 1)) - grow = 1; - - spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); + tbl = sdata->u.mesh.mpp_paths; + ret = rhashtable_lookup_insert_fast(&tbl->rhead, + &new_mpath->rhash, + mesh_rht_params); sdata->u.mesh.mpp_paths_generation++; - - if (grow) { - set_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags); - ieee80211_queue_work(&local->hw, &sdata->work); - } - return 0; - -err_exists: - spin_unlock(&tbl->hashwlock[hash_idx]); - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - kfree(new_node); -err_node_alloc: - kfree(new_mpath); -err_path_alloc: - return err; + return ret; } @@ -727,17 +513,26 @@ err_path_alloc: */ void mesh_plink_broken(struct sta_info *sta) { - struct mesh_table *tbl; + struct ieee80211_sub_if_data *sdata = sta->sdata; + struct mesh_table *tbl = sdata->u.mesh.mesh_paths; static const u8 bcast[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff}; struct mesh_path *mpath; - struct mpath_node *node; - struct ieee80211_sub_if_data *sdata = sta->sdata; - int i; + struct rhashtable_iter iter; + int ret; - rcu_read_lock(); - tbl = rcu_dereference(sdata->u.mesh.mesh_paths); - for_each_mesh_entry(tbl, node, i) { - mpath = node->mpath; + ret = rhashtable_walk_init(&tbl->rhead, &iter, GFP_ATOMIC); + if (ret) + return; + + ret = rhashtable_walk_start(&iter); + if (ret && ret != -EAGAIN) + goto out; + + while ((mpath = rhashtable_walk_next(&iter))) { + if (IS_ERR(mpath) && PTR_ERR(mpath) == -EAGAIN) + continue; + if (IS_ERR(mpath)) + break; if (rcu_access_pointer(mpath->next_hop) == sta && mpath->flags & MESH_PATH_ACTIVE && !(mpath->flags & MESH_PATH_FIXED)) { @@ -751,30 +546,20 @@ void mesh_plink_broken(struct sta_info *sta) WLAN_REASON_MESH_PATH_DEST_UNREACHABLE, bcast); } } - rcu_read_unlock(); -} - -static void mesh_path_node_reclaim(struct rcu_head *rp) -{ - struct mpath_node *node = container_of(rp, struct mpath_node, rcu); - - del_timer_sync(&node->mpath->timer); - kfree(node->mpath); - kfree(node); +out: + rhashtable_walk_stop(&iter); + rhashtable_walk_exit(&iter); } -/* needs to be called with the corresponding hashwlock taken */ -static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node) +static void __mesh_path_del(struct mesh_table *tbl, struct mesh_path *mpath) { - struct mesh_path *mpath = node->mpath; - struct ieee80211_sub_if_data *sdata = node->mpath->sdata; + struct ieee80211_sub_if_data *sdata = mpath->sdata; + rhashtable_remove_fast(&tbl->rhead, &mpath->rhash, mesh_rht_params); spin_lock_bh(&mpath->state_lock); mpath->flags |= MESH_PATH_RESOLVING; - if (mpath->is_gate) - mesh_gate_del(tbl, mpath); - hlist_del_rcu(&node->list); - call_rcu(&node->rcu, mesh_path_node_reclaim); + mesh_gate_del(tbl, mpath); + call_rcu(&mpath->rcu, mesh_path_reclaim); spin_unlock_bh(&mpath->state_lock); atomic_dec(&sdata->u.mesh.mpaths); atomic_dec(&tbl->entries); @@ -794,63 +579,87 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node) void mesh_path_flush_by_nexthop(struct sta_info *sta) { struct ieee80211_sub_if_data *sdata = sta->sdata; - struct mesh_table *tbl; + struct mesh_table *tbl = sdata->u.mesh.mesh_paths; struct mesh_path *mpath; - struct mpath_node *node; - int i; + struct rhashtable_iter iter; + int ret; - rcu_read_lock(); - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - tbl = resize_dereference_mesh_paths(sdata); - for_each_mesh_entry(tbl, node, i) { - mpath = node->mpath; - if (rcu_access_pointer(mpath->next_hop) == sta) { - spin_lock(&tbl->hashwlock[i]); - __mesh_path_del(tbl, node); - spin_unlock(&tbl->hashwlock[i]); - } + ret = rhashtable_walk_init(&tbl->rhead, &iter, GFP_ATOMIC); + if (ret) + return; + + ret = rhashtable_walk_start(&iter); + if (ret && ret != -EAGAIN) + goto out; + + while ((mpath = rhashtable_walk_next(&iter))) { + if (IS_ERR(mpath) && PTR_ERR(mpath) == -EAGAIN) + continue; + if (IS_ERR(mpath)) + break; + + if (rcu_access_pointer(mpath->next_hop) == sta) + __mesh_path_del(tbl, mpath); } - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - rcu_read_unlock(); +out: + rhashtable_walk_stop(&iter); + rhashtable_walk_exit(&iter); } static void mpp_flush_by_proxy(struct ieee80211_sub_if_data *sdata, const u8 *proxy) { - struct mesh_table *tbl; - struct mesh_path *mpp; - struct mpath_node *node; - int i; + struct mesh_table *tbl = sdata->u.mesh.mpp_paths; + struct mesh_path *mpath; + struct rhashtable_iter iter; + int ret; - rcu_read_lock(); - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - tbl = resize_dereference_mpp_paths(sdata); - for_each_mesh_entry(tbl, node, i) { - mpp = node->mpath; - if (ether_addr_equal(mpp->mpp, proxy)) { - spin_lock(&tbl->hashwlock[i]); - __mesh_path_del(tbl, node); - spin_unlock(&tbl->hashwlock[i]); - } + ret = rhashtable_walk_init(&tbl->rhead, &iter, GFP_ATOMIC); + if (ret) + return; + + ret = rhashtable_walk_start(&iter); + if (ret && ret != -EAGAIN) + goto out; + + while ((mpath = rhashtable_walk_next(&iter))) { + if (IS_ERR(mpath) && PTR_ERR(mpath) == -EAGAIN) + continue; + if (IS_ERR(mpath)) + break; + + if (ether_addr_equal(mpath->mpp, proxy)) + __mesh_path_del(tbl, mpath); } - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - rcu_read_unlock(); +out: + rhashtable_walk_stop(&iter); + rhashtable_walk_exit(&iter); } -static void table_flush_by_iface(struct mesh_table *tbl, - struct ieee80211_sub_if_data *sdata) +static void table_flush_by_iface(struct mesh_table *tbl) { struct mesh_path *mpath; - struct mpath_node *node; - int i; - - WARN_ON(!rcu_read_lock_held()); - for_each_mesh_entry(tbl, node, i) { - mpath = node->mpath; - spin_lock_bh(&tbl->hashwlock[i]); - __mesh_path_del(tbl, node); - spin_unlock_bh(&tbl->hashwlock[i]); + struct rhashtable_iter iter; + int ret; + + ret = rhashtable_walk_init(&tbl->rhead, &iter, GFP_ATOMIC); + if (ret) + return; + + ret = rhashtable_walk_start(&iter); + if (ret && ret != -EAGAIN) + goto out; + + while ((mpath = rhashtable_walk_next(&iter))) { + if (IS_ERR(mpath) && PTR_ERR(mpath) == -EAGAIN) + continue; + if (IS_ERR(mpath)) + break; + __mesh_path_del(tbl, mpath); } +out: + rhashtable_walk_stop(&iter); + rhashtable_walk_exit(&iter); } /** @@ -863,16 +672,8 @@ static void table_flush_by_iface(struct mesh_table *tbl, */ void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata) { - struct mesh_table *tbl; - - rcu_read_lock(); - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - tbl = resize_dereference_mesh_paths(sdata); - table_flush_by_iface(tbl, sdata); - tbl = resize_dereference_mpp_paths(sdata); - table_flush_by_iface(tbl, sdata); - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - rcu_read_unlock(); + table_flush_by_iface(sdata->u.mesh.mesh_paths); + table_flush_by_iface(sdata->u.mesh.mpp_paths); } /** @@ -884,36 +685,25 @@ void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata) * * Returns: 0 if successful */ -static int table_path_del(struct mesh_table __rcu *rcu_tbl, +static int table_path_del(struct mesh_table *tbl, struct ieee80211_sub_if_data *sdata, const u8 *addr) { - struct mesh_table *tbl; struct mesh_path *mpath; - struct mpath_node *node; - struct hlist_head *bucket; - int hash_idx; - int err = 0; - - tbl = resize_dereference_paths(sdata, rcu_tbl); - hash_idx = mesh_table_hash(addr, tbl); - bucket = &tbl->hash_buckets[hash_idx]; - - spin_lock(&tbl->hashwlock[hash_idx]); - hlist_for_each_entry(node, bucket, list) { - mpath = node->mpath; - if (ether_addr_equal(addr, mpath->dst)) { - __mesh_path_del(tbl, node); - goto enddel; - } + + rcu_read_lock(); + mpath = rhashtable_lookup_fast(&tbl->rhead, addr, mesh_rht_params); + if (!mpath) { + rcu_read_unlock(); + return -ENXIO; } - err = -ENXIO; -enddel: - spin_unlock(&tbl->hashwlock[hash_idx]); - return err; + __mesh_path_del(tbl, mpath); + rcu_read_unlock(); + return 0; } + /** * mesh_path_del - delete a mesh path from the table * @@ -924,36 +714,13 @@ enddel: */ int mesh_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr) { - int err = 0; + int err; /* flush relevant mpp entries first */ mpp_flush_by_proxy(sdata, addr); - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); err = table_path_del(sdata->u.mesh.mesh_paths, sdata, addr); sdata->u.mesh.mesh_paths_generation++; - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - - return err; -} - -/** - * mpp_path_del - delete a mesh proxy path from the table - * - * @addr: addr address (ETH_ALEN length) - * @sdata: local subif - * - * Returns: 0 if successful - */ -static int mpp_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr) -{ - int err = 0; - - read_lock_bh(&sdata->u.mesh.pathtbl_resize_lock); - err = table_path_del(sdata->u.mesh.mpp_paths, sdata, addr); - sdata->u.mesh.mpp_paths_generation++; - read_unlock_bh(&sdata->u.mesh.pathtbl_resize_lock); - return err; } @@ -987,18 +754,17 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) struct ieee80211_sub_if_data *sdata = mpath->sdata; struct mesh_table *tbl; struct mesh_path *from_mpath = mpath; - struct mesh_path *gate = NULL; + struct mesh_path *gate; bool copy = false; struct hlist_head *known_gates; - rcu_read_lock(); - tbl = rcu_dereference(sdata->u.mesh.mesh_paths); + tbl = sdata->u.mesh.mesh_paths; known_gates = tbl->known_gates; - rcu_read_unlock(); if (!known_gates) return -EHOSTUNREACH; + rcu_read_lock(); hlist_for_each_entry_rcu(gate, known_gates, gate_list) { if (gate->flags & MESH_PATH_ACTIVE) { mpath_dbg(sdata, "Forwarding to %pM\n", gate->dst); @@ -1016,6 +782,7 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) mpath_dbg(sdata, "Sending to %pM\n", gate->dst); mesh_path_tx_pending(gate); } + rcu_read_unlock(); return (from_mpath == mpath) ? -EHOSTUNREACH : 0; } @@ -1072,118 +839,73 @@ void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop) mesh_path_tx_pending(mpath); } -static void mesh_path_node_free(struct hlist_node *p, bool free_leafs) -{ - struct mesh_path *mpath; - struct mpath_node *node = hlist_entry(p, struct mpath_node, list); - mpath = node->mpath; - hlist_del_rcu(p); - if (free_leafs) { - del_timer_sync(&mpath->timer); - kfree(mpath); - } - kfree(node); -} - -static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl) -{ - struct mesh_path *mpath; - struct mpath_node *node, *new_node; - u32 hash_idx; - - new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC); - if (new_node == NULL) - return -ENOMEM; - - node = hlist_entry(p, struct mpath_node, list); - mpath = node->mpath; - new_node->mpath = mpath; - hash_idx = mesh_table_hash(mpath->dst, newtbl); - hlist_add_head(&new_node->list, - &newtbl->hash_buckets[hash_idx]); - return 0; -} - int mesh_pathtbl_init(struct ieee80211_sub_if_data *sdata) { struct mesh_table *tbl_path, *tbl_mpp; int ret; - tbl_path = mesh_table_alloc(INIT_PATHS_SIZE_ORDER); + tbl_path = mesh_table_alloc(); if (!tbl_path) return -ENOMEM; - tbl_path->free_node = &mesh_path_node_free; - tbl_path->copy_node = &mesh_path_node_copy; - tbl_path->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC); - if (!tbl_path->known_gates) { - ret = -ENOMEM; - goto free_path; - } - INIT_HLIST_HEAD(tbl_path->known_gates); - - tbl_mpp = mesh_table_alloc(INIT_PATHS_SIZE_ORDER); + tbl_mpp = mesh_table_alloc(); if (!tbl_mpp) { ret = -ENOMEM; goto free_path; } - tbl_mpp->free_node = &mesh_path_node_free; - tbl_mpp->copy_node = &mesh_path_node_copy; - tbl_mpp->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC); - if (!tbl_mpp->known_gates) { - ret = -ENOMEM; - goto free_mpp; - } - INIT_HLIST_HEAD(tbl_mpp->known_gates); - rwlock_init(&sdata->u.mesh.pathtbl_resize_lock); + rhashtable_init(&tbl_path->rhead, &mesh_rht_params); + rhashtable_init(&tbl_mpp->rhead, &mesh_rht_params); - /* Need no locking since this is during init */ - RCU_INIT_POINTER(sdata->u.mesh.mesh_paths, tbl_path); - RCU_INIT_POINTER(sdata->u.mesh.mpp_paths, tbl_mpp); + sdata->u.mesh.mesh_paths = tbl_path; + sdata->u.mesh.mpp_paths = tbl_mpp; return 0; -free_mpp: - mesh_table_free(tbl_mpp, true); free_path: - mesh_table_free(tbl_path, true); + mesh_table_free(tbl_path); return ret; } -void mesh_path_expire(struct ieee80211_sub_if_data *sdata) +static +void mesh_path_tbl_expire(struct ieee80211_sub_if_data *sdata, + struct mesh_table *tbl) { - struct mesh_table *tbl; struct mesh_path *mpath; - struct mpath_node *node; - int i; + struct rhashtable_iter iter; + int ret; - rcu_read_lock(); - tbl = rcu_dereference(sdata->u.mesh.mesh_paths); - for_each_mesh_entry(tbl, node, i) { - mpath = node->mpath; + ret = rhashtable_walk_init(&tbl->rhead, &iter, GFP_KERNEL); + if (ret) + return; + + ret = rhashtable_walk_start(&iter); + if (ret && ret != -EAGAIN) + goto out; + + while ((mpath = rhashtable_walk_next(&iter))) { + if (IS_ERR(mpath) && PTR_ERR(mpath) == -EAGAIN) + continue; + if (IS_ERR(mpath)) + break; if ((!(mpath->flags & MESH_PATH_RESOLVING)) && (!(mpath->flags & MESH_PATH_FIXED)) && time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) - mesh_path_del(sdata, mpath->dst); - } - - tbl = rcu_dereference(sdata->u.mesh.mpp_paths); - for_each_mesh_entry(tbl, node, i) { - mpath = node->mpath; - if ((!(mpath->flags & MESH_PATH_FIXED)) && - time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) - mpp_path_del(sdata, mpath->dst); + __mesh_path_del(tbl, mpath); } +out: + rhashtable_walk_stop(&iter); + rhashtable_walk_exit(&iter); +} - rcu_read_unlock(); +void mesh_path_expire(struct ieee80211_sub_if_data *sdata) +{ + mesh_path_tbl_expire(sdata, sdata->u.mesh.mesh_paths); + mesh_path_tbl_expire(sdata, sdata->u.mesh.mpp_paths); } void mesh_pathtbl_unregister(struct ieee80211_sub_if_data *sdata) { - /* no need for locking during exit path */ - mesh_table_free(rcu_dereference_protected(sdata->u.mesh.mesh_paths, 1), - true); - mesh_table_free(rcu_dereference_protected(sdata->u.mesh.mpp_paths, 1), - true); + mesh_table_free(sdata->u.mesh.mesh_paths); + mesh_table_free(sdata->u.mesh.mpp_paths); } -- cgit v1.2.3 From 749329594b5e0fb612b2de642a692323ddf661dd Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Fri, 18 Mar 2016 22:03:24 -0400 Subject: mac80211: mesh: fix crash in mesh_path_timer The mesh_path_reclaim() function, called from an rcu callback, cancels the mesh_path_timer associated with a mesh path. Unfortunately, this call can happen much later, perhaps after the hash table itself is destroyed. Such a situation led to the following crash in mesh_path_send_to_gates() when dereferencing the tbl pointer: [ 23.901661] BUG: unable to handle kernel NULL pointer dereference at 0000000000000008 [ 23.905516] IP: [] mesh_path_send_to_gates+0x2b/0x740 [ 23.908757] PGD 99ca067 PUD 99c4067 PMD 0 [ 23.910789] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC [ 23.913485] CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.5.0-rc6-wt+ #43 [ 23.916675] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Debian-1.8.2-1 04/01/2014 [ 23.920471] task: ffffffff81685500 ti: ffffffff81678000 task.ti: ffffffff81678000 [ 23.922619] RIP: 0010:[] [] mesh_path_send_to_gates+0x2b/0x740 [ 23.925237] RSP: 0018:ffff88000b403d30 EFLAGS: 00010286 [ 23.926739] RAX: 0000000000000000 RBX: ffff880009bc0d20 RCX: 0000000000000102 [ 23.928796] RDX: 000000000000002e RSI: 0000000000000001 RDI: ffff880009bc0d20 [ 23.930895] RBP: ffff88000b403e18 R08: 0000000000000001 R09: 0000000000000001 [ 23.932917] R10: 0000000000000000 R11: 0000000000000001 R12: ffff880009c20940 [ 23.936370] R13: ffff880009bc0e70 R14: ffff880009c21c40 R15: ffff880009bc0d20 [ 23.939823] FS: 0000000000000000(0000) GS:ffff88000b400000(0000) knlGS:0000000000000000 [ 23.943688] CS: 0010 DS: 0000 ES: 0000 CR0: 000000008005003b [ 23.946429] CR2: 0000000000000008 CR3: 00000000099c5000 CR4: 00000000000006b0 [ 23.949861] Stack: [ 23.950840] 000000000000002e ffff880009c20940 ffff88000b403da8 ffffffff8109e551 [ 23.954467] ffffffff82711be2 000000000000002e 0000000000000000 ffffffff8166a5f5 [ 23.958141] 0000000000685ce8 0000000000000246 ffff880009bc0d20 ffff880009c20940 [ 23.961801] Call Trace: [ 23.962987] [ 23.963963] [] ? vprintk_emit+0x351/0x5e0 [ 23.966782] [] ? vprintk_default+0x1f/0x30 [ 23.969529] [] ? printk+0x48/0x50 [ 23.971956] [] mesh_path_timer+0x133/0x160 [ 23.974707] [] ? mesh_nexthop_resolve+0x230/0x230 [ 23.977775] [] call_timer_fn+0xce/0x330 [ 23.980448] [] ? call_timer_fn+0x5/0x330 [ 23.983126] [] ? mesh_nexthop_resolve+0x230/0x230 [ 23.986091] [] run_timer_softirq+0x22c/0x390 Instead of cancelling in the RCU callback, set a new flag to prevent the timer from being rearmed, and then cancel the timer synchronously when freeing the mesh path. This leaves mesh_path_reclaim() doing nothing but kfree, so switch to kfree_rcu(). Fixes: 3b302ada7f0a ("mac80211: mesh: move path tables into if_mesh") Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/mesh.h | 3 +++ net/mac80211/mesh_hwmp.c | 4 ++++ net/mac80211/mesh_pathtbl.c | 33 ++++++++++++++++++--------------- 3 files changed, 25 insertions(+), 15 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h index cc6854db156e..e1415c952e9c 100644 --- a/net/mac80211/mesh.h +++ b/net/mac80211/mesh.h @@ -32,6 +32,8 @@ * @MESH_PATH_RESOLVED: the mesh path can has been resolved * @MESH_PATH_REQ_QUEUED: there is an unsent path request for this destination * already queued up, waiting for the discovery process to start. + * @MESH_PATH_DELETED: the mesh path has been deleted and should no longer + * be used * * MESH_PATH_RESOLVED is used by the mesh path timer to * decide when to stop or cancel the mesh path discovery. @@ -43,6 +45,7 @@ enum mesh_path_flags { MESH_PATH_FIXED = BIT(3), MESH_PATH_RESOLVED = BIT(4), MESH_PATH_REQ_QUEUED = BIT(5), + MESH_PATH_DELETED = BIT(6), }; /** diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c index 5b6aec1a0630..2748cf627ee3 100644 --- a/net/mac80211/mesh_hwmp.c +++ b/net/mac80211/mesh_hwmp.c @@ -1012,6 +1012,10 @@ void mesh_path_start_discovery(struct ieee80211_sub_if_data *sdata) goto enddiscovery; spin_lock_bh(&mpath->state_lock); + if (mpath->flags & MESH_PATH_DELETED) { + spin_unlock_bh(&mpath->state_lock); + goto enddiscovery; + } mpath->flags &= ~MESH_PATH_REQ_QUEUED; if (preq_node->flags & PREQ_Q_F_START) { if (mpath->flags & MESH_PATH_RESOLVING) { diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index 7455397f8c3b..1c9412a29ca3 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -18,6 +18,8 @@ #include "ieee80211_i.h" #include "mesh.h" +static void mesh_path_free_rcu(struct mesh_table *tbl, struct mesh_path *mpath); + static u32 mesh_table_hash(const void *addr, u32 len, u32 seed) { /* Use last four bytes of hw addr as hash index */ @@ -40,18 +42,12 @@ static inline bool mpath_expired(struct mesh_path *mpath) !(mpath->flags & MESH_PATH_FIXED); } -static void mesh_path_reclaim(struct rcu_head *rp) -{ - struct mesh_path *mpath = container_of(rp, struct mesh_path, rcu); - - del_timer_sync(&mpath->timer); - kfree(mpath); -} - -static void mesh_path_rht_free(void *ptr, void *unused_arg) +static void mesh_path_rht_free(void *ptr, void *tblptr) { struct mesh_path *mpath = ptr; - call_rcu(&mpath->rcu, mesh_path_reclaim); + struct mesh_table *tbl = tblptr; + + mesh_path_free_rcu(tbl, mpath); } static struct mesh_table *mesh_table_alloc(void) @@ -77,7 +73,7 @@ static struct mesh_table *mesh_table_alloc(void) static void mesh_table_free(struct mesh_table *tbl) { rhashtable_free_and_destroy(&tbl->rhead, - mesh_path_rht_free, NULL); + mesh_path_rht_free, tbl); kfree(tbl); } @@ -551,18 +547,25 @@ out: rhashtable_walk_exit(&iter); } -static void __mesh_path_del(struct mesh_table *tbl, struct mesh_path *mpath) +static void mesh_path_free_rcu(struct mesh_table *tbl, + struct mesh_path *mpath) { struct ieee80211_sub_if_data *sdata = mpath->sdata; - rhashtable_remove_fast(&tbl->rhead, &mpath->rhash, mesh_rht_params); spin_lock_bh(&mpath->state_lock); - mpath->flags |= MESH_PATH_RESOLVING; + mpath->flags |= MESH_PATH_RESOLVING | MESH_PATH_DELETED; mesh_gate_del(tbl, mpath); - call_rcu(&mpath->rcu, mesh_path_reclaim); spin_unlock_bh(&mpath->state_lock); + del_timer_sync(&mpath->timer); atomic_dec(&sdata->u.mesh.mpaths); atomic_dec(&tbl->entries); + kfree_rcu(mpath, rcu); +} + +static void __mesh_path_del(struct mesh_table *tbl, struct mesh_path *mpath) +{ + rhashtable_remove_fast(&tbl->rhead, &mpath->rhash, mesh_rht_params); + mesh_path_free_rcu(tbl, mpath); } /** -- cgit v1.2.3 From 18b27ff7d2e232b0f07f2f51aa8052ff2a617908 Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Fri, 18 Mar 2016 22:11:30 -0400 Subject: mac80211: mesh: embed gates hlist head directly Since we have converted the mesh path tables to rhashtable, we are no longer swapping out the entire mesh_pathtbl pointer with RCU. As a result, we no longer need indirection to the hlist head for the gates list and can simply embed it, saving a pair of pointer-sized allocations. Signed-off-by: Bob Copeland Signed-off-by: Johannes Berg --- net/mac80211/mesh.h | 2 +- net/mac80211/mesh_pathtbl.c | 18 ++++-------------- 2 files changed, 5 insertions(+), 15 deletions(-) (limited to 'net/mac80211/mesh_pathtbl.c') diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h index bc3f9a32b5a4..46b540a25d9d 100644 --- a/net/mac80211/mesh.h +++ b/net/mac80211/mesh.h @@ -134,7 +134,7 @@ struct mesh_path { */ struct mesh_table { atomic_t entries; /* Up to MAX_MESH_NEIGHBOURS */ - struct hlist_head *known_gates; + struct hlist_head known_gates; spinlock_t gates_lock; struct rhashtable rhead; diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c index 1c9412a29ca3..6db2ddfa0695 100644 --- a/net/mac80211/mesh_pathtbl.c +++ b/net/mac80211/mesh_pathtbl.c @@ -58,12 +58,7 @@ static struct mesh_table *mesh_table_alloc(void) if (!newtbl) return NULL; - newtbl->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC); - if (!newtbl->known_gates) { - kfree(newtbl); - return NULL; - } - INIT_HLIST_HEAD(newtbl->known_gates); + INIT_HLIST_HEAD(&newtbl->known_gates); atomic_set(&newtbl->entries, 0); spin_lock_init(&newtbl->gates_lock); @@ -341,7 +336,7 @@ int mesh_path_add_gate(struct mesh_path *mpath) mpath->sdata->u.mesh.num_gates++; spin_lock(&tbl->gates_lock); - hlist_add_head_rcu(&mpath->gate_list, tbl->known_gates); + hlist_add_head_rcu(&mpath->gate_list, &tbl->known_gates); spin_unlock(&tbl->gates_lock); spin_unlock_bh(&mpath->state_lock); @@ -759,16 +754,11 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) struct mesh_path *from_mpath = mpath; struct mesh_path *gate; bool copy = false; - struct hlist_head *known_gates; tbl = sdata->u.mesh.mesh_paths; - known_gates = tbl->known_gates; - - if (!known_gates) - return -EHOSTUNREACH; rcu_read_lock(); - hlist_for_each_entry_rcu(gate, known_gates, gate_list) { + hlist_for_each_entry_rcu(gate, &tbl->known_gates, gate_list) { if (gate->flags & MESH_PATH_ACTIVE) { mpath_dbg(sdata, "Forwarding to %pM\n", gate->dst); mesh_path_move_to_queue(gate, from_mpath, copy); @@ -781,7 +771,7 @@ int mesh_path_send_to_gates(struct mesh_path *mpath) } } - hlist_for_each_entry_rcu(gate, known_gates, gate_list) { + hlist_for_each_entry_rcu(gate, &tbl->known_gates, gate_list) { mpath_dbg(sdata, "Sending to %pM\n", gate->dst); mesh_path_tx_pending(gate); } -- cgit v1.2.3