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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAFn2buA+uHsRLU-TG9Xy42-pATex9Hh7kD4uCtcVRHAKVCgZow@mail.gmail.com>
Date: Thu, 13 Nov 2025 08:18:42 -0800
From: Scott Mitchell <scott.k.mitch1@...il.com>
To: Eric Dumazet <edumazet@...gle.com>
Cc: pablo@...filter.org, kadlec@...filter.org, fw@...len.de, phil@....cc, 
	davem@...emloft.net, kuba@...nel.org, pabeni@...hat.com, horms@...nel.org, 
	netfilter-devel@...r.kernel.org, coreteam@...filter.org, 
	netdev@...r.kernel.org, linux-kernel@...r.kernel.org, 
	syzbot@...kaller.appspotmail.com
Subject: Re: [PATCH v4] netfilter: nfnetlink_queue: optimize verdict lookup
 with hash table

On Thu, Nov 13, 2025 at 7:50 AM Eric Dumazet <edumazet@...gle.com> wrote:
>
> On Thu, Nov 13, 2025 at 7:46 AM Scott Mitchell <scott.k.mitch1@...il.com> wrote:
> >
> > From: Scott Mitchell <scott.k.mitch1@...il.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 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@...il.com>
>
> 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).