linux-kernel - Re: [PATCH v2] 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: <CAFn2buD7QWb42nVaG8yMhEA6+6VtTndk61E+_tZvydLm0Gs3qg@mail.gmail.com>
Date: Thu, 13 Nov 2025 12:56:25 -0800
From: Scott Mitchell <scott.k.mitch1@...il.com>
To: David Laight <david.laight.linux@...il.com>
Cc: Eric Dumazet <edumazet@...gle.com>, 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, 
	Scott Mitchell <scott_mitchell@...le.com>
Subject: Re: [PATCH v2] netfilter: nfnetlink_queue: optimize verdict lookup
 with hash table

On Thu, Nov 13, 2025 at 11:40 AM David Laight
<david.laight.linux@...il.com> wrote:
>
> On Thu, 13 Nov 2025 02:25:24 -0800
> Eric Dumazet <edumazet@...gle.com> wrote:
>
> > On Thu, Nov 13, 2025 at 1:26 AM Scott Mitchell <scott.k.mitch1@...il.com> wrote:
> ....
> > I do not think this is an efficient hash function.
> >
> > queue->id_sequence is monotonically increasing (controlled by the
> > kernel : __nfqnl_enqueue_packet(), not user space).
>
> If id_sequence is allocated by the kernel, is there any requirement
> that the values be sequential rather than just unique?

I will defer to maintainers for the authoritative answer, but
NFQNL_MSG_VERDICT_BATCH API semantics rely on sequential IDs
(nfqnl_recv_verdict_batch applies same verdict to all IDs <= max id).
New options could be added to opt-in to different ID generation
behavior (e.g. user acknowledging NFQNL_MSG_VERDICT_BATCH isn't used),
but not clear this would always be beneficial as "unique for all
packets" depends on size of map relative to number of un-verdicted
packets. Packets can be verdicted out-of-order which would require
additional tracking/searching to get "next unused ID".

>
> If they don't need to be sequential then the kernel can pick an 'id' value
> such that 'id & mask' is unique for all 'live' id values.
> Then the hash becomes 'perfect' and degenerates into a simple array lookup.
> Just needs a bit of housekeeping...
>
>         David