netfilter: nf_conncount: fix gc and rbtree bugs
Subsystems (3)
Florian Westphal
maintainerv3 cover netfilter: nf_conncount: fix gc and rbtree bugs
This addresses a drive-by AI review of nf_conncount. See patch 5 for details.
v3: add patch 1, openvswitch breakage was not raised before.
in patch 4, check seqcount before returning -ENOENT. No other changes.
1) conncount API assumes rcu read lock is held, openvswitch doesn't do that. Fix this.
2) Replace rb_root with a new container structure in nf_conncount to prepare for a per-tree sequence counter to detect concurrent modifications.
3) Split nf_conncount rbtree walk into a helper. Add find_tree_node() to fetch matching node so folluwp patch can reuse the function.
4) Add a sequence count to detect concurrent rbtree modifications.
5) Move rbtree iteration under spinlock, lockless iteration is not safe. Do lock-break + resched + restart to not hold spinlock for too long. Add rcu_barrier before zapping the kmem cache during module exit.
Florian Westphal (5):
netfilter: nf_conncount: callers must hold rcu read lock
netfilter: nf_conncount: prepare for per-tree seqcount
netfilter: nf_conncount: split count_tree_node rbtree walk into helper
netfilter: nf_conncount: add sequence counter to detect tree
modifications
netfilter: nf_conncount: gc and rcu fixes
net/netfilter/nf_conncount.c | 208 ++++++++++++++++++++++------------- net/openvswitch/conntrack.c | 2 +- 2 files changed, 135 insertions(+), 75 deletions(-)
Signature · 1 line
2.54.0
Florian Westphal
maintainerPATCH v3 1/5 netfilter: nf_conncount: callers must hold rcu read lock
rcu_derefence_raw() should not have been used here, it concealed this bug.
Extend the rcu read lock scope accordingly.
---
v3: new in v3.
net/netfilter/nf_conncount.c | 6 +++--- net/openvswitch/conntrack.c | 2 +- 2 files changed, 4 insertions(+), 4 deletions(-)
net/netfilter/nf_conncount.c +3 -3
@@ -499,7 +499,7 @@ count_tree(struct net *net, hash =jhash2 (key, data->keylen, data->initval) %CONNCOUNT_SLOTS ; root = &data->root[hash]; - parent =rcu_dereference_raw (root->rb_node); + parent =rcu_dereference (root->rb_node);while (parent) {int diff;
@@ -507,9 +507,9 @@ count_tree(struct net *net, diff =key_diff (key, rbconn->key, data->keylen);if (diff <0 ) { - parent =rcu_dereference_raw (parent->rb_left); + parent =rcu_dereference (parent->rb_left); }else if (diff >0 ) { - parent =rcu_dereference_raw (parent->rb_right); + parent =rcu_dereference (parent->rb_right); }else {int ret;
net/openvswitch/conntrack.c +1 -1
@@ -1797,10 +1797,10 @@ static int ovs_ct_limit_get_zone_limit(struct net *net, }else {rcu_read_lock (); limit =ct_limit_get (info, zone); -rcu_read_unlock (); err =__ovs_ct_limit_get_zone_limit ( net, info->data, zone, limit, reply); +rcu_read_unlock ();if (err)return err; }
Signature · 1 line
2.54.0
Florian Westphal
maintainerPATCH v3 2/5 netfilter: nf_conncount: prepare for per-tree seqcount
In reply to Florian WestphalThis change is supposed to not have any actual changes, it merely replaces rb_root by a new container structure.
Followup patch will add and use a sequence counter.
---
v3: no changes.
net/netfilter/nf_conncount.c | 43 ++++++++++++++++++++++-------------- 1 file changed, 27 insertions(+), 16 deletions(-)
net/netfilter/nf_conncount.c +27 -16
@@ -56,10 +56,14 @@ struct nf_conncount_rb { static spinlock_t nf_conncount_locks[CONNCOUNT_SLOTS] __cacheline_aligned_in_smp; +struct nf_conncount_root { +struct rb_root root; +}; +struct nf_conncount_data {unsigned int keylen;u32 initval; -struct rb_root root[CONNCOUNT_SLOTS ]; +struct nf_conncount_root root[CONNCOUNT_SLOTS ];struct net *net;struct work_struct gc_work;unsigned long pending_trees[BITS_TO_LONGS (CONNCOUNT_SLOTS )];
@@ -368,7 +372,7 @@ static void __tree_nodes_free(struct rcu_head *h) }/* caller must hold tree nf_conncount_locks[] lock */ -static void tree_nodes_free (struct rb_root *root, +static void tree_nodes_free (struct nf_conncount_root *root,struct nf_conncount_rb *gc_nodes[],unsigned int gc_count) {
@@ -378,7 +382,7 @@ static void tree_nodes_free(struct rb_root *root, rbconn = gc_nodes[--gc_count];spin_lock (&rbconn->list.list_lock);if (!rbconn->list.count) { -rb_erase (&rbconn->node, root); +rb_erase (&rbconn->node, &root->root);call_rcu (&rbconn->rcu_head, __tree_nodes_free); }spin_unlock (&rbconn->list.list_lock);
@@ -396,10 +400,10 @@ insert_tree(struct net *net,const struct sk_buff *skb, u16 l3num, struct nf_conncount_data *data, - struct rb_root *root, unsigned int hash, const u32 *key) { + struct nf_conncount_root *root = &data->root[hash];struct nf_conncount_rb *gc_nodes[CONNCOUNT_GC_MAX_NODES ];const struct nf_conntrack_zone *zone = &nf_ct_zone_dflt;bool do_gc = true, refcounted = false;
@@ -413,7 +417,7 @@ insert_tree(struct net *net,spin_lock_bh (&nf_conncount_locks[hash]); restart: parent =NULL ; - rbnode = &(root->rb_node); + rbnode = &root->root.rb_node;while (*rbnode) {int diff; rbconn = rb_entry(*rbnode, struct nf_conncount_rb, node);
@@ -475,7 +479,7 @@ insert_tree(struct net *net, rbconn->list.count = count;rb_link_node_rcu (&rbconn->node, parent, rbnode); -rb_insert_color (&rbconn->node, root); +rb_insert_color (&rbconn->node, &root->root); } out_unlock:if (refcounted)
@@ -491,7 +495,7 @@ count_tree(struct net *net,struct nf_conncount_data *data, const u32 *key) { - struct rb_root *root; + struct nf_conncount_root *root;struct rb_node *parent;struct nf_conncount_rb *rbconn;unsigned int hash;
@@ -499,7 +503,7 @@ count_tree(struct net *net, hash =jhash2 (key, data->keylen, data->initval) %CONNCOUNT_SLOTS ; root = &data->root[hash]; - parent =rcu_dereference (root->rb_node); + parent =rcu_dereference (root->root.rb_node);while (parent) {int diff;
@@ -544,14 +548,14 @@ count_tree(struct net *net,if (!skb)return 0 ; -return insert_tree (net, skb, l3num, data, root, hash, key); +return insert_tree (net, skb, l3num, data, hash, key); }static void tree_gc_worker (struct work_struct *work) { struct nf_conncount_data *data = container_of(work, struct nf_conncount_data, gc_work);struct nf_conncount_rb *gc_nodes[CONNCOUNT_GC_MAX_NODES ], *rbconn; -struct rb_root *root; +struct nf_conncount_root *root;struct rb_node *node;unsigned int tree, next_tree, gc_count =0 ;
@@ -560,7 +564,7 @@ static void tree_gc_worker(struct work_struct *work)local_bh_disable ();rcu_read_lock (); -for (node =rb_first (root); node !=NULL ; node =rb_next (node)) { +for (node =rb_first (&root->root); node ; node =rb_next (node)) { rbconn = rb_entry(node, struct nf_conncount_rb, node);if (nf_conncount_gc_list (data->net, &rbconn->list)) gc_count++;
@@ -575,7 +579,7 @@ static void tree_gc_worker(struct work_struct *work) goto next;/* do not bother */ gc_count =0 ; - node =rb_first (root); + node =rb_first (&root->root);while (node !=NULL ) { rbconn = rb_entry(node, struct nf_conncount_rb, node); node =rb_next (node);
@@ -620,6 +624,11 @@ unsigned int nf_conncount_count_skb(struct net *net, }EXPORT_SYMBOL_GPL (nf_conncount_count_skb); +static void nf_conncount_root_init (struct nf_conncount_root *r) +{ + r->root =RB_ROOT ; +} +struct nf_conncount_data *nf_conncount_init (struct net *net,unsigned int keylen) {struct nf_conncount_data *data;
@@ -635,13 +644,15 @@ struct nf_conncount_data *nf_conncount_init(struct net *net, unsigned int keylenreturn ERR_PTR (-ENOMEM );for (i =0 ; i <ARRAY_SIZE (data->root); ++i) - data->root[i] =RB_ROOT ; +nf_conncount_root_init (&data->root[i]); data->keylen = keylen /sizeof (u32); data->net = net; data->initval =get_random_u32 ();INIT_WORK (&data->gc_work, tree_gc_worker); +BUILD_BUG_ON (ARRAY_SIZE (data->root) !=ARRAY_SIZE (nf_conncount_locks)); +return data; }EXPORT_SYMBOL_GPL (nf_conncount_init);
@@ -655,15 +666,15 @@ void nf_conncount_cache_free(struct nf_conncount_list *list) }EXPORT_SYMBOL_GPL (nf_conncount_cache_free); -static void destroy_tree (struct rb_root *r) +static void destroy_tree (struct nf_conncount_root *r) {struct nf_conncount_rb *rbconn;struct rb_node *node; -while ((node =rb_first (r)) !=NULL ) { +while ((node =rb_first (&r->root)) !=NULL ) { rbconn = rb_entry(node, struct nf_conncount_rb, node); -rb_erase (node, r); +rb_erase (node, &r->root);nf_conncount_cache_free (&rbconn->list);
Signature · 1 line
2.54.0
Florian Westphal
maintainerPATCH v3 3/5 netfilter: nf_conncount: split count_tree_node rbtree walk into helper
In reply to Florian WestphalAdd find_tree_node() helper that fetches a matching rbtree node.
This is used by followup patch to optionally search the tree again while preventing concurrent updates via tree lock.
---
v3: no changes.
net/netfilter/nf_conncount.c | 100 +++++++++++++++++++++-------------- 1 file changed, 60 insertions(+), 40 deletions(-)
net/netfilter/nf_conncount.c +60 -40
@@ -488,6 +488,32 @@ insert_tree(struct net *net,return count; } +static struct nf_conncount_rb * +find_tree_node (struct nf_conncount_root *root,struct nf_conncount_data *data, +const u32 *key, +bool locked) +{ +struct rb_node *parent; + + parent =rcu_dereference_check (root->root.rb_node, locked); +while (parent) { +struct nf_conncount_rb *rbconn; +int diff; + + rbconn = rb_entry(parent, struct nf_conncount_rb, node); + + diff =key_diff (key, rbconn->key, data->keylen); +if (diff <0 ) + parent =rcu_dereference_check (parent->rb_left, locked); +else if (diff >0 ) + parent =rcu_dereference_check (parent->rb_right, locked); +else +return rbconn; + } + +return ERR_PTR (-ENOENT ); +} + static unsigned int count_tree(struct net *net, const struct sk_buff *skb,
@@ -496,59 +522,53 @@ count_tree(struct net *net, const u32 *key) {struct nf_conncount_root *root; -struct rb_node *parent;struct nf_conncount_rb *rbconn;unsigned int hash; +int ret; hash =jhash2 (key, data->keylen, data->initval) %CONNCOUNT_SLOTS ; root = &data->root[hash]; - parent =rcu_dereference (root->root.rb_node); -while (parent) { -int diff; - - rbconn = rb_entry(parent, struct nf_conncount_rb, node); + rbconn =find_tree_node (root, data, key, false); +if (IS_ERR (rbconn)) { +if (PTR_ERR (rbconn) == -ENOENT ) { +if (!skb) +return 0 ; - diff =key_diff (key, rbconn->key, data->keylen); -if (diff <0 ) { - parent =rcu_dereference (parent->rb_left); - }else if (diff >0 ) { - parent =rcu_dereference (parent->rb_right); - }else { -int ret; +return insert_tree (net, skb, l3num, data, hash, key); + } +DEBUG_NET_WARN_ON_ONCE (IS_ERR (rbconn)); + } -if (!skb) { -nf_conncount_gc_list (net, &rbconn->list); -return rbconn->list.count; - } +DEBUG_NET_WARN_ON_ONCE (IS_ERR_OR_NULL (rbconn)); +if (IS_ERR_OR_NULL (rbconn)) +return 0 ; -spin_lock_bh (&rbconn->list.list_lock); -/* Node might be about to be free'd. -* We need to defer to insert_tree() in this case. -*/ -if (rbconn->list.count ==0 ) { -spin_unlock_bh (&rbconn->list.list_lock); -break ; - } +if (!skb) { +nf_conncount_gc_list (net, &rbconn->list); +return rbconn->list.count; + } -/* same source network -> be counted! */ - ret =__nf_conncount_add (net, skb, l3num, &rbconn->list); -spin_unlock_bh (&rbconn->list.list_lock); -if (ret && ret != -EEXIST ) { -return 0 ;/* hotdrop */ - }else { -/* -EEXIST means add was skipped, update the list */ -if (ret == -EEXIST ) -nf_conncount_gc_list (net, &rbconn->list); -return rbconn->list.count; - } - } +spin_lock_bh (&rbconn->list.list_lock); +/* Node might be about to be free'd. +* We need to defer to insert_tree() in this case. +*/ +if (rbconn->list.count ==0 ) { +spin_unlock_bh (&rbconn->list.list_lock); +return insert_tree (net, skb, l3num, data, hash, key); } -if (!skb) -return 0 ; +/* same source network -> be counted! */ + ret =__nf_conncount_add (net, skb, l3num, &rbconn->list); +spin_unlock_bh (&rbconn->list.list_lock); + +if (ret && ret != -EEXIST ) +return 0 ;/* hotdrop */ +/* -EEXIST means add was skipped, update the list */ +if (ret == -EEXIST ) +nf_conncount_gc_list (net, &rbconn->list); -return insert_tree (net, skb, l3num, data, hash, key); +return rbconn->list.count; }static void tree_gc_worker (struct work_struct *work)
Signature · 1 line
2.54.0
Florian Westphal
maintainerPATCH v3 4/5 netfilter: nf_conncount: add sequence counter to detect tree modifications
In reply to Florian WestphalThere a two issues with traversal:
1. Key lookup (tree search) cannot detect concurrent modifications and may not find a result in case of parallel modification.
2. Worker does a lockless iteration. This is never safe.
Add a sequence counter and re-do the lookup under lock in case the tree was modified / seqcount changed.
gc_worker bugs are addressed in the next patch.
---
v3: return -EAGAIN if no match found but tree was altered.
net/netfilter/nf_conncount.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+)
net/netfilter/nf_conncount.c +19 -0
@@ -58,6 +58,7 @@ static spinlock_t nf_conncount_locks[CONNCOUNT_SLOTS] __cacheline_aligned_in_smpstruct nf_conncount_root {struct rb_root root; +seqcount_t count; };struct nf_conncount_data {
@@ -382,8 +383,10 @@ static void tree_nodes_free(struct nf_conncount_root *root, rbconn = gc_nodes[--gc_count];spin_lock (&rbconn->list.list_lock);if (!rbconn->list.count) { +write_seqcount_begin (&root->count);rb_erase (&rbconn->node, &root->root);call_rcu (&rbconn->rcu_head, __tree_nodes_free); +write_seqcount_end (&root->count); }spin_unlock (&rbconn->list.list_lock); }
@@ -478,8 +481,10 @@ insert_tree(struct net *net, count =1 ; rbconn->list.count = count; +write_seqcount_begin (&root->count);rb_link_node_rcu (&rbconn->node, parent, rbnode);rb_insert_color (&rbconn->node, &root->root); +write_seqcount_end (&root->count); } out_unlock:if (refcounted)
@@ -493,6 +498,7 @@ find_tree_node(struct nf_conncount_root *root, struct nf_conncount_data *data,const u32 *key, bool locked) { + unsigned int seq = read_seqcount_begin(&root->count);struct rb_node *parent; parent =rcu_dereference_check (root->root.rb_node, locked);
@@ -509,8 +515,14 @@ find_tree_node(struct nf_conncount_root *root, struct nf_conncount_data *data, parent =rcu_dereference_check (parent->rb_right, locked); else return rbconn; + +if (read_seqcount_retry (&root->count, seq)) +return ERR_PTR (-EAGAIN ); } +if (read_seqcount_retry (&root->count, seq)) +return ERR_PTR (-EAGAIN ); +return ERR_PTR (-ENOENT ); }
@@ -531,6 +543,12 @@ count_tree(struct net *net, rbconn =find_tree_node (root, data, key, false);if (IS_ERR (rbconn)) { +if (PTR_ERR (rbconn) == -EAGAIN ) { +spin_lock_bh (&nf_conncount_locks[hash]); + rbconn =find_tree_node (root, data, key, true); +spin_unlock_bh (&nf_conncount_locks[hash]); + } +if (PTR_ERR (rbconn) == -ENOENT ) {if (!skb)return 0 ;
@@ -647,6 +665,7 @@ EXPORT_SYMBOL_GPL(nf_conncount_count_skb);static void nf_conncount_root_init (struct nf_conncount_root *r) { r->root =RB_ROOT ; +seqcount_init (&r->count); }struct nf_conncount_data *nf_conncount_init (struct net *net,unsigned int keylen)
Signature · 1 line
2.54.0
Florian Westphal
maintainerPATCH v3 5/5 netfilter: nf_conncount: gc and rcu fixes
In reply to Florian WestphalAnother drive-by AI review:
1) tree_gc_worker fails to wrap around after it can't find more pending work. Update data->gc_tree unconditionally. If its 0, start from the first pending tree (which can be 0).
2) tree_gc_worker() iterates the rbtree without lock. This is never safe. Move iteration under the spinlock. If this takes too long (resched needed), save key of next node, drop lock, resched, re-lock, then search for the key (node). In very rare cases this node might no longer exist, in that case we can just wait for next gc.
3) module exit function needs rcu_barrier before we zap the kmem cache.
4) use disable_work_sync(), we don't want any restarts.
---
v3: no changes.
net/netfilter/nf_conncount.c | 54 +++++++++++++++++++++--------------- 1 file changed, 32 insertions(+), 22 deletions(-)
net/netfilter/nf_conncount.c +32 -22
@@ -593,47 +593,54 @@ static void tree_gc_worker(struct work_struct *work) { struct nf_conncount_data *data = container_of(work, struct nf_conncount_data, gc_work);struct nf_conncount_rb *gc_nodes[CONNCOUNT_GC_MAX_NODES ], *rbconn; +unsigned int tree, next_tree, gc_count =0 ;struct nf_conncount_root *root;struct rb_node *node; -unsigned int tree, next_tree, gc_count =0 ; + +if (data->gc_tree ==0 ) + data->gc_tree =find_first_bit (data->pending_trees,CONNCOUNT_SLOTS ); tree = data->gc_tree %CONNCOUNT_SLOTS ; root = &data->root[tree]; -local_bh_disable (); -rcu_read_lock (); -for (node =rb_first (&root->root); node ; node =rb_next (node)) { - rbconn = rb_entry(node, struct nf_conncount_rb, node); -if (nf_conncount_gc_list (data->net, &rbconn->list)) - gc_count++; - } -rcu_read_unlock (); -local_bh_enable (); - -cond_resched (); -spin_lock_bh (&nf_conncount_locks[tree]); -if (gc_count <ARRAY_SIZE (gc_nodes)) - goto next;/* do not bother */ - gc_count =0 ; node =rb_first (&root->root);while (node !=NULL ) { +u32 key[MAX_KEYLEN ]; +bool drop_lock; + rbconn = rb_entry(node, struct nf_conncount_rb, node); node =rb_next (node); -if (rbconn->list.count >0 ) -continue ; +if (nf_conncount_gc_list (data->net, &rbconn->list)) + gc_nodes[gc_count++] = rbconn; + + drop_lock =need_resched (); - gc_nodes[gc_count++] = rbconn; -if (gc_count >=ARRAY_SIZE (gc_nodes)) { +if (drop_lock || gc_count >=ARRAY_SIZE (gc_nodes)) {tree_nodes_free (root, gc_nodes, gc_count); gc_count =0 ; } + +if (!drop_lock || !node) +continue ; + + rbconn = rb_entry(node, struct nf_conncount_rb, node); +memcpy (key, rbconn->key,sizeof (key)); +spin_unlock_bh (&nf_conncount_locks[tree]); + +cond_resched (); + +spin_lock_bh (&nf_conncount_locks[tree]); + rbconn =find_tree_node (root, data, key, true); +if (IS_ERR_OR_NULL (rbconn))/* rbconn was reaped */ +break ; + + node = &rbconn->node; }tree_nodes_free (root, gc_nodes, gc_count); -next:clear_bit (tree, data->pending_trees); next_tree = (tree +1 ) %CONNCOUNT_SLOTS ;
@@ -642,6 +649,8 @@ static void tree_gc_worker(struct work_struct *work)if (next_tree <CONNCOUNT_SLOTS ) { data->gc_tree = next_tree;schedule_work (work); + }else { + data->gc_tree =0 ; }spin_unlock_bh (&nf_conncount_locks[tree]);
@@ -725,7 +734,7 @@ void nf_conncount_destroy(struct net *net, struct nf_conncount_data *data) {unsigned int i; -cancel_work_sync (&data->gc_work); +disable_work_sync (&data->gc_work);for (i =0 ; i <ARRAY_SIZE (data->root); ++i)destroy_tree (&data->root[i]);
@@ -756,6 +765,7 @@ static int __init nf_conncount_modinit(void) static void __exit nf_conncount_modexit(void) { +rcu_barrier ();kmem_cache_destroy (conncount_conn_cachep);kmem_cache_destroy (conncount_rb_cachep); }
Signature · 1 line
2.54.0