Skip to contentSkip to conversation

netfilter: nfnetlink_queue: optimize verdict lookup with hash table

PATCH In review [email protected] 2 participants 2 messages Jan 23 – Jan 24

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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
index 4aeffddb7586..e6803831d6af 100644
@@ -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)
maintainer
#1 lore raw
Quoted 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.

Thanks for addressing all my comments, I don't see anything else that would block this from getting merged.