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 allocator for the subsequently introduced types `KBox` and
`KVec`.

Signed-off-by: Danilo Krummrich <dakr@kernel.org>
---
 rust/helpers.c                 |  3 +-
 rust/kernel/alloc.rs           |  2 +-
 rust/kernel/alloc/allocator.rs | 68 +++++++++++++++++++++++++++++++++-
 3 files changed, 69 insertions(+), 4 deletions(-)

diff --git a/rust/helpers.c b/rust/helpers.c
index 92d3c03ae1bd..9f7275493365 100644
--- a/rust/helpers.c
+++ b/rust/helpers.c
@@ -193,8 +193,7 @@ void rust_helper_init_work_with_key(struct work_struct *work, work_func_t func,
 }
 EXPORT_SYMBOL_GPL(rust_helper_init_work_with_key);
 
-void * __must_check __realloc_size(2)
-rust_helper_krealloc(const void *objp, size_t new_size, gfp_t flags)
+void *rust_helper_krealloc(const void *objp, size_t new_size, gfp_t flags)
 {
 	return krealloc(objp, new_size, flags);
 }
diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
index 8a71a589469d..bc01a17df5e0 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 2c1eae25da84..c6ad1dd59dd0 100644
--- a/rust/kernel/alloc/allocator.rs
+++ b/rust/kernel/alloc/allocator.rs
@@ -5,8 +5,16 @@
 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 {
@@ -40,6 +48,64 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
     }
 }
 
+/// # 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.
+    fn krealloc() -> Self {
+        Self(bindings::krealloc)
+    }
+
+    /// # Safety
+    ///
+    /// This method has the exact same safety requirements as `Allocator::realloc`.
+    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: `ptr` is valid by the safety requirements 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)?
+        };
+
+        Ok(NonNull::slice_from_raw_parts(ptr, size))
+    }
+}
+
+unsafe impl Allocator for Kmalloc {
+    unsafe fn realloc(
+        ptr: Option<NonNull<u8>>,
+        layout: Layout,
+        flags: Flags,
+    ) -> Result<NonNull<[u8]>, AllocError> {
+        let realloc = ReallocFunc::krealloc();
+
+        // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously
+        // allocated with this `Allocator`.
+        unsafe { realloc.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.45.2

On 05.08.24 17:19, Danilo Krummrich wrote:
> 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 allocator for the subsequently introduced types `KBox` and
> `KVec`.
> 
> Signed-off-by: Danilo Krummrich <dakr@kernel.org>
> ---
>  rust/helpers.c                 |  3 +-
>  rust/kernel/alloc.rs           |  2 +-
>  rust/kernel/alloc/allocator.rs | 68 +++++++++++++++++++++++++++++++++-
>  3 files changed, 69 insertions(+), 4 deletions(-)
> 
> diff --git a/rust/helpers.c b/rust/helpers.c
> index 92d3c03ae1bd..9f7275493365 100644
> --- a/rust/helpers.c
> +++ b/rust/helpers.c
> @@ -193,8 +193,7 @@ void rust_helper_init_work_with_key(struct work_struct *work, work_func_t func,
>  }
>  EXPORT_SYMBOL_GPL(rust_helper_init_work_with_key);
> 
> -void * __must_check __realloc_size(2)
> -rust_helper_krealloc(const void *objp, size_t new_size, gfp_t flags)
> +void *rust_helper_krealloc(const void *objp, size_t new_size, gfp_t flags)
>  {
>  	return krealloc(objp, new_size, flags);
>  }
> diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> index 8a71a589469d..bc01a17df5e0 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 2c1eae25da84..c6ad1dd59dd0 100644
> --- a/rust/kernel/alloc/allocator.rs
> +++ b/rust/kernel/alloc/allocator.rs
> @@ -5,8 +5,16 @@
>  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 {
> @@ -40,6 +48,64 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
>      }
>  }
> 
> +/// # 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.

This INVARIANT comment should be moved one line downwards.

> +    fn krealloc() -> Self {
> +        Self(bindings::krealloc)
> +    }
> +
> +    /// # Safety
> +    ///
> +    /// This method has the exact same safety requirements as `Allocator::realloc`.

I would remove "exact", I don't think we want to mean "almost the same"
when we write just "same".

> +    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: `ptr` is valid by the safety requirements of this function.

"`ptr` is either NULL or valid by the safety requirements 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()

If we call `realloc(Some(ptr), <layout with size = 0>, ...)`, then this
leaks the pointer returned by the call to `self.0` above. I don't know
what the return value of the different functions are that can appear in
`self.0`, do they return NULL?

What about the following sequence:

    let ptr = realloc(None, <layout with size = 0>, ...);
    let ptr = realloc(Some(ptr), <layout with size = 0>, ...);

Then the above call to `self.0` is done with a dangling pointer, can the
functions that appear in `self.0` handle that?

> +        } else {
> +            NonNull::new(raw_ptr).ok_or(AllocError)?
> +        };
> +
> +        Ok(NonNull::slice_from_raw_parts(ptr, size))
> +    }
> +}
> +
> +unsafe impl Allocator for Kmalloc {
> +    unsafe fn realloc(
> +        ptr: Option<NonNull<u8>>,
> +        layout: Layout,
> +        flags: Flags,
> +    ) -> Result<NonNull<[u8]>, AllocError> {
> +        let realloc = ReallocFunc::krealloc();
> +
> +        // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously
> +        // allocated with this `Allocator`.

What about the other requirements? (they should be satisfied, since they
are also requirements for calling this function)

> +        unsafe { realloc.call(ptr, layout, flags) }

If you make `ReallocFunc::krealloc()` into a constant
`ReallocFunc::KREALLOC`, then we could avoid the let binding above.

---
Cheers,
Benno

> +    }
> +}
> +
>  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.45.2
> 

