[PATCH 2/5] rust: alloc: add Vec::pop

[PATCH 2/5] rust: alloc: add Vec::pop

[Alice Ryhl]

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 95e752ed27395fce72d372976b74fb1b0e957194..9943358c70aa63f5ad7ed9782cb8879d7a80a8fb 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -302,6 +302,37 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
         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<T> {
+        let Some(len_sub_1) = self.len.checked_sub(1) else {
+            return None;
+        };
+
+        // INVARIANT: If the first `len` elements are valid, then the first `len-1` elements are
+        // valid.
+        self.len = len_sub_1;
+
+        // INVARIANT: This invalidates a value in this vector's allocation, but the Vec invariants
+        // do not require it to be valid because `self.len <= len_sub_1`.
+        // SAFETY: Since `len_sub_1` is less than the value `self.len` had at the beginning of
+        // `pop`, this index holds a valid value.
+        Some(unsafe { self.as_mut_ptr().add(len_sub_1).read() })
+    }
+
     /// Creates a new [`Vec`] instance with at least the given capacity.
     ///
     /// # Examples

-- 
2.49.0.rc1.451.g8f38331e32-goog

Re: [PATCH 2/5] rust: alloc: add Vec::pop

[Benno Lossin]

On Thu Mar 20, 2025 at 2:52 PM CET, Alice Ryhl wrote:
> 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 <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs | 31 +++++++++++++++++++++++++++++++
>  1 file changed, 31 insertions(+)
>
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 95e752ed27395fce72d372976b74fb1b0e957194..9943358c70aa63f5ad7ed9782cb8879d7a80a8fb 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -302,6 +302,37 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
>          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<T> {
> +        let Some(len_sub_1) = self.len.checked_sub(1) else {
> +            return None;
> +        };

Isn't it possible to do:?
    
    let len_sub_1 = self.len.checked_sub(1)?;

> +
> +        // INVARIANT: If the first `len` elements are valid, then the first `len-1` elements are

Please add spaces around `-`.

> +        // valid.
> +        self.len = len_sub_1;
> +
> +        // INVARIANT: This invalidates a value in this vector's allocation, but the Vec invariants
> +        // do not require it to be valid because `self.len <= len_sub_1`.

I don't think this should be an `INVARIANT` comment. Maybe we don't even
need it.

---
Cheers,
Benno

> +        // SAFETY: Since `len_sub_1` is less than the value `self.len` had at the beginning of
> +        // `pop`, this index holds a valid value.
> +        Some(unsafe { self.as_mut_ptr().add(len_sub_1).read() })
> +    }
> +
>      /// Creates a new [`Vec`] instance with at least the given capacity.
>      ///
>      /// # Examples

Re: [PATCH 2/5] rust: alloc: add Vec::pop

[Alice Ryhl]

On Thu, Mar 20, 2025 at 10:11:09PM +0000, Benno Lossin wrote:
> On Thu Mar 20, 2025 at 2:52 PM CET, Alice Ryhl wrote:
> > 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 <aliceryhl@google.com>
> > ---
> >  rust/kernel/alloc/kvec.rs | 31 +++++++++++++++++++++++++++++++
> >  1 file changed, 31 insertions(+)
> >
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index 95e752ed27395fce72d372976b74fb1b0e957194..9943358c70aa63f5ad7ed9782cb8879d7a80a8fb 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -302,6 +302,37 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
> >          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<T> {
> > +        let Some(len_sub_1) = self.len.checked_sub(1) else {
> > +            return None;
> > +        };
> 
> Isn't it possible to do:?
>     
>     let len_sub_1 = self.len.checked_sub(1)?;

Yes, good catch.

> > +
> > +        // INVARIANT: If the first `len` elements are valid, then the first `len-1` elements are
> 
> Please add spaces around `-`.

I can do that, but does it really read better?

> > +        // valid.
> > +        self.len = len_sub_1;
> > +
> > +        // INVARIANT: This invalidates a value in this vector's allocation, but the Vec invariants
> > +        // do not require it to be valid because `self.len <= len_sub_1`.
> 
> I don't think this should be an `INVARIANT` comment. Maybe we don't even
> need it.

I can drop the INVARIANT: prefix.

Alice

Re: [PATCH 2/5] rust: alloc: add Vec::pop

[Benno Lossin]

On Fri Mar 21, 2025 at 8:44 AM CET, Alice Ryhl wrote:
> On Thu, Mar 20, 2025 at 10:11:09PM +0000, Benno Lossin wrote:
>> On Thu Mar 20, 2025 at 2:52 PM CET, Alice Ryhl wrote:
>> > +
>> > +        // INVARIANT: If the first `len` elements are valid, then the first `len-1` elements are
>> 
>> Please add spaces around `-`.
>
> I can do that, but does it really read better?

That's how rustfmt would format it and I do think it improves
readability for me.

>> > +        // valid.
>> > +        self.len = len_sub_1;
>> > +
>> > +        // INVARIANT: This invalidates a value in this vector's allocation, but the Vec invariants
>> > +        // do not require it to be valid because `self.len <= len_sub_1`.
>> 
>> I don't think this should be an `INVARIANT` comment. Maybe we don't even
>> need it.
>
> I can drop the INVARIANT: prefix.

Sounds good.

---
Cheers,
Benno