Re: [PATCH v4] netfilter: nfnetlink_queue: optimize verdict lookup with hash table

[Eric Dumazet]

On Thu, Nov 13, 2025 at 7:46 AM Scott Mitchell <scott.k.mitch1@xxxxxxxxx> wrote:
>
> From: Scott Mitchell <scott.k.mitch1@xxxxxxxxx>
>
> 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 hash table size is configurable via the new
> NFQA_CFG_HASH_SIZE netlink attribute (default 1024 buckets, matching
> NFQNL_QMAX_DEFAULT; max 131072). The size is normalized to a power of
> two to enable efficient bitwise masking instead of modulo operations.
> Unpatched kernels silently ignore the new attribute, maintaining
> backward compatibility.
>
> The existing list data structure is retained for operations requiring
> linear iteration (e.g. flush, device down events). Hot fields
> (queue_hash_mask, queue_hash pointer) are placed in the same cache line
> as the spinlock and packet counters for optimal memory access patterns.
>
> Signed-off-by: Scott Mitchell <scott.k.mitch1@xxxxxxxxx>

Please wait ~24 hours between each version.

Documentation/process/maintainer-netdev.rst

Thank you.