On Tue, Aug 06, 2024 at 04:51:28PM +0000, Benno Lossin wrote:
> On 05.08.24 17:19, Danilo Krummrich wrote:
> > 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 allocator for the subsequently introduced types `KBox` and
> > `KVec`.
> > 
> > Signed-off-by: Danilo Krummrich <dakr@kernel.org>
> > ---
> >  rust/helpers.c                 |  3 +-
> >  rust/kernel/alloc.rs           |  2 +-
> >  rust/kernel/alloc/allocator.rs | 68 +++++++++++++++++++++++++++++++++-
> >  3 files changed, 69 insertions(+), 4 deletions(-)
> > 
> > diff --git a/rust/helpers.c b/rust/helpers.c
> > index 92d3c03ae1bd..9f7275493365 100644
> > --- a/rust/helpers.c
> > +++ b/rust/helpers.c
> > @@ -193,8 +193,7 @@ void rust_helper_init_work_with_key(struct work_struct *work, work_func_t func,
> >  }
> >  EXPORT_SYMBOL_GPL(rust_helper_init_work_with_key);
> > 
> > -void * __must_check __realloc_size(2)
> > -rust_helper_krealloc(const void *objp, size_t new_size, gfp_t flags)
> > +void *rust_helper_krealloc(const void *objp, size_t new_size, gfp_t flags)
> >  {
> >  	return krealloc(objp, new_size, flags);
> >  }
> > diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs
> > index 8a71a589469d..bc01a17df5e0 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 2c1eae25da84..c6ad1dd59dd0 100644
> > --- a/rust/kernel/alloc/allocator.rs
> > +++ b/rust/kernel/alloc/allocator.rs
> > @@ -5,8 +5,16 @@
> >  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 {
> > @@ -40,6 +48,64 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F
> >      }
> >  }
> > 
> > +/// # 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.
> 
> This INVARIANT comment should be moved one line downwards.
> 
> > +    fn krealloc() -> Self {
> > +        Self(bindings::krealloc)
> > +    }
> > +
> > +    /// # Safety
> > +    ///
> > +    /// This method has the exact same safety requirements as `Allocator::realloc`.
> 
> I would remove "exact", I don't think we want to mean "almost the same"
> when we write just "same".
> 
> > +    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: `ptr` is valid by the safety requirements of this function.
> 
> "`ptr` is either NULL or valid by the safety requirements of this
> function."

