kernel/
list.rs

1// SPDX-License-Identifier: GPL-2.0
2
3// Copyright (C) 2024 Google LLC.
4
5//! A linked list implementation.
6
7use crate::sync::ArcBorrow;
8use crate::types::Opaque;
9use core::iter::{DoubleEndedIterator, FusedIterator};
10use core::marker::PhantomData;
11use core::ptr;
12use pin_init::PinInit;
13
14mod impl_list_item_mod;
15pub use self::impl_list_item_mod::{
16    impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,
17};
18
19mod arc;
20pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc};
21
22mod arc_field;
23pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
24
25/// A linked list.
26///
27/// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
28/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same
29/// prev/next pointers are not used for several linked lists.
30///
31/// # Invariants
32///
33/// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
34///   field of the first element in the list.
35/// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
36/// * For every item in the list, the list owns the associated [`ListArc`] reference and has
37///   exclusive access to the `ListLinks` field.
38///
39/// # Examples
40///
41/// Use [`ListLinks`] as the type of the intrusive field.
42///
43/// ```
44/// use kernel::list::*;
45///
46/// #[pin_data]
47/// struct BasicItem {
48///     value: i32,
49///     #[pin]
50///     links: ListLinks,
51/// }
52///
53/// impl BasicItem {
54///     fn new(value: i32) -> Result<ListArc<Self>> {
55///         ListArc::pin_init(try_pin_init!(Self {
56///             value,
57///             links <- ListLinks::new(),
58///         }), GFP_KERNEL)
59///     }
60/// }
61///
62/// impl_list_arc_safe! {
63///     impl ListArcSafe<0> for BasicItem { untracked; }
64/// }
65/// impl_list_item! {
66///     impl ListItem<0> for BasicItem { using ListLinks { self.links }; }
67/// }
68///
69/// // Create a new empty list.
70/// let mut list = List::new();
71/// {
72///     assert!(list.is_empty());
73/// }
74///
75/// // Insert 3 elements using `push_back()`.
76/// list.push_back(BasicItem::new(15)?);
77/// list.push_back(BasicItem::new(10)?);
78/// list.push_back(BasicItem::new(30)?);
79///
80/// // Iterate over the list to verify the nodes were inserted correctly.
81/// // [15, 10, 30]
82/// {
83///     let mut iter = list.iter();
84///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
85///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
86///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
87///     assert!(iter.next().is_none());
88///
89///     // Verify the length of the list.
90///     assert_eq!(list.iter().count(), 3);
91/// }
92///
93/// // Pop the items from the list using `pop_back()` and verify the content.
94/// {
95///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);
96///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);
97///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);
98/// }
99///
100/// // Insert 3 elements using `push_front()`.
101/// list.push_front(BasicItem::new(15)?);
102/// list.push_front(BasicItem::new(10)?);
103/// list.push_front(BasicItem::new(30)?);
104///
105/// // Iterate over the list to verify the nodes were inserted correctly.
106/// // [30, 10, 15]
107/// {
108///     let mut iter = list.iter();
109///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
110///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
111///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
112///     assert!(iter.next().is_none());
113///
114///     // Verify the length of the list.
115///     assert_eq!(list.iter().count(), 3);
116/// }
117///
118/// // Pop the items from the list using `pop_front()` and verify the content.
119/// {
120///     assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);
121///     assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);
122/// }
123///
124/// // Push `list2` to `list` through `push_all_back()`.
125/// // list: [15]
126/// // list2: [25, 35]
127/// {
128///     let mut list2 = List::new();
129///     list2.push_back(BasicItem::new(25)?);
130///     list2.push_back(BasicItem::new(35)?);
131///
132///     list.push_all_back(&mut list2);
133///
134///     // list: [15, 25, 35]
135///     // list2: []
136///     let mut iter = list.iter();
137///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
138///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 25);
139///     assert_eq!(iter.next().ok_or(EINVAL)?.value, 35);
140///     assert!(iter.next().is_none());
141///     assert!(list2.is_empty());
142/// }
143/// # Result::<(), Error>::Ok(())
144/// ```
145///
146/// Use [`ListLinksSelfPtr`] as the type of the intrusive field. This allows a list of trait object
147/// type.
148///
149/// ```
150/// use kernel::list::*;
151///
152/// trait Foo {
153///     fn foo(&self) -> (&'static str, i32);
154/// }
155///
156/// #[pin_data]
157/// struct DTWrap<T: ?Sized> {
158///     #[pin]
159///     links: ListLinksSelfPtr<DTWrap<dyn Foo>>,
160///     value: T,
161/// }
162///
163/// impl<T> DTWrap<T> {
164///     fn new(value: T) -> Result<ListArc<Self>> {
165///         ListArc::pin_init(try_pin_init!(Self {
166///             value,
167///             links <- ListLinksSelfPtr::new(),
168///         }), GFP_KERNEL)
169///     }
170/// }
171///
172/// impl_list_arc_safe! {
173///     impl{T: ?Sized} ListArcSafe<0> for DTWrap<T> { untracked; }
174/// }
175/// impl_list_item! {
176///     impl ListItem<0> for DTWrap<dyn Foo> { using ListLinksSelfPtr { self.links }; }
177/// }
178///
179/// // Create a new empty list.
180/// let mut list = List::<DTWrap<dyn Foo>>::new();
181/// {
182///     assert!(list.is_empty());
183/// }
184///
185/// struct A(i32);
186/// // `A` returns the inner value for `foo`.
187/// impl Foo for A { fn foo(&self) -> (&'static str, i32) { ("a", self.0) } }
188///
189/// struct B;
190/// // `B` always returns 42.
191/// impl Foo for B { fn foo(&self) -> (&'static str, i32) { ("b", 42) } }
192///
193/// // Insert 3 element using `push_back()`.
194/// list.push_back(DTWrap::new(A(15))?);
195/// list.push_back(DTWrap::new(A(32))?);
196/// list.push_back(DTWrap::new(B)?);
197///
198/// // Iterate over the list to verify the nodes were inserted correctly.
199/// // [A(15), A(32), B]
200/// {
201///     let mut iter = list.iter();
202///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 15));
203///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));
204///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));
205///     assert!(iter.next().is_none());
206///
207///     // Verify the length of the list.
208///     assert_eq!(list.iter().count(), 3);
209/// }
210///
211/// // Pop the items from the list using `pop_back()` and verify the content.
212/// {
213///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("b", 42));
214///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));
215///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));
216/// }
217///
218/// // Insert 3 elements using `push_front()`.
219/// list.push_front(DTWrap::new(A(15))?);
220/// list.push_front(DTWrap::new(A(32))?);
221/// list.push_front(DTWrap::new(B)?);
222///
223/// // Iterate over the list to verify the nodes were inserted correctly.
224/// // [B, A(32), A(15)]
225/// {
226///     let mut iter = list.iter();
227///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));
228///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));
229///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 15));
230///     assert!(iter.next().is_none());
231///
232///     // Verify the length of the list.
233///     assert_eq!(list.iter().count(), 3);
234/// }
235///
236/// // Pop the items from the list using `pop_front()` and verify the content.
237/// {
238///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));
239///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));
240/// }
241///
242/// // Push `list2` to `list` through `push_all_back()`.
243/// // list: [B]
244/// // list2: [B, A(25)]
245/// {
246///     let mut list2 = List::<DTWrap<dyn Foo>>::new();
247///     list2.push_back(DTWrap::new(B)?);
248///     list2.push_back(DTWrap::new(A(25))?);
249///
250///     list.push_all_back(&mut list2);
251///
252///     // list: [B, B, A(25)]
253///     // list2: []
254///     let mut iter = list.iter();
255///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));
256///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));
257///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 25));
258///     assert!(iter.next().is_none());
259///     assert!(list2.is_empty());
260/// }
261/// # Result::<(), Error>::Ok(())
262/// ```
263pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
264    first: *mut ListLinksFields,
265    _ty: PhantomData<ListArc<T, ID>>,
266}
267
268// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
269// type of access to the `ListArc<T, ID>` elements.
270unsafe impl<T, const ID: u64> Send for List<T, ID>
271where
272    ListArc<T, ID>: Send,
273    T: ?Sized + ListItem<ID>,
274{
275}
276// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
277// type of access to the `ListArc<T, ID>` elements.
278unsafe impl<T, const ID: u64> Sync for List<T, ID>
279where
280    ListArc<T, ID>: Sync,
281    T: ?Sized + ListItem<ID>,
282{
283}
284
285/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
286///
287/// # Safety
288///
289/// Implementers must ensure that they provide the guarantees documented on methods provided by
290/// this trait.
291///
292/// [`ListArc<Self>`]: ListArc
293pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
294    /// Views the [`ListLinks`] for this value.
295    ///
296    /// # Guarantees
297    ///
298    /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove`
299    /// since the most recent such call, then this returns the same pointer as the one returned by
300    /// the most recent call to `prepare_to_insert`.
301    ///
302    /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers.
303    ///
304    /// # Safety
305    ///
306    /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
307    unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
308
309    /// View the full value given its [`ListLinks`] field.
310    ///
311    /// Can only be used when the value is in a list.
312    ///
313    /// # Guarantees
314    ///
315    /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`.
316    /// * The returned pointer is valid until the next call to `post_remove`.
317    ///
318    /// # Safety
319    ///
320    /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or
321    ///   from a call to `view_links` that happened after the most recent call to
322    ///   `prepare_to_insert`.
323    /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have
324    ///   been called.
325    unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
326
327    /// This is called when an item is inserted into a [`List`].
328    ///
329    /// # Guarantees
330    ///
331    /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is
332    /// called.
333    ///
334    /// # Safety
335    ///
336    /// * The provided pointer must point at a valid value in an [`Arc`].
337    /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate.
338    /// * The caller must own the [`ListArc`] for this value.
339    /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
340    ///   called after this call to `prepare_to_insert`.
341    ///
342    /// [`Arc`]: crate::sync::Arc
343    unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
344
345    /// This undoes a previous call to `prepare_to_insert`.
346    ///
347    /// # Guarantees
348    ///
349    /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
350    ///
351    /// # Safety
352    ///
353    /// The provided pointer must be the pointer returned by the most recent call to
354    /// `prepare_to_insert`.
355    unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;
356}
357
358#[repr(C)]
359#[derive(Copy, Clone)]
360struct ListLinksFields {
361    next: *mut ListLinksFields,
362    prev: *mut ListLinksFields,
363}
364
365/// The prev/next pointers for an item in a linked list.
366///
367/// # Invariants
368///
369/// The fields are null if and only if this item is not in a list.
370#[repr(transparent)]
371pub struct ListLinks<const ID: u64 = 0> {
372    // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked
373    // list.
374    inner: Opaque<ListLinksFields>,
375}
376
377// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
378// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
379// move this an instance of this type to a different thread if the pointees are `!Send`.
380unsafe impl<const ID: u64> Send for ListLinks<ID> {}
381// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
382// okay to have immutable access to a ListLinks from several threads at once.
383unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
384
385impl<const ID: u64> ListLinks<ID> {
386    /// Creates a new initializer for this type.
387    pub fn new() -> impl PinInit<Self> {
388        // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
389        // not be constructed in an `Arc` that already has a `ListArc`.
390        ListLinks {
391            inner: Opaque::new(ListLinksFields {
392                prev: ptr::null_mut(),
393                next: ptr::null_mut(),
394            }),
395        }
396    }
397
398    /// # Safety
399    ///
400    /// `me` must be dereferenceable.
401    #[inline]
402    unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
403        // SAFETY: The caller promises that the pointer is valid.
404        unsafe { Opaque::cast_into(ptr::addr_of!((*me).inner)) }
405    }
406
407    /// # Safety
408    ///
409    /// `me` must be dereferenceable.
410    #[inline]
411    unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
412        me.cast()
413    }
414}
415
416/// Similar to [`ListLinks`], but also contains a pointer to the full value.
417///
418/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
419#[repr(C)]
420pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
421    /// The `ListLinks` field inside this value.
422    ///
423    /// This is public so that it can be used with `impl_has_list_links!`.
424    pub inner: ListLinks<ID>,
425    // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and
426    // `ptr::null()` doesn't work for `T: ?Sized`.
427    self_ptr: Opaque<*const T>,
428}
429
430// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.
431unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
432// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,
433// it's okay to have immutable access to a ListLinks from several threads at once.
434//
435// Note that `inner` being a public field does not prevent this type from being opaque, since
436// `inner` is a opaque type.
437unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
438
439impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
440    /// Creates a new initializer for this type.
441    pub fn new() -> impl PinInit<Self> {
442        // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
443        // not be constructed in an `Arc` that already has a `ListArc`.
444        Self {
445            inner: ListLinks {
446                inner: Opaque::new(ListLinksFields {
447                    prev: ptr::null_mut(),
448                    next: ptr::null_mut(),
449                }),
450            },
451            self_ptr: Opaque::uninit(),
452        }
453    }
454
455    /// Returns a pointer to the self pointer.
456    ///
457    /// # Safety
458    ///
459    /// The provided pointer must point at a valid struct of type `Self`.
460    pub unsafe fn raw_get_self_ptr(me: *const Self) -> *const Opaque<*const T> {
461        // SAFETY: The caller promises that the pointer is valid.
462        unsafe { ptr::addr_of!((*me).self_ptr) }
463    }
464}
465
466impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
467    /// Creates a new empty list.
468    pub const fn new() -> Self {
469        Self {
470            first: ptr::null_mut(),
471            _ty: PhantomData,
472        }
473    }
474
475    /// Returns whether this list is empty.
476    pub fn is_empty(&self) -> bool {
477        self.first.is_null()
478    }
479
480    /// Inserts `item` before `next` in the cycle.
481    ///
482    /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
483    /// is empty.
484    ///
485    /// # Safety
486    ///
487    /// * `next` must be an element in this list or null.
488    /// * if `next` is null, then the list must be empty.
489    unsafe fn insert_inner(
490        &mut self,
491        item: ListArc<T, ID>,
492        next: *mut ListLinksFields,
493    ) -> *mut ListLinksFields {
494        let raw_item = ListArc::into_raw(item);
495        // SAFETY:
496        // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
497        // * Since we have ownership of the `ListArc`, `post_remove` must have been called after
498        //   the most recent call to `prepare_to_insert`, if any.
499        // * We own the `ListArc`.
500        // * Removing items from this list is always done using `remove_internal_inner`, which
501        //   calls `post_remove` before giving up ownership.
502        let list_links = unsafe { T::prepare_to_insert(raw_item) };
503        // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
504        let item = unsafe { ListLinks::fields(list_links) };
505
506        // Check if the list is empty.
507        if next.is_null() {
508            // SAFETY: The caller just gave us ownership of these fields.
509            // INVARIANT: A linked list with one item should be cyclic.
510            unsafe {
511                (*item).next = item;
512                (*item).prev = item;
513            }
514            self.first = item;
515        } else {
516            // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
517            // it's not null, so it must be valid.
518            let prev = unsafe { (*next).prev };
519            // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
520            // ownership of the fields on `item`.
521            // INVARIANT: This correctly inserts `item` between `prev` and `next`.
522            unsafe {
523                (*item).next = next;
524                (*item).prev = prev;
525                (*prev).next = item;
526                (*next).prev = item;
527            }
528        }
529
530        item
531    }
532
533    /// Add the provided item to the back of the list.
534    pub fn push_back(&mut self, item: ListArc<T, ID>) {
535        // SAFETY:
536        // * `self.first` is null or in the list.
537        // * `self.first` is only null if the list is empty.
538        unsafe { self.insert_inner(item, self.first) };
539    }
540
541    /// Add the provided item to the front of the list.
542    pub fn push_front(&mut self, item: ListArc<T, ID>) {
543        // SAFETY:
544        // * `self.first` is null or in the list.
545        // * `self.first` is only null if the list is empty.
546        let new_elem = unsafe { self.insert_inner(item, self.first) };
547
548        // INVARIANT: `new_elem` is in the list because we just inserted it.
549        self.first = new_elem;
550    }
551
552    /// Removes the last item from this list.
553    pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
554        if self.is_empty() {
555            return None;
556        }
557
558        // SAFETY: We just checked that the list is not empty.
559        let last = unsafe { (*self.first).prev };
560        // SAFETY: The last item of this list is in this list.
561        Some(unsafe { self.remove_internal(last) })
562    }
563
564    /// Removes the first item from this list.
565    pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> {
566        if self.is_empty() {
567            return None;
568        }
569
570        // SAFETY: The first item of this list is in this list.
571        Some(unsafe { self.remove_internal(self.first) })
572    }
573
574    /// Removes the provided item from this list and returns it.
575    ///
576    /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
577    /// this means that the item is not in any list.)
578    ///
579    /// # Safety
580    ///
581    /// `item` must not be in a different linked list (with the same id).
582    pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
583        // SAFETY: TODO.
584        let mut item = unsafe { ListLinks::fields(T::view_links(item)) };
585        // SAFETY: The user provided a reference, and reference are never dangling.
586        //
587        // As for why this is not a data race, there are two cases:
588        //
589        //  * If `item` is not in any list, then these fields are read-only and null.
590        //  * If `item` is in this list, then we have exclusive access to these fields since we
591        //    have a mutable reference to the list.
592        //
593        // In either case, there's no race.
594        let ListLinksFields { next, prev } = unsafe { *item };
595
596        debug_assert_eq!(next.is_null(), prev.is_null());
597        if !next.is_null() {
598            // This is really a no-op, but this ensures that `item` is a raw pointer that was
599            // obtained without going through a pointer->reference->pointer conversion roundtrip.
600            // This ensures that the list is valid under the more restrictive strict provenance
601            // ruleset.
602            //
603            // SAFETY: We just checked that `next` is not null, and it's not dangling by the
604            // list invariants.
605            unsafe {
606                debug_assert_eq!(item, (*next).prev);
607                item = (*next).prev;
608            }
609
610            // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
611            // is in this list. The pointers are in the right order.
612            Some(unsafe { self.remove_internal_inner(item, next, prev) })
613        } else {
614            None
615        }
616    }
617
618    /// Removes the provided item from the list.
619    ///
620    /// # Safety
621    ///
622    /// `item` must point at an item in this list.
623    unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
624        // SAFETY: The caller promises that this pointer is not dangling, and there's no data race
625        // since we have a mutable reference to the list containing `item`.
626        let ListLinksFields { next, prev } = unsafe { *item };
627        // SAFETY: The pointers are ok and in the right order.
628        unsafe { self.remove_internal_inner(item, next, prev) }
629    }
630
631    /// Removes the provided item from the list.
632    ///
633    /// # Safety
634    ///
635    /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
636    /// next` and `(*item).prev == prev`.
637    unsafe fn remove_internal_inner(
638        &mut self,
639        item: *mut ListLinksFields,
640        next: *mut ListLinksFields,
641        prev: *mut ListLinksFields,
642    ) -> ListArc<T, ID> {
643        // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next
644        // pointers are always valid for items in a list.
645        //
646        // INVARIANT: There are three cases:
647        //  * If the list has at least three items, then after removing the item, `prev` and `next`
648        //    will be next to each other.
649        //  * If the list has two items, then the remaining item will point at itself.
650        //  * If the list has one item, then `next == prev == item`, so these writes have no
651        //    effect. The list remains unchanged and `item` is still in the list for now.
652        unsafe {
653            (*next).prev = prev;
654            (*prev).next = next;
655        }
656        // SAFETY: We have exclusive access to items in the list.
657        // INVARIANT: `item` is being removed, so the pointers should be null.
658        unsafe {
659            (*item).prev = ptr::null_mut();
660            (*item).next = ptr::null_mut();
661        }
662        // INVARIANT: There are three cases:
663        //  * If `item` was not the first item, then `self.first` should remain unchanged.
664        //  * If `item` was the first item and there is another item, then we just updated
665        //    `prev->next` to `next`, which is the new first item, and setting `item->next` to null
666        //    did not modify `prev->next`.
667        //  * If `item` was the only item in the list, then `prev == item`, and we just set
668        //    `item->next` to null, so this correctly sets `first` to null now that the list is
669        //    empty.
670        if self.first == item {
671            // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this
672            // list, so it must be valid. There is no race since `prev` is still in the list and we
673            // still have exclusive access to the list.
674            self.first = unsafe { (*prev).next };
675        }
676
677        // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants
678        // of `List`.
679        let list_links = unsafe { ListLinks::from_fields(item) };
680        // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.
681        let raw_item = unsafe { T::post_remove(list_links) };
682        // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`.
683        unsafe { ListArc::from_raw(raw_item) }
684    }
685
686    /// Moves all items from `other` into `self`.
687    ///
688    /// The items of `other` are added to the back of `self`, so the last item of `other` becomes
689    /// the last item of `self`.
690    pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
691        // First, we insert the elements into `self`. At the end, we make `other` empty.
692        if self.is_empty() {
693            // INVARIANT: All of the elements in `other` become elements of `self`.
694            self.first = other.first;
695        } else if !other.is_empty() {
696            let other_first = other.first;
697            // SAFETY: The other list is not empty, so this pointer is valid.
698            let other_last = unsafe { (*other_first).prev };
699            let self_first = self.first;
700            // SAFETY: The self list is not empty, so this pointer is valid.
701            let self_last = unsafe { (*self_first).prev };
702
703            // SAFETY: We have exclusive access to both lists, so we can update the pointers.
704            // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
705            // update `self.first` because the first element of `self` does not change.
706            unsafe {
707                (*self_first).prev = other_last;
708                (*other_last).next = self_first;
709                (*self_last).next = other_first;
710                (*other_first).prev = self_last;
711            }
712        }
713
714        // INVARIANT: The other list is now empty, so update its pointer.
715        other.first = ptr::null_mut();
716    }
717
718    /// Returns a cursor that points before the first element of the list.
719    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
720        // INVARIANT: `self.first` is in this list.
721        Cursor {
722            next: self.first,
723            list: self,
724        }
725    }
726
727    /// Returns a cursor that points after the last element in the list.
728    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
729        // INVARIANT: `next` is allowed to be null.
730        Cursor {
731            next: core::ptr::null_mut(),
732            list: self,
733        }
734    }
735
736    /// Creates an iterator over the list.
737    pub fn iter(&self) -> Iter<'_, T, ID> {
738        // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point
739        // at the first element of the same list.
740        Iter {
741            current: self.first,
742            stop: self.first,
743            _ty: PhantomData,
744        }
745    }
746}
747
748impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {
749    fn default() -> Self {
750        List::new()
751    }
752}
753
754impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
755    fn drop(&mut self) {
756        while let Some(item) = self.pop_front() {
757            drop(item);
758        }
759    }
760}
761
762/// An iterator over a [`List`].
763///
764/// # Invariants
765///
766/// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
767/// * The `current` pointer is null or points at a value in that [`List`].
768/// * The `stop` pointer is equal to the `first` field of that [`List`].
769#[derive(Clone)]
770pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
771    current: *mut ListLinksFields,
772    stop: *mut ListLinksFields,
773    _ty: PhantomData<&'a ListArc<T, ID>>,
774}
775
776impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
777    type Item = ArcBorrow<'a, T>;
778
779    fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
780        if self.current.is_null() {
781            return None;
782        }
783
784        let current = self.current;
785
786        // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not
787        // dangling. There's no race because the iterator holds an immutable borrow to the list.
788        let next = unsafe { (*current).next };
789        // INVARIANT: If `current` was the last element of the list, then this updates it to null.
790        // Otherwise, we update it to the next element.
791        self.current = if next != self.stop {
792            next
793        } else {
794            ptr::null_mut()
795        };
796
797        // SAFETY: The `current` pointer points at a value in the list.
798        let item = unsafe { T::view_value(ListLinks::from_fields(current)) };
799        // SAFETY:
800        // * All values in a list are stored in an `Arc`.
801        // * The value cannot be removed from the list for the duration of the lifetime annotated
802        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
803        //   access to the list. However, the `ArcBorrow` is annotated with the iterator's
804        //   lifetime, and the list is immutably borrowed for that lifetime.
805        // * Values in a list never have a `UniqueArc` reference.
806        Some(unsafe { ArcBorrow::from_raw(item) })
807    }
808}
809
810/// A cursor into a [`List`].
811///
812/// A cursor always rests between two elements in the list. This means that a cursor has a previous
813/// and next element, but no current element. It also means that it's possible to have a cursor
814/// into an empty list.
815///
816/// # Examples
817///
818/// ```
819/// use kernel::prelude::*;
820/// use kernel::list::{List, ListArc, ListLinks};
821///
822/// #[pin_data]
823/// struct ListItem {
824///     value: u32,
825///     #[pin]
826///     links: ListLinks,
827/// }
828///
829/// impl ListItem {
830///     fn new(value: u32) -> Result<ListArc<Self>> {
831///         ListArc::pin_init(try_pin_init!(Self {
832///             value,
833///             links <- ListLinks::new(),
834///         }), GFP_KERNEL)
835///     }
836/// }
837///
838/// kernel::list::impl_list_arc_safe! {
839///     impl ListArcSafe<0> for ListItem { untracked; }
840/// }
841/// kernel::list::impl_list_item! {
842///     impl ListItem<0> for ListItem { using ListLinks { self.links }; }
843/// }
844///
845/// // Use a cursor to remove the first element with the given value.
846/// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
847///     let mut cursor = list.cursor_front();
848///     while let Some(next) = cursor.peek_next() {
849///         if next.value == value {
850///             return Some(next.remove());
851///         }
852///         cursor.move_next();
853///     }
854///     None
855/// }
856///
857/// // Use a cursor to remove the last element with the given value.
858/// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
859///     let mut cursor = list.cursor_back();
860///     while let Some(prev) = cursor.peek_prev() {
861///         if prev.value == value {
862///             return Some(prev.remove());
863///         }
864///         cursor.move_prev();
865///     }
866///     None
867/// }
868///
869/// // Use a cursor to remove all elements with the given value. The removed elements are moved to
870/// // a new list.
871/// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
872///     let mut out = List::new();
873///     let mut cursor = list.cursor_front();
874///     while let Some(next) = cursor.peek_next() {
875///         if next.value == value {
876///             out.push_back(next.remove());
877///         } else {
878///             cursor.move_next();
879///         }
880///     }
881///     out
882/// }
883///
884/// // Use a cursor to insert a value at a specific index. Returns an error if the index is out of
885/// // bounds.
886/// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
887///     let mut cursor = list.cursor_front();
888///     for _ in 0..idx {
889///         if !cursor.move_next() {
890///             return Err(EINVAL);
891///         }
892///     }
893///     cursor.insert_next(new);
894///     Ok(())
895/// }
896///
897/// // Merge two sorted lists into a single sorted list.
898/// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
899///     let mut cursor = list.cursor_front();
900///     for to_insert in merge {
901///         while let Some(next) = cursor.peek_next() {
902///             if to_insert.value < next.value {
903///                 break;
904///             }
905///             cursor.move_next();
906///         }
907///         cursor.insert_prev(to_insert);
908///     }
909/// }
910///
911/// let mut list = List::new();
912/// list.push_back(ListItem::new(14)?);
913/// list.push_back(ListItem::new(12)?);
914/// list.push_back(ListItem::new(10)?);
915/// list.push_back(ListItem::new(12)?);
916/// list.push_back(ListItem::new(15)?);
917/// list.push_back(ListItem::new(14)?);
918/// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
919/// // [14, 10, 15, 14]
920/// assert!(remove_first(&mut list, 14).is_some());
921/// // [10, 15, 14]
922/// insert_at(&mut list, ListItem::new(12)?, 2)?;
923/// // [10, 15, 12, 14]
924/// assert!(remove_last(&mut list, 15).is_some());
925/// // [10, 12, 14]
926///
927/// let mut list2 = List::new();
928/// list2.push_back(ListItem::new(11)?);
929/// list2.push_back(ListItem::new(13)?);
930/// merge_sorted(&mut list, list2);
931///
932/// let mut items = list.into_iter();
933/// assert_eq!(items.next().ok_or(EINVAL)?.value, 10);
934/// assert_eq!(items.next().ok_or(EINVAL)?.value, 11);
935/// assert_eq!(items.next().ok_or(EINVAL)?.value, 12);
936/// assert_eq!(items.next().ok_or(EINVAL)?.value, 13);
937/// assert_eq!(items.next().ok_or(EINVAL)?.value, 14);
938/// assert!(items.next().is_none());
939/// # Result::<(), Error>::Ok(())
940/// ```
941///
942/// # Invariants
943///
944/// The `next` pointer is null or points a value in `list`.
945pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
946    list: &'a mut List<T, ID>,
947    /// Points at the element after this cursor, or null if the cursor is after the last element.
948    next: *mut ListLinksFields,
949}
950
951impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
952    /// Returns a pointer to the element before the cursor.
953    ///
954    /// Returns null if there is no element before the cursor.
955    fn prev_ptr(&self) -> *mut ListLinksFields {
956        let mut next = self.next;
957        let first = self.list.first;
958        if next == first {
959            // We are before the first element.
960            return core::ptr::null_mut();
961        }
962
963        if next.is_null() {
964            // We are after the last element, so we need a pointer to the last element, which is
965            // the same as `(*first).prev`.
966            next = first;
967        }
968
969        // SAFETY: `next` can't be null, because then `first` must also be null, but in that case
970        // we would have exited at the `next == first` check. Thus, `next` is an element in the
971        // list, so we can access its `prev` pointer.
972        unsafe { (*next).prev }
973    }
974
975    /// Access the element after this cursor.
976    pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> {
977        if self.next.is_null() {
978            return None;
979        }
980
981        // INVARIANT:
982        // * We just checked that `self.next` is non-null, so it must be in `self.list`.
983        // * `ptr` is equal to `self.next`.
984        Some(CursorPeek {
985            ptr: self.next,
986            cursor: self,
987        })
988    }
989
990    /// Access the element before this cursor.
991    pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> {
992        let prev = self.prev_ptr();
993
994        if prev.is_null() {
995            return None;
996        }
997
998        // INVARIANT:
999        // * We just checked that `prev` is non-null, so it must be in `self.list`.
1000        // * `self.prev_ptr()` never returns `self.next`.
1001        Some(CursorPeek {
1002            ptr: prev,
1003            cursor: self,
1004        })
1005    }
1006
1007    /// Move the cursor one element forward.
1008    ///
1009    /// If the cursor is after the last element, then this call does nothing. This call returns
1010    /// `true` if the cursor's position was changed.
1011    pub fn move_next(&mut self) -> bool {
1012        if self.next.is_null() {
1013            return false;
1014        }
1015
1016        // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can
1017        // access the `next` field.
1018        let mut next = unsafe { (*self.next).next };
1019
1020        if next == self.list.first {
1021            next = core::ptr::null_mut();
1022        }
1023
1024        // INVARIANT: `next` is either null or the next element after an element in the list.
1025        self.next = next;
1026        true
1027    }
1028
1029    /// Move the cursor one element backwards.
1030    ///
1031    /// If the cursor is before the first element, then this call does nothing. This call returns
1032    /// `true` if the cursor's position was changed.
1033    pub fn move_prev(&mut self) -> bool {
1034        if self.next == self.list.first {
1035            return false;
1036        }
1037
1038        // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list.
1039        self.next = self.prev_ptr();
1040        true
1041    }
1042
1043    /// Inserts an element where the cursor is pointing and get a pointer to the new element.
1044    fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields {
1045        let ptr = if self.next.is_null() {
1046            self.list.first
1047        } else {
1048            self.next
1049        };
1050        // SAFETY:
1051        // * `ptr` is an element in the list or null.
1052        // * if `ptr` is null, then `self.list.first` is null so the list is empty.
1053        let item = unsafe { self.list.insert_inner(item, ptr) };
1054        if self.next == self.list.first {
1055            // INVARIANT: We just inserted `item`, so it's a member of list.
1056            self.list.first = item;
1057        }
1058        item
1059    }
1060
1061    /// Insert an element at this cursor's location.
1062    pub fn insert(mut self, item: ListArc<T, ID>) {
1063        // This is identical to `insert_prev`, but consumes the cursor. This is helpful because it
1064        // reduces confusion when the last operation on the cursor is an insertion; in that case,
1065        // you just want to insert the element at the cursor, and it is confusing that the call
1066        // involves the word prev or next.
1067        self.insert_inner(item);
1068    }
1069
1070    /// Inserts an element after this cursor.
1071    ///
1072    /// After insertion, the new element will be after the cursor.
1073    pub fn insert_next(&mut self, item: ListArc<T, ID>) {
1074        self.next = self.insert_inner(item);
1075    }
1076
1077    /// Inserts an element before this cursor.
1078    ///
1079    /// After insertion, the new element will be before the cursor.
1080    pub fn insert_prev(&mut self, item: ListArc<T, ID>) {
1081        self.insert_inner(item);
1082    }
1083
1084    /// Remove the next element from the list.
1085    pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> {
1086        self.peek_next().map(|v| v.remove())
1087    }
1088
1089    /// Remove the previous element from the list.
1090    pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> {
1091        self.peek_prev().map(|v| v.remove())
1092    }
1093}
1094
1095/// References the element in the list next to the cursor.
1096///
1097/// # Invariants
1098///
1099/// * `ptr` is an element in `self.cursor.list`.
1100/// * `ISNEXT == (self.ptr == self.cursor.next)`.
1101pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> {
1102    cursor: &'a mut Cursor<'b, T, ID>,
1103    ptr: *mut ListLinksFields,
1104}
1105
1106impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64>
1107    CursorPeek<'a, 'b, T, ISNEXT, ID>
1108{
1109    /// Remove the element from the list.
1110    pub fn remove(self) -> ListArc<T, ID> {
1111        if ISNEXT {
1112            self.cursor.move_next();
1113        }
1114
1115        // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next`
1116        // call.
1117        // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of
1118        // `self.cursor.list` by the type invariants of `Cursor`.
1119        unsafe { self.cursor.list.remove_internal(self.ptr) }
1120    }
1121
1122    /// Access this value as an [`ArcBorrow`].
1123    pub fn arc(&self) -> ArcBorrow<'_, T> {
1124        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
1125        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
1126        // SAFETY:
1127        // * All values in a list are stored in an `Arc`.
1128        // * The value cannot be removed from the list for the duration of the lifetime annotated
1129        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
1130        //   access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds
1131        //   an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
1132        //   `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable
1133        //   access requires first releasing the immutable borrow on the `CursorPeek`.
1134        // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
1135        //   reference, and `UniqueArc` references must be unique.
1136        unsafe { ArcBorrow::from_raw(me) }
1137    }
1138}
1139
1140impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref
1141    for CursorPeek<'a, 'b, T, ISNEXT, ID>
1142{
1143    // If you change the `ptr` field to have type `ArcBorrow<'a, T>`, it might seem like you could
1144    // get rid of the `CursorPeek::arc` method and change the deref target to `ArcBorrow<'a, T>`.
1145    // However, that doesn't work because 'a is too long. You could obtain an `ArcBorrow<'a, T>`
1146    // and then call `CursorPeek::remove` without giving up the `ArcBorrow<'a, T>`, which would be
1147    // unsound.
1148    type Target = T;
1149
1150    fn deref(&self) -> &T {
1151        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
1152        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
1153
1154        // SAFETY: The value cannot be removed from the list for the duration of the lifetime
1155        // annotated on the returned `&T`, because removing it from the list would require mutable
1156        // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an
1157        // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
1158        // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access
1159        // requires first releasing the immutable borrow on the `CursorPeek`.
1160        unsafe { &*me }
1161    }
1162}
1163
1164impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
1165
1166impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {
1167    type IntoIter = Iter<'a, T, ID>;
1168    type Item = ArcBorrow<'a, T>;
1169
1170    fn into_iter(self) -> Iter<'a, T, ID> {
1171        self.iter()
1172    }
1173}
1174
1175/// An owning iterator into a [`List`].
1176pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
1177    list: List<T, ID>,
1178}
1179
1180impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {
1181    type Item = ListArc<T, ID>;
1182
1183    fn next(&mut self) -> Option<ListArc<T, ID>> {
1184        self.list.pop_front()
1185    }
1186}
1187
1188impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
1189
1190impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {
1191    fn next_back(&mut self) -> Option<ListArc<T, ID>> {
1192        self.list.pop_back()
1193    }
1194}
1195
1196impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {
1197    type IntoIter = IntoIter<T, ID>;
1198    type Item = ListArc<T, ID>;
1199
1200    fn into_iter(self) -> IntoIter<T, ID> {
1201        IntoIter { list: self }
1202    }
1203}