Re: [PATCH v12 5/5] rust: add dynamic ID pool abstraction for bitmap

[Alice Ryhl]

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@xxxxxxxxxx>
> Suggested-by: Yury Norov <yury.norov@xxxxxxxxx>
> Signed-off-by: Burak Emir <bqe@xxxxxxxxxx>
> ---
>  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@xxxxxxxxx>
>  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@xxxxxxxxx>
> 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.

> +    #[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.

> +        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.

Alice