diff options
| author | Scott Mitchell <scott.k.mitch1@gmail.com> | 2026-01-23 14:09:30 -0800 |
|---|---|---|
| committer | Florian Westphal <fw@strlen.de> | 2026-01-29 09:52:07 +0100 |
| commit | e19079adcd26a25d7d3e586b1837493361fdf8b6 (patch) | |
| tree | db0169206b20d0b70c66cbd47bb70f1cc3ac280b /include | |
| parent | 77fd1b4c6e084619beff1a55cb66e65c6a66615c (diff) | |
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 <scott.k.mitch1@gmail.com>
Signed-off-by: Florian Westphal <fw@strlen.de>
Diffstat (limited to 'include')
| -rw-r--r-- | include/net/netfilter/nf_queue.h | 3 |
1 files changed, 3 insertions, 0 deletions
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 <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 */ }; |