Skip to contentSkip to conversation

netfilter: nfnetlink_queue: optimize verdict lookup with hash table

PATCH Superseded [email protected] 2 participants 3 messages Jan 23

Subsystems (2)

v7 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

PATCH v7 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 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  | 129 ++++++++++++++++++++++++++-----
 2 files changed, 113 insertions(+), 19 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 +110 -19

222 lines not on this page · raw message

Signature · 1 line
2.39.5 (Apple Git-154)
maintainer
#1 lore raw

[email protected] <[email protected]> wrote:

LGTM, just a few minor nits.

Quoted 30 lines
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 +0 -0
index 8b7b39d8a109..e7372955c5a8 100644

net/netfilter/nfnetlink_queue.c line 65

Quoted 5 lines
net/netfilter/nfnetlink_queue.c +3 -0
 #define NFQNL_MAX_COPY_RANGE (0xffff - NLA_HDRLEN)
 
+/* Composite key for packet lookup: (net, queue_num, packet_id) */
+struct nfqnl_packet_key {
+	struct net *net;

possible_net_t net;

so we don't have this member for CONFIG_NET_NS=n

Quoted 13 lines
net/netfilter/nfnetlink_queue.c +7 -0
+	u32 packet_id;
+	u16 queue_num;
+};
+
+/* Global rhashtable - one for entire system, all netns */
+static struct rhashtable nfqnl_packet_map __read_mostly;
+
 struct nfqnl_instance {
 	struct hlist_node hlist;		/* global list of queues */
 	struct rcu_head rcu;
@@ -100,6 +114,45 @@ static inline u_int8_t instance_hashfn(u_int16_t queue_num)
 	return ((queue_num >> 8) ^ queue_num) % INSTANCE_BUCKETS;
 }

net/netfilter/nfnetlink_queue.c static inline u_int8_t instance_hashfn(u_int16_t queue_num) · line 125

Quoted 10 lines
net/netfilter/nfnetlink_queue.c +9 -0
 
+/* Extract composite key from nf_queue_entry for hashing */
+static u32 nfqnl_packet_obj_hashfn(const void *data, u32 len, u32 seed)
+{
+	const struct nf_queue_entry *entry = data;
+	struct nfqnl_packet_key key;
+
+	/* Zero entire struct including padding to ensure deterministic hashing */
+	memset(&key, 0, sizeof(key));
+	key.net = entry->state.net;

write_pnet()

net/netfilter/nfnetlink_queue.c static inline u_int8_t instance_hashfn(u_int16_t queue_num) · line 130

Quoted 2 lines
net/netfilter/nfnetlink_queue.c +2 -0
+	/* jhash2 requires size to be a multiple of sizeof(u32) */
+	BUILD_BUG_ON(sizeof(key) % sizeof(u32) != 0);

I wonder if this works on 32bit.

If not, alternative is to either add __align to the struct or to resort to jhash_3words().

Up to you.

net/netfilter/nfnetlink_queue.c static inline u_int8_t instance_hashfn(u_int16_t queue_num) · line 141

Quoted 8 lines
net/netfilter/nfnetlink_queue.c +8 -0
+/* Compare stack-allocated key against entry */
+static int nfqnl_packet_obj_cmpfn(struct rhashtable_compare_arg *arg,
+				  const void *obj)
+{
+	const struct nfqnl_packet_key *key = arg->key;
+	const struct nf_queue_entry *entry = obj;
+
+	return entry->state.net != key->net ||

net_eq(entry->state.net, read_pnet( ...

net/netfilter/nfnetlink_queue.c instance_destroy(struct nfnl_queue_net *q, struct nfqnl_instance *inst) · line 249

Quoted 3 lines
net/netfilter/nfnetlink_queue.c +1 -0
+static inline int
 __enqueue_entry(struct nfqnl_instance *queue, struct nf_queue_entry *entry)
 {

Is the inline keyword needed here?

net/netfilter/nfnetlink_queue.c instance_destroy(struct nfnl_queue_net *q, struct nfqnl_instance *inst) · line 285

Quoted 4 lines
net/netfilter/nfnetlink_queue.c +4 -0
+	memset(&key, 0, sizeof(key));
+	key.net = net;
+	key.packet_id = id;
+	key.queue_num = queue->queue_num;

Maybe its worth to add a small helper that fills the structure.

net/netfilter/nfnetlink_queue.c __nfqnl_enqueue_packet(struct net *net, struct nfqnl_instance *queue, · line 983

Quoted 11 lines
net/netfilter/nfnetlink_queue.c +11 -0
+	/* Insert into hash BEFORE unicast. If failure don't send to userspace. */
+	err = __enqueue_entry(queue, entry);
+	if (unlikely(err)) {
+		if (queue->flags & NFQA_CFG_F_FAIL_OPEN) {
+			failopen = 1;
+			err = 0;
+		} else {
+			queue->queue_dropped++;
+			net_warn_ratelimited("nf_queue: hash insert failed: %d\n", err);
+		}
+		goto err_out_free_nskb;

This repeated conditional is not so nice, is there a way to avoid it? E.g. new common helper or via goto.

net/netfilter/nfnetlink_queue.c static int __init nfnetlink_queue_init(void) · line 1868

Quoted 3 lines
net/netfilter/nfnetlink_queue.c +3 -0
+	status = rhashtable_init(&nfqnl_packet_map, &nfqnl_rhashtable_params);
+	if (status < 0) {
+		pr_err("failed to init packet hash table\n");

Please remove this pr_err, kernel gets quite noisy when it starts to run out of memory. The other pr_err()s init .init are just historic artefacts.

#2 lore raw

Comments make sense and I will address them with a v8.

Quoted 5 lines
Quoted 3 lines

+static inline int
__enqueue_entry(struct nfqnl_instance *queue, struct nf_queue_entry *entry) {

Is the inline keyword needed here?

I will remove it for v8.