netfilter: nfnetlink_queue: optimize verdict lookup with hash table
Subsystems (3)
PATCH v4 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 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 | 1 + .../uapi/linux/netfilter/nfnetlink_queue.h | 1 + net/netfilter/nfnetlink_queue.c | 128 ++++++++++++++++-- 3 files changed, 122 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 +120 -8
246 lines not on this page · raw message
Signature · 1 line
2.39.5 (Apple Git-154)
Quoted 16 lines · Scott Mitchell
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_SIZEnetlink attribute (default 1024 buckets, matchingNFQNL_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.
Quoted 6 lines
The existing list data structure is retained for operations requiring linear iteration (e.g. flush, device down events). Hot fields (
queue_hash_mask,queue_hashpointer) are placed in the same cache line as the spinlock and packet counters for optimal memory access patterns.Signed-off-by Scott Mitchell <[email protected]>
Please wait ~24 hours between each version.
Documentation/process/maintainer-netdev.rst
Thank you.
Quoted 23 lines · Eric Dumazet
Quoted 21 lines · Scott Mitchell
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_SIZEnetlink attribute (default 1024 buckets, matchingNFQNL_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_hashpointer) are placed in the same cache line as the spinlock and packet counters for optimal memory access patterns.
Quoted 7 lines
Quoted 1 line
Signed-off-by Scott Mitchell <[email protected]>Please wait ~24 hours between each version.
Documentation/process/maintainer-netdev.rstThank you.
ack. I will wait 24 hours to address Florian's comments on v3 (unless instructed otherwise).