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

[Benno Lossin <benno.lossin@proton.me>]

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