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 <aliceryhl@google.com>
---
 rust/kernel/alloc/kvec.rs | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
         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
+    ///
+    /// ```
+    /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;
+    /// for i in 0..10 {
+    ///     v.push_within_capacity(i).unwrap();
+    /// }
+    ///
+    /// assert!(v.push_within_capacity(10).is_err());
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn insert_within_capacity(&mut self, index: usize, element: T) -> Result<(), T> {
+        let len = self.len();
+        assert!(index <= len);
+
+        if len >= self.capacity() {
+            return Err(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

-- 
2.49.0.901.g37484f566f-goog

On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> 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 <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs | 39 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 39 insertions(+)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
>          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.

Why panic and why not just return an error instead?

thanks,

greg k-h

On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > 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 <aliceryhl@google.com>
> > ---
> >  rust/kernel/alloc/kvec.rs | 39 +++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 39 insertions(+)
> > 
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
> >          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.
> 
> Why panic and why not just return an error instead?

It's for consistency with stdlib. Illegal use is panic, expected error
conditions are errors.

Alice

On Wed, Apr 30, 2025 at 11:24:23AM +0000, Alice Ryhl wrote:
> On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> > On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > > 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 <aliceryhl@google.com>
> > > ---
> > >  rust/kernel/alloc/kvec.rs | 39 +++++++++++++++++++++++++++++++++++++++
> > >  1 file changed, 39 insertions(+)
> > > 
> > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > index 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 100644
> > > --- a/rust/kernel/alloc/kvec.rs
> > > +++ b/rust/kernel/alloc/kvec.rs
> > > @@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
> > >          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.
> > 
> > Why panic and why not just return an error instead?
> 
> It's for consistency with stdlib. Illegal use is panic, expected error
> conditions are errors.

But this is the kernel, not userspace :)

As you can return an error, why not?  Rebooting a box should be a "last
resort" type of thing when you can not recover from an error.  You can
easily not overflow and return an error here, so why do you want to just
give up and cause all data to be lost?

And I don't see any other panics happening in this file, so would this
be the first one?

thanks,

greg k-h

On Wed, Apr 30, 2025 at 01:39:03PM +0200, Greg KH wrote:
> On Wed, Apr 30, 2025 at 11:24:23AM +0000, Alice Ryhl wrote:
> > On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> > > On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > > > 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 <aliceryhl@google.com>
> > > > ---
> > > >  rust/kernel/alloc/kvec.rs | 39 +++++++++++++++++++++++++++++++++++++++
> > > >  1 file changed, 39 insertions(+)
> > > > 
> > > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > > index 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 100644
> > > > --- a/rust/kernel/alloc/kvec.rs
> > > > +++ b/rust/kernel/alloc/kvec.rs
> > > > @@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
> > > >          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.
> > > 
> > > Why panic and why not just return an error instead?
> > 
> > It's for consistency with stdlib. Illegal use is panic, expected error
> > conditions are errors.
> 
> But this is the kernel, not userspace :)
> 
> As you can return an error, why not?  Rebooting a box should be a "last
> resort" type of thing when you can not recover from an error.  You can
> easily not overflow and return an error here, so why do you want to just
> give up and cause all data to be lost?
> 
> And I don't see any other panics happening in this file, so would this
> be the first one?

I don't feel strongly about this method, but it's not the first panic.
The vector type has an indexing operator vec[i] that panics if you index
out-of-bounds.

Alice

On Wed, Apr 30, 2025 at 12:15:14PM +0000, Alice Ryhl wrote:
> On Wed, Apr 30, 2025 at 01:39:03PM +0200, Greg KH wrote:
> > On Wed, Apr 30, 2025 at 11:24:23AM +0000, Alice Ryhl wrote:
> > > On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> > > > On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > > > > 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 <aliceryhl@google.com>
> > > > > ---
> > > > >  rust/kernel/alloc/kvec.rs | 39 +++++++++++++++++++++++++++++++++++++++
> > > > >  1 file changed, 39 insertions(+)
> > > > > 
> > > > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > > > index 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 100644
> > > > > --- a/rust/kernel/alloc/kvec.rs
> > > > > +++ b/rust/kernel/alloc/kvec.rs
> > > > > @@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
> > > > >          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.
> > > > 
> > > > Why panic and why not just return an error instead?
> > > 
> > > It's for consistency with stdlib. Illegal use is panic, expected error
> > > conditions are errors.
> > 
> > But this is the kernel, not userspace :)
> > 
> > As you can return an error, why not?  Rebooting a box should be a "last
> > resort" type of thing when you can not recover from an error.  You can
> > easily not overflow and return an error here, so why do you want to just
> > give up and cause all data to be lost?
> > 
> > And I don't see any other panics happening in this file, so would this
> > be the first one?
> 
> I don't feel strongly about this method, but it's not the first panic.
> The vector type has an indexing operator vec[i] that panics if you index
> out-of-bounds.

This is because core::ops::Index isn't fallible and even if we wouldn't
implement Index for Vec, we'd get a slice through Deref, where it is exactly the
same.

In this case though, we can easily avoid the panic by checking the index and
return an error instead, which is what we should do.