| Message ID | 20240816001216.26575-23-dakr@kernel.org (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Generic `Allocator` support for Rust | expand |
On 16.08.24 02:11, Danilo Krummrich wrote: > So far the kernel's `Box` and `Vec` types can't be used by userspace > test cases, since all users of those types (e.g. `CString`) use kernel > allocators for instantiation. > > In order to allow userspace test cases to make use of such types as > well, implement the `Cmalloc` allocator within the allocator_test module > and type alias all kernel allocators to `Cmalloc`. The `Cmalloc` > allocator uses libc's realloc() function as allocator backend. > > Signed-off-by: Danilo Krummrich <dakr@kernel.org> > --- > rust/kernel/alloc/allocator_test.rs | 178 ++++++++++++++++++++++++++-- > 1 file changed, 171 insertions(+), 7 deletions(-) > > diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs > index 1b2642c547ec..7fff308d02dc 100644 > --- a/rust/kernel/alloc/allocator_test.rs > +++ b/rust/kernel/alloc/allocator_test.rs > @@ -2,20 +2,184 @@ > Could add a short paragraph as the module description why this module exists? Would probably be enough to paste the commit message. > #![allow(missing_docs)] > > -use super::{AllocError, Allocator, Flags}; > +use super::{flags::*, AllocError, Allocator, Flags}; > use core::alloc::Layout; > +use core::cmp; > +use core::mem; > +use core::ptr; > use core::ptr::NonNull; > > -pub struct Kmalloc; > +pub struct Cmalloc; > +pub type Kmalloc = Cmalloc; > pub type Vmalloc = Kmalloc; > pub type KVmalloc = Kmalloc; > > -unsafe impl Allocator for Kmalloc { > +extern "C" { > + #[link_name = "aligned_alloc"] > + fn libc_aligned_alloc(align: usize, size: usize) -> *mut core::ffi::c_void; > + > + #[link_name = "free"] > + fn libc_free(ptr: *mut core::ffi::c_void); > +} > + > +struct CmallocData { > + // The actual size as requested through `Cmalloc::alloc` or `Cmalloc::realloc`. > + size: usize, > + // The offset from the pointer returned to the caller of `Cmalloc::alloc` or `Cmalloc::realloc` > + // to the actual base address of the allocation. > + offset: usize, > +} > + > +impl Cmalloc { > + /// Adjust the size and alignment such that we can additionally store `CmallocData` right > + /// before the actual data described by `layout`. > + /// > + /// Example: > + /// > + /// For `CmallocData` assume an alignment of 8 and a size of 16. > + /// For `layout` assume and alignment of 16 and a size of 64. This looks like you want it rendered as bulletpoints (but it won't). > + /// > + /// 0 16 32 96 > + /// |----------------|----------------|------------------------------------------------| > + /// empty CmallocData data Can you put this inside of '```'? Then it will render nicely in markdown (don't forget to specify the type 'text') > + /// > + /// For this example the returned `Layout` has an alignment of 32 and a size of 96. > + fn layout_adjust(layout: Layout) -> Result<Layout, AllocError> { > + let layout = layout.pad_to_align(); > + > + // Ensure that `CmallocData` fits into half the alignment. Additionally, this guarantees > + // that advancing a pointer aligned to `align` by `align / 2` we still satisfy or exceed > + // the alignment requested through `layout`. > + let align = cmp::max( > + layout.align(), > + mem::size_of::<CmallocData>().next_power_of_two(), > + ) * 2; > + > + // Add the additional space required for `CmallocData`. > + let size = layout.size() + mem::size_of::<CmallocData>(); > + > + Ok(Layout::from_size_align(size, align) > + .map_err(|_| AllocError)? > + .pad_to_align()) > + } > + > + fn alloc_store_data(layout: Layout) -> Result<NonNull<u8>, AllocError> { > + let requested_size = layout.size(); > + > + let layout = Self::layout_adjust(layout)?; > + let min_align = layout.align() / 2; > + > + // SAFETY: Returns either NULL or a pointer to a memory allocation that satisfies or > + // exceeds the given size and alignment requirements. > + let raw_ptr = unsafe { libc_aligned_alloc(layout.align(), layout.size()) } as *mut u8; > + > + let priv_ptr = NonNull::new(raw_ptr).ok_or(AllocError)?; > + > + // SAFETY: Advance the pointer by `min_align`. The adjustments from `Self::layout_adjust` > + // ensure that after this operation the original size and alignment requirements are still > + // satisfied or exceeded. This SAFETY comment should address why it's OK to call `add`. You justify something different, namely why the allocation still satisfies the requirements of `layout`. That is something that this function should probably guarantee. > + let ptr = unsafe { priv_ptr.as_ptr().add(min_align) }; > + > + // SAFETY: `min_align` is greater than or equal to the size of `CmallocData`, hence we > + // don't exceed the allocation boundaries. > + let data_ptr: *mut CmallocData = unsafe { ptr.sub(mem::size_of::<CmallocData>()) }.cast(); > + > + let data = CmallocData { > + size: requested_size, > + offset: min_align, > + }; > + > + // SAFETY: `data_ptr` is properly aligned and within the allocation boundaries reserved for > + // `CmallocData`. > + unsafe { data_ptr.write(data) }; > + > + NonNull::new(ptr).ok_or(AllocError) > + } > + > + /// # Safety > + /// > + /// `ptr` must have been previously allocated with `Self::alloc_store_data`. You additionally need that you have shared access to the pointee. > + unsafe fn data<'a>(ptr: NonNull<u8>) -> &'a CmallocData { > + // SAFETY: `Self::alloc_store_data` stores the `CmallocData` right before the address > + // returned to callers of `Self::alloc_store_data`. > + let data_ptr: *mut CmallocData = > + unsafe { ptr.as_ptr().sub(mem::size_of::<CmallocData>()) }.cast(); > + > + // SAFETY: The `CmallocData` has been previously stored at this offset with > + // `Self::alloc_store_data`. > + unsafe { &*data_ptr } > + } > + > + /// # Safety > + /// > + /// This function must not be called more than once for the same allocation. > + /// > + /// `ptr` must have been previously allocated with `Self::alloc_store_data`. You additionally need that you have exclusive access to the pointee. > + unsafe fn free_read_data(ptr: NonNull<u8>) { > + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. > + let data = unsafe { Self::data(ptr) }; > + > + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. > + let priv_ptr = unsafe { ptr.as_ptr().sub(data.offset) }; > + > + // SAFETY: `priv_ptr` has previously been allocatored with this `Allocator`. > + unsafe { libc_free(priv_ptr.cast()) }; > + } > +} > + > +unsafe impl Allocator for Cmalloc { > + fn alloc(layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> { > + if layout.size() == 0 { > + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); > + } > + > + let ptr = Self::alloc_store_data(layout)?; > + > + if flags.contains(__GFP_ZERO) { > + // SAFETY: `Self::alloc_store_data` guarantees that `ptr` points to memory of at least > + // `layout.size()` bytes. > + unsafe { ptr.as_ptr().write_bytes(0, layout.size()) }; > + } This makes me wonder, what other flags should we handle for this allocator? > + > + Ok(NonNull::slice_from_raw_parts(ptr, layout.size())) > + } > + > unsafe fn realloc( > - _ptr: Option<NonNull<u8>>, > - _layout: Layout, > - _flags: Flags, > + ptr: Option<NonNull<u8>>, > + layout: Layout, > + flags: Flags, > ) -> Result<NonNull<[u8]>, AllocError> { > - panic!(); > + let src: NonNull<u8> = if let Some(src) = ptr { > + src.cast() Why the cast? > + } else { > + return Self::alloc(layout, flags); > + }; You should be able to write this instead: let Some(src) = ptr else { return Self::alloc(layout, flags); }; > + > + if layout.size() == 0 { > + // SAFETY: `src` has been created by `Self::alloc_store_data`. This is not true, consider: let ptr = alloc(size = 0); free(ptr) Alloc will return a dangling pointer due to the first if statement and then this function will pass it to `free_read_data`, even though it wasn't created by `alloc_store_data`. This isn't forbidden by the `Allocator` trait function's safety requirements. > + unsafe { Self::free_read_data(src) }; > + > + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); > + } > + > + let dst = Self::alloc(layout, flags)?; > + > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > + let data = unsafe { Self::data(src) }; Same issue here, if the allocation passed in is zero size. I think you have no other choice than to allocate even for zero size requests... Otherwise how would you know that they are zero-sized. --- Cheers, Benno > + > + // SAFETY: `src` has previously been allocated with this `Allocator`; `dst` has just been > + // newly allocated. Copy up to the smaller of both sizes. > + unsafe { > + ptr::copy_nonoverlapping( > + src.as_ptr(), > + dst.as_ptr().cast(), > + cmp::min(layout.size(), data.size), > + ) > + }; > + > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > + unsafe { Self::free_read_data(src) }; > + > + Ok(dst) > } > } > -- > 2.46.0 >
On Thu, Aug 29, 2024 at 07:14:18PM +0000, Benno Lossin wrote: > On 16.08.24 02:11, Danilo Krummrich wrote: > > So far the kernel's `Box` and `Vec` types can't be used by userspace > > test cases, since all users of those types (e.g. `CString`) use kernel > > allocators for instantiation. > > > > In order to allow userspace test cases to make use of such types as > > well, implement the `Cmalloc` allocator within the allocator_test module > > and type alias all kernel allocators to `Cmalloc`. The `Cmalloc` > > allocator uses libc's realloc() function as allocator backend. > > > > Signed-off-by: Danilo Krummrich <dakr@kernel.org> > > --- > > rust/kernel/alloc/allocator_test.rs | 178 ++++++++++++++++++++++++++-- > > 1 file changed, 171 insertions(+), 7 deletions(-) > > > > diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs > > index 1b2642c547ec..7fff308d02dc 100644 > > --- a/rust/kernel/alloc/allocator_test.rs > > +++ b/rust/kernel/alloc/allocator_test.rs > > @@ -2,20 +2,184 @@ > > > > Could add a short paragraph as the module description why this module > exists? Would probably be enough to paste the commit message. Yes, sounds good. > > > #![allow(missing_docs)] > > > > -use super::{AllocError, Allocator, Flags}; > > +use super::{flags::*, AllocError, Allocator, Flags}; > > use core::alloc::Layout; > > +use core::cmp; > > +use core::mem; > > +use core::ptr; > > use core::ptr::NonNull; > > > > -pub struct Kmalloc; > > +pub struct Cmalloc; > > +pub type Kmalloc = Cmalloc; > > pub type Vmalloc = Kmalloc; > > pub type KVmalloc = Kmalloc; > > > > -unsafe impl Allocator for Kmalloc { > > +extern "C" { > > + #[link_name = "aligned_alloc"] > > + fn libc_aligned_alloc(align: usize, size: usize) -> *mut core::ffi::c_void; > > + > > + #[link_name = "free"] > > + fn libc_free(ptr: *mut core::ffi::c_void); > > +} > > + > > +struct CmallocData { > > + // The actual size as requested through `Cmalloc::alloc` or `Cmalloc::realloc`. > > + size: usize, > > + // The offset from the pointer returned to the caller of `Cmalloc::alloc` or `Cmalloc::realloc` > > + // to the actual base address of the allocation. > > + offset: usize, > > +} > > + > > +impl Cmalloc { > > + /// Adjust the size and alignment such that we can additionally store `CmallocData` right > > + /// before the actual data described by `layout`. > > + /// > > + /// Example: > > + /// > > + /// For `CmallocData` assume an alignment of 8 and a size of 16. > > + /// For `layout` assume and alignment of 16 and a size of 64. > > This looks like you want it rendered as bulletpoints (but it won't). Actually, that wasn't my intention, but I'm fine changing that. > > > + /// > > + /// 0 16 32 96 > > + /// |----------------|----------------|------------------------------------------------| > > + /// empty CmallocData data > > Can you put this inside of '```'? Then it will render nicely in markdown > (don't forget to specify the type 'text') Sure. > > > + /// > > + /// For this example the returned `Layout` has an alignment of 32 and a size of 96. > > + fn layout_adjust(layout: Layout) -> Result<Layout, AllocError> { > > + let layout = layout.pad_to_align(); > > + > > + // Ensure that `CmallocData` fits into half the alignment. Additionally, this guarantees > > + // that advancing a pointer aligned to `align` by `align / 2` we still satisfy or exceed > > + // the alignment requested through `layout`. > > + let align = cmp::max( > > + layout.align(), > > + mem::size_of::<CmallocData>().next_power_of_two(), > > + ) * 2; > > + > > + // Add the additional space required for `CmallocData`. > > + let size = layout.size() + mem::size_of::<CmallocData>(); > > + > > + Ok(Layout::from_size_align(size, align) > > + .map_err(|_| AllocError)? > > + .pad_to_align()) > > + } > > + > > + fn alloc_store_data(layout: Layout) -> Result<NonNull<u8>, AllocError> { > > + let requested_size = layout.size(); > > + > > + let layout = Self::layout_adjust(layout)?; > > + let min_align = layout.align() / 2; > > + > > + // SAFETY: Returns either NULL or a pointer to a memory allocation that satisfies or > > + // exceeds the given size and alignment requirements. > > + let raw_ptr = unsafe { libc_aligned_alloc(layout.align(), layout.size()) } as *mut u8; > > + > > + let priv_ptr = NonNull::new(raw_ptr).ok_or(AllocError)?; > > + > > + // SAFETY: Advance the pointer by `min_align`. The adjustments from `Self::layout_adjust` > > + // ensure that after this operation the original size and alignment requirements are still > > + // satisfied or exceeded. > > This SAFETY comment should address why it's OK to call `add`. You > justify something different, namely why the allocation still satisfies > the requirements of `layout`. That is something that this function > should probably guarantee. So, I guess you're arguing that instead I should say that, we're still within the bounds of the same allocated object and don't exceed `isize`? > > > + let ptr = unsafe { priv_ptr.as_ptr().add(min_align) }; > > + > > + // SAFETY: `min_align` is greater than or equal to the size of `CmallocData`, hence we > > + // don't exceed the allocation boundaries. > > + let data_ptr: *mut CmallocData = unsafe { ptr.sub(mem::size_of::<CmallocData>()) }.cast(); > > + > > + let data = CmallocData { > > + size: requested_size, > > + offset: min_align, > > + }; > > + > > + // SAFETY: `data_ptr` is properly aligned and within the allocation boundaries reserved for > > + // `CmallocData`. > > + unsafe { data_ptr.write(data) }; > > + > > + NonNull::new(ptr).ok_or(AllocError) > > + } > > + > > + /// # Safety > > + /// > > + /// `ptr` must have been previously allocated with `Self::alloc_store_data`. > > You additionally need that you have shared access to the pointee. > > > + unsafe fn data<'a>(ptr: NonNull<u8>) -> &'a CmallocData { > > + // SAFETY: `Self::alloc_store_data` stores the `CmallocData` right before the address > > + // returned to callers of `Self::alloc_store_data`. > > + let data_ptr: *mut CmallocData = > > + unsafe { ptr.as_ptr().sub(mem::size_of::<CmallocData>()) }.cast(); > > + > > + // SAFETY: The `CmallocData` has been previously stored at this offset with > > + // `Self::alloc_store_data`. > > + unsafe { &*data_ptr } > > + } > > + > > + /// # Safety > > + /// > > + /// This function must not be called more than once for the same allocation. > > + /// > > + /// `ptr` must have been previously allocated with `Self::alloc_store_data`. > > You additionally need that you have exclusive access to the pointee. > > > + unsafe fn free_read_data(ptr: NonNull<u8>) { > > + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. > > + let data = unsafe { Self::data(ptr) }; > > + > > + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. > > + let priv_ptr = unsafe { ptr.as_ptr().sub(data.offset) }; > > + > > + // SAFETY: `priv_ptr` has previously been allocatored with this `Allocator`. > > + unsafe { libc_free(priv_ptr.cast()) }; > > + } > > +} > > + > > +unsafe impl Allocator for Cmalloc { > > + fn alloc(layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> { > > + if layout.size() == 0 { > > + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); > > + } > > + > > + let ptr = Self::alloc_store_data(layout)?; > > + > > + if flags.contains(__GFP_ZERO) { > > + // SAFETY: `Self::alloc_store_data` guarantees that `ptr` points to memory of at least > > + // `layout.size()` bytes. > > + unsafe { ptr.as_ptr().write_bytes(0, layout.size()) }; > > + } > > This makes me wonder, what other flags should we handle for this > allocator? I don't think there are any other flags that we can handle. The only other one that'd make sense is __GFP_NOFAIL, but we can't guarantee that. If any specific gfp flags are needed, I think it's simply not a candidate for a userspace test. If we really want to do something here, we could whitelist the flags we ignore, since they do not matter (such as __GFP_NOWARN) and panic() for everything else. But I don't think that's really needed. > > > + > > + Ok(NonNull::slice_from_raw_parts(ptr, layout.size())) > > + } > > + > > unsafe fn realloc( > > - _ptr: Option<NonNull<u8>>, > > - _layout: Layout, > > - _flags: Flags, > > + ptr: Option<NonNull<u8>>, > > + layout: Layout, > > + flags: Flags, > > ) -> Result<NonNull<[u8]>, AllocError> { > > - panic!(); > > + let src: NonNull<u8> = if let Some(src) = ptr { > > + src.cast() > > Why the cast? Probably a copy-paste mistake. > > > + } else { > > + return Self::alloc(layout, flags); > > + }; > > You should be able to write this instead: > > let Some(src) = ptr else { > return Self::alloc(layout, flags); > }; Yes, indeed. > > > + > > + if layout.size() == 0 { > > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > > This is not true, consider: > > let ptr = alloc(size = 0); > free(ptr) > > Alloc will return a dangling pointer due to the first if statement and > then this function will pass it to `free_read_data`, even though it > wasn't created by `alloc_store_data`. > This isn't forbidden by the `Allocator` trait function's safety > requirements. > > > + unsafe { Self::free_read_data(src) }; > > + > > + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); > > + } > > + > > + let dst = Self::alloc(layout, flags)?; > > + > > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > > + let data = unsafe { Self::data(src) }; > > Same issue here, if the allocation passed in is zero size. I think you > have no other choice than to allocate even for zero size requests... > Otherwise how would you know that they are zero-sized. Good catch - gonna fix it. > > --- > Cheers, > Benno > > > + > > + // SAFETY: `src` has previously been allocated with this `Allocator`; `dst` has just been > > + // newly allocated. Copy up to the smaller of both sizes. > > + unsafe { > > + ptr::copy_nonoverlapping( > > + src.as_ptr(), > > + dst.as_ptr().cast(), > > + cmp::min(layout.size(), data.size), > > + ) > > + }; > > + > > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > > + unsafe { Self::free_read_data(src) }; > > + > > + Ok(dst) > > } > > } > > -- > > 2.46.0 > > >
On 30.08.24 00:25, Danilo Krummrich wrote: > On Thu, Aug 29, 2024 at 07:14:18PM +0000, Benno Lossin wrote: >> On 16.08.24 02:11, Danilo Krummrich wrote: >>> +impl Cmalloc { >>> + /// Adjust the size and alignment such that we can additionally store `CmallocData` right >>> + /// before the actual data described by `layout`. >>> + /// >>> + /// Example: >>> + /// >>> + /// For `CmallocData` assume an alignment of 8 and a size of 16. >>> + /// For `layout` assume and alignment of 16 and a size of 64. >> >> This looks like you want it rendered as bulletpoints (but it won't). > > Actually, that wasn't my intention, but I'm fine changing that. I see, in that case not putting a newline there is also fine with me. But I think bulletpoints are probably easier to read. >>> + fn alloc_store_data(layout: Layout) -> Result<NonNull<u8>, AllocError> { >>> + let requested_size = layout.size(); >>> + >>> + let layout = Self::layout_adjust(layout)?; >>> + let min_align = layout.align() / 2; >>> + >>> + // SAFETY: Returns either NULL or a pointer to a memory allocation that satisfies or >>> + // exceeds the given size and alignment requirements. >>> + let raw_ptr = unsafe { libc_aligned_alloc(layout.align(), layout.size()) } as *mut u8; >>> + >>> + let priv_ptr = NonNull::new(raw_ptr).ok_or(AllocError)?; >>> + >>> + // SAFETY: Advance the pointer by `min_align`. The adjustments from `Self::layout_adjust` >>> + // ensure that after this operation the original size and alignment requirements are still >>> + // satisfied or exceeded. >> >> This SAFETY comment should address why it's OK to call `add`. You >> justify something different, namely why the allocation still satisfies >> the requirements of `layout`. That is something that this function >> should probably guarantee. > > So, I guess you're arguing that instead I should say that, we're still within > the bounds of the same allocated object and don't exceed `isize`? Yes. >>> + unsafe fn free_read_data(ptr: NonNull<u8>) { >>> + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. >>> + let data = unsafe { Self::data(ptr) }; >>> + >>> + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. >>> + let priv_ptr = unsafe { ptr.as_ptr().sub(data.offset) }; >>> + >>> + // SAFETY: `priv_ptr` has previously been allocatored with this `Allocator`. >>> + unsafe { libc_free(priv_ptr.cast()) }; >>> + } >>> +} >>> + >>> +unsafe impl Allocator for Cmalloc { >>> + fn alloc(layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> { >>> + if layout.size() == 0 { >>> + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); >>> + } >>> + >>> + let ptr = Self::alloc_store_data(layout)?; >>> + >>> + if flags.contains(__GFP_ZERO) { >>> + // SAFETY: `Self::alloc_store_data` guarantees that `ptr` points to memory of at least >>> + // `layout.size()` bytes. >>> + unsafe { ptr.as_ptr().write_bytes(0, layout.size()) }; >>> + } >> >> This makes me wonder, what other flags should we handle for this >> allocator? > > I don't think there are any other flags that we can handle. The only other one > that'd make sense is __GFP_NOFAIL, but we can't guarantee that. > > If any specific gfp flags are needed, I think it's simply not a candidate for a > userspace test. > > If we really want to do something here, we could whitelist the flags we ignore, > since they do not matter (such as __GFP_NOWARN) and panic() for everything else. > > But I don't think that's really needed. Makes sense, just wanted to check that this has been accounted for. --- Cheers, Benno
On Fri, Aug 30, 2024 at 12:25:27AM +0200, Danilo Krummrich wrote: > On Thu, Aug 29, 2024 at 07:14:18PM +0000, Benno Lossin wrote: > > On 16.08.24 02:11, Danilo Krummrich wrote: > > > > > + > > > + if layout.size() == 0 { > > > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > > > > This is not true, consider: > > > > let ptr = alloc(size = 0); > > free(ptr) > > > > Alloc will return a dangling pointer due to the first if statement and > > then this function will pass it to `free_read_data`, even though it > > wasn't created by `alloc_store_data`. > > This isn't forbidden by the `Allocator` trait function's safety > > requirements. > > > > > + unsafe { Self::free_read_data(src) }; > > > + > > > + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); > > > + } > > > + > > > + let dst = Self::alloc(layout, flags)?; > > > + > > > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > > > + let data = unsafe { Self::data(src) }; > > > > Same issue here, if the allocation passed in is zero size. I think you > > have no other choice than to allocate even for zero size requests... > > Otherwise how would you know that they are zero-sized. > > Good catch - gonna fix it. Almost got me. :) I think the code is fine, callers are not allowed to pass pointers to `realloc` and `free`, which haven't been allocated with the same corresponding allocator or are dangling. > > > > > --- > > Cheers, > > Benno > > > > > + > > > + // SAFETY: `src` has previously been allocated with this `Allocator`; `dst` has just been > > > + // newly allocated. Copy up to the smaller of both sizes. > > > + unsafe { > > > + ptr::copy_nonoverlapping( > > > + src.as_ptr(), > > > + dst.as_ptr().cast(), > > > + cmp::min(layout.size(), data.size), > > > + ) > > > + }; > > > + > > > + // SAFETY: `src` has been created by `Self::alloc_store_data`. > > > + unsafe { Self::free_read_data(src) }; > > > + > > > + Ok(dst) > > > } > > > } > > > -- > > > 2.46.0 > > > > >
On 11.09.24 14:31, Danilo Krummrich wrote: > On Fri, Aug 30, 2024 at 12:25:27AM +0200, Danilo Krummrich wrote: >> On Thu, Aug 29, 2024 at 07:14:18PM +0000, Benno Lossin wrote: >>> On 16.08.24 02:11, Danilo Krummrich wrote: >>>> + >>>> + if layout.size() == 0 { >>>> + // SAFETY: `src` has been created by `Self::alloc_store_data`. >>> >>> This is not true, consider: >>> >>> let ptr = alloc(size = 0); >>> free(ptr) >>> >>> Alloc will return a dangling pointer due to the first if statement and >>> then this function will pass it to `free_read_data`, even though it >>> wasn't created by `alloc_store_data`. >>> This isn't forbidden by the `Allocator` trait function's safety >>> requirements. >>> >>>> + unsafe { Self::free_read_data(src) }; >>>> + >>>> + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); >>>> + } >>>> + >>>> + let dst = Self::alloc(layout, flags)?; >>>> + >>>> + // SAFETY: `src` has been created by `Self::alloc_store_data`. >>>> + let data = unsafe { Self::data(src) }; >>> >>> Same issue here, if the allocation passed in is zero size. I think you >>> have no other choice than to allocate even for zero size requests... >>> Otherwise how would you know that they are zero-sized. >> >> Good catch - gonna fix it. > > Almost got me. :) I think the code is fine, callers are not allowed to pass > pointers to `realloc` and `free`, which haven't been allocated with the same > corresponding allocator or are dangling. But what about the example above (ie the `alloc(size = 0)` and then `free`)? I guess this all depends on how one interprets the term "existing, valid memory allocation". To me that describes anything an `Allocator` returns via `alloc` and `realloc`, including zero-sized allocations. But if you argue that those are not valid allocations from that allocator, then that is not properly documented in the safety requirements of `Allocator`. --- Cheers, Benno
On Wed, Sep 11, 2024 at 01:32:31PM +0000, Benno Lossin wrote: > On 11.09.24 14:31, Danilo Krummrich wrote: > > On Fri, Aug 30, 2024 at 12:25:27AM +0200, Danilo Krummrich wrote: > >> On Thu, Aug 29, 2024 at 07:14:18PM +0000, Benno Lossin wrote: > >>> On 16.08.24 02:11, Danilo Krummrich wrote: > >>>> + > >>>> + if layout.size() == 0 { > >>>> + // SAFETY: `src` has been created by `Self::alloc_store_data`. > >>> > >>> This is not true, consider: > >>> > >>> let ptr = alloc(size = 0); > >>> free(ptr) > >>> > >>> Alloc will return a dangling pointer due to the first if statement and > >>> then this function will pass it to `free_read_data`, even though it > >>> wasn't created by `alloc_store_data`. > >>> This isn't forbidden by the `Allocator` trait function's safety > >>> requirements. > >>> > >>>> + unsafe { Self::free_read_data(src) }; > >>>> + > >>>> + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); > >>>> + } > >>>> + > >>>> + let dst = Self::alloc(layout, flags)?; > >>>> + > >>>> + // SAFETY: `src` has been created by `Self::alloc_store_data`. > >>>> + let data = unsafe { Self::data(src) }; > >>> > >>> Same issue here, if the allocation passed in is zero size. I think you > >>> have no other choice than to allocate even for zero size requests... > >>> Otherwise how would you know that they are zero-sized. > >> > >> Good catch - gonna fix it. > > > > Almost got me. :) I think the code is fine, callers are not allowed to pass > > pointers to `realloc` and `free`, which haven't been allocated with the same > > corresponding allocator or are dangling. > > But what about the example above (ie the `alloc(size = 0)` and then > `free`)? This never has been valid for the `Allocator` trait. Look at `Kmalloc`, `Vmalloc` and `KVmalloc`, they don't allow this either. We've discussed this already in previous versions of this series, where for this purpose, you asked for `old_layout` for `free`. Such that `free` can check if the `size` was zero and therefore return without doing anything. > I guess this all depends on how one interprets the term > "existing, valid memory allocation". To me that describes anything an > `Allocator` returns via `alloc` and `realloc`, including zero-sized > allocations. I argue that the dangling pointer returned for `size == 0` does not point to any allocation in the sense of those allocators. It's just a dangling `[u8]` pointer. > But if you argue that those are not valid allocations from that > allocator, then that is not properly documented in the safety > requirements of `Allocator`. The safety requirements of `Allocator` where proposed by you and I thought they consider this aspect? `realloc` has: "If `ptr == Some(p)`, then `p` must point to an existing and valid memory allocation created by this allocator." `free` has: "`ptr` must point to an existing and valid memory allocation created by this `Allocator` and must not be a dangling pointer." We can add the part about the dangling pointer to `realloc` if you want. > > --- > Cheers, > Benno >
On 11.09.24 16:37, Danilo Krummrich wrote: > On Wed, Sep 11, 2024 at 01:32:31PM +0000, Benno Lossin wrote: >> On 11.09.24 14:31, Danilo Krummrich wrote: >>> On Fri, Aug 30, 2024 at 12:25:27AM +0200, Danilo Krummrich wrote: >>>> On Thu, Aug 29, 2024 at 07:14:18PM +0000, Benno Lossin wrote: >>>>> On 16.08.24 02:11, Danilo Krummrich wrote: >>>>>> + >>>>>> + if layout.size() == 0 { >>>>>> + // SAFETY: `src` has been created by `Self::alloc_store_data`. >>>>> >>>>> This is not true, consider: >>>>> >>>>> let ptr = alloc(size = 0); >>>>> free(ptr) >>>>> >>>>> Alloc will return a dangling pointer due to the first if statement and >>>>> then this function will pass it to `free_read_data`, even though it >>>>> wasn't created by `alloc_store_data`. >>>>> This isn't forbidden by the `Allocator` trait function's safety >>>>> requirements. >>>>> >>>>>> + unsafe { Self::free_read_data(src) }; >>>>>> + >>>>>> + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); >>>>>> + } >>>>>> + >>>>>> + let dst = Self::alloc(layout, flags)?; >>>>>> + >>>>>> + // SAFETY: `src` has been created by `Self::alloc_store_data`. >>>>>> + let data = unsafe { Self::data(src) }; >>>>> >>>>> Same issue here, if the allocation passed in is zero size. I think you >>>>> have no other choice than to allocate even for zero size requests... >>>>> Otherwise how would you know that they are zero-sized. >>>> >>>> Good catch - gonna fix it. >>> >>> Almost got me. :) I think the code is fine, callers are not allowed to pass >>> pointers to `realloc` and `free`, which haven't been allocated with the same >>> corresponding allocator or are dangling. >> >> But what about the example above (ie the `alloc(size = 0)` and then >> `free`)? > > This never has been valid for the `Allocator` trait. Look at `Kmalloc`, > `Vmalloc` and `KVmalloc`, they don't allow this either. That is true. > We've discussed this already in previous versions of this series, where for this > purpose, you asked for `old_layout` for `free`. Such that `free` can check if > the `size` was zero and therefore return without doing anything. Yes, but that was only about the old_layout parameter (at least that's what I thought). >> I guess this all depends on how one interprets the term >> "existing, valid memory allocation". To me that describes anything an >> `Allocator` returns via `alloc` and `realloc`, including zero-sized >> allocations. > > I argue that the dangling pointer returned for `size == 0` does not point to any > allocation in the sense of those allocators. It's just a dangling `[u8]` > pointer. Sure, but to me the concept of zero-sized allocations does exist. >> But if you argue that those are not valid allocations from that >> allocator, then that is not properly documented in the safety >> requirements of `Allocator`. > > The safety requirements of `Allocator` where proposed by you and I thought they > consider this aspect? No, they did not consider this aspect. I was under the impression, that we would still allow zero-sized allocations (in retrospect, this is stupid, since dangling pointers shouldn't be passed to `krealloc` etc.). > `realloc` has: > > "If `ptr == Some(p)`, then `p` must point to an existing and valid memory > allocation created by this allocator." > > `free` has: > > "`ptr` must point to an existing and valid memory allocation created by this > `Allocator` and must not be a dangling pointer." > > We can add the part about the dangling pointer to `realloc` if you want. So I think we should do the following: (1) Add a paragraph to the `Allocator` trait that explains that zero-sized allocations are not supported. (2) Add a check to `realloc` for zero-sized allocations + null pointer (ie a new allocation request) that prints a warning and returns an error (3) Instead of writing "existing and valid memory allocation created by this allocator", I think "valid non-zero-sized memory allocation created by this allocator" fits better. --- Cheers, Benno
diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs index 1b2642c547ec..7fff308d02dc 100644 --- a/rust/kernel/alloc/allocator_test.rs +++ b/rust/kernel/alloc/allocator_test.rs @@ -2,20 +2,184 @@ #![allow(missing_docs)] -use super::{AllocError, Allocator, Flags}; +use super::{flags::*, AllocError, Allocator, Flags}; use core::alloc::Layout; +use core::cmp; +use core::mem; +use core::ptr; use core::ptr::NonNull; -pub struct Kmalloc; +pub struct Cmalloc; +pub type Kmalloc = Cmalloc; pub type Vmalloc = Kmalloc; pub type KVmalloc = Kmalloc; -unsafe impl Allocator for Kmalloc { +extern "C" { + #[link_name = "aligned_alloc"] + fn libc_aligned_alloc(align: usize, size: usize) -> *mut core::ffi::c_void; + + #[link_name = "free"] + fn libc_free(ptr: *mut core::ffi::c_void); +} + +struct CmallocData { + // The actual size as requested through `Cmalloc::alloc` or `Cmalloc::realloc`. + size: usize, + // The offset from the pointer returned to the caller of `Cmalloc::alloc` or `Cmalloc::realloc` + // to the actual base address of the allocation. + offset: usize, +} + +impl Cmalloc { + /// Adjust the size and alignment such that we can additionally store `CmallocData` right + /// before the actual data described by `layout`. + /// + /// Example: + /// + /// For `CmallocData` assume an alignment of 8 and a size of 16. + /// For `layout` assume and alignment of 16 and a size of 64. + /// + /// 0 16 32 96 + /// |----------------|----------------|------------------------------------------------| + /// empty CmallocData data + /// + /// For this example the returned `Layout` has an alignment of 32 and a size of 96. + fn layout_adjust(layout: Layout) -> Result<Layout, AllocError> { + let layout = layout.pad_to_align(); + + // Ensure that `CmallocData` fits into half the alignment. Additionally, this guarantees + // that advancing a pointer aligned to `align` by `align / 2` we still satisfy or exceed + // the alignment requested through `layout`. + let align = cmp::max( + layout.align(), + mem::size_of::<CmallocData>().next_power_of_two(), + ) * 2; + + // Add the additional space required for `CmallocData`. + let size = layout.size() + mem::size_of::<CmallocData>(); + + Ok(Layout::from_size_align(size, align) + .map_err(|_| AllocError)? + .pad_to_align()) + } + + fn alloc_store_data(layout: Layout) -> Result<NonNull<u8>, AllocError> { + let requested_size = layout.size(); + + let layout = Self::layout_adjust(layout)?; + let min_align = layout.align() / 2; + + // SAFETY: Returns either NULL or a pointer to a memory allocation that satisfies or + // exceeds the given size and alignment requirements. + let raw_ptr = unsafe { libc_aligned_alloc(layout.align(), layout.size()) } as *mut u8; + + let priv_ptr = NonNull::new(raw_ptr).ok_or(AllocError)?; + + // SAFETY: Advance the pointer by `min_align`. The adjustments from `Self::layout_adjust` + // ensure that after this operation the original size and alignment requirements are still + // satisfied or exceeded. + let ptr = unsafe { priv_ptr.as_ptr().add(min_align) }; + + // SAFETY: `min_align` is greater than or equal to the size of `CmallocData`, hence we + // don't exceed the allocation boundaries. + let data_ptr: *mut CmallocData = unsafe { ptr.sub(mem::size_of::<CmallocData>()) }.cast(); + + let data = CmallocData { + size: requested_size, + offset: min_align, + }; + + // SAFETY: `data_ptr` is properly aligned and within the allocation boundaries reserved for + // `CmallocData`. + unsafe { data_ptr.write(data) }; + + NonNull::new(ptr).ok_or(AllocError) + } + + /// # Safety + /// + /// `ptr` must have been previously allocated with `Self::alloc_store_data`. + unsafe fn data<'a>(ptr: NonNull<u8>) -> &'a CmallocData { + // SAFETY: `Self::alloc_store_data` stores the `CmallocData` right before the address + // returned to callers of `Self::alloc_store_data`. + let data_ptr: *mut CmallocData = + unsafe { ptr.as_ptr().sub(mem::size_of::<CmallocData>()) }.cast(); + + // SAFETY: The `CmallocData` has been previously stored at this offset with + // `Self::alloc_store_data`. + unsafe { &*data_ptr } + } + + /// # Safety + /// + /// This function must not be called more than once for the same allocation. + /// + /// `ptr` must have been previously allocated with `Self::alloc_store_data`. + unsafe fn free_read_data(ptr: NonNull<u8>) { + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. + let data = unsafe { Self::data(ptr) }; + + // SAFETY: `ptr` has been created by `Self::alloc_store_data`. + let priv_ptr = unsafe { ptr.as_ptr().sub(data.offset) }; + + // SAFETY: `priv_ptr` has previously been allocatored with this `Allocator`. + unsafe { libc_free(priv_ptr.cast()) }; + } +} + +unsafe impl Allocator for Cmalloc { + fn alloc(layout: Layout, flags: Flags) -> Result<NonNull<[u8]>, AllocError> { + if layout.size() == 0 { + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); + } + + let ptr = Self::alloc_store_data(layout)?; + + if flags.contains(__GFP_ZERO) { + // SAFETY: `Self::alloc_store_data` guarantees that `ptr` points to memory of at least + // `layout.size()` bytes. + unsafe { ptr.as_ptr().write_bytes(0, layout.size()) }; + } + + Ok(NonNull::slice_from_raw_parts(ptr, layout.size())) + } + unsafe fn realloc( - _ptr: Option<NonNull<u8>>, - _layout: Layout, - _flags: Flags, + ptr: Option<NonNull<u8>>, + layout: Layout, + flags: Flags, ) -> Result<NonNull<[u8]>, AllocError> { - panic!(); + let src: NonNull<u8> = if let Some(src) = ptr { + src.cast() + } else { + return Self::alloc(layout, flags); + }; + + if layout.size() == 0 { + // SAFETY: `src` has been created by `Self::alloc_store_data`. + unsafe { Self::free_read_data(src) }; + + return Ok(NonNull::slice_from_raw_parts(NonNull::dangling(), 0)); + } + + let dst = Self::alloc(layout, flags)?; + + // SAFETY: `src` has been created by `Self::alloc_store_data`. + let data = unsafe { Self::data(src) }; + + // SAFETY: `src` has previously been allocated with this `Allocator`; `dst` has just been + // newly allocated. Copy up to the smaller of both sizes. + unsafe { + ptr::copy_nonoverlapping( + src.as_ptr(), + dst.as_ptr().cast(), + cmp::min(layout.size(), data.size), + ) + }; + + // SAFETY: `src` has been created by `Self::alloc_store_data`. + unsafe { Self::free_read_data(src) }; + + Ok(dst) } }
So far the kernel's `Box` and `Vec` types can't be used by userspace test cases, since all users of those types (e.g. `CString`) use kernel allocators for instantiation. In order to allow userspace test cases to make use of such types as well, implement the `Cmalloc` allocator within the allocator_test module and type alias all kernel allocators to `Cmalloc`. The `Cmalloc` allocator uses libc's realloc() function as allocator backend. Signed-off-by: Danilo Krummrich <dakr@kernel.org> --- rust/kernel/alloc/allocator_test.rs | 178 ++++++++++++++++++++++++++-- 1 file changed, 171 insertions(+), 7 deletions(-)