[PATCH 00/20] Generic `Allocator` support for Rust

[PATCH 00/20] Generic `Allocator` support for Rust

[Danilo Krummrich]

Hi,

This patch series adds generic kernel allocator support for Rust, which so far
is limited to `kmalloc` allocations.

In order to abstain from (re-)adding unstable Rust features to the kernel, this
patch series does not extend the `Allocator` trait from Rust's `alloc` crate,
nor does it extend the `BoxExt` and `VecExt` extensions.

Instead, this series introduces a kernel specific `Allocator` trait, which is
implemented by the `Kmalloc`, `Vmalloc` and `KVmalloc` allocators, also
implemented in the context of this series.

As a consequence we need our own `Box` and `Vec` types, which are implemented by
this series as `KBox` and `KVec`.

With that, we can start using `KBox` and `KVec` throughout the tree and remove
the now obolete extensions `BoxExt` and `VecExt`.

For a final cleanup, this series removes the last minor dependencies to Rust's
`alloc` crate and removes it from the entire kernel build.

The series ensures not to break the `rusttest` make target by implementing the
`allocator_test` module providing a stub implementation for all kernel
`Allocator`s.

This patch series passes all KUnit tests, including the ones added by this
series. Additionally, the tests were run with `kmemleak` and `KASAN` enabled,
without any issues.

This series is also available in [1].

[1] https://gitlab.freedesktop.org/drm/nova/-/tree/topic/allocator

Danilo Krummrich (20):
  rust: alloc: add `Allocator` trait
  rust: alloc: separate `aligned_size` from `krealloc_aligned`
  rust: alloc: rename `KernelAllocator` to `Kmalloc`
  rust: alloc: implement `Allocator` for `Kmalloc`
  rust: alloc: add module `allocator_test`
  rust: alloc: remove `krealloc_aligned`
  rust: alloc: implement `Vmalloc` allocator
  rust: alloc: implement `KVmalloc` allocator
  rust: types: implement `Unique<T>`
  rust: alloc: implement `KBox`
  rust: treewide: switch to `KBox`
  rust: alloc: remove `BoxExt` extension
  rust: alloc: implement `KVec`
  rust: alloc: implement `IntoIterator` for `KVec`
  rust: alloc: implement `collect` for `IntoIter`
  rust: treewide: switch to `KVec`
  rust: alloc: remove `VecExt` extension
  rust: error: use `core::alloc::LayoutError`
  rust: str: test: replace `alloc::format`
  kbuild: rust: remove the `alloc` crate

 rust/Makefile                       |  44 +-
 rust/bindings/bindings_helper.h     |   1 +
 rust/exports.c                      |   1 -
 rust/kernel/alloc.rs                |  92 ++-
 rust/kernel/alloc/allocator.rs      | 177 +++++-
 rust/kernel/alloc/allocator_test.rs |  23 +
 rust/kernel/alloc/box_ext.rs        |  56 --
 rust/kernel/alloc/kbox.rs           | 333 +++++++++++
 rust/kernel/alloc/kvec.rs           | 861 ++++++++++++++++++++++++++++
 rust/kernel/alloc/vec_ext.rs        | 182 ------
 rust/kernel/error.rs                |   2 +-
 rust/kernel/init.rs                 |  72 +--
 rust/kernel/init/__internal.rs      |   2 +-
 rust/kernel/lib.rs                  |   1 -
 rust/kernel/prelude.rs              |   5 +-
 rust/kernel/str.rs                  |  78 ++-
 rust/kernel/sync/arc.rs             |  17 +-
 rust/kernel/sync/condvar.rs         |   5 +-
 rust/kernel/sync/lock/mutex.rs      |   3 +-
 rust/kernel/sync/lock/spinlock.rs   |   3 +-
 rust/kernel/sync/locked_by.rs       |   2 +-
 rust/kernel/types.rs                | 186 +++++-
 rust/kernel/workqueue.rs            |  22 +-
 samples/rust/rust_minimal.rs        |   4 +-
 scripts/Makefile.build              |   7 +-
 25 files changed, 1769 insertions(+), 410 deletions(-)
 create mode 100644 rust/kernel/alloc/allocator_test.rs
 delete mode 100644 rust/kernel/alloc/box_ext.rs
 create mode 100644 rust/kernel/alloc/kbox.rs
 create mode 100644 rust/kernel/alloc/kvec.rs
 delete mode 100644 rust/kernel/alloc/vec_ext.rs


base-commit: 1613e604df0cd359cf2a7fbd9be7a0bcfacfabd0
-- 
2.45.2

[PATCH 01/20] rust: alloc: add `Allocator` trait

[Danilo Krummrich]

Add a kernel specific `Allocator` trait, that in contrast to the one in
Rust's core library doesn't require unstable features and supports GFP
flags.

Subsequent patches add the following trait implementors: `Kmalloc`,
`Vmalloc` and `KVmalloc`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs | 73 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 73 insertions(+)

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 531b5e471cb1..462e00982510 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -11,6 +11,7 @@
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub struct AllocError;
+use core::{alloc::Layout, ptr, ptr::NonNull};
 
 /// Flags to be used when allocating memory.
 ///
@@ -71,3 +72,75 @@ pub mod flags {
     /// small allocations.
     pub const GFP_NOWAIT: Flags = Flags(bindings::GFP_NOWAIT);
 }
+
+/// The kernel's [`Allocator`] trait.
+///
+/// An implementation of [`Allocator`] can allocate, re-allocate and free memory buffer described
+/// via [`Layout`].
+///
+/// [`Allocator`] is designed to be implemented on ZSTs; its safety requirements to not allow for
+/// keeping a state throughout an instance.
+///
+/// # Safety
+///
+/// Memory returned from an allocator must point to a valid memory buffer and remain valid until
+/// its explicitly freed.
+///
+/// Copying, cloning, or moving the allocator must not invalidate memory blocks returned from this
+/// allocator. A copied, cloned or even new allocator of the same type must behave like the same
+/// allocator, and any pointer to a memory buffer which is currently allocated may be passed to any
+/// other method of the allocator.
+pub unsafe trait Allocator {
+    /// Allocate memory based on `layout` and `flags`.
+    ///
+    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the size an
+    /// alignment requirements of layout, but may exceed the requested size.
+    ///
+    /// This function is equivalent to `realloc` when called with a NULL pointer and an `old_size`
+    /// of `0`.
+    fn alloc(&self, layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {
+        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
+        // for a new memory allocation.
+        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
+    }
+
+    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
+    /// requested size is zero, `realloc` behaves equivalent to `free`.
+    ///
+    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
+    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
+    ///
+    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
+    /// buffer; this is implementation specific to the allocator.
+    ///
+    /// On allocation failure, the existing buffer, if any, remains valid.
+    ///
+    /// The buffer is represented as `NonNull<[u8]>`.
+    ///
+    /// # Safety
+    ///
+    /// `ptr` must point to an existing and valid memory allocation created by this allocator
+    /// instance of a size of at least `old_size`.
+    ///
+    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
+    /// created.
+    unsafe fn realloc(
+        &self,
+        ptr: *mut u8,
+        old_size: usize,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError>;
+
+    /// Free an existing memory allocation.
+    ///
+    /// # Safety
+    ///
+    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
+    /// instance.
+    unsafe fn free(&self, ptr: *mut u8) {
+        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
+        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
+        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };
+    }
+}
-- 
2.45.2

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Benno Lossin]

On 04.07.24 19:06, Danilo Krummrich wrote:
> Add a kernel specific `Allocator` trait, that in contrast to the one in
> Rust's core library doesn't require unstable features and supports GFP
> flags.
> 
> Subsequent patches add the following trait implementors: `Kmalloc`,
> `Vmalloc` and `KVmalloc`.
> 
> Signed-off-by: Danilo Krummrich <dakr@redhat.com>
> ---
>  rust/kernel/alloc.rs | 73 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 73 insertions(+)
> 
> diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> index 531b5e471cb1..462e00982510 100644
> --- a/rust/kernel/alloc.rs
> +++ b/rust/kernel/alloc.rs
> @@ -11,6 +11,7 @@
>  /// Indicates an allocation error.
>  #[derive(Copy, Clone, PartialEq, Eq, Debug)]
>  pub struct AllocError;
> +use core::{alloc::Layout, ptr, ptr::NonNull};
> 
>  /// Flags to be used when allocating memory.
>  ///
> @@ -71,3 +72,75 @@ pub mod flags {
>      /// small allocations.
>      pub const GFP_NOWAIT: Flags = Flags(bindings::GFP_NOWAIT);
>  }
> +
> +/// The kernel's [`Allocator`] trait.
> +///
> +/// An implementation of [`Allocator`] can allocate, re-allocate and free memory buffer described
> +/// via [`Layout`].
> +///
> +/// [`Allocator`] is designed to be implemented on ZSTs; its safety requirements to not allow for
> +/// keeping a state throughout an instance.

Why do the functions take `&self` if it is forbidden to have state? I
would remove the receiver in that case.

> +///
> +/// # Safety
> +///
> +/// Memory returned from an allocator must point to a valid memory buffer and remain valid until
> +/// its explicitly freed.
> +///
> +/// Copying, cloning, or moving the allocator must not invalidate memory blocks returned from this
> +/// allocator. A copied, cloned or even new allocator of the same type must behave like the same
> +/// allocator, and any pointer to a memory buffer which is currently allocated may be passed to any
> +/// other method of the allocator.

If you provide no receiver methods, then I think we can remove this
requirement.

> +pub unsafe trait Allocator {
> +    /// Allocate memory based on `layout` and `flags`.
> +    ///
> +    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the size an

typo "an" -> "and"

> +    /// alignment requirements of layout, but may exceed the requested size.

Also if it may exceed the size, then I wouldn't call that "satisfies the
size [...] requirements".

> +    ///
> +    /// This function is equivalent to `realloc` when called with a NULL pointer and an `old_size`
> +    /// of `0`.

This is only true for the default implementation and could be
overridden, since it is not a requirement of implementing this trait to
keep it this way. I would remove this sentence.

> +    fn alloc(&self, layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {

Instead of using the `Flags` type from the alloc module, we should have
an associated `Flags` type in this trait.

Similarly, it might also be a good idea to let the implementer specify a
custom error type.

> +        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
> +        // for a new memory allocation.
> +        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
> +    }
> +
> +    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
> +    /// requested size is zero, `realloc` behaves equivalent to `free`.

This is not guaranteed by the implementation.

> +    ///
> +    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
> +    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
> +    ///
> +    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
> +    /// buffer; this is implementation specific to the allocator.
> +    ///
> +    /// On allocation failure, the existing buffer, if any, remains valid.
> +    ///
> +    /// The buffer is represented as `NonNull<[u8]>`.
> +    ///
> +    /// # Safety
> +    ///
> +    /// `ptr` must point to an existing and valid memory allocation created by this allocator
> +    /// instance of a size of at least `old_size`.
> +    ///
> +    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
> +    /// created.
> +    unsafe fn realloc(
> +        &self,
> +        ptr: *mut u8,
> +        old_size: usize,

Why not request the old layout like the std Allocator's grow/shrink
functions do?

> +        layout: Layout,
> +        flags: Flags,
> +    ) -> Result<NonNull<[u8]>, AllocError>;
> +
> +    /// Free an existing memory allocation.
> +    ///
> +    /// # Safety
> +    ///
> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
> +    /// instance.
> +    unsafe fn free(&self, ptr: *mut u8) {

`ptr` should be `NonNull<u8>`.

> +        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
> +        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
> +        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };

Why does the implementer have to guarantee this?

> +    }
> +}
> --
> 2.45.2
> 

More general questions:
- are there functions in the kernel to efficiently allocate zeroed
  memory? In that case, the Allocator trait should also have methods
  that do that (with a iterating default impl).
- I am not sure putting everything into the single realloc function is a
  good idea, I like the grow/shrink methods of the std allocator. Is
  there a reason aside from concentrating the impl to go for only a
  single realloc function?

---
Cheers,
Benno

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Danilo Krummrich]

On Sat, Jul 06, 2024 at 10:33:49AM +0000, Benno Lossin wrote:
> On 04.07.24 19:06, Danilo Krummrich wrote:
> > Add a kernel specific `Allocator` trait, that in contrast to the one in
> > Rust's core library doesn't require unstable features and supports GFP
> > flags.
> > 
> > Subsequent patches add the following trait implementors: `Kmalloc`,
> > `Vmalloc` and `KVmalloc`.
> > 
> > Signed-off-by: Danilo Krummrich <dakr@redhat.com>
> > ---
> >  rust/kernel/alloc.rs | 73 ++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 73 insertions(+)
> > 
> > diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> > index 531b5e471cb1..462e00982510 100644
> > --- a/rust/kernel/alloc.rs
> > +++ b/rust/kernel/alloc.rs
> > @@ -11,6 +11,7 @@
> >  /// Indicates an allocation error.
> >  #[derive(Copy, Clone, PartialEq, Eq, Debug)]
> >  pub struct AllocError;
> > +use core::{alloc::Layout, ptr, ptr::NonNull};
> > 
> >  /// Flags to be used when allocating memory.
> >  ///
> > @@ -71,3 +72,75 @@ pub mod flags {
> >      /// small allocations.
> >      pub const GFP_NOWAIT: Flags = Flags(bindings::GFP_NOWAIT);
> >  }
> > +
> > +/// The kernel's [`Allocator`] trait.
> > +///
> > +/// An implementation of [`Allocator`] can allocate, re-allocate and free memory buffer described
> > +/// via [`Layout`].
> > +///
> > +/// [`Allocator`] is designed to be implemented on ZSTs; its safety requirements to not allow for
> > +/// keeping a state throughout an instance.
> 
> Why do the functions take `&self` if it is forbidden to have state? I
> would remove the receiver in that case.

Yes, that that makes sense.

> 
> > +///
> > +/// # Safety
> > +///
> > +/// Memory returned from an allocator must point to a valid memory buffer and remain valid until
> > +/// its explicitly freed.
> > +///
> > +/// Copying, cloning, or moving the allocator must not invalidate memory blocks returned from this
> > +/// allocator. A copied, cloned or even new allocator of the same type must behave like the same
> > +/// allocator, and any pointer to a memory buffer which is currently allocated may be passed to any
> > +/// other method of the allocator.
> 
> If you provide no receiver methods, then I think we can remove this
> requirement.

Indeed.

> 
> > +pub unsafe trait Allocator {
> > +    /// Allocate memory based on `layout` and `flags`.
> > +    ///
> > +    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the size an
> 
> typo "an" -> "and"
> 
> > +    /// alignment requirements of layout, but may exceed the requested size.
> 
> Also if it may exceed the size, then I wouldn't call that "satisfies the
> size [...] requirements".

Do you have a better proposal? To me "satisfies or exceeds" sounds reasonable.

> 
> > +    ///
> > +    /// This function is equivalent to `realloc` when called with a NULL pointer and an `old_size`
> > +    /// of `0`.
> 
> This is only true for the default implementation and could be
> overridden, since it is not a requirement of implementing this trait to
> keep it this way. I would remove this sentence.

I could add a bit more generic description and say that for the default impl
"This function is eq..."?

> 
> > +    fn alloc(&self, layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {
> 
> Instead of using the `Flags` type from the alloc module, we should have
> an associated `Flags` type in this trait.

What does this give us?

> 
> Similarly, it might also be a good idea to let the implementer specify a
> custom error type.

Same here, why?

> 
> > +        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
> > +        // for a new memory allocation.
> > +        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
> > +    }
> > +
> > +    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
> > +    /// requested size is zero, `realloc` behaves equivalent to `free`.
> 
> This is not guaranteed by the implementation.

Not sure what exactly you mean? Is it about "satisfy" again?

> 
> > +    ///
> > +    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
> > +    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
> > +    ///
> > +    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
> > +    /// buffer; this is implementation specific to the allocator.
> > +    ///
> > +    /// On allocation failure, the existing buffer, if any, remains valid.
> > +    ///
> > +    /// The buffer is represented as `NonNull<[u8]>`.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// `ptr` must point to an existing and valid memory allocation created by this allocator
> > +    /// instance of a size of at least `old_size`.
> > +    ///
> > +    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
> > +    /// created.
> > +    unsafe fn realloc(
> > +        &self,
> > +        ptr: *mut u8,
> > +        old_size: usize,
> 
> Why not request the old layout like the std Allocator's grow/shrink
> functions do?

Because we only care about the size that needs to be preserved when growing the
buffer. The `alignment` field of `Layout` would be wasted.

> 
> > +        layout: Layout,
> > +        flags: Flags,
> > +    ) -> Result<NonNull<[u8]>, AllocError>;
> > +
> > +    /// Free an existing memory allocation.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
> > +    /// instance.
> > +    unsafe fn free(&self, ptr: *mut u8) {
> 
> `ptr` should be `NonNull<u8>`.

Creating a `NonNull` from a raw pointer is an extra operation for any user of
`free` and given that all `free` functions in the kernel accept a NULL pointer,
I think there is not much value in making this `NonNull`.

> 
> > +        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
> > +        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
> > +        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };
> 
> Why does the implementer have to guarantee this?

Who else can guarantee this?

> 
> > +    }
> > +}
> > --
> > 2.45.2
> > 
> 
> More general questions:
> - are there functions in the kernel to efficiently allocate zeroed
>   memory? In that case, the Allocator trait should also have methods
>   that do that (with a iterating default impl).

We do this with GFP flags. In particular, you can pass GFP_ZERO to `alloc` and
`realloc` to get zeroed memory. Hence, I think having dedicated functions that
just do "flags | GFP_ZERO" would not add much value.

> - I am not sure putting everything into the single realloc function is a
>   good idea, I like the grow/shrink methods of the std allocator. Is
>   there a reason aside from concentrating the impl to go for only a
>   single realloc function?

Yes, `krealloc()` already provides exactly the described behaviour. See the
implementation of `Kmalloc`.

> 
> ---
> Cheers,
> Benno
> 

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Benno Lossin]

On 06.07.24 13:05, Danilo Krummrich wrote:
> On Sat, Jul 06, 2024 at 10:33:49AM +0000, Benno Lossin wrote:
>> On 04.07.24 19:06, Danilo Krummrich wrote:
>>> +pub unsafe trait Allocator {
>>> +    /// Allocate memory based on `layout` and `flags`.
>>> +    ///
>>> +    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the size an
>>
>> typo "an" -> "and"
>>
>>> +    /// alignment requirements of layout, but may exceed the requested size.
>>
>> Also if it may exceed the size, then I wouldn't call that "satisfies the
>> size [...] requirements".
> 
> Do you have a better proposal? To me "satisfies or exceeds" sounds reasonable.

I think "satisfies the layout constraints (i.e. minimum size and
alignment as specified by `layout`)" would be better.

>>> +    ///
>>> +    /// This function is equivalent to `realloc` when called with a NULL pointer and an `old_size`
>>> +    /// of `0`.
>>
>> This is only true for the default implementation and could be
>> overridden, since it is not a requirement of implementing this trait to
>> keep it this way. I would remove this sentence.
> 
> I could add a bit more generic description and say that for the default impl
> "This function is eq..."?
> 
>>
>>> +    fn alloc(&self, layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {
>>
>> Instead of using the `Flags` type from the alloc module, we should have
>> an associated `Flags` type in this trait.
> 
> What does this give us?

1. IIRC not all flags can be used with every allocator (or do not have
   an effect) and it would be best if only the working ones are allowed.
2. that way the design is more flexible and could be upstreamed more
   easily.

>> Similarly, it might also be a good idea to let the implementer specify a
>> custom error type.
> 
> Same here, why?

In this case the argument is weaker, but it could allow us to implement
an allocator with `Error = Infallible`, to statically guarantee
allocation (e.g. when using GFP_ATOMIC). But at the moment there is no
user.

>>> +        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
>>> +        // for a new memory allocation.
>>> +        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
>>> +    }
>>> +
>>> +    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
>>> +    /// requested size is zero, `realloc` behaves equivalent to `free`.
>>
>> This is not guaranteed by the implementation.
> 
> Not sure what exactly you mean? Is it about "satisfy" again?

If the requested size is zero, the implementation could also leak the
memory, nothing prevents me from implementing such an Allocator.

>>> +    ///
>>> +    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
>>> +    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
>>> +    ///
>>> +    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
>>> +    /// buffer; this is implementation specific to the allocator.
>>> +    ///
>>> +    /// On allocation failure, the existing buffer, if any, remains valid.
>>> +    ///
>>> +    /// The buffer is represented as `NonNull<[u8]>`.
>>> +    ///
>>> +    /// # Safety
>>> +    ///
>>> +    /// `ptr` must point to an existing and valid memory allocation created by this allocator
>>> +    /// instance of a size of at least `old_size`.
>>> +    ///
>>> +    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
>>> +    /// created.
>>> +    unsafe fn realloc(
>>> +        &self,
>>> +        ptr: *mut u8,
>>> +        old_size: usize,
>>
>> Why not request the old layout like the std Allocator's grow/shrink
>> functions do?
> 
> Because we only care about the size that needs to be preserved when growing the
> buffer. The `alignment` field of `Layout` would be wasted.

In the std Allocator they specified an old layout. This is probably
because of the following: if `Layout` is ever extended to hold another
property that would need to be updated, the signatures are already
correct.
In our case we could change it tree-wide, so I guess we could fix that
issue when it comes up.

>>> +        layout: Layout,
>>> +        flags: Flags,
>>> +    ) -> Result<NonNull<[u8]>, AllocError>;
>>> +
>>> +    /// Free an existing memory allocation.
>>> +    ///
>>> +    /// # Safety
>>> +    ///
>>> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
>>> +    /// instance.
>>> +    unsafe fn free(&self, ptr: *mut u8) {
>>
>> `ptr` should be `NonNull<u8>`.
> 
> Creating a `NonNull` from a raw pointer is an extra operation for any user of
> `free` and given that all `free` functions in the kernel accept a NULL pointer,
> I think there is not much value in making this `NonNull`.

I don't think that this argument holds for Rust though. For example,
`KBox` contains a `Unique` that contains a `NonNull`, so freeing could
just be done with `free(self.0.0)`.

>>> +        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
>>> +        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
>>> +        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };
>>
>> Why does the implementer have to guarantee this?
> 
> Who else can guarantee this?

Only the implementer yes. But they are not forced to do this i.e.
nothing in the safety requirements of `Allocator` prevents me from doing
a no-op on reallocating to a zero size.

>>> +    }
>>> +}
>>> --
>>> 2.45.2
>>>
>>
>> More general questions:
>> - are there functions in the kernel to efficiently allocate zeroed
>>   memory? In that case, the Allocator trait should also have methods
>>   that do that (with a iterating default impl).
> 
> We do this with GFP flags. In particular, you can pass GFP_ZERO to `alloc` and
> `realloc` to get zeroed memory. Hence, I think having dedicated functions that
> just do "flags | GFP_ZERO" would not add much value.

Ah right, no in that case, we don't need it.

>> - I am not sure putting everything into the single realloc function is a
>>   good idea, I like the grow/shrink methods of the std allocator. Is
>>   there a reason aside from concentrating the impl to go for only a
>>   single realloc function?
> 
> Yes, `krealloc()` already provides exactly the described behaviour. See the
> implementation of `Kmalloc`.

But `kvmalloc` does not and neither does `vmalloc`. I would prefer
multiple smaller functions over one big one in this case.

---
Cheers,
Benno

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Danilo Krummrich]

On Sat, Jul 06, 2024 at 01:17:19PM +0000, Benno Lossin wrote:
> On 06.07.24 13:05, Danilo Krummrich wrote:
> > On Sat, Jul 06, 2024 at 10:33:49AM +0000, Benno Lossin wrote:
> >> On 04.07.24 19:06, Danilo Krummrich wrote:
> >>> +pub unsafe trait Allocator {
> >>> +    /// Allocate memory based on `layout` and `flags`.
> >>> +    ///
> >>> +    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the size an
> >>
> >> typo "an" -> "and"
> >>
> >>> +    /// alignment requirements of layout, but may exceed the requested size.
> >>
> >> Also if it may exceed the size, then I wouldn't call that "satisfies the
> >> size [...] requirements".
> > 
> > Do you have a better proposal? To me "satisfies or exceeds" sounds reasonable.
> 
> I think "satisfies the layout constraints (i.e. minimum size and
> alignment as specified by `layout`)" would be better.
> 
> >>> +    ///
> >>> +    /// This function is equivalent to `realloc` when called with a NULL pointer and an `old_size`
> >>> +    /// of `0`.
> >>
> >> This is only true for the default implementation and could be
> >> overridden, since it is not a requirement of implementing this trait to
> >> keep it this way. I would remove this sentence.
> > 
> > I could add a bit more generic description and say that for the default impl
> > "This function is eq..."?
> > 
> >>
> >>> +    fn alloc(&self, layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {
> >>
> >> Instead of using the `Flags` type from the alloc module, we should have
> >> an associated `Flags` type in this trait.
> > 
> > What does this give us?
> 
> 1. IIRC not all flags can be used with every allocator (or do not have
>    an effect) and it would be best if only the working ones are allowed.

Agreed, but I'm not sure if it's worth the effort having different `Flags`
types for that only.

But I guess this and the below argument justify using an associated type. I will
queue this change up.

> 2. that way the design is more flexible and could be upstreamed more
>    easily.
> 
> >> Similarly, it might also be a good idea to let the implementer specify a
> >> custom error type.
> > 
> > Same here, why?
> 
> In this case the argument is weaker, but it could allow us to implement
> an allocator with `Error = Infallible`, to statically guarantee
> allocation (e.g. when using GFP_ATOMIC). But at the moment there is no
> user.

GFP_ATOMIC can fail, I guess you mean __GFP_NOFAIL.

Not really sure how this would work other than with separate `alloc_nofail` and
`realloc_nofail` functions?

> 
> >>> +        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
> >>> +        // for a new memory allocation.
> >>> +        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
> >>> +    }
> >>> +
> >>> +    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
> >>> +    /// requested size is zero, `realloc` behaves equivalent to `free`.
> >>
> >> This is not guaranteed by the implementation.
> > 
> > Not sure what exactly you mean? Is it about "satisfy" again?
> 
> If the requested size is zero, the implementation could also leak the
> memory, nothing prevents me from implementing such an Allocator.

Well, hopefully the documentation stating that `realloc` must be implemented
this exact way prevents you from doing otherwise. :-)

Please let me know if I need to document this in a different way if it's not
sufficient as it is.

> 
> >>> +    ///
> >>> +    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
> >>> +    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
> >>> +    ///
> >>> +    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
> >>> +    /// buffer; this is implementation specific to the allocator.
> >>> +    ///
> >>> +    /// On allocation failure, the existing buffer, if any, remains valid.
> >>> +    ///
> >>> +    /// The buffer is represented as `NonNull<[u8]>`.
> >>> +    ///
> >>> +    /// # Safety
> >>> +    ///
> >>> +    /// `ptr` must point to an existing and valid memory allocation created by this allocator
> >>> +    /// instance of a size of at least `old_size`.
> >>> +    ///
> >>> +    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
> >>> +    /// created.
> >>> +    unsafe fn realloc(
> >>> +        &self,
> >>> +        ptr: *mut u8,
> >>> +        old_size: usize,
> >>
> >> Why not request the old layout like the std Allocator's grow/shrink
> >> functions do?
> > 
> > Because we only care about the size that needs to be preserved when growing the
> > buffer. The `alignment` field of `Layout` would be wasted.
> 
> In the std Allocator they specified an old layout. This is probably
> because of the following: if `Layout` is ever extended to hold another
> property that would need to be updated, the signatures are already
> correct.
> In our case we could change it tree-wide, so I guess we could fix that
> issue when it comes up.

Yes, I think so too.

> 
> >>> +        layout: Layout,
> >>> +        flags: Flags,
> >>> +    ) -> Result<NonNull<[u8]>, AllocError>;
> >>> +
> >>> +    /// Free an existing memory allocation.
> >>> +    ///
> >>> +    /// # Safety
> >>> +    ///
> >>> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
> >>> +    /// instance.
> >>> +    unsafe fn free(&self, ptr: *mut u8) {
> >>
> >> `ptr` should be `NonNull<u8>`.
> > 
> > Creating a `NonNull` from a raw pointer is an extra operation for any user of
> > `free` and given that all `free` functions in the kernel accept a NULL pointer,
> > I think there is not much value in making this `NonNull`.
> 
> I don't think that this argument holds for Rust though. For example,
> `KBox` contains a `Unique` that contains a `NonNull`, so freeing could
> just be done with `free(self.0.0)`.

Agreed, we can indeed make it a `&NonNull<u8>`. However, I find this a bit
inconsistent with the signature of `realloc`.

Should we go with separate `shrink` / `grow`, `free` could be implemented as
shrinking to zero and allowing a NULL pointer makes not much sense.

But as mentioned, I'm not yet seeing the benefit of having `realloc` split into
`grow` and `shrink`.

> 
> >>> +        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
> >>> +        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
> >>> +        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };
> >>
> >> Why does the implementer have to guarantee this?
> > 
> > Who else can guarantee this?
> 
> Only the implementer yes. But they are not forced to do this i.e.
> nothing in the safety requirements of `Allocator` prevents me from doing
> a no-op on reallocating to a zero size.

Ah, I see now, this is the same as your comment on the documentation of
`realloc`. So, this indeed just about missing a safety comment.

