From fb1bf1067de979c89ae33589e0466d6ce0dde204 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Sat, 15 Mar 2025 16:43:02 +0100 Subject: rust: alloc: add missing invariant in Vec::set_len() When setting a new length, we have to justify that the set length represents the exact number of elements stored in the vector. Reviewed-by: Benno Lossin Reported-by: Alice Ryhl Closes: https://lore.kernel.org/rust-for-linux/20250311-iov-iter-v1-4-f6c9134ea824@google.com Fixes: 2aac4cd7dae3 ("rust: alloc: implement kernel `Vec` type") Link: https://lore.kernel.org/r/20250315154436.65065-2-dakr@kernel.org Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 3 +++ 1 file changed, 3 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index ae9d072741ce..b01dabfe35aa 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -193,6 +193,9 @@ where #[inline] pub unsafe fn set_len(&mut self, new_len: usize) { debug_assert!(new_len <= self.capacity()); + + // INVARIANT: By the safety requirements of this method `new_len` represents the exact + // number of elements stored within `self`. self.len = new_len; } -- cgit v1.2.3 From 81e1c4dab5d0c508907722f18b028102454d52e6 Mon Sep 17 00:00:00 2001 From: Andrew Ballance Date: Sun, 16 Mar 2025 06:16:42 -0500 Subject: rust: alloc: add Vec::truncate method Implement the equivalent to the std's Vec::truncate on the kernel's Vec type. Link: https://lore.kernel.org/r/20250316111644.154602-2-andrewjballance@gmail.com Signed-off-by: Andrew Ballance [ Rewrote safety comment of set_len(). - Danilo ] Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index b01dabfe35aa..8fd941429d7c 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -455,6 +455,41 @@ where Ok(()) } + + /// Shortens the vector, setting the length to `len` and drops the removed values. + /// If `len` is greater than or equal to the current length, this does nothing. + /// + /// This has no effect on the capacity and will not allocate. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![1, 2, 3]?; + /// v.truncate(1); + /// assert_eq!(v.len(), 1); + /// assert_eq!(&v, &[1]); + /// + /// # Ok::<(), Error>(()) + /// ``` + pub fn truncate(&mut self, len: usize) { + if len >= self.len() { + return; + } + + let drop_range = len..self.len(); + + // SAFETY: `drop_range` is a subrange of `[0, len)` by the bounds check above. + let ptr: *mut [T] = unsafe { self.get_unchecked_mut(drop_range) }; + + // SAFETY: By the above bounds check, it is guaranteed that `len < self.capacity()`. + unsafe { self.set_len(len) }; + + // SAFETY: + // - the dropped values are valid `T`s by the type invariant + // - we are allowed to invalidate [`new_len`, `old_len`) because we just changed the + // len, therefore we have exclusive access to [`new_len`, `old_len`) + unsafe { ptr::drop_in_place(ptr) }; + } } impl Vec { -- cgit v1.2.3 From 1679b7159379d11100e4ab7d1de23c8cd7765aa1 Mon Sep 17 00:00:00 2001 From: Andrew Ballance Date: Sun, 16 Mar 2025 06:16:43 -0500 Subject: rust: alloc: add Vec::resize method Implement the equivalent of the rust std's Vec::resize on the kernel's Vec type. Reviewed-by: Benno Lossin Reviewed-by: Tamir Duberstein Link: https://lore.kernel.org/r/20250316111644.154602-3-andrewjballance@gmail.com Signed-off-by: Andrew Ballance [ Use checked_sub(), as suggested by Tamir. - Danilo ] Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 8fd941429d7c..7ebec5c4a277 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -556,6 +556,33 @@ impl Vec { Ok(v) } + + /// Resizes the [`Vec`] so that `len` is equal to `new_len`. + /// + /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d. + /// If `new_len` is larger, each new slot is filled with clones of `value`. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![1, 2, 3]?; + /// v.resize(1, 42, GFP_KERNEL)?; + /// assert_eq!(&v, &[1]); + /// + /// v.resize(3, 42, GFP_KERNEL)?; + /// assert_eq!(&v, &[1, 42, 42]); + /// + /// # Ok::<(), Error>(()) + /// ``` + pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> { + match new_len.checked_sub(self.len()) { + Some(n) => self.extend_with(n, value, flags), + None => { + self.truncate(new_len); + Ok(()) + } + } + } } impl Drop for Vec -- cgit v1.2.3 From c3152988c047a7b6abb10d4dc5e24fafbabe8b7e Mon Sep 17 00:00:00 2001 From: Tamir Duberstein Date: Tue, 18 Mar 2025 10:52:42 -0400 Subject: rust: alloc: use `spare_capacity_mut` to reduce unsafe Use `spare_capacity_mut` in the implementation of `push` to reduce the use of `unsafe`. Both methods were added in commit 2aac4cd7dae3 ("rust: alloc: implement kernel `Vec` type"). Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250318-vec-push-use-spare-v3-1-68741671d1af@gmail.com Signed-off-by: Tamir Duberstein Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 7ebec5c4a277..6ac8756989e5 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -288,15 +288,10 @@ where pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> { self.reserve(1, flags)?; - // SAFETY: - // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is - // guaranteed to be part of the same allocated object. - // - `self.len` can not overflow `isize`. - let ptr = unsafe { self.as_mut_ptr().add(self.len) }; + let spare = self.spare_capacity_mut(); - // SAFETY: - // - `ptr` is properly aligned and valid for writes. - unsafe { core::ptr::write(ptr, v) }; + // SAFETY: The call to `reserve` was successful so the spare capacity is at least 1. + unsafe { spare.get_unchecked_mut(0) }.write(v); // SAFETY: We just initialised the first spare entry, so it is safe to increase the length // by 1. We also know that the new length is <= capacity because of the previous call to -- cgit v1.2.3 From 85f8e98dbb0135d2bc1999c6015cd374fe2c69fa Mon Sep 17 00:00:00 2001 From: Alexandre Courbot Date: Sat, 12 Apr 2025 15:29:13 +0900 Subject: rust: alloc: allow coercion from `Box` to `Box` if T implements U This enables the creation of trait objects backed by a Box, similarly to what can be done with the standard library. Suggested-by: Benno Lossin Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Signed-off-by: Alexandre Courbot Link: https://lore.kernel.org/r/20250412-box_trait_objs-v3-1-f67ced62d520@nvidia.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kbox.rs | 40 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs index b77d32f3a58b..e043bf2f4687 100644 --- a/rust/kernel/alloc/kbox.rs +++ b/rust/kernel/alloc/kbox.rs @@ -57,12 +57,50 @@ use pin_init::{InPlaceWrite, Init, PinInit, ZeroableOption}; /// assert!(KVBox::::new_uninit(GFP_KERNEL).is_ok()); /// ``` /// +/// [`Box`]es can also be used to store trait objects by coercing their type: +/// +/// ``` +/// trait FooTrait {} +/// +/// struct FooStruct; +/// impl FooTrait for FooStruct {} +/// +/// let _ = KBox::new(FooStruct, GFP_KERNEL)? as KBox; +/// # Ok::<(), Error>(()) +/// ``` +/// /// # Invariants /// /// `self.0` is always properly aligned and either points to memory allocated with `A` or, for /// zero-sized types, is a dangling, well aligned pointer. #[repr(transparent)] -pub struct Box(NonNull, PhantomData); +#[cfg_attr(CONFIG_RUSTC_HAS_COERCE_POINTEE, derive(core::marker::CoercePointee))] +pub struct Box<#[cfg_attr(CONFIG_RUSTC_HAS_COERCE_POINTEE, pointee)] T: ?Sized, A: Allocator>( + NonNull, + PhantomData, +); + +// This is to allow coercion from `Box` to `Box` if `T` can be converted to the +// dynamically-sized type (DST) `U`. +#[cfg(not(CONFIG_RUSTC_HAS_COERCE_POINTEE))] +impl core::ops::CoerceUnsized> for Box +where + T: ?Sized + core::marker::Unsize, + U: ?Sized, + A: Allocator, +{ +} + +// This is to allow `Box` to be dispatched on when `Box` can be coerced into `Box`. +#[cfg(not(CONFIG_RUSTC_HAS_COERCE_POINTEE))] +impl core::ops::DispatchFromDyn> for Box +where + T: ?Sized + core::marker::Unsize, + U: ?Sized, + A: Allocator, +{ +} /// Type alias for [`Box`] with a [`Kmalloc`] allocator. /// -- cgit v1.2.3 From 47a17a63f9e23f7e8f39d0965bcda8fee6c322f8 Mon Sep 17 00:00:00 2001 From: Tamir Duberstein Date: Wed, 16 Apr 2025 13:15:40 -0400 Subject: rust: alloc: add Vec::len() <= Vec::capacity invariant Document the invariant that the vector's length is always less than or equal to its capacity. This is already implied by these other invariants: - `self.len` always represents the exact number of elements stored in the vector. - `self.layout` represents the absolute number of elements that can be stored within the vector without re-allocation. but it doesn't hurt to spell it out. Note that the language references `self.capacity` rather than `self.layout.len` as the latter is zero for a vector of ZSTs. Update a safety comment touched by this patch to correctly reference `realloc` rather than `alloc` and replace "leaves" with "leave" to improve grammar. Reviewed-by: Alice Ryhl Signed-off-by: Tamir Duberstein Link: https://lore.kernel.org/r/20250416-vec-set-len-v4-1-112b222604cd@gmail.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 6ac8756989e5..ca30fad90de5 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -90,6 +90,8 @@ macro_rules! kvec { /// without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the /// backing buffer to be larger than `layout`. /// +/// - `self.len()` is always less than or equal to `self.capacity()`. +/// /// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer /// was allocated with (and must be freed with). pub struct Vec { @@ -262,8 +264,8 @@ where /// Returns a slice of `MaybeUninit` for the remaining spare capacity of the vector. pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit] { // SAFETY: - // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is - // guaranteed to be part of the same allocated object. + // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the + // resulting pointer is guaranteed to be part of the same allocated object. // - `self.len` can not overflow `isize`. let ptr = unsafe { self.as_mut_ptr().add(self.len) } as *mut MaybeUninit; @@ -817,12 +819,13 @@ where unsafe { ptr::copy(ptr, buf.as_ptr(), len) }; ptr = buf.as_ptr(); - // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()`. + // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type + // invariant. let layout = unsafe { ArrayLayout::::new_unchecked(len) }; - // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed to be - // smaller than `cap`. Depending on `alloc` this operation may shrink the buffer or leaves - // it as it is. + // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by + // the type invariant to be smaller than `cap`. Depending on `realloc` this operation + // may shrink the buffer or leave it as it is. ptr = match unsafe { A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags) } { -- cgit v1.2.3 From dbb0b840a0cd2ebabbc94a0040e366c7f1a70f7b Mon Sep 17 00:00:00 2001 From: Tamir Duberstein Date: Wed, 16 Apr 2025 13:15:41 -0400 Subject: rust: alloc: add `Vec::dec_len` Add `Vec::dec_len` that reduces the length of the receiver. This method is intended to be used from methods that remove elements from `Vec` such as `truncate`, `pop`, `remove`, and others. This method is intentionally not `pub`. Reviewed-by: Alice Ryhl Signed-off-by: Tamir Duberstein Link: https://lore.kernel.org/r/20250416-vec-set-len-v4-2-112b222604cd@gmail.com [ Add #[expect(unused)] to dec_len(). - Danilo ] Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index ca30fad90de5..7671867165a0 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -201,6 +201,26 @@ where self.len = new_len; } + /// Decreases `self.len` by `count`. + /// + /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's + /// responsibility to drop these elements if necessary. + /// + /// # Safety + /// + /// - `count` must be less than or equal to `self.len`. + #[expect(unused)] + unsafe fn dec_len(&mut self, count: usize) -> &mut [T] { + debug_assert!(count <= self.len()); + // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count, + // self.len)`, hence the updated value of `set.len` represents the exact number of elements + // stored within `self`. + self.len -= count; + // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized + // elements of type `T`. + unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) } + } + /// Returns a slice of the entire vector. #[inline] pub fn as_slice(&self) -> &[T] { -- cgit v1.2.3 From 1b04b466c873f62413bf65a05a558f036660aedc Mon Sep 17 00:00:00 2001 From: Tamir Duberstein Date: Wed, 16 Apr 2025 13:15:42 -0400 Subject: rust: alloc: refactor `Vec::truncate` using `dec_len` Use `checked_sub` to satisfy the safety requirements of `dec_len` and replace nearly the whole body of `truncate` with a call to `dec_len`. Reviewed-by: Andrew Ballance Reviewed-by: Alice Ryhl Signed-off-by: Tamir Duberstein Link: https://lore.kernel.org/r/20250416-vec-set-len-v4-3-112b222604cd@gmail.com [ Remove #[expect(unused)] from dec_len(). - Danilo ] Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 25 ++++++++----------------- 1 file changed, 8 insertions(+), 17 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 7671867165a0..87dc37ecb94d 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -209,7 +209,6 @@ where /// # Safety /// /// - `count` must be less than or equal to `self.len`. - #[expect(unused)] unsafe fn dec_len(&mut self, count: usize) -> &mut [T] { debug_assert!(count <= self.len()); // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count, @@ -489,23 +488,15 @@ where /// # Ok::<(), Error>(()) /// ``` pub fn truncate(&mut self, len: usize) { - if len >= self.len() { - return; + if let Some(count) = self.len().checked_sub(len) { + // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or + // equal to `self.len()`. + let ptr: *mut [T] = unsafe { self.dec_len(count) }; + + // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are + // valid elements whose ownership has been transferred to the caller. + unsafe { ptr::drop_in_place(ptr) }; } - - let drop_range = len..self.len(); - - // SAFETY: `drop_range` is a subrange of `[0, len)` by the bounds check above. - let ptr: *mut [T] = unsafe { self.get_unchecked_mut(drop_range) }; - - // SAFETY: By the above bounds check, it is guaranteed that `len < self.capacity()`. - unsafe { self.set_len(len) }; - - // SAFETY: - // - the dropped values are valid `T`s by the type invariant - // - we are allowed to invalidate [`new_len`, `old_len`) because we just changed the - // len, therefore we have exclusive access to [`new_len`, `old_len`) - unsafe { ptr::drop_in_place(ptr) }; } } -- cgit v1.2.3 From 88d5d6a38d5161228fbfe017eb94d777d5e8a0e4 Mon Sep 17 00:00:00 2001 From: Tamir Duberstein Date: Wed, 16 Apr 2025 13:15:43 -0400 Subject: rust: alloc: replace `Vec::set_len` with `inc_len` Rename `set_len` to `inc_len` and simplify its safety contract. Note that the usage in `CString::try_from_fmt` remains correct as the receiver is known to have `len == 0`. Reviewed-by: Alice Ryhl Signed-off-by: Tamir Duberstein Link: https://lore.kernel.org/r/20250416-vec-set-len-v4-4-112b222604cd@gmail.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 87dc37ecb94d..5798e2c890a2 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -185,20 +185,19 @@ where self.len } - /// Forcefully sets `self.len` to `new_len`. + /// Increments `self.len` by `additional`. /// /// # Safety /// - /// - `new_len` must be less than or equal to [`Self::capacity`]. - /// - If `new_len` is greater than `self.len`, all elements within the interval - /// [`self.len`,`new_len`) must be initialized. + /// - `additional` must be less than or equal to `self.capacity - self.len`. + /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized. #[inline] - pub unsafe fn set_len(&mut self, new_len: usize) { - debug_assert!(new_len <= self.capacity()); - - // INVARIANT: By the safety requirements of this method `new_len` represents the exact - // number of elements stored within `self`. - self.len = new_len; + pub unsafe fn inc_len(&mut self, additional: usize) { + // Guaranteed by the type invariant to never underflow. + debug_assert!(additional <= self.capacity() - self.len()); + // INVARIANT: By the safety requirements of this method this represents the exact number of + // elements stored within `self`. + self.len += additional; } /// Decreases `self.len` by `count`. @@ -317,7 +316,7 @@ where // SAFETY: We just initialised the first spare entry, so it is safe to increase the length // by 1. We also know that the new length is <= capacity because of the previous call to // `reserve` above. - unsafe { self.set_len(self.len() + 1) }; + unsafe { self.inc_len(1) }; Ok(()) } @@ -521,7 +520,7 @@ impl Vec { // SAFETY: // - `self.len() + n < self.capacity()` due to the call to reserve above, // - the loop and the line above initialized the next `n` elements. - unsafe { self.set_len(self.len() + n) }; + unsafe { self.inc_len(n) }; Ok(()) } @@ -552,7 +551,7 @@ impl Vec { // the length by the same number. // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve` // call. - unsafe { self.set_len(self.len() + other.len()) }; + unsafe { self.inc_len(other.len()) }; Ok(()) } -- cgit v1.2.3 From a1e4d5c9d708d7a0e7071015a120a4489404128f Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:29 +0000 Subject: rust: alloc: add Vec::clear Our custom Vec type is missing the stdlib method `clear`, thus add it. It will be used in the miscdevice sample. Reviewed-by: Benno Lossin Reviewed-by: Tamir Duberstein Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Link: https://lore.kernel.org/r/20250502-vec-methods-v5-1-06d20ad9366f@google.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 5798e2c890a2..412a2fe3ce79 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -413,6 +413,26 @@ where (ptr, len, capacity) } + /// Clears the vector, removing all values. + /// + /// Note that this method has no effect on the allocated capacity + /// of the vector. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![1, 2, 3]?; + /// + /// v.clear(); + /// + /// assert!(v.is_empty()); + /// # Ok::<(), Error>(()) + /// ``` + #[inline] + pub fn clear(&mut self) { + self.truncate(0); + } + /// Ensures that the capacity exceeds the length by at least `additional` elements. /// /// # Examples -- cgit v1.2.3 From f2b4dd7093438e4884cb01a783212abfbc9cc40b Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:30 +0000 Subject: rust: alloc: add Vec::pop This introduces a basic method that our custom Vec is missing. I expect that it will be used in many places, but at the time of writing, Rust Binder has six calls to Vec::pop. Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250502-vec-methods-v5-2-06d20ad9366f@google.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 412a2fe3ce79..ebca0cfd31c6 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -320,6 +320,37 @@ where Ok(()) } + /// Removes the last element from a vector and returns it, or `None` if it is empty. + /// + /// # Examples + /// + /// ``` + /// let mut v = KVec::new(); + /// v.push(1, GFP_KERNEL)?; + /// v.push(2, GFP_KERNEL)?; + /// assert_eq!(&v, &[1, 2]); + /// + /// assert_eq!(v.pop(), Some(2)); + /// assert_eq!(v.pop(), Some(1)); + /// assert_eq!(v.pop(), None); + /// # Ok::<(), Error>(()) + /// ``` + pub fn pop(&mut self) -> Option { + if self.is_empty() { + return None; + } + + let removed: *mut T = { + // SAFETY: We just checked that the length is at least one. + let slice = unsafe { self.dec_len(1) }; + // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1. + unsafe { slice.get_unchecked_mut(0) } + }; + + // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value. + Some(unsafe { removed.read() }) + } + /// Creates a new [`Vec`] instance with at least the given capacity. /// /// # Examples -- cgit v1.2.3 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.rs | 46 ++++++++++++++++++++++++++++++++++++---- rust/kernel/alloc/kvec/errors.rs | 23 ++++++++++++++++++++ 2 files changed, 65 insertions(+), 4 deletions(-) create mode 100644 rust/kernel/alloc/kvec/errors.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index ebca0cfd31c6..64dfa9af5589 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -21,6 +21,9 @@ use core::{ slice::SliceIndex, }; +mod errors; +pub use self::errors::PushError; + /// Create a [`KVec`] containing the arguments. /// /// New memory is allocated with `GFP_KERNEL`. @@ -307,17 +310,52 @@ where /// ``` pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> { self.reserve(1, flags)?; + // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater + // than the length. + unsafe { self.push_within_capacity_unchecked(v) }; + Ok(()) + } + /// Appends an element to the back of the [`Vec`] instance without reallocating. + /// + /// Fails if the vector does not have capacity for the new element. + /// + /// # Examples + /// + /// ``` + /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?; + /// for i in 0..10 { + /// v.push_within_capacity(i)?; + /// } + /// + /// assert!(v.push_within_capacity(10).is_err()); + /// # Ok::<(), Error>(()) + /// ``` + pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError> { + if self.len() < self.capacity() { + // SAFETY: The length is less than the capacity. + unsafe { self.push_within_capacity_unchecked(v) }; + Ok(()) + } else { + Err(PushError(v)) + } + } + + /// Appends an element to the back of the [`Vec`] instance without reallocating. + /// + /// # Safety + /// + /// The length must be less than the capacity. + unsafe fn push_within_capacity_unchecked(&mut self, v: T) { let spare = self.spare_capacity_mut(); - // SAFETY: The call to `reserve` was successful so the spare capacity is at least 1. + // SAFETY: By the safety requirements, `spare` is non-empty. unsafe { spare.get_unchecked_mut(0) }.write(v); // SAFETY: We just initialised the first spare entry, so it is safe to increase the length - // by 1. We also know that the new length is <= capacity because of the previous call to - // `reserve` above. + // by 1. We also know that the new length is <= capacity because the caller guarantees that + // the length is less than the capacity at the beginning of this function. unsafe { self.inc_len(1) }; - Ok(()) } /// Removes the last element from a vector and returns it, or `None` if it is empty. 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 088bf14a886e1e746c961a862ebccbb76d7cbd4e Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:32 +0000 Subject: rust: alloc: add Vec::drain_all This is like the stdlib method drain, except that it's hard-coded to use the entire vector's range. Rust Binder uses it in the range allocator to take ownership of everything in a vector in a case where reusing the vector is desirable. Implementing `DrainAll` in terms of `slice::IterMut` lets us reuse some nice optimizations in core for the case where T is a ZST. Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250502-vec-methods-v5-4-06d20ad9366f@google.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 59 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 64dfa9af5589..afaf22865342 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -586,6 +586,30 @@ where unsafe { ptr::drop_in_place(ptr) }; } } + + /// Takes ownership of all items in this vector without consuming the allocation. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![0, 1, 2, 3]?; + /// + /// for (i, j) in v.drain_all().enumerate() { + /// assert_eq!(i, j); + /// } + /// + /// assert!(v.capacity() >= 4); + /// # Ok::<(), Error>(()) + /// ``` + pub fn drain_all(&mut self) -> DrainAll<'_, T> { + // SAFETY: This does not underflow the length. + let elems = unsafe { self.dec_len(self.len()) }; + // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we + // just set the length to zero, we may transfer ownership to the `DrainAll` object. + DrainAll { + elements: elems.iter_mut(), + } + } } impl Vec { @@ -1073,3 +1097,38 @@ where } } } + +/// An iterator that owns all items in a vector, but does not own its allocation. +/// +/// # Invariants +/// +/// Every `&mut T` returned by the iterator references a `T` that the iterator may take ownership +/// of. +pub struct DrainAll<'vec, T> { + elements: slice::IterMut<'vec, T>, +} + +impl<'vec, T> Iterator for DrainAll<'vec, T> { + type Item = T; + + fn next(&mut self) -> Option { + let elem: *mut T = self.elements.next()?; + // SAFETY: By the type invariants, we may take ownership of this value. + Some(unsafe { elem.read() }) + } + + fn size_hint(&self) -> (usize, Option) { + self.elements.size_hint() + } +} + +impl<'vec, T> Drop for DrainAll<'vec, T> { + fn drop(&mut self) { + if core::mem::needs_drop::() { + let iter = core::mem::take(&mut self.elements); + let ptr: *mut [T] = iter.into_slice(); + // SAFETY: By the type invariants, we own these values so we may destroy them. + unsafe { ptr::drop_in_place(ptr) }; + } + } +} -- cgit v1.2.3 From 9f140894e72735f034fdc0e963d0550ef03c6f44 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Fri, 2 May 2025 13:19:33 +0000 Subject: rust: alloc: add Vec::retain This adds a common Vec method called `retain` that removes all elements that don't match a certain condition. Rust Binder uses it to find all processes that match a given pid. The stdlib retain method takes &T rather than &mut T and has a separate retain_mut for the &mut T case. However, this is considered an API mistake that can't be fixed now due to backwards compatibility. There's no reason for us to repeat that mistake. Signed-off-by: Alice Ryhl Reviewed-by: Greg Kroah-Hartman Reviewed-by: Benno Lossin Link: https://lore.kernel.org/r/20250502-vec-methods-v5-5-06d20ad9366f@google.com Signed-off-by: Danilo Krummrich --- rust/kernel/alloc/kvec.rs | 72 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index afaf22865342..8843dea0b377 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -610,6 +610,29 @@ where elements: elems.iter_mut(), } } + + /// Removes all elements that don't match the provided closure. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![1, 2, 3, 4]?; + /// v.retain(|i| *i % 2 == 0); + /// assert_eq!(v, [2, 4]); + /// # Ok::<(), Error>(()) + /// ``` + pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) { + let mut num_kept = 0; + let mut next_to_check = 0; + while let Some(to_check) = self.get_mut(next_to_check) { + if f(to_check) { + self.swap(num_kept, next_to_check); + num_kept += 1; + } + next_to_check += 1; + } + self.truncate(num_kept); + } } impl Vec { @@ -1132,3 +1155,52 @@ impl<'vec, T> Drop for DrainAll<'vec, T> { } } } + +#[macros::kunit_tests(rust_kvec_kunit)] +mod tests { + use super::*; + use crate::prelude::*; + + #[test] + fn test_kvec_retain() { + /// Verify correctness for one specific function. + #[expect(clippy::needless_range_loop)] + fn verify(c: &[bool]) { + let mut vec1: KVec = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); + let mut vec2: KVec = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); + + for i in 0..c.len() { + vec1.push_within_capacity(i).unwrap(); + if c[i] { + vec2.push_within_capacity(i).unwrap(); + } + } + + vec1.retain(|i| c[*i]); + + assert_eq!(vec1, vec2); + } + + /// Add one to a binary integer represented as a boolean array. + fn add(value: &mut [bool]) { + let mut carry = true; + for v in value { + let new_v = carry != *v; + carry = carry && *v; + *v = new_v; + } + } + + // This boolean array represents a function from index to boolean. We check that `retain` + // behaves correctly for all possible boolean arrays of every possible length less than + // ten. + let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap(); + for len in 0..10 { + for _ in 0u32..1u32 << len { + verify(&func); + add(&mut func); + } + func.push_within_capacity(false).unwrap(); + } + } +} -- 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') 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') 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