[PATCH v6 0/2] netfilter: nfnetlink_queue: optimize verdict lookup with hash table

[scott.k.mitch1@gmail.com]

From: Scott Mitchell <scott.k.mitch1@gmail.com>

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. The existing list data structure is retained for
operations requiring linear iteration (e.g. flush, device down events).

Patch 1 refactors locking in nfqnl_recv_config() to allow GFP_KERNEL_ACCOUNT
allocation in instance_create(). This unifies the RCU locking pattern and
prepares for hash table initialization which requires sleeping allocation.

Patch 2 implements a manual hash table with automatic resizing. The hash
table grows at 75% load factor and shrinks at 25% load factor (with 60
second minimum between shrinks to prevent resize cycling). Memory is
allocated with GFP_KERNEL_ACCOUNT for proper cgroup attribution. Resize
operations are deferred to a work queue since they require GFP_KERNEL_ACCOUNT
allocation which cannot be done in softirq context.

v5: https://lore.kernel.org/netfilter-devel/20251122003720.16724-1-scott_mitchell@apple.com/

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)

Scott Mitchell (2):
  netfilter: nfnetlink_queue: nfqnl_instance GFP_ATOMIC ->
    GFP_KERNEL_ACCOUNT allocation
  netfilter: nfnetlink_queue: optimize verdict lookup with hash table

 include/net/netfilter/nf_queue.h |   1 +
 net/netfilter/nfnetlink_queue.c  | 304 ++++++++++++++++++++++++++-----
 2 files changed, 258 insertions(+), 47 deletions(-)

--
2.39.5 (Apple Git-154)