2011-08-25 01:41:02

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 0/9] mesh fixes

A series of fixes and cleanups to the mesh stack.

Javier Cardona (8):
mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()
mac80211: Remove mesh paths when an interface is removed
mac80211: Improve mpath state locking
mac80211: Remove redundant mesh path expiration checks
mac80211: Don't iterate twice over all mpaths when once in sufficient
mac80211: Consolidate {mesh,mpp}_path_flush into one function
mac80211: Don't take the mesh path resize lock when deleting an mpath
mac80211: Consolidate mesh path duplicated functions

Pedro Larbig (1):
mac80211: Limit amount of HWMP frames and forwarded data packets in
queues on mesh interfaces

net/mac80211/cfg.c | 2 +-
net/mac80211/debugfs.c | 4 +
net/mac80211/ieee80211_i.h | 2 +
net/mac80211/iface.c | 6 ++
net/mac80211/mesh.h | 11 +++-
net/mac80211/mesh_hwmp.c | 21 +++++-
net/mac80211/mesh_pathtbl.c | 162 +++++++++++++++++++++++--------------------
net/mac80211/rx.c | 13 +++-
8 files changed, 139 insertions(+), 82 deletions(-)

--
1.7.4.1



2011-08-25 01:41:33

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 8/9] mac80211: Don't take the mesh path resize lock when deleting an mpath

From: Javier Cardona <[email protected]>

The mesh path resize lock is only needed to protect addition or removal
of buckets on the hash table, not nodes on those buckets.

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 9d9e1ac..4bfbe31 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -905,8 +905,8 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
int hash_idx;
int err = 0;

- read_lock_bh(&pathtbl_resize_lock);
- tbl = resize_dereference_mesh_paths();
+ rcu_read_lock();
+ tbl = rcu_dereference(mesh_paths);
hash_idx = mesh_table_hash(addr, sdata, tbl);
bucket = &tbl->hash_buckets[hash_idx];

@@ -924,7 +924,7 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
enddel:
mesh_paths_generation++;
spin_unlock_bh(&tbl->hashwlock[hash_idx]);
- read_unlock_bh(&pathtbl_resize_lock);
+ rcu_read_unlock();
return err;
}

--
1.7.4.1


2011-08-25 01:41:20

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 5/9] mac80211: Remove redundant mesh path expiration checks

From: Javier Cardona <[email protected]>

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 9 +++------
1 files changed, 3 insertions(+), 6 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 3c96e55..562b150 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -359,8 +359,7 @@ struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
if (MPATH_EXPIRED(mpath)) {
spin_lock_bh(&mpath->state_lock);
- if (MPATH_EXPIRED(mpath))
- mpath->flags &= ~MESH_PATH_ACTIVE;
+ mpath->flags &= ~MESH_PATH_ACTIVE;
spin_unlock_bh(&mpath->state_lock);
}
return mpath;
@@ -386,8 +385,7 @@ struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
if (MPATH_EXPIRED(mpath)) {
spin_lock_bh(&mpath->state_lock);
- if (MPATH_EXPIRED(mpath))
- mpath->flags &= ~MESH_PATH_ACTIVE;
+ mpath->flags &= ~MESH_PATH_ACTIVE;
spin_unlock_bh(&mpath->state_lock);
}
return mpath;
@@ -420,8 +418,7 @@ struct mesh_path *mesh_path_lookup_by_idx(int idx, struct ieee80211_sub_if_data
if (j++ == idx) {
if (MPATH_EXPIRED(node->mpath)) {
spin_lock_bh(&node->mpath->state_lock);
- if (MPATH_EXPIRED(node->mpath))
- node->mpath->flags &= ~MESH_PATH_ACTIVE;
+ node->mpath->flags &= ~MESH_PATH_ACTIVE;
spin_unlock_bh(&node->mpath->state_lock);
}
return node->mpath;
--
1.7.4.1


2011-08-25 18:21:59

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

On Thu, 25 Aug 2011 11:16:50 -0700, Javier Cardona wrote:
> On Wed, Aug 24, 2011 at 7:08 PM, Johannes Berg
> <[email protected]> wrote:
>> On Wed, 24 Aug 2011 18:40:44 -0700, Thomas Pedersen wrote:
>>
>>>                da = hdr->addr3;
>>>                ra = hdr->addr1;
>>> +               rcu_read_lock();
>>>                mpath = mesh_path_lookup(da, sdata);
>>> +               rcu_read_unlock();
>>>                if (mpath)
>>>                        sn = ++mpath->sn;
>>>                mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>>> skb->data,
>>
>> You've got to be kidding. Didn't I just explain RCU :)
>
> The patch was prepared before your RCU session :(
> Just to confirm I got it right before we resubmit: given that not
> only
> the path table accessed inside mesh_path_lookup() but also the mpaths
> themselves are RCU protected, the right fix should have been
>
> da = hdr->addr3;
> ra = hdr->addr1;
> + rcu_read_lock();
> mpath = mesh_path_lookup(da, sdata);
> if (mpath)
> sn = ++mpath->sn;
> + rcu_read_unlock();
> mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
> skb->data,
>
> Correct?

Frankly, I'm not sure, since you modify the mpath->sn you probably need
to hold a real lock, otherwise ++mpath->sn can race against itself in
this very function.

johannes

2011-08-25 17:46:58

by Javier Cardona

[permalink] [raw]
Subject: Re: [PATCH 2/9] mac80211: Limit amount of HWMP frames and forwarded data packets in queues on mesh interfaces

On Wed, Aug 24, 2011 at 10:08 PM, Johannes Berg
<[email protected]> wrote:
> On Wed, 2011-08-24 at 18:40 -0700, Thomas Pedersen wrote:
>> From: Pedro Larbig <[email protected]>
>>
>> To avoid contention problems in a mesh network's high load areas, this patch
>> adds a 2-stage packet dropping mechanism:
>> * If the transmit queue for HWMP frames is filled with 256 or more packets,
>> additional HWMP frames will be dropped
>> * If the transmit queue for forwarded packets is at 384 or more, drop those,
>> too
>
>> + ? ? /* Frames going through ieee80211_tx_skb will be on the voice queue,
>> + ? ? ?* Therefor we need to check only IEEE80211_AC_VO */
>> + ? ? if (unlikely(skb_queue_len(&local->pending[IEEE80211_AC_VO]) >=
>> + ? ? ? ?MESH_MGMT_QUEUE_LEN)) {
>> + ? ? ? ? ? ? kfree_skb(skb);
>> + ? ? ? ? ? ? I802_DEBUG_INC(local->tx_handlers_drop_mesh_mgmt);
>> + ? ? ? ? ? ? return;
>> + ? ? }
>
> I still don't think this should be done. If the HW queue is full, we
> will get a stop_queue from the driver, this could also tell mesh to stop
> forwarding or so.

Oh, I see, ieee80211_stop_queue().

Thanks!

Javier

--
Javier Cardona
cozybit Inc.
http://www.cozybit.com

2011-08-27 00:18:27

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 1/8] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

Reported by Pedro Larbig (ASPj)

Signed-off-by: Javier Cardona <[email protected]>

---
v2: - Extend the rcu_read_lock section to protect mpath (Johannes)
- Take state lock when increasing mpath serial number (Johannes)
net/mac80211/mesh_pathtbl.c | 7 ++++++-
1 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 3c2bcb2..c92fd70 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -991,9 +991,14 @@ void mesh_path_discard_frame(struct sk_buff *skb,

da = hdr->addr3;
ra = hdr->addr1;
+ rcu_read_lock();
mpath = mesh_path_lookup(da, sdata);
- if (mpath)
+ if (mpath) {
+ spin_lock_bh(&mpath->state_lock);
sn = ++mpath->sn;
+ spin_unlock_bh(&mpath->state_lock);
+ }
+ rcu_read_unlock();
mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl, skb->data,
cpu_to_le32(sn), reason, ra, sdata);
}
--
1.7.6


2011-08-25 02:08:17

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

On Wed, 24 Aug 2011 18:40:44 -0700, Thomas Pedersen wrote:

> da = hdr->addr3;
> ra = hdr->addr1;
> + rcu_read_lock();
> mpath = mesh_path_lookup(da, sdata);
> + rcu_read_unlock();
> if (mpath)
> sn = ++mpath->sn;
> mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl, skb->data,

You've got to be kidding. Didn't I just explain RCU :)

johannes

2011-08-25 01:41:09

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 2/9] mac80211: Limit amount of HWMP frames and forwarded data packets in queues on mesh interfaces

From: Pedro Larbig <[email protected]>

To avoid contention problems in a mesh network's high load areas, this patch
adds a 2-stage packet dropping mechanism:
* If the transmit queue for HWMP frames is filled with 256 or more packets,
additional HWMP frames will be dropped
* If the transmit queue for forwarded packets is at 384 or more, drop those,
too

This way, if a node runs into contention issues, it first reduces the amount
of HWMP messages, and only if this is not enough, starts also dropping data
packets from other nodes.

So, instead of eating up memory and crashing, a node does only behave selfish
in such situations.
This patch has been tested several hours in a 20-node testbed under heavy
iperf load.

Signed-off-by: Pedro Larbig <[email protected]>
Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/debugfs.c | 4 ++++
net/mac80211/ieee80211_i.h | 2 ++
net/mac80211/mesh.h | 5 +++++
net/mac80211/mesh_hwmp.c | 21 +++++++++++++++++++--
net/mac80211/rx.c | 13 ++++++++++++-
5 files changed, 42 insertions(+), 3 deletions(-)

