Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223// SPDX-License-Identifier: GPL-2.0
// Copyright (C) 2024 Google LLC.
//! A linked list implementation.
use crate::sync::ArcBorrow;use crate::types::Opaque;use core::iter::{DoubleEndedIterator, FusedIterator};use core::marker::PhantomData;use core::ptr;use pin_init::PinInit;
mod impl_list_item_mod;#[doc(inline)]pub use self::impl_list_item_mod::{ impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr, //};
mod arc;#[doc(inline)]pub use self::arc::{ impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc, //};
mod arc_field;#[doc(inline)]pub use self::arc_field::{ define_list_arc_field_getter, ListArcField, //};
/// A linked list.////// All elements in this linked list will be [`ListArc`] references to the value. Since a value can/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same/// prev/next pointers are not used for several linked lists.////// # Invariants////// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`/// field of the first element in the list./// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle./// * For every item in the list, the list owns the associated [`ListArc`] reference and has/// exclusive access to the `ListLinks` field.////// # Examples////// Use [`ListLinks`] as the type of the intrusive field.////// ```/// use kernel::list::*;////// #[pin_data]/// struct BasicItem {/// value: i32,/// #[pin]/// links: ListLinks,/// }////// impl BasicItem {/// fn new(value: i32) -> Result<ListArc<Self>> {/// ListArc::pin_init(try_pin_init!(Self {/// value,/// links <- ListLinks::new(),/// }), GFP_KERNEL)/// }/// }////// impl_list_arc_safe! {/// impl ListArcSafe<0> for BasicItem { untracked; }/// }/// impl_list_item! {/// impl ListItem<0> for BasicItem { using ListLinks { self.links }; }/// }////// // Create a new empty list./// let mut list = List::new();/// {/// assert!(list.is_empty());/// }////// // Insert 3 elements using `push_back()`./// list.push_back(BasicItem::new(15)?);/// list.push_back(BasicItem::new(10)?);/// list.push_back(BasicItem::new(30)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [15, 10, 30]/// {/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);/// assert!(iter.next().is_none());////// // Verify the length of the list./// assert_eq!(list.iter().count(), 3);/// }////// // Pop the items from the list using `pop_back()` and verify the content./// {/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);/// }////// // Insert 3 elements using `push_front()`./// list.push_front(BasicItem::new(15)?);/// list.push_front(BasicItem::new(10)?);/// list.push_front(BasicItem::new(30)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [30, 10, 15]/// {/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);/// assert!(iter.next().is_none());////// // Verify the length of the list./// assert_eq!(list.iter().count(), 3);/// }////// // Pop the items from the list using `pop_front()` and verify the content./// {/// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);/// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);/// }////// // Push `list2` to `list` through `push_all_back()`./// // list: [15]/// // list2: [25, 35]/// {/// let mut list2 = List::new();/// list2.push_back(BasicItem::new(25)?);/// list2.push_back(BasicItem::new(35)?);////// list.push_all_back(&mut list2);////// // list: [15, 25, 35]/// // list2: []/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 25);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 35);/// assert!(iter.next().is_none());/// assert!(list2.is_empty());/// }/// # Result::<(), Error>::Ok(())/// ```////// Use [`ListLinksSelfPtr`] as the type of the intrusive field. This allows a list of trait object/// type.////// ```/// use kernel::list::*;////// trait Foo {/// fn foo(&self) -> (&'static str, i32);/// }////// #[pin_data]/// struct DTWrap<T: ?Sized> {/// #[pin]/// links: ListLinksSelfPtr<DTWrap<dyn Foo>>,/// value: T,/// }////// impl<T> DTWrap<T> {/// fn new(value: T) -> Result<ListArc<Self>> {/// ListArc::pin_init(try_pin_init!(Self {/// value,/// links <- ListLinksSelfPtr::new(),/// }), GFP_KERNEL)/// }/// }////// impl_list_arc_safe! {/// impl{T: ?Sized} ListArcSafe<0> for DTWrap<T> { untracked; }/// }/// impl_list_item! {/// impl ListItem<0> for DTWrap<dyn Foo> { using ListLinksSelfPtr { self.links }; }/// }////// // Create a new empty list./// let mut list = List::<DTWrap<dyn Foo>>::new();/// {/// assert!(list.is_empty());/// }////// struct A(i32);/// // `A` returns the inner value for `foo`./// impl Foo for A { fn foo(&self) -> (&'static str, i32) { ("a", self.0) } }////// struct B;/// // `B` always returns 42./// impl Foo for B { fn foo(&self) -> (&'static str, i32) { ("b", 42) } }////// // Insert 3 element using `push_back()`./// list.push_back(DTWrap::new(A(15))?);/// list.push_back(DTWrap::new(A(32))?);/// list.push_back(DTWrap::new(B)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [A(15), A(32), B]/// {/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 15));/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));/// assert!(iter.next().is_none());////// // Verify the length of the list./// assert_eq!(list.iter().count(), 3);/// }////// // Pop the items from the list using `pop_back()` and verify the content./// {/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("b", 42));/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));/// }////// // Insert 3 elements using `push_front()`./// list.push_front(DTWrap::new(A(15))?);/// list.push_front(DTWrap::new(A(32))?);/// list.push_front(DTWrap::new(B)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [B, A(32), A(15)]/// {/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 15));/// assert!(iter.next().is_none());////// // Verify the length of the list./// assert_eq!(list.iter().count(), 3);/// }////// // Pop the items from the list using `pop_front()` and verify the content./// {/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));/// }////// // Push `list2` to `list` through `push_all_back()`./// // list: [B]/// // list2: [B, A(25)]/// {/// let mut list2 = List::<DTWrap<dyn Foo>>::new();/// list2.push_back(DTWrap::new(B)?);/// list2.push_back(DTWrap::new(A(25))?);////// list.push_all_back(&mut list2);////// // list: [B, B, A(25)]/// // list2: []/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));/// assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 25));/// assert!(iter.next().is_none());/// assert!(list2.is_empty());/// }/// # Result::<(), Error>::Ok(())/// ```pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { first: *mut ListLinksFields, _ty: PhantomData<ListArc<T, ID>>,}
// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same// type of access to the `ListArc<T, ID>` elements.unsafe impl<T, const ID: u64> Send for List<T, ID>where ListArc<T, ID>: Send, T: ?Sized + ListItem<ID>,{}// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same// type of access to the `ListArc<T, ID>` elements.unsafe impl<T, const ID: u64> Sync for List<T, ID>where ListArc<T, ID>: Sync, T: ?Sized + ListItem<ID>,{}
/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].////// # Safety////// Implementers must ensure that they provide the guarantees documented on methods provided by/// this trait.////// [`ListArc<Self>`]: ListArcpub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> { /// Views the [`ListLinks`] for this value. /// /// # Guarantees /// /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove` /// since the most recent such call, then this returns the same pointer as the one returned by /// the most recent call to `prepare_to_insert`. /// /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers. /// /// # Safety /// /// The provided pointer must point at a valid value. (It need not be in an `Arc`.) unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
/// View the full value given its [`ListLinks`] field. /// /// Can only be used when the value is in a list. /// /// # Guarantees /// /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`. /// * The returned pointer is valid until the next call to `post_remove`. /// /// # Safety /// /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or /// from a call to `view_links` that happened after the most recent call to /// `prepare_to_insert`. /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have /// been called. unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
/// This is called when an item is inserted into a [`List`]. /// /// # Guarantees /// /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is /// called. /// /// # Safety /// /// * The provided pointer must point at a valid value in an [`Arc`]. /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate. /// * The caller must own the [`ListArc`] for this value. /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been /// called after this call to `prepare_to_insert`. /// /// [`Arc`]: crate::sync::Arc unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
/// This undoes a previous call to `prepare_to_insert`. /// /// # Guarantees /// /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`. /// /// # Safety /// /// The provided pointer must be the pointer returned by the most recent call to /// `prepare_to_insert`. unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;}
#[repr(C)]#[derive(Copy, Clone)]struct ListLinksFields { next: *mut ListLinksFields, prev: *mut ListLinksFields,}
/// The prev/next pointers for an item in a linked list.////// # Invariants////// The fields are null if and only if this item is not in a list.#[repr(transparent)]pub struct ListLinks<const ID: u64 = 0> { // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked // list. inner: Opaque<ListLinksFields>,}
// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to// move this an instance of this type to a different thread if the pointees are `!Send`.unsafe impl<const ID: u64> Send for ListLinks<ID> {}// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's// okay to have immutable access to a ListLinks from several threads at once.unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
impl<const ID: u64> ListLinks<ID> { /// Creates a new initializer for this type. pub fn new() -> impl PinInit<Self> { // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will // not be constructed in an `Arc` that already has a `ListArc`. ListLinks { inner: Opaque::new(ListLinksFields { prev: ptr::null_mut(), next: ptr::null_mut(), }), } }
/// # Safety /// /// `me` must be dereferenceable. #[inline] unsafe fn fields(me: *mut Self) -> *mut ListLinksFields { // SAFETY: The caller promises that the pointer is valid. unsafe { Opaque::cast_into(ptr::addr_of!((*me).inner)) } }
/// # Safety /// /// `me` must be dereferenceable. #[inline] unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { me.cast() }}
/// Similar to [`ListLinks`], but also contains a pointer to the full value.////// This type can be used instead of [`ListLinks`] to support lists with trait objects.#[repr(C)]pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> { /// The `ListLinks` field inside this value. /// /// This is public so that it can be used with `impl_has_list_links!`. pub inner: ListLinks<ID>, // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and // `ptr::null()` doesn't work for `T: ?Sized`. self_ptr: Opaque<*const T>,}
// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,// it's okay to have immutable access to a ListLinks from several threads at once.//// Note that `inner` being a public field does not prevent this type from being opaque, since// `inner` is a opaque type.unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> { /// Creates a new initializer for this type. pub fn new() -> impl PinInit<Self> { // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will // not be constructed in an `Arc` that already has a `ListArc`. Self { inner: ListLinks { inner: Opaque::new(ListLinksFields { prev: ptr::null_mut(), next: ptr::null_mut(), }), }, self_ptr: Opaque::uninit(), } }
/// Returns a pointer to the self pointer. /// /// # Safety /// /// The provided pointer must point at a valid struct of type `Self`. pub unsafe fn raw_get_self_ptr(me: *const Self) -> *const Opaque<*const T> { // SAFETY: The caller promises that the pointer is valid. unsafe { ptr::addr_of!((*me).self_ptr) } }}
impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { /// Creates a new empty list. pub const fn new() -> Self { Self { first: ptr::null_mut(), _ty: PhantomData, } }
/// Returns whether this list is empty. pub fn is_empty(&self) -> bool { self.first.is_null() }
/// Inserts `item` before `next` in the cycle. /// /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list /// is empty. /// /// # Safety /// /// * `next` must be an element in this list or null. /// * if `next` is null, then the list must be empty. unsafe fn insert_inner( &mut self, item: ListArc<T, ID>, next: *mut ListLinksFields, ) -> *mut ListLinksFields { let raw_item = ListArc::into_raw(item); // SAFETY: // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. // * Since we have ownership of the `ListArc`, `post_remove` must have been called after // the most recent call to `prepare_to_insert`, if any. // * We own the `ListArc`. // * Removing items from this list is always done using `remove_internal_inner`, which // calls `post_remove` before giving up ownership. let list_links = unsafe { T::prepare_to_insert(raw_item) }; // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. let item = unsafe { ListLinks::fields(list_links) };
// Check if the list is empty. if next.is_null() { // SAFETY: The caller just gave us ownership of these fields. // INVARIANT: A linked list with one item should be cyclic. unsafe { (*item).next = item; (*item).prev = item; } self.first = item; } else { // SAFETY: By the type invariant, this pointer is valid or null. We just checked that // it's not null, so it must be valid. let prev = unsafe { (*next).prev }; // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us // ownership of the fields on `item`. // INVARIANT: This correctly inserts `item` between `prev` and `next`. unsafe { (*item).next = next; (*item).prev = prev; (*prev).next = item; (*next).prev = item; } }
item }
/// Add the provided item to the back of the list. pub fn push_back(&mut self, item: ListArc<T, ID>) { // SAFETY: // * `self.first` is null or in the list. // * `self.first` is only null if the list is empty. unsafe { self.insert_inner(item, self.first) }; }
/// Add the provided item to the front of the list. pub fn push_front(&mut self, item: ListArc<T, ID>) { // SAFETY: // * `self.first` is null or in the list. // * `self.first` is only null if the list is empty. let new_elem = unsafe { self.insert_inner(item, self.first) };
// INVARIANT: `new_elem` is in the list because we just inserted it. self.first = new_elem; }
/// Removes the last item from this list. pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> { if self.is_empty() { return None; }
// SAFETY: We just checked that the list is not empty. let last = unsafe { (*self.first).prev }; // SAFETY: The last item of this list is in this list. Some(unsafe { self.remove_internal(last) }) }
/// Removes the first item from this list. pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> { if self.is_empty() { return None; }
// SAFETY: The first item of this list is in this list. Some(unsafe { self.remove_internal(self.first) }) }
/// Removes the provided item from this list and returns it. /// /// This returns `None` if the item is not in the list. (Note that by the safety requirements, /// this means that the item is not in any list.) /// /// When using this method, be careful with using `mem::take` on the same list as that may /// result in violating the safety requirements of this method. /// /// # Safety /// /// `item` must not be in a different linked list (with the same id). pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> { // SAFETY: TODO. let mut item = unsafe { ListLinks::fields(T::view_links(item)) }; // SAFETY: The user provided a reference, and reference are never dangling. // // As for why this is not a data race, there are two cases: // // * If `item` is not in any list, then these fields are read-only and null. // * If `item` is in this list, then we have exclusive access to these fields since we // have a mutable reference to the list. // // In either case, there's no race. let ListLinksFields { next, prev } = unsafe { *item };
debug_assert_eq!(next.is_null(), prev.is_null()); if !next.is_null() { // This is really a no-op, but this ensures that `item` is a raw pointer that was // obtained without going through a pointer->reference->pointer conversion roundtrip. // This ensures that the list is valid under the more restrictive strict provenance // ruleset. // // SAFETY: We just checked that `next` is not null, and it's not dangling by the // list invariants. unsafe { debug_assert_eq!(item, (*next).prev); item = (*next).prev; }
// SAFETY: We just checked that `item` is in a list, so the caller guarantees that it // is in this list. The pointers are in the right order. Some(unsafe { self.remove_internal_inner(item, next, prev) }) } else { None } }
/// Removes the provided item from the list. /// /// # Safety /// /// `item` must point at an item in this list. unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> { // SAFETY: The caller promises that this pointer is not dangling, and there's no data race // since we have a mutable reference to the list containing `item`. let ListLinksFields { next, prev } = unsafe { *item }; // SAFETY: The pointers are ok and in the right order. unsafe { self.remove_internal_inner(item, next, prev) } }
/// Removes the provided item from the list. /// /// # Safety /// /// The `item` pointer must point at an item in this list, and we must have `(*item).next == /// next` and `(*item).prev == prev`. unsafe fn remove_internal_inner( &mut self, item: *mut ListLinksFields, next: *mut ListLinksFields, prev: *mut ListLinksFields, ) -> ListArc<T, ID> { // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next // pointers are always valid for items in a list. // // INVARIANT: There are three cases: // * If the list has at least three items, then after removing the item, `prev` and `next` // will be next to each other. // * If the list has two items, then the remaining item will point at itself. // * If the list has one item, then `next == prev == item`, so these writes have no // effect. The list remains unchanged and `item` is still in the list for now. unsafe { (*next).prev = prev; (*prev).next = next; } // SAFETY: We have exclusive access to items in the list. // INVARIANT: `item` is being removed, so the pointers should be null. unsafe { (*item).prev = ptr::null_mut(); (*item).next = ptr::null_mut(); } // INVARIANT: There are three cases: // * If `item` was not the first item, then `self.first` should remain unchanged. // * If `item` was the first item and there is another item, then we just updated // `prev->next` to `next`, which is the new first item, and setting `item->next` to null // did not modify `prev->next`. // * If `item` was the only item in the list, then `prev == item`, and we just set // `item->next` to null, so this correctly sets `first` to null now that the list is // empty. if self.first == item { // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this // list, so it must be valid. There is no race since `prev` is still in the list and we // still have exclusive access to the list. self.first = unsafe { (*prev).next }; }
// SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants // of `List`. let list_links = unsafe { ListLinks::from_fields(item) }; // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call. let raw_item = unsafe { T::post_remove(list_links) }; // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`. unsafe { ListArc::from_raw(raw_item) } }
/// Moves all items from `other` into `self`. /// /// The items of `other` are added to the back of `self`, so the last item of `other` becomes /// the last item of `self`. pub fn push_all_back(&mut self, other: &mut List<T, ID>) { // First, we insert the elements into `self`. At the end, we make `other` empty. if self.is_empty() { // INVARIANT: All of the elements in `other` become elements of `self`. self.first = other.first; } else if !other.is_empty() { let other_first = other.first; // SAFETY: The other list is not empty, so this pointer is valid. let other_last = unsafe { (*other_first).prev }; let self_first = self.first; // SAFETY: The self list is not empty, so this pointer is valid. let self_last = unsafe { (*self_first).prev };
// SAFETY: We have exclusive access to both lists, so we can update the pointers. // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to // update `self.first` because the first element of `self` does not change. unsafe { (*self_first).prev = other_last; (*other_last).next = self_first; (*self_last).next = other_first; (*other_first).prev = self_last; } }
// INVARIANT: The other list is now empty, so update its pointer. other.first = ptr::null_mut(); }
/// Returns a cursor that points before the first element of the list. pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> { // INVARIANT: `self.first` is in this list. Cursor { next: self.first, list: self, } }
/// Returns a cursor that points after the last element in the list. pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> { // INVARIANT: `next` is allowed to be null. Cursor { next: core::ptr::null_mut(), list: self, } }
/// Creates an iterator over the list. pub fn iter(&self) -> Iter<'_, T, ID> { // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point // at the first element of the same list. Iter { current: self.first, stop: self.first, _ty: PhantomData, } }}
impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> { fn default() -> Self { List::new() }}
impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> { fn drop(&mut self) { while let Some(item) = self.pop_front() { drop(item); } }}
/// An iterator over a [`List`].////// # Invariants////// * There must be a [`List`] that is immutably borrowed for the duration of `'a`./// * The `current` pointer is null or points at a value in that [`List`]./// * The `stop` pointer is equal to the `first` field of that [`List`].#[derive(Clone)]pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { current: *mut ListLinksFields, stop: *mut ListLinksFields, _ty: PhantomData<&'a ListArc<T, ID>>,}
impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> { type Item = ArcBorrow<'a, T>;
fn next(&mut self) -> Option<ArcBorrow<'a, T>> { if self.current.is_null() { return None; }
let current = self.current;
// SAFETY: We just checked that `current` is not null, so it is in a list, and hence not // dangling. There's no race because the iterator holds an immutable borrow to the list. let next = unsafe { (*current).next }; // INVARIANT: If `current` was the last element of the list, then this updates it to null. // Otherwise, we update it to the next element. self.current = if next != self.stop { next } else { ptr::null_mut() };
// SAFETY: The `current` pointer points at a value in the list. let item = unsafe { T::view_value(ListLinks::from_fields(current)) }; // SAFETY: // * All values in a list are stored in an `Arc`. // * The value cannot be removed from the list for the duration of the lifetime annotated // on the returned `ArcBorrow`, because removing it from the list would require mutable // access to the list. However, the `ArcBorrow` is annotated with the iterator's // lifetime, and the list is immutably borrowed for that lifetime. // * Values in a list never have a `UniqueArc` reference. Some(unsafe { ArcBorrow::from_raw(item) }) }}
/// A cursor into a [`List`].////// A cursor always rests between two elements in the list. This means that a cursor has a previous/// and next element, but no current element. It also means that it's possible to have a cursor/// into an empty list.////// # Examples////// ```/// use kernel::prelude::*;/// use kernel::list::{List, ListArc, ListLinks};////// #[pin_data]/// struct ListItem {/// value: u32,/// #[pin]/// links: ListLinks,/// }////// impl ListItem {/// fn new(value: u32) -> Result<ListArc<Self>> {/// ListArc::pin_init(try_pin_init!(Self {/// value,/// links <- ListLinks::new(),/// }), GFP_KERNEL)/// }/// }////// kernel::list::impl_list_arc_safe! {/// impl ListArcSafe<0> for ListItem { untracked; }/// }/// kernel::list::impl_list_item! {/// impl ListItem<0> for ListItem { using ListLinks { self.links }; }/// }////// // Use a cursor to remove the first element with the given value./// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {/// let mut cursor = list.cursor_front();/// while let Some(next) = cursor.peek_next() {/// if next.value == value {/// return Some(next.remove());/// }/// cursor.move_next();/// }/// None/// }////// // Use a cursor to remove the last element with the given value./// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {/// let mut cursor = list.cursor_back();/// while let Some(prev) = cursor.peek_prev() {/// if prev.value == value {/// return Some(prev.remove());/// }/// cursor.move_prev();/// }/// None/// }////// // Use a cursor to remove all elements with the given value. The removed elements are moved to/// // a new list./// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {/// let mut out = List::new();/// let mut cursor = list.cursor_front();/// while let Some(next) = cursor.peek_next() {/// if next.value == value {/// out.push_back(next.remove());/// } else {/// cursor.move_next();/// }/// }/// out/// }////// // Use a cursor to insert a value at a specific index. Returns an error if the index is out of/// // bounds./// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {/// let mut cursor = list.cursor_front();/// for _ in 0..idx {/// if !cursor.move_next() {/// return Err(EINVAL);/// }/// }/// cursor.insert_next(new);/// Ok(())/// }////// // Merge two sorted lists into a single sorted list./// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {/// let mut cursor = list.cursor_front();/// for to_insert in merge {/// while let Some(next) = cursor.peek_next() {/// if to_insert.value < next.value {/// break;/// }/// cursor.move_next();/// }/// cursor.insert_prev(to_insert);/// }/// }////// let mut list = List::new();/// list.push_back(ListItem::new(14)?);/// list.push_back(ListItem::new(12)?);/// list.push_back(ListItem::new(10)?);/// list.push_back(ListItem::new(12)?);/// list.push_back(ListItem::new(15)?);/// list.push_back(ListItem::new(14)?);/// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);/// // [14, 10, 15, 14]/// assert!(remove_first(&mut list, 14).is_some());/// // [10, 15, 14]/// insert_at(&mut list, ListItem::new(12)?, 2)?;/// // [10, 15, 12, 14]/// assert!(remove_last(&mut list, 15).is_some());/// // [10, 12, 14]////// let mut list2 = List::new();/// list2.push_back(ListItem::new(11)?);/// list2.push_back(ListItem::new(13)?);/// merge_sorted(&mut list, list2);////// let mut items = list.into_iter();/// assert_eq!(items.next().ok_or(EINVAL)?.value, 10);/// assert_eq!(items.next().ok_or(EINVAL)?.value, 11);/// assert_eq!(items.next().ok_or(EINVAL)?.value, 12);/// assert_eq!(items.next().ok_or(EINVAL)?.value, 13);/// assert_eq!(items.next().ok_or(EINVAL)?.value, 14);/// assert!(items.next().is_none());/// # Result::<(), Error>::Ok(())/// ```////// # Invariants////// The `next` pointer is null or points a value in `list`.pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { list: &'a mut List<T, ID>, /// Points at the element after this cursor, or null if the cursor is after the last element. next: *mut ListLinksFields,}
impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> { /// Returns a pointer to the element before the cursor. /// /// Returns null if there is no element before the cursor. fn prev_ptr(&self) -> *mut ListLinksFields { let mut next = self.next; let first = self.list.first; if next == first { // We are before the first element. return core::ptr::null_mut(); }
if next.is_null() { // We are after the last element, so we need a pointer to the last element, which is // the same as `(*first).prev`. next = first; }
// SAFETY: `next` can't be null, because then `first` must also be null, but in that case // we would have exited at the `next == first` check. Thus, `next` is an element in the // list, so we can access its `prev` pointer. unsafe { (*next).prev } }
/// Access the element after this cursor. pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> { if self.next.is_null() { return None; }
// INVARIANT: // * We just checked that `self.next` is non-null, so it must be in `self.list`. // * `ptr` is equal to `self.next`. Some(CursorPeek { ptr: self.next, cursor: self, }) }
/// Access the element before this cursor. pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> { let prev = self.prev_ptr();
if prev.is_null() { return None; }
// INVARIANT: // * We just checked that `prev` is non-null, so it must be in `self.list`. // * `self.prev_ptr()` never returns `self.next`. Some(CursorPeek { ptr: prev, cursor: self, }) }
/// Move the cursor one element forward. /// /// If the cursor is after the last element, then this call does nothing. This call returns /// `true` if the cursor's position was changed. pub fn move_next(&mut self) -> bool { if self.next.is_null() { return false; }
// SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can // access the `next` field. let mut next = unsafe { (*self.next).next };
if next == self.list.first { next = core::ptr::null_mut(); }
// INVARIANT: `next` is either null or the next element after an element in the list. self.next = next; true }
/// Move the cursor one element backwards. /// /// If the cursor is before the first element, then this call does nothing. This call returns /// `true` if the cursor's position was changed. pub fn move_prev(&mut self) -> bool { if self.next == self.list.first { return false; }
// INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list. self.next = self.prev_ptr(); true }
/// Inserts an element where the cursor is pointing and get a pointer to the new element. fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields { let ptr = if self.next.is_null() { self.list.first } else { self.next }; // SAFETY: // * `ptr` is an element in the list or null. // * if `ptr` is null, then `self.list.first` is null so the list is empty. let item = unsafe { self.list.insert_inner(item, ptr) }; if self.next == self.list.first { // INVARIANT: We just inserted `item`, so it's a member of list. self.list.first = item; } item }
/// Insert an element at this cursor's location. pub fn insert(mut self, item: ListArc<T, ID>) { // This is identical to `insert_prev`, but consumes the cursor. This is helpful because it // reduces confusion when the last operation on the cursor is an insertion; in that case, // you just want to insert the element at the cursor, and it is confusing that the call // involves the word prev or next. self.insert_inner(item); }
/// Inserts an element after this cursor. /// /// After insertion, the new element will be after the cursor. pub fn insert_next(&mut self, item: ListArc<T, ID>) { self.next = self.insert_inner(item); }
/// Inserts an element before this cursor. /// /// After insertion, the new element will be before the cursor. pub fn insert_prev(&mut self, item: ListArc<T, ID>) { self.insert_inner(item); }
/// Remove the next element from the list. pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> { self.peek_next().map(|v| v.remove()) }
/// Remove the previous element from the list. pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> { self.peek_prev().map(|v| v.remove()) }}
/// References the element in the list next to the cursor.////// # Invariants////// * `ptr` is an element in `self.cursor.list`./// * `ISNEXT == (self.ptr == self.cursor.next)`.pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> { cursor: &'a mut Cursor<'b, T, ID>, ptr: *mut ListLinksFields,}
impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> CursorPeek<'a, 'b, T, ISNEXT, ID>{ /// Remove the element from the list. pub fn remove(self) -> ListArc<T, ID> { if ISNEXT { self.cursor.move_next(); }
// INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next` // call. // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of // `self.cursor.list` by the type invariants of `Cursor`. unsafe { self.cursor.list.remove_internal(self.ptr) } }
/// Access this value as an [`ArcBorrow`]. pub fn arc(&self) -> ArcBorrow<'_, T> { // SAFETY: `self.ptr` points at an element in `self.cursor.list`. let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) }; // SAFETY: // * All values in a list are stored in an `Arc`. // * The value cannot be removed from the list for the duration of the lifetime annotated // on the returned `ArcBorrow`, because removing it from the list would require mutable // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds // an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable // access requires first releasing the immutable borrow on the `CursorPeek`. // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc` // reference, and `UniqueArc` references must be unique. unsafe { ArcBorrow::from_raw(me) } }}
impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref for CursorPeek<'a, 'b, T, ISNEXT, ID>{ // If you change the `ptr` field to have type `ArcBorrow<'a, T>`, it might seem like you could // get rid of the `CursorPeek::arc` method and change the deref target to `ArcBorrow<'a, T>`. // However, that doesn't work because 'a is too long. You could obtain an `ArcBorrow<'a, T>` // and then call `CursorPeek::remove` without giving up the `ArcBorrow<'a, T>`, which would be // unsound. type Target = T;
fn deref(&self) -> &T { // SAFETY: `self.ptr` points at an element in `self.cursor.list`. let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
// SAFETY: The value cannot be removed from the list for the duration of the lifetime // annotated on the returned `&T`, because removing it from the list would require mutable // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access // requires first releasing the immutable borrow on the `CursorPeek`. unsafe { &*me } }}
impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> { type IntoIter = Iter<'a, T, ID>; type Item = ArcBorrow<'a, T>;
fn into_iter(self) -> Iter<'a, T, ID> { self.iter() }}
/// An owning iterator into a [`List`].pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { list: List<T, ID>,}
impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> { type Item = ListArc<T, ID>;
fn next(&mut self) -> Option<ListArc<T, ID>> { self.list.pop_front() }}
impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> { fn next_back(&mut self) -> Option<ListArc<T, ID>> { self.list.pop_back() }}
impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> { type IntoIter = IntoIter<T, ID>; type Item = ListArc<T, ID>;
fn into_iter(self) -> IntoIter<T, ID> { IntoIter { list: self } }}