netfilter: nfnetlink_queue: optimize verdict lookup with hash table
Subsystems (2)
PATCH v8 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 v8:
- Use possible_net_t instead of struct net * in nfqnl_packet_key, with write_pnet()/read_pnet() helpers (Florian Westphal)
- Use net_eq() for network namespace comparison (Florian Westphal)
- Remove inline keyword from __enqueue_entry() (Florian Westphal)
- Add nfqnl_init_key() helper to centralize key initialization (Florian Westphal)
- Consolidate error handling with err_out_queue_drop label (Florian Westphal)
- Remove pr_err() on rhashtable_init() failure (Florian Westphal)
- Remove BUILD_BUG_ON - rely on __aligned(sizeof(u32)) for jhash2 compatibility (Florian Westphal)
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 | 146 ++++++++++++++++++++++++------- 2 files changed, 119 insertions(+), 30 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 +116 -30
245 lines not on this page · raw message
Signature · 1 line
2.39.5 (Apple Git-154)
Florian Westphal
maintainerQuoted 7 lines · [email protected] <[email protected]> wrote:
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.
Quoted 6 lines
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.
Signed-off-by Scott Mitchell <[email protected]>
Thanks for addressing all my comments, I don't see anything else that would block this from getting merged.