diff options
| author | Scott Mitchell <scott.k.mitch1@gmail.com> | 2026-01-23 14:09:30 -0800 |
|---|---|---|
| committer | Greg Kroah-Hartman <gregkh@linuxfoundation.org> | 2026-02-26 15:01:11 -0800 |
| commit | 70e2e3ce4f6841e12ec1c104fc76c0e707398ec4 (patch) | |
| tree | 6f8058130885019163bd73ea42c176327fccf834 /include/net | |
| parent | 8f78f5fadccf0db798189f4fafe10be4be43c548 (diff) | |
netfilter: nfnetlink_queue: optimize verdict lookup with hash table
[ Upstream commit e19079adcd26a25d7d3e586b1837493361fdf8b6 ]
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>
Stable-dep-of: 207b3ebacb61 ("netfilter: nfnetlink_queue: do shared-unconfirmed check before segmentation")
Signed-off-by: Sasha Levin <sashal@kernel.org>
Diffstat (limited to 'include/net')
| -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 */ }; |