diff --git a/net/mac80211/debugfs.c b/net/mac80211/debugfs.c
index 186e02f..8aefd2e 100644
--- a/net/mac80211/debugfs.c
+++ b/net/mac80211/debugfs.c
@@ -496,6 +496,10 @@ void debugfs_hw_add(struct ieee80211_local *local)
local->tx_handlers_drop_not_assoc);
DEBUGFS_STATS_ADD(tx_handlers_drop_unauth_port,
local->tx_handlers_drop_unauth_port);
+ DEBUGFS_STATS_ADD(tx_handlers_drop_mesh_mgmt,
+ local->tx_handlers_drop_mesh_mgmt);
+ DEBUGFS_STATS_ADD(tx_handlers_drop_mesh_fwd,
+ local->tx_handlers_drop_mesh_fwd);
DEBUGFS_STATS_ADD(rx_handlers_drop, local->rx_handlers_drop);
DEBUGFS_STATS_ADD(rx_handlers_queued, local->rx_handlers_queued);
DEBUGFS_STATS_ADD(rx_handlers_drop_nullfunc,
diff --git a/net/mac80211/ieee80211_i.h b/net/mac80211/ieee80211_i.h
index c204cee..12ad787 100644
--- a/net/mac80211/ieee80211_i.h
+++ b/net/mac80211/ieee80211_i.h
@@ -922,6 +922,8 @@ struct ieee80211_local {
unsigned int tx_handlers_drop_wep;
unsigned int tx_handlers_drop_not_assoc;
unsigned int tx_handlers_drop_unauth_port;
+ unsigned int tx_handlers_drop_mesh_mgmt;
+ unsigned int tx_handlers_drop_mesh_fwd;
unsigned int rx_handlers_drop;
unsigned int rx_handlers_queued;
unsigned int rx_handlers_drop_nullfunc;
diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h
index 2027207..6b57b11 100644
--- a/net/mac80211/mesh.h
+++ b/net/mac80211/mesh.h
@@ -186,6 +186,11 @@ struct mesh_rmc {
/* Maximum number of paths per interface */
#define MESH_MAX_MPATHS 1024

+/* Maximum number of data frames to be forwarded in tx queue */
+#define MESH_MAX_FWDING_QUEUE 384
+/* Maximum number of HWMP management frames in tx queue */
+#define MESH_MGMT_QUEUE_LEN 256
+
/* Public interfaces */
/* Various */
int ieee80211_fill_mesh_addresses(struct ieee80211_hdr *hdr, __le16 *fc,
diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index fd4f76a..f09e5e8 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -105,6 +105,23 @@ enum mpath_frame_type {

static const u8 broadcast_addr[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};

+static void mesh_tx_skb(struct ieee80211_sub_if_data *sdata,
+ struct sk_buff *skb)
+{
+ struct ieee80211_local *local = sdata->local;
+
+ /* Frames going through ieee80211_tx_skb will be on the voice queue,
+ * Therefor we need to check only IEEE80211_AC_VO */
+ if (unlikely(skb_queue_len(&local->pending[IEEE80211_AC_VO]) >=
+ MESH_MGMT_QUEUE_LEN)) {
+ kfree_skb(skb);
+ I802_DEBUG_INC(local->tx_handlers_drop_mesh_mgmt);
+ return;
+ }
+
+ ieee80211_tx_skb(sdata, skb);
+}
+
static int mesh_path_sel_frame_tx(enum mpath_frame_type action, u8 flags,
u8 *orig_addr, __le32 orig_sn, u8 target_flags, u8 *target,
__le32 target_sn, const u8 *da, u8 hop_count, u8 ttl,
@@ -198,7 +215,7 @@ static int mesh_path_sel_frame_tx(enum mpath_frame_type action, u8 flags,
pos += 4;
}

- ieee80211_tx_skb(sdata, skb);
+ mesh_tx_skb(sdata, skb);
return 0;
}

@@ -263,7 +280,7 @@ int mesh_path_error_tx(u8 ttl, u8 *target, __le32 target_sn,
pos += 4;
memcpy(pos, &target_rcode, 2);

- ieee80211_tx_skb(sdata, skb);
+ mesh_tx_skb(sdata, skb);
return 0;
}

diff --git a/net/mac80211/rx.c b/net/mac80211/rx.c
index c4453fd..9b5daa1 100644
--- a/net/mac80211/rx.c
+++ b/net/mac80211/rx.c
@@ -1817,7 +1817,7 @@ ieee80211_rx_h_mesh_fwding(struct ieee80211_rx_data *rx)
{
struct ieee80211_hdr *hdr;
struct ieee80211s_hdr *mesh_hdr;
- unsigned int hdrlen;
+ unsigned int hdrlen, q;
struct sk_buff *skb = rx->skb, *fwd_skb;
struct ieee80211_local *local = rx->local;
struct ieee80211_sub_if_data *sdata = rx->sdata;
@@ -1915,6 +1915,17 @@ ieee80211_rx_h_mesh_fwding(struct ieee80211_rx_data *rx)
}
IEEE80211_IFSTA_MESH_CTR_INC(&sdata->u.mesh,
fwded_frames);
+
+ /* Check selected queue's size and drop if full */
+ q = skb_get_queue_mapping(fwd_skb);
+ if (unlikely(skb_queue_len(&local->pending[q]) >=
+ MESH_MAX_FWDING_QUEUE)) {
+ kfree_skb(fwd_skb);
+ I802_DEBUG_INC(local->
+ tx_handlers_drop_mesh_fwd);
+ return RX_DROP_MONITOR;
+ }
+
ieee80211_add_pending_skb(local, fwd_skb);
}
}
--
1.7.4.1


2011-08-29 18:36:38

by Javier Cardona

[permalink] [raw]
Subject: Re: [PATCH v2 6/8] mac80211: Consolidate {mesh,mpp}_path_flush into one function

On Mon, Aug 29, 2011 at 6:49 AM, Johannes Berg
<[email protected]> wrote:
> On Fri, 2011-08-26 at 17:18 -0700, Javier Cardona wrote:
>> Signed-off-by: Javier Cardona <[email protected]>
>>
>> ---
>> v2: - Fix extra space (checkpatch)
>> ? ? - Add lockdep check for RCU
>> ?net/mac80211/mesh_pathtbl.c | ? 65 +++++++++++++++++-------------------------
>> ?1 files changed, 26 insertions(+), 39 deletions(-)
>>
>> diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
>> index ea9e34a..3c03be9 100644
>> --- a/net/mac80211/mesh_pathtbl.c
>> +++ b/net/mac80211/mesh_pathtbl.c
>> @@ -790,35 +790,6 @@ void mesh_plink_broken(struct sta_info *sta)
>> ? ? ? rcu_read_unlock();
>> ?}
>>
>> -/**
>> - * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
>> - *
>> - * @sta - mesh peer to match
>> - *
>> - * RCU notes: this function is called when a mesh plink transitions from
>> - * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
>> - * allows path creation. This will happen before the sta can be freed (because
>> - * sta_info_destroy() calls this) so any reader in a rcu read block will be
>> - * protected against the plink disappearing.
>> - */
>> -void mesh_path_flush_by_nexthop(struct sta_info *sta)
>> -{
>> - ? ? struct mesh_table *tbl;
>> - ? ? struct mesh_path *mpath;
>> - ? ? struct mpath_node *node;
>> - ? ? struct hlist_node *p;
>> - ? ? int i;
>> -
>> - ? ? rcu_read_lock();
>> - ? ? tbl = rcu_dereference(mesh_paths);
>> - ? ? for_each_mesh_entry(tbl, p, node, i) {
>> - ? ? ? ? ? ? mpath = node->mpath;
>> - ? ? ? ? ? ? if (rcu_dereference(mpath->next_hop) == sta)
>> - ? ? ? ? ? ? ? ? ? ? mesh_path_del(mpath->dst, mpath->sdata);
>> - ? ? }
>> - ? ? rcu_read_unlock();
>> -}
>> -
>> ?static void mesh_path_node_reclaim(struct rcu_head *rp)
>> ?{
>> ? ? ? struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
>> @@ -845,7 +816,18 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
>> ? ? ? atomic_dec(&tbl->entries);
>> ?}
>>
>> -static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
>> +/**
>> + * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
>> + *
>> + * @sta - mesh peer to match
>> + *
>> + * RCU notes: this function is called when a mesh plink transitions from
>> + * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
>> + * allows path creation. This will happen before the sta can be freed (because
>> + * sta_info_destroy() calls this) so any reader in a rcu read block will be
>> + * protected against the plink disappearing.
>> + */
>> +void mesh_path_flush_by_nexthop(struct sta_info *sta)
>> ?{
>> ? ? ? struct mesh_table *tbl;
>> ? ? ? struct mesh_path *mpath;
>> @@ -857,7 +839,7 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
>> ? ? ? tbl = rcu_dereference(mesh_paths);
>> ? ? ? for_each_mesh_entry(tbl, p, node, i) {
>> ? ? ? ? ? ? ? mpath = node->mpath;
>> - ? ? ? ? ? ? if (mpath->sdata == sdata) {
>> + ? ? ? ? ? ? if (rcu_dereference(mpath->next_hop) == sta) {
>> ? ? ? ? ? ? ? ? ? ? ? spin_lock_bh(&tbl->hashwlock[i]);
>> ? ? ? ? ? ? ? ? ? ? ? __mesh_path_del(tbl, node);
>> ? ? ? ? ? ? ? ? ? ? ? spin_unlock_bh(&tbl->hashwlock[i]);
>> @@ -866,24 +848,23 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
>> ? ? ? rcu_read_unlock();
>> ?}
>>
>> -static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
>> +static void table_flush_by_iface(struct mesh_table *tbl,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?struct ieee80211_sub_if_data *sdata)
>> ?{
>> - ? ? struct mesh_table *tbl;
>> ? ? ? struct mesh_path *mpath;
>> ? ? ? struct mpath_node *node;
>> ? ? ? struct hlist_node *p;
>> ? ? ? int i;
>>
>> - ? ? read_lock_bh(&pathtbl_resize_lock);
>> - ? ? tbl = rcu_dereference_protected(mpp_paths,
>> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? lockdep_is_held(pathtbl_resize_lock));
>> + ? ? WARN_ON(!rcu_read_lock_held());
>> ? ? ? for_each_mesh_entry(tbl, p, 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]);
>> ? ? ? }
>> - ? ? read_unlock_bh(&pathtbl_resize_lock);
>> ?}
>
> So what protects against the table being grown at the same time? A copy
> will be made, but here you'll be iterating the old table -- which won't
> crash or anything but is semantically incorrect.

You are right. And I believe it actually may crash, given that the
nodes we wanted to delete will still exist in the new table. I'll
re-spin right away.

Thanks!

2011-08-25 01:41:07

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

From: Javier Cardona <[email protected]>

Reported by Pedro Larbig (ASPj)

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 2 ++
1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 3c2bcb2..ee35f75 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -991,7 +991,9 @@ void mesh_path_discard_frame(struct sk_buff *skb,

da = hdr->addr3;
ra = hdr->addr1;
+ rcu_read_lock();
mpath = mesh_path_lookup(da, sdata);
+ rcu_read_unlock();
if (mpath)
sn = ++mpath->sn;
mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl, skb->data,
--
1.7.4.1


2011-08-25 01:41:38

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 9/9] mac80211: Consolidate mesh path duplicated functions

From: Javier Cardona <[email protected]>

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 52 ++++++++++++++-----------------------------
1 files changed, 17 insertions(+), 35 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 4bfbe31..4891cf1 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -335,25 +335,14 @@ static void mesh_path_move_to_queue(struct mesh_path *gate_mpath,
}


-/**
- * mesh_path_lookup - look up a path in the mesh path table
- * @dst: hardware address (ETH_ALEN length) of destination
- * @sdata: local subif
- *
- * Returns: pointer to the mesh path structure, or NULL if not found
- *
- * Locking: must be called within a read rcu section.
- */
-struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
+static struct mesh_path *path_lookup(struct mesh_table *tbl, u8 *dst,
+ struct ieee80211_sub_if_data *sdata)
{
struct mesh_path *mpath;
struct hlist_node *n;
struct hlist_head *bucket;
- struct mesh_table *tbl;
struct mpath_node *node;

- tbl = rcu_dereference(mesh_paths);
-
bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
hlist_for_each_entry_rcu(node, n, bucket, list) {
mpath = node->mpath;
@@ -370,30 +359,23 @@ struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
return NULL;
}

-struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
+/**
+ * mesh_path_lookup - look up a path in the mesh path table
+ * @dst: hardware address (ETH_ALEN length) of destination
+ * @sdata: local subif
+ *
+ * Returns: pointer to the mesh path structure, or NULL if not found
+ *
+ * Locking: must be called within a read rcu section.
+ */
+struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
{
- struct mesh_path *mpath;
- struct hlist_node *n;
- struct hlist_head *bucket;
- struct mesh_table *tbl;
- struct mpath_node *node;
-
- tbl = rcu_dereference(mpp_paths);
+ return path_lookup(rcu_dereference(mesh_paths), dst, sdata);
+}

- bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
- hlist_for_each_entry_rcu(node, n, bucket, list) {
- mpath = node->mpath;
- if (mpath->sdata == sdata &&
- memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
- if (MPATH_EXPIRED(mpath)) {
- spin_lock_bh(&mpath->state_lock);
- mpath->flags &= ~MESH_PATH_ACTIVE;
- spin_unlock_bh(&mpath->state_lock);
- }
- return mpath;
- }
- }
- return NULL;
+struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
+{
+ return path_lookup(rcu_dereference(mpp_paths), dst, sdata);
}


--
1.7.4.1


2011-08-27 00:18:35

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 3/8] mac80211: Improve mpath state locking

No need to take the mpath state lock when an mpath is removed.
Also, no need checking the lock when reading mpath flags.

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh.h | 4 +++-
net/mac80211/mesh_pathtbl.c | 14 ++++----------
2 files changed, 7 insertions(+), 11 deletions(-)

diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h
index 57a2ad0..7118e8e 100644
--- a/net/mac80211/mesh.h
+++ b/net/mac80211/mesh.h
@@ -80,7 +80,9 @@ enum mesh_deferred_task_flags {
* retry
* @discovery_retries: number of discovery retries
* @flags: mesh path flags, as specified on &enum mesh_path_flags
- * @state_lock: mesh path state lock
+ * @state_lock: mesh path state lock used to protect changes to the
+ * mpath itself. No need to take this lock when adding or removing
+ * an mpath to a hash bucket on a path table.
* @is_gate: the destination station of this path is a mesh gate
*
*
diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 1c8c420..b895a7c 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -776,18 +776,17 @@ void mesh_plink_broken(struct sta_info *sta)
tbl = rcu_dereference(mesh_paths);
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- spin_lock_bh(&mpath->state_lock);
if (rcu_dereference(mpath->next_hop) == sta &&
mpath->flags & MESH_PATH_ACTIVE &&
!(mpath->flags & MESH_PATH_FIXED)) {
+ spin_lock_bh(&mpath->state_lock);
mpath->flags &= ~MESH_PATH_ACTIVE;
++mpath->sn;
spin_unlock_bh(&mpath->state_lock);
mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
mpath->dst, cpu_to_le32(mpath->sn),
reason, bcast, sdata);
- } else
- spin_unlock_bh(&mpath->state_lock);
+ }
}
rcu_read_unlock();
}
@@ -866,7 +865,7 @@ static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
if (mpath->sdata != sdata)
continue;
spin_lock_bh(&tbl->hashwlock[i]);
- spin_lock_bh(&mpath->state_lock);
+ hlist_del_rcu(&node->list);
call_rcu(&node->rcu, mesh_path_node_reclaim);
atomic_dec(&tbl->entries);
spin_unlock_bh(&tbl->hashwlock[i]);
@@ -1160,15 +1159,10 @@ void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
if (node->mpath->sdata != sdata)
continue;
mpath = node->mpath;
- spin_lock_bh(&mpath->state_lock);
if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
(!(mpath->flags & MESH_PATH_FIXED)) &&
- time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) {
- spin_unlock_bh(&mpath->state_lock);
+ time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
mesh_path_del(mpath->dst, mpath->sdata);
- } else
- spin_unlock_bh(&mpath->state_lock);
- }
rcu_read_unlock();
}