> 
> >>> +    }
> >>> +}
> >>> --
> >>> 2.45.2
> >>>
> >>
> >> More general questions:
> >> - are there functions in the kernel to efficiently allocate zeroed
> >>   memory? In that case, the Allocator trait should also have methods
> >>   that do that (with a iterating default impl).
> > 
> > We do this with GFP flags. In particular, you can pass GFP_ZERO to `alloc` and
> > `realloc` to get zeroed memory. Hence, I think having dedicated functions that
> > just do "flags | GFP_ZERO" would not add much value.
> 
> Ah right, no in that case, we don't need it.
> 
> >> - I am not sure putting everything into the single realloc function is a
> >>   good idea, I like the grow/shrink methods of the std allocator. Is
> >>   there a reason aside from concentrating the impl to go for only a
> >>   single realloc function?
> > 
> > Yes, `krealloc()` already provides exactly the described behaviour. See the
> > implementation of `Kmalloc`.
> 
> But `kvmalloc` does not and neither does `vmalloc`. I would prefer
> multiple smaller functions over one big one in this case.

What I forsee is that:

  - `alloc` becomes a `grow` from zero.
  - `free` becomes a `shrink` to zero.
  - `grow` and `shrink` become a `realloc` alias,
     because they're almost the same

Wouldn't this just put us were we already are, effectively?

> 
> ---
> Cheers,
> Benno
> 

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Benno Lossin]

On 06.07.24 17:11, Danilo Krummrich wrote:
> On Sat, Jul 06, 2024 at 01:17:19PM +0000, Benno Lossin wrote:
>> On 06.07.24 13:05, Danilo Krummrich wrote:
>>> On Sat, Jul 06, 2024 at 10:33:49AM +0000, Benno Lossin wrote:
>>>> Similarly, it might also be a good idea to let the implementer specify a
>>>> custom error type.
>>>
>>> Same here, why?
>>
>> In this case the argument is weaker, but it could allow us to implement
>> an allocator with `Error = Infallible`, to statically guarantee
>> allocation (e.g. when using GFP_ATOMIC). But at the moment there is no
>> user.
> 
> GFP_ATOMIC can fail, I guess you mean __GFP_NOFAIL.
> 
> Not really sure how this would work other than with separate `alloc_nofail` and
> `realloc_nofail` functions?

You could have an Allocator that always enables __GFP_NOFAIL, so the
error type could be Infallible. But this doesn't seem that useful at the
moment, so keep the AllocError as is.

>>>>> +        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
>>>>> +        // for a new memory allocation.
>>>>> +        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
>>>>> +    }
>>>>> +
>>>>> +    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
>>>>> +    /// requested size is zero, `realloc` behaves equivalent to `free`.
>>>>
>>>> This is not guaranteed by the implementation.
>>>
>>> Not sure what exactly you mean? Is it about "satisfy" again?
>>
>> If the requested size is zero, the implementation could also leak the
>> memory, nothing prevents me from implementing such an Allocator.
> 
> Well, hopefully the documentation stating that `realloc` must be implemented
> this exact way prevents you from doing otherwise. :-)
> 
> Please let me know if I need to document this in a different way if it's not
> sufficient as it is.

It should be part of the safety requirements of the Allocator trait.

>>>>> +    ///
>>>>> +    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
>>>>> +    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
>>>>> +    ///
>>>>> +    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
>>>>> +    /// buffer; this is implementation specific to the allocator.
>>>>> +    ///
>>>>> +    /// On allocation failure, the existing buffer, if any, remains valid.
>>>>> +    ///
>>>>> +    /// The buffer is represented as `NonNull<[u8]>`.
>>>>> +    ///
>>>>> +    /// # Safety
>>>>> +    ///
>>>>> +    /// `ptr` must point to an existing and valid memory allocation created by this allocator
>>>>> +    /// instance of a size of at least `old_size`.
>>>>> +    ///
>>>>> +    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
>>>>> +    /// created.
>>>>> +    unsafe fn realloc(
>>>>> +        &self,
>>>>> +        ptr: *mut u8,
>>>>> +        old_size: usize,
>>>>
>>>> Why not request the old layout like the std Allocator's grow/shrink
>>>> functions do?
>>>
>>> Because we only care about the size that needs to be preserved when growing the
>>> buffer. The `alignment` field of `Layout` would be wasted.
>>
>> In the std Allocator they specified an old layout. This is probably
>> because of the following: if `Layout` is ever extended to hold another
>> property that would need to be updated, the signatures are already
>> correct.
>> In our case we could change it tree-wide, so I guess we could fix that
>> issue when it comes up.
> 
> Yes, I think so too.
> 
>>
>>>>> +        layout: Layout,
>>>>> +        flags: Flags,
>>>>> +    ) -> Result<NonNull<[u8]>, AllocError>;
>>>>> +
>>>>> +    /// Free an existing memory allocation.
>>>>> +    ///
>>>>> +    /// # Safety
>>>>> +    ///
>>>>> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
>>>>> +    /// instance.
>>>>> +    unsafe fn free(&self, ptr: *mut u8) {
>>>>
>>>> `ptr` should be `NonNull<u8>`.
>>>
>>> Creating a `NonNull` from a raw pointer is an extra operation for any user of
>>> `free` and given that all `free` functions in the kernel accept a NULL pointer,
>>> I think there is not much value in making this `NonNull`.
>>
>> I don't think that this argument holds for Rust though. For example,
>> `KBox` contains a `Unique` that contains a `NonNull`, so freeing could
>> just be done with `free(self.0.0)`.
> 
> Agreed, we can indeed make it a `&NonNull<u8>`. However, I find this a bit

I think you mean `NonNull<u8>`, right?

> inconsistent with the signature of `realloc`.
> 
> Should we go with separate `shrink` / `grow`, `free` could be implemented as
> shrinking to zero and allowing a NULL pointer makes not much sense.
> 
> But as mentioned, I'm not yet seeing the benefit of having `realloc` split into
> `grow` and `shrink`.

I would not split it into grow/shrink. I am not sure what exactly would
be best here, but here is what I am trying to achieve:
- people should strongly prefer alloc/free over realloc,
- calling realloc with zero size should not signify freeing the memory,
  but rather resizing the allocation to 0. E.g. because a buffer now
  decides to hold zero elements (in this case, the size should be a
  variable that just happens to be zero).
- calling realloc with a null pointer should not be necessary, since
  `alloc` exists.

This is to improve readability of code, or do you find

    realloc(ptr, 0, Layout::new::<()>(), Flags(0))

more readable than
    
    free(ptr)

>>>>> +        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
>>>>> +        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
>>>>> +        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };
>>>>
>>>> Why does the implementer have to guarantee this?
>>>
>>> Who else can guarantee this?
>>
>> Only the implementer yes. But they are not forced to do this i.e.
>> nothing in the safety requirements of `Allocator` prevents me from doing
>> a no-op on reallocating to a zero size.
> 
> Ah, I see now, this is the same as your comment on the documentation of
> `realloc`. So, this indeed just about missing a safety comment.
> 
>>
>>>>> +    }
>>>>> +}
>>>>> --
>>>>> 2.45.2
>>>>>
>>>>
>>>> More general questions:
>>>> - are there functions in the kernel to efficiently allocate zeroed
>>>>   memory? In that case, the Allocator trait should also have methods
>>>>   that do that (with a iterating default impl).
>>>
>>> We do this with GFP flags. In particular, you can pass GFP_ZERO to `alloc` and
>>> `realloc` to get zeroed memory. Hence, I think having dedicated functions that
>>> just do "flags | GFP_ZERO" would not add much value.
>>
>> Ah right, no in that case, we don't need it.
>>
>>>> - I am not sure putting everything into the single realloc function is a
>>>>   good idea, I like the grow/shrink methods of the std allocator. Is
>>>>   there a reason aside from concentrating the impl to go for only a
>>>>   single realloc function?
>>>
>>> Yes, `krealloc()` already provides exactly the described behaviour. See the
>>> implementation of `Kmalloc`.
>>
>> But `kvmalloc` does not and neither does `vmalloc`. I would prefer
>> multiple smaller functions over one big one in this case.
> 
> What I forsee is that:
> 
>   - `alloc` becomes a `grow` from zero.
>   - `free` becomes a `shrink` to zero.
>   - `grow` and `shrink` become a `realloc` alias,
>      because they're almost the same
> 
> Wouldn't this just put us were we already are, effectively?

We could have a NonNull parameter for realloc and discourage calling
realloc for freeing.

---
Cheers,
Benno

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Danilo Krummrich]

On Sat, Jul 06, 2024 at 05:08:26PM +0000, Benno Lossin wrote:
> On 06.07.24 17:11, Danilo Krummrich wrote:
> > On Sat, Jul 06, 2024 at 01:17:19PM +0000, Benno Lossin wrote:
> >> On 06.07.24 13:05, Danilo Krummrich wrote:
> >>> On Sat, Jul 06, 2024 at 10:33:49AM +0000, Benno Lossin wrote:
> >>>> Similarly, it might also be a good idea to let the implementer specify a
> >>>> custom error type.
> >>>
> >>> Same here, why?
> >>
> >> In this case the argument is weaker, but it could allow us to implement
> >> an allocator with `Error = Infallible`, to statically guarantee
> >> allocation (e.g. when using GFP_ATOMIC). But at the moment there is no
> >> user.
> > 
> > GFP_ATOMIC can fail, I guess you mean __GFP_NOFAIL.
> > 
> > Not really sure how this would work other than with separate `alloc_nofail` and
> > `realloc_nofail` functions?
> 
> You could have an Allocator that always enables __GFP_NOFAIL, so the
> error type could be Infallible. But this doesn't seem that useful at the
> moment, so keep the AllocError as is.
> 
> >>>>> +        // SAFETY: Passing a NULL pointer to `realloc` is valid by it's safety requirements and asks
> >>>>> +        // for a new memory allocation.
> >>>>> +        unsafe { self.realloc(ptr::null_mut(), 0, layout, flags) }
> >>>>> +    }
> >>>>> +
> >>>>> +    /// Re-allocate an existing memory allocation to satisfy the requested `layout`. If the
> >>>>> +    /// requested size is zero, `realloc` behaves equivalent to `free`.
> >>>>
> >>>> This is not guaranteed by the implementation.
> >>>
> >>> Not sure what exactly you mean? Is it about "satisfy" again?
> >>
> >> If the requested size is zero, the implementation could also leak the
> >> memory, nothing prevents me from implementing such an Allocator.
> > 
> > Well, hopefully the documentation stating that `realloc` must be implemented
> > this exact way prevents you from doing otherwise. :-)
> > 
> > Please let me know if I need to document this in a different way if it's not
> > sufficient as it is.
> 
> It should be part of the safety requirements of the Allocator trait.

Makes sense, gonna add it.

> 
> >>>>> +    ///
> >>>>> +    /// If the requested size is larger than `old_size`, a successful call to `realloc` guarantees
> >>>>> +    /// that the new or grown buffer has at least `Layout::size` bytes, but may also be larger.
> >>>>> +    ///
> >>>>> +    /// If the requested size is smaller than `old_size`, `realloc` may or may not shrink the
> >>>>> +    /// buffer; this is implementation specific to the allocator.
> >>>>> +    ///
> >>>>> +    /// On allocation failure, the existing buffer, if any, remains valid.
> >>>>> +    ///
> >>>>> +    /// The buffer is represented as `NonNull<[u8]>`.
> >>>>> +    ///
> >>>>> +    /// # Safety
> >>>>> +    ///
> >>>>> +    /// `ptr` must point to an existing and valid memory allocation created by this allocator
> >>>>> +    /// instance of a size of at least `old_size`.
> >>>>> +    ///
> >>>>> +    /// Additionally, `ptr` is allowed to be a NULL pointer; in this case a new memory allocation is
> >>>>> +    /// created.
> >>>>> +    unsafe fn realloc(
> >>>>> +        &self,
> >>>>> +        ptr: *mut u8,
> >>>>> +        old_size: usize,
> >>>>
> >>>> Why not request the old layout like the std Allocator's grow/shrink
> >>>> functions do?
> >>>
> >>> Because we only care about the size that needs to be preserved when growing the
> >>> buffer. The `alignment` field of `Layout` would be wasted.
> >>
> >> In the std Allocator they specified an old layout. This is probably
> >> because of the following: if `Layout` is ever extended to hold another
> >> property that would need to be updated, the signatures are already
> >> correct.
> >> In our case we could change it tree-wide, so I guess we could fix that
> >> issue when it comes up.
> > 
> > Yes, I think so too.
> > 
> >>
> >>>>> +        layout: Layout,
> >>>>> +        flags: Flags,
> >>>>> +    ) -> Result<NonNull<[u8]>, AllocError>;
> >>>>> +
> >>>>> +    /// Free an existing memory allocation.
> >>>>> +    ///
> >>>>> +    /// # Safety
> >>>>> +    ///
> >>>>> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
> >>>>> +    /// instance.
> >>>>> +    unsafe fn free(&self, ptr: *mut u8) {
> >>>>
> >>>> `ptr` should be `NonNull<u8>`.
> >>>
> >>> Creating a `NonNull` from a raw pointer is an extra operation for any user of
> >>> `free` and given that all `free` functions in the kernel accept a NULL pointer,
> >>> I think there is not much value in making this `NonNull`.
> >>
> >> I don't think that this argument holds for Rust though. For example,
> >> `KBox` contains a `Unique` that contains a `NonNull`, so freeing could
> >> just be done with `free(self.0.0)`.
> > 
> > Agreed, we can indeed make it a `&NonNull<u8>`. However, I find this a bit
> 
> I think you mean `NonNull<u8>`, right?

Yes, but I still don't see how that improves things, e.g. in `Drop` of
`KVec`:

`A::free(self.ptr.to_non_null().cast())`

vs.

`A::free(self.as_mut_ptr().cast())`

I'm not against this change, but I don't see how this makes things better.

> 
> > inconsistent with the signature of `realloc`.
> > 
> > Should we go with separate `shrink` / `grow`, `free` could be implemented as
> > shrinking to zero and allowing a NULL pointer makes not much sense.
> > 
> > But as mentioned, I'm not yet seeing the benefit of having `realloc` split into
> > `grow` and `shrink`.
> 
> I would not split it into grow/shrink. I am not sure what exactly would
> be best here, but here is what I am trying to achieve:
> - people should strongly prefer alloc/free over realloc,

I agree; the functions for that are there: `Allocator::alloc` and
`Allocator::free`.

`KBox` uses both of them, `KVec` instead, for obvious reasons, uses
`Allocator::realloc` directly to grow from zero and `Allocator::free`.

> - calling realloc with zero size should not signify freeing the memory,
>   but rather resizing the allocation to 0. E.g. because a buffer now
>   decides to hold zero elements (in this case, the size should be a
>   variable that just happens to be zero).

If a buffer is forced to a new size of zero, isn't that effectively a free?

At least that's exactly what the kernel does, if we ask krealloc() to resize to
zero it will free the memory and return ZERO_SIZE_PTR.

So, what exactly would you want `realloc` to do when a size of zero is passed
in?

> - calling realloc with a null pointer should not be necessary, since
>   `alloc` exists.

But `alloc` calls `realloc` with a NULL pointer to allocate new memory.

Let's take `Kmalloc` as example, surely I could implement `alloc` by calling
into kmalloc() instead. But then we'd have to implement `alloc` for all
allocators, instead of having a generic `alloc`.

And I wonder what's the point given that `realloc` with a NULL pointer already
does this naturally? Besides that, it comes in handy when we want to allocate
memory for data structures that grow from zero, such as `KVec`.

> 
> This is to improve readability of code, or do you find
> 
>     realloc(ptr, 0, Layout::new::<()>(), Flags(0))
> 
> more readable than
>     
>     free(ptr)

No, but that's not what users of allocators would do. They'd just call `free`,
as I do in `KBox` and `KVec`.

> 
> >>>>> +        // SAFETY: `ptr` is guaranteed to be previously allocated with this `Allocator` or NULL.
> >>>>> +        // Calling `realloc` with a buffer size of zero, frees the buffer `ptr` points to.
> >>>>> +        let _ = unsafe { self.realloc(ptr, 0, Layout::new::<()>(), Flags(0)) };
> >>>>
> >>>> Why does the implementer have to guarantee this?
> >>>
> >>> Who else can guarantee this?
> >>
> >> Only the implementer yes. But they are not forced to do this i.e.
> >> nothing in the safety requirements of `Allocator` prevents me from doing
> >> a no-op on reallocating to a zero size.
> > 
> > Ah, I see now, this is the same as your comment on the documentation of
> > `realloc`. So, this indeed just about missing a safety comment.
> > 
> >>
> >>>>> +    }
> >>>>> +}
> >>>>> --
> >>>>> 2.45.2
> >>>>>
> >>>>
> >>>> More general questions:
> >>>> - are there functions in the kernel to efficiently allocate zeroed
> >>>>   memory? In that case, the Allocator trait should also have methods
> >>>>   that do that (with a iterating default impl).
> >>>
> >>> We do this with GFP flags. In particular, you can pass GFP_ZERO to `alloc` and
> >>> `realloc` to get zeroed memory. Hence, I think having dedicated functions that
> >>> just do "flags | GFP_ZERO" would not add much value.
> >>
> >> Ah right, no in that case, we don't need it.
> >>
> >>>> - I am not sure putting everything into the single realloc function is a
> >>>>   good idea, I like the grow/shrink methods of the std allocator. Is
> >>>>   there a reason aside from concentrating the impl to go for only a
> >>>>   single realloc function?
> >>>
> >>> Yes, `krealloc()` already provides exactly the described behaviour. See the
> >>> implementation of `Kmalloc`.
> >>
> >> But `kvmalloc` does not and neither does `vmalloc`. I would prefer
> >> multiple smaller functions over one big one in this case.
> > 
> > What I forsee is that:
> > 
> >   - `alloc` becomes a `grow` from zero.
> >   - `free` becomes a `shrink` to zero.
> >   - `grow` and `shrink` become a `realloc` alias,
> >      because they're almost the same
> > 
> > Wouldn't this just put us were we already are, effectively?
> 
> We could have a NonNull parameter for realloc and discourage calling
> realloc for freeing.

But what does this get us, other than that we have to implement `alloc` and
`free` explicitly for every allocator?

Also, as mentioned above, `realloc` taking a NULL pointer for a new allocation
is useful for growing structures that start from zero, such as `KVec`.

> 
> ---
> Cheers,
> Benno
> 

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Benno Lossin]

On 06.07.24 20:47, Danilo Krummrich wrote:
> On Sat, Jul 06, 2024 at 05:08:26PM +0000, Benno Lossin wrote:
>> On 06.07.24 17:11, Danilo Krummrich wrote:
>>> On Sat, Jul 06, 2024 at 01:17:19PM +0000, Benno Lossin wrote:
>>>> On 06.07.24 13:05, Danilo Krummrich wrote:
>>>>>>> +        layout: Layout,
>>>>>>> +        flags: Flags,
>>>>>>> +    ) -> Result<NonNull<[u8]>, AllocError>;
>>>>>>> +
>>>>>>> +    /// Free an existing memory allocation.
>>>>>>> +    ///
>>>>>>> +    /// # Safety
>>>>>>> +    ///
>>>>>>> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
>>>>>>> +    /// instance.
>>>>>>> +    unsafe fn free(&self, ptr: *mut u8) {
>>>>>>
>>>>>> `ptr` should be `NonNull<u8>`.
>>>>>
>>>>> Creating a `NonNull` from a raw pointer is an extra operation for any user of
>>>>> `free` and given that all `free` functions in the kernel accept a NULL pointer,
>>>>> I think there is not much value in making this `NonNull`.
>>>>
>>>> I don't think that this argument holds for Rust though. For example,
>>>> `KBox` contains a `Unique` that contains a `NonNull`, so freeing could
>>>> just be done with `free(self.0.0)`.
>>>
>>> Agreed, we can indeed make it a `&NonNull<u8>`. However, I find this a bit
>>
>> I think you mean `NonNull<u8>`, right?
> 
> Yes, but I still don't see how that improves things, e.g. in `Drop` of
> `KVec`:
> 
> `A::free(self.ptr.to_non_null().cast())`
> 
> vs.
> 
> `A::free(self.as_mut_ptr().cast())`
> 
> I'm not against this change, but I don't see how this makes things better.

Ah you still need to convert the `Unique<T>` to a pointer...
But we could have a trait that allows that conversion. Additionally, we
could get rid of the cast if we made the function generic.

>>> inconsistent with the signature of `realloc`.
>>>
>>> Should we go with separate `shrink` / `grow`, `free` could be implemented as
>>> shrinking to zero and allowing a NULL pointer makes not much sense.
>>>
>>> But as mentioned, I'm not yet seeing the benefit of having `realloc` split into
>>> `grow` and `shrink`.
>>
>> I would not split it into grow/shrink. I am not sure what exactly would
>> be best here, but here is what I am trying to achieve:
>> - people should strongly prefer alloc/free over realloc,
> 
> I agree; the functions for that are there: `Allocator::alloc` and
> `Allocator::free`.
> 
> `KBox` uses both of them, `KVec` instead, for obvious reasons, uses
> `Allocator::realloc` directly to grow from zero and `Allocator::free`.
> 
>> - calling realloc with zero size should not signify freeing the memory,
>>   but rather resizing the allocation to 0. E.g. because a buffer now
>>   decides to hold zero elements (in this case, the size should be a
>>   variable that just happens to be zero).
> 
> If a buffer is forced to a new size of zero, isn't that effectively a free?

I would argue that they are different, since you get a pointer back that
points to an allocation of zero size. A vector of size zero still keeps
around a (dangling) pointer.
You also can free a zero sized allocation (it's a no-op), but you must
not free an allocation twice.

> At least that's exactly what the kernel does, if we ask krealloc() to resize to
> zero it will free the memory and return ZERO_SIZE_PTR.

Not every allocator behaves like krealloc, in your patch, both vmalloc
and kvmalloc are implemented with `if`s to check for the various special
cases.

> So, what exactly would you want `realloc` to do when a size of zero is passed
> in?

I don't want to change the behavior, I want to prevent people from using
it unnecessarily.

>> - calling realloc with a null pointer should not be necessary, since
>>   `alloc` exists.
> 
> But `alloc` calls `realloc` with a NULL pointer to allocate new memory.
> 
> Let's take `Kmalloc` as example, surely I could implement `alloc` by calling
> into kmalloc() instead. But then we'd have to implement `alloc` for all
> allocators, instead of having a generic `alloc`.

My intuition is telling me that I don't like that you can pass null to
realloc. I can't put my finger on exactly why that is, maybe because
there isn't actually any argument here or maybe there is. I'd like to
hear other people's opinion.

> And I wonder what's the point given that `realloc` with a NULL pointer already
> does this naturally? Besides that, it comes in handy when we want to allocate
> memory for data structures that grow from zero, such as `KVec`.

You can just `alloc` with size zero and then call `realloc` with the
pointer that you got. I don't see how this would be a problem.

>> This is to improve readability of code, or do you find
>>
>>     realloc(ptr, 0, Layout::new::<()>(), Flags(0))
>>
>> more readable than
>>
>>     free(ptr)
> 
> No, but that's not what users of allocators would do. They'd just call `free`,
> as I do in `KBox` and `KVec`.

I agree that we have to free the memory when supplying a zero size, but
I don't like adding additional features to `realloc`.

Conceptually, I see an allocator like this:

    pub trait Allocator {
        type Flags;
        type Allocation;
        type Error;
    
        fn alloc(layout: Layout, flags: Self::Flags) -> Result<Self::Allocation, Self::Error>;
    
        fn realloc(
            alloc: Self::Allocation,
            old: Layout,
            new: Layout,
            flags: Self::Flags,
        ) -> Result<Self::Allocation, (Self::Allocation, Self::Error)>;
    
        fn free(alloc: Self::Allocation);
    }

I.e. to reallocate something, you first have to have something
allocated.

For some reason if we use `Option<NonNull<u8>>` instead of `*mut u8`, I
have a better feeling, but that might be worse for ergonomics...

---
Cheers,
Benno

Re: [PATCH 01/20] rust: alloc: add `Allocator` trait

[Danilo Krummrich]

On Mon, Jul 08, 2024 at 08:12:34AM +0000, Benno Lossin wrote:
> On 06.07.24 20:47, Danilo Krummrich wrote:
> > On Sat, Jul 06, 2024 at 05:08:26PM +0000, Benno Lossin wrote:
> >> On 06.07.24 17:11, Danilo Krummrich wrote:
> >>> On Sat, Jul 06, 2024 at 01:17:19PM +0000, Benno Lossin wrote:
> >>>> On 06.07.24 13:05, Danilo Krummrich wrote:
> >>>>>>> +        layout: Layout,
> >>>>>>> +        flags: Flags,
> >>>>>>> +    ) -> Result<NonNull<[u8]>, AllocError>;
> >>>>>>> +
> >>>>>>> +    /// Free an existing memory allocation.
> >>>>>>> +    ///
> >>>>>>> +    /// # Safety
> >>>>>>> +    ///
> >>>>>>> +    /// `ptr` must point to an existing and valid memory allocation created by this `Allocator`
> >>>>>>> +    /// instance.
> >>>>>>> +    unsafe fn free(&self, ptr: *mut u8) {
> >>>>>>
> >>>>>> `ptr` should be `NonNull<u8>`.
> >>>>>
> >>>>> Creating a `NonNull` from a raw pointer is an extra operation for any user of
> >>>>> `free` and given that all `free` functions in the kernel accept a NULL pointer,
> >>>>> I think there is not much value in making this `NonNull`.
> >>>>
> >>>> I don't think that this argument holds for Rust though. For example,
> >>>> `KBox` contains a `Unique` that contains a `NonNull`, so freeing could
> >>>> just be done with `free(self.0.0)`.
> >>>
> >>> Agreed, we can indeed make it a `&NonNull<u8>`. However, I find this a bit
> >>
> >> I think you mean `NonNull<u8>`, right?
> > 
> > Yes, but I still don't see how that improves things, e.g. in `Drop` of
> > `KVec`:
> > 
> > `A::free(self.ptr.to_non_null().cast())`
> > 
> > vs.
> > 
> > `A::free(self.as_mut_ptr().cast())`
> > 
> > I'm not against this change, but I don't see how this makes things better.
> 
> Ah you still need to convert the `Unique<T>` to a pointer...
> But we could have a trait that allows that conversion. Additionally, we
> could get rid of the cast if we made the function generic.

I'm still not convinced of the `NonNull`, since technically it's not required,
but using a generic could indeed get us rid of all the `cast` calls - same for
`realloc` I guess.

> 
> >>> inconsistent with the signature of `realloc`.
> >>>
> >>> Should we go with separate `shrink` / `grow`, `free` could be implemented as
> >>> shrinking to zero and allowing a NULL pointer makes not much sense.
> >>>
> >>> But as mentioned, I'm not yet seeing the benefit of having `realloc` split into
> >>> `grow` and `shrink`.
> >>
> >> I would not split it into grow/shrink. I am not sure what exactly would
> >> be best here, but here is what I am trying to achieve:
> >> - people should strongly prefer alloc/free over realloc,
> > 
> > I agree; the functions for that are there: `Allocator::alloc` and
> > `Allocator::free`.
> > 
> > `KBox` uses both of them, `KVec` instead, for obvious reasons, uses
> > `Allocator::realloc` directly to grow from zero and `Allocator::free`.
> > 
> >> - calling realloc with zero size should not signify freeing the memory,
> >>   but rather resizing the allocation to 0. E.g. because a buffer now
> >>   decides to hold zero elements (in this case, the size should be a
> >>   variable that just happens to be zero).
> > 
> > If a buffer is forced to a new size of zero, isn't that effectively a free?
> 
> I would argue that they are different, since you get a pointer back that
> points to an allocation of zero size. A vector of size zero still keeps
> around a (dangling) pointer.
> You also can free a zero sized allocation (it's a no-op), but you must
> not free an allocation twice.

I don't think this is contradictive. For instance, if you call krealloc() with
a size of zero, it will free the existing allocation and return ZERO_SIZE_PTR,
which, effectively, can be seen as zero sized allocation. You can also pass
ZERO_SIZE_PTR to free(), but, of course, it doens't do anything, hence, as you
said, it's a no-op.

> 
> > At least that's exactly what the kernel does, if we ask krealloc() to resize to
> > zero it will free the memory and return ZERO_SIZE_PTR.
> 
> Not every allocator behaves like krealloc, in your patch, both vmalloc
> and kvmalloc are implemented with `if`s to check for the various special
> cases.

Well, for `Vmalloc` there simply is no vrealloc() on the C side...

For `KVmalloc` there is indeed a kvrealloc(), but it behaves different than
krealloc(), which seems inconsistant. Also note that kvrealloc() has a hand full
of users only.

My plan was to stick with the logic that krealloc() uses (because I think that's
what it should be) and, once we land this series, align kvrealloc() and get a
vrealloc() on the C side in place. We could do this in the scope of this series
as well, but I think this series is huge enough and separating this out makes
things much easier.

So, my goal would be that `Vmalloc` and `KVmalloc` look exactly like `Kmalloc`
looks right now in the end.

> 
> > So, what exactly would you want `realloc` to do when a size of zero is passed
> > in?
> 
> I don't want to change the behavior, I want to prevent people from using
> it unnecessarily.

I'm not overly worried about this. In fact, the C side proves that krealloc()
isn't really prone to be used where kmalloc() or free() can be used instead. And
sometimes it makes sense, `KVec` is a good example for that.

Besides that, who do we expect to use this API? In Rust most use cases should be
covered by `KBox` and `KVec` anyways. I don't expect much direct users of this
API.

> 
> >> - calling realloc with a null pointer should not be necessary, since
> >>   `alloc` exists.
> > 
> > But `alloc` calls `realloc` with a NULL pointer to allocate new memory.
> > 
> > Let's take `Kmalloc` as example, surely I could implement `alloc` by calling
> > into kmalloc() instead. But then we'd have to implement `alloc` for all
> > allocators, instead of having a generic `alloc`.
> 
> My intuition is telling me that I don't like that you can pass null to
> realloc. I can't put my finger on exactly why that is, maybe because
> there isn't actually any argument here or maybe there is. I'd like to
> hear other people's opinion.
> 
> > And I wonder what's the point given that `realloc` with a NULL pointer already
> > does this naturally? Besides that, it comes in handy when we want to allocate
> > memory for data structures that grow from zero, such as `KVec`.
> 
> You can just `alloc` with size zero and then call `realloc` with the
> pointer that you got. I don't see how this would be a problem.

In contrast to that, I don't see why calling two functions where just one would
be sufficient makes anything better.

> 
> >> This is to improve readability of code, or do you find
> >>
> >>     realloc(ptr, 0, Layout::new::<()>(), Flags(0))
> >>
> >> more readable than
> >>
> >>     free(ptr)
> > 
> > No, but that's not what users of allocators would do. They'd just call `free`,
> > as I do in `KBox` and `KVec`.
> 
> I agree that we have to free the memory when supplying a zero size, but
> I don't like adding additional features to `realloc`.

So, if you agree that we have to free the memory when supplying a zero size, why
would it be an additional feature then?

Besides that, as mentioned above, krealloc() already does that and kvrealloc()
should be fixed to be consistent with that.

> 
> Conceptually, I see an allocator like this:
> 
>     pub trait Allocator {
>         type Flags;

Agreed.

>         type Allocation;

What do we need this for?

I already thought about having some kind of `Allocation` type, also with a
drop() trait freeing the memory etc. But, I came to the conclusion that this is
likely to be overkill. We have `KBox` and `KVec` to take care of managing their
memory.

>         type Error;

I'm not worried about adding this, but maybe it makes sense to wait until we
actually implement somthing that needs this.

>     
>         fn alloc(layout: Layout, flags: Self::Flags) -> Result<Self::Allocation, Self::Error>;
>     
>         fn realloc(
>             alloc: Self::Allocation,
>             old: Layout,

We only really care about the size here. `Alignment` would be wasted. Are we
keen taking this downside for a bit more consistency?

>             new: Layout,
>             flags: Self::Flags,
>         ) -> Result<Self::Allocation, (Self::Allocation, Self::Error)>;
>     
>         fn free(alloc: Self::Allocation);
>     }
> 
> I.e. to reallocate something, you first have to have something
> allocated.

See the discussion above for this point.

> 
> For some reason if we use `Option<NonNull<u8>>` instead of `*mut u8`, I
> have a better feeling, but that might be worse for ergonomics...

As argument for `realloc`?

I get your point here. And for any other API I'd probably agree instantly.

Generally, `Allocator` is a bit special to me. It's not supposed to be used by a
lot of users, other than types like `KBox` or `KVec`, that are supposed to
manage the memory and the interface is pretty unsafe by definition. To me
keeping a rather "raw" access to krealloc() and friends seems to be desirable
here.

> 
> ---
> Cheers,
> Benno
> 

[PATCH 02/20] rust: alloc: separate `aligned_size` from `krealloc_aligned`

[Danilo Krummrich]

Separate `aligned_size` from `krealloc_aligned`.

Subsequent patches implement `Allocator` derivates, such as `Kmalloc`,
that require `aligned_size` and replace the original `krealloc_aligned`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc/allocator.rs | 26 ++++++++++++++++++--------
 1 file changed, 18 insertions(+), 8 deletions(-)

diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs
index 229642960cd1..49fb33cc18d9 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -8,13 +8,7 @@
 
 struct KernelAllocator;
 
-/// Calls `krealloc` with a proper size to alloc a new object aligned to `new_layout`'s alignment.
-///
-/// # Safety
-///
-/// - `ptr` can be either null or a pointer which has been allocated by this allocator.
-/// - `new_layout` must have a non-zero size.
-pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: Flags) -> *mut u8 {
+fn aligned_size(new_layout: Layout) -> usize {
     // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first.
     let layout = new_layout.pad_to_align();
 
@@ -30,12 +24,28 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
         size = size.next_power_of_two();
     }
 
+    size
+}
+
+/// Calls `krealloc` with a proper size to alloc a new object aligned to `new_layout`'s alignment.
+///
+/// # Safety
+///
+/// - `ptr` can be either null or a pointer which has been allocated by this allocator.
+/// - `new_layout` must have a non-zero size.
+pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: Flags) -> *mut u8 {
     // SAFETY:
     // - `ptr` is either null or a pointer returned from a previous `k{re}alloc()` by the
     //   function safety requirement.
     // - `size` is greater than 0 since it's either a `layout.size()` (which cannot be zero
     //   according to the function safety requirement) or a result from `next_power_of_two()`.
-    unsafe { bindings::krealloc(ptr as *const core::ffi::c_void, size, flags.0) as *mut u8 }
+    unsafe {
+        bindings::krealloc(
+            ptr as *const core::ffi::c_void,
+            aligned_size(new_layout),
+            flags.0,
+        ) as *mut u8
+    }
 }
 
 unsafe impl GlobalAlloc for KernelAllocator {
-- 
2.45.2

[PATCH 03/20] rust: alloc: rename `KernelAllocator` to `Kmalloc`

[Danilo Krummrich]

Subsequent patches implement `Vmalloc` and `KVmalloc` allocators, hence
align `KernelAllocator` to this naming scheme.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc/allocator.rs | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs
index 49fb33cc18d9..e47ab8fe21ab 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -6,7 +6,7 @@
 use core::alloc::{GlobalAlloc, Layout};
 use core::ptr;
 
-struct KernelAllocator;
+struct Kmalloc;
 
 fn aligned_size(new_layout: Layout) -> usize {
     // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first.
@@ -48,7 +48,7 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
     }
 }
 
-unsafe impl GlobalAlloc for KernelAllocator {
+unsafe impl GlobalAlloc for Kmalloc {
     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
         // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety
         // requirement.
@@ -84,7 +84,7 @@ unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
 }
 
 #[global_allocator]
-static ALLOCATOR: KernelAllocator = KernelAllocator;
+static ALLOCATOR: Kmalloc = Kmalloc;
 
 // See <https://github.com/rust-lang/rust/pull/86844>.
 #[no_mangle]
-- 
2.45.2

[PATCH 04/20] rust: alloc: implement `Allocator` for `Kmalloc`

[Danilo Krummrich]

Implement `Allocator` for `Kmalloc`, the kernel's default allocator,
typically used for objects smaller than page size.

All memory allocations made with `Kmalloc` end up in `krealloc()`.

It serves as the default allocator for the subsequently introduced types
`KBox` and `KVec`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs           |  2 +-
 rust/kernel/alloc/allocator.rs | 74 ++++++++++++++++++++++++++++------
 2 files changed, 63 insertions(+), 13 deletions(-)

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 462e00982510..8d79cc95dc1e 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -4,7 +4,7 @@
 
 #[cfg(not(test))]
 #[cfg(not(testlib))]
-mod allocator;
+pub mod allocator;
 pub mod box_ext;
 pub mod vec_ext;
 
diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs
index e47ab8fe21ab..b7c0490f6415 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -5,9 +5,18 @@
 use super::{flags::*, Flags};
 use core::alloc::{GlobalAlloc, Layout};
 use core::ptr;
+use core::ptr::NonNull;
 
-struct Kmalloc;
+use crate::alloc::{AllocError, Allocator};
+use crate::bindings;
 
+/// The contiguous kernel allocator.
+///
+/// The contiguous kernel allocator only ever allocates physically contiguous memory through
+/// `bindings::krealloc`.
+pub struct Kmalloc;
+
+/// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment.
 fn aligned_size(new_layout: Layout) -> usize {
     // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first.
     let layout = new_layout.pad_to_align();
@@ -27,7 +36,7 @@ fn aligned_size(new_layout: Layout) -> usize {
     size
 }
 
-/// Calls `krealloc` with a proper size to alloc a new object aligned to `new_layout`'s alignment.
+/// Calls `krealloc` with a proper size to alloc a new object.
 ///
 /// # Safety
 ///
@@ -48,20 +57,54 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
     }
 }
 
+unsafe impl Allocator for Kmalloc {
+    unsafe fn realloc(
+        &self,
+        old_ptr: *mut u8,
+        _old_size: usize,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let size = aligned_size(layout);
+
+        // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
+        // `old_size`, which was previously allocated with this `Allocator` or NULL.
+        let raw_ptr = unsafe {
+            // If `size == 0` and `old_ptr != NULL` `krealloc()` frees the memory behind the
+            // pointer.
+            bindings::krealloc(old_ptr.cast(), size, flags.0).cast()
+        };
+
+        let ptr = if size == 0 {
+            NonNull::dangling()
+        } else {
+            NonNull::new(raw_ptr).ok_or(AllocError)?
+        };
+
+        Ok(NonNull::slice_from_raw_parts(ptr, size))
+    }
+}
+
 unsafe impl GlobalAlloc for Kmalloc {
     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
-        // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety
-        // requirement.
-        unsafe { krealloc_aligned(ptr::null_mut(), layout, GFP_KERNEL) }
+        let this: &dyn Allocator = self;
+
+        match this.alloc(layout, GFP_KERNEL) {
+            Ok(ptr) => ptr.as_ptr().cast(),
+            Err(_) => ptr::null_mut(),
+        }
     }
 
     unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
-        unsafe {
-            bindings::kfree(ptr as *const core::ffi::c_void);
-        }
+        // SAFETY: The safety requirements of `dealloc` are a superset of the ones of
+        // `Allocator::free`.
+        unsafe { self.free(ptr) }
     }
 
     unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        let this: &dyn Allocator = self;
