linux-kernel - Re: [PATCH v3 4/5] rust: id_pool: do not immediately acquire new ids

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: <aQE6FOn_9Z84NMnG@google.com>
Date: Tue, 28 Oct 2025 21:48:04 +0000
From: Alice Ryhl <aliceryhl@...gle.com>
To: Yury Norov <yury.norov@...il.com>
Cc: Greg Kroah-Hartman <gregkh@...uxfoundation.org>, 
	"Arve Hjønnevåg" <arve@...roid.com>, Todd Kjos <tkjos@...roid.com>, Martijn Coenen <maco@...roid.com>, 
	Joel Fernandes <joelagnelf@...dia.com>, Christian Brauner <brauner@...nel.org>, 
	Carlos Llamas <cmllamas@...gle.com>, Suren Baghdasaryan <surenb@...gle.com>, Burak Emir <bqe@...gle.com>, 
	Miguel Ojeda <ojeda@...nel.org>, Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>, 
	"Björn Roy Baron" <bjorn3_gh@...tonmail.com>, Benno Lossin <lossin@...nel.org>, 
	Andreas Hindborg <a.hindborg@...nel.org>, Trevor Gross <tmgross@...ch.edu>, 
	Danilo Krummrich <dakr@...nel.org>, rust-for-linux@...r.kernel.org, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3 4/5] rust: id_pool: do not immediately acquire new ids

On Tue, Oct 28, 2025 at 02:42:13PM -0400, Yury Norov wrote:
> On Tue, Oct 28, 2025 at 10:55:17AM +0000, Alice Ryhl wrote:
> > When Rust Binder assigns a new ID, it performs various fallible
> > operations before it "commits" to actually using the new ID. To support
> > this pattern, change acquire_next_id() so that it does not immediately
> > call set_bit(), but instead returns an object that may be used to call
> > set_bit() later.
> > 
> > The UnusedId type holds a exclusive reference to the IdPool, so it's
> > guaranteed that nobody else can call find_unused_id() while the UnusedId
> > object is live.
> 
> Hi Alice,
> 
> I'm not sure about this change, but it looks like a lock wrapping
> acquire_next_id().
> 
> If so, we don't protect functions with locks, we protect data
> structures.
> 
> If the above is wrong, and this new UnusedId type serializes all
> accesses to a bitmap (lock-like), or write-accesses (rw-lock like),
> then this is still questionable.
> 
> Bitmaps are widely adopted as a lockless data structure among the
> kernel. If you modify bitmaps with set_bit() and clear_bit() only,
> with some precautions you are running race-proof. The kernel lacks
> for atomic bit-aquire function, but you can implement it youself.
> 
> I actually proposed atomic acquire API, but it was rejected:
> 
> https://lore.kernel.org/all/20240620175703.605111-2-yury.norov@gmail.com/
> 
> You can check the above series for a number of examples.
> 
> Bitmaps are widely used because they allow to implement lockless data
> access so cheap with just set_bit() and clear_bit(). There's nothing
> wrong to allocate a bit and release it shortly in case of some error
> just because it's really cheap.
> 
> So, with all the above said, I've nothing against this UnusedId,
> but if you need it to only serialize the access to an underlying
> bitmap, can you explain in more details what's wrong with the existing
> pattern? If you have a performance impact in mind, can you show any
> numbers?
> 
> Thanks,
> Yury

Hi Yury,

This does not change the locking requirements of IdPool at all. Both
before and after this change, acquiring a bit from the pool uses the
signature &mut self, which means that the caller of the method is
required to enforce exclusive access to the entire IdPool (doesn't have
to be a lock - the caller may use any exclusion mechanism of its
choosing). In the case of Rust Binder, exclusive access is enforced
using a spinlock. In the case of the examples in IdPool docs, exclusive
access is enforced by having the IdPool be stored in a local variable
that has not been shared with anyone.

It's true that the underlying bitmap supports lockless/atomic operations
by using the methods set_bit_atomic() and similar. Those methods are
&self rather than &mut self because they do not require exclusive access
to the entire Bitmap. But IdPool can't provide &self methods. The
existing acquire_next_id() method has a race condition if you tried to
perform two calls in parallel. But even if we changed it to perform a
correct atomic bit-acquire, the fact that IdPool is resizable also
incurs a locking requirement.

The only purpose of this UnusedId change is to make use of RAII to
automatically clean up the acquired ID in error paths. I avoided
setting the bit right away for simplicity, but setting the bit and
unsetting it in error paths via RAII would also work. But there would
still be a lock in Rust Binder that protects the bitmap without this
change.

Alice