// 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>(()) /// ``` pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> { let mut v = Vec::new(); v.reserve(capacity, flags)?; Ok(v) } /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// v.reserve(1, GFP_KERNEL)?; /// /// let (mut ptr, mut len, cap) = v.into_raw_parts(); /// /// // SAFETY: We've just reserved memory for another element. /// unsafe { ptr.add(len).write(4) }; /// len += 1; /// /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it /// // from the exact same raw parts. /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) }; /// /// assert_eq!(v, [1, 2, 3, 4]); /// /// # Ok::<(), Error>(()) /// ``` /// /// # Safety /// /// If `T` is a ZST: /// /// - `ptr` must be a dangling, well aligned pointer. /// /// Otherwise: /// /// - `ptr` must have been allocated with the allocator `A`. /// - `ptr` must satisfy or exceed the alignment requirements of `T`. /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes. /// - The allocated size in bytes must not be larger than `isize::MAX`. /// - `length` must be less than or equal to `capacity`. /// - The first `length` elements must be initialized values of type `T`. /// /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for /// `cap` and `len`. pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { let layout = if Self::is_zst() { ArrayLayout::empty() } else { // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is // smaller than `isize::MAX`. unsafe { ArrayLayout::new_unchecked(capacity) } }; // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are // covered by the safety requirements of this function. Self { // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid // memory allocation, allocated with `A`. ptr: unsafe { NonNull::new_unchecked(ptr) }, layout, len: length, _p: PhantomData::<A>, } } /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`. /// /// This will not run the destructor of the contained elements and for non-ZSTs the allocation /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the /// elements and free the allocation, if any. pub fn into_raw_parts(self) -> (*mut T, usize, usize) { let mut me = ManuallyDrop::new(self); let len = me.len(); let capacity = me.capacity(); let ptr = me.as_mut_ptr(); (ptr, len, capacity) } /// Clears the vector, removing all values. /// /// Note that this method has no effect on the allocated capacity /// of the vector. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// /// v.clear(); /// /// assert!(v.is_empty()); /// # Ok::<(), Error>(()) /// ``` #[inline] pub fn clear(&mut self) { self.truncate(0); } /// Ensures that the capacity exceeds the length by at least `additional` elements. /// /// # Examples /// /// ``` /// let mut v = KVec::new(); /// v.push(1, GFP_KERNEL)?; /// /// v.reserve(10, GFP_KERNEL)?; /// let cap = v.capacity(); /// assert!(cap >= v.len() + 10); /// /// v.reserve(10, GFP_KERNEL)?; /// let new_cap = v.capacity(); /// assert_eq!(new_cap, cap); /// /// # Ok::<(), Error>(()) /// ``` pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> { let len = self.len(); let cap = self.capacity(); if cap - len >= additional { return Ok(()); } if Self::is_zst() { // The capacity is already `usize::MAX` for ZSTs, we can't go higher. return Err(AllocError); } // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the // multiplication by two won't overflow. let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?); let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?; // SAFETY: // - `ptr` is valid because it's either `None` or comes from a previous call to // `A::realloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. let ptr = unsafe { A::realloc( Some(self.ptr.cast()), layout.into(), self.layout.into(), flags, NumaNode::NO_NODE, )? }; // INVARIANT: // - `layout` is some `ArrayLayout::<T>`, // - `ptr` has been created by `A::realloc` from `layout`. self.ptr = ptr.cast(); self.layout = layout; Ok(()) } /// Shortens the vector, setting the length to `len` and drops the removed values. /// If `len` is greater than or equal to the current length, this does nothing. /// /// This has no effect on the capacity and will not allocate. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// v.truncate(1); /// assert_eq!(v.len(), 1); /// assert_eq!(&v, &[1]); /// /// # Ok::<(), Error>(()) /// ``` pub fn truncate(&mut self, len: usize) { if let Some(count) = self.len().checked_sub(len) { // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or // equal to `self.len()`. let ptr: *mut [T] = unsafe { self.dec_len(count) }; // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are // valid elements whose ownership has been transferred to the caller. unsafe { ptr::drop_in_place(ptr) }; } } /// Takes ownership of all items in this vector without consuming the allocation. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![0, 1, 2, 3]?; /// /// for (i, j) in v.drain_all().enumerate() { /// assert_eq!(i, j); /// } /// /// assert!(v.capacity() >= 4); /// # Ok::<(), Error>(()) /// ``` pub fn drain_all(&mut self) -> DrainAll<'_, T> { // SAFETY: This does not underflow the length. let elems = unsafe { self.dec_len(self.len()) }; // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we // just set the length to zero, we may transfer ownership to the `DrainAll` object. DrainAll { elements: elems.iter_mut(), } } /// Removes all elements that don't match the provided closure. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3, 4]?; /// v.retain(|i| *i % 2 == 0); /// assert_eq!(v, [2, 4]); /// # Ok::<(), Error>(()) /// ``` pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) { let mut num_kept = 0; let mut next_to_check = 0; while let Some(to_check) = self.get_mut(next_to_check) { if f(to_check) { self.swap(num_kept, next_to_check); num_kept += 1; } next_to_check += 1; } self.truncate(num_kept); }}// TODO: This is a temporary KVVec-specific implementation. It should be replaced with a generic// `shrink_to()` for `impl<T, A: Allocator> Vec<T, A>` that uses `A::realloc()` once the// underlying allocators properly support shrinking via realloc.impl<T> Vec<T, KVmalloc> { /// Shrinks the capacity of the vector with a lower bound. /// /// The capacity will remain at least as large as both the length and the supplied value. /// If the current capacity is less than the lower limit, this is a no-op. /// /// For `kmalloc` allocations, this delegates to `realloc()`, which decides whether /// shrinking is worthwhile. For `vmalloc` allocations, shrinking only occurs if the /// operation would free at least one page of memory, and performs a deep copy since /// `vrealloc` does not yet support in-place shrinking. /// /// # Examples /// /// ``` /// // Allocate enough capacity to span multiple pages. /// let elements_per_page = kernel::page::PAGE_SIZE / core::mem::size_of::<u32>(); /// let mut v = KVVec::with_capacity(elements_per_page * 4, GFP_KERNEL)?; /// v.push(1, GFP_KERNEL)?; /// v.push(2, GFP_KERNEL)?; /// /// v.shrink_to(0, GFP_KERNEL)?; /// # Ok::<(), Error>(()) /// ``` pub fn shrink_to(&mut self, min_capacity: usize, flags: Flags) -> Result<(), AllocError> { let target_cap = core::cmp::max(self.len(), min_capacity); if self.capacity() <= target_cap { return Ok(()); } if Self::is_zst() { return Ok(()); } // For kmalloc allocations, delegate to realloc() and let the allocator decide // whether shrinking is worthwhile. // // SAFETY: `self.ptr` points to a valid `KVmalloc` allocation. if !unsafe { bindings::is_vmalloc_addr(self.ptr.as_ptr().cast()) } { let new_layout = ArrayLayout::<T>::new(target_cap).map_err(|_| AllocError)?; // SAFETY: // - `self.ptr` is valid and was previously allocated with `KVmalloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. let ptr = unsafe { KVmalloc::realloc( Some(self.ptr.cast()), new_layout.into(), self.layout.into(), flags, NumaNode::NO_NODE, )? }; self.ptr = ptr.cast(); self.layout = new_layout; return Ok(()); } // Only shrink if we would free at least one page. let current_size = self.capacity() * core::mem::size_of::<T>(); let target_size = target_cap * core::mem::size_of::<T>(); let current_pages = current_size.div_ceil(PAGE_SIZE); let target_pages = target_size.div_ceil(PAGE_SIZE); if current_pages <= target_pages { return Ok(()); } if target_cap == 0 { if !self.layout.is_empty() { // SAFETY: // - `self.ptr` was previously allocated with `KVmalloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. unsafe { KVmalloc::free(self.ptr.cast(), self.layout.into()) }; } self.ptr = NonNull::dangling(); self.layout = ArrayLayout::empty(); return Ok(()); } // SAFETY: `target_cap <= self.capacity()` and original capacity was valid. let new_layout = unsafe { ArrayLayout::<T>::new_unchecked(target_cap) }; let new_ptr = KVmalloc::alloc(new_layout.into(), flags, NumaNode::NO_NODE)?; // SAFETY: // - `self.as_ptr()` is valid for reads of `self.len()` elements of `T`. // - `new_ptr` is valid for writes of at least `target_cap >= self.len()` elements. // - The two allocations do not overlap since `new_ptr` is freshly allocated. // - Both pointers are properly aligned for `T`. unsafe { ptr::copy_nonoverlapping(self.as_ptr(), new_ptr.as_ptr().cast::<T>(), self.len()) }; // SAFETY: // - `self.ptr` was previously allocated with `KVmalloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. unsafe { KVmalloc::free(self.ptr.cast(), self.layout.into()) }; self.ptr = new_ptr.cast::<T>(); self.layout = new_layout; Ok(()) }} impl<T: Clone, A: Allocator> Vec<T, A> { /// Extend the vector by `n` clones of `value`. /// /// # Examples /// /// ``` /// let mut v = KVec::new(); /// v.push(1, GFP_KERNEL)?; /// /// v.extend_with(3, 5, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 5, 5, 5]); /// /// v.extend_with(2, 8, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 5, 5, 5, 8, 8]); /// /// v.extend_with(0, 3, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 5, 5, 5, 8, 8]); /// /// # Ok::<(), Error>(()) /// ``` pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> { if n == 0 { return Ok(()); } self.reserve(n, flags)?; let spare = self.spare_capacity_mut(); for item in spare.iter_mut().take(n - 1) { item.write(value.clone()); } // We can write the last element directly without cloning needlessly. spare[n - 1].write(value); // SAFETY: // - `self.len() + n <= self.capacity()` due to the call to reserve above, // - the loop and the line above initialized the next `n` elements. unsafe { self.inc_len(n) }; Ok(()) } /// Pushes clones of the elements of slice into the [`Vec`] instance. /// /// # Examples /// /// ``` /// let mut v = KVec::new(); /// v.push(1, GFP_KERNEL)?; /// /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?; /// assert_eq!(&v, &[1, 20, 30, 40]); /// /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?; /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]); /// # Ok::<(), Error>(()) /// ``` pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> { self.reserve(other.len(), flags)?; for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) { slot.write(item.clone()); } // SAFETY: // - `other.len()` spare entries have just been initialized, so it is safe to increase // the length by the same number. // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve` // call. unsafe { self.inc_len(other.len()) }; Ok(()) } /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`. pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> { let mut v = Self::with_capacity(n, flags)?; v.extend_with(n, value, flags)?; Ok(v) } /// Resizes the [`Vec`] so that `len` is equal to `new_len`. /// /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d. /// If `new_len` is larger, each new slot is filled with clones of `value`. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// v.resize(1, 42, GFP_KERNEL)?; /// assert_eq!(&v, &[1]); /// /// v.resize(3, 42, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 42, 42]); /// /// # Ok::<(), Error>(()) /// ``` pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> { match new_len.checked_sub(self.len()) { Some(n) => self.extend_with(n, value, flags), None => { self.truncate(new_len); Ok(()) } } }} impl<T, A> Drop for Vec<T, A>where A: Allocator,{ fn drop(&mut self) { // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant. unsafe { ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut( self.as_mut_ptr(), self.len, )) }; // SAFETY: // - `self.ptr` was previously allocated with `A`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. unsafe { A::free(self.ptr.cast(), self.layout.into()) };Lines 501–1000 of 1661. Previous lines Load more
// 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>(()) /// ``` pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> { let mut v = Vec::new(); v.reserve(capacity, flags)?; Ok(v) } /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// v.reserve(1, GFP_KERNEL)?; /// /// let (mut ptr, mut len, cap) = v.into_raw_parts(); /// /// // SAFETY: We've just reserved memory for another element. /// unsafe { ptr.add(len).write(4) }; /// len += 1; /// /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it /// // from the exact same raw parts. /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) }; /// /// assert_eq!(v, [1, 2, 3, 4]); /// /// # Ok::<(), Error>(()) /// ``` /// /// # Safety /// /// If `T` is a ZST: /// /// - `ptr` must be a dangling, well aligned pointer. /// /// Otherwise: /// /// - `ptr` must have been allocated with the allocator `A`. /// - `ptr` must satisfy or exceed the alignment requirements of `T`. /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes. /// - The allocated size in bytes must not be larger than `isize::MAX`. /// - `length` must be less than or equal to `capacity`. /// - The first `length` elements must be initialized values of type `T`. /// /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for /// `cap` and `len`. pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { let layout = if Self::is_zst() { ArrayLayout::empty() } else { // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is // smaller than `isize::MAX`. unsafe { ArrayLayout::new_unchecked(capacity) } }; // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are // covered by the safety requirements of this function. Self { // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid // memory allocation, allocated with `A`. ptr: unsafe { NonNull::new_unchecked(ptr) }, layout, len: length, _p: PhantomData::<A>, } } /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`. /// /// This will not run the destructor of the contained elements and for non-ZSTs the allocation /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the /// elements and free the allocation, if any. pub fn into_raw_parts(self) -> (*mut T, usize, usize) { let mut me = ManuallyDrop::new(self); let len = me.len(); let capacity = me.capacity(); let ptr = me.as_mut_ptr(); (ptr, len, capacity) } /// Clears the vector, removing all values. /// /// Note that this method has no effect on the allocated capacity /// of the vector. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// /// v.clear(); /// /// assert!(v.is_empty()); /// # Ok::<(), Error>(()) /// ``` #[inline] pub fn clear(&mut self) { self.truncate(0); } /// Ensures that the capacity exceeds the length by at least `additional` elements. /// /// # Examples /// /// ``` /// let mut v = KVec::new(); /// v.push(1, GFP_KERNEL)?; /// /// v.reserve(10, GFP_KERNEL)?; /// let cap = v.capacity(); /// assert!(cap >= v.len() + 10); /// /// v.reserve(10, GFP_KERNEL)?; /// let new_cap = v.capacity(); /// assert_eq!(new_cap, cap); /// /// # Ok::<(), Error>(()) /// ``` pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> { let len = self.len(); let cap = self.capacity(); if cap - len >= additional { return Ok(()); } if Self::is_zst() { // The capacity is already `usize::MAX` for ZSTs, we can't go higher. return Err(AllocError); } // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the // multiplication by two won't overflow. let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?); let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?; // SAFETY: // - `ptr` is valid because it's either `None` or comes from a previous call to // `A::realloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. let ptr = unsafe { A::realloc( Some(self.ptr.cast()), layout.into(), self.layout.into(), flags, NumaNode::NO_NODE, )? }; // INVARIANT: // - `layout` is some `ArrayLayout::<T>`, // - `ptr` has been created by `A::realloc` from `layout`. self.ptr = ptr.cast(); self.layout = layout; Ok(()) } /// Shortens the vector, setting the length to `len` and drops the removed values. /// If `len` is greater than or equal to the current length, this does nothing. /// /// This has no effect on the capacity and will not allocate. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// v.truncate(1); /// assert_eq!(v.len(), 1); /// assert_eq!(&v, &[1]); /// /// # Ok::<(), Error>(()) /// ``` pub fn truncate(&mut self, len: usize) { if let Some(count) = self.len().checked_sub(len) { // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or // equal to `self.len()`. let ptr: *mut [T] = unsafe { self.dec_len(count) }; // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are // valid elements whose ownership has been transferred to the caller. unsafe { ptr::drop_in_place(ptr) }; } } /// Takes ownership of all items in this vector without consuming the allocation. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![0, 1, 2, 3]?; /// /// for (i, j) in v.drain_all().enumerate() { /// assert_eq!(i, j); /// } /// /// assert!(v.capacity() >= 4); /// # Ok::<(), Error>(()) /// ``` pub fn drain_all(&mut self) -> DrainAll<'_, T> { // SAFETY: This does not underflow the length. let elems = unsafe { self.dec_len(self.len()) }; // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we // just set the length to zero, we may transfer ownership to the `DrainAll` object. DrainAll { elements: elems.iter_mut(), } } /// Removes all elements that don't match the provided closure. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3, 4]?; /// v.retain(|i| *i % 2 == 0); /// assert_eq!(v, [2, 4]); /// # Ok::<(), Error>(()) /// ``` pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) { let mut num_kept = 0; let mut next_to_check = 0; while let Some(to_check) = self.get_mut(next_to_check) { if f(to_check) { self.swap(num_kept, next_to_check); num_kept += 1; } next_to_check += 1; } self.truncate(num_kept); } } // TODO: This is a temporary KVVec-specific implementation. It should be replaced with a generic // `shrink_to()` for `impl<T, A: Allocator> Vec<T, A>` that uses `A::realloc()` once the // underlying allocators properly support shrinking via realloc. impl<T> Vec<T, KVmalloc> { /// Shrinks the capacity of the vector with a lower bound. /// /// The capacity will remain at least as large as both the length and the supplied value. /// If the current capacity is less than the lower limit, this is a no-op. /// /// For `kmalloc` allocations, this delegates to `realloc()`, which decides whether /// shrinking is worthwhile. For `vmalloc` allocations, shrinking only occurs if the /// operation would free at least one page of memory, and performs a deep copy since /// `vrealloc` does not yet support in-place shrinking. /// /// # Examples /// /// ``` /// // Allocate enough capacity to span multiple pages. /// let elements_per_page = kernel::page::PAGE_SIZE / core::mem::size_of::<u32>(); /// let mut v = KVVec::with_capacity(elements_per_page * 4, GFP_KERNEL)?; /// v.push(1, GFP_KERNEL)?; /// v.push(2, GFP_KERNEL)?; /// /// v.shrink_to(0, GFP_KERNEL)?; /// # Ok::<(), Error>(()) /// ``` pub fn shrink_to(&mut self, min_capacity: usize, flags: Flags) -> Result<(), AllocError> { let target_cap = core::cmp::max(self.len(), min_capacity); if self.capacity() <= target_cap { return Ok(()); } if Self::is_zst() { return Ok(()); } // For kmalloc allocations, delegate to realloc() and let the allocator decide // whether shrinking is worthwhile. // // SAFETY: `self.ptr` points to a valid `KVmalloc` allocation. if !unsafe { bindings::is_vmalloc_addr(self.ptr.as_ptr().cast()) } { let new_layout = ArrayLayout::<T>::new(target_cap).map_err(|_| AllocError)?; // SAFETY: // - `self.ptr` is valid and was previously allocated with `KVmalloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. let ptr = unsafe { KVmalloc::realloc( Some(self.ptr.cast()), new_layout.into(), self.layout.into(), flags, NumaNode::NO_NODE, )? }; self.ptr = ptr.cast(); self.layout = new_layout; return Ok(()); } // Only shrink if we would free at least one page. let current_size = self.capacity() * core::mem::size_of::<T>(); let target_size = target_cap * core::mem::size_of::<T>(); let current_pages = current_size.div_ceil(PAGE_SIZE); let target_pages = target_size.div_ceil(PAGE_SIZE); if current_pages <= target_pages { return Ok(()); } if target_cap == 0 { if !self.layout.is_empty() { // SAFETY: // - `self.ptr` was previously allocated with `KVmalloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. unsafe { KVmalloc::free(self.ptr.cast(), self.layout.into()) }; } self.ptr = NonNull::dangling(); self.layout = ArrayLayout::empty(); return Ok(()); } // SAFETY: `target_cap <= self.capacity()` and original capacity was valid. let new_layout = unsafe { ArrayLayout::<T>::new_unchecked(target_cap) }; let new_ptr = KVmalloc::alloc(new_layout.into(), flags, NumaNode::NO_NODE)?; // SAFETY: // - `self.as_ptr()` is valid for reads of `self.len()` elements of `T`. // - `new_ptr` is valid for writes of at least `target_cap >= self.len()` elements. // - The two allocations do not overlap since `new_ptr` is freshly allocated. // - Both pointers are properly aligned for `T`. unsafe { ptr::copy_nonoverlapping(self.as_ptr(), new_ptr.as_ptr().cast::<T>(), self.len()) }; // SAFETY: // - `self.ptr` was previously allocated with `KVmalloc`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. unsafe { KVmalloc::free(self.ptr.cast(), self.layout.into()) }; self.ptr = new_ptr.cast::<T>(); self.layout = new_layout; Ok(()) } } impl<T: Clone, A: Allocator> Vec<T, A> { /// Extend the vector by `n` clones of `value`. /// /// # Examples /// /// ``` /// let mut v = KVec::new(); /// v.push(1, GFP_KERNEL)?; /// /// v.extend_with(3, 5, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 5, 5, 5]); /// /// v.extend_with(2, 8, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 5, 5, 5, 8, 8]); /// /// v.extend_with(0, 3, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 5, 5, 5, 8, 8]); /// /// # Ok::<(), Error>(()) /// ``` pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> { if n == 0 { return Ok(()); } self.reserve(n, flags)?; let spare = self.spare_capacity_mut(); for item in spare.iter_mut().take(n - 1) { item.write(value.clone()); } // We can write the last element directly without cloning needlessly. spare[n - 1].write(value); // SAFETY: // - `self.len() + n <= self.capacity()` due to the call to reserve above, // - the loop and the line above initialized the next `n` elements. unsafe { self.inc_len(n) }; Ok(()) } /// Pushes clones of the elements of slice into the [`Vec`] instance. /// /// # Examples /// /// ``` /// let mut v = KVec::new(); /// v.push(1, GFP_KERNEL)?; /// /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?; /// assert_eq!(&v, &[1, 20, 30, 40]); /// /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?; /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]); /// # Ok::<(), Error>(()) /// ``` pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> { self.reserve(other.len(), flags)?; for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) { slot.write(item.clone()); } // SAFETY: // - `other.len()` spare entries have just been initialized, so it is safe to increase // the length by the same number. // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve` // call. unsafe { self.inc_len(other.len()) }; Ok(()) } /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`. pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> { let mut v = Self::with_capacity(n, flags)?; v.extend_with(n, value, flags)?; Ok(v) } /// Resizes the [`Vec`] so that `len` is equal to `new_len`. /// /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d. /// If `new_len` is larger, each new slot is filled with clones of `value`. /// /// # Examples /// /// ``` /// let mut v = kernel::kvec![1, 2, 3]?; /// v.resize(1, 42, GFP_KERNEL)?; /// assert_eq!(&v, &[1]); /// /// v.resize(3, 42, GFP_KERNEL)?; /// assert_eq!(&v, &[1, 42, 42]); /// /// # Ok::<(), Error>(()) /// ``` pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> { match new_len.checked_sub(self.len()) { Some(n) => self.extend_with(n, value, flags), None => { self.truncate(new_len); Ok(()) } } } } impl<T, A> Drop for Vec<T, A> where A: Allocator, { fn drop(&mut self) { // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant. unsafe { ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut( self.as_mut_ptr(), self.len, )) }; // SAFETY: // - `self.ptr` was previously allocated with `A`. // - `self.layout` matches the `ArrayLayout` of the preceding allocation. unsafe { A::free(self.ptr.cast(), self.layout.into()) };