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

[Gary Guo]

On Thu, 12 Sep 2024 00:52:37 +0200
Danilo Krummrich <dakr@xxxxxxxxxx> 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

> 
> Reviewed-by: Alice Ryhl <aliceryhl@xxxxxxxxxx>
> Signed-off-by: Danilo Krummrich <dakr@xxxxxxxxxx>
> ---
>  rust/kernel/alloc.rs | 112 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 112 insertions(+)
> 
> diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> index 1966bd407017..6c21bd2edad9 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::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.
> +///
> +/// 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.

> +///
> +/// 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.

> +///
> +/// # 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
> +// 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.

> +//
> +// 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.

> +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.
> +    ///
> +    /// 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.

> +    /// 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)) };
> +    }
> +}