From e19079adcd26a25d7d3e586b1837493361fdf8b6 Mon Sep 17 00:00:00 2001 From: Scott Mitchell Date: Fri, 23 Jan 2026 14:09:30 -0800 Subject: netfilter: nfnetlink_queue: optimize verdict lookup with hash table 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. Signed-off-by: Scott Mitchell Signed-off-by: Florian Westphal --- include/net/netfilter/nf_queue.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'include/net') diff --git a/include/net/netfilter/nf_queue.h b/include/net/netfilter/nf_queue.h index 4aeffddb7586..e6803831d6af 100644 --- a/include/net/netfilter/nf_queue.h +++ b/include/net/netfilter/nf_queue.h @@ -6,11 +6,13 @@ #include #include #include +#include #include /* 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 */ }; -- cgit v1.2.3