// SPDX-License-Identifier: GPL-2.0 //! Implementation of [`Vec`]. use super::{    allocator::{KVmalloc, Kmalloc, Vmalloc, VmallocPageIter},    layout::ArrayLayout,    AllocError, Allocator, Box, Flags, NumaNode,};use crate::{    fmt,    page::AsPageIter, //};use core::{    borrow::{Borrow, BorrowMut},    marker::PhantomData,    mem::{ManuallyDrop, MaybeUninit},    ops::Deref,    ops::DerefMut,    ops::Index,    ops::IndexMut,    ptr,    ptr::NonNull,    slice,    slice::SliceIndex,}; mod errors;pub use self::errors::{InsertError, PushError, RemoveError}; /// Create a [`KVec`] containing the arguments.////// New memory is allocated with `GFP_KERNEL`.////// # Examples////// ```/// let mut v = kernel::kvec![];/// v.push(1, GFP_KERNEL)?;/// assert_eq!(v, [1]);////// let mut v = kernel::kvec![1; 3]?;/// v.push(4, GFP_KERNEL)?;/// assert_eq!(v, [1, 1, 1, 4]);////// let mut v = kernel::kvec![1, 2, 3]?;/// v.push(4, GFP_KERNEL)?;/// assert_eq!(v, [1, 2, 3, 4]);////// # Ok::<(), Error>(())/// ```#[macro_export]macro_rules! kvec {    () => (        $crate::alloc::KVec::new()    );    ($elem:expr; $n:expr) => (        $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL)    );    ($($x:expr),+ $(,)?) => (        match $crate::alloc::KBox::new_uninit(GFP_KERNEL) {            Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))),            Err(e) => Err(e),        }    );} /// The kernel's [`Vec`] type.////// A contiguous growable array type with contents allocated with the kernel's allocators (e.g./// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec<T, A>`.////// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For/// the most common allocators the type aliases [`KVec`], [`VVec`] and [`KVVec`] exist.////// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.////// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the/// capacity of the vector (the number of elements that currently fit into the vector), its length/// (the number of elements that are currently stored in the vector) and the `Allocator` type used/// to allocate (and free) the backing buffer.////// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts/// and manually modified.////// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements/// are added to the vector.////// # Invariants////// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for///   zero-sized types, is a dangling, well aligned pointer.////// - `self.len` always represents the exact number of elements stored in the vector.////// - `self.layout` represents the absolute number of elements that can be stored within the vector///   without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the///   backing buffer to be larger than `layout`.////// - `self.len()` is always less than or equal to `self.capacity()`.////// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer///   was allocated with (and must be freed with).pub struct Vec<T, A: Allocator> {    ptr: NonNull<T>,    /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes.    ///    /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of    /// elements we can still store without reallocating.    layout: ArrayLayout<T>,    len: usize,    _p: PhantomData<A>,} /// Type alias for [`Vec`] with a [`Kmalloc`] allocator.////// # Examples////// ```/// let mut v = KVec::new();/// v.push(1, GFP_KERNEL)?;/// assert_eq!(&v, &[1]);////// # Ok::<(), Error>(())/// ```pub type KVec<T> = Vec<T, Kmalloc>; /// Type alias for [`Vec`] with a [`Vmalloc`] allocator.////// # Examples////// ```/// let mut v = VVec::new();/// v.push(1, GFP_KERNEL)?;/// assert_eq!(&v, &[1]);////// # Ok::<(), Error>(())/// ```pub type VVec<T> = Vec<T, Vmalloc>; /// Type alias for [`Vec`] with a [`KVmalloc`] allocator.////// # Examples////// ```/// let mut v = KVVec::new();/// v.push(1, GFP_KERNEL)?;/// assert_eq!(&v, &[1]);////// # Ok::<(), Error>(())/// ```pub type KVVec<T> = Vec<T, KVmalloc>; // SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements.unsafe impl<T, A> Send for Vec<T, A>where    T: Send,    A: Allocator,{} // SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements.unsafe impl<T, A> Sync for Vec<T, A>where    T: Sync,    A: Allocator,{} impl<T, A> Vec<T, A>where    A: Allocator,{    #[inline]    const fn is_zst() -> bool {        core::mem::size_of::<T>() == 0    }     /// Returns the number of elements that can be stored within the vector without allocating    /// additional memory.    pub const fn capacity(&self) -> usize {        if const { Self::is_zst() } {            usize::MAX        } else {            self.layout.len()        }    }     /// Returns the number of elements stored within the vector.    #[inline]    pub const fn len(&self) -> usize {        self.len    }     /// Increments `self.len` by `additional`.    ///    /// # Safety    ///    /// - `additional` must be less than or equal to `self.capacity - self.len`.    /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized.    #[inline]    pub const unsafe fn inc_len(&mut self, additional: usize) {        // Guaranteed by the type invariant to never underflow.        debug_assert!(additional <= self.capacity() - self.len());        // INVARIANT: By the safety requirements of this method this represents the exact number of        // elements stored within `self`.        self.len += additional;    }     /// Decreases `self.len` by `count`.    ///    /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's    /// responsibility to drop these elements if necessary.    ///    /// # Safety    ///    /// - `count` must be less than or equal to `self.len`.    unsafe fn dec_len(&mut self, count: usize) -> &mut [T] {        debug_assert!(count <= self.len());        // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count,        // self.len)`, hence the updated value of `set.len` represents the exact number of elements        // stored within `self`.        self.len -= count;        // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized        // elements of type `T`.        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) }    }     /// Returns a slice of the entire vector.    ///    /// # Examples    ///    /// ```    /// let mut v = KVec::new();    /// v.push(1, GFP_KERNEL)?;    /// v.push(2, GFP_KERNEL)?;    /// assert_eq!(v.as_slice(), &[1, 2]);    /// # Ok::<(), Error>(())    /// ```    #[inline]    pub fn as_slice(&self) -> &[T] {        self    }     /// Returns a mutable slice of the entire vector.    #[inline]    pub fn as_mut_slice(&mut self) -> &mut [T] {        self    }     /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a    /// dangling raw pointer.    #[inline]    pub fn as_mut_ptr(&mut self) -> *mut T {        self.ptr.as_ptr()    }     /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw    /// pointer.    #[inline]    pub const fn as_ptr(&self) -> *const T {        self.ptr.as_ptr()    }     /// Returns `true` if the vector contains no elements, `false` otherwise.    ///    /// # Examples    ///    /// ```    /// let mut v = KVec::new();    /// assert!(v.is_empty());    ///    /// v.push(1, GFP_KERNEL);    /// assert!(!v.is_empty());    /// ```    #[inline]    pub const fn is_empty(&self) -> bool {        self.len() == 0    }     /// Creates a new, empty `Vec<T, A>`.    ///    /// This method does not allocate by itself.    #[inline]    pub const fn new() -> Self {        // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet,        // - `ptr` is a properly aligned dangling pointer for type `T`,        // - `layout` is an empty `ArrayLayout` (zero capacity)        // - `len` is zero, since no elements can be or have been stored,        // - `A` is always valid.        Self {            ptr: NonNull::dangling(),            layout: ArrayLayout::empty(),            len: 0,            _p: PhantomData::<A>,        }    }     /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector.    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {        // SAFETY:        // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the        //   resulting pointer is guaranteed to be part of the same allocated object.        // - `self.len` can not overflow `isize`.        let ptr = unsafe { self.as_mut_ptr().add(self.len) }.cast::<MaybeUninit<T>>();         // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated        // and valid, but uninitialized.        unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) }    }     /// Appends an element to the back of the [`Vec`] instance.    ///    /// # Examples    ///    /// ```    /// let mut v = KVec::new();    /// v.push(1, GFP_KERNEL)?;    /// assert_eq!(&v, &[1]);    ///    /// v.push(2, GFP_KERNEL)?;    /// assert_eq!(&v, &[1, 2]);    /// # Ok::<(), Error>(())    /// ```    pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {        self.reserve(1, flags)?;        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater        // than the length.        unsafe { self.push_within_capacity_unchecked(v) };        Ok(())    }     /// Appends an element to the back of the [`Vec`] instance without reallocating.    ///    /// Fails if the vector does not have capacity for the new element.    ///    /// # Examples    ///    /// ```    /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;    /// for i in 0..10 {    ///     v.push_within_capacity(i)?;    /// }    ///    /// assert!(v.push_within_capacity(10).is_err());    /// # Ok::<(), Error>(())    /// ```    pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> {        if self.len() < self.capacity() {            // SAFETY: The length is less than the capacity.            unsafe { self.push_within_capacity_unchecked(v) };            Ok(())        } else {            Err(PushError(v))        }    }     /// Appends an element to the back of the [`Vec`] instance without reallocating.    ///    /// # Safety    ///    /// The length must be less than the capacity.    unsafe fn push_within_capacity_unchecked(&mut self, v: T) {        let spare = self.spare_capacity_mut();         // SAFETY: By the safety requirements, `spare` is non-empty.        unsafe { spare.get_unchecked_mut(0) }.write(v);         // SAFETY: We just initialised the first spare entry, so it is safe to increase the length        // by 1. We also know that the new length is <= capacity because the caller guarantees that        // the length is less than the capacity at the beginning of this function.        unsafe { self.inc_len(1) };    }     /// Inserts an element at the given index in the [`Vec`] instance.    ///    /// Fails if the vector does not have capacity for the new element. Panics if the index is out    /// of bounds.    ///    /// # Examples    ///    /// ```    /// use kernel::alloc::kvec::InsertError;    ///    /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?;    /// for i in 0..5 {    ///     v.insert_within_capacity(0, i)?;    /// }    ///    /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_))));    /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_))));    /// assert_eq!(v, [4, 3, 2, 1, 0]);    /// # Ok::<(), Error>(())    /// ```    pub fn insert_within_capacity(        &mut self,        index: usize,        element: T,    ) -> Result<(), InsertError<T>> {        let len = self.len();        if index > len {            return Err(InsertError::IndexOutOfBounds(element));        }         if len >= self.capacity() {            return Err(InsertError::OutOfCapacity(element));        }         // SAFETY: This is in bounds since `index <= len < capacity`.        let p = unsafe { self.as_mut_ptr().add(index) };        // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element,        // but we restore the invariants below.        // SAFETY: Both the src and dst ranges end no later than one element after the length.        // Since the length is less than the capacity, both ranges are in bounds of the allocation.        unsafe { ptr::copy(p, p.add(1), len - index) };        // INVARIANT: This restores the Vec invariants.        // SAFETY: The pointer is in-bounds of the allocation.        unsafe { ptr::write(p, element) };        // SAFETY: Index `len` contains a valid element due to the above copy and write.        unsafe { self.inc_len(1) };        Ok(())    }     /// Removes the last element from a vector and returns it, or `None` if it is empty.    ///    /// # Examples    ///    /// ```    /// let mut v = KVec::new();    /// v.push(1, GFP_KERNEL)?;    /// v.push(2, GFP_KERNEL)?;    /// assert_eq!(&v, &[1, 2]);    ///    /// assert_eq!(v.pop(), Some(2));    /// assert_eq!(v.pop(), Some(1));    /// assert_eq!(v.pop(), None);    /// # Ok::<(), Error>(())    /// ```    pub fn pop(&mut self) -> Option<T> {        if self.is_empty() {            return None;        }         let removed: *mut T = {            // SAFETY: We just checked that the length is at least one.            let slice = unsafe { self.dec_len(1) };            // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1.            unsafe { slice.get_unchecked_mut(0) }        };         // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value.        Some(unsafe { removed.read() })    }     /// Removes the element at the given index.    ///    /// # Examples    ///    /// ```    /// let mut v = kernel::kvec![1, 2, 3]?;    /// assert_eq!(v.remove(1)?, 2);    /// assert_eq!(v, [1, 3]);    /// # Ok::<(), Error>(())    /// ```    pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> {        let value = {            let value_ref = self.get(i).ok_or(RemoveError)?;            // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we            // restore the invariants below.            // SAFETY: The value at index `i` is valid, because otherwise we would have already            // failed with `RemoveError`.            unsafe { ptr::read(value_ref) }        };         // SAFETY: We checked that `i` is in-bounds.        let p = unsafe { self.as_mut_ptr().add(i) };         // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants        // are restored after the below call to `dec_len(1)`.        // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the        // beginning of the vector, so this is in-bounds of the vector's allocation.        unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };         // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`,        // the length is at least one.        unsafe { self.dec_len(1) };         Ok(value)    }     /// Creates a new [`Vec`] instance with at least the given capacity.    ///    /// # Examples    ///    /// ```    /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?;    ///    /// assert!(v.capacity() >= 20);    /// # Ok::<(), Error>(())    /// ```

Lines 1–500 of 1401. Load more