--
1.7.6


2011-08-27 00:18:43

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 7/8] mac80211: Don't take the mesh path resize lock when deleting an mpath

The mesh path resize lock is only needed to protect addition or removal
of buckets on the hash table, not nodes on those buckets.

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 3c03be9..216bd2f 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -905,8 +905,8 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
int hash_idx;
int err = 0;

- read_lock_bh(&pathtbl_resize_lock);
- tbl = resize_dereference_mesh_paths();
+ rcu_read_lock();
+ tbl = rcu_dereference(mesh_paths);
hash_idx = mesh_table_hash(addr, sdata, tbl);
bucket = &tbl->hash_buckets[hash_idx];

@@ -924,7 +924,7 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
enddel:
mesh_paths_generation++;
spin_unlock_bh(&tbl->hashwlock[hash_idx]);
- read_unlock_bh(&pathtbl_resize_lock);
+ rcu_read_unlock();
return err;
}

--
1.7.6


2011-08-25 19:05:09

by Javier Cardona

[permalink] [raw]
Subject: Re: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

On Thu, Aug 25, 2011 at 11:48 AM, Johannes Berg
<[email protected]> wrote:
> On Thu, 25 Aug 2011 11:45:11 -0700, Javier Cardona wrote:
>>
>> On Thu, Aug 25, 2011 at 11:21 AM, Johannes Berg
>> <[email protected]> wrote:
>>>
>>> On Thu, 25 Aug 2011 11:16:50 -0700, Javier Cardona wrote:
>>>>
>>>> On Wed, Aug 24, 2011 at 7:08 PM, Johannes Berg
>>>> <[email protected]> wrote:
>>>>>
>>>>> On Wed, 24 Aug 2011 18:40:44 -0700, Thomas Pedersen wrote:
>>>>>
>>>>>> ? ? ? ? ? ? ? ?da = hdr->addr3;
>>>>>> ? ? ? ? ? ? ? ?ra = hdr->addr1;
>>>>>> + ? ? ? ? ? ? ? rcu_read_lock();
>>>>>> ? ? ? ? ? ? ? ?mpath = mesh_path_lookup(da, sdata);
>>>>>> + ? ? ? ? ? ? ? rcu_read_unlock();
>>>>>> ? ? ? ? ? ? ? ?if (mpath)
>>>>>> ? ? ? ? ? ? ? ? ? ? ? ?sn = ++mpath->sn;
>>>>>> ? ? ? ? ? ? ? ?mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>>>>>> skb->data,
>>>>>
>>>>> You've got to be kidding. Didn't I just explain RCU :)
>>>>
>>>> The patch was prepared before your RCU session :(
>>>> Just to confirm I got it right before we resubmit: given that not only
>>>> the path table accessed inside mesh_path_lookup() but also the mpaths
>>>> themselves are RCU protected, the right fix should have been
>>>>
>>>> ? ? ? ? ? ? ? da = hdr->addr3;
>>>> ? ? ? ? ? ? ? ra = hdr->addr1;
>>>> + ? ? ? ? ? ? rcu_read_lock();
>>>> ? ? ? ? ? ? ? mpath = mesh_path_lookup(da, sdata);
>>>> ? ? ? ? ? ? ? if (mpath)
>>>> ? ? ? ? ? ? ? ? ? ? ? sn = ++mpath->sn;
>>>> + ? ? ? ? ? ? rcu_read_unlock();
>>>> ? ? ? ? ? ? ? mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>>>> skb->data,
>>>>
>>>> Correct?
>>>
>>> Frankly, I'm not sure, since you modify the mpath->sn you probably need
>>> to
>>> hold a real lock, otherwise ++mpath->sn can race against itself in this
>>> very
>>> function.
>>
>> Oh, I see. ?That's a different issue from what I was originally trying
>> to fix (unprotected access to the path table inside the lookup
>> function). ?But you are completely right. ?Changing the math sequence
>> number requires taking the mpath state lock:
>>
>> ? ? ? ? ? ? da = hdr->addr3;
>> ? ? ? ? ? ? ra = hdr->addr1;
>> + ? ? ? ? ? rcu_read_lock();
>> ? ? ? ? ? ? mpath = mesh_path_lookup(da, sdata);
>> - ? ? ? ? ? ? if (mpath)
>> + ? ? ? ? ? ? if (mpath) {
>> + ? ? ? ? ? ? ? ? ? ?spin_lock_bh(&mpath->state_lock);
>> ? ? ? ? ? ? ? ? ? ? ?sn = ++mpath->sn;
>> + ? ? ? ? ? ? ? ? ? ?spin_unlock_bh(&mpath->state_lock);
>> + ? ? ? ? ? }
>> + ? ? ? ? ? rcu_read_unlock();
>> ? ? ? ? ? ? mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>> skb->data,
>
> Seems about right to me, but I don't know about all the locking :)

After your RCU session I went back to the path table module and
reviewed the locking. That's what triggered some the patches on the
set:
http://thread.gmane.org/gmane.linux.kernel.wireless.general/75812/focus=75816
http://thread.gmane.org/gmane.linux.kernel.wireless.general/75812/focus=75818
http://thread.gmane.org/gmane.linux.kernel.wireless.general/75812/focus=75820

Mesh path tables and mpaths are protected by RCU.
The internal state of each mpath is protected by mpath->state_lock.
And there's a lock for each bucket on the mesh path tables.

Thanks!

Javier

2011-08-29 18:38:57

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH v2 6/8] mac80211: Consolidate {mesh,mpp}_path_flush into one function

