FILE
list.rs
File preview with syntax highlighting.
linux-6.19.14/rust/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 /// When using this method, be careful with using `mem::take` on the same list as that may 580 /// result in violating the safety requirements of this method. 581 /// 582 /// # Safety 583 /// 584 /// `item` must not be in a different linked list (with the same id). 585 pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> { 586 // SAFETY: TODO. 587 let mut item = unsafe { ListLinks::fields(T::view_links(item)) }; 588 // SAFETY: The user provided a reference, and reference are never dangling. 589 // 590 // As for why this is not a data race, there are two cases: 591 // 592 // * If `item` is not in any list, then these fields are read-only and null. 593 // * If `item` is in this list, then we have exclusive access to these fields since we 594 // have a mutable reference to the list. 595 // 596 // In either case, there's no race. 597 let ListLinksFields { next, prev } = unsafe { *item }; 598 599 debug_assert_eq!(next.is_null(), prev.is_null()); 600 if !next.is_null() { 601 // This is really a no-op, but this ensures that `item` is a raw pointer that was 602 // obtained without going through a pointer->reference->pointer conversion roundtrip. 603 // This ensures that the list is valid under the more restrictive strict provenance 604 // ruleset. 605 // 606 // SAFETY: We just checked that `next` is not null, and it's not dangling by the 607 // list invariants. 608 unsafe { 609 debug_assert_eq!(item, (*next).prev); 610 item = (*next).prev; 611 } 612 613 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it 614 // is in this list. The pointers are in the right order. 615 Some(unsafe { self.remove_internal_inner(item, next, prev) }) 616 } else { 617 None 618 } 619 } 620 621 /// Removes the provided item from the list. 622 /// 623 /// # Safety 624 /// 625 /// `item` must point at an item in this list. 626 unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> { 627 // SAFETY: The caller promises that this pointer is not dangling, and there's no data race 628 // since we have a mutable reference to the list containing `item`. 629 let ListLinksFields { next, prev } = unsafe { *item }; 630 // SAFETY: The pointers are ok and in the right order. 631 unsafe { self.remove_internal_inner(item, next, prev) } 632 } 633 634 /// Removes the provided item from the list. 635 /// 636 /// # Safety 637 /// 638 /// The `item` pointer must point at an item in this list, and we must have `(*item).next == 639 /// next` and `(*item).prev == prev`. 640 unsafe fn remove_internal_inner( 641 &mut self, 642 item: *mut ListLinksFields, 643 next: *mut ListLinksFields, 644 prev: *mut ListLinksFields, 645 ) -> ListArc<T, ID> { 646 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next 647 // pointers are always valid for items in a list. 648 // 649 // INVARIANT: There are three cases: 650 // * If the list has at least three items, then after removing the item, `prev` and `next` 651 // will be next to each other. 652 // * If the list has two items, then the remaining item will point at itself. 653 // * If the list has one item, then `next == prev == item`, so these writes have no 654 // effect. The list remains unchanged and `item` is still in the list for now. 655 unsafe { 656 (*next).prev = prev; 657 (*prev).next = next; 658 } 659 // SAFETY: We have exclusive access to items in the list. 660 // INVARIANT: `item` is being removed, so the pointers should be null. 661 unsafe { 662 (*item).prev = ptr::null_mut(); 663 (*item).next = ptr::null_mut(); 664 } 665 // INVARIANT: There are three cases: 666 // * If `item` was not the first item, then `self.first` should remain unchanged. 667 // * If `item` was the first item and there is another item, then we just updated 668 // `prev->next` to `next`, which is the new first item, and setting `item->next` to null 669 // did not modify `prev->next`. 670 // * If `item` was the only item in the list, then `prev == item`, and we just set 671 // `item->next` to null, so this correctly sets `first` to null now that the list is 672 // empty. 673 if self.first == item { 674 // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this 675 // list, so it must be valid. There is no race since `prev` is still in the list and we 676 // still have exclusive access to the list. 677 self.first = unsafe { (*prev).next }; 678 } 679 680 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants 681 // of `List`. 682 let list_links = unsafe { ListLinks::from_fields(item) }; 683 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call. 684 let raw_item = unsafe { T::post_remove(list_links) }; 685 // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`. 686 unsafe { ListArc::from_raw(raw_item) } 687 } 688 689 /// Moves all items from `other` into `self`. 690 /// 691 /// The items of `other` are added to the back of `self`, so the last item of `other` becomes 692 /// the last item of `self`. 693 pub fn push_all_back(&mut self, other: &mut List<T, ID>) { 694 // First, we insert the elements into `self`. At the end, we make `other` empty. 695 if self.is_empty() { 696 // INVARIANT: All of the elements in `other` become elements of `self`. 697 self.first = other.first; 698 } else if !other.is_empty() { 699 let other_first = other.first; 700 // SAFETY: The other list is not empty, so this pointer is valid. 701 let other_last = unsafe { (*other_first).prev }; 702 let self_first = self.first; 703 // SAFETY: The self list is not empty, so this pointer is valid. 704 let self_last = unsafe { (*self_first).prev }; 705 706 // SAFETY: We have exclusive access to both lists, so we can update the pointers. 707 // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to 708 // update `self.first` because the first element of `self` does not change. 709 unsafe { 710 (*self_first).prev = other_last; 711 (*other_last).next = self_first; 712 (*self_last).next = other_first; 713 (*other_first).prev = self_last; 714 } 715 } 716 717 // INVARIANT: The other list is now empty, so update its pointer. 718 other.first = ptr::null_mut(); 719 } 720 721 /// Returns a cursor that points before the first element of the list. 722 pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> { 723 // INVARIANT: `self.first` is in this list. 724 Cursor { 725 next: self.first, 726 list: self, 727 } 728 } 729 730 /// Returns a cursor that points after the last element in the list. 731 pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> { 732 // INVARIANT: `next` is allowed to be null. 733 Cursor { 734 next: core::ptr::null_mut(), 735 list: self, 736 } 737 } 738 739 /// Creates an iterator over the list. 740 pub fn iter(&self) -> Iter<'_, T, ID> { 741 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point 742 // at the first element of the same list. 743 Iter { 744 current: self.first, 745 stop: self.first, 746 _ty: PhantomData, 747 } 748 } 749} 750 751impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> { 752 fn default() -> Self { 753 List::new() 754 } 755} 756 757impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> { 758 fn drop(&mut self) { 759 while let Some(item) = self.pop_front() { 760 drop(item); 761 } 762 } 763} 764 765/// An iterator over a [`List`]. 766/// 767/// # Invariants 768/// 769/// * There must be a [`List`] that is immutably borrowed for the duration of `'a`. 770/// * The `current` pointer is null or points at a value in that [`List`]. 771/// * The `stop` pointer is equal to the `first` field of that [`List`]. 772#[derive(Clone)] 773pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { 774 current: *mut ListLinksFields, 775 stop: *mut ListLinksFields, 776 _ty: PhantomData<&'a ListArc<T, ID>>, 777} 778 779impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> { 780 type Item = ArcBorrow<'a, T>; 781 782 fn next(&mut self) -> Option<ArcBorrow<'a, T>> { 783 if self.current.is_null() { 784 return None; 785 } 786 787 let current = self.current; 788 789 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not 790 // dangling. There's no race because the iterator holds an immutable borrow to the list. 791 let next = unsafe { (*current).next }; 792 // INVARIANT: If `current` was the last element of the list, then this updates it to null. 793 // Otherwise, we update it to the next element. 794 self.current = if next != self.stop { 795 next 796 } else { 797 ptr::null_mut() 798 }; 799 800 // SAFETY: The `current` pointer points at a value in the list. 801 let item = unsafe { T::view_value(ListLinks::from_fields(current)) }; 802 // SAFETY: 803 // * All values in a list are stored in an `Arc`. 804 // * The value cannot be removed from the list for the duration of the lifetime annotated 805 // on the returned `ArcBorrow`, because removing it from the list would require mutable 806 // access to the list. However, the `ArcBorrow` is annotated with the iterator's 807 // lifetime, and the list is immutably borrowed for that lifetime. 808 // * Values in a list never have a `UniqueArc` reference. 809 Some(unsafe { ArcBorrow::from_raw(item) }) 810 } 811} 812 813/// A cursor into a [`List`]. 814/// 815/// A cursor always rests between two elements in the list. This means that a cursor has a previous 816/// and next element, but no current element. It also means that it's possible to have a cursor 817/// into an empty list. 818/// 819/// # Examples 820/// 821/// ``` 822/// use kernel::prelude::*; 823/// use kernel::list::{List, ListArc, ListLinks}; 824/// 825/// #[pin_data] 826/// struct ListItem { 827/// value: u32, 828/// #[pin] 829/// links: ListLinks, 830/// } 831/// 832/// impl ListItem { 833/// fn new(value: u32) -> Result<ListArc<Self>> { 834/// ListArc::pin_init(try_pin_init!(Self { 835/// value, 836/// links <- ListLinks::new(), 837/// }), GFP_KERNEL) 838/// } 839/// } 840/// 841/// kernel::list::impl_list_arc_safe! { 842/// impl ListArcSafe<0> for ListItem { untracked; } 843/// } 844/// kernel::list::impl_list_item! { 845/// impl ListItem<0> for ListItem { using ListLinks { self.links }; } 846/// } 847/// 848/// // Use a cursor to remove the first element with the given value. 849/// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> { 850/// let mut cursor = list.cursor_front(); 851/// while let Some(next) = cursor.peek_next() { 852/// if next.value == value { 853/// return Some(next.remove()); 854/// } 855/// cursor.move_next(); 856/// } 857/// None 858/// } 859/// 860/// // Use a cursor to remove the last element with the given value. 861/// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> { 862/// let mut cursor = list.cursor_back(); 863/// while let Some(prev) = cursor.peek_prev() { 864/// if prev.value == value { 865/// return Some(prev.remove()); 866/// } 867/// cursor.move_prev(); 868/// } 869/// None 870/// } 871/// 872/// // Use a cursor to remove all elements with the given value. The removed elements are moved to 873/// // a new list. 874/// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> { 875/// let mut out = List::new(); 876/// let mut cursor = list.cursor_front(); 877/// while let Some(next) = cursor.peek_next() { 878/// if next.value == value { 879/// out.push_back(next.remove()); 880/// } else { 881/// cursor.move_next(); 882/// } 883/// } 884/// out 885/// } 886/// 887/// // Use a cursor to insert a value at a specific index. Returns an error if the index is out of 888/// // bounds. 889/// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result { 890/// let mut cursor = list.cursor_front(); 891/// for _ in 0..idx { 892/// if !cursor.move_next() { 893/// return Err(EINVAL); 894/// } 895/// } 896/// cursor.insert_next(new); 897/// Ok(()) 898/// } 899/// 900/// // Merge two sorted lists into a single sorted list. 901/// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) { 902/// let mut cursor = list.cursor_front(); 903/// for to_insert in merge { 904/// while let Some(next) = cursor.peek_next() { 905/// if to_insert.value < next.value { 906/// break; 907/// } 908/// cursor.move_next(); 909/// } 910/// cursor.insert_prev(to_insert); 911/// } 912/// } 913/// 914/// let mut list = List::new(); 915/// list.push_back(ListItem::new(14)?); 916/// list.push_back(ListItem::new(12)?); 917/// list.push_back(ListItem::new(10)?); 918/// list.push_back(ListItem::new(12)?); 919/// list.push_back(ListItem::new(15)?); 920/// list.push_back(ListItem::new(14)?); 921/// assert_eq!(remove_all(&mut list, 12).iter().count(), 2); 922/// // [14, 10, 15, 14] 923/// assert!(remove_first(&mut list, 14).is_some()); 924/// // [10, 15, 14] 925/// insert_at(&mut list, ListItem::new(12)?, 2)?; 926/// // [10, 15, 12, 14] 927/// assert!(remove_last(&mut list, 15).is_some()); 928/// // [10, 12, 14] 929/// 930/// let mut list2 = List::new(); 931/// list2.push_back(ListItem::new(11)?); 932/// list2.push_back(ListItem::new(13)?); 933/// merge_sorted(&mut list, list2); 934/// 935/// let mut items = list.into_iter(); 936/// assert_eq!(items.next().ok_or(EINVAL)?.value, 10); 937/// assert_eq!(items.next().ok_or(EINVAL)?.value, 11); 938/// assert_eq!(items.next().ok_or(EINVAL)?.value, 12); 939/// assert_eq!(items.next().ok_or(EINVAL)?.value, 13); 940/// assert_eq!(items.next().ok_or(EINVAL)?.value, 14); 941/// assert!(items.next().is_none()); 942/// # Result::<(), Error>::Ok(()) 943/// ``` 944/// 945/// # Invariants 946/// 947/// The `next` pointer is null or points a value in `list`. 948pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { 949 list: &'a mut List<T, ID>, 950 /// Points at the element after this cursor, or null if the cursor is after the last element. 951 next: *mut ListLinksFields, 952} 953 954impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> { 955 /// Returns a pointer to the element before the cursor. 956 /// 957 /// Returns null if there is no element before the cursor. 958 fn prev_ptr(&self) -> *mut ListLinksFields { 959 let mut next = self.next; 960 let first = self.list.first; 961 if next == first { 962 // We are before the first element. 963 return core::ptr::null_mut(); 964 } 965 966 if next.is_null() { 967 // We are after the last element, so we need a pointer to the last element, which is 968 // the same as `(*first).prev`. 969 next = first; 970 } 971 972 // SAFETY: `next` can't be null, because then `first` must also be null, but in that case 973 // we would have exited at the `next == first` check. Thus, `next` is an element in the 974 // list, so we can access its `prev` pointer. 975 unsafe { (*next).prev } 976 } 977 978 /// Access the element after this cursor. 979 pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> { 980 if self.next.is_null() { 981 return None; 982 } 983 984 // INVARIANT: 985 // * We just checked that `self.next` is non-null, so it must be in `self.list`. 986 // * `ptr` is equal to `self.next`. 987 Some(CursorPeek { 988 ptr: self.next, 989 cursor: self, 990 }) 991 } 992 993 /// Access the element before this cursor. 994 pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> { 995 let prev = self.prev_ptr(); 996 997 if prev.is_null() { 998 return None; 999 } 1000 1001 // INVARIANT: 1002 // * We just checked that `prev` is non-null, so it must be in `self.list`. 1003 // * `self.prev_ptr()` never returns `self.next`. 1004 Some(CursorPeek { 1005 ptr: prev, 1006 cursor: self, 1007 }) 1008 } 1009 1010 /// Move the cursor one element forward. 1011 /// 1012 /// If the cursor is after the last element, then this call does nothing. This call returns 1013 /// `true` if the cursor's position was changed. 1014 pub fn move_next(&mut self) -> bool { 1015 if self.next.is_null() { 1016 return false; 1017 } 1018 1019 // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can 1020 // access the `next` field. 1021 let mut next = unsafe { (*self.next).next }; 1022 1023 if next == self.list.first { 1024 next = core::ptr::null_mut(); 1025 } 1026 1027 // INVARIANT: `next` is either null or the next element after an element in the list. 1028 self.next = next; 1029 true 1030 } 1031 1032 /// Move the cursor one element backwards. 1033 /// 1034 /// If the cursor is before the first element, then this call does nothing. This call returns 1035 /// `true` if the cursor's position was changed. 1036 pub fn move_prev(&mut self) -> bool { 1037 if self.next == self.list.first { 1038 return false; 1039 } 1040 1041 // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list. 1042 self.next = self.prev_ptr(); 1043 true 1044 } 1045 1046 /// Inserts an element where the cursor is pointing and get a pointer to the new element. 1047 fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields { 1048 let ptr = if self.next.is_null() { 1049 self.list.first 1050 } else { 1051 self.next 1052 }; 1053 // SAFETY: 1054 // * `ptr` is an element in the list or null. 1055 // * if `ptr` is null, then `self.list.first` is null so the list is empty. 1056 let item = unsafe { self.list.insert_inner(item, ptr) }; 1057 if self.next == self.list.first { 1058 // INVARIANT: We just inserted `item`, so it's a member of list. 1059 self.list.first = item; 1060 } 1061 item 1062 } 1063 1064 /// Insert an element at this cursor's location. 1065 pub fn insert(mut self, item: ListArc<T, ID>) { 1066 // This is identical to `insert_prev`, but consumes the cursor. This is helpful because it 1067 // reduces confusion when the last operation on the cursor is an insertion; in that case, 1068 // you just want to insert the element at the cursor, and it is confusing that the call 1069 // involves the word prev or next. 1070 self.insert_inner(item); 1071 } 1072 1073 /// Inserts an element after this cursor. 1074 /// 1075 /// After insertion, the new element will be after the cursor. 1076 pub fn insert_next(&mut self, item: ListArc<T, ID>) { 1077 self.next = self.insert_inner(item); 1078 } 1079 1080 /// Inserts an element before this cursor. 1081 /// 1082 /// After insertion, the new element will be before the cursor. 1083 pub fn insert_prev(&mut self, item: ListArc<T, ID>) { 1084 self.insert_inner(item); 1085 } 1086 1087 /// Remove the next element from the list. 1088 pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> { 1089 self.peek_next().map(|v| v.remove()) 1090 } 1091 1092 /// Remove the previous element from the list. 1093 pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> { 1094 self.peek_prev().map(|v| v.remove()) 1095 } 1096} 1097 1098/// References the element in the list next to the cursor. 1099/// 1100/// # Invariants 1101/// 1102/// * `ptr` is an element in `self.cursor.list`. 1103/// * `ISNEXT == (self.ptr == self.cursor.next)`. 1104pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> { 1105 cursor: &'a mut Cursor<'b, T, ID>, 1106 ptr: *mut ListLinksFields, 1107} 1108 1109impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> 1110 CursorPeek<'a, 'b, T, ISNEXT, ID> 1111{ 1112 /// Remove the element from the list. 1113 pub fn remove(self) -> ListArc<T, ID> { 1114 if ISNEXT { 1115 self.cursor.move_next(); 1116 } 1117 1118 // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next` 1119 // call. 1120 // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of 1121 // `self.cursor.list` by the type invariants of `Cursor`. 1122 unsafe { self.cursor.list.remove_internal(self.ptr) } 1123 } 1124 1125 /// Access this value as an [`ArcBorrow`]. 1126 pub fn arc(&self) -> ArcBorrow<'_, T> { 1127 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. 1128 let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) }; 1129 // SAFETY: 1130 // * All values in a list are stored in an `Arc`. 1131 // * The value cannot be removed from the list for the duration of the lifetime annotated 1132 // on the returned `ArcBorrow`, because removing it from the list would require mutable 1133 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds 1134 // an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the 1135 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable 1136 // access requires first releasing the immutable borrow on the `CursorPeek`. 1137 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc` 1138 // reference, and `UniqueArc` references must be unique. 1139 unsafe { ArcBorrow::from_raw(me) } 1140 } 1141} 1142 1143impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref 1144 for CursorPeek<'a, 'b, T, ISNEXT, ID> 1145{ 1146 // If you change the `ptr` field to have type `ArcBorrow<'a, T>`, it might seem like you could 1147 // get rid of the `CursorPeek::arc` method and change the deref target to `ArcBorrow<'a, T>`. 1148 // However, that doesn't work because 'a is too long. You could obtain an `ArcBorrow<'a, T>` 1149 // and then call `CursorPeek::remove` without giving up the `ArcBorrow<'a, T>`, which would be 1150 // unsound. 1151 type Target = T; 1152 1153 fn deref(&self) -> &T { 1154 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. 1155 let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) }; 1156 1157 // SAFETY: The value cannot be removed from the list for the duration of the lifetime 1158 // annotated on the returned `&T`, because removing it from the list would require mutable 1159 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an 1160 // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the 1161 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access 1162 // requires first releasing the immutable borrow on the `CursorPeek`. 1163 unsafe { &*me } 1164 } 1165} 1166 1167impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {} 1168 1169impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> { 1170 type IntoIter = Iter<'a, T, ID>; 1171 type Item = ArcBorrow<'a, T>; 1172 1173 fn into_iter(self) -> Iter<'a, T, ID> { 1174 self.iter() 1175 } 1176} 1177 1178/// An owning iterator into a [`List`]. 1179pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { 1180 list: List<T, ID>, 1181} 1182 1183impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> { 1184 type Item = ListArc<T, ID>; 1185 1186 fn next(&mut self) -> Option<ListArc<T, ID>> { 1187 self.list.pop_front() 1188 } 1189} 1190 1191impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {} 1192 1193impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> { 1194 fn next_back(&mut self) -> Option<ListArc<T, ID>> { 1195 self.list.pop_back() 1196 } 1197} 1198 1199impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> { 1200 type IntoIter = IntoIter<T, ID>; 1201 type Item = ListArc<T, ID>; 1202 1203 fn into_iter(self) -> IntoIter<T, ID> { 1204 IntoIter { list: self } 1205 } 1206}
~/
Read-only file preview.