From 9def0d0a2a1c62d7970f4ce5ad5557968c98f637 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:31 +0000 Subject: rust: alloc: add Vec::push_within_capacity This introduces a new method called `push_within_capacity` for appending to a vector without attempting to allocate if the capacity is full. Rust Binder will use this in various places to safely push to a vector while holding a spinlock. The implementation is moved to a push_within_capacity_unchecked method. This is preferred over having push() call push_within_capacity() followed by an unwrap_unchecked() for simpler unsafe. Panics in the kernel are best avoided when possible, so an error is returned if the vector does not have sufficient capacity. An error type is used rather than just returning Result<(),T> to make it more convenient for callers (i.e. they can use ? or unwrap). Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250502-vec-methods-v5-3-06d20ad9366f@google.com [ Remove public visibility from `Vec::push_within_capacity_unchecked()`. - Danilo ] Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec/errors.rs | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) create mode 100644 rust/kernel/alloc/kvec/errors.rs (limited to 'rust/kernel/alloc/kvec/errors.rs') diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs new file mode 100644 index 000000000000..84c96ec5007d --- /dev/null +++ b/rust/kernel/alloc/kvec/errors.rs @@ -0,0 +1,23 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Errors for the [`Vec`] type. + +use core::fmt::{self, Debug, Formatter}; +use kernel::prelude::*; + +/// Error type for [`Vec::push_within_capacity`]. +pub struct PushError(pub T); + +impl Debug for PushError { + fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { + write!(f, "Not enough capacity") + } +} + +impl From> for Error { + fn from(_: PushError) -> Error { + // Returning ENOMEM isn't appropriate because the system is not out of memory. The vector + // is just full and we are refusing to resize it. + EINVAL + } +} -- cgit v1.2.3 From 294a7ecbdf0a5d65c6df1287c5d56241e9331cf2 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:34 +0000 Subject: rust: alloc: add Vec::remove This is needed by Rust Binder in the range allocator, and by upcoming GPU drivers during firmware initialization. Panics in the kernel are best avoided when possible, so an error is returned if the index is out of bounds. An error type is used rather than just returning Option to let callers handle errors with ?. Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250502-vec-methods-v5-6-06d20ad9366f@google.com [ Remove `# Panics` section; `Vec::remove() handles the error properly.` - Danilo ] Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 38 +++++++++++++++++++++++++++++++++++++- rust/kernel/alloc/kvec/errors.rs | 15 +++++++++++++++ 2 files changed, 52 insertions(+), 1 deletion(-) (limited to 'rust/kernel/alloc/kvec/errors.rs') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 8843dea0b377..3f2617b08753 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -22,7 +22,7 @@ use core::{ }; mod errors; -pub use self::errors::PushError; +pub use self::errors::{PushError, RemoveError}; /// Create a [`KVec`] containing the arguments. /// @@ -389,6 +389,42 @@ where Some(unsafe { removed.read() }) } + /// Removes the element at the given index. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![1, 2, 3]?; + /// assert_eq!(v.remove(1)?, 2); + /// assert_eq!(v, [1, 3]); + /// # Ok::<(), Error>(()) + /// ``` + pub fn remove(&mut self, i: usize) -> Result { + let value = { + let value_ref = self.get(i).ok_or(RemoveError)?; + // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we + // restore the invariants below. + // SAFETY: The value at index `i` is valid, because otherwise we would have already + // failed with `RemoveError`. + unsafe { ptr::read(value_ref) } + }; + + // SAFETY: We checked that `i` is in-bounds. + let p = unsafe { self.as_mut_ptr().add(i) }; + + // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants + // are restored after the below call to `dec_len(1)`. + // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the + // beginning of the vector, so this is in-bounds of the vector's allocation. + unsafe { ptr::copy(p.add(1), p, self.len - i - 1) }; + + // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`, + // the length is at least one. + unsafe { self.dec_len(1) }; + + Ok(value) + } + /// Creates a new [`Vec`] instance with at least the given capacity. /// /// # Examples diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs index 84c96ec5007d..06fe696e8bc6 100644 --- a/rust/kernel/alloc/kvec/errors.rs +++ b/rust/kernel/alloc/kvec/errors.rs @@ -21,3 +21,18 @@ impl From> for Error { EINVAL } } + +/// Error type for [`Vec::remove`]. +pub struct RemoveError; + +impl Debug for RemoveError { + fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { + write!(f, "Index out of bounds") + } +} + +impl From for Error { + fn from(_: RemoveError) -> Error { + EINVAL + } +} -- cgit v1.2.3 From 771c5a7d9843643b035938624050e7769133b9cc Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:35 +0000 Subject: rust: alloc: add Vec::insert_within_capacity This adds a variant of Vec::insert that does not allocate memory. This makes it safe to use this function while holding a spinlock. Rust Binder uses it for the range allocator fast path. Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250502-vec-methods-v5-7-06d20ad9366f@google.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 51 +++++++++++++++++++++++++++++++++++++++- rust/kernel/alloc/kvec/errors.rs | 23 ++++++++++++++++++ 2 files changed, 73 insertions(+), 1 deletion(-) (limited to 'rust/kernel/alloc/kvec/errors.rs') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 3f2617b08753..1a0dd852a468 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -22,7 +22,7 @@ use core::{ }; mod errors; -pub use self::errors::{PushError, RemoveError}; +pub use self::errors::{InsertError, PushError, RemoveError}; /// Create a [`KVec`] containing the arguments. /// @@ -358,6 +358,55 @@ where unsafe { self.inc_len(1) }; } + /// Inserts an element at the given index in the [`Vec`] instance. + /// + /// Fails if the vector does not have capacity for the new element. Panics if the index is out + /// of bounds. + /// + /// # Examples + /// + /// ``` + /// use kernel::alloc::kvec::InsertError; + /// + /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?; + /// for i in 0..5 { + /// v.insert_within_capacity(0, i)?; + /// } + /// + /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_)))); + /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_)))); + /// assert_eq!(v, [4, 3, 2, 1, 0]); + /// # Ok::<(), Error>(()) + /// ``` + pub fn insert_within_capacity( + &mut self, + index: usize, + element: T, + ) -> Result<(), InsertError> { + let len = self.len(); + if index > len { + return Err(InsertError::IndexOutOfBounds(element)); + } + + if len >= self.capacity() { + return Err(InsertError::OutOfCapacity(element)); + } + + // SAFETY: This is in bounds since `index <= len < capacity`. + let p = unsafe { self.as_mut_ptr().add(index) }; + // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element, + // but we restore the invariants below. + // SAFETY: Both the src and dst ranges end no later than one element after the length. + // Since the length is less than the capacity, both ranges are in bounds of the allocation. + unsafe { ptr::copy(p, p.add(1), len - index) }; + // INVARIANT: This restores the Vec invariants. + // SAFETY: The pointer is in-bounds of the allocation. + unsafe { ptr::write(p, element) }; + // SAFETY: Index `len` contains a valid element due to the above copy and write. + unsafe { self.inc_len(1) }; + Ok(()) + } + /// Removes the last element from a vector and returns it, or `None` if it is empty. /// /// # Examples diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs index 06fe696e8bc6..348b8d27e102 100644 --- a/rust/kernel/alloc/kvec/errors.rs +++ b/rust/kernel/alloc/kvec/errors.rs @@ -36,3 +36,26 @@ impl From for Error { EINVAL } } + +/// Error type for [`Vec::insert_within_capacity`]. +pub enum InsertError { + /// The value could not be inserted because the index is out of bounds. + IndexOutOfBounds(T), + /// The value could not be inserted because the vector is out of capacity. + OutOfCapacity(T), +} + +impl Debug for InsertError { + fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { + match self { + InsertError::IndexOutOfBounds(_) => write!(f, "Index out of bounds"), + InsertError::OutOfCapacity(_) => write!(f, "Not enough capacity"), + } + } +} + +impl From> for Error { + fn from(_: InsertError) -> Error { + EINVAL + } +} -- cgit v1.2.3