netfilter: nf_conncount: fix gc and
Subsystems (2)
Florian Westphal
maintainerv2 cover netfilter: nf_conncount: fix gc and
This addresses a drive-by AI review of nf_conncount. See patch 4 for details.
1) Replace rb_root with a new container structure in nf_conncount to prepare for a per-tree sequence counter to detect concurrent modifications.
2) Split nf_conncount rbtree walk into a helper. Add find_tree_node() to fetch matching node so folluwp patch can reuse the function.
3) Add a sequence count to detect concurrent rbtree modifications.
4) Fix tree_gc_worker wrap-around by updating gc_tree unconditionally. Add rcu_barrier before zapping the kmem cache during module exit.
Florian Westphal (4):
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 | 203 ++++++++++++++++++++++------------- 1 file changed, 130 insertions(+), 73 deletions(-)
Signature · 1 line
2.53.0
Florian Westphal
maintainerPATCH v2 2/4 netfilter: nf_conncount: split count_tree_node rbtree walk into helper
Add 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.
---
v2: no changes.
net/netfilter/nf_conncount.c | 96 ++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 38 deletions(-)
net/netfilter/nf_conncount.c +58 -38
@@ -488,23 +488,15 @@ insert_tree(struct net *net,return count; } -static unsigned int -count_tree (struct net *net, -const struct sk_buff *skb, -u16 l3num, -struct nf_conncount_data *data, -const u32 *key) +static struct nf_conncount_rb * +find_tree_node (struct nf_conncount_root *root,struct nf_conncount_data *data, +const u32 *key) { -struct nf_conncount_root *root;struct rb_node *parent; -struct nf_conncount_rb *rbconn; -unsigned int hash; - - hash =jhash2 (key, data->keylen, data->initval) %CONNCOUNT_SLOTS ; - root = &data->root[hash]; parent =rcu_dereference_raw (root->root.rb_node);while (parent) { +struct nf_conncount_rb *rbconn;int diff; rbconn = rb_entry(parent, struct nf_conncount_rb, node);
@@ -515,40 +507,68 @@ count_tree(struct net *net, }else if (diff >0 ) { parent =rcu_dereference_raw (parent->rb_right); }else { -int ret; +return rbconn; + } + } -if (!skb) { -nf_conncount_gc_list (net, &rbconn->list); -return rbconn->list.count; - } +return ERR_PTR (-ENOENT ); +} -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 ; - } +static unsigned int +count_tree (struct net *net, +const struct sk_buff *skb, +u16 l3num, +struct nf_conncount_data *data, +const u32 *key) +{ +struct nf_conncount_root *root; +struct nf_conncount_rb *rbconn; +unsigned int hash; +int ret; -/* 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; - } + hash =jhash2 (key, data->keylen, data->initval) %CONNCOUNT_SLOTS ; + root = &data->root[hash]; + + rbconn =find_tree_node (root, data, key); +if (IS_ERR (rbconn)) { +if (PTR_ERR (rbconn) == -ENOENT ) { +if (!skb) +return 0 ; + +return insert_tree (net, skb, l3num, data, hash, key); } +DEBUG_NET_WARN_ON_ONCE (IS_ERR (rbconn)); } -if (!skb) +DEBUG_NET_WARN_ON_ONCE (IS_ERR_OR_NULL (rbconn)); +if (IS_ERR_OR_NULL (rbconn))return 0 ; -return insert_tree (net, skb, l3num, data, hash, key); +if (!skb) { +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); + } + +/* 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 rbconn->list.count; }static void tree_gc_worker (struct work_struct *work)
Signature · 1 line
2.54.0
Florian Westphal
maintainerPATCH v2 1/4 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.
---
v2: 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_raw (root->rb_node); + parent =rcu_dereference_raw (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 v2 3/4 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.
---
v2: new in this iteration (split from last patch)
net/netfilter/nf_conncount.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
net/netfilter/nf_conncount.c +16 -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)
@@ -492,6 +497,7 @@ static struct nf_conncount_rb * find_tree_node(struct nf_conncount_root *root, struct nf_conncount_data *data, const u32 *key) { + unsigned int seq = read_seqcount_begin(&root->count);struct rb_node *parent; parent =rcu_dereference_raw (root->root.rb_node);
@@ -509,6 +515,9 @@ find_tree_node(struct nf_conncount_root *root, struct nf_conncount_data *data, }else {return rbconn; } + +if (read_seqcount_retry (&root->count, seq)) +return ERR_PTR (-EAGAIN ); }return ERR_PTR (-ENOENT );
@@ -531,6 +540,12 @@ count_tree(struct net *net, rbconn =find_tree_node (root, data, key);if (IS_ERR (rbconn)) { +if (PTR_ERR (rbconn) == -EAGAIN ) { +spin_lock_bh (&nf_conncount_locks[hash]); + rbconn =find_tree_node (root, data, key); +spin_unlock_bh (&nf_conncount_locks[hash]); + } +if (PTR_ERR (rbconn) == -ENOENT ) {if (!skb)return 0 ;
@@ -647,6 +662,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 v2 4/4 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.
---
v2: remove unsafe lockless walk
bump seqcnt on rb_erase
net/netfilter/nf_conncount.c | 54 +++++++++++++++++++++--------------- 1 file changed, 32 insertions(+), 22 deletions(-)
net/netfilter/nf_conncount.c +32 -22
@@ -590,47 +590,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); +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 ;
@@ -639,6 +646,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]);
@@ -722,7 +731,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]);
@@ -753,6 +762,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