On Mon, 2011-08-29 at 11:36 -0700, Javier Cardona wrote:

> >> - read_lock_bh(&pathtbl_resize_lock);
> >> - tbl = rcu_dereference_protected(mpp_paths,
> >> - lockdep_is_held(pathtbl_resize_lock));
> >> + WARN_ON(!rcu_read_lock_held());
> >> for_each_mesh_entry(tbl, p, 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]);
> >> }
> >> - read_unlock_bh(&pathtbl_resize_lock);
> >> }
> >
> > So what protects against the table being grown at the same time? A copy
> > will be made, but here you'll be iterating the old table -- which won't
> > crash or anything but is semantically incorrect.
>
> You are right. And I believe it actually may crash, given that the
> nodes we wanted to delete will still exist in the new table. I'll
> re-spin right away.

Yes, it will crash just as before -- I was referring to this function
only. Due to RCU, this function will always have a valid "node" pointer,
but of course deleting that might not delete it from the right table...

johannes


2011-08-27 00:18:39

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 5/8] mac80211: Don't iterate twice over all mpaths when once in sufficient

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 64 +++++++++++++++++++++++++------------------
1 files changed, 37 insertions(+), 27 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 598249e..ea9e34a 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -49,7 +49,9 @@ int mesh_paths_generation;

/* This lock will have the grow table function as writer and add / delete nodes
* as readers. When reading the table (i.e. doing lookups) we are well protected
- * by RCU
+ * by RCU. We need to take this lock when modying the number of buckets
+ * on one of the path tables but we don't need to if adding or removing mpaths
+ * from hash buckets.
*/
static DEFINE_RWLOCK(pathtbl_resize_lock);

@@ -817,6 +819,32 @@ void mesh_path_flush_by_nexthop(struct sta_info *sta)
rcu_read_unlock();
}

+static void mesh_path_node_reclaim(struct rcu_head *rp)
+{
+ struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
+ struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
+
+ del_timer_sync(&node->mpath->timer);
+ atomic_dec(&sdata->u.mesh.mpaths);
+ kfree(node->mpath);
+ kfree(node);
+}
+
+/* needs to be called with the corresponding hashwlock taken */
+static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
+{
+ struct mesh_path *mpath;
+ mpath = node->mpath;
+ spin_lock(&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);
+ atomic_dec(&tbl->entries);
+}
+
static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
{
struct mesh_table *tbl;
@@ -829,23 +857,15 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
tbl = rcu_dereference(mesh_paths);
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- if (mpath->sdata == sdata)
- mesh_path_del(mpath->dst, mpath->sdata);
+ if (mpath->sdata == sdata) {
+ spin_lock_bh(&tbl->hashwlock[i]);
+ __mesh_path_del(tbl, node);
+ spin_unlock_bh(&tbl->hashwlock[i]);
+ }
}
rcu_read_unlock();
}

-static void mesh_path_node_reclaim(struct rcu_head *rp)
-{
- struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
- struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
-
- del_timer_sync(&node->mpath->timer);
- atomic_dec(&sdata->u.mesh.mpaths);
- kfree(node->mpath);
- kfree(node);
-}
-
static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
{
struct mesh_table *tbl;
@@ -859,12 +879,8 @@ static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
lockdep_is_held(pathtbl_resize_lock));
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- if (mpath->sdata != sdata)
- continue;
spin_lock_bh(&tbl->hashwlock[i]);
- hlist_del_rcu(&node->list);
- call_rcu(&node->rcu, mesh_path_node_reclaim);
- atomic_dec(&tbl->entries);
+ __mesh_path_del(tbl, node);
spin_unlock_bh(&tbl->hashwlock[i]);
}
read_unlock_bh(&pathtbl_resize_lock);
@@ -912,14 +928,7 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
mpath = node->mpath;
if (mpath->sdata == sdata &&
memcmp(addr, mpath->dst, ETH_ALEN) == 0) {
- spin_lock_bh(&mpath->state_lock);
- if (mpath->is_gate)
- mesh_gate_del(tbl, mpath);
- mpath->flags |= MESH_PATH_RESOLVING;
- hlist_del_rcu(&node->list);
- call_rcu(&node->rcu, mesh_path_node_reclaim);
- atomic_dec(&tbl->entries);
- spin_unlock_bh(&mpath->state_lock);
+ __mesh_path_del(tbl, node);
goto enddel;
}
}
@@ -1160,6 +1169,7 @@ void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
(!(mpath->flags & MESH_PATH_FIXED)) &&
time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
mesh_path_del(mpath->dst, mpath->sdata);
+ }
rcu_read_unlock();
}

--
1.7.6


2011-08-25 05:08:05

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH 2/9] mac80211: Limit amount of HWMP frames and forwarded data packets in queues on mesh interfaces

On Wed, 2011-08-24 at 18:40 -0700, Thomas Pedersen wrote:
> From: Pedro Larbig <[email protected]>
>
> To avoid contention problems in a mesh network's high load areas, this patch
> adds a 2-stage packet dropping mechanism:
> * If the transmit queue for HWMP frames is filled with 256 or more packets,
> additional HWMP frames will be dropped
> * If the transmit queue for forwarded packets is at 384 or more, drop those,
> too

> + /* Frames going through ieee80211_tx_skb will be on the voice queue,
> + * Therefor we need to check only IEEE80211_AC_VO */
> + if (unlikely(skb_queue_len(&local->pending[IEEE80211_AC_VO]) >=
> + MESH_MGMT_QUEUE_LEN)) {
> + kfree_skb(skb);
> + I802_DEBUG_INC(local->tx_handlers_drop_mesh_mgmt);
> + return;
> + }

I still don't think this should be done. If the HW queue is full, we
will get a stop_queue from the driver, this could also tell mesh to stop
forwarding or so.

johannes


2011-08-25 18:45:31

by Javier Cardona

[permalink] [raw]
Subject: Re: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

On Thu, Aug 25, 2011 at 11:21 AM, Johannes Berg
<[email protected]> wrote:
> On Thu, 25 Aug 2011 11:16:50 -0700, Javier Cardona wrote:
>>
>> On Wed, Aug 24, 2011 at 7:08 PM, Johannes Berg
>> <[email protected]> wrote:
>>>
>>> On Wed, 24 Aug 2011 18:40:44 -0700, Thomas Pedersen wrote:
>>>
>>>> ? ? ? ? ? ? ? ?da = hdr->addr3;
>>>> ? ? ? ? ? ? ? ?ra = hdr->addr1;
>>>> + ? ? ? ? ? ? ? rcu_read_lock();
>>>> ? ? ? ? ? ? ? ?mpath = mesh_path_lookup(da, sdata);
>>>> + ? ? ? ? ? ? ? rcu_read_unlock();
>>>> ? ? ? ? ? ? ? ?if (mpath)
>>>> ? ? ? ? ? ? ? ? ? ? ? ?sn = ++mpath->sn;
>>>> ? ? ? ? ? ? ? ?mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>>>> skb->data,
>>>
>>> You've got to be kidding. Didn't I just explain RCU :)
>>
>> The patch was prepared before your RCU session :(
>> Just to confirm I got it right before we resubmit: given that not only
>> the path table accessed inside mesh_path_lookup() but also the mpaths
>> themselves are RCU protected, the right fix should have been
>>
>> ? ? ? ? ? ? ? da = hdr->addr3;
>> ? ? ? ? ? ? ? ra = hdr->addr1;
>> + ? ? ? ? ? ? rcu_read_lock();
>> ? ? ? ? ? ? ? mpath = mesh_path_lookup(da, sdata);
>> ? ? ? ? ? ? ? if (mpath)
>> ? ? ? ? ? ? ? ? ? ? ? sn = ++mpath->sn;
>> + ? ? ? ? ? ? rcu_read_unlock();
>> ? ? ? ? ? ? ? mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>> skb->data,
>>
>> Correct?
>
> Frankly, I'm not sure, since you modify the mpath->sn you probably need to
> hold a real lock, otherwise ++mpath->sn can race against itself in this very
> function.

Oh, I see. That's a different issue from what I was originally trying
to fix (unprotected access to the path table inside the lookup
function). But you are completely right. Changing the math sequence
number requires taking the mpath state lock:

da = hdr->addr3;
ra = hdr->addr1;
+ rcu_read_lock();
mpath = mesh_path_lookup(da, sdata);
- if (mpath)
+ if (mpath) {
+ spin_lock_bh(&mpath->state_lock);
sn = ++mpath->sn;
+ spin_unlock_bh(&mpath->state_lock);
+ }
+ rcu_read_unlock();
mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl, skb->data,

Thanks,

Javier

2011-08-25 01:41:28

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 7/9] mac80211: Consolidate {mesh,mpp}_path_flush into one function

