netfilter: nfnetlink_queue: optimize verdict lookup with hash table
Subsystems (3)
PATCH v3 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. The hash table size is configurable via the new NFQA_CFG_HASH_SIZE netlink attribute (default 1024 buckets, matching NFQNL_QMAX_DEFAULT; max 131072). The size is normalized to a power of two to enable efficient bitwise masking instead of modulo operations. Unpatched kernels silently ignore the new attribute, maintaining backward compatibility.
The existing list data structure is retained for operations requiring linear iteration (e.g. flush, device down events). Hot fields (queue_hash_mask, queue_hash pointer) are placed in the same cache line as the spinlock and packet counters for optimal memory access patterns.
---
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 | 1 + .../uapi/linux/netfilter/nfnetlink_queue.h | 1 + net/netfilter/nfnetlink_queue.c | 129 ++++++++++++++++-- 3 files changed, 123 insertions(+), 8 deletions(-)
include/net/netfilter/nf_queue.h +1 -0
@@ -11,6 +11,7 @@/* Each queued (to userspace) skbuff has one of these. */ struct nf_queue_entry {struct list_head list; +struct hlist_node hash_node;struct sk_buff *skb;unsigned int id;unsigned int hook_index;/* index in hook_entries->hook[] */
include/uapi/linux/netfilter/nfnetlink_queue.h +1 -0
@@ -107,6 +107,7 @@ enum nfqnl_attr_config {NFQA_CFG_QUEUE_MAXLEN ,/* __u32 */ NFQA_CFG_MASK ,/* identify which flags to change */ NFQA_CFG_FLAGS ,/* value of these flags (__u32) */ +NFQA_CFG_HASH_SIZE ,/* __u32 hash table size (rounded to power of 2) */ __NFQA_CFG_MAX };#define NFQA_CFG_MAX (__NFQA_CFG_MAX-1)
net/netfilter/nfnetlink_queue.c +121 -8
247 lines not on this page · raw message
Signature · 1 line
2.39.5 (Apple Git-154)
Florian Westphal
maintainernet/netfilter/nfnetlink_queue.c instance_lookup(struct nfnl_queue_net *q, u_int16_t queue_num) · line 167
Quoted 12 lines · Scott Mitchell
net/netfilter/nfnetlink_queue.c +12
-0+static int +nfqnl_hash_resize (struct nfqnl_instance *inst,u32 hash_size) +{ +struct hlist_head *new_hash, *old_hash; +struct nf_queue_entry *entry; +unsigned int h, hash_mask; + + hash_size =nfqnl_normalize_hash_size (hash_size); +if (hash_size == inst->queue_hash_size) +return 0 ; + + new_hash =kvcalloc (hash_size,sizeof (*new_hash),GFP_KERNEL_ACCOUNT );
This doesn't work, please re-test with LOCKDEP enabled before sending next version.
net/netfilter/nfnetlink_queue.c instance_create(struct nfnl_queue_net *q, u_int16_t queue_num, u32 portid) · line 219
Quoted 2 lines
net/netfilter/nfnetlink_queue.c +2
-0+ inst->queue_hash =kvcalloc (hash_size,sizeof (*inst->queue_hash), +GFP_KERNEL_ACCOUNT );
.. and this doesn't work either, we are holding rcu read lock and the queue instance spinlock, so we cannot do a sleeping allocation.
That said, I don't see a compelling reason why rcu read lock is held here, but resolving that needs prep work :-/
So there are only two choices:
1. add a prep patch that pushes the locks to where they are needed, the rebase this patch on top
2. use GFP_ATOMIC like in v1 and update comment to say that GFP_KERNEL_ACCOUNT would need more work to place allocations outside of the locks.
Quoted 27 lines · Florian Westphal
net/netfilter/nfnetlink_queue.c instance_lookup(struct nfnl_queue_net *q, u_int16_t queue_num) · line 167
Quoted 12 lines · Scott Mitchell
net/netfilter/nfnetlink_queue.c +12
-0+static int +nfqnl_hash_resize (struct nfqnl_instance *inst,u32 hash_size) +{ +struct hlist_head *new_hash, *old_hash; +struct nf_queue_entry *entry; +unsigned int h, hash_mask; + + hash_size =nfqnl_normalize_hash_size (hash_size); +if (hash_size == inst->queue_hash_size) +return 0 ; + + new_hash =kvcalloc (hash_size,sizeof (*new_hash),GFP_KERNEL_ACCOUNT );This doesn't work, please re-test with LOCKDEP enabled before sending next version.
net/netfilter/nfnetlink_queue.c instance_create(struct nfnl_queue_net *q, u_int16_t queue_num, u32 portid) · line 219
Quoted 2 lines
net/netfilter/nfnetlink_queue.c +2
-0+ inst->queue_hash =kvcalloc (hash_size,sizeof (*inst->queue_hash), +GFP_KERNEL_ACCOUNT );.. and this doesn't work either, we are holding rcu read lock and the queue instance spinlock, so we cannot do a sleeping allocation.
That said, I don't see a compelling reason why rcu read lock is held here, but resolving that needs prep work :-/
Quoted 6 lines
So there are only two choices:
1. add a prep patch that pushes the locks to where they are needed, the rebase this patch on top
2. useGFP_ATOMIClike in v1 and update comment to say thatGFP_KERNEL_ACCOUNTwould need more work to place allocations outside of the locks.
I will go with option 2 to make incremental progress.