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

[Alice Ryhl]

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@xxxxxxxxx/
> 
> 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