From: Javier Cardona <[email protected]>

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 65 +++++++++++++++++-------------------------
1 files changed, 26 insertions(+), 39 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index e941de2..9d9e1ac 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -790,35 +790,6 @@ void mesh_plink_broken(struct sta_info *sta)
rcu_read_unlock();
}

-/**
- * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
- *
- * @sta - mesh peer to match
- *
- * RCU notes: this function is called when a mesh plink transitions from
- * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
- * allows path creation. This will happen before the sta can be freed (because
- * sta_info_destroy() calls this) so any reader in a rcu read block will be
- * protected against the plink disappearing.
- */
-void mesh_path_flush_by_nexthop(struct sta_info *sta)
-{
- struct mesh_table *tbl;
- struct mesh_path *mpath;
- struct mpath_node *node;
- struct hlist_node *p;
- int i;
-
- rcu_read_lock();
- tbl = rcu_dereference(mesh_paths);
- for_each_mesh_entry(tbl, p, node, i) {
- mpath = node->mpath;
- if (rcu_dereference(mpath->next_hop) == sta)
- mesh_path_del(mpath->dst, mpath->sdata);
- }
- rcu_read_unlock();
-}
-
static void mesh_path_node_reclaim(struct rcu_head *rp)
{
struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
@@ -845,7 +816,18 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
atomic_dec(&tbl->entries);
}

-static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
+/**
+ * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
+ *
+ * @sta - mesh peer to match
+ *
+ * RCU notes: this function is called when a mesh plink transitions from
+ * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
+ * allows path creation. This will happen before the sta can be freed (because
+ * sta_info_destroy() calls this) so any reader in a rcu read block will be
+ * protected against the plink disappearing.
+ */
+void mesh_path_flush_by_nexthop(struct sta_info *sta)
{
struct mesh_table *tbl;
struct mesh_path *mpath;
@@ -857,7 +839,7 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
tbl = rcu_dereference(mesh_paths);
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- if (mpath->sdata == sdata) {
+ if (rcu_dereference(mpath->next_hop) == sta) {
spin_lock_bh(&tbl->hashwlock[i]);
__mesh_path_del(tbl, node);
spin_unlock_bh(&tbl->hashwlock[i]);
@@ -866,24 +848,23 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
rcu_read_unlock();
}

-static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
+/* Needs to be called with the rcu read lock taken */
+static void table_flush_by_iface(struct mesh_table *tbl,
+ struct ieee80211_sub_if_data *sdata)
{
- struct mesh_table *tbl;
struct mesh_path *mpath;
struct mpath_node *node;
struct hlist_node *p;
int i;

- read_lock_bh(&pathtbl_resize_lock);
- tbl = rcu_dereference_protected(mpp_paths,
- lockdep_is_held(pathtbl_resize_lock));
for_each_mesh_entry(tbl, p, 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]);
}
- read_unlock_bh(&pathtbl_resize_lock);
}

/**
@@ -896,8 +877,14 @@ static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
*/
void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
{
- mesh_path_flush(sdata);
- mpp_path_flush(sdata);
+ struct mesh_table *tbl;
+
+ rcu_read_lock();
+ tbl = rcu_dereference(mesh_paths);
+ table_flush_by_iface(tbl, sdata);
+ tbl = rcu_dereference(mpp_paths);
+ table_flush_by_iface(tbl, sdata);
+ rcu_read_unlock();
}

/**
--
1.7.4.1


2011-08-29 13:49:10

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH v2 6/8] mac80211: Consolidate {mesh,mpp}_path_flush into one function

On Fri, 2011-08-26 at 17:18 -0700, Javier Cardona wrote:
> Signed-off-by: Javier Cardona <[email protected]>
>
> ---
> v2: - Fix extra space (checkpatch)
> - Add lockdep check for RCU
> net/mac80211/mesh_pathtbl.c | 65 +++++++++++++++++-------------------------
> 1 files changed, 26 insertions(+), 39 deletions(-)
>
> diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
> index ea9e34a..3c03be9 100644
> --- a/net/mac80211/mesh_pathtbl.c
> +++ b/net/mac80211/mesh_pathtbl.c
> @@ -790,35 +790,6 @@ void mesh_plink_broken(struct sta_info *sta)
> rcu_read_unlock();
> }
>
> -/**
> - * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
> - *
> - * @sta - mesh peer to match
> - *
> - * RCU notes: this function is called when a mesh plink transitions from
> - * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
> - * allows path creation. This will happen before the sta can be freed (because
> - * sta_info_destroy() calls this) so any reader in a rcu read block will be
> - * protected against the plink disappearing.
> - */
> -void mesh_path_flush_by_nexthop(struct sta_info *sta)
> -{
> - struct mesh_table *tbl;
> - struct mesh_path *mpath;
> - struct mpath_node *node;
> - struct hlist_node *p;
> - int i;
> -
> - rcu_read_lock();
> - tbl = rcu_dereference(mesh_paths);
> - for_each_mesh_entry(tbl, p, node, i) {
> - mpath = node->mpath;
> - if (rcu_dereference(mpath->next_hop) == sta)
> - mesh_path_del(mpath->dst, mpath->sdata);
> - }
> - rcu_read_unlock();
> -}
> -
> static void mesh_path_node_reclaim(struct rcu_head *rp)
> {
> struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
> @@ -845,7 +816,18 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
> atomic_dec(&tbl->entries);
> }
>
> -static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
> +/**
> + * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
> + *
> + * @sta - mesh peer to match
> + *
> + * RCU notes: this function is called when a mesh plink transitions from
> + * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
> + * allows path creation. This will happen before the sta can be freed (because
> + * sta_info_destroy() calls this) so any reader in a rcu read block will be
> + * protected against the plink disappearing.
> + */
> +void mesh_path_flush_by_nexthop(struct sta_info *sta)
> {
> struct mesh_table *tbl;
> struct mesh_path *mpath;
> @@ -857,7 +839,7 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
> tbl = rcu_dereference(mesh_paths);
> for_each_mesh_entry(tbl, p, node, i) {
> mpath = node->mpath;
> - if (mpath->sdata == sdata) {
> + if (rcu_dereference(mpath->next_hop) == sta) {
> spin_lock_bh(&tbl->hashwlock[i]);
> __mesh_path_del(tbl, node);
> spin_unlock_bh(&tbl->hashwlock[i]);
> @@ -866,24 +848,23 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
> rcu_read_unlock();
> }
>
> -static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
> +static void table_flush_by_iface(struct mesh_table *tbl,
> + struct ieee80211_sub_if_data *sdata)
> {
> - struct mesh_table *tbl;
> struct mesh_path *mpath;
> struct mpath_node *node;
> struct hlist_node *p;
> int i;
>
> - read_lock_bh(&pathtbl_resize_lock);
> - tbl = rcu_dereference_protected(mpp_paths,
> - lockdep_is_held(pathtbl_resize_lock));
> + WARN_ON(!rcu_read_lock_held());
> for_each_mesh_entry(tbl, p, 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]);
> }
> - read_unlock_bh(&pathtbl_resize_lock);
> }

So what protects against the table being grown at the same time? A copy
will be made, but here you'll be iterating the old table -- which won't
crash or anything but is semantically incorrect.

johannes


2011-08-27 00:18:22

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 0/8] mesh fixes

A series of fixes and cleanups to the mesh stack.
There were two contentious patches in the first version:

1. mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

This has been fixed (see version patch description).

2. mac80211: Limit amount of HWMP frames and forwarded data packets in
queues on mesh interfaces

This has been removed from the set until we figure out a more elegant way to
solve the problem it tried to fix.

Cheers,

Javier Cardona (8):
mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()
mac80211: Remove mesh paths when an interface is removed
mac80211: Improve mpath state locking
mac80211: Remove redundant mesh path expiration checks
mac80211: Don't iterate twice over all mpaths when once in sufficient
mac80211: Consolidate {mesh,mpp}_path_flush into one function
mac80211: Don't take the mesh path resize lock when deleting an mpath
mac80211: Consolidate mesh path duplicated functions

net/mac80211/cfg.c | 2 +-
net/mac80211/iface.c | 6 ++
net/mac80211/mesh.h | 6 +-
net/mac80211/mesh_pathtbl.c | 167 +++++++++++++++++++++++--------------------
4 files changed, 101 insertions(+), 80 deletions(-)

--
1.7.6


2011-08-25 01:41:11

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 3/9] mac80211: Remove mesh paths when an interface is removed

From: Javier Cardona <[email protected]>

When an interface is removed, the mesh paths associated with it should
also be removed.

This fixes a bug we observed when reloading a device driver module
without reloading mac80211s.

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/cfg.c | 2 +-
net/mac80211/iface.c | 6 ++++++
net/mac80211/mesh.h | 2 +-
net/mac80211/mesh_pathtbl.c | 42 +++++++++++++++++++++++++++++++++++++++++-
4 files changed, 49 insertions(+), 3 deletions(-)

diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c
index 6ab67ab..adfd032 100644
--- a/net/mac80211/cfg.c
+++ b/net/mac80211/cfg.c
@@ -918,7 +918,7 @@ static int ieee80211_del_mpath(struct wiphy *wiphy, struct net_device *dev,
if (dst)
return mesh_path_del(dst, sdata);

- mesh_path_flush(sdata);
+ mesh_path_flush_by_iface(sdata);
return 0;
}

diff --git a/net/mac80211/iface.c b/net/mac80211/iface.c
index 556e7e6..eaa80a3 100644
--- a/net/mac80211/iface.c
+++ b/net/mac80211/iface.c
@@ -1214,6 +1214,9 @@ void ieee80211_if_remove(struct ieee80211_sub_if_data *sdata)
list_del_rcu(&sdata->list);
mutex_unlock(&sdata->local->iflist_mtx);

+ if (ieee80211_vif_is_mesh(&sdata->vif))
+ mesh_path_flush_by_iface(sdata);
+
synchronize_rcu();
unregister_netdevice(sdata->dev);
}
@@ -1233,6 +1236,9 @@ void ieee80211_remove_interfaces(struct ieee80211_local *local)
list_for_each_entry_safe(sdata, tmp, &local->interfaces, list) {
list_del(&sdata->list);

+ if (ieee80211_vif_is_mesh(&sdata->vif))
+ mesh_path_flush_by_iface(sdata);
+
unregister_netdevice_queue(sdata->dev, &unreg_list);
}
mutex_unlock(&local->iflist_mtx);
diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h
index 6b57b11..ac84dc6 100644
--- a/net/mac80211/mesh.h
+++ b/net/mac80211/mesh.h
@@ -243,7 +243,6 @@ struct mesh_path *mesh_path_lookup_by_idx(int idx,
struct ieee80211_sub_if_data *sdata);
void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop);
void mesh_path_expire(struct ieee80211_sub_if_data *sdata);
-void mesh_path_flush(struct ieee80211_sub_if_data *sdata);
void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data *sdata,
struct ieee80211_mgmt *mgmt, size_t len);
int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata);
@@ -280,6 +279,7 @@ void mesh_pathtbl_unregister(void);
int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata);
void mesh_path_timer(unsigned long data);
void mesh_path_flush_by_nexthop(struct sta_info *sta);
+void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata);
void mesh_path_discard_frame(struct sk_buff *skb,
struct ieee80211_sub_if_data *sdata);
void mesh_path_quiesce(struct ieee80211_sub_if_data *sdata);
diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index ee35f75..ef558c1 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -821,7 +821,7 @@ void mesh_path_flush_by_nexthop(struct sta_info *sta)
rcu_read_unlock();
}

-void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
+static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
{
struct mesh_table *tbl;
struct mesh_path *mpath;
@@ -850,6 +850,46 @@ static void mesh_path_node_reclaim(struct rcu_head *rp)
kfree(node);
}

+static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
+{
+ struct mesh_table *tbl;
+ struct mesh_path *mpath;
+ struct mpath_node *node;
+ struct hlist_node *p;
+ int i;
+
+ read_lock_bh(&pathtbl_resize_lock);
+ tbl = rcu_dereference_protected(mpp_paths,
+ lockdep_is_held(pathtbl_resize_lock));
+ for_each_mesh_entry(tbl, p, node, i) {
+ mpath = node->mpath;
+ if (mpath->sdata != sdata)
+ continue;
+ spin_lock_bh(&tbl->hashwlock[i]);
+ spin_lock_bh(&mpath->state_lock);
+ hlist_del_rcu(&node->list);
+ call_rcu(&node->rcu, mesh_path_node_reclaim);
+ atomic_dec(&tbl->entries);
+ spin_unlock_bh(&mpath->state_lock);
+ spin_unlock_bh(&tbl->hashwlock[i]);
+ }
+ read_unlock_bh(&pathtbl_resize_lock);
+}
+
+/**
+ * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface
+ *
+ * This function deletes both mesh paths as well as mesh portal paths.
+ *
+ * @sdata - interface data to match
+ *
+ */
+void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
+{
+ mesh_path_flush(sdata);
+ mpp_path_flush(sdata);
+}
+
/**
* mesh_path_del - delete a mesh path from the table
*
--
1.7.4.1


2011-08-25 18:17:10

by Javier Cardona

[permalink] [raw]
Subject: Re: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

On Wed, Aug 24, 2011 at 7:08 PM, Johannes Berg
<[email protected]> wrote:
> On Wed, 24 Aug 2011 18:40:44 -0700, Thomas Pedersen wrote:
>
>> ? ? ? ? ? ? ? ?da = hdr->addr3;
>> ? ? ? ? ? ? ? ?ra = hdr->addr1;
>> + ? ? ? ? ? ? ? rcu_read_lock();
>> ? ? ? ? ? ? ? ?mpath = mesh_path_lookup(da, sdata);
>> + ? ? ? ? ? ? ? rcu_read_unlock();
>> ? ? ? ? ? ? ? ?if (mpath)
>> ? ? ? ? ? ? ? ? ? ? ? ?sn = ++mpath->sn;
>> ? ? ? ? ? ? ? ?mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>> skb->data,
>
> You've got to be kidding. Didn't I just explain RCU :)

The patch was prepared before your RCU session :(
Just to confirm I got it right before we resubmit: given that not only
the path table accessed inside mesh_path_lookup() but also the mpaths
themselves are RCU protected, the right fix should have been

da = hdr->addr3;
ra = hdr->addr1;
+ rcu_read_lock();
mpath = mesh_path_lookup(da, sdata);
if (mpath)
sn = ++mpath->sn;
+ rcu_read_unlock();
mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl, skb->data,

Correct?

Thanks!

Javier

2011-08-27 00:18:30

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 2/8] mac80211: Remove mesh paths when an interface is removed

When an interface is removed, the mesh paths associated with it should
also be removed.

This fixes a bug we observed when reloading a device driver module
without reloading mac80211s.

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/cfg.c | 2 +-
net/mac80211/iface.c | 6 ++++++
net/mac80211/mesh.h | 2 +-
net/mac80211/mesh_pathtbl.c | 40 +++++++++++++++++++++++++++++++++++++++-
4 files changed, 47 insertions(+), 3 deletions(-)

diff --git a/net/mac80211/cfg.c b/net/mac80211/cfg.c
index 0baaaec..5c0d8fa 100644
--- a/net/mac80211/cfg.c
+++ b/net/mac80211/cfg.c
@@ -921,7 +921,7 @@ static int ieee80211_del_mpath(struct wiphy *wiphy, struct net_device *dev,
if (dst)
return mesh_path_del(dst, sdata);

- mesh_path_flush(sdata);
+ mesh_path_flush_by_iface(sdata);
return 0;
}

diff --git a/net/mac80211/iface.c b/net/mac80211/iface.c
index 556e7e6..eaa80a3 100644
--- a/net/mac80211/iface.c
+++ b/net/mac80211/iface.c
@@ -1214,6 +1214,9 @@ void ieee80211_if_remove(struct ieee80211_sub_if_data *sdata)
list_del_rcu(&sdata->list);
mutex_unlock(&sdata->local->iflist_mtx);

+ if (ieee80211_vif_is_mesh(&sdata->vif))
+ mesh_path_flush_by_iface(sdata);
+
synchronize_rcu();
unregister_netdevice(sdata->dev);
}
@@ -1233,6 +1236,9 @@ void ieee80211_remove_interfaces(struct ieee80211_local *local)
list_for_each_entry_safe(sdata, tmp, &local->interfaces, list) {
list_del(&sdata->list);

+ if (ieee80211_vif_is_mesh(&sdata->vif))
+ mesh_path_flush_by_iface(sdata);
+
unregister_netdevice_queue(sdata->dev, &unreg_list);
}
mutex_unlock(&local->iflist_mtx);
diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h
index 2027207..57a2ad0 100644
--- a/net/mac80211/mesh.h
+++ b/net/mac80211/mesh.h
@@ -238,7 +238,6 @@ struct mesh_path *mesh_path_lookup_by_idx(int idx,
struct ieee80211_sub_if_data *sdata);
void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop);
void mesh_path_expire(struct ieee80211_sub_if_data *sdata);
-void mesh_path_flush(struct ieee80211_sub_if_data *sdata);
void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data *sdata,
struct ieee80211_mgmt *mgmt, size_t len);
int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata);
@@ -275,6 +274,7 @@ void mesh_pathtbl_unregister(void);
int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata);
void mesh_path_timer(unsigned long data);
void mesh_path_flush_by_nexthop(struct sta_info *sta);
+void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata);
void mesh_path_discard_frame(struct sk_buff *skb,
struct ieee80211_sub_if_data *sdata);
void mesh_path_quiesce(struct ieee80211_sub_if_data *sdata);
diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index c92fd70..1c8c420 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -821,7 +821,7 @@ void mesh_path_flush_by_nexthop(struct sta_info *sta)
rcu_read_unlock();
}

-void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
+static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
{
struct mesh_table *tbl;
struct mesh_path *mpath;
@@ -850,6 +850,44 @@ static void mesh_path_node_reclaim(struct rcu_head *rp)
kfree(node);
}

+static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
+{
+ struct mesh_table *tbl;
+ struct mesh_path *mpath;
+ struct mpath_node *node;
+ struct hlist_node *p;
+ int i;
+
+ read_lock_bh(&pathtbl_resize_lock);
+ tbl = rcu_dereference_protected(mpp_paths,
+ lockdep_is_held(pathtbl_resize_lock));
+ for_each_mesh_entry(tbl, p, node, i) {
+ mpath = node->mpath;
+ if (mpath->sdata != sdata)
+ continue;
+ spin_lock_bh(&tbl->hashwlock[i]);
+ spin_lock_bh(&mpath->state_lock);
+ call_rcu(&node->rcu, mesh_path_node_reclaim);
+ atomic_dec(&tbl->entries);
+ spin_unlock_bh(&tbl->hashwlock[i]);
+ }
+ read_unlock_bh(&pathtbl_resize_lock);
+}
+
+/**
+ * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface
+ *
+ * This function deletes both mesh paths as well as mesh portal paths.
+ *
+ * @sdata - interface data to match
+ *
+ */
+void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
+{
+ mesh_path_flush(sdata);
+ mpp_path_flush(sdata);
+}
+
/**
* mesh_path_del - delete a mesh path from the table
*
--
1.7.6


2011-08-25 01:41:24

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 6/9] mac80211: Don't iterate twice over all mpaths when once in sufficient

From: Javier Cardona <[email protected]>

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 64 +++++++++++++++++++++++++------------------
1 files changed, 37 insertions(+), 27 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 562b150..e941de2 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -49,7 +49,9 @@ int mesh_paths_generation;

/* This lock will have the grow table function as writer and add / delete nodes
* as readers. When reading the table (i.e. doing lookups) we are well protected
- * by RCU
+ * by RCU. We need to take this lock when modying the number of buckets
+ * on one of the path tables but we don't need to if adding or removing mpaths
+ * from hash buckets.
*/
static DEFINE_RWLOCK(pathtbl_resize_lock);