+        let old_size = layout.size();
+
         // SAFETY:
         // - `new_size`, when rounded up to the nearest multiple of `layout.align()`, will not
         //   overflow `isize` by the function safety requirement.
@@ -73,13 +116,20 @@ unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut
         //   requirement.
         // - the size of `layout` is not zero because `new_size` is not zero by the function safety
         //   requirement.
-        unsafe { krealloc_aligned(ptr, layout, GFP_KERNEL) }
+        // - `old_size` represents the memory that needs to be preserved.
+        match unsafe { this.realloc(ptr, old_size, layout, GFP_KERNEL) } {
+            Ok(ptr) => ptr.as_ptr().cast(),
+            Err(_) => ptr::null_mut(),
+        }
     }
 
     unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
-        // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety
-        // requirement.
-        unsafe { krealloc_aligned(ptr::null_mut(), layout, GFP_KERNEL | __GFP_ZERO) }
+        let this: &dyn Allocator = self;
+
+        match this.alloc(layout, GFP_KERNEL | __GFP_ZERO) {
+            Ok(ptr) => ptr.as_ptr().cast(),
+            Err(_) => ptr::null_mut(),
+        }
     }
 }
 
-- 
2.45.2

Re: [PATCH 04/20] rust: alloc: implement `Allocator` for `Kmalloc`

[Benno Lossin]

On 04.07.24 19:06, Danilo Krummrich wrote:
> @@ -48,20 +57,54 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
>      }
>  }
> 
> +unsafe impl Allocator for Kmalloc {
> +    unsafe fn realloc(
> +        &self,
> +        old_ptr: *mut u8,
> +        _old_size: usize,
> +        layout: Layout,
> +        flags: Flags,
> +    ) -> Result<NonNull<[u8]>, AllocError> {
> +        let size = aligned_size(layout);
> +
> +        // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> +        // `old_size`, which was previously allocated with this `Allocator` or NULL.
> +        let raw_ptr = unsafe {
> +            // If `size == 0` and `old_ptr != NULL` `krealloc()` frees the memory behind the
> +            // pointer.
> +            bindings::krealloc(old_ptr.cast(), size, flags.0).cast()
> +        };
> +
> +        let ptr = if size == 0 {
> +            NonNull::dangling()
> +        } else {
> +            NonNull::new(raw_ptr).ok_or(AllocError)?
> +        };
> +
> +        Ok(NonNull::slice_from_raw_parts(ptr, size))
> +    }
> +}
> +
>  unsafe impl GlobalAlloc for Kmalloc {

Since you remove `alloc` entirely at the end of this series, do we even
need this?
If not, it would be best to just leave the implementation as-is until a
patch removes it entirely.

---
Cheers,
Benno

>      unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
> -        // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety
> -        // requirement.
> -        unsafe { krealloc_aligned(ptr::null_mut(), layout, GFP_KERNEL) }
> +        let this: &dyn Allocator = self;
> +
> +        match this.alloc(layout, GFP_KERNEL) {
> +            Ok(ptr) => ptr.as_ptr().cast(),
> +            Err(_) => ptr::null_mut(),
> +        }
>      }

Re: [PATCH 04/20] rust: alloc: implement `Allocator` for `Kmalloc`

[Danilo Krummrich]

On Sat, Jul 06, 2024 at 10:37:00AM +0000, Benno Lossin wrote:
> On 04.07.24 19:06, Danilo Krummrich wrote:
> > @@ -48,20 +57,54 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
> >      }
> >  }
> > 
> > +unsafe impl Allocator for Kmalloc {
> > +    unsafe fn realloc(
> > +        &self,
> > +        old_ptr: *mut u8,
> > +        _old_size: usize,
> > +        layout: Layout,
> > +        flags: Flags,
> > +    ) -> Result<NonNull<[u8]>, AllocError> {
> > +        let size = aligned_size(layout);
> > +
> > +        // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> > +        // `old_size`, which was previously allocated with this `Allocator` or NULL.
> > +        let raw_ptr = unsafe {
> > +            // If `size == 0` and `old_ptr != NULL` `krealloc()` frees the memory behind the
> > +            // pointer.
> > +            bindings::krealloc(old_ptr.cast(), size, flags.0).cast()
> > +        };
> > +
> > +        let ptr = if size == 0 {
> > +            NonNull::dangling()
> > +        } else {
> > +            NonNull::new(raw_ptr).ok_or(AllocError)?
> > +        };
> > +
> > +        Ok(NonNull::slice_from_raw_parts(ptr, size))
> > +    }
> > +}
> > +
> >  unsafe impl GlobalAlloc for Kmalloc {
> 
> Since you remove `alloc` entirely at the end of this series, do we even
> need this?
> If not, it would be best to just leave the implementation as-is until a
> patch removes it entirely.

I may have done this to not break the rusttest target, but I think with what I
ended up with, this shouldn't be required anymore and can be removed in a single
patch at the end of the series.

> 
> ---
> Cheers,
> Benno
> 
> >      unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
> > -        // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety
> > -        // requirement.
> > -        unsafe { krealloc_aligned(ptr::null_mut(), layout, GFP_KERNEL) }
> > +        let this: &dyn Allocator = self;
> > +
> > +        match this.alloc(layout, GFP_KERNEL) {
> > +            Ok(ptr) => ptr.as_ptr().cast(),
> > +            Err(_) => ptr::null_mut(),
> > +        }
> >      }
> 

[PATCH 05/20] rust: alloc: add module `allocator_test`

[Danilo Krummrich]

`Allocator`s, such as `Kmalloc`, will be used by e.g. `KBox` and `KVec`
in subsequent patches, and hence this dependency propagates throughout
the whole kernel.

Add the `allocator_test` module that provides an empty implementation
for all `Allocator`s in the kernel, such that we don't break the
`rusttest` make target in subsequent patches.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs                |  9 +++++++--
 rust/kernel/alloc/allocator_test.rs | 21 +++++++++++++++++++++
 2 files changed, 28 insertions(+), 2 deletions(-)
 create mode 100644 rust/kernel/alloc/allocator_test.rs

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 8d79cc95dc1e..46ebdd059c92 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -2,12 +2,17 @@
 
 //! Extensions to the [`alloc`] crate.
 
-#[cfg(not(test))]
-#[cfg(not(testlib))]
+#[cfg(not(any(test, testlib)))]
 pub mod allocator;
 pub mod box_ext;
 pub mod vec_ext;
 
+#[cfg(any(test, testlib))]
+pub mod allocator_test;
+
+#[cfg(any(test, testlib))]
+pub use self::allocator_test as allocator;
+
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub struct AllocError;
diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs
new file mode 100644
index 000000000000..3a0abe65491d
--- /dev/null
+++ b/rust/kernel/alloc/allocator_test.rs
@@ -0,0 +1,21 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#![allow(missing_docs)]
+
+use super::{AllocError, Allocator, Flags};
+use core::alloc::Layout;
+use core::ptr::NonNull;
+
+pub struct Kmalloc;
+
+unsafe impl Allocator for Kmalloc {
+    unsafe fn realloc(
+        &self,
+        _old_ptr: *mut u8,
+        _old_size: usize,
+        _layout: Layout,
+        _flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        panic!();
+    }
+}
-- 
2.45.2

[PATCH 06/20] rust: alloc: remove `krealloc_aligned`

[Danilo Krummrich]

Now that we have `Allocator` for `Kmalloc` in place, remove explicit
calls to `krealloc_aligned` and get rid of `krealloc_aligned` itself.

`bindings::krealloc` should only be called from `Kmalloc::realloc`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc/allocator.rs | 21 ---------------------
 rust/kernel/alloc/box_ext.rs   | 13 ++++---------
 rust/kernel/alloc/vec_ext.rs   | 23 +++++++++++++----------
 3 files changed, 17 insertions(+), 40 deletions(-)

diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs
index b7c0490f6415..1860cb79b875 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -36,27 +36,6 @@ fn aligned_size(new_layout: Layout) -> usize {
     size
 }
 