Agreed, for this one and the above ones.

> 
> > +        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()
> 
> If we call `realloc(Some(ptr), <layout with size = 0>, ...)`, then this
> leaks the pointer returned by the call to `self.0` above. I don't know
> what the return value of the different functions are that can appear in
> `self.0`, do they return NULL?

That is fine, we don't care about the return value. All `ReallocFunc` free the
memory behind `ptr` if called with a size of zero. But to answer the question,
they return either NULL or ZERO_SIZE_PTR.

> 
> What about the following sequence:
> 
>     let ptr = realloc(None, <layout with size = 0>, ...);
>     let ptr = realloc(Some(ptr), <layout with size = 0>, ...);
> 
> Then the above call to `self.0` is done with a dangling pointer, can the
> functions that appear in `self.0` handle that?

This would be incorrect.

Calling `realloc(Some(ptr), <layout with size = 0>, ...)` frees the memory
behind `ptr`. This is guranteed behavior for all `ReallocFunc`s, i.e.
krealloc(), vrealloc(), kvrealloc().

> 
> > +        } else {
> > +            NonNull::new(raw_ptr).ok_or(AllocError)?
> > +        };
> > +
> > +        Ok(NonNull::slice_from_raw_parts(ptr, size))
> > +    }
> > +}
> > +
> > +unsafe impl Allocator for Kmalloc {
> > +    unsafe fn realloc(
> > +        ptr: Option<NonNull<u8>>,
> > +        layout: Layout,
> > +        flags: Flags,
> > +    ) -> Result<NonNull<[u8]>, AllocError> {
> > +        let realloc = ReallocFunc::krealloc();
> > +
> > +        // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously
> > +        // allocated with this `Allocator`.
> 
> What about the other requirements? (they should be satisfied, since they
> are also requirements for calling this function)

Indeed, I think we should just write that by definition `Realloc::call` has the
same safety requirements as `Allocator::realloc`.

> 
> > +        unsafe { realloc.call(ptr, layout, flags) }
> 
> If you make `ReallocFunc::krealloc()` into a constant
> `ReallocFunc::KREALLOC`, then we could avoid the let binding above.

Agreed, sounds good.

> 
> ---
> Cheers,
> Benno
> 
> > +    }
> > +}
> > +
> >  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.45.2
> > 
>

On 06.08.24 20:55, Danilo Krummrich wrote:
> On Tue, Aug 06, 2024 at 04:51:28PM +0000, Benno Lossin wrote:
>> On 05.08.24 17:19, Danilo Krummrich wrote:
>>> +        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()
>>
>> If we call `realloc(Some(ptr), <layout with size = 0>, ...)`, then this
>> leaks the pointer returned by the call to `self.0` above. I don't know
>> what the return value of the different functions are that can appear in
>> `self.0`, do they return NULL?
> 
> That is fine, we don't care about the return value. All `ReallocFunc` free the
> memory behind `ptr` if called with a size of zero. But to answer the question,
> they return either NULL or ZERO_SIZE_PTR.

I see, then it's fine. I think it would help if we know the exact
behavior of `kmalloc` & friends (either add a link to C docs or write it
down on `ReallocFunc`).

>> What about the following sequence:
>>
>>     let ptr = realloc(None, <layout with size = 0>, ...);
>>     let ptr = realloc(Some(ptr), <layout with size = 0>, ...);
>>
>> Then the above call to `self.0` is done with a dangling pointer, can the
>> functions that appear in `self.0` handle that?
> 
> This would be incorrect.
> 
> Calling `realloc(Some(ptr), <layout with size = 0>, ...)` frees the memory
> behind `ptr`. This is guranteed behavior for all `ReallocFunc`s, i.e.
> krealloc(), vrealloc(), kvrealloc().

Note that I don't use `ptr` afterwards, the code snippet above is
equivalent to this:

    let ptr = Kmalloc::alloc(<layout with size = 0>, ...);
    unsafe { Kmalloc::free(ptr) };

internally exactly the realloc calls that I put above should be called.

---
Cheers,
Benno

