netdev - Re: [RFC PATCH bpf-next 2/3] bpf: udp: Avoid socket skips and repeats during iteration

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250408001649.5560-1-kuniyu@amazon.com>
Date: Mon, 7 Apr 2025 17:16:25 -0700
From: Kuniyuki Iwashima <kuniyu@...zon.com>
To: <jordan@...fe.io>
CC: <aditi.ghag@...valent.com>, <bpf@...r.kernel.org>, <daniel@...earbox.net>,
	<kuniyu@...zon.com>, <martin.lau@...ux.dev>, <netdev@...r.kernel.org>,
	<willemdebruijn.kernel@...il.com>
Subject: Re: [RFC PATCH bpf-next 2/3] bpf: udp: Avoid socket skips and repeats during iteration

From: Jordan Rife <jordan@...fe.io>
Date: Mon, 7 Apr 2025 16:30:46 -0700
> > We may need to iterate all visited sockets again in this bucket if all
> > unvisited sockets disappear from the previous iteration.
> 
> If the next socket disappears between iterator stop and start, the
> outer loop would need to keep going until it finds a socket from last
> time that still exists. In most cases, it seems unlikely that the next
> socket will disappear between iterator reads, so in general the outer
> loop would only need to iterate once; the common case should perform
> the same as before with the offset approach. The worst case indeed
> would be if all the sockets disappear between reads. Then you'd have
> to scan through all items in the bucket n_cookies times. Again though,
> this is hopefully a rare case.
> 
> > When the number of the unvisited sockets is small like 1, the duplicated
> > records will not be rare and rather more often than before ?
> 
> Sorry if I'm missing something, but what's the relationship between
> the number of unvisited sockets and rarity of duplicated records?

Sorry, I misread the code, and s/duplicated/skipped/.

I was thinking that rarity of such unwanted events depends on how
many unvisited sockets are left before restarting.

Let's say batch has 16 sockets and the iterator stopped at 15,
it's more likely that a single socket disappear.

This should be fine given the batch size normally covers the full
bucket of the hash, and it's unlikely that many sockets are added
in the bucket between stop and restart.

In the worst case, where vmalloc() fails and the batch does not
cover full bucket, say the batch size is 16 but the list length
is 256, if the iterator stops at sk15 and sk16 disappers,
sk17 ~ sk256 will be skipped in the next iteration.

 sk1 -> ... sk15 -> sk16 -> sk17 -> ... -> sk256