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

[Yury Norov <yury.norov@gmail.com>]

On Tue, Oct 28, 2025 at 09:48:04PM +0000, Alice Ryhl wrote:
> 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.

You can use test_and_set_bit(), so that even if multiple threads will
find the same bit, only one will actually acquire it.

> But even if we changed it to perform a
> correct atomic bit-acquire, the fact that IdPool is resizable also
> incurs a locking requirement.

To address resizing, you can use RCU engine, so that resize is
possible only during grace period.
 
> 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.

OK then.

There's still no real users for the IdPool, so the above performance
hints make no practical reasons. Are there any plans to actually start
using IdPool in the mainline kernel?

Thanks,
Yury