On Wed, Aug 07, 2024 at 07:14:13AM +0000, Benno Lossin wrote:
> On 06.08.24 20:55, Danilo Krummrich wrote:
> > On Tue, Aug 06, 2024 at 04:51:28PM +0000, Benno Lossin wrote:
> >> On 05.08.24 17:19, Danilo Krummrich wrote:
> >>> +        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()
> >>
> >> If we call `realloc(Some(ptr), <layout with size = 0>, ...)`, then this
> >> leaks the pointer returned by the call to `self.0` above. I don't know
> >> what the return value of the different functions are that can appear in
> >> `self.0`, do they return NULL?
> > 
> > That is fine, we don't care about the return value. All `ReallocFunc` free the
> > memory behind `ptr` if called with a size of zero. But to answer the question,
> > they return either NULL or ZERO_SIZE_PTR.
> 
> I see, then it's fine. I think it would help if we know the exact
> behavior of `kmalloc` & friends (either add a link to C docs or write it
> down on `ReallocFunc`).
> 
> >> What about the following sequence:
> >>
> >>     let ptr = realloc(None, <layout with size = 0>, ...);
> >>     let ptr = realloc(Some(ptr), <layout with size = 0>, ...);
> >>
> >> Then the above call to `self.0` is done with a dangling pointer, can the
> >> functions that appear in `self.0` handle that?
> > 
> > This would be incorrect.
> > 
> > Calling `realloc(Some(ptr), <layout with size = 0>, ...)` frees the memory
> > behind `ptr`. This is guranteed behavior for all `ReallocFunc`s, i.e.
> > krealloc(), vrealloc(), kvrealloc().
> 
> Note that I don't use `ptr` afterwards, the code snippet above is
> equivalent to this:
> 
>     let ptr = Kmalloc::alloc(<layout with size = 0>, ...);
>     unsafe { Kmalloc::free(ptr) };
> 
> internally exactly the realloc calls that I put above should be called.

I think I misunderstood what you mean here.

So, that's not permitted. `free` can't be called with a dangling pointer. The
kernel free functions (*1) can't handle it, and I can't detect it, since a
dangling pointer does not have a descrete value.

We can decide for a specific dangling pointer to be allowed, i.e. the dangling
pointer returned by `alloc` for a zero sized allocation is always
`dangling<u8>`, so we can assert that `free` is only allowed to be called with
what was previously returned by `alloc` or `free` and therefore disallow
dangling pointers with a different alignment.

Surely, we could also let the caller pass the old alignment, but this all sounds
complicated for something that is very trivial for the caller to take care of,
i.e. just don't try to free something that was never actually allocated.

It can also lead to subtle bugs, e.g. what if someone calls `Box::from_raw` for
a ZST with some other random pointer? Currently, that doesn't hurt us, which for
robustness, seems to be a good thing.

I think it's better to just let `Box` and `Vec` figure out if calling `free` is
the right thing to do. The code for that is simple and obvious, i.e. check if
`T` is a ZST.

*1: kfree() can handle dangling pointers up to 16 bytes aligned, see
ZERO_OR_NULL_PTR(x).

> 
> ---
> Cheers,
> Benno
>

