kernel/alloc/
kvec.rs

1// SPDX-License-Identifier: GPL-2.0
2
3//! Implementation of [`Vec`].
4
5use super::{
6    allocator::{KVmalloc, Kmalloc, Vmalloc},
7    layout::ArrayLayout,
8    AllocError, Allocator, Box, Flags,
9};
10use core::{
11    borrow::{Borrow, BorrowMut},
12    fmt,
13    marker::PhantomData,
14    mem::{ManuallyDrop, MaybeUninit},
15    ops::Deref,
16    ops::DerefMut,
17    ops::Index,
18    ops::IndexMut,
19    ptr,
20    ptr::NonNull,
21    slice,
22    slice::SliceIndex,
23};
24
25mod errors;
26pub use self::errors::{InsertError, PushError, RemoveError};
27
28/// Create a [`KVec`] containing the arguments.
29///
30/// New memory is allocated with `GFP_KERNEL`.
31///
32/// # Examples
33///
34/// ```
35/// let mut v = kernel::kvec![];
36/// v.push(1, GFP_KERNEL)?;
37/// assert_eq!(v, [1]);
38///
39/// let mut v = kernel::kvec![1; 3]?;
40/// v.push(4, GFP_KERNEL)?;
41/// assert_eq!(v, [1, 1, 1, 4]);
42///
43/// let mut v = kernel::kvec![1, 2, 3]?;
44/// v.push(4, GFP_KERNEL)?;
45/// assert_eq!(v, [1, 2, 3, 4]);
46///
47/// # Ok::<(), Error>(())
48/// ```
49#[macro_export]
50macro_rules! kvec {
51    () => (
52        $crate::alloc::KVec::new()
53    );
54    ($elem:expr; $n:expr) => (
55        $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL)
56    );
57    ($($x:expr),+ $(,)?) => (
58        match $crate::alloc::KBox::new_uninit(GFP_KERNEL) {
59            Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))),
60            Err(e) => Err(e),
61        }
62    );
63}
64
65/// The kernel's [`Vec`] type.
66///
67/// A contiguous growable array type with contents allocated with the kernel's allocators (e.g.
68/// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec<T, A>`.
69///
70/// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For
71/// the most common allocators the type aliases [`KVec`], [`VVec`] and [`KVVec`] exist.
72///
73/// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.
74///
75/// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the
76/// capacity of the vector (the number of elements that currently fit into the vector), its length
77/// (the number of elements that are currently stored in the vector) and the `Allocator` type used
78/// to allocate (and free) the backing buffer.
79///
80/// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts
81/// and manually modified.
82///
83/// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements
84/// are added to the vector.
85///
86/// # Invariants
87///
88/// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for
89///   zero-sized types, is a dangling, well aligned pointer.
90///
91/// - `self.len` always represents the exact number of elements stored in the vector.
92///
93/// - `self.layout` represents the absolute number of elements that can be stored within the vector
94///   without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the
95///   backing buffer to be larger than `layout`.
96///
97/// - `self.len()` is always less than or equal to `self.capacity()`.
98///
99/// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer
100///   was allocated with (and must be freed with).
101pub struct Vec<T, A: Allocator> {
102    ptr: NonNull<T>,
103    /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes.
104    ///
105    /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of
106    /// elements we can still store without reallocating.
107    layout: ArrayLayout<T>,
108    len: usize,
109    _p: PhantomData<A>,
110}
111
112/// Type alias for [`Vec`] with a [`Kmalloc`] allocator.
113///
114/// # Examples
115///
116/// ```
117/// let mut v = KVec::new();
118/// v.push(1, GFP_KERNEL)?;
119/// assert_eq!(&v, &[1]);
120///
121/// # Ok::<(), Error>(())
122/// ```
123pub type KVec<T> = Vec<T, Kmalloc>;
124
125/// Type alias for [`Vec`] with a [`Vmalloc`] allocator.
126///
127/// # Examples
128///
129/// ```
130/// let mut v = VVec::new();
131/// v.push(1, GFP_KERNEL)?;
132/// assert_eq!(&v, &[1]);
133///
134/// # Ok::<(), Error>(())
135/// ```
136pub type VVec<T> = Vec<T, Vmalloc>;
137
138/// Type alias for [`Vec`] with a [`KVmalloc`] allocator.
139///
140/// # Examples
141///
142/// ```
143/// let mut v = KVVec::new();
144/// v.push(1, GFP_KERNEL)?;
145/// assert_eq!(&v, &[1]);
146///
147/// # Ok::<(), Error>(())
148/// ```
149pub type KVVec<T> = Vec<T, KVmalloc>;
150
151// SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements.
152unsafe impl<T, A> Send for Vec<T, A>
153where
154    T: Send,
155    A: Allocator,
156{
157}
158
159// SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements.
160unsafe impl<T, A> Sync for Vec<T, A>
161where
162    T: Sync,
163    A: Allocator,
164{
165}
166
167impl<T, A> Vec<T, A>
168where
169    A: Allocator,
170{
171    #[inline]
172    const fn is_zst() -> bool {
173        core::mem::size_of::<T>() == 0
174    }
175
176    /// Returns the number of elements that can be stored within the vector without allocating
177    /// additional memory.
178    pub fn capacity(&self) -> usize {
179        if const { Self::is_zst() } {
180            usize::MAX
181        } else {
182            self.layout.len()
183        }
184    }
185
186    /// Returns the number of elements stored within the vector.
187    #[inline]
188    pub fn len(&self) -> usize {
189        self.len
190    }
191
192    /// Increments `self.len` by `additional`.
193    ///
194    /// # Safety
195    ///
196    /// - `additional` must be less than or equal to `self.capacity - self.len`.
197    /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized.
198    #[inline]
199    pub unsafe fn inc_len(&mut self, additional: usize) {
200        // Guaranteed by the type invariant to never underflow.
201        debug_assert!(additional <= self.capacity() - self.len());
202        // INVARIANT: By the safety requirements of this method this represents the exact number of
203        // elements stored within `self`.
204        self.len += additional;
205    }
206
207    /// Decreases `self.len` by `count`.
208    ///
209    /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's
210    /// responsibility to drop these elements if necessary.
211    ///
212    /// # Safety
213    ///
214    /// - `count` must be less than or equal to `self.len`.
215    unsafe fn dec_len(&mut self, count: usize) -> &mut [T] {
216        debug_assert!(count <= self.len());
217        // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count,
218        // self.len)`, hence the updated value of `set.len` represents the exact number of elements
219        // stored within `self`.
220        self.len -= count;
221        // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized
222        // elements of type `T`.
223        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) }
224    }
225
226    /// Returns a slice of the entire vector.
227    #[inline]
228    pub fn as_slice(&self) -> &[T] {
229        self
230    }
231
232    /// Returns a mutable slice of the entire vector.
233    #[inline]
234    pub fn as_mut_slice(&mut self) -> &mut [T] {
235        self
236    }
237
238    /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a
239    /// dangling raw pointer.
240    #[inline]
241    pub fn as_mut_ptr(&mut self) -> *mut T {
242        self.ptr.as_ptr()
243    }
244
245    /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw
246    /// pointer.
247    #[inline]
248    pub fn as_ptr(&self) -> *const T {
249        self.ptr.as_ptr()
250    }
251
252    /// Returns `true` if the vector contains no elements, `false` otherwise.
253    ///
254    /// # Examples
255    ///
256    /// ```
257    /// let mut v = KVec::new();
258    /// assert!(v.is_empty());
259    ///
260    /// v.push(1, GFP_KERNEL);
261    /// assert!(!v.is_empty());
262    /// ```
263    #[inline]
264    pub fn is_empty(&self) -> bool {
265        self.len() == 0
266    }
267
268    /// Creates a new, empty `Vec<T, A>`.
269    ///
270    /// This method does not allocate by itself.
271    #[inline]
272    pub const fn new() -> Self {
273        // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet,
274        // - `ptr` is a properly aligned dangling pointer for type `T`,
275        // - `layout` is an empty `ArrayLayout` (zero capacity)
276        // - `len` is zero, since no elements can be or have been stored,
277        // - `A` is always valid.
278        Self {
279            ptr: NonNull::dangling(),
280            layout: ArrayLayout::empty(),
281            len: 0,
282            _p: PhantomData::<A>,
283        }
284    }
285
286    /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector.
287    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
288        // SAFETY:
289        // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the
290        //   resulting pointer is guaranteed to be part of the same allocated object.
291        // - `self.len` can not overflow `isize`.
292        let ptr = unsafe { self.as_mut_ptr().add(self.len) }.cast::<MaybeUninit<T>>();
293
294        // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated
295        // and valid, but uninitialized.
296        unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) }
297    }
298
299    /// Appends an element to the back of the [`Vec`] instance.
300    ///
301    /// # Examples
302    ///
303    /// ```
304    /// let mut v = KVec::new();
305    /// v.push(1, GFP_KERNEL)?;
306    /// assert_eq!(&v, &[1]);
307    ///
308    /// v.push(2, GFP_KERNEL)?;
309    /// assert_eq!(&v, &[1, 2]);
310    /// # Ok::<(), Error>(())
311    /// ```
312    pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
313        self.reserve(1, flags)?;
314        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
315        // than the length.
316        unsafe { self.push_within_capacity_unchecked(v) };
317        Ok(())
318    }
319
320    /// Appends an element to the back of the [`Vec`] instance without reallocating.
321    ///
322    /// Fails if the vector does not have capacity for the new element.
323    ///
324    /// # Examples
325    ///
326    /// ```
327    /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;
328    /// for i in 0..10 {
329    ///     v.push_within_capacity(i)?;
330    /// }
331    ///
332    /// assert!(v.push_within_capacity(10).is_err());
333    /// # Ok::<(), Error>(())
334    /// ```
335    pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> {
336        if self.len() < self.capacity() {
337            // SAFETY: The length is less than the capacity.
338            unsafe { self.push_within_capacity_unchecked(v) };
339            Ok(())
340        } else {
341            Err(PushError(v))
342        }
343    }
344
345    /// Appends an element to the back of the [`Vec`] instance without reallocating.
346    ///
347    /// # Safety
348    ///
349    /// The length must be less than the capacity.
350    unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
351        let spare = self.spare_capacity_mut();
352
353        // SAFETY: By the safety requirements, `spare` is non-empty.
354        unsafe { spare.get_unchecked_mut(0) }.write(v);
355
356        // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
357        // by 1. We also know that the new length is <= capacity because the caller guarantees that
358        // the length is less than the capacity at the beginning of this function.
359        unsafe { self.inc_len(1) };
360    }
361
362    /// Inserts an element at the given index in the [`Vec`] instance.
363    ///
364    /// Fails if the vector does not have capacity for the new element. Panics if the index is out
365    /// of bounds.
366    ///
367    /// # Examples
368    ///
369    /// ```
370    /// use kernel::alloc::kvec::InsertError;
371    ///
372    /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?;
373    /// for i in 0..5 {
374    ///     v.insert_within_capacity(0, i)?;
375    /// }
376    ///
377    /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_))));
378    /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_))));
379    /// assert_eq!(v, [4, 3, 2, 1, 0]);
380    /// # Ok::<(), Error>(())
381    /// ```
382    pub fn insert_within_capacity(
383        &mut self,
384        index: usize,
385        element: T,
386    ) -> Result<(), InsertError<T>> {
387        let len = self.len();
388        if index > len {
389            return Err(InsertError::IndexOutOfBounds(element));
390        }
391
392        if len >= self.capacity() {
393            return Err(InsertError::OutOfCapacity(element));
394        }
395
396        // SAFETY: This is in bounds since `index <= len < capacity`.
397        let p = unsafe { self.as_mut_ptr().add(index) };
398        // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element,
399        // but we restore the invariants below.
400        // SAFETY: Both the src and dst ranges end no later than one element after the length.
401        // Since the length is less than the capacity, both ranges are in bounds of the allocation.
402        unsafe { ptr::copy(p, p.add(1), len - index) };
403        // INVARIANT: This restores the Vec invariants.
404        // SAFETY: The pointer is in-bounds of the allocation.
405        unsafe { ptr::write(p, element) };
406        // SAFETY: Index `len` contains a valid element due to the above copy and write.
407        unsafe { self.inc_len(1) };
408        Ok(())
409    }
410
411    /// Removes the last element from a vector and returns it, or `None` if it is empty.
412    ///
413    /// # Examples
414    ///
415    /// ```
416    /// let mut v = KVec::new();
417    /// v.push(1, GFP_KERNEL)?;
418    /// v.push(2, GFP_KERNEL)?;
419    /// assert_eq!(&v, &[1, 2]);
420    ///
421    /// assert_eq!(v.pop(), Some(2));
422    /// assert_eq!(v.pop(), Some(1));
423    /// assert_eq!(v.pop(), None);
424    /// # Ok::<(), Error>(())
425    /// ```
426    pub fn pop(&mut self) -> Option<T> {
427        if self.is_empty() {
428            return None;
429        }
430
431        let removed: *mut T = {
432            // SAFETY: We just checked that the length is at least one.
433            let slice = unsafe { self.dec_len(1) };
434            // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1.
435            unsafe { slice.get_unchecked_mut(0) }
436        };
437
438        // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value.
439        Some(unsafe { removed.read() })
440    }
441
442    /// Removes the element at the given index.
443    ///
444    /// # Examples
445    ///
446    /// ```
447    /// let mut v = kernel::kvec![1, 2, 3]?;
448    /// assert_eq!(v.remove(1)?, 2);
449    /// assert_eq!(v, [1, 3]);
450    /// # Ok::<(), Error>(())
451    /// ```
452    pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> {
453        let value = {
454            let value_ref = self.get(i).ok_or(RemoveError)?;
455            // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we
456            // restore the invariants below.
457            // SAFETY: The value at index `i` is valid, because otherwise we would have already
458            // failed with `RemoveError`.
459            unsafe { ptr::read(value_ref) }
460        };
461
462        // SAFETY: We checked that `i` is in-bounds.
463        let p = unsafe { self.as_mut_ptr().add(i) };
464
465        // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants
466        // are restored after the below call to `dec_len(1)`.
467        // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the
468        // beginning of the vector, so this is in-bounds of the vector's allocation.
469        unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };
470
471        // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`,
472        // the length is at least one.
473        unsafe { self.dec_len(1) };
474
475        Ok(value)
476    }
477
478    /// Creates a new [`Vec`] instance with at least the given capacity.
479    ///
480    /// # Examples
481    ///
482    /// ```
483    /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?;
484    ///
485    /// assert!(v.capacity() >= 20);
486    /// # Ok::<(), Error>(())
487    /// ```
488    pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {
489        let mut v = Vec::new();
490
491        v.reserve(capacity, flags)?;
492
493        Ok(v)
494    }
495
496    /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`.
497    ///
498    /// # Examples
499    ///
500    /// ```
501    /// let mut v = kernel::kvec![1, 2, 3]?;
502    /// v.reserve(1, GFP_KERNEL)?;
503    ///
504    /// let (mut ptr, mut len, cap) = v.into_raw_parts();
505    ///
506    /// // SAFETY: We've just reserved memory for another element.
507    /// unsafe { ptr.add(len).write(4) };
508    /// len += 1;
509    ///
510    /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and
511    /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it
512    /// // from the exact same raw parts.
513    /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) };
514    ///
515    /// assert_eq!(v, [1, 2, 3, 4]);
516    ///
517    /// # Ok::<(), Error>(())
518    /// ```
519    ///
520    /// # Safety
521    ///
522    /// If `T` is a ZST:
523    ///
524    /// - `ptr` must be a dangling, well aligned pointer.
525    ///
526    /// Otherwise:
527    ///
528    /// - `ptr` must have been allocated with the allocator `A`.
529    /// - `ptr` must satisfy or exceed the alignment requirements of `T`.
530    /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes.
531    /// - The allocated size in bytes must not be larger than `isize::MAX`.
532    /// - `length` must be less than or equal to `capacity`.
533    /// - The first `length` elements must be initialized values of type `T`.
534    ///
535    /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for
536    /// `cap` and `len`.
537    pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
538        let layout = if Self::is_zst() {
539            ArrayLayout::empty()
540        } else {
541            // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is
542            // smaller than `isize::MAX`.
543            unsafe { ArrayLayout::new_unchecked(capacity) }
544        };
545
546        // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are
547        // covered by the safety requirements of this function.
548        Self {
549            // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid
550            // memory allocation, allocated with `A`.
551            ptr: unsafe { NonNull::new_unchecked(ptr) },
552            layout,
553            len: length,
554            _p: PhantomData::<A>,
555        }
556    }
557
558    /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`.
559    ///
560    /// This will not run the destructor of the contained elements and for non-ZSTs the allocation
561    /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the
562    /// elements and free the allocation, if any.
563    pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
564        let mut me = ManuallyDrop::new(self);
565        let len = me.len();
566        let capacity = me.capacity();
567        let ptr = me.as_mut_ptr();
568        (ptr, len, capacity)
569    }
570
571    /// Clears the vector, removing all values.
572    ///
573    /// Note that this method has no effect on the allocated capacity
574    /// of the vector.
575    ///
576    /// # Examples
577    ///
578    /// ```
579    /// let mut v = kernel::kvec![1, 2, 3]?;
580    ///
581    /// v.clear();
582    ///
583    /// assert!(v.is_empty());
584    /// # Ok::<(), Error>(())
585    /// ```
586    #[inline]
587    pub fn clear(&mut self) {
588        self.truncate(0);
589    }
590
591    /// Ensures that the capacity exceeds the length by at least `additional` elements.
592    ///
593    /// # Examples
594    ///
595    /// ```
596    /// let mut v = KVec::new();
597    /// v.push(1, GFP_KERNEL)?;
598    ///
599    /// v.reserve(10, GFP_KERNEL)?;
600    /// let cap = v.capacity();
601    /// assert!(cap >= 10);
602    ///
603    /// v.reserve(10, GFP_KERNEL)?;
604    /// let new_cap = v.capacity();
605    /// assert_eq!(new_cap, cap);
606    ///
607    /// # Ok::<(), Error>(())
608    /// ```
609    pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {
610        let len = self.len();
611        let cap = self.capacity();
612
613        if cap - len >= additional {
614            return Ok(());
615        }
616
617        if Self::is_zst() {
618            // The capacity is already `usize::MAX` for ZSTs, we can't go higher.
619            return Err(AllocError);
620        }
621
622        // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the
623        // multiplication by two won't overflow.
624        let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?);
625        let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?;
626
627        // SAFETY:
628        // - `ptr` is valid because it's either `None` or comes from a previous call to
629        //   `A::realloc`.
630        // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
631        let ptr = unsafe {
632            A::realloc(
633                Some(self.ptr.cast()),
634                layout.into(),
635                self.layout.into(),
636                flags,
637            )?
638        };
639
640        // INVARIANT:
641        // - `layout` is some `ArrayLayout::<T>`,
642        // - `ptr` has been created by `A::realloc` from `layout`.
643        self.ptr = ptr.cast();
644        self.layout = layout;
645
646        Ok(())
647    }
648
649    /// Shortens the vector, setting the length to `len` and drops the removed values.
650    /// If `len` is greater than or equal to the current length, this does nothing.
651    ///
652    /// This has no effect on the capacity and will not allocate.
653    ///
654    /// # Examples
655    ///
656    /// ```
657    /// let mut v = kernel::kvec![1, 2, 3]?;
658    /// v.truncate(1);
659    /// assert_eq!(v.len(), 1);
660    /// assert_eq!(&v, &[1]);
661    ///
662    /// # Ok::<(), Error>(())
663    /// ```
664    pub fn truncate(&mut self, len: usize) {
665        if let Some(count) = self.len().checked_sub(len) {
666            // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
667            // equal to `self.len()`.
668            let ptr: *mut [T] = unsafe { self.dec_len(count) };
669
670            // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are
671            // valid elements whose ownership has been transferred to the caller.
672            unsafe { ptr::drop_in_place(ptr) };
673        }
674    }
675
676    /// Takes ownership of all items in this vector without consuming the allocation.
677    ///
678    /// # Examples
679    ///
680    /// ```
681    /// let mut v = kernel::kvec![0, 1, 2, 3]?;
682    ///
683    /// for (i, j) in v.drain_all().enumerate() {
684    ///     assert_eq!(i, j);
685    /// }
686    ///
687    /// assert!(v.capacity() >= 4);
688    /// # Ok::<(), Error>(())
689    /// ```
690    pub fn drain_all(&mut self) -> DrainAll<'_, T> {
691        // SAFETY: This does not underflow the length.
692        let elems = unsafe { self.dec_len(self.len()) };
693        // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we
694        // just set the length to zero, we may transfer ownership to the `DrainAll` object.
695        DrainAll {
696            elements: elems.iter_mut(),
697        }
698    }
699
700    /// Removes all elements that don't match the provided closure.
701    ///
702    /// # Examples
703    ///
704    /// ```
705    /// let mut v = kernel::kvec![1, 2, 3, 4]?;
706    /// v.retain(|i| *i % 2 == 0);
707    /// assert_eq!(v, [2, 4]);
708    /// # Ok::<(), Error>(())
709    /// ```
710    pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) {
711        let mut num_kept = 0;
712        let mut next_to_check = 0;
713        while let Some(to_check) = self.get_mut(next_to_check) {
714            if f(to_check) {
715                self.swap(num_kept, next_to_check);
716                num_kept += 1;
717            }
718            next_to_check += 1;
719        }
720        self.truncate(num_kept);
721    }
722}
723
724impl<T: Clone, A: Allocator> Vec<T, A> {
725    /// Extend the vector by `n` clones of `value`.
726    pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> {
727        if n == 0 {
728            return Ok(());
729        }
730
731        self.reserve(n, flags)?;
732
733        let spare = self.spare_capacity_mut();
734
735        for item in spare.iter_mut().take(n - 1) {
736            item.write(value.clone());
737        }
738
739        // We can write the last element directly without cloning needlessly.
740        spare[n - 1].write(value);
741
742        // SAFETY:
743        // - `self.len() + n < self.capacity()` due to the call to reserve above,
744        // - the loop and the line above initialized the next `n` elements.
745        unsafe { self.inc_len(n) };
746
747        Ok(())
748    }
749
750    /// Pushes clones of the elements of slice into the [`Vec`] instance.
751    ///
752    /// # Examples
753    ///
754    /// ```
755    /// let mut v = KVec::new();
756    /// v.push(1, GFP_KERNEL)?;
757    ///
758    /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?;
759    /// assert_eq!(&v, &[1, 20, 30, 40]);
760    ///
761    /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?;
762    /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]);
763    /// # Ok::<(), Error>(())
764    /// ```
765    pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> {
766        self.reserve(other.len(), flags)?;
767        for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) {
768            slot.write(item.clone());
769        }
770
771        // SAFETY:
772        // - `other.len()` spare entries have just been initialized, so it is safe to increase
773        //   the length by the same number.
774        // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve`
775        //   call.
776        unsafe { self.inc_len(other.len()) };
777        Ok(())
778    }
779
780    /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`.
781    pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> {
782        let mut v = Self::with_capacity(n, flags)?;
783
784        v.extend_with(n, value, flags)?;
785
786        Ok(v)
787    }
788
789    /// Resizes the [`Vec`] so that `len` is equal to `new_len`.
790    ///
791    /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d.
792    /// If `new_len` is larger, each new slot is filled with clones of `value`.
793    ///
794    /// # Examples
795    ///
796    /// ```
797    /// let mut v = kernel::kvec![1, 2, 3]?;
798    /// v.resize(1, 42, GFP_KERNEL)?;
799    /// assert_eq!(&v, &[1]);
800    ///
801    /// v.resize(3, 42, GFP_KERNEL)?;
802    /// assert_eq!(&v, &[1, 42, 42]);
803    ///
804    /// # Ok::<(), Error>(())
805    /// ```
806    pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> {
807        match new_len.checked_sub(self.len()) {
808            Some(n) => self.extend_with(n, value, flags),
809            None => {
810                self.truncate(new_len);
811                Ok(())
812            }
813        }
814    }
815}
816
817impl<T, A> Drop for Vec<T, A>
818where
819    A: Allocator,
820{
821    fn drop(&mut self) {
822        // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant.
823        unsafe {
824            ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut(
825                self.as_mut_ptr(),
826                self.len,
827            ))
828        };
829
830        // SAFETY:
831        // - `self.ptr` was previously allocated with `A`.
832        // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
833        unsafe { A::free(self.ptr.cast(), self.layout.into()) };
834    }
835}
836
837impl<T, A, const N: usize> From<Box<[T; N], A>> for Vec<T, A>
838where
839    A: Allocator,
840{
841    fn from(b: Box<[T; N], A>) -> Vec<T, A> {
842        let len = b.len();
843        let ptr = Box::into_raw(b);
844
845        // SAFETY:
846        // - `b` has been allocated with `A`,
847        // - `ptr` fulfills the alignment requirements for `T`,
848        // - `ptr` points to memory with at least a size of `size_of::<T>() * len`,
849        // - all elements within `b` are initialized values of `T`,
850        // - `len` does not exceed `isize::MAX`.
851        unsafe { Vec::from_raw_parts(ptr.cast(), len, len) }
852    }
853}
854
855impl<T, A: Allocator> Default for Vec<T, A> {
856    #[inline]
857    fn default() -> Self {
858        Self::new()
859    }
860}
861
862impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
863    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
864        fmt::Debug::fmt(&**self, f)
865    }
866}
867
868impl<T, A> Deref for Vec<T, A>
869where
870    A: Allocator,
871{
872    type Target = [T];
873
874    #[inline]
875    fn deref(&self) -> &[T] {
876        // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len`
877        // initialized elements of type `T`.
878        unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
879    }
880}
881
882impl<T, A> DerefMut for Vec<T, A>
883where
884    A: Allocator,
885{
886    #[inline]
887    fn deref_mut(&mut self) -> &mut [T] {
888        // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len`
889        // initialized elements of type `T`.
890        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
891    }
892}
893
894/// # Examples
895///
896/// ```
897/// # use core::borrow::Borrow;
898/// struct Foo<B: Borrow<[u32]>>(B);
899///
900/// // Owned array.
901/// let owned_array = Foo([1, 2, 3]);
902///
903/// // Owned vector.
904/// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?);
905///
906/// let arr = [1, 2, 3];
907/// // Borrowed slice from `arr`.
908/// let borrowed_slice = Foo(&arr[..]);
909/// # Ok::<(), Error>(())
910/// ```
911impl<T, A> Borrow<[T]> for Vec<T, A>
912where
913    A: Allocator,
914{
915    fn borrow(&self) -> &[T] {
916        self.as_slice()
917    }
918}
919
920/// # Examples
921///
922/// ```
923/// # use core::borrow::BorrowMut;
924/// struct Foo<B: BorrowMut<[u32]>>(B);
925///
926/// // Owned array.
927/// let owned_array = Foo([1, 2, 3]);
928///
929/// // Owned vector.
930/// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?);
931///
932/// let mut arr = [1, 2, 3];
933/// // Borrowed slice from `arr`.
934/// let borrowed_slice = Foo(&mut arr[..]);
935/// # Ok::<(), Error>(())
936/// ```
937impl<T, A> BorrowMut<[T]> for Vec<T, A>
938where
939    A: Allocator,
940{
941    fn borrow_mut(&mut self) -> &mut [T] {
942        self.as_mut_slice()
943    }
944}
945
946impl<T: Eq, A> Eq for Vec<T, A> where A: Allocator {}
947
948impl<T, I: SliceIndex<[T]>, A> Index<I> for Vec<T, A>
949where
950    A: Allocator,
951{
952    type Output = I::Output;
953
954    #[inline]
955    fn index(&self, index: I) -> &Self::Output {
956        Index::index(&**self, index)
957    }
958}
959
960impl<T, I: SliceIndex<[T]>, A> IndexMut<I> for Vec<T, A>
961where
962    A: Allocator,
963{
964    #[inline]
965    fn index_mut(&mut self, index: I) -> &mut Self::Output {
966        IndexMut::index_mut(&mut **self, index)
967    }
968}
969
970macro_rules! impl_slice_eq {
971    ($([$($vars:tt)*] $lhs:ty, $rhs:ty,)*) => {
972        $(
973            impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs
974            where
975                T: PartialEq<U>,
976            {
977                #[inline]
978                fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
979            }
980        )*
981    }
982}
983
984impl_slice_eq! {
985    [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2>,
986    [A: Allocator] Vec<T, A>, &[U],
987    [A: Allocator] Vec<T, A>, &mut [U],
988    [A: Allocator] &[T], Vec<U, A>,
989    [A: Allocator] &mut [T], Vec<U, A>,
990    [A: Allocator] Vec<T, A>, [U],
991    [A: Allocator] [T], Vec<U, A>,
992    [A: Allocator, const N: usize] Vec<T, A>, [U; N],
993    [A: Allocator, const N: usize] Vec<T, A>, &[U; N],
994}
995
996impl<'a, T, A> IntoIterator for &'a Vec<T, A>
997where
998    A: Allocator,
999{
1000    type Item = &'a T;
1001    type IntoIter = slice::Iter<'a, T>;
1002
1003    fn into_iter(self) -> Self::IntoIter {
1004        self.iter()
1005    }
1006}
1007
1008impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A>
1009where
1010    A: Allocator,
1011{
1012    type Item = &'a mut T;
1013    type IntoIter = slice::IterMut<'a, T>;
1014
1015    fn into_iter(self) -> Self::IntoIter {
1016        self.iter_mut()
1017    }
1018}
1019
1020/// An [`Iterator`] implementation for [`Vec`] that moves elements out of a vector.
1021///
1022/// This structure is created by the [`Vec::into_iter`] method on [`Vec`] (provided by the
1023/// [`IntoIterator`] trait).
1024///
1025/// # Examples
1026///
1027/// ```
1028/// let v = kernel::kvec![0, 1, 2]?;
1029/// let iter = v.into_iter();
1030///
1031/// # Ok::<(), Error>(())
1032/// ```
1033pub struct IntoIter<T, A: Allocator> {
1034    ptr: *mut T,
1035    buf: NonNull<T>,
1036    len: usize,
1037    layout: ArrayLayout<T>,
1038    _p: PhantomData<A>,
1039}
1040
1041impl<T, A> IntoIter<T, A>
1042where
1043    A: Allocator,
1044{
1045    fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) {
1046        let me = ManuallyDrop::new(self);
1047        let ptr = me.ptr;
1048        let buf = me.buf;
1049        let len = me.len;
1050        let cap = me.layout.len();
1051        (ptr, buf, len, cap)
1052    }
1053
1054    /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`.
1055    ///
1056    /// # Examples
1057    ///
1058    /// ```
1059    /// let v = kernel::kvec![1, 2, 3]?;
1060    /// let mut it = v.into_iter();
1061    ///
1062    /// assert_eq!(it.next(), Some(1));
1063    ///
1064    /// let v = it.collect(GFP_KERNEL);
1065    /// assert_eq!(v, [2, 3]);
1066    ///
1067    /// # Ok::<(), Error>(())
1068    /// ```
1069    ///
1070    /// # Implementation details
1071    ///
1072    /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait
1073    /// in the kernel, namely:
1074    ///
1075    /// - Rust's specialization feature is unstable. This prevents us to optimize for the special
1076    ///   case where `I::IntoIter` equals `Vec`'s `IntoIter` type.
1077    /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator`
1078    ///   doesn't require this type to be `'static`.
1079    /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence
1080    ///   we can't properly handle allocation failures.
1081    /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation
1082    ///   flags.
1083    ///
1084    /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a
1085    /// `Vec` again.
1086    ///
1087    /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing
1088    /// buffer. However, this backing buffer may be shrunk to the actual count of elements.
1089    pub fn collect(self, flags: Flags) -> Vec<T, A> {
1090        let old_layout = self.layout;
1091        let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
1092        let has_advanced = ptr != buf.as_ptr();
1093
1094        if has_advanced {
1095            // Copy the contents we have advanced to at the beginning of the buffer.
1096            //
1097            // SAFETY:
1098            // - `ptr` is valid for reads of `len * size_of::<T>()` bytes,
1099            // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes,
1100            // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to
1101            //   each other,
1102            // - both `ptr` and `buf.ptr()` are properly aligned.
1103            unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
1104            ptr = buf.as_ptr();
1105
1106            // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type
1107            // invariant.
1108            let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) };
1109
1110            // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by
1111            // the type invariant to be smaller than `cap`. Depending on `realloc` this operation
1112            // may shrink the buffer or leave it as it is.
1113            ptr = match unsafe {
1114                A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags)
1115            } {
1116                // If we fail to shrink, which likely can't even happen, continue with the existing
1117                // buffer.
1118                Err(_) => ptr,
1119                Ok(ptr) => {
1120                    cap = len;
1121                    ptr.as_ptr().cast()
1122                }
1123            };
1124        }
1125
1126        // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
1127        // the beginning of the buffer and `len` has been adjusted accordingly.
1128        //
1129        // - `ptr` is guaranteed to point to the start of the backing buffer.
1130        // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`.
1131        // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original
1132        //   `Vec`.
1133        unsafe { Vec::from_raw_parts(ptr, len, cap) }
1134    }
1135}
1136
1137impl<T, A> Iterator for IntoIter<T, A>
1138where
1139    A: Allocator,
1140{
1141    type Item = T;
1142
1143    /// # Examples
1144    ///
1145    /// ```
1146    /// let v = kernel::kvec![1, 2, 3]?;
1147    /// let mut it = v.into_iter();
1148    ///
1149    /// assert_eq!(it.next(), Some(1));
1150    /// assert_eq!(it.next(), Some(2));
1151    /// assert_eq!(it.next(), Some(3));
1152    /// assert_eq!(it.next(), None);
1153    ///
1154    /// # Ok::<(), Error>(())
1155    /// ```
1156    fn next(&mut self) -> Option<T> {
1157        if self.len == 0 {
1158            return None;
1159        }
1160
1161        let current = self.ptr;
1162
1163        // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr`
1164        // by one guarantees that.
1165        unsafe { self.ptr = self.ptr.add(1) };
1166
1167        self.len -= 1;
1168
1169        // SAFETY: `current` is guaranteed to point at a valid element within the buffer.
1170        Some(unsafe { current.read() })
1171    }
1172
1173    /// # Examples
1174    ///
1175    /// ```
1176    /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?;
1177    /// let mut iter = v.into_iter();
1178    /// let size = iter.size_hint().0;
1179    ///
1180    /// iter.next();
1181    /// assert_eq!(iter.size_hint().0, size - 1);
1182    ///
1183    /// iter.next();
1184    /// assert_eq!(iter.size_hint().0, size - 2);
1185    ///
1186    /// iter.next();
1187    /// assert_eq!(iter.size_hint().0, size - 3);
1188    ///
1189    /// # Ok::<(), Error>(())
1190    /// ```
1191    fn size_hint(&self) -> (usize, Option<usize>) {
1192        (self.len, Some(self.len))
1193    }
1194}
1195
1196impl<T, A> Drop for IntoIter<T, A>
1197where
1198    A: Allocator,
1199{
1200    fn drop(&mut self) {
1201        // SAFETY: `self.ptr` is guaranteed to be valid by the type invariant.
1202        unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) };
1203
1204        // SAFETY:
1205        // - `self.buf` was previously allocated with `A`.
1206        // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
1207        unsafe { A::free(self.buf.cast(), self.layout.into()) };
1208    }
1209}
1210
1211impl<T, A> IntoIterator for Vec<T, A>
1212where
1213    A: Allocator,
1214{
1215    type Item = T;
1216    type IntoIter = IntoIter<T, A>;
1217
1218    /// Consumes the `Vec<T, A>` and creates an `Iterator`, which moves each value out of the
1219    /// vector (from start to end).
1220    ///
1221    /// # Examples
1222    ///
1223    /// ```
1224    /// let v = kernel::kvec![1, 2]?;
1225    /// let mut v_iter = v.into_iter();
1226    ///
1227    /// let first_element: Option<u32> = v_iter.next();
1228    ///
1229    /// assert_eq!(first_element, Some(1));
1230    /// assert_eq!(v_iter.next(), Some(2));
1231    /// assert_eq!(v_iter.next(), None);
1232    ///
1233    /// # Ok::<(), Error>(())
1234    /// ```
1235    ///
1236    /// ```
1237    /// let v = kernel::kvec![];
1238    /// let mut v_iter = v.into_iter();
1239    ///
1240    /// let first_element: Option<u32> = v_iter.next();
1241    ///
1242    /// assert_eq!(first_element, None);
1243    ///
1244    /// # Ok::<(), Error>(())
1245    /// ```
1246    #[inline]
1247    fn into_iter(self) -> Self::IntoIter {
1248        let buf = self.ptr;
1249        let layout = self.layout;
1250        let (ptr, len, _) = self.into_raw_parts();
1251
1252        IntoIter {
1253            ptr,
1254            buf,
1255            len,
1256            layout,
1257            _p: PhantomData::<A>,
1258        }
1259    }
1260}
1261
1262/// An iterator that owns all items in a vector, but does not own its allocation.
1263///
1264/// # Invariants
1265///
1266/// Every `&mut T` returned by the iterator references a `T` that the iterator may take ownership
1267/// of.
1268pub struct DrainAll<'vec, T> {
1269    elements: slice::IterMut<'vec, T>,
1270}
1271
1272impl<'vec, T> Iterator for DrainAll<'vec, T> {
1273    type Item = T;
1274
1275    fn next(&mut self) -> Option<T> {
1276        let elem: *mut T = self.elements.next()?;
1277        // SAFETY: By the type invariants, we may take ownership of this value.
1278        Some(unsafe { elem.read() })
1279    }
1280
1281    fn size_hint(&self) -> (usize, Option<usize>) {
1282        self.elements.size_hint()
1283    }
1284}
1285
1286impl<'vec, T> Drop for DrainAll<'vec, T> {
1287    fn drop(&mut self) {
1288        if core::mem::needs_drop::<T>() {
1289            let iter = core::mem::take(&mut self.elements);
1290            let ptr: *mut [T] = iter.into_slice();
1291            // SAFETY: By the type invariants, we own these values so we may destroy them.
1292            unsafe { ptr::drop_in_place(ptr) };
1293        }
1294    }
1295}
1296
1297#[macros::kunit_tests(rust_kvec_kunit)]
1298mod tests {
1299    use super::*;
1300    use crate::prelude::*;
1301
1302    #[test]
1303    fn test_kvec_retain() {
1304        /// Verify correctness for one specific function.
1305        #[expect(clippy::needless_range_loop)]
1306        fn verify(c: &[bool]) {
1307            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
1308            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
1309
1310            for i in 0..c.len() {
1311                vec1.push_within_capacity(i).unwrap();
1312                if c[i] {
1313                    vec2.push_within_capacity(i).unwrap();
1314                }
1315            }
1316
1317            vec1.retain(|i| c[*i]);
1318
1319            assert_eq!(vec1, vec2);
1320        }
1321
1322        /// Add one to a binary integer represented as a boolean array.
1323        fn add(value: &mut [bool]) {
1324            let mut carry = true;
1325            for v in value {
1326                let new_v = carry != *v;
1327                carry = carry && *v;
1328                *v = new_v;
1329            }
1330        }
1331
1332        // This boolean array represents a function from index to boolean. We check that `retain`
1333        // behaves correctly for all possible boolean arrays of every possible length less than
1334        // ten.
1335        let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap();
1336        for len in 0..10 {
1337            for _ in 0u32..1u32 << len {
1338                verify(&func);
1339                add(&mut func);
1340            }
1341            func.push_within_capacity(false).unwrap();
1342        }
1343    }
1344}