projects/linux·blob uaccess-cleanups · refs

1222 lines · 43.6 KiB

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