Message-ID: <CACQBu=VnqSHMPaMgMKGOt6E5Aw=bB94uVwKQYypwEXhHp91oXQ@mail.gmail.com>
Date: Fri, 20 Jun 2025 10:27:41 +0200
From: Burak Emir <bqe@...gle.com>
To: Alice Ryhl <aliceryhl@...gle.com>
Cc: Yury Norov <yury.norov@...il.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>, 
	Boqun Feng <boqun.feng@...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>, 
	Trevor Gross <tmgross@...ch.edu>, "Gustavo A . R . Silva" <gustavoars@...nel.org>, 
	Carlos LLama <cmllamas@...gle.com>, Pekka Ristola <pekkarr@...tonmail.com>, 
	rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org, 
	linux-hardening@...r.kernel.org
Subject: Re: [PATCH v12 5/5] rust: add dynamic ID pool abstraction for bitmap

On Thu, Jun 12, 2025 at 11:09 AM Alice Ryhl <aliceryhl@...gle.com> wrote:
>
> On Wed, Jun 11, 2025 at 07:48:38PM +0000, Burak Emir wrote:
> > This is a port of the Binder data structure introduced in commit
> > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > Rust.
> >
> > Like drivers/android/dbitmap.h, the ID pool abstraction lets
> > clients acquire and release IDs. The implementation uses a bitmap to
> > know what IDs are in use, and gives clients fine-grained control over
> > the time of allocation. This fine-grained control is needed in the
> > Android Binder. We provide an example that release a spinlock for
> > allocation and unit tests (rustdoc examples).
> >
> > The implementation does not permit shrinking below capacity below
> > BITS_PER_LONG.
> >
> > Suggested-by: Alice Ryhl <aliceryhl@...gle.com>
> > Suggested-by: Yury Norov <yury.norov@...il.com>
> > Signed-off-by: Burak Emir <bqe@...gle.com>
> > ---
> >  MAINTAINERS            |   1 +
> >  rust/kernel/id_pool.rs | 223 +++++++++++++++++++++++++++++++++++++++++
> >  rust/kernel/lib.rs     |   1 +
> >  3 files changed, 225 insertions(+)
> >  create mode 100644 rust/kernel/id_pool.rs
> >
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index 943d85ed1876..bc95d98f266b 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -4134,6 +4134,7 @@ R:      Yury Norov <yury.norov@...il.com>
> >  S:   Maintained
> >  F:   lib/find_bit_benchmark_rust.rs
> >  F:   rust/kernel/bitmap.rs
> > +F:   rust/kernel/id_pool.rs
> >
> >  BITOPS API
> >  M:   Yury Norov <yury.norov@...il.com>
> > diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
> > new file mode 100644
> > index 000000000000..355a8ae93268
> > --- /dev/null
> > +++ b/rust/kernel/id_pool.rs
> > @@ -0,0 +1,223 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +// Copyright (C) 2025 Google LLC.
> > +
> > +//! Rust API for an ID pool backed by a [`Bitmap`].
> > +
> > +use crate::alloc::{AllocError, Flags};
> > +use crate::bitmap::Bitmap;
> > +
> > +/// Represents a dynamic ID pool backed by a [`Bitmap`].
> > +///
> > +/// Clients acquire and release IDs from unset bits in a bitmap.
> > +///
> > +/// The capacity of the ID pool may be adjusted by users as
> > +/// needed. The API supports the scenario where users need precise control
> > +/// over the time of allocation of a new backing bitmap, which may require
> > +/// release of spinlock.
> > +/// Due to concurrent updates, all operations are re-verified to determine
> > +/// if the grow or shrink is sill valid.
> > +///
> > +/// # Examples
> > +///
> > +/// Basic usage
> > +///
> > +/// ```
> > +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +/// use kernel::id_pool::IdPool;
> > +///
> > +/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
> > +/// for i in 0..64 {
> > +///   assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
> > +/// }
> > +///
> > +/// pool.release_id(23);
> > +/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
> > +///
> > +/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
> > +/// let resizer = pool.grow_request().ok_or(ENOSPC)?.realloc(GFP_KERNEL)?;
> > +/// pool.grow(resizer);
> > +///
> > +/// assert_eq!(pool.acquire_next_id(0), Some(64));
> > +/// # Ok::<(), Error>(())
> > +/// ```
> > +///
> > +/// Releasing spinlock to grow the pool
> > +///
> > +/// ```no_run
> > +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +/// use kernel::sync::{new_spinlock, SpinLock};
> > +/// use kernel::id_pool::IdPool;
> > +///
> > +/// fn get_id_maybe_realloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
> > +///   let mut pool = guarded_pool.lock();
> > +///   loop {
> > +///     match pool.acquire_next_id(0) {
> > +///       Some(index) => return Ok(index),
> > +///       None => {
> > +///         let alloc_request = pool.grow_request();
> > +///         drop(pool);
> > +///         let resizer = alloc_request.ok_or(AllocError)?.realloc(GFP_KERNEL)?;
> > +///         pool = guarded_pool.lock();
> > +///         pool.grow(resizer)
> > +///       }
> > +///     }
> > +///   }
> > +/// }
> > +/// ```
>
> These examples use two spaces for indentation, but in Rust we use four
> spaces.
>
> > +pub struct IdPool {
> > +    map: Bitmap,
> > +}
> > +
> > +/// Indicates that an [`IdPool`] should change to a new target size.
> > +pub struct ReallocRequest {
> > +    num_ids: usize,
> > +}
> > +
> > +/// Contains a [`Bitmap`] of a size suitable for reallocating [`IdPool`].
> > +pub struct PoolResizer {
> > +    new: Bitmap,
> > +}
> > +
> > +impl ReallocRequest {
> > +    /// Allocates a new backing [`Bitmap`] for [`IdPool`].
> > +    ///
> > +    /// This method only prepares reallocation and does not complete it.
> > +    /// Reallocation will complete after passing the [`PoolResizer`] to the
> > +    /// [`IdPool::grow`] or [`IdPool::shrink`] operation, which will check
> > +    /// that reallocation still makes sense.
> > +    pub fn realloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
> > +        let new = Bitmap::new(self.num_ids, flags)?;
> > +        Ok(PoolResizer { new })
> > +    }
> > +}
> > +
> > +impl IdPool {
> > +    /// Constructs a new [`IdPool`].
> > +    ///
> > +    /// [BITS_PER_LONG]: srctree/include/asm-generic/bitsperlong.h
> > +    /// A capacity below [`BITS_PER_LONG`][BITS_PER_LONG] is adjusted to
> > +    /// [`BITS_PER_LONG`][BITS_PER_LONG].
>
> I'm concerned that this might not render correctly in the html docs.
> Markdown links are usually written below the text and with an empty
> line:
>
> /// A capacity below [`BITS_PER_LONG`][BITS_PER_LONG] is adjusted to
> /// [`BITS_PER_LONG`][BITS_PER_LONG].
> ///
> /// [BITS_PER_LONG]: srctree/include/asm-generic/bitsperlong.h
>
> which can be further simplified to
>
> /// A capacity below [`BITS_PER_LONG`] is adjusted to [`BITS_PER_LONG`].
> ///
> /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
>
> Furthermore, if you declare a public BITS_PER_LONG constant on the Rust
> side like I suggested in my reply to one of the other patches, then it
> will automatically link to that if you've imported it with `use` and
> don't specify a link target:
>
> use kernel::bitmap::BITS_PER_LONG;
>
> /// A capacity below [`BITS_PER_LONG`] is adjusted to [`BITS_PER_LONG`].
>
> Same applies to other docs that link to this constant.

Previously, there was no BITS_PER_LONG in scope, so to make rustdoc work
I had resorted to clumsy way above. I had tried it locally, but was wondering
whether there is a better way.

In v13, I define a local BITS_PER_LONG usize const as you suggested on
the other file.
With that, it works and the code also reads better.
For a convenience const declaration, I think local redefinition is
better than linking elsewhere.

> > +    #[inline]
> > +    pub fn new(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
> > +        let num_ids = core::cmp::max(num_ids, bindings::BITS_PER_LONG as usize);
>
> Nit: I like to write usize::max(...) instead of core::cmp::max(...),
> which I think reads better.

Done

> > +        let map = Bitmap::new(num_ids, flags)?;
> > +        Ok(Self { map })
> > +    }
> > +
> > +    /// Returns how many IDs this pool can currently have.
> > +    #[expect(clippy::len_without_is_empty)]
> > +    #[inline]
> > +    pub fn len(&self) -> usize {
>
> Maybe this should be called capacity() instead? Or maybe we just don't
> have this method at all.

capacity sounds good. I think it is useful in helping readability.

Thanks,
Burak

Powered by blists - more mailing lists