@@ -817,6 +819,32 @@ void mesh_path_flush_by_nexthop(struct sta_info *sta)
rcu_read_unlock();
}

+static void mesh_path_node_reclaim(struct rcu_head *rp)
+{
+ struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
+ struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
+
+ del_timer_sync(&node->mpath->timer);
+ atomic_dec(&sdata->u.mesh.mpaths);
+ kfree(node->mpath);
+ kfree(node);
+}
+
+/* needs to be called with the corresponding hashwlock taken */
+static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
+{
+ struct mesh_path *mpath;
+ mpath = node->mpath;
+ spin_lock(&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);
+ atomic_dec(&tbl->entries);
+}
+
static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
{
struct mesh_table *tbl;
@@ -829,23 +857,15 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
tbl = rcu_dereference(mesh_paths);
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- if (mpath->sdata == sdata)
- mesh_path_del(mpath->dst, mpath->sdata);
+ if (mpath->sdata == sdata) {
+ spin_lock_bh(&tbl->hashwlock[i]);
+ __mesh_path_del(tbl, node);
+ spin_unlock_bh(&tbl->hashwlock[i]);
+ }
}
rcu_read_unlock();
}

-static void mesh_path_node_reclaim(struct rcu_head *rp)
-{
- struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
- struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
-
- del_timer_sync(&node->mpath->timer);
- atomic_dec(&sdata->u.mesh.mpaths);
- kfree(node->mpath);
- kfree(node);
-}
-
static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
{
struct mesh_table *tbl;
@@ -859,12 +879,8 @@ static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
lockdep_is_held(pathtbl_resize_lock));
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- if (mpath->sdata != sdata)
- continue;
spin_lock_bh(&tbl->hashwlock[i]);
- hlist_del_rcu(&node->list);
- call_rcu(&node->rcu, mesh_path_node_reclaim);
- atomic_dec(&tbl->entries);
+ __mesh_path_del(tbl, node);
spin_unlock_bh(&tbl->hashwlock[i]);
}
read_unlock_bh(&pathtbl_resize_lock);
@@ -912,14 +928,7 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
mpath = node->mpath;
if (mpath->sdata == sdata &&
memcmp(addr, mpath->dst, ETH_ALEN) == 0) {
- spin_lock_bh(&mpath->state_lock);
- if (mpath->is_gate)
- mesh_gate_del(tbl, mpath);
- mpath->flags |= MESH_PATH_RESOLVING;
- hlist_del_rcu(&node->list);
- call_rcu(&node->rcu, mesh_path_node_reclaim);
- atomic_dec(&tbl->entries);
- spin_unlock_bh(&mpath->state_lock);
+ __mesh_path_del(tbl, node);
goto enddel;
}
}
@@ -1157,6 +1166,7 @@ void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
(!(mpath->flags & MESH_PATH_FIXED)) &&
time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
mesh_path_del(mpath->dst, mpath->sdata);
+ }
rcu_read_unlock();
}

--
1.7.4.1


2011-08-29 13:49:52

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH v2 7/8] mac80211: Don't take the mesh path resize lock when deleting an mpath

On Fri, 2011-08-26 at 17:18 -0700, Javier Cardona wrote:
> The mesh path resize lock is only needed to protect addition or removal
> of buckets on the hash table, not nodes on those buckets.
>
> Signed-off-by: Javier Cardona <[email protected]>
> ---
> net/mac80211/mesh_pathtbl.c | 6 +++---
> 1 files changed, 3 insertions(+), 3 deletions(-)
>
> diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
> index 3c03be9..216bd2f 100644
> --- a/net/mac80211/mesh_pathtbl.c
> +++ b/net/mac80211/mesh_pathtbl.c
> @@ -905,8 +905,8 @@ int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
> int hash_idx;
> int err = 0;
>
> - read_lock_bh(&pathtbl_resize_lock);
> - tbl = resize_dereference_mesh_paths();
> + rcu_read_lock();
> + tbl = rcu_dereference(mesh_paths);
> hash_idx = mesh_table_hash(addr, sdata, tbl);
> bucket = &tbl->hash_buckets[hash_idx];

Doesn't that pose a similar question to the one I just had on the other
patch?

johannes


2011-08-27 00:18:37

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 4/8] mac80211: Remove redundant mesh path expiration checks

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 9 +++------
1 files changed, 3 insertions(+), 6 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index b895a7c..598249e 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -359,8 +359,7 @@ struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
if (MPATH_EXPIRED(mpath)) {
spin_lock_bh(&mpath->state_lock);
- if (MPATH_EXPIRED(mpath))
- mpath->flags &= ~MESH_PATH_ACTIVE;
+ mpath->flags &= ~MESH_PATH_ACTIVE;
spin_unlock_bh(&mpath->state_lock);
}
return mpath;
@@ -386,8 +385,7 @@ struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
if (MPATH_EXPIRED(mpath)) {
spin_lock_bh(&mpath->state_lock);
- if (MPATH_EXPIRED(mpath))
- mpath->flags &= ~MESH_PATH_ACTIVE;
+ mpath->flags &= ~MESH_PATH_ACTIVE;
spin_unlock_bh(&mpath->state_lock);
}
return mpath;
@@ -420,8 +418,7 @@ struct mesh_path *mesh_path_lookup_by_idx(int idx, struct ieee80211_sub_if_data
if (j++ == idx) {
if (MPATH_EXPIRED(node->mpath)) {
spin_lock_bh(&node->mpath->state_lock);
- if (MPATH_EXPIRED(node->mpath))
- node->mpath->flags &= ~MESH_PATH_ACTIVE;
+ node->mpath->flags &= ~MESH_PATH_ACTIVE;
spin_unlock_bh(&node->mpath->state_lock);
}
return node->mpath;
--
1.7.6


2011-08-27 00:18:41

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 6/8] mac80211: Consolidate {mesh,mpp}_path_flush into one function

Signed-off-by: Javier Cardona <[email protected]>

---
v2: - Fix extra space (checkpatch)
- Add lockdep check for RCU
net/mac80211/mesh_pathtbl.c | 65 +++++++++++++++++-------------------------
1 files changed, 26 insertions(+), 39 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index ea9e34a..3c03be9 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -790,35 +790,6 @@ void mesh_plink_broken(struct sta_info *sta)
rcu_read_unlock();
}

-/**
- * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
- *
- * @sta - mesh peer to match
- *
- * RCU notes: this function is called when a mesh plink transitions from
- * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
- * allows path creation. This will happen before the sta can be freed (because
- * sta_info_destroy() calls this) so any reader in a rcu read block will be
- * protected against the plink disappearing.
- */
-void mesh_path_flush_by_nexthop(struct sta_info *sta)
-{
- struct mesh_table *tbl;
- struct mesh_path *mpath;
- struct mpath_node *node;
- struct hlist_node *p;
- int i;
-
- rcu_read_lock();
- tbl = rcu_dereference(mesh_paths);
- for_each_mesh_entry(tbl, p, node, i) {
- mpath = node->mpath;
- if (rcu_dereference(mpath->next_hop) == sta)
- mesh_path_del(mpath->dst, mpath->sdata);
- }
- rcu_read_unlock();
-}
-
static void mesh_path_node_reclaim(struct rcu_head *rp)
{
struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
@@ -845,7 +816,18 @@ static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
atomic_dec(&tbl->entries);
}

-static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
+/**
+ * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
+ *
+ * @sta - mesh peer to match
+ *
+ * RCU notes: this function is called when a mesh plink transitions from
+ * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
+ * allows path creation. This will happen before the sta can be freed (because
+ * sta_info_destroy() calls this) so any reader in a rcu read block will be
+ * protected against the plink disappearing.
+ */
+void mesh_path_flush_by_nexthop(struct sta_info *sta)
{
struct mesh_table *tbl;
struct mesh_path *mpath;
@@ -857,7 +839,7 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
tbl = rcu_dereference(mesh_paths);
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- if (mpath->sdata == sdata) {
+ if (rcu_dereference(mpath->next_hop) == sta) {
spin_lock_bh(&tbl->hashwlock[i]);
__mesh_path_del(tbl, node);
spin_unlock_bh(&tbl->hashwlock[i]);
@@ -866,24 +848,23 @@ static void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
rcu_read_unlock();
}

-static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
+static void table_flush_by_iface(struct mesh_table *tbl,
+ struct ieee80211_sub_if_data *sdata)
{
- struct mesh_table *tbl;
struct mesh_path *mpath;
struct mpath_node *node;
struct hlist_node *p;
int i;

- read_lock_bh(&pathtbl_resize_lock);
- tbl = rcu_dereference_protected(mpp_paths,
- lockdep_is_held(pathtbl_resize_lock));
+ WARN_ON(!rcu_read_lock_held());
for_each_mesh_entry(tbl, p, 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]);
}
- read_unlock_bh(&pathtbl_resize_lock);
}

