Generic `Allocator` support for Rust

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.

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)

rust/kernel/alloc.rs +1 -0

index 1966bd407017..6c21bd2edad9 100644
@@ -11,6 +11,7 @@
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub struct AllocError;
+use core::{alloc::Layout, ptr::NonNull};
 
 /// Flags to be used when allocating memory.
 ///

@@ -86,3 +87,114 @@ pub mod flags {
     /// small allocations.

rust/kernel/alloc.rs +5 -0

+///
+/// # Safety
+///
+/// - A memory allocation returned from an allocator must remain valid until it is explicitly freed.
+///

rust/kernel/alloc.rs +31 -0

+pub unsafe trait Allocator {
+    /// Allocate memory based on `layout` and `flags`.
+    ///
+    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the layout
+    /// constraints (i.e. minimum size and alignment as specified by `layout`).
+    ///
+    /// This function is equivalent to `realloc` when called with `None`.
+    ///
+    /// # Guarantees
+    ///
+    /// When the return value is `Ok(ptr)`, then `ptr` is
+    /// - valid for reads and writes for `layout.size()` bytes, until it is passed to
+    ///   [`Allocator::free`] or [`Allocator::realloc`],
+    /// - aligned to `layout.align()`,
+    ///
+    /// Additionally, `Flags` are honored as documented in
+    /// <https://docs.kernel.org/core-api/mm-api.html#mm-api-gfp-flags>.
+    fn alloc(layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {
+        // SAFETY: Passing `None` to `realloc` is valid by it's safety requirements and asks for a
+        // new memory allocation.
+        unsafe { Self::realloc(None, 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 the size of the existing allocation, a successful call
+    /// to `realloc` guarantees that the new or grown buffer has at least `Layout::size` bytes, but
+    /// may also be larger.
+    ///

rust/kernel/alloc.rs +37 -0

+    /// by this allocator. The alignment encoded in `layout` must be smaller than or equal to the
+    /// alignment requested in the previous `alloc` or `realloc` call of the same allocation.
+    ///
+    /// Additionally, `ptr` is allowed to be `None`; in this case a new memory allocation is
+    /// created.
+    ///
+    /// # Guarantees
+    ///
+    /// This function has the same guarantees as [`Allocator::alloc`]. When `ptr == Some(p)`, then
+    /// it additionally guarantees that:
+    /// - the contents of the memory pointed to by `p` are preserved up to the lesser of the new
+    ///   and old size,
+    ///   and old size, i.e.
+    ///   `ret_ptr[0..min(layout.size(), old_size)] == p[0..min(layout.size(), old_size)]`, where
+    ///   `old_size` is the size of the allocation that `p` points at.
+    /// - when the return value is `Err(AllocError)`, then `p` is still valid.
+    unsafe fn realloc(
+        ptr: Option<NonNull<u8>>,
+        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` and
+    /// must not be a dangling pointer.
+    ///
+    /// The memory allocation at `ptr` must never again be read from or written to.
+    unsafe fn free(ptr: NonNull<u8>) {
+        // SAFETY: The caller guarantees that `ptr` points at a valid allocation created by this
+        // allocator. We are passing a `Layout` with the smallest possible alignment, so it is
+        // smaller than or equal to the alignment previously used with this allocation.
+        let _ = unsafe { Self::realloc(Some(ptr), Layout::new::<()>(), Flags(0)) };
+    }
+}

Quoted 6 lines · On Thu, 12 Sep 2024 00:52:37 +0200 Danilo Krummrich <[email protected]> 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.

Hi Danilo,

I think the current design is unsound regarding ZST.

Let's say that Allocator::alloc gets called with a ZST type with alignment of 4096. Your implementation will call into krelloc with new_size of 0, which gets turned into of kfree of null pointer, which is no-op. Everything is fine so far. Krealloc returns ZERO_SIZE_PTR, and then implementation of <Kmalloc as Allocator>::realloc throws it away and returns NonNull::dangling.

Since NonNull::dangling is called with T=u8, this means the pointer returns is 1, and it's invalid for ZSTs with larger alignments.

And this is unfixable even if the realloc implementation is changed. Let's say the realloc now returns a dangling pointer that is suitable aligned. Now let's see what happens when the Allocator::free is called. kfree would be trying to free a Rust-side ZST pointer, but it has no way to know that it's ZST!

I can see 3 ways of fixing this:
1. Reject ZSTs that have larger alignment than 16 and fix the realloc implementation to return suitable aligned ZST pointer. I don't particularly like the idea of allocating ZST can fail though.
2. Say ZST must be handled by the caller, and make alloc function unsafe. This means that we essentially revert to the GlobalAlloc design of Rust, and all callers have to check for ZST.
3. Accept the old_layout and use it to check whether the allocation is ZST allocation.

My personal preference is 3.

Best,
Gary

Quoted 26 lines

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)

rust/kernel/alloc.rs +4 -0

index 1966bd407017..6c21bd2edad9 100644
@@ -11,6 +11,7 @@
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub struct AllocError;
+use core::{alloc::Layout, ptr::NonNull};
 
 /// Flags to be used when allocating memory.
 ///

@@ -86,3 +87,114 @@ pub mod flags {
     /// small allocations.
     pub const GFP_NOWAIT: Flags = Flags(bindings::GFP_NOWAIT);
 }
+
+/// The kernel's [`Allocator`] trait.
+///

rust/kernel/alloc.rs pub mod flags { · line 97

Quoted 5 lines

rust/kernel/alloc.rs +5 -0

+/// An implementation of [`Allocator`] can allocate, re-allocate and free memory buffers described
+/// via [`Layout`].
+///
+/// [`Allocator`] is designed to be implemented as a ZST; [`Allocator`] functions do not operate on
+/// an object instance.

I think whether the Allocator is ZST or not doesn't matter anymore since we say that functions do not operate on an instance.

rust/kernel/alloc.rs pub mod flags { · line 101

Quoted 5 lines

rust/kernel/alloc.rs +4 -0

+///
+/// In order to be able to support `#[derive(SmartPointer)]` later on, we need to avoid a design
+/// that requires an `Allocator` to be instantiated, hence its functions must not contain any kind
+/// of `self` parameter.

nit: this is the reason for Allocator to not have instances, so should be merged together with the preceding sentence into one paragraph.

Quoted 13 lines

rust/kernel/alloc.rs +13 -0

+///
+/// # Safety
+///
+/// - A memory allocation returned from an allocator must remain valid until it is explicitly freed.
+///
+/// - Any pointer to a valid memory allocation must be valid to be passed to any other [`Allocator`]
+///   function of the same type.
+///
+/// - Implementers must ensure that all trait functions abide by the guarantees documented in the
+///   `# Guarantees` sections.
+//
+// Note that `Allocator::{realloc,free}` don't have an `old_layout` argument (like stdlib's
+// corresponding `Allocator` trait functions have), since the implemented (kernel) allocators

rust/kernel/alloc.rs pub mod flags { · line 116

Quoted 2 lines

rust/kernel/alloc.rs +2 -0

+// neither need nor honor such an argument. Thus, it would be misleading to make this API require it
+// anyways.

I would drop the "honor" part, and drop the sentence saying it's misleading to require it. The documentation should say why we don't have the old_layout argument (because we don't need it for now), and shouldn't be trying to dissuade it from being added if it ends up being useful in the future.

rust/kernel/alloc.rs pub mod flags { · line 122

Quoted 7 lines

rust/kernel/alloc.rs +6 -0

+//
+// More generally, this trait isn't intended for implementers to encode a lot of semantics, but
+// rather provide a thin generalization layer for the kernel's allocators.
+//
+// Depending on future requirements, the requirements for this trait may change as well and
+// implementing allocators that need to encode more semantics may become desirable.

Not sure what's the purpose of these two paragraphs. They sound contradictory to each other.

Quoted 32 lines

rust/kernel/alloc.rs +31 -0

+pub unsafe trait Allocator {
+    /// Allocate memory based on `layout` and `flags`.
+    ///
+    /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the layout
+    /// constraints (i.e. minimum size and alignment as specified by `layout`).
+    ///
+    /// This function is equivalent to `realloc` when called with `None`.
+    ///
+    /// # Guarantees
+    ///
+    /// When the return value is `Ok(ptr)`, then `ptr` is
+    /// - valid for reads and writes for `layout.size()` bytes, until it is passed to
+    ///   [`Allocator::free`] or [`Allocator::realloc`],
+    /// - aligned to `layout.align()`,
+    ///
+    /// Additionally, `Flags` are honored as documented in
+    /// <https://docs.kernel.org/core-api/mm-api.html#mm-api-gfp-flags>.
+    fn alloc(layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> {
+        // SAFETY: Passing `None` to `realloc` is valid by it's safety requirements and asks for a
+        // new memory allocation.
+        unsafe { Self::realloc(None, 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 the size of the existing allocation, a successful call
+    /// to `realloc` guarantees that the new or grown buffer has at least `Layout::size` bytes, but
+    /// may also be larger.
+    ///

rust/kernel/alloc.rs pub mod flags { · line 163

Quoted 10 lines

rust/kernel/alloc.rs +10 -0

+    /// If the requested size is smaller than the size of the existing allocation, `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
+    ///
+    /// If `ptr == Some(p)`, then `p` must point to an existing and valid memory allocation created

nit: maybe

	If `ptr` is `Some(p)`?

because ptr carries the provenance not only addresses.

Quoted 38 lines

rust/kernel/alloc.rs +37 -0

+    /// by this allocator. The alignment encoded in `layout` must be smaller than or equal to the
+    /// alignment requested in the previous `alloc` or `realloc` call of the same allocation.
+    ///
+    /// Additionally, `ptr` is allowed to be `None`; in this case a new memory allocation is
+    /// created.
+    ///
+    /// # Guarantees
+    ///
+    /// This function has the same guarantees as [`Allocator::alloc`]. When `ptr == Some(p)`, then
+    /// it additionally guarantees that:
+    /// - the contents of the memory pointed to by `p` are preserved up to the lesser of the new
+    ///   and old size,
+    ///   and old size, i.e.
+    ///   `ret_ptr[0..min(layout.size(), old_size)] == p[0..min(layout.size(), old_size)]`, where
+    ///   `old_size` is the size of the allocation that `p` points at.
+    /// - when the return value is `Err(AllocError)`, then `p` is still valid.
+    unsafe fn realloc(
+        ptr: Option<NonNull<u8>>,
+        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` and
+    /// must not be a dangling pointer.
+    ///
+    /// The memory allocation at `ptr` must never again be read from or written to.
+    unsafe fn free(ptr: NonNull<u8>) {
+        // SAFETY: The caller guarantees that `ptr` points at a valid allocation created by this
+        // allocator. We are passing a `Layout` with the smallest possible alignment, so it is
+        // smaller than or equal to the alignment previously used with this allocation.
+        let _ = unsafe { Self::realloc(Some(ptr), Layout::new::<()>(), Flags(0)) };
+    }
+}

Hi Gary,

thanks for taking a look.

Quoted 21 lines · Gary Guo

Quoted 6 lines · On Thu, 12 Sep 2024 00:52:37 +0200 Danilo Krummrich <[email protected]> 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.

Hi Danilo,

I think the current design is unsound regarding ZST.

Let's say that Allocator::alloc gets called with a ZST type with alignment of 4096. Your implementation will call into krelloc with new_size of 0, which gets turned into of kfree of null pointer, which is no-op. Everything is fine so far. Krealloc returns ZERO_SIZE_PTR, and then implementation of <Kmalloc as Allocator>::realloc throws it away and returns NonNull::dangling.

Quoted 2 lines

Since NonNull::dangling is called with T=u8, this means the pointer returns is 1, and it's invalid for ZSTs with larger alignments.

Right, this interface is not meant to handle "allocations" for ZSTs.

But you're right, since alloc is a safe function, we should return a properly aligned pointer.

Quoted 6 lines

And this is unfixable even if the realloc implementation is changed. Let's say the realloc now returns a dangling pointer that is suitable aligned. Now let's see what happens when the Allocator::free is called. kfree would be trying to free a Rust-side ZST pointer, but it has no way to know that it's ZST!

Right, that's why it's not valid to call free with dangling pointers.

From the safety comment of free:

"ptr must point to an existing and valid memory allocation created by this Allocator and must not be a dangling pointer."

We still need the same in realloc though.

Quoted 12 lines

I can see 3 ways of fixing this:
1. Reject ZSTs that have larger alignment than 16 and fix the realloc implementation to return suitable aligned ZST pointer. I don't particularly like the idea of allocating ZST can fail though.
2. Say ZST must be handled by the caller, and make alloc function unsafe. This means that we essentially revert to the GlobalAlloc design of Rust, and all callers have to check for ZST.
3. Accept the old_layout and use it to check whether the allocation is ZST allocation.

Quoted 1 line

My personal preference is 3.

There is also 4.

Let alloc and realloc return a properly aligned dangling pointer for size == 0 and don't accept dangling pointers in realloc and free.

And 5.

Reject the combination of None and size == 0 entirely, as earlier proposed by Benno.

I'm fine with both, 4. and 5. with a slight preference for 4.

I'd also go along with 1., as a mix of 4. and 5.

I really don't like making alloc unsafe, and I really don't want to have old_layout in free. Please let's not discuss this again. :-)

Quoted 11 lines

Best,
Gary

Quoted 6 lines

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)

Quoted 41 lines · On Sun, 15 Sep 2024 19:02:40 +0200 Danilo Krummrich <[email protected]> wrote:

Hi Gary,

thanks for taking a look.

Quoted 21 lines · Gary Guo

Quoted 6 lines · On Thu, 12 Sep 2024 00:52:37 +0200 Danilo Krummrich <[email protected]> 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.

Hi Danilo,

I think the current design is unsound regarding ZST.

Let's say that Allocator::alloc gets called with a ZST type with alignment of 4096. Your implementation will call into krelloc with new_size of 0, which gets turned into of kfree of null pointer, which is no-op. Everything is fine so far. Krealloc returns ZERO_SIZE_PTR, and then implementation of <Kmalloc as Allocator>::realloc throws it away and returns NonNull::dangling.

Quoted 2 lines

Since NonNull::dangling is called with T=u8, this means the pointer returns is 1, and it's invalid for ZSTs with larger alignments.

Right, this interface is not meant to handle "allocations" for ZSTs.

But you're right, since alloc is a safe function, we should return a properly aligned pointer.

Quoted 6 lines

And this is unfixable even if the realloc implementation is changed. Let's say the realloc now returns a dangling pointer that is suitable aligned. Now let's see what happens when the Allocator::free is called. kfree would be trying to free a Rust-side ZST pointer, but it has no way to know that it's ZST!

Quoted 8 lines

Right, that's why it's not valid to call free with dangling pointers.

From the safety comment of free:

"ptr must point to an existing and valid memory allocation created by this Allocator and must not be a dangling pointer."

We still need the same in realloc though.

I don't agree with this reading. If you allocate something with alloc and it doesn't return an error then you should be able to feed it to free. Whether the allocator does actual allocation when size is zero or return a dangling pointer shouldn't matter to the caller.

The fact you Kmalloc returns a dangling pointer for ZST is an implementation detail and the caller shouldn't care (and it also couldn't check whether it's a dangling pointer). Nothing in your alloc doc mention about dangling pointer return for zero-sized alloc at all.

Quoted 12 lines

Quoted 12 lines

I can see 3 ways of fixing this:
1. Reject ZSTs that have larger alignment than 16 and fix the realloc implementation to return suitable aligned ZST pointer. I don't particularly like the idea of allocating ZST can fail though.
2. Say ZST must be handled by the caller, and make alloc function unsafe. This means that we essentially revert to the GlobalAlloc design of Rust, and all callers have to check for ZST.
3. Accept the old_layout and use it to check whether the allocation is ZST allocation.

Quoted 6 lines

Quoted 1 line

My personal preference is 3.

There is also 4.

Let alloc and realloc return a properly aligned dangling pointer for size == 0 and don't accept dangling pointers in realloc and free.

I'll consider the API design to be bad if I can't pass allocated pointer to free. If caller needs to handle ZST specially then we might as well just ban it completely.

Quoted 11 lines

And 5.

Reject the combination of None and size == 0 entirely, as earlier proposed by Benno.

I'm fine with both, 4. and 5. with a slight preference for 4.

I'd also go along with 1., as a mix of 4. and 5.

I really don't like making alloc unsafe, and I really don't want to have old_layout in free. Please let's not discuss this again. :-)

I don't buy it.

Your argument for having old_layout is so that the caller doesn't need to care about the size. But as demonstrated the caller *does* need to care about whether the size is zero.

Our previous discussion doesn't cover the particular case of ZST and you said that it reason arise that we need this extra parameter, then it could be added. It feels to me that sane behaviour when it comes to ZST allocation is a very good reason.

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)  

Just to add that if you *really* want to avoid the old layout param, another approach accceptable to me is to have a NonZeroLayout and have alloc only accept that.

Either Allocator trait handles ZST well or it refuses to handle them at all. No "it works for alloc but not for free" please.

Best,
Gary

Quoted 8 lines

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)  

Quoted 4 lines · On Sun, 15 Sep 2024 19:02:40 +0200 Danilo Krummrich <[email protected]> wrote:

There is also 4.

Let alloc and realloc return a properly aligned dangling pointer for size == 0 and don't accept dangling pointers in realloc and free.

I'll consider the API design to be bad if I can't pass allocated pointer to free. If caller needs to handle ZST specially then we might as well just ban it completely.

Quoted 6 lines

And 5.

Reject the combination of None and size == 0 entirely, as earlier proposed by Benno.

Quoted 6 lines

I'm fine with both, 4. and 5. with a slight preference for 4.

I'd also go along with 1., as a mix of 4. and 5.

I really don't like making alloc unsafe, and I really don't want to have old_layout in free. Please let's not discuss this again. :-)

I don't buy it.

Your argument for having old_layout is so that the caller doesn't need to care about the size. But as demonstrated the caller *does* need to care about whether the size is zero.

Our previous discussion doesn't cover the particular case of ZST and you said that it reason arise that we need this extra parameter, then it could be added. It feels to me that sane behaviour when it comes to ZST allocation is a very good reason.

Quoted 12 lines

Quoted 12 lines

Best,
Gary

Quoted 6 lines

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)

rust/kernel/alloc/allocator.rs +1 -0

@@ -84,11 +92,18 @@ unsafe fn call(
         &self,
         ptr: Option<NonNull<u8>>,
         layout: Layout,
+        old_layout: Layout,
         flags: Flags,
     ) -> Result<NonNull<[u8]>, AllocError> {

Quoted 12 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +3 -1

@@ -84,11 +92,18 @@ unsafe fn call(
         &self,
         ptr: Option<NonNull<u8>>,
         layout: Layout,
+        old_layout: Layout,
         flags: Flags,
     ) -> Result<NonNull<[u8]>, AllocError> {
         let size = aligned_size(layout);
         let ptr = match ptr {
-            Some(ptr) => ptr.as_ptr(),
+            Some(ptr) => {
+                if old_layout.size() == 0 {

rust/kernel/alloc/allocator.rs unsafe fn call( · line 106

Quoted 5 lines

rust/kernel/alloc/allocator.rs +5 -0

+                    ptr::null()
+                } else {
+                    ptr.as_ptr()
+                }
+            }

This is making Allocator work with zero-sized types, which deviates from std. We should not do that without a reason. What is the reason?

Quoted 7 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +1 -0

@@ -84,11 +92,18 @@ unsafe fn call(
         &self,
         ptr: Option<NonNull<u8>>,
         layout: Layout,
+        old_layout: Layout,
         flags: Flags,
     ) -> Result<NonNull<[u8]>, AllocError> {

rust/kernel/alloc/allocator.rs unsafe fn call( · line 106

Quoted 10 lines

rust/kernel/alloc/allocator.rs +7 -1

         let size = aligned_size(layout);
         let ptr = match ptr {
-            Some(ptr) => ptr.as_ptr(),
+            Some(ptr) => {
+                if old_layout.size() == 0 {
+                    ptr::null()
+                } else {
+                    ptr.as_ptr()
+                }
+            }  

This is making Allocator work with zero-sized types, which deviates from std. We should not do that without a reason. What is the reason?

Alice

Quoted 22 lines · On Mon, 23 Sep 2024 15:56:28 +0200 Alice Ryhl <[email protected]> wrote:

Quoted 7 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +1 -0

@@ -84,11 +92,18 @@ unsafe fn call(
         &self,
         ptr: Option<NonNull<u8>>,
         layout: Layout,
+        old_layout: Layout,
         flags: Flags,
     ) -> Result<NonNull<[u8]>, AllocError> {

rust/kernel/alloc/allocator.rs unsafe fn call( · line 106

Quoted 10 lines

rust/kernel/alloc/allocator.rs +7 -1

         let size = aligned_size(layout);
         let ptr = match ptr {
-            Some(ptr) => ptr.as_ptr(),
+            Some(ptr) => {
+                if old_layout.size() == 0 {
+                    ptr::null()
+                } else {
+                    ptr.as_ptr()
+                }
+            }  

This is making Allocator work with zero-sized types, which deviates from std. We should not do that without a reason. What is the reason?

Quoted 1 line

Alice

As Benno said, this makes the API closer to Rust allocator_api Allocator trait as opposed to deviation.

There's one benefit of doing this (discussed with Danilo off-list), which is it removes ZST special casing from caller. This RFC patch simplifies Box handling, and if we add this line to the safety doc

ptr does not need to be a pointer returned by this allocator if the layout is zero-sized.

then the Vec can also be simplified, removing all logics handling ZST specially, except for Vec::new() which it forges a well-aligned dangling pointer from nowhere.

Best,
Gary

Quoted 37 lines · Gary Guo

Quoted 22 lines · On Mon, 23 Sep 2024 15:56:28 +0200 Alice Ryhl <[email protected]> wrote:

Quoted 7 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +1 -0

@@ -84,11 +92,18 @@ unsafe fn call(
         &self,
         ptr: Option<NonNull<u8>>,
         layout: Layout,
+        old_layout: Layout,
         flags: Flags,
     ) -> Result<NonNull<[u8]>, AllocError> {

rust/kernel/alloc/allocator.rs unsafe fn call( · line 106

Quoted 10 lines

rust/kernel/alloc/allocator.rs +7 -1

         let size = aligned_size(layout);
         let ptr = match ptr {
-            Some(ptr) => ptr.as_ptr(),
+            Some(ptr) => {
+                if old_layout.size() == 0 {
+                    ptr::null()
+                } else {
+                    ptr.as_ptr()
+                }
+            }  

This is making Allocator work with zero-sized types, which deviates from std. We should not do that without a reason. What is the reason?

Quoted 1 line

Alice

As Benno said, this makes the API closer to Rust allocator_api Allocator trait as opposed to deviation.

There's one benefit of doing this (discussed with Danilo off-list), which is it removes ZST special casing from caller. This RFC patch simplifies Box handling, and if we add this line to the safety doc

ptr does not need to be a pointer returned by this allocator if the layout is zero-sized.

Quoted 3 lines

then the Vec can also be simplified, removing all logics handling ZST specially, except for Vec::new() which it forges a well-aligned dangling pointer from nowhere.

Partially, we still need the additional Layout for Allocator::free, which in Vec::drop and IntoIter::drop looks like this:

let layout = Layout::array::<T>(self.cap).unwrap();

I really dislike that this can potentially transform into BUG(), but that's probably unrelated to this patch series.

Quoted 4 lines

Best,
Gary

Quoted 37 lines · Gary Guo

Quoted 22 lines · On Mon, 23 Sep 2024 15:56:28 +0200 Alice Ryhl <[email protected]> wrote:

Quoted 7 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +1 -0

@@ -84,11 +92,18 @@ unsafe fn call(
         &self,
         ptr: Option<NonNull<u8>>,
         layout: Layout,
+        old_layout: Layout,
         flags: Flags,
     ) -> Result<NonNull<[u8]>, AllocError> {

rust/kernel/alloc/allocator.rs unsafe fn call( · line 106

Quoted 10 lines

rust/kernel/alloc/allocator.rs +7 -1

         let size = aligned_size(layout);
         let ptr = match ptr {
-            Some(ptr) => ptr.as_ptr(),
+            Some(ptr) => {
+                if old_layout.size() == 0 {
+                    ptr::null()
+                } else {
+                    ptr.as_ptr()
+                }
+            }    

This is making Allocator work with zero-sized types, which deviates from std. We should not do that without a reason. What is the reason?

Quoted 1 line

Alice

As Benno said, this makes the API closer to Rust allocator_api Allocator trait as opposed to deviation.

There's one benefit of doing this (discussed with Danilo off-list), which is it removes ZST special casing from caller. This RFC patch simplifies Box handling, and if we add this line to the safety doc

ptr does not need to be a pointer returned by this allocator if the layout is zero-sized.

Quoted 3 lines

then the Vec can also be simplified, removing all logics handling ZST specially, except for Vec::new() which it forges a well-aligned dangling pointer from nowhere.

Partially, we still need the additional Layout for Allocator::free, which in Vec::drop and IntoIter::drop looks like this:

let layout = Layout::array::<T>(self.cap).unwrap();

I really dislike that this can potentially transform into BUG(), but that's probably unrelated to this patch series.

rust/kernel/alloc/allocator.rs +44 -0

+/// # Invariants
+///
+/// One of the following `krealloc`, `vrealloc`, `kvrealloc`.
+struct ReallocFunc(
+    unsafe extern "C" fn(*const core::ffi::c_void, usize, u32) -> *mut core::ffi::c_void,
+);
+
+impl ReallocFunc {
+    // INVARIANT: `krealloc` satisfies the type invariants.
+    const KREALLOC: Self = Self(bindings::krealloc);
+
+    /// # Safety
+    ///
+    /// This method has the same safety requirements as [`Allocator::realloc`].
+    ///
+    /// # Guarantees
+    ///
+    /// This method has the same guarantees as `Allocator::realloc`. Additionally
+    /// - it accepts any pointer to a valid memory allocation allocated by this function.
+    /// - memory allocated by this function remains valid until it is passed to this function.
+    unsafe fn call(
+        &self,
+        ptr: Option<NonNull<u8>>,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let size = aligned_size(layout);
+        let ptr = match ptr {
+            Some(ptr) => ptr.as_ptr(),
+            None => ptr::null(),
+        };
+
+        // SAFETY:
+        // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc` and thus only requires that
+        //   `ptr` is NULL or valid.
+        // - `ptr` is either NULL or valid by the safety requirements of this function.
+        //
+        // GUARANTEE:
+        // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc`.
+        // - Those functions provide the guarantees of this function.
+        let raw_ptr = unsafe {
+            // If `size == 0` and `ptr != NULL` the memory behind the pointer is freed.
+            self.0(ptr.cast(), size, flags.0).cast()
+        };

rust/kernel/alloc/allocator.rs +17 -1

+
+// SAFETY: `realloc` delegates to `ReallocFunc::call`, which guarantees that
+// - memory remains valid until it is explicitly freed,
+// - passing a pointer to a valid memory allocation is OK,
+// - `realloc` satisfies the guarantees, since `ReallocFunc::call` has the same.
+unsafe impl Allocator for Kmalloc {
+    #[inline]
+    unsafe fn realloc(
+        ptr: Option<NonNull<u8>>,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        // SAFETY: `ReallocFunc::call` has the same safety requirements as `Allocator::realloc`.
+        unsafe { ReallocFunc::KREALLOC.call(ptr, layout, flags) }
+    }
+}
 
 
+
 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
--

2.46.0

Quoted 51 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +51 -0

+/// # Invariants
+///
+/// One of the following `krealloc`, `vrealloc`, `kvrealloc`.
+struct ReallocFunc(
+    unsafe extern "C" fn(*const core::ffi::c_void, usize, u32) -> *mut core::ffi::c_void,
+);
+
+impl ReallocFunc {
+    // INVARIANT: `krealloc` satisfies the type invariants.
+    const KREALLOC: Self = Self(bindings::krealloc);
+
+    /// # Safety
+    ///
+    /// This method has the same safety requirements as [`Allocator::realloc`].
+    ///
+    /// # Guarantees
+    ///
+    /// This method has the same guarantees as `Allocator::realloc`. Additionally
+    /// - it accepts any pointer to a valid memory allocation allocated by this function.
+    /// - memory allocated by this function remains valid until it is passed to this function.
+    unsafe fn call(
+        &self,
+        ptr: Option<NonNull<u8>>,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let size = aligned_size(layout);
+        let ptr = match ptr {
+            Some(ptr) => ptr.as_ptr(),
+            None => ptr::null(),
+        };
+
+        // SAFETY:
+        // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc` and thus only requires that
+        //   `ptr` is NULL or valid.
+        // - `ptr` is either NULL or valid by the safety requirements of this function.
+        //
+        // GUARANTEE:
+        // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc`.
+        // - Those functions provide the guarantees of this function.
+        let raw_ptr = unsafe {
+            // If `size == 0` and `ptr != NULL` the memory behind the pointer is freed.
+            self.0(ptr.cast(), size, flags.0).cast()
+        };
+
+        let ptr = if size == 0 {
+            NonNull::dangling()
+        } else {
+            NonNull::new(raw_ptr).ok_or(AllocError)?
+        };
+

rust/kernel/alloc/allocator.rs pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F · line 108

Quoted 3 lines

rust/kernel/alloc/allocator.rs +3 -0

+        Ok(NonNull::slice_from_raw_parts(ptr, size))
+    }
+}

I remember asking you to split this into a different commit. I think you argued that it would be better to keep it in the same commit when bisecting. I don't think that applies in this case, are there any other disadvantages?

---
Cheers,
Benno

Quoted 25 lines

rust/kernel/alloc/allocator.rs +17 -1

+
+// SAFETY: `realloc` delegates to `ReallocFunc::call`, which guarantees that
+// - memory remains valid until it is explicitly freed,
+// - passing a pointer to a valid memory allocation is OK,
+// - `realloc` satisfies the guarantees, since `ReallocFunc::call` has the same.
+unsafe impl Allocator for Kmalloc {
+    #[inline]
+    unsafe fn realloc(
+        ptr: Option<NonNull<u8>>,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        // SAFETY: `ReallocFunc::call` has the same safety requirements as `Allocator::realloc`.
+        unsafe { ReallocFunc::KREALLOC.call(ptr, layout, flags) }
+    }
+}
 
 
+
 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
--

2.46.0

Quoted 52 lines · Benno Lossin

Quoted 51 lines · Danilo Krummrich

rust/kernel/alloc/allocator.rs +51 -0

+/// # Invariants
+///
+/// One of the following `krealloc`, `vrealloc`, `kvrealloc`.
+struct ReallocFunc(
+    unsafe extern "C" fn(*const core::ffi::c_void, usize, u32) -> *mut core::ffi::c_void,
+);
+
+impl ReallocFunc {
+    // INVARIANT: `krealloc` satisfies the type invariants.
+    const KREALLOC: Self = Self(bindings::krealloc);
+
+    /// # Safety
+    ///
+    /// This method has the same safety requirements as [`Allocator::realloc`].
+    ///
+    /// # Guarantees
+    ///
+    /// This method has the same guarantees as `Allocator::realloc`. Additionally
+    /// - it accepts any pointer to a valid memory allocation allocated by this function.
+    /// - memory allocated by this function remains valid until it is passed to this function.
+    unsafe fn call(
+        &self,
+        ptr: Option<NonNull<u8>>,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let size = aligned_size(layout);
+        let ptr = match ptr {
+            Some(ptr) => ptr.as_ptr(),
+            None => ptr::null(),
+        };
+
+        // SAFETY:
+        // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc` and thus only requires that
+        //   `ptr` is NULL or valid.
+        // - `ptr` is either NULL or valid by the safety requirements of this function.
+        //
+        // GUARANTEE:
+        // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc`.
+        // - Those functions provide the guarantees of this function.
+        let raw_ptr = unsafe {
+            // If `size == 0` and `ptr != NULL` the memory behind the pointer is freed.
+            self.0(ptr.cast(), size, flags.0).cast()
+        };
+
+        let ptr = if size == 0 {
+            NonNull::dangling()
+        } else {
+            NonNull::new(raw_ptr).ok_or(AllocError)?
+        };
+

Quoted 8 lines

rust/kernel/alloc/allocator.rs pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F · line 108

Quoted 3 lines

rust/kernel/alloc/allocator.rs +3 -0

+        Ok(NonNull::slice_from_raw_parts(ptr, size))
+    }
+}

I remember asking you to split this into a different commit. I think you argued that it would be better to keep it in the same commit when bisecting. I don't think that applies in this case, are there any other disadvantages?

I don't really like the intermediate #[expect(dead_code)], plus it's additional work you didn't really give me a motivation for, i.e. you did not mention what would be the advantage.

But sure, I will change it for the next version.

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 vrealloc().

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/helpers/helpers.c              |  1 +
 rust/helpers/vmalloc.c              |  9 ++++++++
 rust/kernel/alloc/allocator.rs      | 36 +++++++++++++++++++++++++++++
 rust/kernel/alloc/allocator_test.rs |  1 +
 4 files changed, 47 insertions(+)
 create mode 100644 rust/helpers/vmalloc.c

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().

Reviewed-by Alice Ryhl <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/helpers/slab.c                 |  6 +++++
 rust/kernel/alloc/allocator.rs      | 35 +++++++++++++++++++++++++++++
 rust/kernel/alloc/allocator_test.rs |  1 +
 3 files changed, 42 insertions(+)

Some test cases in subsequent patches provoke allocation failures. Add __GFP_NOWARN to enable test cases to silence unpleasant warnings.

Reviewed-by Alice Ryhl <[email protected]>

Reviewed-by Benno Lossin <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/bindings/bindings_helper.h | 1 +
 rust/kernel/alloc.rs            | 5 +++++
 2 files changed, 6 insertions(+)

rust/bindings/bindings_helper.h +1 -0

index ae82e9c941af..a80783fcbe04 100644
@@ -31,4 +31,5 @@ const gfp_t RUST_CONST_HELPER_GFP_KERNEL_ACCOUNT = GFP_KERNEL_ACCOUNT;
 const gfp_t RUST_CONST_HELPER_GFP_NOWAIT = GFP_NOWAIT;
 const gfp_t RUST_CONST_HELPER___GFP_ZERO = __GFP_ZERO;
 const gfp_t RUST_CONST_HELPER___GFP_HIGHMEM = ___GFP_HIGHMEM;
+const gfp_t RUST_CONST_HELPER___GFP_NOWARN = ___GFP_NOWARN;
 const blk_features_t RUST_CONST_HELPER_BLK_FEAT_ROTATIONAL = BLK_FEAT_ROTATIONAL;

rust/kernel/alloc.rs +5 -0

index da025faf07f8..7a405d6f3034 100644
@@ -91,6 +91,11 @@ pub mod flags {
     /// use any filesystem callback.  It is very likely to fail to allocate memory, even for very
     /// small allocations.
     pub const GFP_NOWAIT: Flags = Flags(bindings::GFP_NOWAIT);
+
+    /// Suppresses allocation failure reports.
+    ///
+    /// This is normally or'd with other flags.
+    pub const __GFP_NOWARN: Flags = Flags(bindings::__GFP_NOWARN);
 }
 
 /// The kernel's [`Allocator`] trait.

Box 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 Rust's Box type, the kernel Box type 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 <[email protected]>

---
 rust/kernel/alloc.rs      |   6 +
 rust/kernel/alloc/kbox.rs | 465 ++++++++++++++++++++++++++++++++++++++
 rust/kernel/prelude.rs    |   2 +-
 3 files changed, 472 insertions(+), 1 deletion(-)
 create mode 100644 rust/kernel/alloc/kbox.rs

rust/kernel/alloc/kbox.rs new file +22 -0

+    /// aligned for and holds a valid `T`. The caller passes ownership of the allocation to the
+    /// `Box`.
+    ///
+    /// For ZSTs, `raw` must be a dangling, well aligned pointer.
+    #[inline]
+    pub const unsafe fn from_raw(raw: *mut T) -> Self {
+        // INVARIANT: Validity of `raw` is guaranteed by the safety preconditions of this function.
+        // SAFETY: By the safety preconditions of this function, `raw` is not a NULL pointer.
+        Self(unsafe { NonNull::new_unchecked(raw) }, PhantomData::<A>)
+    }
+
+    /// Consumes the `Box<T, A>` and returns a raw pointer.
+    ///
+    /// This will not run the destructor of `T` and for non-ZSTs the allocation will stay alive
+    /// indefinitely. Use [`Box::from_raw`] to recover the [`Box`], drop the value and free the
+    /// allocation, if any.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let x = KBox::new(24, GFP_KERNEL)?;
+    /// let ptr = KBox::into_raw(x);

rust/kernel/alloc/kbox.rs new file +12 -0

+    }
+
+    /// Consumes and leaks the `Box<T, A>` and returns a mutable reference.
+    ///
+    /// See [Box::into_raw] for more details.
+    #[inline]
+    pub fn leak<'a>(b: Self) -> &'a mut T {
+        // SAFETY: `Box::into_raw` always returns a properly aligned and dereferenceable pointer
+        // which points to an initialized instance of `T`.
+        unsafe { &mut *Box::into_raw(b) }
+    }
+}

Box 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 Rust's Box type, the kernel Box type 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 <[email protected]>

---
 rust/kernel/alloc.rs      |   6 +
 rust/kernel/alloc/kbox.rs | 465 ++++++++++++++++++++++++++++++++++++++
 rust/kernel/prelude.rs    |   2 +-
 3 files changed, 472 insertions(+), 1 deletion(-)
 create mode 100644 rust/kernel/alloc/kbox.rs

rust/kernel/alloc.rs +6 -0

index 7a405d6f3034..b1f28334b27a 100644
@@ -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,11 @@
 #[cfg(any(test, testlib))]
 pub use self::allocator_test as allocator;
 
+pub use self::kbox::Box;
+pub use self::kbox::KBox;
+pub use self::kbox::KVBox;
+pub use self::kbox::VBox;
+
 /// Indicates an allocation error.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub struct AllocError;

rust/kernel/alloc/kbox.rs new file +125 -0

new file mode 100644
index 000000000000..6188494f040d
@@ -0,0 +1,465 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Implementation of [`Box`].
+
+#[allow(unused_imports)] // Used in doc comments.
+use super::allocator::{KVmalloc, Kmalloc, Vmalloc};
+use super::{AllocError, Allocator, Flags};
+use core::fmt;
+use core::marker::PhantomData;
+use core::mem::ManuallyDrop;
+use core::mem::MaybeUninit;
+use core::ops::{Deref, DerefMut};
+use core::pin::Pin;
+use core::ptr::NonNull;
+use core::result::Result;
+
+use crate::init::{InPlaceInit, InPlaceWrite, Init, PinInit};
+use crate::types::ForeignOwnable;
+
+/// The kernel's [`Box`] type -- a heap allocation for a single value of type `T`.
+///
+/// This is the kernel's version of the Rust stdlib's `Box`. There are several of differences,
+/// for example no `noalias` attribute is emitted and partially moving out of a `Box` is not
+/// supported. There are also several API differences, e.g. `Box` always requires an [`Allocator`]
+/// implementation to be passed as generic, page [`Flags`] when allocating memory and all functions
+/// that may allocate memory are fallible.
+///
+/// `Box` works with any of the kernel's allocators, e.g. [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`].
+/// There are aliases for `Box` with these allocators ([`KBox`], [`VBox`], [`KVBox`]).
+///
+/// When dropping a [`Box`], the value is also dropped and the heap memory is automatically freed.
+///
+/// # Examples
+///
+/// ```
+/// let b = KBox::<u64>::new(24_u64, GFP_KERNEL)?;
+///
+/// assert_eq!(*b, 24_u64);
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// ```
+/// # use kernel::bindings;
+/// const SIZE: usize = bindings::KMALLOC_MAX_SIZE as usize + 1;
+/// struct Huge([u8; SIZE]);
+///
+/// assert!(KBox::<Huge>::new_uninit(GFP_KERNEL | __GFP_NOWARN).is_err());
+/// ```
+///
+/// ```
+/// # use kernel::bindings;
+/// const SIZE: usize = bindings::KMALLOC_MAX_SIZE as usize + 1;
+/// struct Huge([u8; SIZE]);
+///
+/// assert!(KVBox::<Huge>::new_uninit(GFP_KERNEL).is_ok());
+/// ```
+///
+/// # Invariants
+///
+/// `self.0` is always properly aligned and either points to memory allocated with `A` or, for
+/// zero-sized types, is a dangling, well aligned pointer.
+#[repr(transparent)]
+pub struct Box<T: ?Sized, A: Allocator>(NonNull<T>, PhantomData<A>);
+
+/// Type alias for [`Box`] with a [`Kmalloc`] allocator.
+///
+/// # Examples
+///
+/// ```
+/// let b = KBox::new(24_u64, GFP_KERNEL)?;
+///
+/// assert_eq!(*b, 24_u64);
+/// # Ok::<(), Error>(())
+/// ```
+pub type KBox<T> = Box<T, super::allocator::Kmalloc>;
+
+/// Type alias for [`Box`] with a [`Vmalloc`] allocator.
+///
+/// # Examples
+///
+/// ```
+/// let b = VBox::new(24_u64, GFP_KERNEL)?;
+///
+/// assert_eq!(*b, 24_u64);
+/// # Ok::<(), Error>(())
+/// ```
+pub type VBox<T> = Box<T, super::allocator::Vmalloc>;
+
+/// Type alias for [`Box`] with a [`KVmalloc`] allocator.
+///
+/// # Examples
+///
+/// ```
+/// let b = KVBox::new(24_u64, GFP_KERNEL)?;
+///
+/// assert_eq!(*b, 24_u64);
+/// # Ok::<(), Error>(())
+/// ```
+pub type KVBox<T> = Box<T, super::allocator::KVmalloc>;
+
+// SAFETY: `Box` is `Send` if `T` is `Send` because the `Box` owns a `T`.
+unsafe impl<T, A> Send for Box<T, A>
+where
+    T: Send + ?Sized,
+    A: Allocator,
+{
+}
+
+// SAFETY: `Box` is `Sync` if `T` is `Sync` because the `Box` owns a `T`.
+unsafe impl<T, A> Sync for Box<T, A>
+where
+    T: Sync + ?Sized,
+    A: Allocator,
+{
+}
+
+impl<T, A> Box<T, A>
+where
+    T: ?Sized,
+    A: Allocator,
+{
+    /// Creates a new `Box<T, A>` from a raw pointer.
+    ///
+    /// # Safety
+    ///

rust/kernel/alloc/kbox.rs new file +39 -0

+    }
+
+    /// Consumes the `Box<T, A>` and returns a raw pointer.
+    ///
+    /// This will not run the destructor of `T` and for non-ZSTs the allocation will stay alive
+    /// indefinitely. Use [`Box::from_raw`] to recover the [`Box`], drop the value and free the
+    /// allocation, if any.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let x = KBox::new(24, GFP_KERNEL)?;
+    /// let ptr = KBox::into_raw(x);
+    /// let x = unsafe { KBox::from_raw(ptr) };
+    ///
+    /// assert_eq!(*x, 24);
+    /// # Ok::<(), Error>(())
+    /// ```
+    #[inline]
+    pub fn into_raw(b: Self) -> *mut T {
+        let b = ManuallyDrop::new(b);
+
+        b.0.as_ptr()
+    }
+
+    /// Consumes and leaks the `Box<T, A>` and returns a mutable reference.
+    ///
+    /// See [Box::into_raw] for more details.
+    #[inline]
+    pub fn leak<'a>(b: Self) -> &'a mut T {
+        // SAFETY: `Box::into_raw` always returns a properly aligned and dereferenceable pointer
+        // which points to an initialized instance of `T`.
+        unsafe { &mut *Box::into_raw(b) }
+    }
+}
+
+impl<T, A> Box<MaybeUninit<T>, A>
+where
+    A: Allocator,

rust/kernel/alloc/kbox.rs new file +4 -0

+        let raw = Self::into_raw(b);
+
+        // SAFETY: `raw` comes from a previous call to `Box::into_raw`. By the safety requirements
+        // of this function, the value inside the `Box` is in an initialized state. Hence, it is

rust/kernel/alloc/kbox.rs new file +18 -0

+}
+
+impl<T, A> Box<T, A>
+where
+    A: Allocator,
+{
+    fn is_zst() -> bool {
+        core::mem::size_of::<T>() == 0
+    }
+
+    /// Creates a new `Box<T, A>` and initializes its contents with `x`.
+    ///
+    /// New memory is allocated with `A`. The allocation may fail, in which case an error is
+    /// returned. For ZSTs no memory is allocated.
+    pub fn new(x: T, flags: Flags) -> Result<Self, AllocError> {
+        let b = Self::new_uninit(flags)?;
+        Ok(Box::write(b, x))
+    }

Now that we got the kernel Box type in place, convert all existing Box users to make use of it.

Reviewed-by Alice Ryhl <[email protected]>

Reviewed-by Benno Lossin <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 drivers/block/rnull.rs            |  4 +--
 rust/kernel/init.rs               | 51 ++++++++++++++++---------------
 rust/kernel/init/__internal.rs    |  2 +-
 rust/kernel/rbtree.rs             | 49 ++++++++++++++++-------------
 rust/kernel/sync/arc.rs           | 17 +++++------
 rust/kernel/sync/condvar.rs       |  4 +--
 rust/kernel/sync/lock/mutex.rs    |  2 +-
 rust/kernel/sync/lock/spinlock.rs |  2 +-
 rust/kernel/workqueue.rs          | 20 ++++++------
 rust/macros/lib.rs                |  6 ++--
 10 files changed, 81 insertions(+), 76 deletions(-)

Quoted 6 lines · On Thu, 12 Sep 2024 00:52:46 +0200 Danilo Krummrich <[email protected]> wrote:

Now that we got the kernel Box type in place, convert all existing Box users to make use of it.

Reviewed-by Alice Ryhl <[email protected]>

Reviewed-by Benno Lossin <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

Reviewed-by Gary Guo <[email protected]>

Have you considered defaulting the A in Box to Kmalloc? This would avoid doing a lot of tree-wide changes.

If you have a reason against it (I'm pretty sure you have), then probably you should put it in the commit message.

Best,
Gary

Quoted 12 lines

---
 drivers/block/rnull.rs            |  4 +--
 rust/kernel/init.rs               | 51 ++++++++++++++++---------------
 rust/kernel/init/__internal.rs    |  2 +-
 rust/kernel/rbtree.rs             | 49 ++++++++++++++++-------------
 rust/kernel/sync/arc.rs           | 17 +++++------
 rust/kernel/sync/condvar.rs       |  4 +--
 rust/kernel/sync/lock/mutex.rs    |  2 +-
 rust/kernel/sync/lock/spinlock.rs |  2 +-
 rust/kernel/workqueue.rs          | 20 ++++++------
 rust/macros/lib.rs                |  6 ++--
 10 files changed, 81 insertions(+), 76 deletions(-)

Now that all existing Box users were moved to the kernel Box type, remove the BoxExt extension and all other related extensions.

Reviewed-by Alice Ryhl <[email protected]>

Reviewed-by Benno Lossin <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/alloc.rs         |  1 -
 rust/kernel/alloc/box_ext.rs | 87 ------------------------------------
 rust/kernel/init.rs          | 46 +------------------
 rust/kernel/lib.rs           |  1 -
 rust/kernel/prelude.rs       |  4 +-
 rust/kernel/types.rs         | 50 ---------------------
 6 files changed, 3 insertions(+), 186 deletions(-)
 delete mode 100644 rust/kernel/alloc/box_ext.rs

Now that we removed BoxExt and the corresponding includes in prelude.rs, add the new kernel Box type instead.

Reviewed-by Alice Ryhl <[email protected]>

Reviewed-by Benno Lossin <[email protected]>

Signed-off-by Danilo Krummrich <[email protected]>

---
 rust/kernel/prelude.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

rust/kernel/prelude.rs +1 -1

index c1f8e5c832e2..d5f2fe42d093 100644
@@ -14,7 +14,7 @@
 #[doc(no_inline)]
 pub use core::pin::Pin;
 
-pub use crate::alloc::{flags::*, vec_ext::VecExt, KBox, KVBox, VBox};
+pub use crate::alloc::{flags::*, vec_ext::VecExt, Box, KBox, KVBox, VBox};
 
 #[doc(no_inline)]
 pub use alloc::vec::Vec;

rust/kernel/alloc/kvec.rs new file +12 -0

new file mode 100644
index 000000000000..631a44e19f35
@@ -0,0 +1,638 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Implementation of [`Vec`].
+
+use super::{
+    allocator::{KVmalloc, Kmalloc, Vmalloc},
+    AllocError, Allocator, Box, Flags,
+};
+use core::{
+    fmt,
+    marker::PhantomData,
+    mem::{ManuallyDrop, MaybeUninit},

rust/kernel/alloc/kvec.rs new file +28 -0

+///
+/// # Examples
+///
+/// ```
+/// let mut v = kernel::kvec![];
+/// v.push(1, GFP_KERNEL)?;
+/// assert_eq!(v, [1]);
+///
+/// let mut v = kernel::kvec![1; 3]?;
+/// v.push(4, GFP_KERNEL)?;
+/// assert_eq!(v, [1, 1, 1, 4]);
+///
+/// let mut v = kernel::kvec![1, 2, 3]?;
+/// v.push(4, GFP_KERNEL)?;
+/// 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, GFP_KERNEL)
+    );
+    ($($x:expr),+ $(,)?) => (
+        match $crate::alloc::KBox::new_uninit(GFP_KERNEL) {