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

Message-ID: <CACQBu=XmC-9OHSHv_9KP88HpV3Ei83gmNmy-B8DAfbtipKmyLQ@mail.gmail.com>
Date: Mon, 26 May 2025 16:22:29 +0200
From: Burak Emir <bqe@...gle.com>
To: Yury Norov <yury.norov@...il.com>
Cc: Carlos Llamas <cmllamas@...gle.com>, Boqun Feng <boqun.feng@...il.com>, 
	Jann Horn <jannh@...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 3:50 PM Yury Norov <yury.norov@...il.com> wrote:
>
> 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 all for the additional context.

Yury, I've addressed most of the comments.

You also commented on the API. The weirdness of the API is all due to
the separating "request to shrink/grow" from allocation.
Since allocation can happen while other threads may mess with the id
pool, one has to double check that the request to shrink/grow still
makes sense.
Dealing with this situation is required in the Android binder context
where this ID pool is used, my understanding is that one cannot
allocate there while holding the spinlock.

In the next version, I have renamed the operations to make this a bit
clearer, and made the comments a bit more explicit.
If it's ok, let's move the discussion to v9 that I will send in a
moment, I hope it clears things up a bit.

Thanks.
Burak