From f5535d78e12600deb30a9fb3c628c425f0caec21 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 25 Nov 2025 13:59:37 +0000 Subject: rust: bitmap: add MAX_LEN and MAX_INLINE_LEN constants To avoid hard-coding these values in drivers, define constants for them that drivers can reference. Also, update all instances in bitmap.rs and id_pool.rs that use these values to use the new constants. Signed-off-by: Alice Ryhl Reviewed-by: Burak Emir Signed-off-by: Yury Norov (NVIDIA) --- rust/kernel/bitmap.rs | 33 +++++++++++++++++++-------------- rust/kernel/id_pool.rs | 39 ++++++++++++++++++++++----------------- 2 files changed, 41 insertions(+), 31 deletions(-) (limited to 'rust/kernel') diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index aa8fc7bf06fc..0705646c6251 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -12,8 +12,6 @@ use crate::bindings; use crate::pr_err; use core::ptr::NonNull; -const BITS_PER_LONG: usize = bindings::BITS_PER_LONG as usize; - /// Represents a C bitmap. Wraps underlying C bitmap API. /// /// # Invariants @@ -149,14 +147,14 @@ macro_rules! bitmap_assert_return { /// /// # Invariants /// -/// * `nbits` is `<= i32::MAX` and never changes. -/// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a `usize`. +/// * `nbits` is `<= MAX_LEN`. +/// * if `nbits <= MAX_INLINE_LEN`, then `repr` is a `usize`. /// * otherwise, `repr` holds a non-null pointer to an initialized /// array of `unsigned long` that is large enough to hold `nbits` bits. pub struct BitmapVec { /// Representation of bitmap. repr: BitmapRepr, - /// Length of this bitmap. Must be `<= i32::MAX`. + /// Length of this bitmap. Must be `<= MAX_LEN`. nbits: usize, } @@ -164,7 +162,7 @@ impl core::ops::Deref for BitmapVec { type Target = Bitmap; fn deref(&self) -> &Bitmap { - let ptr = if self.nbits <= BITS_PER_LONG { + let ptr = if self.nbits <= BitmapVec::MAX_INLINE_LEN { // SAFETY: Bitmap is represented inline. #[allow(unused_unsafe, reason = "Safe since Rust 1.92.0")] unsafe { @@ -183,7 +181,7 @@ impl core::ops::Deref for BitmapVec { impl core::ops::DerefMut for BitmapVec { fn deref_mut(&mut self) -> &mut Bitmap { - let ptr = if self.nbits <= BITS_PER_LONG { + let ptr = if self.nbits <= BitmapVec::MAX_INLINE_LEN { // SAFETY: Bitmap is represented inline. #[allow(unused_unsafe, reason = "Safe since Rust 1.92.0")] unsafe { @@ -213,7 +211,7 @@ unsafe impl Sync for BitmapVec {} impl Drop for BitmapVec { fn drop(&mut self) { - if self.nbits <= BITS_PER_LONG { + if self.nbits <= BitmapVec::MAX_INLINE_LEN { return; } // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`. @@ -226,23 +224,29 @@ impl Drop for BitmapVec { } impl BitmapVec { + /// The maximum possible length of a `BitmapVec`. + pub const MAX_LEN: usize = i32::MAX as usize; + + /// The maximum length that uses the inline representation. + pub const MAX_INLINE_LEN: usize = usize::BITS as usize; + /// Constructs a new [`BitmapVec`]. /// /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. This - /// includes the case when `nbits` is greater than `i32::MAX`. + /// includes the case when `nbits` is greater than `MAX_LEN`. #[inline] pub fn new(nbits: usize, flags: Flags) -> Result { - if nbits <= BITS_PER_LONG { + if nbits <= BitmapVec::MAX_INLINE_LEN { return Ok(BitmapVec { repr: BitmapRepr { bitmap: 0 }, nbits, }); } - if nbits > i32::MAX.try_into().unwrap() { + if nbits > Self::MAX_LEN { return Err(AllocError); } let nbits_u32 = u32::try_from(nbits).unwrap(); - // SAFETY: `BITS_PER_LONG < nbits` and `nbits <= i32::MAX`. + // SAFETY: `MAX_INLINE_LEN < nbits` and `nbits <= MAX_LEN`. let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) }; let ptr = NonNull::new(ptr).ok_or(AllocError)?; // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked. @@ -495,9 +499,10 @@ mod tests { #[test] fn bitmap_borrow() { let fake_bitmap: [usize; 2] = [0, 0]; + let fake_bitmap_len = 2 * usize::BITS as usize; // SAFETY: `fake_c_bitmap` is an array of expected length. - let b = unsafe { Bitmap::from_raw(fake_bitmap.as_ptr(), 2 * BITS_PER_LONG) }; - assert_eq!(2 * BITS_PER_LONG, b.len()); + let b = unsafe { Bitmap::from_raw(fake_bitmap.as_ptr(), fake_bitmap_len) }; + assert_eq!(fake_bitmap_len, b.len()); assert_eq!(None, b.next_bit(0)); } diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index a41a3404213c..0b1f720a1f7d 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -7,8 +7,6 @@ use crate::alloc::{AllocError, Flags}; use crate::bitmap::BitmapVec; -const BITS_PER_LONG: usize = bindings::BITS_PER_LONG as usize; - /// Represents a dynamic ID pool backed by a [`BitmapVec`]. /// /// Clients acquire and release IDs from unset bits in a bitmap. @@ -97,13 +95,12 @@ impl ReallocRequest { impl IdPool { /// Constructs a new [`IdPool`]. /// - /// A capacity below [`BITS_PER_LONG`] is adjusted to - /// [`BITS_PER_LONG`]. + /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LEN`]. /// - /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h + /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN #[inline] pub fn new(num_ids: usize, flags: Flags) -> Result { - let num_ids = core::cmp::max(num_ids, BITS_PER_LONG); + let num_ids = usize::max(num_ids, BitmapVec::MAX_INLINE_LEN); let map = BitmapVec::new(num_ids, flags)?; Ok(Self { map }) } @@ -116,28 +113,34 @@ impl IdPool { /// Returns a [`ReallocRequest`] if the [`IdPool`] can be shrunk, [`None`] otherwise. /// - /// The capacity of an [`IdPool`] cannot be shrunk below [`BITS_PER_LONG`]. + /// The capacity of an [`IdPool`] cannot be shrunk below [`MAX_INLINE_LEN`]. /// - /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h + /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN /// /// # Examples /// /// ``` - /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; - /// use kernel::id_pool::{ReallocRequest, IdPool}; + /// use kernel::{ + /// alloc::AllocError, + /// bitmap::BitmapVec, + /// id_pool::{ + /// IdPool, + /// ReallocRequest, + /// }, + /// }; /// /// let mut pool = IdPool::new(1024, GFP_KERNEL)?; /// let alloc_request = pool.shrink_request().ok_or(AllocError)?; /// let resizer = alloc_request.realloc(GFP_KERNEL)?; /// pool.shrink(resizer); - /// assert_eq!(pool.capacity(), kernel::bindings::BITS_PER_LONG as usize); + /// assert_eq!(pool.capacity(), BitmapVec::MAX_INLINE_LEN); /// # Ok::<(), AllocError>(()) /// ``` #[inline] pub fn shrink_request(&self) -> Option { let cap = self.capacity(); - // Shrinking below [`BITS_PER_LONG`] is never possible. - if cap <= BITS_PER_LONG { + // Shrinking below `MAX_INLINE_LEN` is never possible. + if cap <= BitmapVec::MAX_INLINE_LEN { return None; } // Determine if the bitmap can shrink based on the position of @@ -146,13 +149,13 @@ impl IdPool { // bitmap should shrink to half its current size. let Some(bit) = self.map.last_bit() else { return Some(ReallocRequest { - num_ids: BITS_PER_LONG, + num_ids: BitmapVec::MAX_INLINE_LEN, }); }; if bit >= (cap / 4) { return None; } - let num_ids = usize::max(BITS_PER_LONG, cap / 2); + let num_ids = usize::max(BitmapVec::MAX_INLINE_LEN, cap / 2); Some(ReallocRequest { num_ids }) } @@ -177,11 +180,13 @@ impl IdPool { /// Returns a [`ReallocRequest`] for growing this [`IdPool`], if possible. /// - /// The capacity of an [`IdPool`] cannot be grown above [`i32::MAX`]. + /// The capacity of an [`IdPool`] cannot be grown above [`MAX_LEN`]. + /// + /// [`MAX_LEN`]: BitmapVec::MAX_LEN #[inline] pub fn grow_request(&self) -> Option { let num_ids = self.capacity() * 2; - if num_ids > i32::MAX.try_into().unwrap() { + if num_ids > BitmapVec::MAX_LEN { return None; } Some(ReallocRequest { num_ids }) -- cgit From d0cf6512bbcf77afb6102f886fcd7fd48b7ae043 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 25 Nov 2025 13:59:38 +0000 Subject: rust: bitmap: add BitmapVec::new_inline() This constructor is useful when you just want to create a BitmapVec without allocating but don't care how large it is. Acked-by: Yury Norov (NVIDIA) Reviewed-by: Burak Emir Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl Signed-off-by: Yury Norov (NVIDIA) --- rust/kernel/bitmap.rs | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'rust/kernel') diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index 0705646c6251..83d7dea99137 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -230,6 +230,16 @@ impl BitmapVec { /// The maximum length that uses the inline representation. pub const MAX_INLINE_LEN: usize = usize::BITS as usize; + /// Construct a longest possible inline [`BitmapVec`]. + #[inline] + pub fn new_inline() -> Self { + // INVARIANT: `nbits <= MAX_INLINE_LEN`, so an inline bitmap is the right repr. + BitmapVec { + repr: BitmapRepr { bitmap: 0 }, + nbits: BitmapVec::MAX_INLINE_LEN, + } + } + /// Constructs a new [`BitmapVec`]. /// /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. This -- cgit From 6297fb3863d81b0970fd435476b837739c0ea4e7 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 25 Nov 2025 13:59:39 +0000 Subject: rust: id_pool: rename IdPool::new() to with_capacity() We want to change ::new() to take no parameters and produce a pool that is as large as possible while also being inline because that is the constructor that Rust Binder actually needs. However, to avoid complications in examples, we still need the current constructor. So rename it to with_capacity(), which is the idiomatic Rust name for this kind constructor. Reviewed-by: Burak Emir Signed-off-by: Alice Ryhl Signed-off-by: Yury Norov (NVIDIA) --- rust/kernel/id_pool.rs | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'rust/kernel') diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index 0b1f720a1f7d..7968b6c5566b 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -26,7 +26,7 @@ use crate::bitmap::BitmapVec; /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; /// use kernel::id_pool::IdPool; /// -/// let mut pool = IdPool::new(64, GFP_KERNEL)?; +/// let mut pool = IdPool::with_capacity(64, GFP_KERNEL)?; /// for i in 0..64 { /// assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?); /// } @@ -93,13 +93,13 @@ impl ReallocRequest { } impl IdPool { - /// Constructs a new [`IdPool`]. + /// Constructs a new [`IdPool`] with space for a specific number of bits. /// /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LEN`]. /// /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN #[inline] - pub fn new(num_ids: usize, flags: Flags) -> Result { + pub fn with_capacity(num_ids: usize, flags: Flags) -> Result { let num_ids = usize::max(num_ids, BitmapVec::MAX_INLINE_LEN); let map = BitmapVec::new(num_ids, flags)?; Ok(Self { map }) @@ -129,7 +129,7 @@ impl IdPool { /// }, /// }; /// - /// let mut pool = IdPool::new(1024, GFP_KERNEL)?; + /// let mut pool = IdPool::with_capacity(1024, GFP_KERNEL)?; /// let alloc_request = pool.shrink_request().ok_or(AllocError)?; /// let resizer = alloc_request.realloc(GFP_KERNEL)?; /// pool.shrink(resizer); -- cgit From 69ec6a1bed3017293a3430e2f8e3c01b29496446 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 25 Nov 2025 13:59:40 +0000 Subject: rust: id_pool: do not supply starting capacity Rust Binder wants to use inline bitmaps whenever possible to avoid allocations, so introduce a constructor for an IdPool with arbitrary capacity that stores the bitmap inline. The existing constructor could be renamed to with_capacity() to match constructors for other similar types, but it is removed as there is currently no user for it. [Miguel: rust: id_pool: fix broken intra-doc link] Acked-by: Yury Norov (NVIDIA) Reviewed-by: Burak Emir Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl Signed-off-by: Yury Norov (NVIDIA) --- rust/kernel/id_pool.rs | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'rust/kernel') diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index 7968b6c5566b..afde05f53588 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -93,6 +93,18 @@ impl ReallocRequest { } impl IdPool { + /// Constructs a new [`IdPool`]. + /// + /// The pool will have a capacity of [`MAX_INLINE_LEN`]. + /// + /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN + #[inline] + pub fn new() -> Self { + Self { + map: BitmapVec::new_inline(), + } + } + /// Constructs a new [`IdPool`] with space for a specific number of bits. /// /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LEN`]. @@ -229,3 +241,10 @@ impl IdPool { self.map.clear_bit(id); } } + +impl Default for IdPool { + #[inline] + fn default() -> Self { + Self::new() + } +} -- cgit From f523d110a63b5b38ab5d54df1d06f1e0988c9b74 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 25 Nov 2025 13:59:41 +0000 Subject: rust: id_pool: do not immediately acquire new ids 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. [Miguel: rust: id_pool: fix example] Reviewed-by: Burak Emir Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl Signed-off-by: Yury Norov (NVIDIA) --- rust/kernel/id_pool.rs | 77 +++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 61 insertions(+), 16 deletions(-) (limited to 'rust/kernel') diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index afde05f53588..384753fe0e44 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -23,22 +23,22 @@ use crate::bitmap::BitmapVec; /// Basic usage /// /// ``` -/// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; -/// use kernel::id_pool::IdPool; +/// use kernel::alloc::AllocError; +/// use kernel::id_pool::{IdPool, UnusedId}; /// /// let mut pool = IdPool::with_capacity(64, GFP_KERNEL)?; /// for i in 0..64 { -/// assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?); +/// assert_eq!(i, pool.find_unused_id(i).ok_or(ENOSPC)?.acquire()); /// } /// /// pool.release_id(23); -/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?); +/// assert_eq!(23, pool.find_unused_id(0).ok_or(ENOSPC)?.acquire()); /// -/// assert_eq!(None, pool.acquire_next_id(0)); // time to realloc. +/// assert!(pool.find_unused_id(0).is_none()); // 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)); +/// assert_eq!(pool.find_unused_id(0).ok_or(ENOSPC)?.acquire(), 64); /// # Ok::<(), Error>(()) /// ``` /// @@ -52,8 +52,8 @@ use crate::bitmap::BitmapVec; /// fn get_id_maybe_realloc(guarded_pool: &SpinLock) -> Result { /// let mut pool = guarded_pool.lock(); /// loop { -/// match pool.acquire_next_id(0) { -/// Some(index) => return Ok(index), +/// match pool.find_unused_id(0) { +/// Some(index) => return Ok(index.acquire()), /// None => { /// let alloc_request = pool.grow_request(); /// drop(pool); @@ -221,18 +221,18 @@ impl IdPool { self.map = resizer.new; } - /// Acquires a new ID by finding and setting the next zero bit in the - /// bitmap. + /// Finds an unused ID in the bitmap. /// /// Upon success, returns its index. Otherwise, returns [`None`] /// to indicate that a [`Self::grow_request`] is needed. #[inline] - pub fn acquire_next_id(&mut self, offset: usize) -> Option { - let next_zero_bit = self.map.next_zero_bit(offset); - if let Some(nr) = next_zero_bit { - self.map.set_bit(nr); - } - next_zero_bit + #[must_use] + pub fn find_unused_id(&mut self, offset: usize) -> Option> { + // INVARIANT: `next_zero_bit()` returns None or an integer less than `map.len()` + Some(UnusedId { + id: self.map.next_zero_bit(offset)?, + pool: self, + }) } /// Releases an ID. @@ -242,6 +242,51 @@ impl IdPool { } } +/// Represents an unused id in an [`IdPool`]. +/// +/// # Invariants +/// +/// The value of `id` is less than `pool.map.len()`. +pub struct UnusedId<'pool> { + id: usize, + pool: &'pool mut IdPool, +} + +impl<'pool> UnusedId<'pool> { + /// Get the unused id as an usize. + /// + /// Be aware that the id has not yet been acquired in the pool. The + /// [`acquire`] method must be called to prevent others from taking the id. + /// + /// [`acquire`]: UnusedId::acquire() + #[inline] + #[must_use] + pub fn as_usize(&self) -> usize { + self.id + } + + /// Get the unused id as an u32. + /// + /// Be aware that the id has not yet been acquired in the pool. The + /// [`acquire`] method must be called to prevent others from taking the id. + /// + /// [`acquire`]: UnusedId::acquire() + #[inline] + #[must_use] + pub fn as_u32(&self) -> u32 { + // CAST: By the type invariants: + // `self.id < pool.map.len() <= BitmapVec::MAX_LEN = i32::MAX`. + self.id as u32 + } + + /// Acquire the unused id. + #[inline] + pub fn acquire(self) -> usize { + self.pool.map.set_bit(self.id); + self.id + } +} + impl Default for IdPool { #[inline] fn default() -> Self { -- cgit