On 07.08.24 12:11, Danilo Krummrich wrote:
> On Wed, Aug 07, 2024 at 07:14:13AM +0000, Benno Lossin wrote:
>> On 06.08.24 20:55, Danilo Krummrich wrote:
>>> On Tue, Aug 06, 2024 at 04:51:28PM +0000, Benno Lossin wrote:
>>>> On 05.08.24 17:19, Danilo Krummrich wrote:
>>>>> +        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()
>>>>
>>>> If we call `realloc(Some(ptr), <layout with size = 0>, ...)`, then this
>>>> leaks the pointer returned by the call to `self.0` above. I don't know
>>>> what the return value of the different functions are that can appear in
>>>> `self.0`, do they return NULL?
>>>
>>> That is fine, we don't care about the return value. All `ReallocFunc` free the
>>> memory behind `ptr` if called with a size of zero. But to answer the question,
>>> they return either NULL or ZERO_SIZE_PTR.
>>
>> I see, then it's fine. I think it would help if we know the exact
>> behavior of `kmalloc` & friends (either add a link to C docs or write it
>> down on `ReallocFunc`).
>>
>>>> What about the following sequence:
>>>>
>>>>     let ptr = realloc(None, <layout with size = 0>, ...);
>>>>     let ptr = realloc(Some(ptr), <layout with size = 0>, ...);
>>>>
>>>> Then the above call to `self.0` is done with a dangling pointer, can the
>>>> functions that appear in `self.0` handle that?
>>>
>>> This would be incorrect.
>>>
>>> Calling `realloc(Some(ptr), <layout with size = 0>, ...)` frees the memory
>>> behind `ptr`. This is guranteed behavior for all `ReallocFunc`s, i.e.
>>> krealloc(), vrealloc(), kvrealloc().
>>
>> Note that I don't use `ptr` afterwards, the code snippet above is
>> equivalent to this:
>>
>>     let ptr = Kmalloc::alloc(<layout with size = 0>, ...);
>>     unsafe { Kmalloc::free(ptr) };
>>
>> internally exactly the realloc calls that I put above should be called.
> 
> I think I misunderstood what you mean here.
> 
> So, that's not permitted. `free` can't be called with a dangling pointer. The
> kernel free functions (*1) can't handle it, and I can't detect it, since a
> dangling pointer does not have a descrete value.

That is true, but only if we do not have access to the old layout of the
allocation. If we add `old_layout` as a parameter, then we can handle
dangling pointers.

> We can decide for a specific dangling pointer to be allowed, i.e. the dangling
> pointer returned by `alloc` for a zero sized allocation is always
> `dangling<u8>`, so we can assert that `free` is only allowed to be called with
> what was previously returned by `alloc` or `free` and therefore disallow
> dangling pointers with a different alignment.

I don't like that.

> Surely, we could also let the caller pass the old alignment, but this all sounds
> complicated for something that is very trivial for the caller to take care of,
> i.e. just don't try to free something that was never actually allocated.
> 
> It can also lead to subtle bugs, e.g. what if someone calls `Box::from_raw` for
> a ZST with some other random pointer? Currently, that doesn't hurt us, which for
> robustness, seems to be a good thing.

I think we should forbid that. To me it's just plain wrong to take a
random integer literal and cast it to a ZST. IIRC it even is UB if that
points to a previously allocated object that has been freed (but I don't
remember where I read it...).

Also if we use the size of the old layout instead of comparing alignment
with the address of the pointer, then we avoid this issue.

> I think it's better to just let `Box` and `Vec` figure out if calling `free` is
> the right thing to do. The code for that is simple and obvious, i.e. check if
> `T` is a ZST.

I don't think that it is as simple as you make it out to be. To me this
is functionality that we can move into one place and never have to think
about again.
Also if we at some point decide to add some sort of debugging allocator
(am I right in assuming that such a thing already exists for C?) then we
might want to tag on extra data in the allocation, in that case it would
be very useful if the allocator also saw zero-sized allocations, since
we should check all allocations.

> *1: kfree() can handle dangling pointers up to 16 bytes aligned, see
> ZERO_OR_NULL_PTR(x).

I agree with you that we shouldn't rely on that.

---
Cheers,
Benno

On Wed, Aug 07, 2024 at 08:15:41PM +0000, Benno Lossin wrote:
> > So, that's not permitted. `free` can't be called with a dangling pointer. The
> > kernel free functions (*1) can't handle it, and I can't detect it, since a
> > dangling pointer does not have a descrete value.
> 
> That is true, but only if we do not have access to the old layout of the
> allocation. If we add `old_layout` as a parameter, then we can handle
> dangling pointers.

Then we'd need `free` to be `fn free(ptr: NonNull<u8>, layout: Layout)` just to
compare whether `ptr.as_ptr() == layout.align() as _`. Same for `realloc`, but
that's less weird.

It's also not that we safe code with that. `Box`, `Vec`, any other user, still
would have to create the `Layout` before they call `A::free`.