/**
@@ -896,8 +877,14 @@ static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
*/
void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
{
- mesh_path_flush(sdata);
- mpp_path_flush(sdata);
+ struct mesh_table *tbl;
+
+ rcu_read_lock();
+ tbl = rcu_dereference(mesh_paths);
+ table_flush_by_iface(tbl, sdata);
+ tbl = rcu_dereference(mpp_paths);
+ table_flush_by_iface(tbl, sdata);
+ rcu_read_unlock();
}

/**
--
1.7.6


2011-08-25 18:48:10

by Johannes Berg

[permalink] [raw]
Subject: Re: [PATCH 1/9] mac80211: Fix RCU pointer dereference in mesh_path_discard_frame()

On Thu, 25 Aug 2011 11:45:11 -0700, Javier Cardona wrote:
> On Thu, Aug 25, 2011 at 11:21 AM, Johannes Berg
> <[email protected]> wrote:
>> On Thu, 25 Aug 2011 11:16:50 -0700, Javier Cardona wrote:
>>>
>>> On Wed, Aug 24, 2011 at 7:08 PM, Johannes Berg
>>> <[email protected]> wrote:
>>>>
>>>> On Wed, 24 Aug 2011 18:40:44 -0700, Thomas Pedersen wrote:
>>>>
>>>>>                da = hdr->addr3;
>>>>>                ra = hdr->addr1;
>>>>> +               rcu_read_lock();
>>>>>                mpath = mesh_path_lookup(da, sdata);
>>>>> +               rcu_read_unlock();
>>>>>                if (mpath)
>>>>>                        sn = ++mpath->sn;
>>>>>              
>>>>>  mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>>>>> skb->data,
>>>>
>>>> You've got to be kidding. Didn't I just explain RCU :)
>>>
>>> The patch was prepared before your RCU session :(
>>> Just to confirm I got it right before we resubmit: given that not
>>> only
>>> the path table accessed inside mesh_path_lookup() but also the
>>> mpaths
>>> themselves are RCU protected, the right fix should have been
>>>
>>>               da = hdr->addr3;
>>>               ra = hdr->addr1;
>>> +             rcu_read_lock();
>>>               mpath = mesh_path_lookup(da, sdata);
>>>               if (mpath)
>>>                       sn = ++mpath->sn;
>>> +             rcu_read_unlock();
>>>               mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
>>> skb->data,
>>>
>>> Correct?
>>
>> Frankly, I'm not sure, since you modify the mpath->sn you probably
>> need to
>> hold a real lock, otherwise ++mpath->sn can race against itself in
>> this very
>> function.
>
> Oh, I see. That's a different issue from what I was originally
> trying
> to fix (unprotected access to the path table inside the lookup
> function). But you are completely right. Changing the math sequence
> number requires taking the mpath state lock:
>
> da = hdr->addr3;
> ra = hdr->addr1;
> + rcu_read_lock();
> mpath = mesh_path_lookup(da, sdata);
> - if (mpath)
> + if (mpath) {
> + spin_lock_bh(&mpath->state_lock);
> sn = ++mpath->sn;
> + spin_unlock_bh(&mpath->state_lock);
> + }
> + rcu_read_unlock();
> mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
> skb->data,

Seems about right to me, but I don't know about all the locking :)

johannes

2011-08-25 01:41:18

by Thomas Pedersen

[permalink] [raw]
Subject: [PATCH 4/9] mac80211: Improve mpath state locking

From: Javier Cardona <[email protected]>

No need to take the mpath state lock when an mpath is removed.
Also, no need checking the lock when reading mpath flags.

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh.h | 4 +++-
net/mac80211/mesh_pathtbl.c | 14 +++-----------
2 files changed, 6 insertions(+), 12 deletions(-)

diff --git a/net/mac80211/mesh.h b/net/mac80211/mesh.h
index ac84dc6..42536a4 100644
--- a/net/mac80211/mesh.h
+++ b/net/mac80211/mesh.h
@@ -80,7 +80,9 @@ enum mesh_deferred_task_flags {
* retry
* @discovery_retries: number of discovery retries
* @flags: mesh path flags, as specified on &enum mesh_path_flags
- * @state_lock: mesh path state lock
+ * @state_lock: mesh path state lock used to protect changes to the
+ * mpath itself. No need to take this lock when adding or removing
+ * an mpath to a hash bucket on a path table.
* @is_gate: the destination station of this path is a mesh gate
*
*
diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index ef558c1..3c96e55 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -776,18 +776,17 @@ void mesh_plink_broken(struct sta_info *sta)
tbl = rcu_dereference(mesh_paths);
for_each_mesh_entry(tbl, p, node, i) {
mpath = node->mpath;
- spin_lock_bh(&mpath->state_lock);
if (rcu_dereference(mpath->next_hop) == sta &&
mpath->flags & MESH_PATH_ACTIVE &&
!(mpath->flags & MESH_PATH_FIXED)) {
+ spin_lock_bh(&mpath->state_lock);
mpath->flags &= ~MESH_PATH_ACTIVE;
++mpath->sn;
spin_unlock_bh(&mpath->state_lock);
mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
mpath->dst, cpu_to_le32(mpath->sn),
reason, bcast, sdata);
- } else
- spin_unlock_bh(&mpath->state_lock);
+ }
}
rcu_read_unlock();
}
@@ -866,11 +865,9 @@ static void mpp_path_flush(struct ieee80211_sub_if_data *sdata)
if (mpath->sdata != sdata)
continue;
spin_lock_bh(&tbl->hashwlock[i]);
- spin_lock_bh(&mpath->state_lock);
hlist_del_rcu(&node->list);
call_rcu(&node->rcu, mesh_path_node_reclaim);
atomic_dec(&tbl->entries);
- spin_unlock_bh(&mpath->state_lock);
spin_unlock_bh(&tbl->hashwlock[i]);
}
read_unlock_bh(&pathtbl_resize_lock);
@@ -1159,15 +1156,10 @@ void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
if (node->mpath->sdata != sdata)
continue;
mpath = node->mpath;
- spin_lock_bh(&mpath->state_lock);
if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
(!(mpath->flags & MESH_PATH_FIXED)) &&
- time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) {
- spin_unlock_bh(&mpath->state_lock);
+ time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
mesh_path_del(mpath->dst, mpath->sdata);
- } else
- spin_unlock_bh(&mpath->state_lock);
- }
rcu_read_unlock();
}

--
1.7.4.1


2011-08-27 00:18:45

by Javier Cardona

[permalink] [raw]
Subject: [PATCH v2 8/8] mac80211: Consolidate mesh path duplicated functions

Signed-off-by: Javier Cardona <[email protected]>
---
net/mac80211/mesh_pathtbl.c | 52 ++++++++++++++-----------------------------
1 files changed, 17 insertions(+), 35 deletions(-)

diff --git a/net/mac80211/mesh_pathtbl.c b/net/mac80211/mesh_pathtbl.c
index 216bd2f..9482e87 100644
--- a/net/mac80211/mesh_pathtbl.c
+++ b/net/mac80211/mesh_pathtbl.c
@@ -335,25 +335,14 @@ static void mesh_path_move_to_queue(struct mesh_path *gate_mpath,
}


-/**
- * mesh_path_lookup - look up a path in the mesh path table
- * @dst: hardware address (ETH_ALEN length) of destination
- * @sdata: local subif
- *
- * Returns: pointer to the mesh path structure, or NULL if not found
- *
- * Locking: must be called within a read rcu section.
- */
-struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
+static struct mesh_path *path_lookup(struct mesh_table *tbl, u8 *dst,
+ struct ieee80211_sub_if_data *sdata)
{
struct mesh_path *mpath;
struct hlist_node *n;
struct hlist_head *bucket;
- struct mesh_table *tbl;
struct mpath_node *node;

- tbl = rcu_dereference(mesh_paths);
-
bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
hlist_for_each_entry_rcu(node, n, bucket, list) {
mpath = node->mpath;
@@ -370,30 +359,23 @@ struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
return NULL;
}

-struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
+/**
+ * mesh_path_lookup - look up a path in the mesh path table
+ * @dst: hardware address (ETH_ALEN length) of destination
+ * @sdata: local subif
+ *
+ * Returns: pointer to the mesh path structure, or NULL if not found
+ *
+ * Locking: must be called within a read rcu section.
+ */
+struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
{
- struct mesh_path *mpath;
- struct hlist_node *n;
- struct hlist_head *bucket;
- struct mesh_table *tbl;
- struct mpath_node *node;
-
- tbl = rcu_dereference(mpp_paths);
+ return path_lookup(rcu_dereference(mesh_paths), dst, sdata);
+}

- bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
- hlist_for_each_entry_rcu(node, n, bucket, list) {
- mpath = node->mpath;
- if (mpath->sdata == sdata &&
- memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
- if (MPATH_EXPIRED(mpath)) {
- spin_lock_bh(&mpath->state_lock);
- mpath->flags &= ~MESH_PATH_ACTIVE;
- spin_unlock_bh(&mpath->state_lock);
- }
- return mpath;
- }
- }
- return NULL;
+struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
+{
+ return path_lookup(rcu_dereference(mpp_paths), dst, sdata);
}


--
1.7.6