summaryrefslogtreecommitdiff
path: root/rust/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'rust/kernel')
-rw-r--r--rust/kernel/bitmap.rs43
-rw-r--r--rust/kernel/id_pool.rs141
-rw-r--r--rust/kernel/lib.rs2
-rw-r--r--rust/kernel/list.rs3
4 files changed, 139 insertions, 50 deletions
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index aa8fc7bf06fc..83d7dea99137 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,39 @@ 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;
+
+ /// 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
- /// 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<Self, AllocError> {
- 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 +509,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..384753fe0e44 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.
@@ -25,22 +23,22 @@ const BITS_PER_LONG: usize = bindings::BITS_PER_LONG as usize;
/// 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::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)?);
+/// 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>(())
/// ```
///
@@ -54,8 +52,8 @@ const BITS_PER_LONG: usize = bindings::BITS_PER_LONG as usize;
/// 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),
+/// match pool.find_unused_id(0) {
+/// Some(index) => return Ok(index.acquire()),
/// None => {
/// let alloc_request = pool.grow_request();
/// drop(pool);
@@ -97,13 +95,24 @@ impl ReallocRequest {
impl IdPool {
/// Constructs a new [`IdPool`].
///
- /// A capacity below [`BITS_PER_LONG`] is adjusted to
- /// [`BITS_PER_LONG`].
+ /// 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`].
///
- /// [`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<Self, AllocError> {
- let num_ids = core::cmp::max(num_ids, BITS_PER_LONG);
+ pub fn with_capacity(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
+ let num_ids = usize::max(num_ids, BitmapVec::MAX_INLINE_LEN);
let map = BitmapVec::new(num_ids, flags)?;
Ok(Self { map })
}
@@ -116,28 +125,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 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);
- /// 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<ReallocRequest> {
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 +161,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 +192,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<ReallocRequest> {
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 })
@@ -204,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<usize> {
- 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<UnusedId<'_>> {
+ // 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.
@@ -224,3 +241,55 @@ impl IdPool {
self.map.clear_bit(id);
}
}
+
+/// 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 {
+ Self::new()
+ }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index 6083dec1f190..f812cf120042 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -149,6 +149,8 @@ pub mod tracepoint;
pub mod transmute;
pub mod types;
pub mod uaccess;
+#[cfg(CONFIG_USB = "y")]
+pub mod usb;
pub mod workqueue;
pub mod xarray;
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 7355bbac16a7..8349ff32fc37 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -576,6 +576,9 @@ impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
/// This returns `None` if the item is not in the list. (Note that by the safety requirements,
/// this means that the item is not in any list.)
///
+ /// When using this method, be careful with using `mem::take` on the same list as that may
+ /// result in violating the safety requirements of this method.
+ ///
/// # Safety
///
/// `item` must not be in a different linked list (with the same id).
generated by cgit (git 2.34.1) at 2025-12-07 15:41:48 +0000