-/// Calls `krealloc` with a proper size to alloc a new object.
-///
-/// # Safety
-///
-/// - `ptr` can be either null or a pointer which has been allocated by this allocator.
-/// - `new_layout` must have a non-zero size.
-pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: Flags) -> *mut u8 {
-    // SAFETY:
-    // - `ptr` is either null or a pointer returned from a previous `k{re}alloc()` by the
-    //   function safety requirement.
-    // - `size` is greater than 0 since it's either a `layout.size()` (which cannot be zero
-    //   according to the function safety requirement) or a result from `next_power_of_two()`.
-    unsafe {
-        bindings::krealloc(
-            ptr as *const core::ffi::c_void,
-            aligned_size(new_layout),
-            flags.0,
-        ) as *mut u8
-    }
-}
-
 unsafe impl Allocator for Kmalloc {
     unsafe fn realloc(
         &self,
diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs
index 829cb1c1cf9e..1aeae02c147e 100644
--- a/rust/kernel/alloc/box_ext.rs
+++ b/rust/kernel/alloc/box_ext.rs
@@ -33,24 +33,19 @@ fn new_uninit(_flags: Flags) -> Result<Box<MaybeUninit<T>>, AllocError> {
     #[cfg(not(any(test, testlib)))]
     fn new_uninit(flags: Flags) -> Result<Box<MaybeUninit<T>>, AllocError> {
         let ptr = if core::mem::size_of::<MaybeUninit<T>>() == 0 {
-            core::ptr::NonNull::<_>::dangling().as_ptr()
+            core::ptr::NonNull::dangling()
         } else {
+            let alloc: &dyn super::Allocator = &super::allocator::Kmalloc;
             let layout = core::alloc::Layout::new::<MaybeUninit<T>>();
 
             // SAFETY: Memory is being allocated (first arg is null). The only other source of
             // safety issues is sleeping on atomic context, which is addressed by klint. Lastly,
             // the type is not a SZT (checked above).
-            let ptr =
-                unsafe { super::allocator::krealloc_aligned(core::ptr::null_mut(), layout, flags) };
-            if ptr.is_null() {
-                return Err(AllocError);
-            }
-
-            ptr.cast::<MaybeUninit<T>>()
+            alloc.alloc(layout, flags)?.cast()
         };
 
         // SAFETY: For non-zero-sized types, we allocate above using the global allocator. For
         // zero-sized types, we use `NonNull::dangling`.
-        Ok(unsafe { Box::from_raw(ptr) })
+        Ok(unsafe { Box::from_raw(ptr.as_ptr()) })
     }
 }
diff --git a/rust/kernel/alloc/vec_ext.rs b/rust/kernel/alloc/vec_ext.rs
index e9a81052728a..bf277976ed38 100644
--- a/rust/kernel/alloc/vec_ext.rs
+++ b/rust/kernel/alloc/vec_ext.rs
@@ -118,6 +118,7 @@ fn reserve(&mut self, additional: usize, _flags: Flags) -> Result<(), AllocError
 
     #[cfg(not(any(test, testlib)))]
     fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {
+        let alloc: &dyn super::Allocator = &super::allocator::Kmalloc;
         let len = self.len();
         let cap = self.capacity();
 
@@ -145,16 +146,18 @@ fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError>
 
         // SAFETY: `ptr` is valid because it's either NULL or comes from a previous call to
         // `krealloc_aligned`. We also verified that the type is not a ZST.
-        let new_ptr = unsafe { super::allocator::krealloc_aligned(ptr.cast(), layout, flags) };
-        if new_ptr.is_null() {
-            // SAFETY: We are just rebuilding the existing `Vec` with no changes.
-            unsafe { rebuild(self, old_ptr, len, cap) };
-            Err(AllocError)
-        } else {
-            // SAFETY: `ptr` has been reallocated with the layout for `new_cap` elements. New cap
-            // is greater than `cap`, so it continues to be >= `len`.
-            unsafe { rebuild(self, new_ptr.cast::<T>(), len, new_cap) };
-            Ok(())
+        match unsafe { alloc.realloc(ptr.cast(), cap, layout, flags) } {
+            Ok(ptr) => {
+                // SAFETY: `ptr` has been reallocated with the layout for `new_cap` elements.
+                // `new_cap` is greater than `cap`, so it continues to be >= `len`.
+                unsafe { rebuild(self, ptr.as_ptr().cast(), len, new_cap) };
+                Ok(())
+            }
+            Err(err) => {
+                // SAFETY: We are just rebuilding the existing `Vec` with no changes.
+                unsafe { rebuild(self, old_ptr, len, cap) };
+                Err(err)
+            }
         }
     }
 }
-- 
2.45.2

[PATCH 07/20] rust: alloc: implement `Vmalloc` allocator

[Danilo Krummrich]

Implement `Allocator` for `Vmalloc`, the kernel's virtually contiguous
allocator, typically used for larger objects, (much) larger than page
size.

All memory allocations made with `Vmalloc` end up in
`__vmalloc_noprof()`; all frees in `vfree()`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/bindings/bindings_helper.h     |  1 +
 rust/kernel/alloc/allocator.rs      | 55 +++++++++++++++++++++++++++++
 rust/kernel/alloc/allocator_test.rs |  1 +
 3 files changed, 57 insertions(+)

diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
index ddb5644d4fd9..f10518045c16 100644
--- a/rust/bindings/bindings_helper.h
+++ b/rust/bindings/bindings_helper.h
@@ -15,6 +15,7 @@
 #include <linux/refcount.h>
 #include <linux/sched.h>
 #include <linux/slab.h>
+#include <linux/vmalloc.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
 
diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs
index 1860cb79b875..0a4f27c5c3a6 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -16,6 +16,12 @@
 /// `bindings::krealloc`.
 pub struct Kmalloc;
 
+/// The virtually contiguous kernel allocator.
+///
+/// The vmalloc allocator allocates pages from the page level allocator and maps them into the
+/// contiguous kernel virtual space.
+pub struct Vmalloc;
+
 /// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment.
 fn aligned_size(new_layout: Layout) -> usize {
     // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first.
@@ -112,6 +118,55 @@ unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
     }
 }
 
+unsafe impl Allocator for Vmalloc {
+    unsafe fn realloc(
+        &self,
+        src: *mut u8,
+        old_size: usize,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let mut size = aligned_size(layout);
+
+        let dst = if size == 0 {
+            // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or NULL.
+            unsafe { bindings::vfree(src.cast()) };
+            NonNull::dangling()
+        } else if size <= old_size {
+            size = old_size;
+            NonNull::new(src).ok_or(AllocError)?
+        } else {
+            // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
+            // `old_size`, which was previously allocated with this `Allocator` or NULL.
+            let dst = unsafe { bindings::__vmalloc_noprof(size as u64, flags.0) };
+
+            // Validate that we actually allocated the requested memory.
+            let dst = NonNull::new(dst.cast()).ok_or(AllocError)?;
+
+            if !src.is_null() {
+                // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
+                // `old_size`; `dst` is guaranteed to point to valid memory with a size of at least
+                // `size`.
+                unsafe {
+                    core::ptr::copy_nonoverlapping(
+                        src,
+                        dst.as_ptr(),
+                        core::cmp::min(old_size, size),
+                    )
+                };
+
+                // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or
+                // NULL.
+                unsafe { bindings::vfree(src.cast()) }
+            }
+
+            dst
+        };
+
+        Ok(NonNull::slice_from_raw_parts(dst, size))
+    }
+}
+
 #[global_allocator]
 static ALLOCATOR: Kmalloc = Kmalloc;
 
diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs
index 3a0abe65491d..b2d7db492ba6 100644
--- a/rust/kernel/alloc/allocator_test.rs
+++ b/rust/kernel/alloc/allocator_test.rs
@@ -7,6 +7,7 @@
 use core::ptr::NonNull;
 
 pub struct Kmalloc;
+pub type Vmalloc = Kmalloc;
 
 unsafe impl Allocator for Kmalloc {
     unsafe fn realloc(
-- 
2.45.2

Re: [PATCH 07/20] rust: alloc: implement `Vmalloc` allocator

[Benno Lossin]

On 04.07.24 19:06, Danilo Krummrich wrote:
> @@ -112,6 +118,55 @@ unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
>      }
>  }
> 
> +unsafe impl Allocator for Vmalloc {
> +    unsafe fn realloc(
> +        &self,
> +        src: *mut u8,
> +        old_size: usize,
> +        layout: Layout,
> +        flags: Flags,
> +    ) -> Result<NonNull<[u8]>, AllocError> {
> +        let mut size = aligned_size(layout);
> +
> +        let dst = if size == 0 {
> +            // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or NULL.
> +            unsafe { bindings::vfree(src.cast()) };
> +            NonNull::dangling()
> +        } else if size <= old_size {
> +            size = old_size;
> +            NonNull::new(src).ok_or(AllocError)?
> +        } else {
> +            // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> +            // `old_size`, which was previously allocated with this `Allocator` or NULL.
> +            let dst = unsafe { bindings::__vmalloc_noprof(size as u64, flags.0) };
> +
> +            // Validate that we actually allocated the requested memory.
> +            let dst = NonNull::new(dst.cast()).ok_or(AllocError)?;
> +
> +            if !src.is_null() {
> +                // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> +                // `old_size`; `dst` is guaranteed to point to valid memory with a size of at least
> +                // `size`.
> +                unsafe {
> +                    core::ptr::copy_nonoverlapping(
> +                        src,
> +                        dst.as_ptr(),
> +                        core::cmp::min(old_size, size),
> +                    )
> +                };
> +
> +                // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or
> +                // NULL.
> +                unsafe { bindings::vfree(src.cast()) }
> +            }
> +
> +            dst
> +        };

If we had not a single realloc, but shrink/grow/free/alloc, then we
would not need these checks here, I personally would prefer that, what
do you guys think? 

---
Cheers,
Benno

> +
> +        Ok(NonNull::slice_from_raw_parts(dst, size))
> +    }
> +}
> +
>  #[global_allocator]
>  static ALLOCATOR: Kmalloc = Kmalloc;
> 
> diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs
> index 3a0abe65491d..b2d7db492ba6 100644
> --- a/rust/kernel/alloc/allocator_test.rs
> +++ b/rust/kernel/alloc/allocator_test.rs
> @@ -7,6 +7,7 @@
>  use core::ptr::NonNull;
> 
>  pub struct Kmalloc;
> +pub type Vmalloc = Kmalloc;
> 
>  unsafe impl Allocator for Kmalloc {
>      unsafe fn realloc(
> --
> 2.45.2
> 

Re: [PATCH 07/20] rust: alloc: implement `Vmalloc` allocator

[Danilo Krummrich]

On Sat, Jul 06, 2024 at 10:41:28AM +0000, Benno Lossin wrote:
> On 04.07.24 19:06, Danilo Krummrich wrote:
> > @@ -112,6 +118,55 @@ unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
> >      }
> >  }
> > 
> > +unsafe impl Allocator for Vmalloc {
> > +    unsafe fn realloc(
> > +        &self,
> > +        src: *mut u8,
> > +        old_size: usize,
> > +        layout: Layout,
> > +        flags: Flags,
> > +    ) -> Result<NonNull<[u8]>, AllocError> {
> > +        let mut size = aligned_size(layout);
> > +
> > +        let dst = if size == 0 {
> > +            // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or NULL.
> > +            unsafe { bindings::vfree(src.cast()) };
> > +            NonNull::dangling()
> > +        } else if size <= old_size {
> > +            size = old_size;
> > +            NonNull::new(src).ok_or(AllocError)?
> > +        } else {
> > +            // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> > +            // `old_size`, which was previously allocated with this `Allocator` or NULL.
> > +            let dst = unsafe { bindings::__vmalloc_noprof(size as u64, flags.0) };
> > +
> > +            // Validate that we actually allocated the requested memory.
> > +            let dst = NonNull::new(dst.cast()).ok_or(AllocError)?;
> > +
> > +            if !src.is_null() {
> > +                // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> > +                // `old_size`; `dst` is guaranteed to point to valid memory with a size of at least
> > +                // `size`.
> > +                unsafe {
> > +                    core::ptr::copy_nonoverlapping(
> > +                        src,
> > +                        dst.as_ptr(),
> > +                        core::cmp::min(old_size, size),
> > +                    )
> > +                };
> > +
> > +                // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or
> > +                // NULL.
> > +                unsafe { bindings::vfree(src.cast()) }
> > +            }
> > +
> > +            dst
> > +        };
> 
> If we had not a single realloc, but shrink/grow/free/alloc, then we
> would not need these checks here, I personally would prefer that, what
> do you guys think? 

Yeah, but look at `Kmalloc`, you'd have these checks in `Kmalloc`'s shrink/grow
functions instead, since `krealloc()` already behaves this way.

Personally, I don't see much value in `shrink` and `grow`. I think
implementations end up calling into some `realloc` with either `new < old` or
`new > old` anyway.

> 
> ---
> Cheers,
> Benno
> 
> > +
> > +        Ok(NonNull::slice_from_raw_parts(dst, size))
> > +    }
> > +}
> > +
> >  #[global_allocator]
> >  static ALLOCATOR: Kmalloc = Kmalloc;
> > 
> > diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs
> > index 3a0abe65491d..b2d7db492ba6 100644
> > --- a/rust/kernel/alloc/allocator_test.rs
> > +++ b/rust/kernel/alloc/allocator_test.rs
> > @@ -7,6 +7,7 @@
> >  use core::ptr::NonNull;
> > 
> >  pub struct Kmalloc;
> > +pub type Vmalloc = Kmalloc;
> > 
> >  unsafe impl Allocator for Kmalloc {
> >      unsafe fn realloc(
> > --
> > 2.45.2
> > 
> 

Re: [PATCH 07/20] rust: alloc: implement `Vmalloc` allocator

[Benno Lossin]

On 06.07.24 13:13, Danilo Krummrich wrote:
> On Sat, Jul 06, 2024 at 10:41:28AM +0000, Benno Lossin wrote:
>> On 04.07.24 19:06, Danilo Krummrich wrote:
>>> @@ -112,6 +118,55 @@ unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
>>>      }
>>>  }
>>>
>>> +unsafe impl Allocator for Vmalloc {
>>> +    unsafe fn realloc(
>>> +        &self,
>>> +        src: *mut u8,
>>> +        old_size: usize,
>>> +        layout: Layout,
>>> +        flags: Flags,
>>> +    ) -> Result<NonNull<[u8]>, AllocError> {
>>> +        let mut size = aligned_size(layout);
>>> +
>>> +        let dst = if size == 0 {
>>> +            // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or NULL.
>>> +            unsafe { bindings::vfree(src.cast()) };
>>> +            NonNull::dangling()
>>> +        } else if size <= old_size {
>>> +            size = old_size;
>>> +            NonNull::new(src).ok_or(AllocError)?
>>> +        } else {
>>> +            // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
>>> +            // `old_size`, which was previously allocated with this `Allocator` or NULL.
>>> +            let dst = unsafe { bindings::__vmalloc_noprof(size as u64, flags.0) };
>>> +
>>> +            // Validate that we actually allocated the requested memory.
>>> +            let dst = NonNull::new(dst.cast()).ok_or(AllocError)?;
>>> +
>>> +            if !src.is_null() {
>>> +                // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
>>> +                // `old_size`; `dst` is guaranteed to point to valid memory with a size of at least
>>> +                // `size`.
>>> +                unsafe {
>>> +                    core::ptr::copy_nonoverlapping(
>>> +                        src,
>>> +                        dst.as_ptr(),
>>> +                        core::cmp::min(old_size, size),
>>> +                    )
>>> +                };
>>> +
>>> +                // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or
>>> +                // NULL.
>>> +                unsafe { bindings::vfree(src.cast()) }
>>> +            }
>>> +
>>> +            dst
>>> +        };
>>
>> If we had not a single realloc, but shrink/grow/free/alloc, then we
>> would not need these checks here, I personally would prefer that, what
>> do you guys think?
> 
> Yeah, but look at `Kmalloc`, you'd have these checks in `Kmalloc`'s shrink/grow
> functions instead, since `krealloc()` already behaves this way.

In the kmalloc case you would have different instantiations, no checks.
IIUC for freeing you would do `krealloc(ptr, 0, flags)`.

> Personally, I don't see much value in `shrink` and `grow`. I think
> implementations end up calling into some `realloc` with either `new < old` or
> `new > old` anyway.

I think a `resize` would make more sense. In general, splitting
resizing, creating and freeing makes sense to me.

---
Cheers,
Benno

Re: [PATCH 07/20] rust: alloc: implement `Vmalloc` allocator

[Danilo Krummrich]

On Sat, Jul 06, 2024 at 01:21:39PM +0000, Benno Lossin wrote:
> On 06.07.24 13:13, Danilo Krummrich wrote:
> > On Sat, Jul 06, 2024 at 10:41:28AM +0000, Benno Lossin wrote:
> >> On 04.07.24 19:06, Danilo Krummrich wrote:
> >>> @@ -112,6 +118,55 @@ unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
> >>>      }
> >>>  }
> >>>
> >>> +unsafe impl Allocator for Vmalloc {
> >>> +    unsafe fn realloc(
> >>> +        &self,
> >>> +        src: *mut u8,
> >>> +        old_size: usize,
> >>> +        layout: Layout,
> >>> +        flags: Flags,
> >>> +    ) -> Result<NonNull<[u8]>, AllocError> {
> >>> +        let mut size = aligned_size(layout);
> >>> +
> >>> +        let dst = if size == 0 {
> >>> +            // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or NULL.
> >>> +            unsafe { bindings::vfree(src.cast()) };
> >>> +            NonNull::dangling()
> >>> +        } else if size <= old_size {
> >>> +            size = old_size;
> >>> +            NonNull::new(src).ok_or(AllocError)?
> >>> +        } else {
> >>> +            // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> >>> +            // `old_size`, which was previously allocated with this `Allocator` or NULL.
> >>> +            let dst = unsafe { bindings::__vmalloc_noprof(size as u64, flags.0) };
> >>> +
> >>> +            // Validate that we actually allocated the requested memory.
> >>> +            let dst = NonNull::new(dst.cast()).ok_or(AllocError)?;
> >>> +
> >>> +            if !src.is_null() {
> >>> +                // SAFETY: `src` is guaranteed to point to valid memory with a size of at least
> >>> +                // `old_size`; `dst` is guaranteed to point to valid memory with a size of at least
> >>> +                // `size`.
> >>> +                unsafe {
> >>> +                    core::ptr::copy_nonoverlapping(
> >>> +                        src,
> >>> +                        dst.as_ptr(),
> >>> +                        core::cmp::min(old_size, size),
> >>> +                    )
> >>> +                };
> >>> +
> >>> +                // SAFETY: `src` is guaranteed to be previously allocated with this `Allocator` or
> >>> +                // NULL.
> >>> +                unsafe { bindings::vfree(src.cast()) }
> >>> +            }
> >>> +
> >>> +            dst
> >>> +        };
> >>
> >> If we had not a single realloc, but shrink/grow/free/alloc, then we
> >> would not need these checks here, I personally would prefer that, what
> >> do you guys think?
> > 
> > Yeah, but look at `Kmalloc`, you'd have these checks in `Kmalloc`'s shrink/grow
> > functions instead, since `krealloc()` already behaves this way.
> 
> In the kmalloc case you would have different instantiations, no checks.
> IIUC for freeing you would do `krealloc(ptr, 0, flags)`.

We can't allow to shrink on a `grow` call and we can't allow to grow on a
`shrink` call, so we have to do the checks there before we call into krealloc().

Unless, we say that passing stupid arguments to `grow` can actually shrink and
vice versa, but then we can just keep `realloc`, right?

> 
> > Personally, I don't see much value in `shrink` and `grow`. I think
> > implementations end up calling into some `realloc` with either `new < old` or
> > `new > old` anyway.
> 
> I think a `resize` would make more sense. In general, splitting
> resizing, creating and freeing makes sense to me.

Please see the other mail thread.

> 
> ---
> Cheers,
> Benno
> 

[PATCH 08/20] rust: alloc: implement `KVmalloc` allocator

[Danilo Krummrich]

Implement `Allocator` for `KVmalloc`, an `Allocator` that tries to
allocate memory wth `kmalloc` first and, on failure, falls back to
`vmalloc`.

All memory allocations made with `KVmalloc` end up in
`kvrealloc_noprof()`; all frees in `kvfree()`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc/allocator.rs      | 35 +++++++++++++++++++++++++++++
 rust/kernel/alloc/allocator_test.rs |  1 +
 2 files changed, 36 insertions(+)

diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs
index 0a4f27c5c3a6..d561c594cc7f 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -22,6 +22,12 @@
 /// contiguous kernel virtual space.
 pub struct Vmalloc;
 
+/// The kvmalloc kernel allocator.
+///
+/// Attempt to allocate physically contiguous memory, but upon failure, fall back to non-contiguous
+/// (vmalloc) allocation.
+pub struct KVmalloc;
+
 /// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment.
 fn aligned_size(new_layout: Layout) -> usize {
     // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first.
@@ -167,6 +173,35 @@ unsafe fn realloc(
     }
 }
 
+unsafe impl Allocator for KVmalloc {
+    unsafe fn realloc(
+        &self,
+        old_ptr: *mut u8,
+        old_size: usize,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let size = aligned_size(layout);
+
+        let ptr = if size == 0 {
+            // SAFETY: `old_ptr` is guaranteed to be previously allocated with this `Allocator` or
+            // NULL.
+            unsafe { bindings::kvfree(old_ptr.cast()) };
+            NonNull::dangling()
+        } else {
+            // SAFETY: `old_ptr` is guaranteed to point to valid memory with a size of at least
+            // `old_size`, which was previously allocated with this `Allocator` or NULL.
+            let raw_ptr = unsafe {
+                bindings::kvrealloc_noprof(old_ptr.cast(), old_size, size, flags.0).cast()
+            };
+
+            NonNull::new(raw_ptr).ok_or(AllocError)?
+        };
+
+        Ok(NonNull::slice_from_raw_parts(ptr, size))
+    }
+}
+
 #[global_allocator]
 static ALLOCATOR: Kmalloc = Kmalloc;
 
diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs
index b2d7db492ba6..f0e96016b196 100644
--- a/rust/kernel/alloc/allocator_test.rs
+++ b/rust/kernel/alloc/allocator_test.rs
@@ -8,6 +8,7 @@
 
 pub struct Kmalloc;
 pub type Vmalloc = Kmalloc;
+pub type KVmalloc = Kmalloc;
 
 unsafe impl Allocator for Kmalloc {
     unsafe fn realloc(
-- 
2.45.2

[PATCH 09/20] rust: types: implement `Unique<T>`

[Danilo Krummrich]

Implement the `Unique` type as a prerequisite for `KBox` and `Kvec`
introduced in subsequent patches.

`Unique` serves as wrapper around a `NonNull`, but indicates that the
possessor of this wrapper owns the referent.

This type already exists in Rust's core library, but, unfortunately, is
exposed as unstable API and hence shouldn't be used in the kernel.

This implementation of `Unique` is almost identical, but mostly stripped
down to the functionality we need for `KBox` and `KVec`. Additionally,
all unstable features are removed and / or replaced by stable ones.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/types.rs | 176 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 176 insertions(+)

diff --git a/rust/kernel/types.rs b/rust/kernel/types.rs
index 2e7c9008621f..281327ea2932 100644
--- a/rust/kernel/types.rs
+++ b/rust/kernel/types.rs
@@ -409,3 +409,179 @@ pub enum Either<L, R> {
     /// Constructs an instance of [`Either`] containing a value of type `R`.
     Right(R),
 }
+
+/// A wrapper around a raw non-null `*mut T` that indicates that the possessor
+/// of this wrapper owns the referent. Useful for building abstractions like
+/// `Box<T>`, `Vec<T>`, `String`, and `HashMap<K, V>`.
+///
+/// Unlike `*mut T`, `Unique<T>` behaves "as if" it were an instance of `T`.
+/// It implements `Send`/`Sync` if `T` is `Send`/`Sync`. It also implies
+/// the kind of strong aliasing guarantees an instance of `T` can expect:
+/// the referent of the pointer should not be modified without a unique path to
+/// its owning Unique.
+///
+/// If you're uncertain of whether it's correct to use `Unique` for your purposes,
+/// consider using `NonNull`, which has weaker semantics.
+///
+/// Unlike `*mut T`, the pointer must always be non-null, even if the pointer
+/// is never dereferenced. This is so that enums may use this forbidden value
+/// as a discriminant -- `Option<Unique<T>>` has the same size as `Unique<T>`.
+/// However the pointer may still dangle if it isn't dereferenced.
+///
+/// Unlike `*mut T`, `Unique<T>` is covariant over `T`. This should always be correct
+/// for any type which upholds Unique's aliasing requirements.
+#[repr(transparent)]
+pub struct Unique<T: ?Sized> {
+    pointer: NonNull<T>,
+    // NOTE: this marker has no consequences for variance, but is necessary
+    // for dropck to understand that we logically own a `T`.
+    //
+    // For details, see:
+    // https://github.com/rust-lang/rfcs/blob/master/text/0769-sound-generic-drop.md#phantom-data
+    _marker: PhantomData<T>,
+}
+
+/// `Unique` pointers are `Send` if `T` is `Send` because the data they
+/// reference is unaliased. Note that this aliasing invariant is
+/// unenforced by the type system; the abstraction using the
+/// `Unique` must enforce it.
+unsafe impl<T: Send + ?Sized> Send for Unique<T> {}
+
+/// `Unique` pointers are `Sync` if `T` is `Sync` because the data they
+/// reference is unaliased. Note that this aliasing invariant is
+/// unenforced by the type system; the abstraction using the
+/// `Unique` must enforce it.
+unsafe impl<T: Sync + ?Sized> Sync for Unique<T> {}
+
+impl<T: Sized> Unique<T> {
+    /// Creates a new `Unique` that is dangling, but well-aligned.
+    ///
+    /// This is useful for initializing types which lazily allocate, like
+    /// `Vec::new` does.
+    ///
+    /// Note that the pointer value may potentially represent a valid pointer to
+    /// a `T`, which means this must not be used as a "not yet initialized"
+    /// sentinel value. Types that lazily allocate must track initialization by
+    /// some other means.
+    #[must_use]
+    #[inline]
+    pub const fn dangling() -> Self {
+        Unique {
+            pointer: NonNull::dangling(),
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<T: ?Sized> Unique<T> {
+    /// Creates a new `Unique`.
+    ///
+    /// # Safety
+    ///
+    /// `ptr` must be non-null.
+    #[inline]
+    pub const unsafe fn new_unchecked(ptr: *mut T) -> Self {
+        // SAFETY: the caller must guarantee that `ptr` is non-null.
+        unsafe {
+            Unique {
+                pointer: NonNull::new_unchecked(ptr),
+                _marker: PhantomData,
+            }
+        }
+    }
+
+    /// Creates a new `Unique` if `ptr` is non-null.
+    #[allow(clippy::manual_map)]
+    #[inline]
+    pub fn new(ptr: *mut T) -> Option<Self> {
+        if let Some(pointer) = NonNull::new(ptr) {
+            Some(Unique {
+                pointer,
+                _marker: PhantomData,
+            })
+        } else {
+            None
+        }
+    }
+
+    /// Acquires the underlying `*mut` pointer.
+    #[must_use = "`self` will be dropped if the result is not used"]
+    #[inline]
+    pub const fn as_ptr(self) -> *mut T {
+        self.pointer.as_ptr()
+    }
+
+    /// Dereferences the content.
+    ///
+    /// The resulting lifetime is bound to self so this behaves "as if"
+    /// it were actually an instance of T that is getting borrowed. If a longer
+    /// (unbound) lifetime is needed, use `&*my_ptr.as_ptr()`.
+    ///
+    /// # Safety
+    ///
+    /// Safety requirements for this function are inherited from [NonNull::as_ref].
+    ///
+    #[must_use]
+    #[inline]
+    pub const unsafe fn as_ref(&self) -> &T {
+        // SAFETY: the caller must guarantee that `self` meets all the
+        // requirements for a reference.
+        unsafe { self.pointer.as_ref() }
+    }
+
+    /// Mutably dereferences the content.
+    ///
+    /// The resulting lifetime is bound to self so this behaves "as if"
+    /// it were actually an instance of T that is getting borrowed. If a longer
+    /// (unbound) lifetime is needed, use `&mut *my_ptr.as_ptr()`.
+    ///
+    /// # Safety
+    ///
+    /// Safety requirements for this function are inherited from [NonNull::as_mut].
+    #[must_use]
+    #[inline]
+    pub unsafe fn as_mut(&mut self) -> &mut T {
+        // SAFETY: the caller must guarantee that `self` meets all the
+        // requirements for a mutable reference.
+        unsafe { self.pointer.as_mut() }
+    }
+
+    /// Casts to a pointer of another type.
+    #[must_use = "`self` will be dropped if the result is not used"]
+    #[inline]
+    pub fn cast<U>(self) -> Unique<U> {
+        Unique::from(self.pointer.cast())
+    }
+}
+
+impl<T: ?Sized> Clone for Unique<T> {
+    #[inline]
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+impl<T: ?Sized> Copy for Unique<T> {}
+
+impl<T: ?Sized> From<&mut T> for Unique<T> {
+    /// Converts a `&mut T` to a `Unique<T>`.
+    ///
+    /// This conversion is infallible since references cannot be null.
+    #[inline]
+    fn from(reference: &mut T) -> Self {
+        Self::from(NonNull::from(reference))
+    }
+}
+
+impl<T: ?Sized> From<NonNull<T>> for Unique<T> {
+    /// Converts a `NonNull<T>` to a `Unique<T>`.
+    ///
+    /// This conversion is infallible since `NonNull` cannot be null.
+    #[inline]
+    fn from(pointer: NonNull<T>) -> Self {
+        Unique {
+            pointer,
+            _marker: PhantomData,
+        }
+    }
+}
-- 
2.45.2

Re: [PATCH 09/20] rust: types: implement `Unique<T>`

[Benno Lossin]

On 04.07.24 19:06, Danilo Krummrich wrote:
> Implement the `Unique` type as a prerequisite for `KBox` and `Kvec`
> introduced in subsequent patches.
> 
> `Unique` serves as wrapper around a `NonNull`, but indicates that the
> possessor of this wrapper owns the referent.
> 
> This type already exists in Rust's core library, but, unfortunately, is
> exposed as unstable API and hence shouldn't be used in the kernel.

It's not really exposed, as the feature (ptr_internals) is an internal
unstable feature and thus probably perma-unstable.

(but your argument still holds, this just means that we *really* should
not be using it)

> This implementation of `Unique` is almost identical, but mostly stripped
> down to the functionality we need for `KBox` and `KVec`. Additionally,
> all unstable features are removed and / or replaced by stable ones.
> 
> Signed-off-by: Danilo Krummrich <dakr@redhat.com>
> ---
>  rust/kernel/types.rs | 176 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 176 insertions(+)
> 
> diff --git a/rust/kernel/types.rs b/rust/kernel/types.rs
> index 2e7c9008621f..281327ea2932 100644
> --- a/rust/kernel/types.rs
> +++ b/rust/kernel/types.rs
> @@ -409,3 +409,179 @@ pub enum Either<L, R> {
>      /// Constructs an instance of [`Either`] containing a value of type `R`.
>      Right(R),
>  }
> +
> +/// A wrapper around a raw non-null `*mut T` that indicates that the possessor
> +/// of this wrapper owns the referent. Useful for building abstractions like
> +/// `Box<T>`, `Vec<T>`, `String`, and `HashMap<K, V>`.
> +///
> +/// Unlike `*mut T`, `Unique<T>` behaves "as if" it were an instance of `T`.
> +/// It implements `Send`/`Sync` if `T` is `Send`/`Sync`. It also implies
> +/// the kind of strong aliasing guarantees an instance of `T` can expect:
> +/// the referent of the pointer should not be modified without a unique path to
> +/// its owning Unique.
> +///
> +/// If you're uncertain of whether it's correct to use `Unique` for your purposes,
> +/// consider using `NonNull`, which has weaker semantics.
> +///
> +/// Unlike `*mut T`, the pointer must always be non-null, even if the pointer
> +/// is never dereferenced. This is so that enums may use this forbidden value
> +/// as a discriminant -- `Option<Unique<T>>` has the same size as `Unique<T>`.
> +/// However the pointer may still dangle if it isn't dereferenced.
> +///
> +/// Unlike `*mut T`, `Unique<T>` is covariant over `T`. This should always be correct
> +/// for any type which upholds Unique's aliasing requirements.

Since you copied this directly from the stdlib, should this be citing
it?

> +#[repr(transparent)]
> +pub struct Unique<T: ?Sized> {
> +    pointer: NonNull<T>,

Gary and I already mentioned this in the meeting, but I will put it here
for the record:

The `Unique` from std is special, in the sense that the Rust compiler
will emit the `noalias` LLVM attribute.

This gives std's `Box` type a possible performance advantage (IIRC Gary
had a compiler explorer example that showed different instruction
count).

I thought that we could mimic this behavior if we would change the type
of `pointer` to `ManuallyDrop<Box<T>>`. But that only works if the
pointer is always valid, since otherwise we can't call `Box::from_raw`.

So currently I don't see a workaround that would give us the noalias
attribute back.

It would be a good idea to get some benchmarks on how this affects
performance, Andreas or Alice do you think you can give a bit of compute
time, once this patchset is more mature?

> +    // NOTE: this marker has no consequences for variance, but is necessary
> +    // for dropck to understand that we logically own a `T`.
> +    //
> +    // For details, see:
> +    // https://github.com/rust-lang/rfcs/blob/master/text/0769-sound-generic-drop.md#phantom-data
> +    _marker: PhantomData<T>,
> +}
> +
> +/// `Unique` pointers are `Send` if `T` is `Send` because the data they
> +/// reference is unaliased. Note that this aliasing invariant is
> +/// unenforced by the type system; the abstraction using the
> +/// `Unique` must enforce it.
> +unsafe impl<T: Send + ?Sized> Send for Unique<T> {}
> +
> +/// `Unique` pointers are `Sync` if `T` is `Sync` because the data they
> +/// reference is unaliased. Note that this aliasing invariant is
> +/// unenforced by the type system; the abstraction using the
> +/// `Unique` must enforce it.
> +unsafe impl<T: Sync + ?Sized> Sync for Unique<T> {}
> +
> +impl<T: Sized> Unique<T> {
> +    /// Creates a new `Unique` that is dangling, but well-aligned.
> +    ///
> +    /// This is useful for initializing types which lazily allocate, like
> +    /// `Vec::new` does.
> +    ///
> +    /// Note that the pointer value may potentially represent a valid pointer to
> +    /// a `T`, which means this must not be used as a "not yet initialized"
> +    /// sentinel value. Types that lazily allocate must track initialization by
> +    /// some other means.
> +    #[must_use]
> +    #[inline]
> +    pub const fn dangling() -> Self {
> +        Unique {
> +            pointer: NonNull::dangling(),
> +            _marker: PhantomData,
> +        }
> +    }
> +}
> +
> +impl<T: ?Sized> Unique<T> {
> +    /// Creates a new `Unique`.
> +    ///
> +    /// # Safety
> +    ///
> +    /// `ptr` must be non-null.
> +    #[inline]
> +    pub const unsafe fn new_unchecked(ptr: *mut T) -> Self {
> +        // SAFETY: the caller must guarantee that `ptr` is non-null.
> +        unsafe {
> +            Unique {
> +                pointer: NonNull::new_unchecked(ptr),
> +                _marker: PhantomData,
> +            }
> +        }
> +    }
> +
> +    /// Creates a new `Unique` if `ptr` is non-null.
> +    #[allow(clippy::manual_map)]
> +    #[inline]
> +    pub fn new(ptr: *mut T) -> Option<Self> {

I think we should give `Unique` the invariant that it is unique, making
this function `unsafe`, since the caller must ensure that only this
unique has access to the pointee.

---
Cheers,
Benno

> +        if let Some(pointer) = NonNull::new(ptr) {
> +            Some(Unique {
> +                pointer,
> +                _marker: PhantomData,
> +            })
> +        } else {
> +            None
> +        }
> +    }

Re: [PATCH 09/20] rust: types: implement `Unique<T>`

[Miguel Ojeda]

On Sat, Jul 6, 2024 at 12:59 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> The `Unique` from std is special, in the sense that the Rust compiler
> will emit the `noalias` LLVM attribute.
>
> This gives std's `Box` type a possible performance advantage (IIRC Gary
> had a compiler explorer example that showed different instruction
> count).

The example in question: https://godbolt.org/z/n93vePqMj -- there is
one less memory load.

One can also easily craft examples where the compiler e.g. removes an
entire loop: https://godbolt.org/z/c8ncbdKMe

But, of course, it depends on whether we will actually encounter these
situations in real code, as you say. It could also be that today we
don't find any relevant benefit, but there may exist situations later
(perhaps because we have more code, or perhaps because codegen
backends change).

From a quick look, there are still quite a few open issues about the
exact properties of `Box` and `Unique`, including whether `Box` has a
derefencability requirement
(https://github.com/rust-lang/unsafe-code-guidelines/issues/145).

What properties would we want, today, from our `Box` types, if we
could pick any? Should we have several kinds of `Box`es if there is no
unique answer? Is it worth diverging from the standard one(s) in
either direction (i.e. more invariants or less)?

Cheers,
Miguel

Re: [PATCH 09/20] rust: types: implement `Unique<T>`

[Benno Lossin]

On 06.07.24 14:40, Miguel Ojeda wrote:
> On Sat, Jul 6, 2024 at 12:59 PM Benno Lossin <benno.lossin@proton.me> wrote:
>>
>> The `Unique` from std is special, in the sense that the Rust compiler
>> will emit the `noalias` LLVM attribute.
>>
>> This gives std's `Box` type a possible performance advantage (IIRC Gary
>> had a compiler explorer example that showed different instruction
>> count).
> 
> The example in question: https://godbolt.org/z/n93vePqMj -- there is
> one less memory load.
> 
> One can also easily craft examples where the compiler e.g. removes an
> entire loop: https://godbolt.org/z/c8ncbdKMe
> 
> But, of course, it depends on whether we will actually encounter these
> situations in real code, as you say. It could also be that today we
> don't find any relevant benefit, but there may exist situations later
> (perhaps because we have more code, or perhaps because codegen
> backends change).

It would be a good idea to ask the Rust folks if they could give us a
unique type that does what we need.

> From a quick look, there are still quite a few open issues about the
> exact properties of `Box` and `Unique`, including whether `Box` has a
> derefencability requirement
> (https://github.com/rust-lang/unsafe-code-guidelines/issues/145).

Yes, this is why I wasn't sure if we could do the workaround I
mentioned. My guess is that it doesn't work or that at least it isn't
supported (i.e. could change at any point).

> What properties would we want, today, from our `Box` types, if we
> could pick any? Should we have several kinds of `Box`es if there is no
> unique answer? Is it worth diverging from the standard one(s) in
> either direction (i.e. more invariants or less)?

I would expect that `Box<T>` behaves like `&mut T` except that it owns
the memory.

For starters we probably want this "normal" Box. If we get a unique
pointer type, then we can introduce more, but I don't think we need that
at the moment.

---
Cheers,
Benno

[PATCH 10/20] rust: alloc: implement `KBox`

[Danilo Krummrich]

`KBox` provides the simplest way to allocate memory for a generic type
with one of the kernel's allocators, e.g. `Kmalloc`, `Vmalloc` or
`KVmalloc`.

In contrast to `Box`, `KBox` considers the kernel's GFP flags for all
appropriate functions, always reports allocation failures through
`Result<_, AllocError>` and remains independent from unstable features.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs      |   3 +
 rust/kernel/alloc/kbox.rs | 319 ++++++++++++++++++++++++++++++++++++++
 rust/kernel/init.rs       |  32 +++-
 rust/kernel/prelude.rs    |   2 +-
 rust/kernel/types.rs      |  23 +++
 5 files changed, 377 insertions(+), 2 deletions(-)
 create mode 100644 rust/kernel/alloc/kbox.rs

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 46ebdd059c92..ff90cefad0ea 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -5,6 +5,7 @@
 #[cfg(not(any(test, testlib)))]
 pub mod allocator;
 pub mod box_ext;
+pub mod kbox;
 pub mod vec_ext;
 
 #[cfg(any(test, testlib))]
@@ -13,6 +14,8 @@
 #[cfg(any(test, testlib))]
 pub use self::allocator_test as allocator;
 
+pub use self::kbox::KBox;
+
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub struct AllocError;
diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs
new file mode 100644
index 000000000000..69976fd1d518
--- /dev/null
+++ b/rust/kernel/alloc/kbox.rs
@@ -0,0 +1,319 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Implementation of [`KBox`].
+
+use super::{allocator::Kmalloc, AllocError, Allocator, Flags};
+use core::fmt;
+use core::mem::ManuallyDrop;
+use core::mem::MaybeUninit;
+use core::ops::{Deref, DerefMut};
+use core::pin::Pin;
+use core::ptr;
+use core::result::Result;
+
+use crate::types::Unique;
+
+/// The kernel's `Box` type named [`KBox`].
+///
+/// `KBox` provides the simplest way to allocate memory for a generic type with one of the kernel's
+/// allocators, e.g. `Kmalloc`, `Vmalloc` or `KVmalloc`.
+///
+/// For non-zero-sized values, a [`KBox`] will use the given allocator `A` for its allocation. If
+/// no specific `Allocator` is requested, [`KBox`] will default to `Kmalloc`.
+///
+/// It is valid to convert both ways between a [`KBox`] and a raw pointer allocated with any
+/// `Allocator`, given that the `Layout` used with the allocator is correct for the type.
+///
+/// For zero-sized values the [`KBox`]' pointer must be `dangling_mut::<T>`; no memory is
+/// allocated.
+///
+/// So long as `T: Sized`, a `Box<T>` is guaranteed to be represented as a single pointer and is
+/// also ABI-compatible with C pointers (i.e. the C type `T*`).
+///
+/// # Invariants
+///
+/// The [`KBox`]' pointer always properly aligned and either points to memory allocated with `A` or,
+/// for zero-sized types, is a dangling pointer.
+///
+/// # Examples
+///
+/// ```
+/// let b = KBox::new(24_u64, GFP_KERNEL)?;
+///
+/// assert_eq!(*b, 24_u64);
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// ```
+/// use kernel::alloc::allocator::KVmalloc;
+///
+/// struct Huge([u8; 1 << 24]);
+///
+/// assert!(KBox::<Huge, KVmalloc>::new_uninit_alloc(KVmalloc, GFP_KERNEL).is_ok());
+/// ```
+pub struct KBox<T: ?Sized, A: Allocator = Kmalloc>(Unique<T>, A);
+
+impl<T, A> KBox<T, A>
+where
+    T: ?Sized,
+    A: Allocator,
+{
+    /// Constructs a `KBox<T, A>` from a raw pointer.
+    ///
+    /// # Safety
+    ///
+    /// `raw` must point to valid memory, previously allocated with `A`, and at least the size of
+    /// type `T`.
+    #[inline]
+    pub const unsafe fn from_raw_alloc(raw: *mut T, alloc: A) -> Self {
+        // SAFETY: Safe by the requirements of this function.
+        KBox(unsafe { Unique::new_unchecked(raw) }, alloc)
+    }
+
+    /// Consumes the `KBox<T, A>`, returning a wrapped raw pointer and the allocator it was
+    /// allocated with.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let x = KBox::new(24, GFP_KERNEL)?;
+    /// let (ptr, alloc) = KBox::into_raw_alloc(x);
+    /// let x = unsafe { KBox::from_raw_alloc(ptr, alloc) };
+    ///
+    /// assert_eq!(*x, 24);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn into_raw_alloc(self) -> (*mut T, A) {
+        let b = ManuallyDrop::new(self);
+        let alloc = unsafe { ptr::read(&b.1) };
+        (b.0.as_ptr(), alloc)
+    }
+
+    /// Consumes the `KBox<T>`, returning a wrapped raw pointer.
+    #[inline]
+    pub fn into_raw(self) -> *mut T {
+        self.into_raw_alloc().0
+    }
+
+    /// Consumes and leaks the `KBox<T>`, returning a mutable reference, &'a mut T.
+    #[inline]
+    pub fn leak<'a>(b: Self) -> &'a mut T
+    where
+        T: 'a,
+    {
+        // SAFETY: `KBox::into_raw` always returns a properly aligned and dereferenceable pointer
+        // which points to an initialized instance of `T`.
+        unsafe { &mut *KBox::into_raw(b) }
+    }
+
+    /// Converts a `KBox<T>` into a `Pin<KBox<T>>`.
+    #[inline]
+    pub fn into_pin(b: Self) -> Pin<Self>
+    where
+        A: 'static,
+    {
+        // SAFETY: It's not possible to move or replace the insides of a `Pin<KBox<T>>` when
+        // `T: !Unpin`, so it's safe to pin it directly without any additional requirements.
+        unsafe { Pin::new_unchecked(b) }
+    }
+}
+
+impl<T, A> KBox<MaybeUninit<T>, A>
+where
+    A: Allocator,
+{
+    /// Converts to `KBox<T, A>`.
+    ///
+    /// # Safety
+    ///
+    /// As with MaybeUninit::assume_init, it is up to the caller to guarantee that the value really
+    /// is in an initialized state. Calling this when the content is not yet fully initialized
+    /// causes immediate undefined behavior.
+    pub unsafe fn assume_init(self) -> KBox<T, A> {
+        let (raw, alloc) = KBox::into_raw_alloc(self);
+        // SAFETY: Reconstruct the `KBox<MaybeUninit<T>, A>` as KBox<T, A> now that has been
+        // initialized. `raw` and `alloc` are safe by the invariants of `KBox`.
+        unsafe { KBox::from_raw_alloc(raw as *mut T, alloc) }
+    }
+
+    /// Writes the value and converts to `KBox<T, A>`.
+    pub fn write(mut boxed: Self, value: T) -> KBox<T, A> {
+        (*boxed).write(value);
+        // SAFETY: We've just initialized `boxed`'s value.
+        unsafe { boxed.assume_init() }
+    }
+}
+
+impl<T> KBox<T> {
+    /// Allocates memory with `Kmalloc` and then places `x` into it.
+    ///
+    /// This doesn’t actually allocate if T is zero-sized.
+    pub fn new(x: T, flags: Flags) -> Result<Self, AllocError> {
+        let b = Self::new_uninit(flags)?;
+        Ok(KBox::write(b, x))
+    }
+
+    /// Constructs a new `KBox<T>` with uninitialized contents.
+    #[inline]
+    pub fn new_uninit(flags: Flags) -> Result<KBox<MaybeUninit<T>>, AllocError> {
+        Self::new_uninit_alloc(Kmalloc, flags)
+    }
+
+    /// Constructs a new `Pin<KBox<T>>`. If `T` does not implement [`Unpin`], then `x` will be
+    /// pinned in memory and unable to be moved.
+    #[inline]
+    pub fn pin(x: T, flags: Flags) -> Result<Pin<KBox<T>>, AllocError> {
+        Ok(KBox::new(x, flags)?.into())
+    }
+}
+
+impl<T> KBox<T>
+where
+    T: ?Sized,
+{
+    /// Constructs a `KBox<T>` from a raw pointer.
+    ///
+    /// # Safety
+    ///
+    /// `raw` must point to valid memory, previously allocated with the `Kmalloc`, and at least the
+    /// size of type `T`.
+    #[inline]
+    pub const unsafe fn from_raw(raw: *mut T) -> Self {
+        // SAFETY: Validity of `raw` is guaranteed by the safety preconditions of this function.
+        KBox(unsafe { Unique::new_unchecked(raw) }, Kmalloc)
+    }
+}
+
+impl<T, A> KBox<T, A>
+where
+    A: Allocator,
+{
+    fn is_zst() -> bool {
+        core::mem::size_of::<T>() == 0
+    }
+
+    /// Allocates memory with the allocator `A` and then places `x` into it.
+    ///
+    /// This doesn’t actually allocate if T is zero-sized.
+    pub fn new_alloc(x: T, alloc: A, flags: Flags) -> Result<Self, AllocError> {
+        let b = Self::new_uninit_alloc(alloc, flags)?;
+        Ok(KBox::write(b, x))
+    }
+
+    /// Constructs a new `KBox<T, A>` with uninitialized contents.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::allocator::Kmalloc;
+    ///
+    /// let b = KBox::<u64>::new_uninit_alloc(Kmalloc, GFP_KERNEL)?;
+    /// let b = KBox::write(b, 24);
+    ///
+    /// assert_eq!(*b, 24_u64);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn new_uninit_alloc(alloc: A, flags: Flags) -> Result<KBox<MaybeUninit<T>, A>, AllocError> {
+        let ptr = if Self::is_zst() {
+            Unique::dangling()
+        } else {
+            let layout = core::alloc::Layout::new::<MaybeUninit<T>>();
+            let ptr = alloc.alloc(layout, flags)?;
+
+            ptr.cast().into()
+        };
+
+        Ok(KBox(ptr, alloc))
+    }
+
+    /// Constructs a new `Pin<KBox<T, A>>`. If `T` does not implement [`Unpin`], then `x` will be
+    /// pinned in memory and unable to be moved.
+    #[inline]
+    pub fn pin_alloc(x: T, alloc: A, flags: Flags) -> Result<Pin<KBox<T, A>>, AllocError>
+    where
+        A: 'static,
+    {
+        Ok(Self::new_alloc(x, alloc, flags)?.into())
+    }
+}
+
+impl<T, A> From<KBox<T, A>> for Pin<KBox<T, A>>
+where
+    T: ?Sized,
+    A: Allocator,
+    A: 'static,
+{
+    /// Converts a `KBox<T>` into a `Pin<KBox<T>>`. If `T` does not implement [`Unpin`], then
+    /// `*boxed` will be pinned in memory and unable to be moved.
+    ///
+    /// This conversion does not allocate on the heap and happens in place.
+    ///
+    /// This is also available via [`KBox::into_pin`].
+    ///
+    /// Constructing and pinning a `KBox` with <code><Pin<KBox\<T>>>::from([KBox::new]\(x))</code>
+    /// can also be written more concisely using <code>[KBox::pin]\(x)</code>.
+    /// This `From` implementation is useful if you already have a `KBox<T>`, or you are
+    /// constructing a (pinned) `KBox` in a different way than with [`KBox::new`].
+    fn from(b: KBox<T, A>) -> Self {
+        KBox::into_pin(b)
+    }
+}
+
+impl<T, A> Deref for KBox<T, A>
+where
+    T: ?Sized,
+    A: Allocator,
+{
+    type Target = T;
+
+    fn deref(&self) -> &T {
+        // SAFETY: `self.0` is always properly aligned, dereferenceable and points to an initialized
+        // instance of `T`.
+        unsafe { self.0.as_ref() }
+    }
+}
+
+impl<T, A> DerefMut for KBox<T, A>
+where
+    T: ?Sized,
+    A: Allocator,
+{
+    fn deref_mut(&mut self) -> &mut T {
+        // SAFETY: `self.0` is always properly aligned, dereferenceable and points to an initialized
+        // instance of `T`.
+        unsafe { self.0.as_mut() }
+    }
+}
+
+impl<T, A> fmt::Debug for KBox<T, A>
+where
+    T: ?Sized + fmt::Debug,
+    A: Allocator,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(&**self, f)
+    }
+}
+
+impl<T, A> Drop for KBox<T, A>
+where
+    T: ?Sized,
+    A: Allocator,
+{
+    fn drop(&mut self) {
+        let ptr = self.0.as_ptr();
+
+        // SAFETY: We need to drop `self.0` in place, before we free the backing memory.
+        unsafe { core::ptr::drop_in_place(ptr) };
+
+        // SAFETY: `ptr` is always properly aligned, dereferenceable and points to an initialized
+        // instance of `T`.
+        if unsafe { core::mem::size_of_val(&*ptr) } != 0 {
+            // SAFETY: `ptr` was previously allocated with `self.1`.
+            unsafe { self.1.free(ptr.cast()) };
+        }
+    }
+}
diff --git a/rust/kernel/init.rs b/rust/kernel/init.rs
index 68605b633e73..b34c8127b76d 100644
--- a/rust/kernel/init.rs
+++ b/rust/kernel/init.rs
@@ -211,7 +211,7 @@
 //! [`pin_init!`]: crate::pin_init!
 
 use crate::{
-    alloc::{box_ext::BoxExt, AllocError, Flags},
+    alloc::{box_ext::BoxExt, AllocError, Flags, KBox},
     error::{self, Error},
     sync::UniqueArc,
     types::{Opaque, ScopeGuard},
@@ -1183,6 +1183,36 @@ fn try_init<E>(init: impl Init<T, E>, flags: Flags) -> Result<Self, E>
     }
 }
 
+impl<T> InPlaceInit<T> for KBox<T> {
+    #[inline]
+    fn try_pin_init<E>(init: impl PinInit<T, E>, flags: Flags) -> Result<Pin<Self>, E>
+    where
+        E: From<AllocError>,
+    {
+        let mut this = KBox::<_>::new_uninit(flags)?;
+        let slot = this.as_mut_ptr();
+        // SAFETY: When init errors/panics, slot will get deallocated but not dropped,
+        // slot is valid and will not be moved, because we pin it later.
+        unsafe { init.__pinned_init(slot)? };
+        // SAFETY: All fields have been initialized.
+        Ok(unsafe { this.assume_init() }.into())
+    }
+
+    #[inline]
+    fn try_init<E>(init: impl Init<T, E>, flags: Flags) -> Result<Self, E>
+    where
+        E: From<AllocError>,
+    {
+        let mut this = KBox::<_>::new_uninit(flags)?;
+        let slot = this.as_mut_ptr();
+        // SAFETY: When init errors/panics, slot will get deallocated but not dropped,
+        // slot is valid.
+        unsafe { init.__init(slot)? };
+        // SAFETY: All fields have been initialized.
+        Ok(unsafe { this.assume_init() })
+    }
+}
+
 impl<T> InPlaceInit<T> for UniqueArc<T> {
     #[inline]
     fn try_pin_init<E>(init: impl PinInit<T, E>, flags: Flags) -> Result<Pin<Self>, E>
diff --git a/rust/kernel/prelude.rs b/rust/kernel/prelude.rs
index b37a0b3180fb..d75c14234133 100644
--- a/rust/kernel/prelude.rs
+++ b/rust/kernel/prelude.rs
@@ -14,7 +14,7 @@
 #[doc(no_inline)]
 pub use core::pin::Pin;
 
-pub use crate::alloc::{box_ext::BoxExt, flags::*, vec_ext::VecExt};
+pub use crate::alloc::{box_ext::BoxExt, flags::*, vec_ext::VecExt, KBox};
 
 #[doc(no_inline)]
 pub use alloc::{boxed::Box, vec::Vec};
diff --git a/rust/kernel/types.rs b/rust/kernel/types.rs
index 281327ea2932..939ec27c584d 100644
--- a/rust/kernel/types.rs
+++ b/rust/kernel/types.rs
@@ -2,6 +2,7 @@
 
 //! Kernel types.
 
+use crate::alloc::KBox;
 use crate::init::{self, PinInit};
 use alloc::boxed::Box;
 use core::{
@@ -89,6 +90,28 @@ unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self {
     }
 }
 
+impl<T: 'static> ForeignOwnable for KBox<T> {
+    type Borrowed<'a> = &'a T;
+
+    fn into_foreign(self) -> *const core::ffi::c_void {
+        KBox::into_raw(self) as _
+    }
+
+    unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> &'a T {
+        // SAFETY: The safety requirements for this function ensure that the object is still alive,
+        // so it is safe to dereference the raw pointer.
+        // The safety requirements of `from_foreign` also ensure that the object remains alive for
+        // the lifetime of the returned value.
+        unsafe { &*ptr.cast() }
+    }
+
+    unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self {
+        // SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous
+        // call to `Self::into_foreign`.
+        unsafe { KBox::from_raw(ptr as _) }
+    }
+}
+
 impl ForeignOwnable for () {
     type Borrowed<'a> = ();
 
-- 
2.45.2

[PATCH 11/20] rust: treewide: switch to `KBox`

[Danilo Krummrich]

Now that we got `KBox` in place, convert all existing `Box` users to
`KBox`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/init.rs               | 62 ++++++++++++++++---------------
 rust/kernel/init/__internal.rs    |  2 +-
 rust/kernel/sync/arc.rs           | 17 ++++-----
 rust/kernel/sync/condvar.rs       |  5 ++-
 rust/kernel/sync/lock/mutex.rs    |  3 +-
 rust/kernel/sync/lock/spinlock.rs |  3 +-
 rust/kernel/workqueue.rs          | 22 +++++------
 7 files changed, 59 insertions(+), 55 deletions(-)

diff --git a/rust/kernel/init.rs b/rust/kernel/init.rs
index b34c8127b76d..b386bafd5f95 100644
--- a/rust/kernel/init.rs
+++ b/rust/kernel/init.rs
@@ -13,7 +13,7 @@
 //! To initialize a `struct` with an in-place constructor you will need two things:
 //! - an in-place constructor,
 //! - a memory location that can hold your `struct` (this can be the [stack], an [`Arc<T>`],
-//!   [`UniqueArc<T>`], [`Box<T>`] or any other smart pointer that implements [`InPlaceInit`]).
+//!   [`UniqueArc<T>`], [`KBox<T>`] or any other smart pointer that implements [`InPlaceInit`]).
 //!
 //! To get an in-place constructor there are generally three options:
 //! - directly creating an in-place constructor using the [`pin_init!`] macro,
@@ -56,6 +56,7 @@
 //!
 //! ```rust
 //! # #![allow(clippy::disallowed_names)]
+//! # use kernel::alloc::KBox;
 //! # use kernel::sync::{new_mutex, Mutex};
 //! # use core::pin::Pin;
 //! # #[pin_data]
@@ -68,7 +69,7 @@
 //! #     a <- new_mutex!(42, "Foo::a"),
 //! #     b: 24,
 //! # });
-//! let foo: Result<Pin<Box<Foo>>> = Box::pin_init(foo, GFP_KERNEL);
+//! let foo: Result<Pin<KBox<Foo>>> = KBox::pin_init(foo, GFP_KERNEL);
 //! ```
 //!
 //! For more information see the [`pin_init!`] macro.
@@ -88,19 +89,19 @@
 //!
 //! ```rust
 //! # #![allow(clippy::disallowed_names)]
-//! # use kernel::{sync::Mutex, new_mutex, init::PinInit, try_pin_init};
+//! # use kernel::{alloc::KBox, sync::Mutex, new_mutex, init::PinInit, try_pin_init};
 //! #[pin_data]
 //! struct DriverData {
 //!     #[pin]
 //!     status: Mutex<i32>,
-//!     buffer: Box<[u8; 1_000_000]>,
+//!     buffer: KBox<[u8; 1_000_000]>,
 //! }
 //!
 //! impl DriverData {
 //!     fn new() -> impl PinInit<Self, Error> {
 //!         try_pin_init!(Self {
 //!             status <- new_mutex!(0, "DriverData::status"),
-//!             buffer: Box::init(kernel::init::zeroed(), GFP_KERNEL)?,
+//!             buffer: KBox::init(kernel::init::zeroed(), GFP_KERNEL)?,
 //!         })
 //!     }
 //! }
@@ -292,12 +293,12 @@ macro_rules! stack_pin_init {
 /// # #![allow(clippy::disallowed_names)]
 /// # use kernel::{init, pin_init, stack_try_pin_init, init::*, sync::Mutex, new_mutex};
 /// # use macros::pin_data;
-/// # use core::{alloc::AllocError, pin::Pin};
+/// # use core::{alloc::{AllocError, KBox}, pin::Pin};
 /// #[pin_data]
 /// struct Foo {
 ///     #[pin]
 ///     a: Mutex<usize>,
-///     b: Box<Bar>,
+///     b: KBox<Bar>,
 /// }
 ///
 /// struct Bar {
@@ -306,7 +307,7 @@ macro_rules! stack_pin_init {
 ///
 /// stack_try_pin_init!(let foo: Result<Pin<&mut Foo>, AllocError> = pin_init!(Foo {
 ///     a <- new_mutex!(42),
-///     b: Box::new(Bar {
+///     b: KBox::new(Bar {
 ///         x: 64,
 ///     }, GFP_KERNEL)?,
 /// }));
@@ -318,12 +319,12 @@ macro_rules! stack_pin_init {
 /// # #![allow(clippy::disallowed_names)]
 /// # use kernel::{init, pin_init, stack_try_pin_init, init::*, sync::Mutex, new_mutex};
 /// # use macros::pin_data;
-/// # use core::{alloc::AllocError, pin::Pin};
+/// # use core::{alloc::{AllocError, KBox}, pin::Pin};
 /// #[pin_data]
 /// struct Foo {
 ///     #[pin]
 ///     a: Mutex<usize>,
-///     b: Box<Bar>,
+///     b: KBox<Bar>,
 /// }
 ///
 /// struct Bar {
@@ -332,7 +333,7 @@ macro_rules! stack_pin_init {
 ///
 /// stack_try_pin_init!(let foo: Pin<&mut Foo> =? pin_init!(Foo {
 ///     a <- new_mutex!(42),
-///     b: Box::new(Bar {
+///     b: KBox::new(Bar {
 ///         x: 64,
 ///     }, GFP_KERNEL)?,
 /// }));
@@ -368,7 +369,7 @@ macro_rules! stack_try_pin_init {
 ///
 /// ```rust
 /// # #![allow(clippy::disallowed_names)]
-/// # use kernel::{init, pin_init, macros::pin_data, init::*};
+/// # use kernel::{alloc::KBox, init, pin_init, macros::pin_data, init::*};
 /// # use core::pin::Pin;
 /// #[pin_data]
 /// struct Foo {
@@ -391,7 +392,7 @@ macro_rules! stack_try_pin_init {
 ///     },
 /// });
 /// # initializer }
-/// # Box::pin_init(demo(), GFP_KERNEL).unwrap();
+/// # KBox::pin_init(demo(), GFP_KERNEL).unwrap();
 /// ```
 ///
 /// Arbitrary Rust expressions can be used to set the value of a variable.
@@ -440,7 +441,7 @@ macro_rules! stack_try_pin_init {
 ///
 /// ```rust
 /// # #![allow(clippy::disallowed_names)]
-/// # use kernel::{init, pin_init, macros::pin_data, init::*};
+/// # use kernel::{alloc::KBox, init, pin_init, macros::pin_data, init::*};
 /// # use core::pin::Pin;
 /// # #[pin_data]
 /// # struct Foo {
@@ -461,7 +462,7 @@ macro_rules! stack_try_pin_init {
 /// #         })
 /// #     }
 /// # }
-/// let foo = Box::pin_init(Foo::new(), GFP_KERNEL);
+/// let foo = KBox::pin_init(Foo::new(), GFP_KERNEL);
 /// ```
 ///
 /// They can also easily embed it into their own `struct`s:
@@ -590,10 +591,10 @@ macro_rules! pin_init {
 ///
 /// ```rust
 /// # #![feature(new_uninit)]
-/// use kernel::{init::{self, PinInit}, error::Error};
+/// use kernel::{alloc::KBox, init::{self, PinInit}, error::Error};
 /// #[pin_data]
 /// struct BigBuf {
-///     big: Box<[u8; 1024 * 1024 * 1024]>,
+///     big: KBox<[u8; 1024 * 1024 * 1024]>,
 ///     small: [u8; 1024 * 1024],
 ///     ptr: *mut u8,
 /// }
@@ -601,7 +602,7 @@ macro_rules! pin_init {
 /// impl BigBuf {
 ///     fn new() -> impl PinInit<Self, Error> {
 ///         try_pin_init!(Self {
-///             big: Box::init(init::zeroed(), GFP_KERNEL)?,
+///             big: KBox::init(init::zeroed(), GFP_KERNEL)?,
 ///             small: [0; 1024 * 1024],
 ///             ptr: core::ptr::null_mut(),
 ///         }? Error)
@@ -693,16 +694,16 @@ macro_rules! init {
 /// # Examples
 ///
 /// ```rust
-/// use kernel::{init::{PinInit, zeroed}, error::Error};
+/// use kernel::{alloc::KBox, init::{PinInit, zeroed}, error::Error};
 /// struct BigBuf {
-///     big: Box<[u8; 1024 * 1024 * 1024]>,
+///     big: KBox<[u8; 1024 * 1024 * 1024]>,
 ///     small: [u8; 1024 * 1024],
 /// }
 ///
 /// impl BigBuf {
 ///     fn new() -> impl Init<Self, Error> {
 ///         try_init!(Self {
-///             big: Box::init(zeroed(), GFP_KERNEL)?,
+///             big: KBox::init(zeroed(), GFP_KERNEL)?,
 ///             small: [0; 1024 * 1024],
 ///         }? Error)
 ///     }
@@ -745,8 +746,8 @@ macro_rules! try_init {
 /// A pin-initializer for the type `T`.
 ///
 /// To use this initializer, you will need a suitable memory location that can hold a `T`. This can
-/// be [`Box<T>`], [`Arc<T>`], [`UniqueArc<T>`] or even the stack (see [`stack_pin_init!`]). Use the
-/// [`InPlaceInit::pin_init`] function of a smart pointer like [`Arc<T>`] on this.
+/// be [`KBox<T>`], [`Arc<T>`], [`UniqueArc<T>`] or even the stack (see [`stack_pin_init!`]). Use
+/// the [`InPlaceInit::pin_init`] function of a smart pointer like [`Arc<T>`] on this.
 ///
 /// Also see the [module description](self).
 ///
@@ -825,7 +826,7 @@ fn pin_chain<F>(self, f: F) -> ChainPinInit<Self, F, T, E>
 }
 
 /// An initializer returned by [`PinInit::pin_chain`].
-pub struct ChainPinInit<I, F, T: ?Sized, E>(I, F, __internal::Invariant<(E, Box<T>)>);
+pub struct ChainPinInit<I, F, T: ?Sized, E>(I, F, __internal::Invariant<(E, KBox<T>)>);
 
 // SAFETY: The `__pinned_init` function is implemented such that it
 // - returns `Ok(())` on successful initialization,
@@ -854,8 +855,8 @@ unsafe fn __pinned_init(self, slot: *mut T) -> Result<(), E> {
 /// An initializer for `T`.
 ///
 /// To use this initializer, you will need a suitable memory location that can hold a `T`. This can
-/// be [`Box<T>`], [`Arc<T>`], [`UniqueArc<T>`] or even the stack (see [`stack_pin_init!`]). Use the
-/// [`InPlaceInit::init`] function of a smart pointer like [`Arc<T>`] on this. Because
+/// be [`KBox<T>`], [`Arc<T>`], [`UniqueArc<T>`] or even the stack (see [`stack_pin_init!`]). Use
+/// the [`InPlaceInit::init`] function of a smart pointer like [`Arc<T>`] on this. Because
 /// [`PinInit<T, E>`] is a super trait, you can use every function that takes it as well.
 ///
 /// Also see the [module description](self).
@@ -927,7 +928,7 @@ fn chain<F>(self, f: F) -> ChainInit<Self, F, T, E>
 }
 
 /// An initializer returned by [`Init::chain`].
-pub struct ChainInit<I, F, T: ?Sized, E>(I, F, __internal::Invariant<(E, Box<T>)>);
+pub struct ChainInit<I, F, T: ?Sized, E>(I, F, __internal::Invariant<(E, KBox<T>)>);
 
 // SAFETY: The `__init` function is implemented such that it
 // - returns `Ok(())` on successful initialization,
@@ -1013,8 +1014,9 @@ pub fn uninit<T, E>() -> impl Init<MaybeUninit<T>, E> {
 /// # Examples
 ///
 /// ```rust
-/// use kernel::{error::Error, init::init_array_from_fn};
-/// let array: Box<[usize; 1_000]> = Box::init::<Error>(init_array_from_fn(|i| i), GFP_KERNEL).unwrap();
+/// use kernel::{alloc::KBox, error::Error, init::init_array_from_fn};
+/// let array: KBox<[usize; 1_000]> =
+///     KBox::init::<Error>(init_array_from_fn(|i| i), GFP_KERNEL).unwrap();
 /// assert_eq!(array.len(), 1_000);
 /// ```
 pub fn init_array_from_fn<I, const N: usize, T, E>(
@@ -1351,7 +1353,7 @@ macro_rules! impl_zeroable {
     //
     // In this case we are allowed to use `T: ?Sized`, since all zeros is the `None` variant.
     {<T: ?Sized>} Option<NonNull<T>>,
-    {<T: ?Sized>} Option<Box<T>>,
+    {<T: ?Sized>} Option<KBox<T>>,
 
     // SAFETY: `null` pointer is valid.
     //
diff --git a/rust/kernel/init/__internal.rs b/rust/kernel/init/__internal.rs
index db3372619ecd..dfb2204918c7 100644
--- a/rust/kernel/init/__internal.rs
+++ b/rust/kernel/init/__internal.rs
@@ -102,7 +102,7 @@ fn make_closure<F, O, E>(self, f: F) -> F
     }
 }
 
-pub struct AllData<T: ?Sized>(PhantomData<fn(Box<T>) -> Box<T>>);
+pub struct AllData<T: ?Sized>(PhantomData<fn(KBox<T>) -> KBox<T>>);
 
 impl<T: ?Sized> Clone for AllData<T> {
     fn clone(&self) -> Self {
diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index 3673496c2363..b5c84995d7d2 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -16,13 +16,12 @@
 //! [`Arc`]: https://doc.rust-lang.org/std/sync/struct.Arc.html
 
 use crate::{
-    alloc::{box_ext::BoxExt, AllocError, Flags},
+    alloc::{AllocError, Flags, KBox},
     error::{self, Error},
     init::{self, InPlaceInit, Init, PinInit},
     try_init,
     types::{ForeignOwnable, Opaque},
 };
-use alloc::boxed::Box;
 use core::{
     alloc::Layout,
     fmt,
@@ -203,11 +202,11 @@ pub fn new(contents: T, flags: Flags) -> Result<Self, AllocError> {
             data: contents,
         };
 
-        let inner = <Box<_> as BoxExt<_>>::new(value, flags)?;
+        let inner = KBox::new(value, flags)?;
 
         // SAFETY: We just created `inner` with a reference count of 1, which is owned by the new
         // `Arc` object.
-        Ok(unsafe { Self::from_inner(Box::leak(inner).into()) })
+        Ok(unsafe { Self::from_inner(KBox::leak(inner).into()) })
     }
 
     /// Use the given initializer to in-place initialize a `T`.
@@ -422,8 +421,8 @@ fn drop(&mut self) {
         if is_zero {
             // The count reached zero, we must free the memory.
             //
-            // SAFETY: The pointer was initialised from the result of `Box::leak`.
-            unsafe { drop(Box::from_raw(self.ptr.as_ptr())) };
+            // SAFETY: The pointer was initialised from the result of `KBox::leak`.
+            unsafe { drop(KBox::from_raw(self.ptr.as_ptr())) };
         }
     }
 }
@@ -668,7 +667,7 @@ pub fn new(value: T, flags: Flags) -> Result<Self, AllocError> {
     /// Tries to allocate a new [`UniqueArc`] instance whose contents are not initialised yet.
     pub fn new_uninit(flags: Flags) -> Result<UniqueArc<MaybeUninit<T>>, AllocError> {
         // INVARIANT: The refcount is initialised to a non-zero value.
-        let inner = Box::try_init::<AllocError>(
+        let inner = KBox::try_init::<AllocError>(
             try_init!(ArcInner {
                 // SAFETY: There are no safety requirements for this FFI call.
                 refcount: Opaque::new(unsafe { bindings::REFCOUNT_INIT(1) }),
@@ -678,8 +677,8 @@ pub fn new_uninit(flags: Flags) -> Result<UniqueArc<MaybeUninit<T>>, AllocError>
         )?;
         Ok(UniqueArc {
             // INVARIANT: The newly-created object has a refcount of 1.
-            // SAFETY: The pointer from the `Box` is valid.
-            inner: unsafe { Arc::from_inner(Box::leak(inner).into()) },
+            // SAFETY: The pointer from the `KBox` is valid.
+            inner: unsafe { Arc::from_inner(KBox::leak(inner).into()) },
         })
     }
 }
diff --git a/rust/kernel/sync/condvar.rs b/rust/kernel/sync/condvar.rs
index 2b306afbe56d..700dcda58fb1 100644
--- a/rust/kernel/sync/condvar.rs
+++ b/rust/kernel/sync/condvar.rs
@@ -44,6 +44,7 @@ macro_rules! new_condvar {
 /// The following is an example of using a condvar with a mutex:
 ///
 /// ```
+/// use kernel::alloc::KBox;
 /// use kernel::sync::{new_condvar, new_mutex, CondVar, Mutex};
 ///
 /// #[pin_data]
@@ -70,8 +71,8 @@ macro_rules! new_condvar {
 /// }
 ///
 /// /// Allocates a new boxed `Example`.
-/// fn new_example() -> Result<Pin<Box<Example>>> {
-///     Box::pin_init(pin_init!(Example {
+/// fn new_example() -> Result<Pin<KBox<Example>>> {
+///     KBox::pin_init(pin_init!(Example {
 ///         value <- new_mutex!(0),
 ///         value_changed <- new_condvar!(),
 ///     }), GFP_KERNEL)
diff --git a/rust/kernel/sync/lock/mutex.rs b/rust/kernel/sync/lock/mutex.rs
index 30632070ee67..e19481cf0a2c 100644
--- a/rust/kernel/sync/lock/mutex.rs
+++ b/rust/kernel/sync/lock/mutex.rs
@@ -34,6 +34,7 @@ macro_rules! new_mutex {
 /// contains an inner struct (`Inner`) that is protected by a mutex.
 ///
 /// ```
+/// use kernel::alloc::KBox;
 /// use kernel::sync::{new_mutex, Mutex};
 ///
 /// struct Inner {
@@ -58,7 +59,7 @@ macro_rules! new_mutex {
 /// }
 ///
 /// // Allocate a boxed `Example`.
-/// let e = Box::pin_init(Example::new(), GFP_KERNEL)?;
+/// let e = KBox::pin_init(Example::new(), GFP_KERNEL)?;
 /// assert_eq!(e.c, 10);
 /// assert_eq!(e.d.lock().a, 20);
 /// assert_eq!(e.d.lock().b, 30);
diff --git a/rust/kernel/sync/lock/spinlock.rs b/rust/kernel/sync/lock/spinlock.rs
index ea5c5bc1ce12..dfb74dfefafe 100644
--- a/rust/kernel/sync/lock/spinlock.rs
+++ b/rust/kernel/sync/lock/spinlock.rs
@@ -32,6 +32,7 @@ macro_rules! new_spinlock {
 /// contains an inner struct (`Inner`) that is protected by a spinlock.
 ///
 /// ```
+/// use kernel::alloc::KBox;
 /// use kernel::sync::{new_spinlock, SpinLock};
 ///
 /// struct Inner {
@@ -56,7 +57,7 @@ macro_rules! new_spinlock {
 /// }
 ///
 /// // Allocate a boxed `Example`.
-/// let e = Box::pin_init(Example::new(), GFP_KERNEL)?;
+/// let e = KBox::pin_init(Example::new(), GFP_KERNEL)?;
 /// assert_eq!(e.c, 10);
 /// assert_eq!(e.d.lock().a, 20);
 /// assert_eq!(e.d.lock().b, 30);
diff --git a/rust/kernel/workqueue.rs b/rust/kernel/workqueue.rs
index 1cec63a2aea8..e1a1606267ed 100644
--- a/rust/kernel/workqueue.rs
+++ b/rust/kernel/workqueue.rs
@@ -130,7 +130,7 @@
 //!
 //! C header: [`include/linux/workqueue.h`](srctree/include/linux/workqueue.h)
 
-use crate::alloc::{AllocError, Flags};
+use crate::alloc::{AllocError, Flags, KBox};
 use crate::{prelude::*, sync::Arc, sync::LockClassKey, types::Opaque};
 use core::marker::PhantomData;
 
@@ -216,7 +216,7 @@ pub fn try_spawn<T: 'static + Send + FnOnce()>(
             func: Some(func),
         });
 
-        self.enqueue(Box::pin_init(init, flags).map_err(|_| AllocError)?);
+        self.enqueue(KBox::pin_init(init, flags).map_err(|_| AllocError)?);
         Ok(())
     }
 }
@@ -239,9 +239,9 @@ fn project(self: Pin<&mut Self>) -> &mut Option<T> {
 }
 
 impl<T: FnOnce()> WorkItem for ClosureWork<T> {
-    type Pointer = Pin<Box<Self>>;
+    type Pointer = Pin<KBox<Self>>;
 
-    fn run(mut this: Pin<Box<Self>>) {
+    fn run(mut this: Pin<KBox<Self>>) {
         if let Some(func) = this.as_mut().project().take() {
             (func)()
         }
@@ -297,7 +297,7 @@ unsafe fn __enqueue<F>(self, queue_work_on: F) -> Self::EnqueueOutput
 
 /// Defines the method that should be called directly when a work item is executed.
 ///
-/// This trait is implemented by `Pin<Box<T>>` and [`Arc<T>`], and is mainly intended to be
+/// This trait is implemented by `Pin<KBox<T>>` and [`Arc<T>`], and is mainly intended to be
 /// implemented for smart pointer types. For your own structs, you would implement [`WorkItem`]
 /// instead. The [`run`] method on this trait will usually just perform the appropriate
 /// `container_of` translation and then call into the [`run`][WorkItem::run] method from the
@@ -329,7 +329,7 @@ pub unsafe trait WorkItemPointer<const ID: u64>: RawWorkItem<ID> {
 /// This trait is used when the `work_struct` field is defined using the [`Work`] helper.
 pub trait WorkItem<const ID: u64 = 0> {
     /// The pointer type that this struct is wrapped in. This will typically be `Arc<Self>` or
-    /// `Pin<Box<Self>>`.
+    /// `Pin<KBox<Self>>`.
     type Pointer: WorkItemPointer<ID>;
 
     /// The method that should be called when this work item is executed.
@@ -563,7 +563,7 @@ unsafe fn __enqueue<F>(self, queue_work_on: F) -> Self::EnqueueOutput
     }
 }
 
-unsafe impl<T, const ID: u64> WorkItemPointer<ID> for Pin<Box<T>>
+unsafe impl<T, const ID: u64> WorkItemPointer<ID> for Pin<KBox<T>>
 where
     T: WorkItem<ID, Pointer = Self>,
     T: HasWork<T, ID>,
@@ -574,7 +574,7 @@ unsafe impl<T, const ID: u64> WorkItemPointer<ID> for Pin<Box<T>>
         // SAFETY: This computes the pointer that `__enqueue` got from `Arc::into_raw`.
         let ptr = unsafe { T::work_container_of(ptr) };
         // SAFETY: This pointer comes from `Arc::into_raw` and we've been given back ownership.
-        let boxed = unsafe { Box::from_raw(ptr) };
+        let boxed = unsafe { KBox::from_raw(ptr) };
         // SAFETY: The box was already pinned when it was enqueued.
         let pinned = unsafe { Pin::new_unchecked(boxed) };
 
@@ -582,7 +582,7 @@ unsafe impl<T, const ID: u64> WorkItemPointer<ID> for Pin<Box<T>>
     }
 }
 
-unsafe impl<T, const ID: u64> RawWorkItem<ID> for Pin<Box<T>>
+unsafe impl<T, const ID: u64> RawWorkItem<ID> for Pin<KBox<T>>
 where
     T: WorkItem<ID, Pointer = Self>,
     T: HasWork<T, ID>,
@@ -596,9 +596,9 @@ unsafe fn __enqueue<F>(self, queue_work_on: F) -> Self::EnqueueOutput
         // SAFETY: We're not going to move `self` or any of its fields, so its okay to temporarily
         // remove the `Pin` wrapper.
         let boxed = unsafe { Pin::into_inner_unchecked(self) };
-        let ptr = Box::into_raw(boxed);
+        let ptr = KBox::into_raw(boxed);
 
-        // SAFETY: Pointers into a `Box` point at a valid value.
+        // SAFETY: Pointers into a `KBox` point at a valid value.
         let work_ptr = unsafe { T::raw_get_work(ptr) };
         // SAFETY: `raw_get_work` returns a pointer to a valid value.
         let work_ptr = unsafe { Work::raw_get(work_ptr) };
-- 
2.45.2

[PATCH 12/20] rust: alloc: remove `BoxExt` extension

[Danilo Krummrich]

Now that all existing `Box` users were moved to `KBox`, remove the
`BoxExt` extension.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs         |  1 -
 rust/kernel/alloc/box_ext.rs | 51 ------------------------------------
 rust/kernel/init.rs          | 34 +-----------------------
 rust/kernel/lib.rs           |  1 -
 rust/kernel/prelude.rs       |  4 +--
 rust/kernel/types.rs         | 23 ----------------
 6 files changed, 3 insertions(+), 111 deletions(-)
 delete mode 100644 rust/kernel/alloc/box_ext.rs

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index ff90cefad0ea..882a65212653 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -4,7 +4,6 @@
 
 #[cfg(not(any(test, testlib)))]
 pub mod allocator;
-pub mod box_ext;
 pub mod kbox;
 pub mod vec_ext;
 
diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs
deleted file mode 100644
index 1aeae02c147e..000000000000
--- a/rust/kernel/alloc/box_ext.rs
+++ /dev/null
@@ -1,51 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0
-
-//! Extensions to [`Box`] for fallible allocations.
-
-use super::{AllocError, Flags};
-use alloc::boxed::Box;
-use core::mem::MaybeUninit;
-
-/// Extensions to [`Box`].
-pub trait BoxExt<T>: Sized {
-    /// Allocates a new box.
-    ///
-    /// The allocation may fail, in which case an error is returned.
-    fn new(x: T, flags: Flags) -> Result<Self, AllocError>;
-
-    /// Allocates a new uninitialised box.
-    ///
-    /// The allocation may fail, in which case an error is returned.
-    fn new_uninit(flags: Flags) -> Result<Box<MaybeUninit<T>>, AllocError>;
-}
-
-impl<T> BoxExt<T> for Box<T> {
-    fn new(x: T, flags: Flags) -> Result<Self, AllocError> {
-        let b = <Self as BoxExt<_>>::new_uninit(flags)?;
-        Ok(Box::write(b, x))
-    }
-
-    #[cfg(any(test, testlib))]
-    fn new_uninit(_flags: Flags) -> Result<Box<MaybeUninit<T>>, AllocError> {
-        Ok(Box::new_uninit())
-    }
-
-    #[cfg(not(any(test, testlib)))]
-    fn new_uninit(flags: Flags) -> Result<Box<MaybeUninit<T>>, AllocError> {
-        let ptr = if core::mem::size_of::<MaybeUninit<T>>() == 0 {
-            core::ptr::NonNull::dangling()
-        } else {
-            let alloc: &dyn super::Allocator = &super::allocator::Kmalloc;
-            let layout = core::alloc::Layout::new::<MaybeUninit<T>>();
-
-            // SAFETY: Memory is being allocated (first arg is null). The only other source of
-            // safety issues is sleeping on atomic context, which is addressed by klint. Lastly,
-            // the type is not a SZT (checked above).
-            alloc.alloc(layout, flags)?.cast()
-        };
-
-        // SAFETY: For non-zero-sized types, we allocate above using the global allocator. For
-        // zero-sized types, we use `NonNull::dangling`.
-        Ok(unsafe { Box::from_raw(ptr.as_ptr()) })
-    }
-}
diff --git a/rust/kernel/init.rs b/rust/kernel/init.rs
index b386bafd5f95..f59f502c3e0b 100644
--- a/rust/kernel/init.rs
+++ b/rust/kernel/init.rs
@@ -212,12 +212,11 @@
 //! [`pin_init!`]: crate::pin_init!
 
 use crate::{
-    alloc::{box_ext::BoxExt, AllocError, Flags, KBox},
+    alloc::{AllocError, Flags, KBox},
     error::{self, Error},
     sync::UniqueArc,
     types::{Opaque, ScopeGuard},
 };
-use alloc::boxed::Box;
 use core::{
     cell::UnsafeCell,
     convert::Infallible,
@@ -590,7 +589,6 @@ macro_rules! pin_init {
 /// # Examples
 ///
 /// ```rust
-/// # #![feature(new_uninit)]
 /// use kernel::{alloc::KBox, init::{self, PinInit}, error::Error};
 /// #[pin_data]
 /// struct BigBuf {
@@ -1155,36 +1153,6 @@ fn init<E>(init: impl Init<T, E>, flags: Flags) -> error::Result<Self>
     }
 }
 
-impl<T> InPlaceInit<T> for Box<T> {
-    #[inline]
-    fn try_pin_init<E>(init: impl PinInit<T, E>, flags: Flags) -> Result<Pin<Self>, E>
-    where
-        E: From<AllocError>,
-    {
-        let mut this = <Box<_> as BoxExt<_>>::new_uninit(flags)?;
-        let slot = this.as_mut_ptr();
-        // SAFETY: When init errors/panics, slot will get deallocated but not dropped,
-        // slot is valid and will not be moved, because we pin it later.
-        unsafe { init.__pinned_init(slot)? };
-        // SAFETY: All fields have been initialized.
-        Ok(unsafe { this.assume_init() }.into())
-    }
-
-    #[inline]
-    fn try_init<E>(init: impl Init<T, E>, flags: Flags) -> Result<Self, E>
-    where
-        E: From<AllocError>,
-    {
-        let mut this = <Box<_> as BoxExt<_>>::new_uninit(flags)?;
-        let slot = this.as_mut_ptr();
-        // SAFETY: When init errors/panics, slot will get deallocated but not dropped,
-        // slot is valid.
-        unsafe { init.__init(slot)? };
-        // SAFETY: All fields have been initialized.
-        Ok(unsafe { this.assume_init() })
-    }
-}
-
 impl<T> InPlaceInit<T> for KBox<T> {
     #[inline]
     fn try_pin_init<E>(init: impl PinInit<T, E>, flags: Flags) -> Result<Pin<Self>, E>
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index fbd91a48ff8b..f119bbde955b 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -14,7 +14,6 @@
 #![no_std]
 #![feature(coerce_unsized)]
 #![feature(dispatch_from_dyn)]
-#![feature(new_uninit)]
 #![feature(receiver_trait)]
 #![feature(unsize)]
 
diff --git a/rust/kernel/prelude.rs b/rust/kernel/prelude.rs
index d75c14234133..20112233d750 100644
--- a/rust/kernel/prelude.rs
+++ b/rust/kernel/prelude.rs
@@ -14,10 +14,10 @@
 #[doc(no_inline)]
 pub use core::pin::Pin;
 
-pub use crate::alloc::{box_ext::BoxExt, flags::*, vec_ext::VecExt, KBox};
+pub use crate::alloc::{flags::*, vec_ext::VecExt, KBox};
 
 #[doc(no_inline)]
-pub use alloc::{boxed::Box, vec::Vec};
+pub use alloc::vec::Vec;
 
 #[doc(no_inline)]
 pub use macros::{module, pin_data, pinned_drop, vtable, Zeroable};
diff --git a/rust/kernel/types.rs b/rust/kernel/types.rs
index 939ec27c584d..0b2a3ce538a6 100644
--- a/rust/kernel/types.rs
+++ b/rust/kernel/types.rs
@@ -4,7 +4,6 @@
 
 use crate::alloc::KBox;
 use crate::init::{self, PinInit};
-use alloc::boxed::Box;
 use core::{
     cell::UnsafeCell,
     marker::{PhantomData, PhantomPinned},
@@ -68,28 +67,6 @@ unsafe fn try_from_foreign(ptr: *const core::ffi::c_void) -> Option<Self> {
     }
 }
 
-impl<T: 'static> ForeignOwnable for Box<T> {
-    type Borrowed<'a> = &'a T;
-
-    fn into_foreign(self) -> *const core::ffi::c_void {
-        Box::into_raw(self) as _
-    }
-
-    unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> &'a T {
-        // SAFETY: The safety requirements for this function ensure that the object is still alive,
-        // so it is safe to dereference the raw pointer.
-        // The safety requirements of `from_foreign` also ensure that the object remains alive for
-        // the lifetime of the returned value.
-        unsafe { &*ptr.cast() }
-    }
-
-    unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self {
-        // SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous
-        // call to `Self::into_foreign`.
-        unsafe { Box::from_raw(ptr as _) }
-    }
-}
-
 impl<T: 'static> ForeignOwnable for KBox<T> {
     type Borrowed<'a> = &'a T;
 
-- 
2.45.2

[PATCH 13/20] rust: alloc: implement `KVec`

[Danilo Krummrich]

`KVec` provides a contiguous growable array type (such as `Vec`) with
contents allocated with the kernel's allocators (e.g. `Kmalloc`,
`Vmalloc` or `KVmalloc`).

In contrast to `Vec`, `KVec` considers the kernel's GFP flags for all
appropriate functions, always reports allocation failures through
`Result<_, AllocError>` and remains independent from unstable features.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs      |   2 +
 rust/kernel/alloc/kbox.rs |  16 +-
 rust/kernel/alloc/kvec.rs | 605 ++++++++++++++++++++++++++++++++++++++
 rust/kernel/prelude.rs    |   2 +-
 4 files changed, 623 insertions(+), 2 deletions(-)
 create mode 100644 rust/kernel/alloc/kvec.rs

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 882a65212653..3a0195d23bb4 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -5,6 +5,7 @@
 #[cfg(not(any(test, testlib)))]
 pub mod allocator;
 pub mod kbox;
+pub mod kvec;
 pub mod vec_ext;
 
 #[cfg(any(test, testlib))]
@@ -14,6 +15,7 @@
 pub use self::allocator_test as allocator;
 
 pub use self::kbox::KBox;
+pub use self::kvec::KVec;
 
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs
index 69976fd1d518..3cb2d12f7c39 100644
--- a/rust/kernel/alloc/kbox.rs
+++ b/rust/kernel/alloc/kbox.rs
@@ -2,7 +2,7 @@
 
 //! Implementation of [`KBox`].
 
-use super::{allocator::Kmalloc, AllocError, Allocator, Flags};
+use super::{allocator::Kmalloc, AllocError, Allocator, Flags, KVec};
 use core::fmt;
 use core::mem::ManuallyDrop;
 use core::mem::MaybeUninit;
@@ -120,6 +120,20 @@ pub fn into_pin(b: Self) -> Pin<Self>
     }
 }
 
+impl<T, A, const N: usize> KBox<[T; N], A>
+where
+    A: Allocator,
+{
+    /// Convert a `KBox<[T], A>` to a `KVec<T, A>`.
+    pub fn into_vec(self) -> KVec<T, A> {
+        let len = self.len();
+        unsafe {
+            let (ptr, alloc) = self.into_raw_alloc();
+            KVec::from_raw_parts_alloc(ptr as _, len, len, alloc)
+        }
+    }
+}
+
 impl<T, A> KBox<MaybeUninit<T>, A>
 where
     A: Allocator,
diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
new file mode 100644
index 000000000000..7ec898657832
--- /dev/null
+++ b/rust/kernel/alloc/kvec.rs
@@ -0,0 +1,605 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Implementation of [`KVec`].
+
+use super::{allocator::Kmalloc, AllocError, Allocator, Flags};
+use crate::types::Unique;
+use core::{
+    fmt,
+    mem::{ManuallyDrop, MaybeUninit},
+    ops::Deref,
+    ops::DerefMut,
+    ops::Index,
+    ops::IndexMut,
+    ptr, slice,
+    slice::SliceIndex,
+};
+
+/// Create a [`KVec`] containing the arguments.
+///
+/// # Examples
+///
+/// ```
+/// use kernel::alloc::{flags::*, KVec};
+///
+/// let mut v = kernel::kvec![];
+/// v.push(1, GFP_KERNEL).unwrap();
+/// assert_eq!(v, [1]);
+///
+/// let mut v = kernel::kvec![1; 3]?;
+/// v.push(4, GFP_KERNEL).unwrap();
+/// assert_eq!(v, [1, 1, 1, 4]);
+///
+/// let mut v = kernel::kvec![1, 2, 3]?;
+/// v.push(4, GFP_KERNEL).unwrap();
+/// assert_eq!(v, [1, 2, 3, 4]);
+///
+/// # Ok::<(), Error>(())
+/// ```
+#[macro_export]
+macro_rules! kvec {
+    () => (
+        {
+            $crate::alloc::KVec::new()
+        }
+    );
+    ($elem:expr; $n:expr) => (
+        {
+            $crate::alloc::KVec::from_elem(
+                $elem, $n,
+                $crate::alloc::allocator::Kmalloc,
+                GFP_KERNEL
+            )
+        }
+    );
+    ($($x:expr),+ $(,)?) => (
+        {
+            match $crate::alloc::KBox::new([$($x),+], GFP_KERNEL) {
+                Ok(b) => Ok($crate::alloc::KBox::into_vec(b)),
+                Err(e) => Err(e),
+            }
+        }
+    );
+}
+
+/// The kernel's `Vec` type named [`KVec`].
+///
+/// A contiguous growable array type with contents allocated with the kernel's allocators (e.g.
+/// `Kmalloc`, `Vmalloc` or `KVmalloc`, written `KVec<T, A>`.
+///
+/// For non-zero-sized values, a [`KVec`] will use the given allocator `A` for its allocation. If
+/// no specific `Allocator` is requested, [`KVec`] will default to `Kmalloc`.
+///
+/// For zero-sized types the [`KVec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.
+///
+/// Generally, [`KVec`] consists of a pointer that represents the vector's backing buffer, the
+/// capacity of the vector (the number of elements that currently fit into the vector), it's length
+/// (the number of elements that are currently stored in the vector) and the `Allocator` used to
+/// allocate (and free) the backing buffer.
+///
+/// A [`KVec`] can be deconstructed into and (re-)constructed from it's previously named raw parts
+/// and manually modified.
+///
+/// [`KVec`]'s backing buffer gets, if required, automatically increased (re-allocated) when
+/// elements are added to the vector.
+///
+/// # Invariants
+///
+/// The [`KVec`] backing buffer's pointer always properly aligned and either points to memory
+/// allocated with `A` or, for zero-sized types, is a dangling pointer.
+///
+/// The length of the vector always represents the exact number of elements stored in the vector.
+///
+/// The capacity of the vector always represents the absolute number of elements that can be stored
+/// within the vector without re-allocation. However, it is legal for the backing buffer to be
+/// larger than `size_of<T>` times the capacity.
+///
+/// The `Allocator` of the vector is the exact allocator the backing buffer was allocated with (and
+/// must be freed with).
+pub struct KVec<T, A: Allocator = Kmalloc> {
+    ptr: Unique<T>,
+    /// Never used for ZSTs; it's `capacity()`'s responsibility to return usize::MAX in that case.
+    ///
+    /// # Safety
+    ///
+    /// `cap` must be in the `0..=isize::MAX` range.
+    cap: usize,
+    len: usize,
+    alloc: A,
+}
+
+impl<T> KVec<T> {
+    /// Create a new empty `KVec` with no memory allocated yet.
+    #[inline]
+    pub const fn new() -> Self {
+        Self::new_alloc(Kmalloc)
+    }
+
+    /// Creates a new [`KVec`] instance with at least the given capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{flags::*, KVec};
+    ///
+    /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?;
+    ///
+    /// assert!(v.capacity() >= 20);
+    /// # Ok::<(), Error>(())
+    /// ```
+    #[inline]
+    pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {
+        Self::with_capacity_alloc(capacity, Kmalloc, flags)
+    }
+}
+
+impl<T, A> KVec<T, A>
+where
+    A: Allocator,
+{
+    #[inline]
+    fn is_zst() -> bool {
+        core::mem::size_of::<T>() == 0
+    }
+
+    fn buffer_size(capacity: usize) -> Result<usize, AllocError> {
+        if Self::is_zst() {
+            Ok(0)
+        } else {
+            capacity
+                .checked_mul(core::mem::size_of::<T>())
+                .ok_or(AllocError)
+        }
+    }
+
+    /// Returns a reference to the underlying allocator.
+    #[inline]
+    pub fn allocator(&self) -> &A {
+        &self.alloc
+    }
+
+    /// Returns the total number of elements the vector can hold without
+    /// reallocating.
+    pub fn capacity(&self) -> usize {
+        if Self::is_zst() {
+            usize::MAX
+        } else {
+            self.cap
+        }
+    }
+
+    /// Returns the number of elements in the vector, also referred to
+    /// as its 'length'.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.len
+    }
+
+    /// Forces the length of the vector to new_len.
+    ///
+    /// # Safety
+    ///
+    /// - `new_len` must be less than or equal to [`Self::capacity()`].
+    /// - The elements at `old_len..new_len` must be initialized.
+    #[inline]
+    pub unsafe fn set_len(&mut self, new_len: usize) {
+        self.len = new_len;
+    }
+
+    /// Extracts a slice containing the entire vector.
+    ///
+    /// Equivalent to `&s[..]`.
+    #[inline]
+    pub fn as_slice(&self) -> &[T] {
+        self
+    }
+
+    /// Extracts a mutable slice of the entire vector.
+    ///
+    /// Equivalent to `&mut s[..]`.
+    #[inline]
+    pub fn as_mut_slice(&mut self) -> &mut [T] {
+        self
+    }
+
+    /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
+    /// raw pointer valid for zero sized reads if the vector didn't allocate.
+    #[inline]
+    pub fn as_mut_ptr(&self) -> *mut T {
+        self.ptr.as_ptr()
+    }
+
+    /// Returns a raw pointer to the slice's buffer.
+    #[inline]
+    pub fn as_ptr(&self) -> *const T {
+        self.as_mut_ptr()
+    }
+
+    /// Returns `true` if the vector contains no elements.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{flags::*, KVec};
+    ///
+    /// let mut v = KVec::new();
+    /// assert!(v.is_empty());
+    ///
+    /// v.push(1, GFP_KERNEL);
+    /// assert!(!v.is_empty());
+    /// ```
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Like `new`, but parameterized over the choice of allocator for the returned `KVec`.
+    #[inline]
+    pub const fn new_alloc(alloc: A) -> Self {
+        Self {
+            ptr: Unique::dangling(),
+            cap: 0,
+            len: 0,
+            alloc,
+        }
+    }
+
+    fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
+        // Note:
+        // This method is not implemented in terms of `split_at_spare_mut`,
+        // to prevent invalidation of pointers to the buffer.
+        unsafe {
+            slice::from_raw_parts_mut(
+                self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
+                self.capacity() - self.len,
+            )
+        }
+    }
+
+    /// Appends an element to the back of the [`KVec`] instance.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{flags::*, KVec};
+    ///
+    /// let mut v = KVec::new();
+    /// v.push(1, GFP_KERNEL)?;
+    /// assert_eq!(&v, &[1]);
+    ///
+    /// v.push(2, GFP_KERNEL)?;
+    /// assert_eq!(&v, &[1, 2]);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
+        KVec::reserve(self, 1, flags)?;
+        let s = self.spare_capacity_mut();
+        s[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.
+        unsafe { self.set_len(self.len() + 1) };
+        Ok(())
+    }
+
+    /// Creates a new [`KVec`] instance with at least the given capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{allocator::Kmalloc, flags::*, KVec};
+    ///
+    /// let v = KVec::<u32, _>::with_capacity_alloc(20, Kmalloc, GFP_KERNEL)?;
+    ///
+    /// assert!(v.capacity() >= 20);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn with_capacity_alloc(
+        capacity: usize,
+        alloc: A,
+        flags: Flags,
+    ) -> Result<Self, AllocError> {
+        let mut v = KVec::new_alloc(alloc);
+
+        Self::reserve(&mut v, capacity, flags)?;
+
+        Ok(v)
+    }
+
+    /// Pushes clones of the elements of slice into the [`KVec`] instance.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{allocator::Kmalloc, flags::*, KVec};
+    ///
+    /// let mut v = KVec::new_alloc(Kmalloc);
+    /// v.push(1, GFP_KERNEL)?;
+    ///
+    /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?;
+    /// assert_eq!(&v, &[1, 20, 30, 40]);
+    ///
+    /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?;
+    /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError>
+    where
+        T: Clone,
+    {
+        self.reserve(other.len(), flags)?;
+        for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) {
+            slot.write(item.clone());
+        }
+
+        // SAFETY: We just initialised the `other.len()` spare entries, so it is safe to increase
+        // the length by the same amount. We also know that the new length is <= capacity because
+        // of the previous call to `reserve` above.
+        unsafe { self.set_len(self.len() + other.len()) };
+        Ok(())
+    }
+
+    /// Creates a KVec<T, A> directly from a pointer, a length, a capacity, and an allocator.
+    ///
+    /// # Safety
+    ///
+    /// This is highly unsafe, due to the number of invariants that aren’t checked:
+    ///
+    /// - `ptr` must be currently allocated via the given allocator `alloc`.
+    /// - `T` needs to have the same alignment as what `ptr` was allocated with. (`T` having a less
+    ///   strict alignment is not sufficient, the alignment really needs to be equal to satisfy the
+    ///   `dealloc` requirement that memory must be allocated and deallocated with the same layout.)
+    /// - The size of `T` times the `capacity` (i.e. the allocated size in bytes) needs to be
+    ///   smaller or equal the size the pointer was allocated with.
+    /// - `length` needs to be less than or equal to `capacity`.
+    /// - The first `length` values must be properly initialized values of type `T`.
+    /// - The allocated size in bytes must be no larger than `isize::MAX`. See the safety
+    ///   documentation of `pointer::offset`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = kernel::kvec![1, 2, 3]?;
+    /// v.reserve(1, GFP_KERNEL)?;
+    ///
+    /// let (mut ptr, mut len, cap, alloc) = v.into_raw_parts_alloc();
+    ///
+    /// unsafe { ptr.add(len).write(4) };
+    /// len += 1;
+    ///
+    /// let v = unsafe { KVec::from_raw_parts_alloc(ptr, len, cap, alloc) };
+    ///
+    /// assert_eq!(v, [1, 2, 3, 4]);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub unsafe fn from_raw_parts_alloc(
+        ptr: *mut T,
+        length: usize,
+        capacity: usize,
+        alloc: A,
+    ) -> Self {
+        let cap = if Self::is_zst() { 0 } else { capacity };
+
+        Self {
+            ptr: unsafe { Unique::new_unchecked(ptr) },
+            cap,
+            len: length,
+            alloc,
+        }
+    }
+
+    /// Decomposes a `KVec<T, A>` into its raw components: (`pointer`, `length`, `capacity`,
+    /// `allocator`).
+    pub fn into_raw_parts_alloc(self) -> (*mut T, usize, usize, A) {
+        let me = ManuallyDrop::new(self);
+        let len = me.len();
+        let capacity = me.capacity();
+        let ptr = me.as_mut_ptr();
+        let alloc = unsafe { ptr::read(me.allocator()) };
+        (ptr, len, capacity, alloc)
+    }
+
+    /// Ensures that the capacity exceeds the length by at least `additional` elements.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{allocator::Kmalloc, flags::*, KVec};
+    ///
+    /// let mut v = KVec::new_alloc(Kmalloc);
+    /// v.push(1, GFP_KERNEL)?;
+    ///
+    /// v.reserve(10, GFP_KERNEL)?;
+    /// let cap = v.capacity();
+    /// assert!(cap >= 10);
+    ///
+    /// v.reserve(10, GFP_KERNEL)?;
+    /// let new_cap = v.capacity();
+    /// assert_eq!(new_cap, cap);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {
+        let len = self.len();
+        let cap = self.capacity();
+
+        if cap - len >= additional {
+            return Ok(());
+        }
+
+        if Self::is_zst() {
+            // The capacity is already `usize::MAX` for SZTs, we can't go higher.
+            return Err(AllocError);
+        }
+
+        // We know cap is <= `isize::MAX` because `Layout::array` fails if the resulting byte size
+        // is greater than `isize::MAX`. So the multiplication by two won't overflow.
+        let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?);
+        let layout = core::alloc::Layout::array::<T>(new_cap).map_err(|_| AllocError)?;
+
+        // We need to make sure that `ptr` is either NULL or comes from a previous call to
+        // `realloc_flags`. A `KVec<T, A>`'s `ptr` value is not guaranteed to be NULL and might be
+        // dangling after being created with `KVec::new`. Instead, we can rely on `KVec<T, A>`'s
+        // capacity to be zero if no memory has been allocated yet.
+        let ptr = if cap == 0 {
+            ptr::null_mut()
+        } else {
+            self.as_mut_ptr()
+        };
+
+        // SAFETY: `ptr` is valid because it's either NULL or comes from a previous call to
+        // `krealloc_aligned`. We also verified that the type is not a ZST.
+        let ptr = unsafe {
+            self.alloc
+                .realloc(ptr.cast(), Self::buffer_size(cap)?, layout, flags)
+        }?;
+
+        self.ptr = ptr.cast().into();
+        self.cap = new_cap;
+
+        Ok(())
+    }
+}
+
+impl<T: Clone, A: Allocator> KVec<T, A> {
+    /// Extend the vector by `n` clones of value.
+    pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> {
+        self.reserve(n, flags)?;
+
+        unsafe {
+            let mut ptr = self.as_mut_ptr().add(self.len());
+
+            // Write all elements except the last one
+            for _ in 1..n {
+                ptr::write(ptr, value.clone());
+                ptr = ptr.add(1);
+            }
+
+            if n > 0 {
+                // We can write the last element directly without cloning needlessly
+                ptr::write(ptr, value);
+            }
+        }
+
+        // SAFETY: `self.reserve` not bailing out with an error guarantees that we're not
+        // exceeding the capacity of this `KVec`.
+        unsafe { self.set_len(self.len() + n) };
+
+        Ok(())
+    }
+
+    /// Create a new `KVec<T, A> and extend it by `n` clones of value.
+    pub fn from_elem(value: T, n: usize, alloc: A, flags: Flags) -> Result<Self, AllocError> {
+        let mut v = Self::with_capacity_alloc(n, alloc, flags)?;
+
+        v.extend_with(n, value, flags)?;
+
+        Ok(v)
+    }
+}
+
+impl<T, A> Drop for KVec<T, A>
+where
+    A: Allocator,
+{
+    fn drop(&mut self) {
+        // SAFETY: We need to drop the vector's elements in place, before we free the backing
+        // memory.
+        unsafe {
+            core::ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut(
+                self.as_mut_ptr(),
+                self.len,
+            ))
+        };
+
+        // If `cap == 0` we never allocated any memory in the first place.
+        if self.cap != 0 {
+            // SAFETY: `self.ptr` was previously allocated with `self.alloc`.
+            unsafe { self.alloc.free(self.as_mut_ptr().cast()) };
+        }
+    }
+}
+
+impl<T> Default for KVec<T> {
+    #[inline]
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<T: fmt::Debug, A: Allocator> fmt::Debug for KVec<T, A> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(&**self, f)
+    }
+}
+
+impl<T, A> Deref for KVec<T, A>
+where
+    A: Allocator,
+{
+    type Target = [T];
+
+    #[inline]
+    fn deref(&self) -> &[T] {
+        unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
+    }
+}
+
+impl<T, A> DerefMut for KVec<T, A>
+where
+    A: Allocator,
+{
+    #[inline]
+    fn deref_mut(&mut self) -> &mut [T] {
+        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
+    }
+}
+
+impl<T: Eq, A> Eq for KVec<T, A> where A: Allocator {}
+
+impl<T, I: SliceIndex<[T]>, A> Index<I> for KVec<T, A>
+where
+    A: Allocator,
+{
+    type Output = I::Output;
+
+    #[inline]
+    fn index(&self, index: I) -> &Self::Output {
+        Index::index(&**self, index)
+    }
+}
+
+impl<T, I: SliceIndex<[T]>, A> IndexMut<I> for KVec<T, A>
+where
+    A: Allocator,
+{
+    #[inline]
+    fn index_mut(&mut self, index: I) -> &mut Self::Output {
+        IndexMut::index_mut(&mut **self, index)
+    }
+}
+
+macro_rules! __impl_slice_eq {
+    ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?) => {
+        impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs
+        where
+            T: PartialEq<U>,
+            $($ty: $bound)?
+        {
+            #[inline]
+            fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
+        }
+    }
+}
+
+__impl_slice_eq! { [A1: Allocator, A2: Allocator] KVec<T, A1>, KVec<U, A2> }
+__impl_slice_eq! { [A: Allocator] KVec<T, A>, &[U] }
+__impl_slice_eq! { [A: Allocator] KVec<T, A>, &mut [U] }
+__impl_slice_eq! { [A: Allocator] &[T], KVec<U, A> }
+__impl_slice_eq! { [A: Allocator] &mut [T], KVec<U, A> }
+__impl_slice_eq! { [A: Allocator] KVec<T, A>, [U] }
+__impl_slice_eq! { [A: Allocator] [T], KVec<U, A> }
+__impl_slice_eq! { [A: Allocator, const N: usize] KVec<T, A>, [U; N] }
+__impl_slice_eq! { [A: Allocator, const N: usize] KVec<T, A>, &[U; N] }
diff --git a/rust/kernel/prelude.rs b/rust/kernel/prelude.rs
index 20112233d750..0ee3f0d203e2 100644
--- a/rust/kernel/prelude.rs
+++ b/rust/kernel/prelude.rs
@@ -14,7 +14,7 @@
 #[doc(no_inline)]
 pub use core::pin::Pin;
 
-pub use crate::alloc::{flags::*, vec_ext::VecExt, KBox};
+pub use crate::alloc::{flags::*, vec_ext::VecExt, KBox, KVec};
 
 #[doc(no_inline)]
 pub use alloc::vec::Vec;
-- 
2.45.2

[PATCH 14/20] rust: alloc: implement `IntoIterator` for `KVec`

[Danilo Krummrich]

Implement `IntoIterator` for `KVec`, `KVec`'s `IntoIter` type, as well
as `Iterator` for `IntoIter`.

`KVec::into_iter` disassembles the `KVec` into its raw parts;
additionally, `IntoIter` keeps track of a separate pointer, which is
incremented correspondingsly as the iterator advances, while the length,
or the count of elements, is decremented.

This also means that `IntoIter` takes the ownership of the backing
buffer and is responsible to drop the remaining elements and free the
backing buffer, if it's dropped.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs      |   1 +
 rust/kernel/alloc/kvec.rs | 177 +++++++++++++++++++++++++++++++++++++-
 2 files changed, 177 insertions(+), 1 deletion(-)

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 3a0195d23bb4..e6a5d65e0c48 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -15,6 +15,7 @@
 pub use self::allocator_test as allocator;
 
 pub use self::kbox::KBox;
+pub use self::kvec::IntoIter;
 pub use self::kvec::KVec;
 
 /// Indicates an allocation error.
diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 7ec898657832..ece48930966e 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -11,7 +11,9 @@
     ops::DerefMut,
     ops::Index,
     ops::IndexMut,
-    ptr, slice,
+    ptr,
+    ptr::NonNull,
+    slice,
     slice::SliceIndex,
 };
 
@@ -603,3 +605,176 @@ fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
 __impl_slice_eq! { [A: Allocator] [T], KVec<U, A> }
 __impl_slice_eq! { [A: Allocator, const N: usize] KVec<T, A>, [U; N] }
 __impl_slice_eq! { [A: Allocator, const N: usize] KVec<T, A>, &[U; N] }
+
+impl<'a, T, A> IntoIterator for &'a KVec<T, A>
+where
+    A: Allocator,
+{
+    type Item = &'a T;
+    type IntoIter = slice::Iter<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, T, A: Allocator> IntoIterator for &'a mut KVec<T, A>
+where
+    A: Allocator,
+{
+    type Item = &'a mut T;
+    type IntoIter = slice::IterMut<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
+/// An iterator that moves out of a vector.
+///
+/// This `struct` is created by the `into_iter` method on [`KVec`] (provided by the [`IntoIterator`]
+/// trait).
+///
+/// # Examples
+///
+/// ```
+/// let v = kernel::kvec![0, 1, 2]?;
+/// let iter: kernel::alloc::IntoIter<_> = v.into_iter();
+///
+/// # Ok::<(), Error>(())
+/// ```
+pub struct IntoIter<T, A: Allocator = Kmalloc> {
+    ptr: *mut T,
+    buf: NonNull<T>,
+    len: usize,
+    cap: usize,
+    alloc: A,
+}
+
+impl<T, A> IntoIter<T, A>
+where
+    A: Allocator,
+{
+    fn as_raw_mut_slice(&mut self) -> *mut [T] {
+        ptr::slice_from_raw_parts_mut(self.ptr, self.len)
+    }
+}
+
+impl<T, A> Iterator for IntoIter<T, A>
+where
+    A: Allocator,
+{
+    type Item = T;
+
+    /// # Examples
+    ///
+    /// ```
+    /// let v = kernel::kvec![1, 2, 3]?;
+    /// let mut it = v.into_iter();
+    ///
+    /// assert_eq!(it.next(), Some(1));
+    /// assert_eq!(it.next(), Some(2));
+    /// assert_eq!(it.next(), Some(3));
+    /// assert_eq!(it.next(), None);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    fn next(&mut self) -> Option<T> {
+        if self.len == 0 {
+            return None;
+        }
+
+        let ptr = self.ptr;
+        if !KVec::<T>::is_zst() {
+            // SAFETY: We can't overflow; `end` is guaranteed to mark the end of the buffer.
+            unsafe { self.ptr = self.ptr.add(1) };
+        } else {
+            // For ZST `ptr` has to stay where it is to remain aligned, so we just reduce `self.len`
+            // by 1.
+        }
+        self.len -= 1;
+
+        // SAFETY: `ptr` is guaranteed to point at a valid element within the buffer.
+        Some(unsafe { ptr.read() })
+    }
+
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::KVec;
+    ///
+    /// let v: KVec<u32, _> = kernel::kvec![1, 2, 3]?;
+    /// let mut iter = v.into_iter();
+    /// let size = iter.size_hint().0;
+    ///
+    /// iter.next();
+    /// assert_eq!(iter.size_hint().0, size - 1);
+    ///
+    /// iter.next();
+    /// assert_eq!(iter.size_hint().0, size - 2);
+    ///
+    /// iter.next();
+    /// assert_eq!(iter.size_hint().0, size - 3);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.len, Some(self.len))
+    }
+}
+
+impl<T, A> Drop for IntoIter<T, A>
+where
+    A: Allocator,
+{
+    fn drop(&mut self) {
+        // SAFETY: Drop the remaining vector's elements in place, before we free the backing
+        // memory.
+        unsafe { ptr::drop_in_place(self.as_raw_mut_slice()) };
+
+        // If `cap == 0` we never allocated any memory in the first place.
+        if self.cap != 0 {
+            // SAFETY: `self.buf` was previously allocated with `self.alloc`.
+            unsafe { self.alloc.free(self.buf.as_ptr().cast()) };
+        }
+    }
+}
+
+impl<T, A> IntoIterator for KVec<T, A>
+where
+    A: Allocator,
+{
+    type Item = T;
+    type IntoIter = IntoIter<T, A>;
+
+    /// Creates a consuming iterator, that is, one that moves each value out of
+    /// the vector (from start to end). The vector cannot be used after calling
+    /// this.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let v = kernel::kvec![1, 2]?;
+    /// let mut v_iter = v.into_iter();
+    ///
+    /// let first_element: Option<u32> = v_iter.next();
+    ///
+    /// assert_eq!(first_element, Some(1));
+    /// assert_eq!(v_iter.next(), Some(2));
+    /// assert_eq!(v_iter.next(), None);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    #[inline]
+    fn into_iter(self) -> Self::IntoIter {
+        let (ptr, len, cap, alloc) = self.into_raw_parts_alloc();
+
+        IntoIter {
+            ptr,
+            buf: unsafe { NonNull::new_unchecked(ptr) },
+            len,
+            cap,
+            alloc,
+        }
+    }
+}
-- 
2.45.2

[PATCH 15/20] rust: alloc: implement `collect` for `IntoIter`

[Danilo Krummrich]

Currently, we can't implement `FromIterator`. There are a couple of
issues with this trait in the kernel, namely:

  - Rust's specialization feature is unstable. This prevents us to
    optimze for the special case where `I::IntoIter` equals `KVec`'s
    `IntoIter` type.
  - We also can't use `I::IntoIter`'s type ID either to work around this,
    since `FromIterator` doesn't require this type to be `'static`.
  - `FromIterator::from_iter` does return `Self` instead of
    `Result<Self, AllocError>`, hence we can't properly handle allocation
    failures.
  - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle
    additional allocation flags.

Instead, provide `IntoIter::collect`, such that we can at least convert
`IntoIter` into a `KVec` again.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc/kvec.rs | 83 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 82 insertions(+), 1 deletion(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index ece48930966e..463c8910c23c 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -2,7 +2,7 @@
 
 //! Implementation of [`KVec`].
 
-use super::{allocator::Kmalloc, AllocError, Allocator, Flags};
+use super::{allocator::Kmalloc, flags::*, AllocError, Allocator, Flags};
 use crate::types::Unique;
 use core::{
     fmt,
@@ -658,6 +658,87 @@ impl<T, A> IntoIter<T, A>
     fn as_raw_mut_slice(&mut self) -> *mut [T] {
         ptr::slice_from_raw_parts_mut(self.ptr, self.len)
     }
+
+    fn allocator(&self) -> &A {
+        &self.alloc
+    }
+
+    fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize, A) {
+        let me = ManuallyDrop::new(self);
+        let ptr = me.ptr;
+        let buf = me.buf;
+        let len = me.len;
+        let cap = me.cap;
+        let alloc = unsafe { ptr::read(me.allocator()) };
+        (ptr, buf, len, cap, alloc)
+    }
+
+    /// Same as `Iterator::collect` but specialized for `KVec`'s `IntoIter`.
+    ///
+    /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait
+    /// in the kernel, namely:
+    ///
+    /// - Rust's specialization feature is unstable. This prevents us to optimze for the special
+    ///   case where `I::IntoIter` equals `KVec`'s `IntoIter` type.
+    /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator`
+    ///   doesn't require this type to be `'static`.
+    /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence
+    ///   we can't properly handle allocation failures.
+    /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation
+    ///   flags.
+    ///
+    /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a
+    /// `KVec` again.
+    ///
+    /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing
+    /// buffer. However, this backing buffer may be shrunk to the actual count of elements.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let v = kernel::kvec![1, 2, 3]?;
+    /// let mut it = v.into_iter();
+    ///
+    /// assert_eq!(it.next(), Some(1));
+    ///
+    /// let v = it.collect()?;
+    /// assert_eq!(v, [2, 3]);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn collect(self) -> Result<KVec<T, A>, AllocError> {
+        let (mut ptr, buf, len, mut cap, alloc) = self.into_raw_parts();
+        let has_advanced = ptr != buf.as_ptr();
+
+        if has_advanced {
+            // SAFETY: Copy the contents we have advanced to at the beginning of the buffer.
+            // `ptr` is guaranteed to be between `buf` and `buf.add(cap)` and `ptr.add(len)` is
+            // guaranteed to be smaller than `buf.add(cap)`.
+            unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
+            ptr = buf.as_ptr();
+        }
+
+        // Do not allow for too much spare capacity.
+        if len < cap / 2 {
+            let layout = core::alloc::Layout::array::<T>(len).map_err(|_| AllocError)?;
+            // SAFETY: `ptr` points to the start of the backing buffer, `cap` is the capacity of
+            // the original `KVec` and `len` is guaranteed to be smaller than `cap`. Depending on
+            // `alloc` this operation may shrink the buffer or leaves it as it is.
+            ptr = unsafe {
+                alloc.realloc(ptr.cast(), KVec::<T>::buffer_size(cap)?, layout, GFP_KERNEL)
+            }?
+            .as_ptr()
+            .cast();
+            cap = len;
+        }
+
+        // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
+        // the beginning of the buffer and `len` has been adjusted accordingly. `ptr` is guaranteed
+        // to point to the start of the backing buffer. `cap` is either the original capacity or,
+        // after shrinking the buffer, equal to `len`. `alloc` is guaranteed to be unchanged since
+        // `into_iter` has been called on the original `KVec`.
+        Ok(unsafe { KVec::from_raw_parts_alloc(ptr, len, cap, alloc) })
+    }
 }
 
 impl<T, A> Iterator for IntoIter<T, A>
-- 
2.45.2

Re: [PATCH 15/20] rust: alloc: implement `collect` for `IntoIter`

[Boqun Feng]

On Thu, Jul 04, 2024 at 07:06:43PM +0200, Danilo Krummrich wrote:
[...]
> @@ -658,6 +658,87 @@ impl<T, A> IntoIter<T, A>
>      fn as_raw_mut_slice(&mut self) -> *mut [T] {
>          ptr::slice_from_raw_parts_mut(self.ptr, self.len)
>      }
> +
> +    fn allocator(&self) -> &A {
> +        &self.alloc
> +    }
> +
> +    fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize, A) {
> +        let me = ManuallyDrop::new(self);
> +        let ptr = me.ptr;
> +        let buf = me.buf;
> +        let len = me.len;
> +        let cap = me.cap;
> +        let alloc = unsafe { ptr::read(me.allocator()) };
> +        (ptr, buf, len, cap, alloc)
> +    }
> +
[...]
> +    pub fn collect(self) -> Result<KVec<T, A>, AllocError> {
> +        let (mut ptr, buf, len, mut cap, alloc) = self.into_raw_parts();

We have leaked the `IntoIter` here,

> +        let has_advanced = ptr != buf.as_ptr();
> +
> +        if has_advanced {
> +            // SAFETY: Copy the contents we have advanced to at the beginning of the buffer.
> +            // `ptr` is guaranteed to be between `buf` and `buf.add(cap)` and `ptr.add(len)` is
> +            // guaranteed to be smaller than `buf.add(cap)`.
> +            unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
> +            ptr = buf.as_ptr();
> +        }
> +
> +        // Do not allow for too much spare capacity.
> +        if len < cap / 2 {
> +            let layout = core::alloc::Layout::array::<T>(len).map_err(|_| AllocError)?;
> +            // SAFETY: `ptr` points to the start of the backing buffer, `cap` is the capacity of
> +            // the original `KVec` and `len` is guaranteed to be smaller than `cap`. Depending on
> +            // `alloc` this operation may shrink the buffer or leaves it as it is.
> +            ptr = unsafe {
> +                alloc.realloc(ptr.cast(), KVec::<T>::buffer_size(cap)?, layout, GFP_KERNEL)
> +            }?

and if `realloc` fails, we end up leaking memory, right? A simple fix
would be continuing if `realloc` fails. Maybe you could even make this
function returns `KVec<T,A>` instead of a `Result`.

Regards,
Boqun

> +            .as_ptr()
> +            .cast();
> +            cap = len;
> +        }
> +
> +        // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
> +        // the beginning of the buffer and `len` has been adjusted accordingly. `ptr` is guaranteed
> +        // to point to the start of the backing buffer. `cap` is either the original capacity or,
> +        // after shrinking the buffer, equal to `len`. `alloc` is guaranteed to be unchanged since
> +        // `into_iter` has been called on the original `KVec`.
> +        Ok(unsafe { KVec::from_raw_parts_alloc(ptr, len, cap, alloc) })
> +    }
>  }
>  
>  impl<T, A> Iterator for IntoIter<T, A>
> -- 
> 2.45.2
> 

Re: [PATCH 15/20] rust: alloc: implement `collect` for `IntoIter`

[Danilo Krummrich]

On Thu, Jul 04, 2024 at 04:27:13PM -0700, Boqun Feng wrote:
> On Thu, Jul 04, 2024 at 07:06:43PM +0200, Danilo Krummrich wrote:
> [...]
> > @@ -658,6 +658,87 @@ impl<T, A> IntoIter<T, A>
> >      fn as_raw_mut_slice(&mut self) -> *mut [T] {
> >          ptr::slice_from_raw_parts_mut(self.ptr, self.len)
> >      }
> > +
> > +    fn allocator(&self) -> &A {
> > +        &self.alloc
> > +    }
> > +
> > +    fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize, A) {
> > +        let me = ManuallyDrop::new(self);
> > +        let ptr = me.ptr;
> > +        let buf = me.buf;
> > +        let len = me.len;
> > +        let cap = me.cap;
> > +        let alloc = unsafe { ptr::read(me.allocator()) };
> > +        (ptr, buf, len, cap, alloc)
> > +    }
> > +
> [...]
> > +    pub fn collect(self) -> Result<KVec<T, A>, AllocError> {
> > +        let (mut ptr, buf, len, mut cap, alloc) = self.into_raw_parts();
> 
> We have leaked the `IntoIter` here,
> 
> > +        let has_advanced = ptr != buf.as_ptr();
> > +
> > +        if has_advanced {
> > +            // SAFETY: Copy the contents we have advanced to at the beginning of the buffer.
> > +            // `ptr` is guaranteed to be between `buf` and `buf.add(cap)` and `ptr.add(len)` is
> > +            // guaranteed to be smaller than `buf.add(cap)`.
> > +            unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
> > +            ptr = buf.as_ptr();
> > +        }
> > +
> > +        // Do not allow for too much spare capacity.
> > +        if len < cap / 2 {
> > +            let layout = core::alloc::Layout::array::<T>(len).map_err(|_| AllocError)?;
> > +            // SAFETY: `ptr` points to the start of the backing buffer, `cap` is the capacity of
> > +            // the original `KVec` and `len` is guaranteed to be smaller than `cap`. Depending on
> > +            // `alloc` this operation may shrink the buffer or leaves it as it is.
> > +            ptr = unsafe {
> > +                alloc.realloc(ptr.cast(), KVec::<T>::buffer_size(cap)?, layout, GFP_KERNEL)
> > +            }?
> 
> and if `realloc` fails, we end up leaking memory, right? A simple fix

Good catch!

I think `realloc` should never fail for a shrink request though, but this isn't
a guarantee I want `Allocator` to actually provide. Besides that, this is just
best effort here, if it fails, it fails and we should just continue.

> would be continuing if `realloc` fails. Maybe you could even make this
> function returns `KVec<T,A>` instead of a `Result`.

Yes, I will queue this up for v2.

> 
> Regards,
> Boqun
> 
> > +            .as_ptr()
> > +            .cast();
> > +            cap = len;
> > +        }
> > +
> > +        // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
> > +        // the beginning of the buffer and `len` has been adjusted accordingly. `ptr` is guaranteed
> > +        // to point to the start of the backing buffer. `cap` is either the original capacity or,
> > +        // after shrinking the buffer, equal to `len`. `alloc` is guaranteed to be unchanged since
> > +        // `into_iter` has been called on the original `KVec`.
> > +        Ok(unsafe { KVec::from_raw_parts_alloc(ptr, len, cap, alloc) })
> > +    }
> >  }
> >  
> >  impl<T, A> Iterator for IntoIter<T, A>
> > -- 
> > 2.45.2
> > 
> 

[PATCH 16/20] rust: treewide: switch to `KVec`

[Danilo Krummrich]

Now that we got `KVec` in place, convert all existing `Vec` users to
`KVec`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/str.rs            | 12 +++++-------
 rust/kernel/sync/locked_by.rs |  2 +-
 rust/kernel/types.rs          |  2 +-
 samples/rust/rust_minimal.rs  |  4 ++--
 4 files changed, 9 insertions(+), 11 deletions(-)

diff --git a/rust/kernel/str.rs b/rust/kernel/str.rs
index bb8d4f41475b..0b6ffbade521 100644
--- a/rust/kernel/str.rs
+++ b/rust/kernel/str.rs
@@ -2,8 +2,7 @@
 
 //! String representations.
 
-use crate::alloc::{flags::*, vec_ext::VecExt, AllocError};
-use alloc::vec::Vec;
+use crate::alloc::{flags::*, AllocError, KVec};
 use core::fmt::{self, Write};
 use core::ops::{self, Deref, DerefMut, Index};
 
@@ -790,7 +789,7 @@ fn write_str(&mut self, s: &str) -> fmt::Result {
 /// assert_eq!(s.is_ok(), false);
 /// ```
 pub struct CString {
-    buf: Vec<u8>,
+    buf: KVec<u8>,
 }
 
 impl CString {
@@ -803,7 +802,7 @@ pub fn try_from_fmt(args: fmt::Arguments<'_>) -> Result<Self, Error> {
         let size = f.bytes_written();
 
         // Allocate a vector with the required number of bytes, and write to it.
-        let mut buf = <Vec<_> as VecExt<_>>::with_capacity(size, GFP_KERNEL)?;
+        let mut buf = KVec::with_capacity(size, GFP_KERNEL)?;
         // SAFETY: The buffer stored in `buf` is at least of size `size` and is valid for writes.
         let mut f = unsafe { Formatter::from_buffer(buf.as_mut_ptr(), size) };
         f.write_fmt(args)?;
@@ -850,10 +849,9 @@ impl<'a> TryFrom<&'a CStr> for CString {
     type Error = AllocError;
 
     fn try_from(cstr: &'a CStr) -> Result<CString, AllocError> {
-        let mut buf = Vec::new();
+        let mut buf = KVec::new();
 
-        <Vec<_> as VecExt<_>>::extend_from_slice(&mut buf, cstr.as_bytes_with_nul(), GFP_KERNEL)
-            .map_err(|_| AllocError)?;
+        KVec::extend_from_slice(&mut buf, cstr.as_bytes_with_nul(), GFP_KERNEL)?;
 
         // INVARIANT: The `CStr` and `CString` types have the same invariants for
         // the string data, and we copied it over without changes.
diff --git a/rust/kernel/sync/locked_by.rs b/rust/kernel/sync/locked_by.rs
index babc731bd5f6..b94517231fcc 100644
--- a/rust/kernel/sync/locked_by.rs
+++ b/rust/kernel/sync/locked_by.rs
@@ -43,7 +43,7 @@
 /// struct InnerDirectory {
 ///     /// The sum of the bytes used by all files.
 ///     bytes_used: u64,
-///     _files: Vec<File>,
+///     _files: KVec<File>,
 /// }
 ///
 /// struct Directory {
diff --git a/rust/kernel/types.rs b/rust/kernel/types.rs
index 0b2a3ce538a6..5ef52d46a386 100644
--- a/rust/kernel/types.rs
+++ b/rust/kernel/types.rs
@@ -155,7 +155,7 @@ unsafe fn from_foreign(_: *const core::ffi::c_void) -> Self {}
 /// # use kernel::types::ScopeGuard;
 /// fn example3(arg: bool) -> Result {
 ///     let mut vec =
-///         ScopeGuard::new_with_data(Vec::new(), |v| pr_info!("vec had {} elements\n", v.len()));
+///         ScopeGuard::new_with_data(KVec::new(), |v| pr_info!("vec had {} elements\n", v.len()));
 ///
 ///     vec.push(10u8, GFP_KERNEL)?;
 ///     if arg {
diff --git a/samples/rust/rust_minimal.rs b/samples/rust/rust_minimal.rs
index 2a9eaab62d1c..4aaf117bf8e3 100644
--- a/samples/rust/rust_minimal.rs
+++ b/samples/rust/rust_minimal.rs
@@ -13,7 +13,7 @@
 }
 
 struct RustMinimal {
-    numbers: Vec<i32>,
+    numbers: KVec<i32>,
 }
 
 impl kernel::Module for RustMinimal {
@@ -21,7 +21,7 @@ fn init(_module: &'static ThisModule) -> Result<Self> {
         pr_info!("Rust minimal sample (init)\n");
         pr_info!("Am I built-in? {}\n", !cfg!(MODULE));
 
-        let mut numbers = Vec::new();
+        let mut numbers = KVec::new();
         numbers.push(72, GFP_KERNEL)?;
         numbers.push(108, GFP_KERNEL)?;
         numbers.push(200, GFP_KERNEL)?;
-- 
2.45.2

[PATCH 17/20] rust: alloc: remove `VecExt` extension

[Danilo Krummrich]

Now that all existing `Vec` users were moved to `KVec`, remove the
`VecExt` extension.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/alloc.rs         |   1 -
 rust/kernel/alloc/vec_ext.rs | 185 -----------------------------------
 rust/kernel/prelude.rs       |   5 +-
 3 files changed, 1 insertion(+), 190 deletions(-)
 delete mode 100644 rust/kernel/alloc/vec_ext.rs

diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index e6a5d65e0c48..178f556aa7b0 100644
--- a/rust/kernel/alloc.rs
+++ b/rust/kernel/alloc.rs
@@ -6,7 +6,6 @@
 pub mod allocator;
 pub mod kbox;
 pub mod kvec;
-pub mod vec_ext;
 
 #[cfg(any(test, testlib))]
 pub mod allocator_test;
diff --git a/rust/kernel/alloc/vec_ext.rs b/rust/kernel/alloc/vec_ext.rs
deleted file mode 100644
index bf277976ed38..000000000000
--- a/rust/kernel/alloc/vec_ext.rs
+++ /dev/null
@@ -1,185 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0
-
-//! Extensions to [`Vec`] for fallible allocations.
-
-use super::{AllocError, Flags};
-use alloc::vec::Vec;
-use core::ptr;
-
-/// Extensions to [`Vec`].
-pub trait VecExt<T>: Sized {
-    /// Creates a new [`Vec`] instance with at least the given capacity.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let v = Vec::<u32>::with_capacity(20, GFP_KERNEL)?;
-    ///
-    /// assert!(v.capacity() >= 20);
-    /// # Ok::<(), Error>(())
-    /// ```
-    fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError>;
-
-    /// Appends an element to the back of the [`Vec`] instance.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let mut v = Vec::new();
-    /// v.push(1, GFP_KERNEL)?;
-    /// assert_eq!(&v, &[1]);
-    ///
-    /// v.push(2, GFP_KERNEL)?;
-    /// assert_eq!(&v, &[1, 2]);
-    /// # Ok::<(), Error>(())
-    /// ```
-    fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError>;
-
-    /// Pushes clones of the elements of slice into the [`Vec`] instance.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let mut v = Vec::new();
-    /// v.push(1, GFP_KERNEL)?;
-    ///
-    /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?;
-    /// assert_eq!(&v, &[1, 20, 30, 40]);
-    ///
-    /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?;
-    /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]);
-    /// # Ok::<(), Error>(())
-    /// ```
-    fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError>
-    where
-        T: Clone;
-
-    /// Ensures that the capacity exceeds the length by at least `additional` elements.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// let mut v = Vec::new();
-    /// v.push(1, GFP_KERNEL)?;
-    ///
-    /// v.reserve(10, GFP_KERNEL)?;
-    /// let cap = v.capacity();
-    /// assert!(cap >= 10);
-    ///
-    /// v.reserve(10, GFP_KERNEL)?;
-    /// let new_cap = v.capacity();
-    /// assert_eq!(new_cap, cap);
-    ///
-    /// # Ok::<(), Error>(())
-    /// ```
-    fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError>;
-}
-
-impl<T> VecExt<T> for Vec<T> {
-    fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {
-        let mut v = Vec::new();
-        <Self as VecExt<_>>::reserve(&mut v, capacity, flags)?;
-        Ok(v)
-    }
-
-    fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
-        <Self as VecExt<_>>::reserve(self, 1, flags)?;
-        let s = self.spare_capacity_mut();
-        s[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.
-        unsafe { self.set_len(self.len() + 1) };
-        Ok(())
-    }
-
-    fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError>
-    where
-        T: Clone,
-    {
-        <Self as VecExt<_>>::reserve(self, other.len(), flags)?;
-        for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) {
-            slot.write(item.clone());
-        }
-
-        // SAFETY: We just initialised the `other.len()` spare entries, so it is safe to increase
-        // the length by the same amount. We also know that the new length is <= capacity because
-        // of the previous call to `reserve` above.
-        unsafe { self.set_len(self.len() + other.len()) };
-        Ok(())
-    }
-
-    #[cfg(any(test, testlib))]
-    fn reserve(&mut self, additional: usize, _flags: Flags) -> Result<(), AllocError> {
-        Vec::reserve(self, additional);
-        Ok(())
-    }
-
-    #[cfg(not(any(test, testlib)))]
-    fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {
-        let alloc: &dyn super::Allocator = &super::allocator::Kmalloc;
-        let len = self.len();
-        let cap = self.capacity();
-
-        if cap - len >= additional {
-            return Ok(());
-        }
-
-        if core::mem::size_of::<T>() == 0 {
-            // The capacity is already `usize::MAX` for SZTs, we can't go higher.
-            return Err(AllocError);
-        }
-
-        // We know cap is <= `isize::MAX` because `Layout::array` fails if the resulting byte size
-        // is greater than `isize::MAX`. So the multiplication by two won't overflow.
-        let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?);
-        let layout = core::alloc::Layout::array::<T>(new_cap).map_err(|_| AllocError)?;
-
-        let (old_ptr, len, cap) = destructure(self);
-
-        // We need to make sure that `ptr` is either NULL or comes from a previous call to
-        // `krealloc_aligned`. A `Vec<T>`'s `ptr` value is not guaranteed to be NULL and might be
-        // dangling after being created with `Vec::new`. Instead, we can rely on `Vec<T>`'s capacity
-        // to be zero if no memory has been allocated yet.
-        let ptr = if cap == 0 { ptr::null_mut() } else { old_ptr };
-
-        // SAFETY: `ptr` is valid because it's either NULL or comes from a previous call to
-        // `krealloc_aligned`. We also verified that the type is not a ZST.
-        match unsafe { alloc.realloc(ptr.cast(), cap, layout, flags) } {
-            Ok(ptr) => {
-                // SAFETY: `ptr` has been reallocated with the layout for `new_cap` elements.
-                // `new_cap` is greater than `cap`, so it continues to be >= `len`.
-                unsafe { rebuild(self, ptr.as_ptr().cast(), len, new_cap) };
-                Ok(())
-            }
-            Err(err) => {
-                // SAFETY: We are just rebuilding the existing `Vec` with no changes.
-                unsafe { rebuild(self, old_ptr, len, cap) };
-                Err(err)
-            }
-        }
-    }
-}
-
-#[cfg(not(any(test, testlib)))]
-fn destructure<T>(v: &mut Vec<T>) -> (*mut T, usize, usize) {
-    let mut tmp = Vec::new();
-    core::mem::swap(&mut tmp, v);
-    let mut tmp = core::mem::ManuallyDrop::new(tmp);
-    let len = tmp.len();
-    let cap = tmp.capacity();
-    (tmp.as_mut_ptr(), len, cap)
-}
-
-/// Rebuilds a `Vec` from a pointer, length, and capacity.
-///
-/// # Safety
-///
-/// The same as [`Vec::from_raw_parts`].
-#[cfg(not(any(test, testlib)))]
-unsafe fn rebuild<T>(v: &mut Vec<T>, ptr: *mut T, len: usize, cap: usize) {
-    // SAFETY: The safety requirements from this function satisfy those of `from_raw_parts`.
-    let mut tmp = unsafe { Vec::from_raw_parts(ptr, len, cap) };
-    core::mem::swap(&mut tmp, v);
-}
diff --git a/rust/kernel/prelude.rs b/rust/kernel/prelude.rs
index 0ee3f0d203e2..0836394ddab8 100644
--- a/rust/kernel/prelude.rs
+++ b/rust/kernel/prelude.rs
@@ -14,10 +14,7 @@
 #[doc(no_inline)]
 pub use core::pin::Pin;
 
-pub use crate::alloc::{flags::*, vec_ext::VecExt, KBox, KVec};
-
-#[doc(no_inline)]
-pub use alloc::vec::Vec;
+pub use crate::alloc::{flags::*, KBox, KVec};
 
 #[doc(no_inline)]
 pub use macros::{module, pin_data, pinned_drop, vtable, Zeroable};
-- 
2.45.2

[PATCH 18/20] rust: error: use `core::alloc::LayoutError`

[Danilo Krummrich]

Use `core::alloc::LayoutError` instead of `alloc::alloc::LayoutError` in
preparation to get rid of Rust's alloc crate.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/error.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/rust/kernel/error.rs b/rust/kernel/error.rs
index 55280ae9fe40..20306588bc9e 100644
--- a/rust/kernel/error.rs
+++ b/rust/kernel/error.rs
@@ -6,7 +6,7 @@
 
 use crate::{alloc::AllocError, str::CStr};
 
-use alloc::alloc::LayoutError;
+use core::alloc::LayoutError;
 
 use core::fmt;
 use core::num::TryFromIntError;
-- 
2.45.2

[PATCH 19/20] rust: str: test: replace `alloc::format`

[Danilo Krummrich]

The current implementation of tests in str.rs use `format!` to format
strings for comparison, which, internally, creates a new `String`.

In order to prepare for getting rid of Rust's alloc crate, we have to
cut this dependency. Instead, we could implement `format!` for
`CString`, however `CString` uses `KVec` and hence the kernel
allocators, which can't be used for tests run in userspace.

Instead, implement `fmt_assert_eq`, which formats strings into a stack
allocated buffer for comparison with a `&str`.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/kernel/str.rs | 66 ++++++++++++++++++++++++++++++++--------------
 1 file changed, 46 insertions(+), 20 deletions(-)

diff --git a/rust/kernel/str.rs b/rust/kernel/str.rs
index 0b6ffbade521..539be40754f4 100644
--- a/rust/kernel/str.rs
+++ b/rust/kernel/str.rs
@@ -523,7 +523,6 @@ macro_rules! c_str {
 #[cfg(test)]
 mod tests {
     use super::*;
-    use alloc::format;
 
     const ALL_ASCII_CHARS: &'static str =
         "\\x01\\x02\\x03\\x04\\x05\\x06\\x07\\x08\\x09\\x0a\\x0b\\x0c\\x0d\\x0e\\x0f\
@@ -539,6 +538,33 @@ mod tests {
         \\xe0\\xe1\\xe2\\xe3\\xe4\\xe5\\xe6\\xe7\\xe8\\xe9\\xea\\xeb\\xec\\xed\\xee\\xef\
         \\xf0\\xf1\\xf2\\xf3\\xf4\\xf5\\xf6\\xf7\\xf8\\xf9\\xfa\\xfb\\xfc\\xfd\\xfe\\xff";
 
+    fn format_into_buf<'a>(args: fmt::Arguments<'_>, buf: &'a mut [u8]) -> Result<&'a str, Error> {
+        let mut f = RawFormatter::new();
+        f.write_fmt(args)?;
+        let size = f.bytes_written();
+
+        assert!(buf.len() >= size);
+
+        // SAFETY: `buf` has at least a size of `size` bytes and is valid for writes.
+        let mut f = unsafe { Formatter::from_buffer(buf.as_mut_ptr(), size) };
+        f.write_fmt(args)?;
+
+        Ok(core::str::from_utf8(&buf[0..size])?)
+    }
+
+    macro_rules! fmt_assert_eq {
+        ($str:expr, $($f:tt)*) => ({
+            let mut buf = [0_u8; ALL_ASCII_CHARS.len()];
+
+            let s = match format_into_buf(kernel::fmt!($($f)*), &mut buf) {
+                Ok(s) => s,
+                Err(_) => panic!("Could not format into buffer."),
+            };
+
+            assert_eq!($str, s);
+        })
+    }
+
     #[test]
     fn test_cstr_to_str() {
         let good_bytes = b"\xf0\x9f\xa6\x80\0";
@@ -566,13 +592,13 @@ fn test_cstr_as_str_unchecked() {
     #[test]
     fn test_cstr_display() {
         let hello_world = CStr::from_bytes_with_nul(b"hello, world!\0").unwrap();
-        assert_eq!(format!("{}", hello_world), "hello, world!");
+        fmt_assert_eq!("hello, world!", "{}", hello_world);
         let non_printables = CStr::from_bytes_with_nul(b"\x01\x09\x0a\0").unwrap();
-        assert_eq!(format!("{}", non_printables), "\\x01\\x09\\x0a");
+        fmt_assert_eq!("\\x01\\x09\\x0a", "{}", non_printables);
         let non_ascii = CStr::from_bytes_with_nul(b"d\xe9j\xe0 vu\0").unwrap();
-        assert_eq!(format!("{}", non_ascii), "d\\xe9j\\xe0 vu");
+        fmt_assert_eq!("d\\xe9j\\xe0 vu", "{}", non_ascii);
         let good_bytes = CStr::from_bytes_with_nul(b"\xf0\x9f\xa6\x80\0").unwrap();
-        assert_eq!(format!("{}", good_bytes), "\\xf0\\x9f\\xa6\\x80");
+        fmt_assert_eq!("\\xf0\\x9f\\xa6\\x80", "{}", good_bytes);
     }
 
     #[test]
@@ -583,47 +609,47 @@ fn test_cstr_display_all_bytes() {
             bytes[i as usize] = i.wrapping_add(1);
         }
         let cstr = CStr::from_bytes_with_nul(&bytes).unwrap();
-        assert_eq!(format!("{}", cstr), ALL_ASCII_CHARS);
+        fmt_assert_eq!(ALL_ASCII_CHARS, "{}", cstr);
     }
 
     #[test]
     fn test_cstr_debug() {
         let hello_world = CStr::from_bytes_with_nul(b"hello, world!\0").unwrap();
-        assert_eq!(format!("{:?}", hello_world), "\"hello, world!\"");
+        fmt_assert_eq!("\"hello, world!\"", "{:?}", hello_world);
         let non_printables = CStr::from_bytes_with_nul(b"\x01\x09\x0a\0").unwrap();
-        assert_eq!(format!("{:?}", non_printables), "\"\\x01\\x09\\x0a\"");
+        fmt_assert_eq!("\"\\x01\\x09\\x0a\"", "{:?}", non_printables);
         let non_ascii = CStr::from_bytes_with_nul(b"d\xe9j\xe0 vu\0").unwrap();
-        assert_eq!(format!("{:?}", non_ascii), "\"d\\xe9j\\xe0 vu\"");
+        fmt_assert_eq!("\"d\\xe9j\\xe0 vu\"", "{:?}", non_ascii);
         let good_bytes = CStr::from_bytes_with_nul(b"\xf0\x9f\xa6\x80\0").unwrap();
-        assert_eq!(format!("{:?}", good_bytes), "\"\\xf0\\x9f\\xa6\\x80\"");
+        fmt_assert_eq!("\"\\xf0\\x9f\\xa6\\x80\"", "{:?}", good_bytes);
     }
 
     #[test]
     fn test_bstr_display() {
         let hello_world = BStr::from_bytes(b"hello, world!");
-        assert_eq!(format!("{}", hello_world), "hello, world!");
+        fmt_assert_eq!("hello, world!", "{}", hello_world);
         let escapes = BStr::from_bytes(b"_\t_\n_\r_\\_\'_\"_");
-        assert_eq!(format!("{}", escapes), "_\\t_\\n_\\r_\\_'_\"_");
+        fmt_assert_eq!("_\\t_\\n_\\r_\\_'_\"_", "{}", escapes);
         let others = BStr::from_bytes(b"\x01");
-        assert_eq!(format!("{}", others), "\\x01");
+        fmt_assert_eq!("\\x01", "{}", others);
         let non_ascii = BStr::from_bytes(b"d\xe9j\xe0 vu");
-        assert_eq!(format!("{}", non_ascii), "d\\xe9j\\xe0 vu");
+        fmt_assert_eq!("d\\xe9j\\xe0 vu", "{}", non_ascii);
         let good_bytes = BStr::from_bytes(b"\xf0\x9f\xa6\x80");
-        assert_eq!(format!("{}", good_bytes), "\\xf0\\x9f\\xa6\\x80");
+        fmt_assert_eq!("\\xf0\\x9f\\xa6\\x80", "{}", good_bytes);
     }
 
     #[test]
     fn test_bstr_debug() {
         let hello_world = BStr::from_bytes(b"hello, world!");
-        assert_eq!(format!("{:?}", hello_world), "\"hello, world!\"");
+        fmt_assert_eq!("\"hello, world!\"", "{:?}", hello_world);
         let escapes = BStr::from_bytes(b"_\t_\n_\r_\\_\'_\"_");
-        assert_eq!(format!("{:?}", escapes), "\"_\\t_\\n_\\r_\\\\_'_\\\"_\"");
+        fmt_assert_eq!("\"_\\t_\\n_\\r_\\\\_'_\\\"_\"", "{:?}", escapes);
         let others = BStr::from_bytes(b"\x01");
-        assert_eq!(format!("{:?}", others), "\"\\x01\"");
+        fmt_assert_eq!("\"\\x01\"", "{:?}", others);
         let non_ascii = BStr::from_bytes(b"d\xe9j\xe0 vu");
-        assert_eq!(format!("{:?}", non_ascii), "\"d\\xe9j\\xe0 vu\"");
+        fmt_assert_eq!("\"d\\xe9j\\xe0 vu\"", "{:?}", non_ascii);
         let good_bytes = BStr::from_bytes(b"\xf0\x9f\xa6\x80");
-        assert_eq!(format!("{:?}", good_bytes), "\"\\xf0\\x9f\\xa6\\x80\"");
+        fmt_assert_eq!("\"\\xf0\\x9f\\xa6\\x80\"", "{:?}", good_bytes);
     }
 }
 
-- 
2.45.2

[PATCH 20/20] kbuild: rust: remove the `alloc` crate

[Danilo Krummrich]

Now that we have our own `Allocator`, `KBox` and `KVec` we can remove
Rust's `alloc` crate and the corresponding unstable features.

Signed-off-by: Danilo Krummrich <dakr@redhat.com>
---
 rust/Makefile          | 44 ++++++++++--------------------------------
 rust/exports.c         |  1 -
 scripts/Makefile.build |  7 +------
 3 files changed, 11 insertions(+), 41 deletions(-)

diff --git a/rust/Makefile b/rust/Makefile
index f70d5e244fee..409be08ad09a 100644
--- a/rust/Makefile
+++ b/rust/Makefile
@@ -15,9 +15,8 @@ always-$(CONFIG_RUST) += libmacros.so
 no-clean-files += libmacros.so
 
 always-$(CONFIG_RUST) += bindings/bindings_generated.rs bindings/bindings_helpers_generated.rs
-obj-$(CONFIG_RUST) += alloc.o bindings.o kernel.o
-always-$(CONFIG_RUST) += exports_alloc_generated.h exports_bindings_generated.h \
-    exports_kernel_generated.h
+obj-$(CONFIG_RUST) += bindings.o kernel.o
+always-$(CONFIG_RUST) += exports_bindings_generated.h exports_kernel_generated.h
 
 always-$(CONFIG_RUST) += uapi/uapi_generated.rs
 obj-$(CONFIG_RUST) += uapi.o
@@ -60,11 +59,6 @@ endif
 core-cfgs = \
     --cfg no_fp_fmt_parse
 
-alloc-cfgs = \
-    --cfg no_global_oom_handling \
-    --cfg no_rc \
-    --cfg no_sync
-
 quiet_cmd_rustdoc = RUSTDOC $(if $(rustdoc_host),H, ) $<
       cmd_rustdoc = \
 	OBJTREE=$(abspath $(objtree)) \
@@ -87,7 +81,7 @@ quiet_cmd_rustdoc = RUSTDOC $(if $(rustdoc_host),H, ) $<
 # command-like flags to solve the issue. Meanwhile, we use the non-custom case
 # and then retouch the generated files.
 rustdoc: rustdoc-core rustdoc-macros rustdoc-compiler_builtins \
-    rustdoc-alloc rustdoc-kernel
+    rustdoc-kernel
 	$(Q)cp $(srctree)/Documentation/images/logo.svg $(rustdoc_output)/static.files/
 	$(Q)cp $(srctree)/Documentation/images/COPYING-logo $(rustdoc_output)/static.files/
 	$(Q)find $(rustdoc_output) -name '*.html' -type f -print0 | xargs -0 sed -Ei \
@@ -111,20 +105,11 @@ rustdoc-core: $(RUST_LIB_SRC)/core/src/lib.rs FORCE
 rustdoc-compiler_builtins: $(src)/compiler_builtins.rs rustdoc-core FORCE
 	+$(call if_changed,rustdoc)
 
-# We need to allow `rustdoc::broken_intra_doc_links` because some
-# `no_global_oom_handling` functions refer to non-`no_global_oom_handling`
-# functions. Ideally `rustdoc` would have a way to distinguish broken links
-# due to things that are "configured out" vs. entirely non-existing ones.
-rustdoc-alloc: private rustc_target_flags = $(alloc-cfgs) \
-    -Arustdoc::broken_intra_doc_links
-rustdoc-alloc: $(RUST_LIB_SRC)/alloc/src/lib.rs rustdoc-core rustdoc-compiler_builtins FORCE
-	+$(call if_changed,rustdoc)
-
-rustdoc-kernel: private rustc_target_flags = --extern alloc \
+rustdoc-kernel: private rustc_target_flags = \
     --extern build_error --extern macros=$(objtree)/$(obj)/libmacros.so \
     --extern bindings --extern uapi
 rustdoc-kernel: $(src)/kernel/lib.rs rustdoc-core rustdoc-macros \
-    rustdoc-compiler_builtins rustdoc-alloc $(obj)/libmacros.so \
+    rustdoc-compiler_builtins $(obj)/libmacros.so \
     $(obj)/bindings.o FORCE
 	+$(call if_changed,rustdoc)
 
@@ -169,7 +154,7 @@ quiet_cmd_rustdoc_test_kernel = RUSTDOC TK $<
 	mkdir -p $(objtree)/$(obj)/test/doctests/kernel; \
 	OBJTREE=$(abspath $(objtree)) \
 	$(RUSTDOC) --test $(rust_flags) \
-		-L$(objtree)/$(obj) --extern alloc --extern kernel \
+		-L$(objtree)/$(obj) --extern kernel \
 		--extern build_error --extern macros \
 		--extern bindings --extern uapi \
 		--no-run --crate-name kernel -Zunstable-options \
@@ -251,7 +236,7 @@ rusttest-macros: $(src)/macros/lib.rs rusttest-prepare FORCE
 	+$(call if_changed,rustc_test)
 	+$(call if_changed,rustdoc_test)
 
-rusttest-kernel: private rustc_target_flags = --extern alloc \
+rusttest-kernel: private rustc_target_flags = \
     --extern build_error --extern macros --extern bindings --extern uapi
 rusttest-kernel: $(src)/kernel/lib.rs rusttest-prepare \
     rusttestlib-build_error rusttestlib-macros rusttestlib-bindings \
@@ -364,9 +349,6 @@ quiet_cmd_exports = EXPORTS $@
 $(obj)/exports_core_generated.h: $(obj)/core.o FORCE
 	$(call if_changed,exports)
 
-$(obj)/exports_alloc_generated.h: $(obj)/alloc.o FORCE
-	$(call if_changed,exports)
-
 $(obj)/exports_bindings_generated.h: $(obj)/bindings.o FORCE
 	$(call if_changed,exports)
 
@@ -402,7 +384,7 @@ quiet_cmd_rustc_library = $(if $(skip_clippy),RUSTC,$(RUSTC_OR_CLIPPY_QUIET)) L
 
 rust-analyzer:
 	$(Q)$(srctree)/scripts/generate_rust_analyzer.py \
-		--cfgs='core=$(core-cfgs)' --cfgs='alloc=$(alloc-cfgs)' \
+		--cfgs='core=$(core-cfgs)' \
 		$(realpath $(srctree)) $(realpath $(objtree)) \
 		$(RUST_LIB_SRC) $(KBUILD_EXTMOD) > \
 		$(if $(KBUILD_EXTMOD),$(extmod_prefix),$(objtree))/rust-project.json
@@ -434,12 +416,6 @@ $(obj)/compiler_builtins.o: private rustc_objcopy = -w -W '__*'
 $(obj)/compiler_builtins.o: $(src)/compiler_builtins.rs $(obj)/core.o FORCE
 	+$(call if_changed_dep,rustc_library)
 
-$(obj)/alloc.o: private skip_clippy = 1
-$(obj)/alloc.o: private skip_flags = -Dunreachable_pub
-$(obj)/alloc.o: private rustc_target_flags = $(alloc-cfgs)
-$(obj)/alloc.o: $(RUST_LIB_SRC)/alloc/src/lib.rs $(obj)/compiler_builtins.o FORCE
-	+$(call if_changed_dep,rustc_library)
-
 $(obj)/build_error.o: $(src)/build_error.rs $(obj)/compiler_builtins.o FORCE
 	+$(call if_changed_dep,rustc_library)
 
@@ -454,9 +430,9 @@ $(obj)/uapi.o: $(src)/uapi/lib.rs \
     $(obj)/uapi/uapi_generated.rs FORCE
 	+$(call if_changed_dep,rustc_library)
 
-$(obj)/kernel.o: private rustc_target_flags = --extern alloc \
+$(obj)/kernel.o: private rustc_target_flags = \
     --extern build_error --extern macros --extern bindings --extern uapi
-$(obj)/kernel.o: $(src)/kernel/lib.rs $(obj)/alloc.o $(obj)/build_error.o \
+$(obj)/kernel.o: $(src)/kernel/lib.rs $(obj)/build_error.o \
     $(obj)/libmacros.so $(obj)/bindings.o $(obj)/uapi.o FORCE
 	+$(call if_changed_dep,rustc_library)
 
diff --git a/rust/exports.c b/rust/exports.c
index 3803c21d1403..1b870e8e83ea 100644
--- a/rust/exports.c
+++ b/rust/exports.c
@@ -16,7 +16,6 @@
 #define EXPORT_SYMBOL_RUST_GPL(sym) extern int sym; EXPORT_SYMBOL_GPL(sym)
 
 #include "exports_core_generated.h"
-#include "exports_alloc_generated.h"
 #include "exports_bindings_generated.h"
 #include "exports_kernel_generated.h"
 
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index efacca63c897..7e7b6b3d5bb9 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -262,18 +262,13 @@ $(obj)/%.lst: $(obj)/%.c FORCE
 
 # Compile Rust sources (.rs)
 # ---------------------------------------------------------------------------
-
-rust_allowed_features := new_uninit
-
 # `--out-dir` is required to avoid temporaries being created by `rustc` in the
 # current working directory, which may be not accessible in the out-of-tree
 # modules case.
 rust_common_cmd = \
 	RUST_MODFILE=$(modfile) $(RUSTC_OR_CLIPPY) $(rust_flags) \
-	-Zallow-features=$(rust_allowed_features) \
 	-Zcrate-attr=no_std \
-	-Zcrate-attr='feature($(rust_allowed_features))' \
-	-Zunstable-options --extern force:alloc --extern kernel \
+	-Zunstable-options --extern kernel \
 	--crate-type rlib -L $(objtree)/rust/ \
 	--crate-name $(basename $(notdir $@)) \
 	--sysroot=/dev/null \
-- 
2.45.2

Re: [PATCH 20/20] kbuild: rust: remove the `alloc` crate

[kernel test robot]

Hi Danilo,

kernel test robot noticed the following build warnings:

[auto build test WARNING on 1613e604df0cd359cf2a7fbd9be7a0bcfacfabd0]

url:    https://github.com/intel-lab-lkp/linux/commits/Danilo-Krummrich/rust-alloc-add-Allocator-trait/20240705-155308
base:   1613e604df0cd359cf2a7fbd9be7a0bcfacfabd0
patch link:    https://lore.kernel.org/r/20240704170738.3621-21-dakr%40redhat.com
patch subject: [PATCH 20/20] kbuild: rust: remove the `alloc` crate
config: x86_64-rhel-8.3-rust (https://download.01.org/0day-ci/archive/20240706/202407061152.YNTsL28i-lkp@intel.com/config)
compiler: clang version 18.1.5 (https://github.com/llvm/llvm-project 617a15a9eac96088ae5e9134248d8236e34b91b1)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240706/202407061152.YNTsL28i-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202407061152.YNTsL28i-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> warning: unresolved link to `alloc`
   --> rust/kernel/alloc.rs:3:25
   |
   3 | //! Extensions to the [`alloc`] crate.
   |                         ^^^^^ no item named `alloc` in scope
   |
   = help: to escape `[` and `]` characters, add '' before them like `[` or `]`
   = note: `#[warn(rustdoc::broken_intra_doc_links)]` on by default

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki