netfilter: nfnetlink_queue: optimize verdict lookup with hash table
Subsystems (2)
PATCH v7 1/1 netfilter: nfnetlink_queue: optimize verdict lookup with hash table
From: Scott Mitchell <[email protected]>
The current implementation uses a linear list to find queued packets by ID when processing verdicts from userspace. With large queue depths and out-of-order verdicting, this O(n) lookup becomes a significant bottleneck, causing userspace verdict processing to dominate CPU time.
Replace the linear search with a hash table for O(1) average-case packet lookup by ID. A global rhashtable spanning all network namespaces attributes hash bucket memory to kernel but is subject to fixed upper bound.
---
Changes in v7:
- Use global rhashtable instead of per-queue hash.
- Split previous patch 1 (no longer necessary for rhashtable) into independent patch series.
Changes in v6:
- Split into 2-patch series
- Patch 1: Refactor locking to allow GFP_KERNEL_ACCOUNT allocation in instance_create() by dropping RCU lock after instance_lookup() and peer_portid verification (Florian Westphal)
- Patch 2: Remove UAPI for hash size, automatic resize, attribute memory to cgroup.
Changes in v5:
- Use GFP_ATOMIC with kvmalloc_array instead of GFP_KERNEL_ACCOUNT due to rcu_read_lock held in nfqnl_recv_config. Add comment explaining that GFP_KERNEL_ACCOUNT would require lock refactoring (Florian Westphal)
Changes in v4:
- Fix sleeping while atomic bug: allocate hash table before taking spinlock in instance_create() (syzbot)
Changes in v3:
- Simplify hash function to use direct masking (id & mask) instead of hash_32() for better cache locality with sequential IDs (Eric Dumazet)
Changes in v2:
- Use kvcalloc/kvfree with GFP_KERNEL_ACCOUNT to support larger hash tables with vmalloc fallback (Florian Westphal)
- Remove incorrect comment about concurrent resizes - nfnetlink subsystem mutex already serializes config operations (Florian Westphal)
- Fix style: remove unnecessary braces around single-line if (Florian Westphal)
include/net/netfilter/nf_queue.h | 3 + net/netfilter/nfnetlink_queue.c | 129 ++++++++++++++++++++++++++----- 2 files changed, 113 insertions(+), 19 deletions(-)
include/net/netfilter/nf_queue.h +3 -0
@@ -6,11 +6,13 @@#include <linux/ipv6.h> #include <linux/jhash.h> #include <linux/netfilter.h> +#include <linux/rhashtable-types.h> #include <linux/skbuff.h> /* Each queued (to userspace) skbuff has one of these. */ struct nf_queue_entry {struct list_head list; +struct rhash_head hash_node;struct sk_buff *skb;unsigned int id;unsigned int hook_index;/* index in hook_entries->hook[] */
@@ -20,6 +22,7 @@ struct nf_queue_entry {#endif struct nf_hook_state state;u16 size;/* sizeof(entry) + saved route keys */ +u16 queue_num;/* extra space to store route keys */ };
net/netfilter/nfnetlink_queue.c +110 -19
222 lines not on this page · raw message
Signature · 1 line
2.39.5 (Apple Git-154)
Florian Westphal
maintainer[email protected] <[email protected]> wrote:
LGTM, just a few minor nits.
Quoted 30 lines
include/net/netfilter/nf_queue.h +3
-0@@ -6,11 +6,13 @@#include <linux/ipv6.h> #include <linux/jhash.h> #include <linux/netfilter.h> +#include <linux/rhashtable-types.h> #include <linux/skbuff.h> /* Each queued (to userspace) skbuff has one of these. */ struct nf_queue_entry {struct list_head list; +struct rhash_head hash_node;struct sk_buff *skb;unsigned int id;unsigned int hook_index;/* index in hook_entries->hook[] */ @@ -20,6 +22,7 @@ struct nf_queue_entry {#endif struct nf_hook_state state;u16 size;/* sizeof(entry) + saved route keys */ +u16 queue_num;/* extra space to store route keys */ };net/netfilter/nfnetlink_queue.c +0
-0
net/netfilter/nfnetlink_queue.c line 65
Quoted 5 lines
net/netfilter/nfnetlink_queue.c +3
-0#define NFQNL_MAX_COPY_RANGE (0xffff - NLA_HDRLEN) +/* Composite key for packet lookup: (net, queue_num, packet_id) */ +struct nfqnl_packet_key { +struct net *net;
possible_net_t net;
so we don't have this member for CONFIG_NET_NS=n
Quoted 13 lines
net/netfilter/nfnetlink_queue.c +7
-0+u32 packet_id; +u16 queue_num; +}; + +/* Global rhashtable - one for entire system, all netns */ +static struct rhashtable nfqnl_packet_map__read_mostly ; +struct nfqnl_instance {struct hlist_node hlist;/* global list of queues */ struct rcu_head rcu;@@ -100,6 +114,45 @@ static inline u_int8_t instance_hashfn(u_int16_t queue_num)return ((queue_num >>8 ) ^ queue_num) %INSTANCE_BUCKETS ; }
net/netfilter/nfnetlink_queue.c static inline u_int8_t instance_hashfn(u_int16_t queue_num) · line 125
Quoted 10 lines
net/netfilter/nfnetlink_queue.c +9
-0+/* Extract composite key from nf_queue_entry for hashing */ +static u32 nfqnl_packet_obj_hashfn (const void *data,u32 len,u32 seed) +{ +const struct nf_queue_entry *entry = data; +struct nfqnl_packet_key key; + +/* Zero entire struct including padding to ensure deterministic hashing */ +memset (&key,0 ,sizeof (key)); + key.net = entry->state.net;
write_pnet()
net/netfilter/nfnetlink_queue.c static inline u_int8_t instance_hashfn(u_int16_t queue_num) · line 130
Quoted 2 lines
net/netfilter/nfnetlink_queue.c +2
-0+/* jhash2 requires size to be a multiple of sizeof(u32) */ +BUILD_BUG_ON (sizeof (key) %sizeof (u32) !=0 );
I wonder if this works on 32bit.
If not, alternative is to either add __align to the struct or to resort to jhash_3words().
Up to you.
net/netfilter/nfnetlink_queue.c static inline u_int8_t instance_hashfn(u_int16_t queue_num) · line 141
Quoted 8 lines
net/netfilter/nfnetlink_queue.c +8
-0+/* Compare stack-allocated key against entry */ +static int nfqnl_packet_obj_cmpfn (struct rhashtable_compare_arg *arg, +const void *obj) +{ +const struct nfqnl_packet_key *key = arg->key; +const struct nf_queue_entry *entry = obj; + + return entry->state.net != key->net ||
net_eq(entry->state.net, read_pnet( ...
net/netfilter/nfnetlink_queue.c instance_destroy(struct nfnl_queue_net *q, struct nfqnl_instance *inst) · line 249
Quoted 3 lines
net/netfilter/nfnetlink_queue.c +1
-0+static inline int __enqueue_entry (struct nfqnl_instance *queue,struct nf_queue_entry *entry) {
Is the inline keyword needed here?
net/netfilter/nfnetlink_queue.c instance_destroy(struct nfnl_queue_net *q, struct nfqnl_instance *inst) · line 285
Quoted 4 lines
net/netfilter/nfnetlink_queue.c +4
-0+memset (&key,0 ,sizeof (key)); + key.net = net; + key.packet_id = id; + key.queue_num = queue->queue_num;
Maybe its worth to add a small helper that fills the structure.
net/netfilter/nfnetlink_queue.c __nfqnl_enqueue_packet(struct net *net, struct nfqnl_instance *queue, · line 983
Quoted 11 lines
net/netfilter/nfnetlink_queue.c +11
-0+/* Insert into hash BEFORE unicast. If failure don't send to userspace. */ + err =__enqueue_entry (queue, entry); +if (unlikely (err)) { +if (queue->flags &NFQA_CFG_F_FAIL_OPEN ) { + failopen =1 ; + err =0 ; + }else { + queue->queue_dropped++; +net_warn_ratelimited ("nf_queue: hash insert failed: %d\n" , err); + } + goto err_out_free_nskb;
This repeated conditional is not so nice, is there a way to avoid it? E.g. new common helper or via goto.
net/netfilter/nfnetlink_queue.c static int __init nfnetlink_queue_init(void) · line 1868
Quoted 3 lines
net/netfilter/nfnetlink_queue.c +3
-0+ status =rhashtable_init (&nfqnl_packet_map, &nfqnl_rhashtable_params); +if (status <0 ) { +pr_err ("failed to init packet hash table\n" );
Please remove this pr_err, kernel gets quite noisy when it starts to run out of memory. The other pr_err()s init .init are just historic artefacts.
Comments make sense and I will address them with a v8.
Quoted 5 lines
Quoted 3 lines
+static inline int
__enqueue_entry(struct nfqnl_instance *queue, struct nf_queue_entry *entry){Is the inline keyword needed here?
I will remove it for v8.