// SPDX-License-Identifier: GPL-2.012//! Implementation of [`Box`].34#[allow(unused_imports)] // Used in doc comments.5use super::allocator::{KVmalloc, Kmalloc, Vmalloc, VmallocPageIter};6use super::{AllocError, Allocator, Flags, NumaNode};7use core::alloc::Layout;8use core::borrow::{Borrow, BorrowMut};9use core::marker::PhantomData;10use core::mem::ManuallyDrop;11use core::mem::MaybeUninit;12use core::ops::{Deref, DerefMut};13use core::pin::Pin;14use core::ptr::NonNull;15use core::result::Result;1617use crate::ffi::c_void;18use crate::fmt;19use crate::init::InPlaceInit;20use crate::page::AsPageIter;21use crate::types::ForeignOwnable;22use pin_init::{InPlaceWrite, Init, PinInit, ZeroableOption};2324/// The kernel's [`Box`] type -- a heap allocation for a single value of type `T`.25///26/// This is the kernel's version of the Rust stdlib's `Box`. There are several differences,27/// for example no `noalias` attribute is emitted and partially moving out of a `Box` is not28/// supported. There are also several API differences, e.g. `Box` always requires an [`Allocator`]29/// implementation to be passed as generic, page [`Flags`] when allocating memory and all functions30/// that may allocate memory are fallible.31///32/// `Box` works with any of the kernel's allocators, e.g. [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`].33/// There are aliases for `Box` with these allocators ([`KBox`], [`VBox`], [`KVBox`]).34///35/// When dropping a [`Box`], the value is also dropped and the heap memory is automatically freed.36///37/// # Examples38///39/// ```40/// let b = KBox::<u64>::new(24_u64, GFP_KERNEL)?;41///42/// assert_eq!(*b, 24_u64);43/// # Ok::<(), Error>(())44/// ```45///46/// ```47/// # use kernel::bindings;48/// const SIZE: usize = bindings::KMALLOC_MAX_SIZE as usize + 1;49/// struct Huge([u8; SIZE]);50///51/// assert!(KBox::<Huge>::new_uninit(GFP_KERNEL | __GFP_NOWARN).is_err());52/// ```53///54/// ```55/// # use kernel::bindings;56/// const SIZE: usize = bindings::KMALLOC_MAX_SIZE as usize + 1;57/// struct Huge([u8; SIZE]);58///59/// assert!(KVBox::<Huge>::new_uninit(GFP_KERNEL).is_ok());60/// ```61///62/// [`Box`]es can also be used to store trait objects by coercing their type:63///64/// ```65/// trait FooTrait {}66///67/// struct FooStruct;68/// impl FooTrait for FooStruct {}69///70/// let _ = KBox::new(FooStruct, GFP_KERNEL)? as KBox<dyn FooTrait>;71/// # Ok::<(), Error>(())72/// ```73///74/// # Invariants75///76/// `self.0` is always properly aligned and either points to memory allocated with `A` or, for77/// zero-sized types, is a dangling, well aligned pointer.78#[repr(transparent)]79#[cfg_attr(CONFIG_RUSTC_HAS_COERCE_POINTEE, derive(core::marker::CoercePointee))]80pub struct Box<#[cfg_attr(CONFIG_RUSTC_HAS_COERCE_POINTEE, pointee)] T: ?Sized, A: Allocator>(81NonNull<T>,82PhantomData<A>,83);8485// This is to allow coercion from `Box<T, A>` to `Box<U, A>` if `T` can be converted to the86// dynamically-sized type (DST) `U`.87#[cfg(not(CONFIG_RUSTC_HAS_COERCE_POINTEE))]88impl<T, U, A> core::ops::CoerceUnsized<Box<U, A>> for Box<T, A>89where90T: ?Sized + core::marker::Unsize<U>,91U: ?Sized,92A: Allocator,93{94}9596// This is to allow `Box<U, A>` to be dispatched on when `Box<T, A>` can be coerced into `Box<U,97// A>`.98#[cfg(not(CONFIG_RUSTC_HAS_COERCE_POINTEE))]99impl<T, U, A> core::ops::DispatchFromDyn<Box<U, A>> for Box<T, A>100where101T: ?Sized + core::marker::Unsize<U>,102U: ?Sized,103A: Allocator,104{105}106107/// Type alias for [`Box`] with a [`Kmalloc`] allocator.108///109/// # Examples110///111/// ```112/// let b = KBox::new(24_u64, GFP_KERNEL)?;113///114/// assert_eq!(*b, 24_u64);115/// # Ok::<(), Error>(())116/// ```117pub type KBox<T> = Box<T, super::allocator::Kmalloc>;118119/// Type alias for [`Box`] with a [`Vmalloc`] allocator.120///121/// # Examples122///123/// ```124/// let b = VBox::new(24_u64, GFP_KERNEL)?;125///126/// assert_eq!(*b, 24_u64);127/// # Ok::<(), Error>(())128/// ```129pub type VBox<T> = Box<T, super::allocator::Vmalloc>;130131/// Type alias for [`Box`] with a [`KVmalloc`] allocator.132///133/// # Examples134///135/// ```136/// let b = KVBox::new(24_u64, GFP_KERNEL)?;137///138/// assert_eq!(*b, 24_u64);139/// # Ok::<(), Error>(())140/// ```141pub type KVBox<T> = Box<T, super::allocator::KVmalloc>;142143// SAFETY: All zeros is equivalent to `None` (option layout optimization guarantee:144// <https://doc.rust-lang.org/stable/std/option/index.html#representation>).145unsafe impl<T, A: Allocator> ZeroableOption for Box<T, A> {}146147// SAFETY: `Box` is `Send` if `T` is `Send` because the `Box` owns a `T`.148unsafe impl<T, A> Send for Box<T, A>149where150T: Send + ?Sized,151A: Allocator,152{153}154155// SAFETY: `Box` is `Sync` if `T` is `Sync` because the `Box` owns a `T`.156unsafe impl<T, A> Sync for Box<T, A>157where158T: Sync + ?Sized,159A: Allocator,160{161}162163impl<T, A> Box<T, A>164where165T: ?Sized,166A: Allocator,167{168/// Creates a new `Box<T, A>` from a raw pointer.169///170/// # Safety171///172/// For non-ZSTs, `raw` must point at an allocation allocated with `A` that is sufficiently173/// aligned for and holds a valid `T`. The caller passes ownership of the allocation to the174/// `Box`.175///176/// For ZSTs, `raw` must be a dangling, well aligned pointer.177#[inline]178pub const unsafe fn from_raw(raw: *mut T) -> Self {179// INVARIANT: Validity of `raw` is guaranteed by the safety preconditions of this function.180// SAFETY: By the safety preconditions of this function, `raw` is not a NULL pointer.181Self(unsafe { NonNull::new_unchecked(raw) }, PhantomData)182}183184/// Consumes the `Box<T, A>` and returns a raw pointer.185///186/// This will not run the destructor of `T` and for non-ZSTs the allocation will stay alive187/// indefinitely. Use [`Box::from_raw`] to recover the [`Box`], drop the value and free the188/// allocation, if any.189///190/// # Examples191///192/// ```193/// let x = KBox::new(24, GFP_KERNEL)?;194/// let ptr = KBox::into_raw(x);195/// // SAFETY: `ptr` comes from a previous call to `KBox::into_raw`.196/// let x = unsafe { KBox::from_raw(ptr) };197///198/// assert_eq!(*x, 24);199/// # Ok::<(), Error>(())200/// ```201#[inline]202pub fn into_raw(b: Self) -> *mut T {203ManuallyDrop::new(b).0.as_ptr()204}205206/// Consumes and leaks the `Box<T, A>` and returns a mutable reference.207///208/// See [`Box::into_raw`] for more details.209#[inline]210pub fn leak<'a>(b: Self) -> &'a mut T {211// SAFETY: `Box::into_raw` always returns a properly aligned and dereferenceable pointer212// which points to an initialized instance of `T`.213unsafe { &mut *Box::into_raw(b) }214}215}216217impl<T, A> Box<MaybeUninit<T>, A>218where219A: Allocator,220{221/// Converts a `Box<MaybeUninit<T>, A>` to a `Box<T, A>`.222///223/// It is undefined behavior to call this function while the value inside of `b` is not yet224/// fully initialized.225///226/// # Safety227///228/// Callers must ensure that the value inside of `b` is in an initialized state.229pub unsafe fn assume_init(self) -> Box<T, A> {230let raw = Self::into_raw(self);231232// SAFETY: `raw` comes from a previous call to `Box::into_raw`. By the safety requirements233// of this function, the value inside the `Box` is in an initialized state. Hence, it is234// safe to reconstruct the `Box` as `Box<T, A>`.235unsafe { Box::from_raw(raw.cast()) }236}237238/// Writes the value and converts to `Box<T, A>`.239pub fn write(mut self, value: T) -> Box<T, A> {240(*self).write(value);241242// SAFETY: We've just initialized `b`'s value.243unsafe { self.assume_init() }244}245}246247impl<T, A> Box<T, A>248where249A: Allocator,250{251/// Creates a new `Box<T, A>` and initializes its contents with `x`.252///253/// New memory is allocated with `A`. The allocation may fail, in which case an error is254/// returned. For ZSTs no memory is allocated.255pub fn new(x: T, flags: Flags) -> Result<Self, AllocError> {256let b = Self::new_uninit(flags)?;257Ok(Box::write(b, x))258}259260/// Creates a new `Box<T, A>` with uninitialized contents.261///262/// New memory is allocated with `A`. The allocation may fail, in which case an error is263/// returned. For ZSTs no memory is allocated.264///265/// # Examples266///267/// ```268/// let b = KBox::<u64>::new_uninit(GFP_KERNEL)?;269/// let b = KBox::write(b, 24);270///271/// assert_eq!(*b, 24_u64);272/// # Ok::<(), Error>(())273/// ```274pub fn new_uninit(flags: Flags) -> Result<Box<MaybeUninit<T>, A>, AllocError> {275let layout = Layout::new::<MaybeUninit<T>>();276let ptr = A::alloc(layout, flags, NumaNode::NO_NODE)?;277278// INVARIANT: `ptr` is either a dangling pointer or points to memory allocated with `A`,279// which is sufficient in size and alignment for storing a `T`.280Ok(Box(ptr.cast(), PhantomData))281}282283/// Constructs a new `Pin<Box<T, A>>`. If `T` does not implement [`Unpin`], then `x` will be284/// pinned in memory and can't be moved.285#[inline]286pub fn pin(x: T, flags: Flags) -> Result<Pin<Box<T, A>>, AllocError>287where288A: 'static,289{290Ok(Self::new(x, flags)?.into())291}292293/// Construct a pinned slice of elements `Pin<Box<[T], A>>`.294///295/// This is a convenient means for creation of e.g. slices of structrures containing spinlocks296/// or mutexes.297///298/// # Examples299///300/// ```301/// use kernel::sync::{new_spinlock, SpinLock};302///303/// struct Inner {304/// a: u32,305/// b: u32,306/// }307///308/// #[pin_data]309/// struct Example {310/// c: u32,311/// #[pin]312/// d: SpinLock<Inner>,313/// }314///315/// impl Example {316/// fn new() -> impl PinInit<Self, Error> {317/// try_pin_init!(Self {318/// c: 10,319/// d <- new_spinlock!(Inner { a: 20, b: 30 }),320/// })321/// }322/// }323///324/// // Allocate a boxed slice of 10 `Example`s.325/// let s = KBox::pin_slice(326/// | _i | Example::new(),327/// 10,328/// GFP_KERNEL329/// )?;330///331/// assert_eq!(s[5].c, 10);332/// assert_eq!(s[3].d.lock().a, 20);333/// # Ok::<(), Error>(())334/// ```335pub fn pin_slice<Func, Item, E>(336mut init: Func,337len: usize,338flags: Flags,339) -> Result<Pin<Box<[T], A>>, E>340where341Func: FnMut(usize) -> Item,342Item: PinInit<T, E>,343E: From<AllocError>,344{345let mut buffer = super::Vec::<T, A>::with_capacity(len, flags)?;346for i in 0..len {347let ptr = buffer.spare_capacity_mut().as_mut_ptr().cast();348// SAFETY:349// - `ptr` is a valid pointer to uninitialized memory.350// - `ptr` is not used if an error is returned.351// - `ptr` won't be moved until it is dropped, i.e. it is pinned.352unsafe { init(i).__pinned_init(ptr)? };353354// SAFETY:355// - `i + 1 <= len`, hence we don't exceed the capacity, due to the call to356// `with_capacity()` above.357// - The new value at index buffer.len() + 1 is the only element being added here, and358// it has been initialized above by `init(i).__pinned_init(ptr)`.359unsafe { buffer.inc_len(1) };360}361362let (ptr, _, _) = buffer.into_raw_parts();363let slice = core::ptr::slice_from_raw_parts_mut(ptr, len);364365// SAFETY: `slice` points to an allocation allocated with `A` (`buffer`) and holds a valid366// `[T]`.367Ok(Pin::from(unsafe { Box::from_raw(slice) }))368}369370/// Convert a [`Box<T,A>`] to a [`Pin<Box<T,A>>`]. If `T` does not implement371/// [`Unpin`], then `x` will be pinned in memory and can't be moved.372pub fn into_pin(this: Self) -> Pin<Self> {373this.into()374}375376/// Forgets the contents (does not run the destructor), but keeps the allocation.377fn forget_contents(this: Self) -> Box<MaybeUninit<T>, A> {378let ptr = Self::into_raw(this);379380// SAFETY: `ptr` is valid, because it came from `Box::into_raw`.381unsafe { Box::from_raw(ptr.cast()) }382}383384/// Drops the contents, but keeps the allocation.385///386/// # Examples387///388/// ```389/// let value = KBox::new([0; 32], GFP_KERNEL)?;390/// assert_eq!(*value, [0; 32]);391/// let value = KBox::drop_contents(value);392/// // Now we can re-use `value`:393/// let value = KBox::write(value, [1; 32]);394/// assert_eq!(*value, [1; 32]);395/// # Ok::<(), Error>(())396/// ```397pub fn drop_contents(this: Self) -> Box<MaybeUninit<T>, A> {398let ptr = this.0.as_ptr();399400// SAFETY: `ptr` is valid, because it came from `this`. After this call we never access the401// value stored in `this` again.402unsafe { core::ptr::drop_in_place(ptr) };403404Self::forget_contents(this)405}406407/// Moves the `Box`'s value out of the `Box` and consumes the `Box`.408pub fn into_inner(b: Self) -> T {409// SAFETY: By the type invariant `&*b` is valid for `read`.410let value = unsafe { core::ptr::read(&*b) };411let _ = Self::forget_contents(b);412value413}414}415416impl<T, A> From<Box<T, A>> for Pin<Box<T, A>>417where418T: ?Sized,419A: Allocator,420{421/// Converts a `Box<T, A>` into a `Pin<Box<T, A>>`. If `T` does not implement [`Unpin`], then422/// `*b` will be pinned in memory and can't be moved.423///424/// This moves `b` into `Pin` without moving `*b` or allocating and copying any memory.425fn from(b: Box<T, A>) -> Self {426// SAFETY: The value wrapped inside a `Pin<Box<T, A>>` cannot be moved or replaced as long427// as `T` does not implement `Unpin`.428unsafe { Pin::new_unchecked(b) }429}430}431432impl<T, A> InPlaceWrite<T> for Box<MaybeUninit<T>, A>433where434A: Allocator + 'static,435{436type Initialized = Box<T, A>;437438fn write_init<E>(mut self, init: impl Init<T, E>) -> Result<Self::Initialized, E> {439let slot = self.as_mut_ptr();440// SAFETY: When init errors/panics, slot will get deallocated but not dropped,441// slot is valid.442unsafe { init.__init(slot)? };443// SAFETY: All fields have been initialized.444Ok(unsafe { Box::assume_init(self) })445}446447fn write_pin_init<E>(mut self, init: impl PinInit<T, E>) -> Result<Pin<Self::Initialized>, E> {448let slot = self.as_mut_ptr();449// SAFETY: When init errors/panics, slot will get deallocated but not dropped,450// slot is valid and will not be moved, because we pin it later.451unsafe { init.__pinned_init(slot)? };452// SAFETY: All fields have been initialized.453Ok(unsafe { Box::assume_init(self) }.into())454}455}456457impl<T, A> InPlaceInit<T> for Box<T, A>458where459A: Allocator + 'static,460{461type PinnedSelf = Pin<Self>;462463#[inline]464fn try_pin_init<E>(init: impl PinInit<T, E>, flags: Flags) -> Result<Pin<Self>, E>465where466E: From<AllocError>,467{468Box::<_, A>::new_uninit(flags)?.write_pin_init(init)469}470471#[inline]472fn try_init<E>(init: impl Init<T, E>, flags: Flags) -> Result<Self, E>473where474E: From<AllocError>,475{476Box::<_, A>::new_uninit(flags)?.write_init(init)477}478}479480// SAFETY: The pointer returned by `into_foreign` comes from a well aligned481// pointer to `T` allocated by `A`.482unsafe impl<T: 'static, A> ForeignOwnable for Box<T, A>483where484A: Allocator,485{486const FOREIGN_ALIGN: usize = if core::mem::align_of::<T>() < A::MIN_ALIGN {487A::MIN_ALIGN488} else {489core::mem::align_of::<T>()490};491492type Borrowed<'a> = &'a T;493type BorrowedMut<'a> = &'a mut T;494495fn into_foreign(self) -> *mut c_void {496Box::into_raw(self).cast()497}498499unsafe fn from_foreign(ptr: *mut c_void) -> Self {500// SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous501// call to `Self::into_foreign`.502unsafe { Box::from_raw(ptr.cast()) }503}504505unsafe fn borrow<'a>(ptr: *mut c_void) -> &'a T {506// SAFETY: The safety requirements of this method ensure that the object remains alive and507// immutable for the duration of 'a.508unsafe { &*ptr.cast() }509}510511unsafe fn borrow_mut<'a>(ptr: *mut c_void) -> &'a mut T {512let ptr = ptr.cast();513// SAFETY: The safety requirements of this method ensure that the pointer is valid and that514// nothing else will access the value for the duration of 'a.515unsafe { &mut *ptr }516}517}518519// SAFETY: The pointer returned by `into_foreign` comes from a well aligned520// pointer to `T` allocated by `A`.521unsafe impl<T: 'static, A> ForeignOwnable for Pin<Box<T, A>>522where523A: Allocator,524{525const FOREIGN_ALIGN: usize = <Box<T, A> as ForeignOwnable>::FOREIGN_ALIGN;526type Borrowed<'a> = Pin<&'a T>;527type BorrowedMut<'a> = Pin<&'a mut T>;528529fn into_foreign(self) -> *mut c_void {530// SAFETY: We are still treating the box as pinned.531Box::into_raw(unsafe { Pin::into_inner_unchecked(self) }).cast()532}533534unsafe fn from_foreign(ptr: *mut c_void) -> Self {535// SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous536// call to `Self::into_foreign`.537unsafe { Pin::new_unchecked(Box::from_raw(ptr.cast())) }538}539540unsafe fn borrow<'a>(ptr: *mut c_void) -> Pin<&'a T> {541// SAFETY: The safety requirements for this function ensure that the object is still alive,542// so it is safe to dereference the raw pointer.543// The safety requirements of `from_foreign` also ensure that the object remains alive for544// the lifetime of the returned value.545let r = unsafe { &*ptr.cast() };546547// SAFETY: This pointer originates from a `Pin<Box<T>>`.548unsafe { Pin::new_unchecked(r) }549}550551unsafe fn borrow_mut<'a>(ptr: *mut c_void) -> Pin<&'a mut T> {552let ptr = ptr.cast();553// SAFETY: The safety requirements for this function ensure that the object is still alive,554// so it is safe to dereference the raw pointer.555// The safety requirements of `from_foreign` also ensure that the object remains alive for556// the lifetime of the returned value.557let r = unsafe { &mut *ptr };558559// SAFETY: This pointer originates from a `Pin<Box<T>>`.560unsafe { Pin::new_unchecked(r) }561}562}563564impl<T, A> Deref for Box<T, A>565where566T: ?Sized,567A: Allocator,568{569type Target = T;570571fn deref(&self) -> &T {572// SAFETY: `self.0` is always properly aligned, dereferenceable and points to an initialized573// instance of `T`.574unsafe { self.0.as_ref() }575}576}577578impl<T, A> DerefMut for Box<T, A>579where580T: ?Sized,581A: Allocator,582{583fn deref_mut(&mut self) -> &mut T {584// SAFETY: `self.0` is always properly aligned, dereferenceable and points to an initialized585// instance of `T`.586unsafe { self.0.as_mut() }587}588}589590/// # Examples591///592/// ```593/// # use core::borrow::Borrow;594/// # use kernel::alloc::KBox;595/// struct Foo<B: Borrow<u32>>(B);596///597/// // Owned instance.598/// let owned = Foo(1);599///600/// // Owned instance using `KBox`.601/// let owned_kbox = Foo(KBox::new(1, GFP_KERNEL)?);602///603/// let i = 1;604/// // Borrowed from `i`.605/// let borrowed = Foo(&i);606/// # Ok::<(), Error>(())607/// ```608impl<T, A> Borrow<T> for Box<T, A>609where610T: ?Sized,611A: Allocator,612{613fn borrow(&self) -> &T {614self.deref()615}616}617618/// # Examples619///620/// ```621/// # use core::borrow::BorrowMut;622/// # use kernel::alloc::KBox;623/// struct Foo<B: BorrowMut<u32>>(B);624///625/// // Owned instance.626/// let owned = Foo(1);627///628/// // Owned instance using `KBox`.629/// let owned_kbox = Foo(KBox::new(1, GFP_KERNEL)?);630///631/// let mut i = 1;632/// // Borrowed from `i`.633/// let borrowed = Foo(&mut i);634/// # Ok::<(), Error>(())635/// ```636impl<T, A> BorrowMut<T> for Box<T, A>637where638T: ?Sized,639A: Allocator,640{641fn borrow_mut(&mut self) -> &mut T {642self.deref_mut()643}644}645646impl<T, A> fmt::Display for Box<T, A>647where648T: ?Sized + fmt::Display,649A: Allocator,650{651fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {652<T as fmt::Display>::fmt(&**self, f)653}654}655656impl<T, A> fmt::Debug for Box<T, A>657where658T: ?Sized + fmt::Debug,659A: Allocator,660{661fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {662<T as fmt::Debug>::fmt(&**self, f)663}664}665666impl<T, A> Drop for Box<T, A>667where668T: ?Sized,669A: Allocator,670{671fn drop(&mut self) {672let layout = Layout::for_value::<T>(self);673674// SAFETY: The pointer in `self.0` is guaranteed to be valid by the type invariant.675unsafe { core::ptr::drop_in_place::<T>(self.deref_mut()) };676677// SAFETY:678// - `self.0` was previously allocated with `A`.679// - `layout` is equal to the `Layout´ `self.0` was allocated with.680unsafe { A::free(self.0.cast(), layout) };681}682}683684/// # Examples685///686/// ```687/// # use kernel::prelude::*;688/// use kernel::alloc::allocator::VmallocPageIter;689/// use kernel::page::{AsPageIter, PAGE_SIZE};690///691/// let mut vbox = VBox::new((), GFP_KERNEL)?;692///693/// assert!(vbox.page_iter().next().is_none());694///695/// let mut vbox = VBox::<[u8; PAGE_SIZE]>::new_uninit(GFP_KERNEL)?;696///697/// let page = vbox.page_iter().next().expect("At least one page should be available.\n");698///699/// // SAFETY: There is no concurrent read or write to the same page.700/// unsafe { page.fill_zero_raw(0, PAGE_SIZE)? };701/// # Ok::<(), Error>(())702/// ```703impl<T> AsPageIter for VBox<T> {704type Iter<'a>705= VmallocPageIter<'a>706where707T: 'a;708709fn page_iter(&mut self) -> Self::Iter<'_> {710let ptr = self.0.cast();711let size = core::mem::size_of::<T>();712713// SAFETY:714// - `ptr` is a valid pointer to the beginning of a `Vmalloc` allocation.715// - `ptr` is guaranteed to be valid for the lifetime of `'a`.716// - `size` is the size of the `Vmalloc` allocation `ptr` points to.717unsafe { VmallocPageIter::new(ptr, size) }718}719}720721722