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}