linux-kernel - Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

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: <aC3aOHWEGzjjDNgb@yury>
Date: Wed, 21 May 2025 09:50:48 -0400
From: Yury Norov <yury.norov@...il.com>
To: Carlos Llamas <cmllamas@...gle.com>
Cc: Boqun Feng <boqun.feng@...il.com>, Jann Horn <jannh@...gle.com>,
	Burak Emir <bqe@...gle.com>, Kees Cook <kees@...nel.org>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Viresh Kumar <viresh.kumar@...aro.org>,
	Miguel Ojeda <ojeda@...nel.org>,
	Alex Gaynor <alex.gaynor@...il.com>, Gary Guo <gary@...yguo.net>,
	Björn Roy Baron <bjorn3_gh@...tonmail.com>,
	Benno Lossin <benno.lossin@...ton.me>,
	Andreas Hindborg <a.hindborg@...nel.org>,
	Alice Ryhl <aliceryhl@...gle.com>, Trevor Gross <tmgross@...ch.edu>,
	"Gustavo A . R . Silva" <gustavoars@...nel.org>,
	rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org,
	linux-hardening@...r.kernel.org
Subject: Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

On Wed, May 21, 2025 at 03:57:55AM +0000, Carlos Llamas wrote:
> On Mon, May 19, 2025 at 08:57:04PM -0400, Yury Norov wrote:
> > + Carlos Llamas

...

> > Carlos, can you please elaborate your motivation to switch to bitmaps?
> > Have you considered rb-trees with O(logn) lookup?
> 
> Yeah, we tried rb-trees. There was even a patch that implemented the
> augmented logic. See this:
> https://lore.kernel.org/all/20240917030203.286-1-ebpqwerty472123@gmail.com/
> IIRC, it just didn't make sense for our use case because of the extra
> memory bytes required for this solution. The performance ended up being
> the same (from my local testing).
> 
> I'm not certain of this but one potential factor is that the rb nodes
> are in-strucutre members allocated separately. This can lead to more
> cache misses when traversing them. I don't know how applicable this
> would be for the Rust implementation though. Take that with a grain of
> salt as I didn't actually look super close while running the tests.
> 
> I would also note, this whole logic wouldn't be required if userspace
> wasn't using these descriptor IDs as vector indexes. At some point this
> practice will be fixed and we can remove the "dbitmap" implementation.

Yeah, I expected to get this kind of feedback from real-world testing.
Your reply to the patch you mentioned above answers all my questions:

https://lore.kernel.org/all/ZwdWe_I2p3zD-v1O@google.com/

Let's stick to bitmaps unless someone shows clear benefit of using any
alternative approach, both in time and memory perspectives, supported
by testing.

Thanks,
Yury