Hi,
Here are five fixes which address potential problems with parallel OGM processing. For the multicast subsystem the issues can be quite severe as found and pointed out by Sven here [0].
Cheers, Linus
[0]: https://lists.open-mesh.org/pipermail/b.a.t.m.a.n/2015-June/013193.html
-----
Changelog v4:
* [PATCHv4 maint 5/5]: * Shortened if...BUG() to BUG_ON()
Changelog v3:
* [PATCHv3 maint 5/5]: * added kerneldoc for new mcast_handler_lock in types.h
Changelog v2:
* Split [PATCH maint 1/2] into [PATCHv2 {1,2,3,4}/5] * [PATCHv2 maint 5/5]: * moved mcast_flags initialization outside of spinlock * added spinlock in batadv_mcast_purge_orig() (not strictly necessary bc. if we are here then the orig-node is out-of-scope as it's going to be kfree'd a few instructions later - but added for style reasons / to avoid future errors) * added hlist_unhashed()+BUG() calls (again, shouldn't be necessary as the checks and new spinlock should avoid this case. But since the safety of hlist_del_rcu() isn't directly obvious, better adding these annotations and to avoid future regressions with kernel panics)
PS: Thanks to Marek for the suggestions.
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 2b1c07b918d2 ("batman-adv: tvlv - add distributed arp table container") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue --- distributed-arp-table.c | 4 ++-- types.h | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/distributed-arp-table.c b/distributed-arp-table.c index 0d791dc..b2cc19b 100644 --- a/distributed-arp-table.c +++ b/distributed-arp-table.c @@ -682,9 +682,9 @@ static void batadv_dat_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, uint16_t tvlv_value_len) { if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND) - orig->capabilities &= ~BATADV_ORIG_CAPA_HAS_DAT; + clear_bit(BATADV_ORIG_CAPA_HAS_DAT, &orig->capabilities); else - orig->capabilities |= BATADV_ORIG_CAPA_HAS_DAT; + set_bit(BATADV_ORIG_CAPA_HAS_DAT, &orig->capabilities); }
/** diff --git a/types.h b/types.h index 28f2461..e33b5aa 100644 --- a/types.h +++ b/types.h @@ -256,7 +256,7 @@ struct batadv_orig_node { struct hlist_node mcast_want_all_ipv4_node; struct hlist_node mcast_want_all_ipv6_node; #endif - uint8_t capabilities; + unsigned long capabilities; uint8_t capa_initialized; atomic_t last_ttvn; unsigned char *tt_buff;
On Tuesday, June 16, 2015 17:10:22 Linus Lüssing wrote:
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 2b1c07b918d2 ("batman-adv: tvlv - add distributed arp table container") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue
distributed-arp-table.c | 4 ++-- types.h | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-)
Applied in revision bfd0fba.
Thanks, Marek
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 7dd9d8992b0c ("batman-adv: tvlv - add network coding container") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue --- network-coding.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/network-coding.c b/network-coding.c index 89e1d47..3ce493e 100644 --- a/network-coding.c +++ b/network-coding.c @@ -105,9 +105,9 @@ static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, uint16_t tvlv_value_len) { if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND) - orig->capabilities &= ~BATADV_ORIG_CAPA_HAS_NC; + clear_bit(BATADV_ORIG_CAPA_HAS_NC, &orig->capabilities); else - orig->capabilities |= BATADV_ORIG_CAPA_HAS_NC; + set_bit(BATADV_ORIG_CAPA_HAS_NC, &orig->capabilities); }
/**
On Tuesday, June 16, 2015 17:10:23 Linus Lüssing wrote:
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 7dd9d8992b0c ("batman-adv: tvlv - add network coding container") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue
network-coding.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
Applied in revision 586df9e.
Thanks, Marek
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 5d2121af6d31 ("batman-adv: introduce capability initialization bitfield") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue --- translation-table.c | 4 ++-- types.h | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/translation-table.c b/translation-table.c index b098e53..e95a424 100644 --- a/translation-table.c +++ b/translation-table.c @@ -1843,7 +1843,7 @@ void batadv_tt_global_del_orig(struct batadv_priv *bat_priv, } spin_unlock_bh(list_lock); } - orig_node->capa_initialized &= ~BATADV_ORIG_CAPA_HAS_TT; + clear_bit(BATADV_ORIG_CAPA_HAS_TT, &orig_node->capa_initialized); }
static bool batadv_tt_global_to_purge(struct batadv_tt_global_entry *tt_global, @@ -2802,7 +2802,7 @@ static void _batadv_tt_update_changes(struct batadv_priv *bat_priv, return; } } - orig_node->capa_initialized |= BATADV_ORIG_CAPA_HAS_TT; + set_bit(BATADV_ORIG_CAPA_HAS_TT, &orig_node->capa_initialized); }
static void batadv_tt_fill_gtable(struct batadv_priv *bat_priv, diff --git a/types.h b/types.h index e33b5aa..c6ec558 100644 --- a/types.h +++ b/types.h @@ -257,7 +257,7 @@ struct batadv_orig_node { struct hlist_node mcast_want_all_ipv6_node; #endif unsigned long capabilities; - uint8_t capa_initialized; + unsigned long capa_initialized; atomic_t last_ttvn; unsigned char *tt_buff; int16_t tt_buff_len;
On Tuesday, June 16, 2015 17:10:24 Linus Lüssing wrote:
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 5d2121af6d31 ("batman-adv: introduce capability initialization bitfield") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue
translation-table.c | 4 ++-- types.h | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-)
Applied in revision a51fa16.
Thanks, Marek
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 77ec494490d6 ("batman-adv: Announce new capability via multicast TVLV") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue --- multicast.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/multicast.c b/multicast.c index 09f2838..00612bf 100644 --- a/multicast.c +++ b/multicast.c @@ -684,7 +684,7 @@ static void batadv_mcast_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, !(orig->capabilities & BATADV_ORIG_CAPA_HAS_MCAST)) { if (orig_initialized) atomic_dec(&bat_priv->mcast.num_disabled); - orig->capabilities |= BATADV_ORIG_CAPA_HAS_MCAST; + set_bit(BATADV_ORIG_CAPA_HAS_MCAST, &orig->capabilities); /* If mcast support is being switched off or if this is an initial * OGM without mcast support then increase the disabled mcast * node counter. @@ -693,10 +693,10 @@ static void batadv_mcast_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, (orig->capabilities & BATADV_ORIG_CAPA_HAS_MCAST || !orig_initialized)) { atomic_inc(&bat_priv->mcast.num_disabled); - orig->capabilities &= ~BATADV_ORIG_CAPA_HAS_MCAST; + clear_bit(BATADV_ORIG_CAPA_HAS_MCAST, &orig->capabilities); }
- orig->capa_initialized |= BATADV_ORIG_CAPA_HAS_MCAST; + set_bit(BATADV_ORIG_CAPA_HAS_MCAST, &orig->capa_initialized);
if (orig_mcast_enabled && tvlv_value && (tvlv_value_len >= sizeof(mcast_flags)))
On Tuesday, June 16, 2015 17:10:25 Linus Lüssing wrote:
Bitwise OR/AND assignments in C aren't guaranteed to be atomic. One OGM handler might undo the set/clear of a specific bit from another handler run in between.
Fix this by using the atomic set_bit()/clear_bit() functions.
Fixes: 77ec494490d6 ("batman-adv: Announce new capability via multicast TVLV") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue
multicast.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
Applied in revision 201a54b.
Thanks, Marek
So far the mcast tvlv handler did not anticipate the processing of multiple incoming OGMs from the same originator at the same time. This can lead to various issues:
* Broken refcounting: For instance two mcast handlers might both assume that an originator just got multicast capabilities and will together wrongly decrease mcast.num_disabled by two, potentially leading to an integer underflow.
* Potential kernel panic on hlist_del_rcu(): Two mcast handlers might one after another try to do an hlist_del_rcu(&orig->mcast_want_all_*_node). The second one will cause memory corruption / crashes. (Reported by: Sven Eckelmann sven@narfation.org)
Right in the beginning the code path makes assumptions about the current multicast related state of an originator and bases all updates on that. The easiest and least error prune way to fix the issues in this case is to serialize multiple mcast handler invocations with a spinlock.
Fixes: 77ec494490d6 ("batman-adv: Announce new capability via multicast TVLV") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue --- multicast.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++------------ originator.c | 4 ++++ types.h | 3 +++ 3 files changed, 56 insertions(+), 13 deletions(-)
diff --git a/multicast.c b/multicast.c index 00612bf..b75bcc3 100644 --- a/multicast.c +++ b/multicast.c @@ -565,19 +565,26 @@ batadv_mcast_forw_mode(struct batadv_priv *bat_priv, struct sk_buff *skb, * * If the BATADV_MCAST_WANT_ALL_UNSNOOPABLES flag of this originator, * orig, has toggled then this method updates counter and list accordingly. + * + * Caller needs to hold orig->mcast_handler_lock. */ static void batadv_mcast_want_unsnoop_update(struct batadv_priv *bat_priv, struct batadv_orig_node *orig, uint8_t mcast_flags) { + struct hlist_node *node = &orig->mcast_want_all_unsnoopables_node; + struct hlist_head *head = &bat_priv->mcast.want_all_unsnoopables_list; + /* switched from flag unset to set */ if (mcast_flags & BATADV_MCAST_WANT_ALL_UNSNOOPABLES && !(orig->mcast_flags & BATADV_MCAST_WANT_ALL_UNSNOOPABLES)) { atomic_inc(&bat_priv->mcast.num_want_all_unsnoopables);
spin_lock_bh(&bat_priv->mcast.want_lists_lock); - hlist_add_head_rcu(&orig->mcast_want_all_unsnoopables_node, - &bat_priv->mcast.want_all_unsnoopables_list); + /* flag checks above + mcast_handler_lock prevents this */ + BUG_ON(!hlist_unhashed(node)); + + hlist_add_head_rcu(node, head); spin_unlock_bh(&bat_priv->mcast.want_lists_lock); /* switched from flag set to unset */ } else if (!(mcast_flags & BATADV_MCAST_WANT_ALL_UNSNOOPABLES) && @@ -585,7 +592,10 @@ static void batadv_mcast_want_unsnoop_update(struct batadv_priv *bat_priv, atomic_dec(&bat_priv->mcast.num_want_all_unsnoopables);
spin_lock_bh(&bat_priv->mcast.want_lists_lock); - hlist_del_rcu(&orig->mcast_want_all_unsnoopables_node); + /* flag checks above + mcast_handler_lock prevents this */ + BUG_ON(hlist_unhashed(node)); + + hlist_del_init_rcu(node); spin_unlock_bh(&bat_priv->mcast.want_lists_lock); } } @@ -598,19 +608,26 @@ static void batadv_mcast_want_unsnoop_update(struct batadv_priv *bat_priv, * * If the BATADV_MCAST_WANT_ALL_IPV4 flag of this originator, orig, has * toggled then this method updates counter and list accordingly. + * + * Caller needs to hold orig->mcast_handler_lock. */ static void batadv_mcast_want_ipv4_update(struct batadv_priv *bat_priv, struct batadv_orig_node *orig, uint8_t mcast_flags) { + struct hlist_node *node = &orig->mcast_want_all_ipv4_node; + struct hlist_head *head = &bat_priv->mcast.want_all_ipv4_list; + /* switched from flag unset to set */ if (mcast_flags & BATADV_MCAST_WANT_ALL_IPV4 && !(orig->mcast_flags & BATADV_MCAST_WANT_ALL_IPV4)) { atomic_inc(&bat_priv->mcast.num_want_all_ipv4);
spin_lock_bh(&bat_priv->mcast.want_lists_lock); - hlist_add_head_rcu(&orig->mcast_want_all_ipv4_node, - &bat_priv->mcast.want_all_ipv4_list); + /* flag checks above + mcast_handler_lock prevents this */ + BUG_ON(!hlist_unhashed(node)); + + hlist_add_head_rcu(node, head); spin_unlock_bh(&bat_priv->mcast.want_lists_lock); /* switched from flag set to unset */ } else if (!(mcast_flags & BATADV_MCAST_WANT_ALL_IPV4) && @@ -618,7 +635,10 @@ static void batadv_mcast_want_ipv4_update(struct batadv_priv *bat_priv, atomic_dec(&bat_priv->mcast.num_want_all_ipv4);
spin_lock_bh(&bat_priv->mcast.want_lists_lock); - hlist_del_rcu(&orig->mcast_want_all_ipv4_node); + /* flag checks above + mcast_handler_lock prevents this */ + BUG_ON(hlist_unhashed(node)); + + hlist_del_init_rcu(node); spin_unlock_bh(&bat_priv->mcast.want_lists_lock); } } @@ -631,19 +651,26 @@ static void batadv_mcast_want_ipv4_update(struct batadv_priv *bat_priv, * * If the BATADV_MCAST_WANT_ALL_IPV6 flag of this originator, orig, has * toggled then this method updates counter and list accordingly. + * + * Caller needs to hold orig->mcast_handler_lock. */ static void batadv_mcast_want_ipv6_update(struct batadv_priv *bat_priv, struct batadv_orig_node *orig, uint8_t mcast_flags) { + struct hlist_node *node = &orig->mcast_want_all_ipv6_node; + struct hlist_head *head = &bat_priv->mcast.want_all_ipv6_list; + /* switched from flag unset to set */ if (mcast_flags & BATADV_MCAST_WANT_ALL_IPV6 && !(orig->mcast_flags & BATADV_MCAST_WANT_ALL_IPV6)) { atomic_inc(&bat_priv->mcast.num_want_all_ipv6);
spin_lock_bh(&bat_priv->mcast.want_lists_lock); - hlist_add_head_rcu(&orig->mcast_want_all_ipv6_node, - &bat_priv->mcast.want_all_ipv6_list); + /* flag checks above + mcast_handler_lock prevents this */ + BUG_ON(!hlist_unhashed(node)); + + hlist_add_head_rcu(node, head); spin_unlock_bh(&bat_priv->mcast.want_lists_lock); /* switched from flag set to unset */ } else if (!(mcast_flags & BATADV_MCAST_WANT_ALL_IPV6) && @@ -651,7 +678,10 @@ static void batadv_mcast_want_ipv6_update(struct batadv_priv *bat_priv, atomic_dec(&bat_priv->mcast.num_want_all_ipv6);
spin_lock_bh(&bat_priv->mcast.want_lists_lock); - hlist_del_rcu(&orig->mcast_want_all_ipv6_node); + /* flag checks above + mcast_handler_lock prevents this */ + BUG_ON(hlist_unhashed(node)); + + hlist_del_init_rcu(node); spin_unlock_bh(&bat_priv->mcast.want_lists_lock); } } @@ -674,6 +704,11 @@ static void batadv_mcast_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv, uint8_t mcast_flags = BATADV_NO_FLAGS; bool orig_initialized;
+ if (orig_mcast_enabled && tvlv_value && + (tvlv_value_len >= sizeof(mcast_flags))) + mcast_flags = *(uint8_t *)tvlv_value; + + spin_lock_bh(&orig->mcast_handler_lock); orig_initialized = orig->capa_initialized & BATADV_ORIG_CAPA_HAS_MCAST;
/* If mcast support is turned on decrease the disabled mcast node @@ -698,15 +733,12 @@ static void batadv_mcast_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv,
set_bit(BATADV_ORIG_CAPA_HAS_MCAST, &orig->capa_initialized);
- if (orig_mcast_enabled && tvlv_value && - (tvlv_value_len >= sizeof(mcast_flags))) - mcast_flags = *(uint8_t *)tvlv_value; - batadv_mcast_want_unsnoop_update(bat_priv, orig, mcast_flags); batadv_mcast_want_ipv4_update(bat_priv, orig, mcast_flags); batadv_mcast_want_ipv6_update(bat_priv, orig, mcast_flags);
orig->mcast_flags = mcast_flags; + spin_unlock_bh(&orig->mcast_handler_lock); }
/** @@ -740,6 +772,8 @@ void batadv_mcast_purge_orig(struct batadv_orig_node *orig) { struct batadv_priv *bat_priv = orig->bat_priv;
+ spin_lock_bh(&orig->mcast_handler_lock); + if (!(orig->capabilities & BATADV_ORIG_CAPA_HAS_MCAST) && orig->capa_initialized & BATADV_ORIG_CAPA_HAS_MCAST) atomic_dec(&bat_priv->mcast.num_disabled); @@ -747,4 +781,6 @@ void batadv_mcast_purge_orig(struct batadv_orig_node *orig) batadv_mcast_want_unsnoop_update(bat_priv, orig, BATADV_NO_FLAGS); batadv_mcast_want_ipv4_update(bat_priv, orig, BATADV_NO_FLAGS); batadv_mcast_want_ipv6_update(bat_priv, orig, BATADV_NO_FLAGS); + + spin_unlock_bh(&orig->mcast_handler_lock); } diff --git a/originator.c b/originator.c index e3900e4..a2ba182 100644 --- a/originator.c +++ b/originator.c @@ -658,11 +658,15 @@ struct batadv_orig_node *batadv_orig_node_new(struct batadv_priv *bat_priv, INIT_HLIST_HEAD(&orig_node->neigh_list); INIT_LIST_HEAD(&orig_node->vlan_list); INIT_HLIST_HEAD(&orig_node->ifinfo_list); + INIT_HLIST_NODE(&orig_node->mcast_want_all_unsnoopables_node); + INIT_HLIST_NODE(&orig_node->mcast_want_all_ipv4_node); + INIT_HLIST_NODE(&orig_node->mcast_want_all_ipv6_node); spin_lock_init(&orig_node->bcast_seqno_lock); spin_lock_init(&orig_node->neigh_list_lock); spin_lock_init(&orig_node->tt_buff_lock); spin_lock_init(&orig_node->tt_lock); spin_lock_init(&orig_node->vlan_list_lock); + spin_lock_init(&orig_node->mcast_handler_lock);
batadv_nc_init_orig(orig_node);
diff --git a/types.h b/types.h index c6ec558..65dc6bf 100644 --- a/types.h +++ b/types.h @@ -204,6 +204,7 @@ struct batadv_orig_bat_iv { * @batadv_dat_addr_t: address of the orig node in the distributed hash * @last_seen: time when last packet from this node was received * @bcast_seqno_reset: time when the broadcast seqno window was reset + * @mcast_handler_lock: synchronizes mcast-capability and -flag changes * @mcast_flags: multicast flags announced by the orig node * @mcast_want_all_unsnoop_node: a list node for the * mcast.want_all_unsnoopables list @@ -251,6 +252,8 @@ struct batadv_orig_node { unsigned long last_seen; unsigned long bcast_seqno_reset; #ifdef CONFIG_BATMAN_ADV_MCAST + /* synchronizes mcast tvlv specific orig changes */ + spinlock_t mcast_handler_lock; uint8_t mcast_flags; struct hlist_node mcast_want_all_unsnoopables_node; struct hlist_node mcast_want_all_ipv4_node;
On Tuesday, June 16, 2015 17:10:26 Linus Lüssing wrote:
So far the mcast tvlv handler did not anticipate the processing of multiple incoming OGMs from the same originator at the same time. This can lead to various issues:
Broken refcounting: For instance two mcast handlers might both assume that an originator just got multicast capabilities and will together wrongly decrease mcast.num_disabled by two, potentially leading to an integer underflow.
Potential kernel panic on hlist_del_rcu(): Two mcast handlers might one after another try to do an hlist_del_rcu(&orig->mcast_want_all_*_node). The second one will cause memory corruption / crashes. (Reported by: Sven Eckelmann sven@narfation.org)
Right in the beginning the code path makes assumptions about the current multicast related state of an originator and bases all updates on that. The easiest and least error prune way to fix the issues in this case is to serialize multiple mcast handler invocations with a spinlock.
Fixes: 77ec494490d6 ("batman-adv: Announce new capability via multicast TVLV") Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue
multicast.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++------------ originator.c | 4 ++++ types.h | 3 +++ 3 files changed, 56 insertions(+), 13 deletions(-)
Applied in revision 7f220ed.
Thanks, Marek
b.a.t.m.a.n@lists.open-mesh.org
-
Linus Lüssing -
Marek Lindner