> > Surely, we could also let the caller pass the old alignment, but this all sounds
> > complicated for something that is very trivial for the caller to take care of,
> > i.e. just don't try to free something that was never actually allocated.
> > 
> > It can also lead to subtle bugs, e.g. what if someone calls `Box::from_raw` for
> > a ZST with some other random pointer? Currently, that doesn't hurt us, which for
> > robustness, seems to be a good thing.
> 
> I think we should forbid that. To me it's just plain wrong to take a
> random integer literal and cast it to a ZST. IIRC it even is UB if that
> points to a previously allocated object that has been freed (but I don't
> remember where I read it...).

I think my argument about robustness still holds even if we forbid it.

The documentation says "For operations of size zero, every pointer is valid,
including the null pointer." [1]

[1] https://doc.rust-lang.org/std/ptr/index.html

> 
> Also if we use the size of the old layout instead of comparing alignment
> with the address of the pointer, then we avoid this issue.

That is just another problem when passing the old `Layout` (or maybe just the
old size as usize). Neither do we need the old size, nor do we honor it with any
kernel allocator. This has the following implications:

(1) We never see any error if the old size that is passed is garbage (unless
    it's non-zero, when it should be zero and vice versa), which is bad.

(2) We'd need `free` to be `fn free(ptr: NonNull<u8>, size: usize)`, which is
    confusing, because it implies that an actual free relies on this size for
    freeing the memory.

If we want to avoid (1) and (2), we'd need to make it
`fn free(ptr: NonNull<u8>, zero: bool)` instead, but then also the caller can
just check this boolean and conditionally call `free`.

I don't really see why it's better to let `free` do the `if !zero` check.

On 08.08.24 01:05, Danilo Krummrich wrote:
> On Wed, Aug 07, 2024 at 08:15:41PM +0000, Benno Lossin wrote:
>>> So, that's not permitted. `free` can't be called with a dangling pointer. The
>>> kernel free functions (*1) can't handle it, and I can't detect it, since a
>>> dangling pointer does not have a descrete value.
>>
>> That is true, but only if we do not have access to the old layout of the
>> allocation. If we add `old_layout` as a parameter, then we can handle
>> dangling pointers.
> 
> Then we'd need `free` to be `fn free(ptr: NonNull<u8>, layout: Layout)` just to
> compare whether `ptr.as_ptr() == layout.align() as _`. Same for `realloc`, but
> that's less weird.

I don't think that's a problem (though we would check against the size
and not compare the address!). `Allocator` from stdlib also has the
extra argument.

> It's also not that we safe code with that. `Box`, `Vec`, any other user, still
> would have to create the `Layout` before they call `A::free`.

But for `Box` it would just be `Layout::<T>::new()` and `Vec` needs
`Layout::<T>::new().repeat(self.cap)`.

Though for `repeat` we need the `alloc_layout_extra` feature, which is
an argument against doing this.

>>> Surely, we could also let the caller pass the old alignment, but this all sounds
>>> complicated for something that is very trivial for the caller to take care of,
>>> i.e. just don't try to free something that was never actually allocated.
>>>
>>> It can also lead to subtle bugs, e.g. what if someone calls `Box::from_raw` for
>>> a ZST with some other random pointer? Currently, that doesn't hurt us, which for
>>> robustness, seems to be a good thing.
>>
>> I think we should forbid that. To me it's just plain wrong to take a
>> random integer literal and cast it to a ZST. IIRC it even is UB if that
>> points to a previously allocated object that has been freed (but I don't
>> remember where I read it...).
> 
> I think my argument about robustness still holds even if we forbid it.
> 
> The documentation says "For operations of size zero, every pointer is valid,
> including the null pointer." [1]

How does this increase robustness? I am not allowed to call `free` with
a random pointer, only pointers returned by that allocator. The same
should also be true for `Box::from_raw`. That way the ZST dangling
pointer stuff leaks into that API.

> [1] https://doc.rust-lang.org/std/ptr/index.html
> 
>>
>> Also if we use the size of the old layout instead of comparing alignment
>> with the address of the pointer, then we avoid this issue.
> 
> That is just another problem when passing the old `Layout` (or maybe just the
> old size as usize). Neither do we need the old size, nor do we honor it with any
> kernel allocator. This has the following implications:
> 
> (1) We never see any error if the old size that is passed is garbage (unless
>     it's non-zero, when it should be zero and vice versa), which is bad.

We could add debug support for that though?

> (2) We'd need `free` to be `fn free(ptr: NonNull<u8>, size: usize)`, which is
>     confusing, because it implies that an actual free relies on this size for
>     freeing the memory.

I don't think that it is confusing to ask for the old layout.

> If we want to avoid (1) and (2), we'd need to make it
> `fn free(ptr: NonNull<u8>, zero: bool)` instead, but then also the caller can
> just check this boolean and conditionally call `free`.

Yeah having `free` with a `zero: bool` sounds like a bad idea.

> I don't really see why it's better to let `free` do the `if !zero` check.

You did not reply to my last argument:

>> I think it's better to just let `Box` and `Vec` figure out if calling `free` is
>> the right thing to do. The code for that is simple and obvious, i.e. check if
>> `T` is a ZST.
>
> I don't think that it is as simple as you make it out to be. To me this
> is functionality that we can move into one place and never have to think
> about again.
> Also if we at some point decide to add some sort of debugging allocator
> (am I right in assuming that such a thing already exists for C?) then we
> might want to tag on extra data in the allocation, in that case it would
> be very useful if the allocator also saw zero-sized allocations, since
> we should check all allocations.

---
Cheers,
Benno

On Thu, Aug 08, 2024 at 08:55:29AM +0000, Benno Lossin wrote:
> On 08.08.24 01:05, Danilo Krummrich wrote:
> > On Wed, Aug 07, 2024 at 08:15:41PM +0000, Benno Lossin wrote:
> >>> So, that's not permitted. `free` can't be called with a dangling pointer. The
> >>> kernel free functions (*1) can't handle it, and I can't detect it, since a
> >>> dangling pointer does not have a descrete value.
> >>
> >> That is true, but only if we do not have access to the old layout of the
> >> allocation. If we add `old_layout` as a parameter, then we can handle
> >> dangling pointers.
> > 
> > Then we'd need `free` to be `fn free(ptr: NonNull<u8>, layout: Layout)` just to
> > compare whether `ptr.as_ptr() == layout.align() as _`. Same for `realloc`, but
> > that's less weird.
> 
> I don't think that's a problem (though we would check against the size
> and not compare the address!). `Allocator` from stdlib also has the
> extra argument.

Because `Allocator` from stdlib actually needs it, e.g. they have to open code
`realloc`, since userspace allocators don't give proper alignment guarantees.

Again, the kernel allocators neither need, nor take and honor this extra
information.

> 
> > It's also not that we safe code with that. `Box`, `Vec`, any other user, still
> > would have to create the `Layout` before they call `A::free`.
> 
> But for `Box` it would just be `Layout::<T>::new()` and `Vec` needs
> `Layout::<T>::new().repeat(self.cap)`.

Let's take `Vec` for instance, there it's either

current code
------------
```
	if cap != 0 {
		unsafe { A::free(self.ptr.as_non_null().cast()) };
	}
```

your proposal
-------------
```
	let layout = Layout::<T>::array(self.cap).unwrap();
	unsafe { A::free(self.ptr.as_non_null().cast(), layout) };
```

I really don't see how that's an improvement.

> 
> Though for `repeat` we need the `alloc_layout_extra` feature, which is
> an argument against doing this.
> 
> >>> Surely, we could also let the caller pass the old alignment, but this all sounds
> >>> complicated for something that is very trivial for the caller to take care of,
> >>> i.e. just don't try to free something that was never actually allocated.
> >>>
> >>> It can also lead to subtle bugs, e.g. what if someone calls `Box::from_raw` for
> >>> a ZST with some other random pointer? Currently, that doesn't hurt us, which for
> >>> robustness, seems to be a good thing.
> >>
> >> I think we should forbid that. To me it's just plain wrong to take a
> >> random integer literal and cast it to a ZST. IIRC it even is UB if that
> >> points to a previously allocated object that has been freed (but I don't
> >> remember where I read it...).
> > 
> > I think my argument about robustness still holds even if we forbid it.
> > 
> > The documentation says "For operations of size zero, every pointer is valid,
> > including the null pointer." [1]
> 
> How does this increase robustness? I am not allowed to call `free` with
> a random pointer, only pointers returned by that allocator. The same
> should also be true for `Box::from_raw`. That way the ZST dangling
> pointer stuff leaks into that API.

This point was about your first proposal to use the alignment. With cosidering
only the alignment we can't handle the case where `Box::from_raw` is called with
a random pointer for a ZST, which *technically* isn't illegal. We can define it
as illegal, but I'd consider it to be more robust, if we don't oops in case.

But as you say checking the size instead of the alignment does not have this
problem.

> 
> > [1] https://doc.rust-lang.org/std/ptr/index.html
> > 
> >>
> >> Also if we use the size of the old layout instead of comparing alignment
> >> with the address of the pointer, then we avoid this issue.
> > 
> > That is just another problem when passing the old `Layout` (or maybe just the
> > old size as usize). Neither do we need the old size, nor do we honor it with any
> > kernel allocator. This has the following implications:
> > 
> > (1) We never see any error if the old size that is passed is garbage (unless
> >     it's non-zero, when it should be zero and vice versa), which is bad.
> 
> We could add debug support for that though?

And add even more complexity just to avoid a simple `if !zero` check before
calling `free`? I don't like that.

Just to clarify, I'm not against passing the old layout in general. But I really
don't want to pass something in that is not required *and* not honored by a
single kernel allocator.

IMO, the only other valid reason to accept unneeded arguments would be if we
could use the `Allocator` interface from stdlib.

> 
> > (2) We'd need `free` to be `fn free(ptr: NonNull<u8>, size: usize)`, which is
> >     confusing, because it implies that an actual free relies on this size for
> >     freeing the memory.
> 
> I don't think that it is confusing to ask for the old layout.

It is always confusing if a function asks for information that it doesn't need
and doesn't consider, because asking for it in the first place creates the
impression that it is indeed needed and considered.

> 
> > If we want to avoid (1) and (2), we'd need to make it
> > `fn free(ptr: NonNull<u8>, zero: bool)` instead, but then also the caller can
> > just check this boolean and conditionally call `free`.
> 
> Yeah having `free` with a `zero: bool` sounds like a bad idea.
> 
> > I don't really see why it's better to let `free` do the `if !zero` check.
> 
> You did not reply to my last argument:
> 
> >> I think it's better to just let `Box` and `Vec` figure out if calling `free` is
> >> the right thing to do. The code for that is simple and obvious, i.e. check if
> >> `T` is a ZST.
> >
> > I don't think that it is as simple as you make it out to be. To me this
> > is functionality that we can move into one place and never have to think
> > about again.
> > Also if we at some point decide to add some sort of debugging allocator
> > (am I right in assuming that such a thing already exists for C?) then we

The C side allocators have quite a lot of debugging capabilities, but there is
no separate one.

> > might want to tag on extra data in the allocation, in that case it would
> > be very useful if the allocator also saw zero-sized allocations, since
> > we should check all allocations.

What would such a debugging allocator do on the Rust side?

The allocators we have are just simple wrappers around the real kernel
allocators from the C side.

I don't really see the need for some sort of debugging allocator.

On 08.08.24 10:55, Benno Lossin wrote:
> On 08.08.24 01:05, Danilo Krummrich wrote:
>> It's also not that we safe code with that. `Box`, `Vec`, any other user, still
>> would have to create the `Layout` before they call `A::free`.
> 
> But for `Box` it would just be `Layout::<T>::new()` and `Vec` needs
> `Layout::<T>::new().repeat(self.cap)`.
> 
> Though for `repeat` we need the `alloc_layout_extra` feature, which is
> an argument against doing this.

Oops, I overlooked the `Layout::array` function, so this is not a
problem. Instead it just is `Layout::<T>::array(self.cap).unwrap()`.

---
Cheers,
Benno