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

[Scott Mitchell]

On Thu, Nov 13, 2025 at 7:50 AM Eric Dumazet <edumazet@xxxxxxxxxx> wrote:
>
> 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.

ack. I will wait 24 hours to address Florian's comments on v3 (unless
instructed otherwise).