1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863
//! A generic trait based interface for abstracting over various schemes for //! concurrent memory reclamation. //! //! # Memory Management in Rust //! //! Unlike garbage collected languages such as *Go* or *Java*, memory //! management in *Rust* is primarily scope or ownership based and more akin to //! *C++*. //! Rust's ownership model in combination with the standard library's smart //! pointer types `Box`, `Rc` and `Arc` make memory management as painless as //! possible and are able to handle the vast majority of use-cases, while at the //! same time preventing the classic memory bugs such as *use-after-free*, //! *double-free* or memory leaks. //! Consequently, there is usually little need for the relatively small //! additional comfort provided by a fully automated **Garbage Collector** (GC). //! //! ## The Need for Automatic Memory Reclamation //! //! In the domain of concurrent lock-free data structures, however, the //! aforementioned memory management schemes are insufficient for determining, //! when a removed entry can be actually dropped and de-allocated: //! Just because an entry has been removed (*unlinked*) from some shared data //! structure does not guarantee, that no other thread could still be in the //! process of reading that same entry at the same time. //! This is due to the possible existence of stale references that were created //! by other threads before the unlinking occurred. //! The only fact that can be ascertained, due to nature of atomic *swap* and //! *compare-and-swap* operations, is that other threads can not acquire *new* //! references after an entry has been unlinked. //! //! ## Extending the Grace Period //! //! Concurrent memory reclamation schemes work by granting every value //! (*record*) earmarked for deletion (*retired*) a certain **grace period** //! before being actually dropped and de-allocated. //! During this period the value will be cached and can still be safely read by //! other threads with live references to it, but no new references must be //! possible. //! Determining the exact length of this grace period is up to each individual //! reclamation scheme. //! It is usually either not possible or not practical to determine the exact //! moment at which it becomes safe to reclaim a retired. //! Hence, reclamation schemes commonly tend to only guarantee grace periods //! that are *at least* as long as to ensure no references can possibly exist //! afterwards. //! //! # The Reclaim Interface //! //! Lock-free data structures are usually required to work on atomic pointers to //! heap allocated memory. //! This is due to the restrictions of atomic CPU instructions to machine-word //! sized values, such as pointers. //! Working with raw pointers is inherently *unsafe* in the Rust sense. //! Consequently, this crate avoids and discourages the use of raw pointers as //! much as possible in favor of safer abstractions with stricter constraints //! for their usage. //! In effect, the vast majority of this crate's public API is safe to use under //! any circumstances. //! This, however, is achieved by shifting and concentrating the burden of //! manually maintaining safety invariants into one specific key aspect: //! The retiring (and eventual reclamation) of records. //! //! ## Traits and Types //! //! The `reclaim` crate primarily exposes four different traits, which are //! relevant for users of generic code and implementors of reclamation schemes //! alike. //! The first trait is [`Reclaim`], which provides generic functionality for //! retiring records. //! Note, that this trait does not presume the presence of an operating system //! and functionality like thread local storage. //! Hence, this trait can even be used in `#[no_std]` environments. //! However, in order to use this trait's associated methods, an explicit //! reference to the current thread's (local) state is required. //! For environments with implicit access to thread local storage, the //! [`GlobalReclaim`] trait exists as an extension to [`Reclaim`]. //! This trait additionally requires an associated type //! [`Guard`][GlobalReclaim::Guard], which must implement both the [`Default`] //! and the [`Protect`] trait. //! //! Types implementing the [`Protect`] trait can be used to safely read values //! from shared memory that are subsequently safe from concurrent reclamation //! and can hence be safely de-referenced. //! Note that a single guard can only protect one value at a time. //! This follows the design of many reclamation schemes, such as *hazard //! pointers*. //! This is represented by the requirement to pass a *mutable* reference to a //! guard in order to safely load a shared value. //! //! Some reclamation schemes (e.g. epoch based ones) do not require individual //! protection of values, but instead protect arbitrary numbers of shared at //! once. //! The guard types for these schemes can additionally implement the //! [`ProtectRegion`] trait. //! Such guards do not have to carry any state and protect values simply by //! their existence. //! Consequently, it is also possible to call eg [`Atomic::load`] with a shared //! reference to a guard implementing that trait. //! //! ## The `Atomic` Type //! //! The [`Atomic`] markable concurrent pointer type is the main point of //! interaction with this crate. //! It can only be safely created as a `null` pointer or with valid heap //! allocation backing it up. //! It supports all common atomic operations like `load`, `store`, //! `compare_exchange`, etc. //! The key aspect of this type is that together with a guard, shared values //! can be safely loaded and de-referenced while other threads can concurrently //! reclaim removed values. //! In addition to the [`Shared`] type, which represents a shared reference that //! is protected from reclamation, other atomic operations can yield //! [`Unprotected`] or [`Unlinked`] values. //! The former are explicitly not protected from reclamation and can be loaded //! without any guards. //! They are not safe to de-reference, but can be used to e.g. swing a pointer //! from one linked list node to another. //! [`Unlinked`] values are the result of *swap* or *compare-and-swap* //! operations and represent values/references to which no new references can be //! acquired any more by other threads. //! They are like *owned* values that are also borrowed, since other threads may //! still reference them. //! All of these three different types are guaranteed to never be null at the //! type level. //! //! ## Marked Pointer & Reference Types //! //! It is a ubiquitous technique in lock-free programming to use the lower bits //! of a pointer address to store additional information alongside an address. //! Common use-cases are ABA problem mitigation or to mark a node of a linked //! list for removal. //! //! Accordingly, this crate allows all pointer and reference types //! ([`MarkedPtr`], [`Shared`], etc.) to be marked. //! The number of usable mark bits is encoded in the type itself as a generic //! parameter `N`. //! However, the number of available mark bits has a physical upper bound, which //! is dictated by the alignment of the pointed-to type. //! For instance, a `bool` has an alignment of 1, hence pointers to boolean //! values can not, in fact, be marked. //! On a 64-bit system, an `usize` has an alignment of 8, which means a pointer //! to one can use up to 3 mark bits. //! Since the number `N` is encoded in the pointer types themselves, attempting //! to declare types with more available mark bits than what the pointed-to //! type's alignment will lead to a (currently fairly cryptic) compile time //! error. //! Note, that tags are allowed to overflow. This can lead to surprising results //! when attempting to e.g. mark a pointer that is declared to support zero mark //! bits (`N = 0`), as the tag will be silently truncated. //! //! # Terminology //! //! Throughout this crate's API and its documentation a certain terminology is //! consistently used, which is summarized below: //! //! - record //! //! A heap allocated value which is managed by some reclamation scheme. //! //! - unlink //! //! The act removing the pointer to a *record* from shared memory through an //! atomic operation such as *compare-and-swap*. //! //! - retire //! //! The act of marking an *unlinked* record as no longer in use and handing //! off the responsibility for de-allocation to the reclamation scheme. //! //! - reclaim //! //! The act of dropping and de-allocating a *retired* record. //! The reclamation scheme is responsible for guaranteeing that *retired* //! records are kept alive (cached) **at least** until their respective *grace //! periods* have expired. #![cfg_attr(not(any(test, feature = "std")), no_std)] #![warn(missing_docs)] #[cfg(not(feature = "std"))] extern crate alloc; #[macro_use] mod macros; pub mod align; pub mod leak; pub mod prelude { //! Useful and/or required types, discriminants and traits for the `reclaim` //! crate. pub use crate::pointer::{ Marked::{self, Null, Value}, MarkedPointer, NonNullable, }; pub use crate::GlobalReclaim; pub use crate::Protect; pub use crate::ProtectRegion; pub use crate::Reclaim; } mod atomic; mod internal; mod owned; mod pointer; mod retired; mod shared; mod unlinked; mod unprotected; #[cfg(feature = "std")] use std::error::Error; use core::fmt; use core::marker::PhantomData; use core::mem; use core::ptr::NonNull; use core::sync::atomic::Ordering; // TODO: replace with const generics once available pub use typenum; use memoffset::offset_of; use typenum::Unsigned; pub use crate::atomic::{Atomic, CompareExchangeFailure}; pub use crate::pointer::{ AtomicMarkedPtr, InvalidNullError, Marked, MarkedNonNull, MarkedPointer, MarkedPtr, NonNullable, }; pub use crate::retired::Retired; //////////////////////////////////////////////////////////////////////////////////////////////////// // GlobalReclaim (trait) //////////////////////////////////////////////////////////////////////////////////////////////////// /// A trait for retiring and reclaiming entries removed from concurrent /// collections and data structures. /// /// Implementing this trait requires first implementing the [`Reclaim`] /// trait for the same type and is usually only possible in `std` environments /// with access to thread local storage. /// /// # Examples /// /// Defining a concurrent data structure generic over the employed reclamation /// scheme: /// /// ``` /// use reclaim::typenum::U0; /// use reclaim::GlobalReclaim; /// /// type Atomic<T, R> = reclaim::Atomic<T, R, U0>; /// /// pub struct Stack<T, R: GlobalReclaim> { /// head: Atomic<Node<T, R>, R>, /// } /// /// struct Node<T, R: GlobalReclaim> { /// elem: T, /// next: Atomic<Node<T, R>, R>, /// } /// ``` pub unsafe trait GlobalReclaim where Self: Reclaim, { /// The type used for protecting concurrently shared references. type Guard: Protect<Reclaimer = Self> + Default; /// Creates a new [`Guard`][GlobalReclaim::Guard]. /// /// When `Self::Guard` implements [`ProtectRegion`], this operation /// instantly establishes protection for loaded values. /// Otherwise, the guard must first explicitly protect a specific shared /// value. fn guard() -> Self::Guard { Self::Guard::default() } /// Attempts to safely reclaim some retired records. /// /// Retired records are often cached locally by each thread to some /// extent. /// In cases, where opportunities for reclaiming these records (usually /// actions requiring protection of shared values) materialize only rarely, /// this function can be used to initiate the (safe) reclamation manually. fn try_flush(); /// Retires a record and caches it **at least** until it is safe to /// deallocate it. /// /// For further information, refer to the documentation of /// [`retire_local`][`Reclaim::retire_local`]. /// /// # Safety /// /// The same caveats as with [`retire_local`][`LocalReclaim::retire_local`] /// apply. unsafe fn retire<T: 'static, N: Unsigned>(unlinked: Unlinked<T, Self, N>); /// Retires a record and caches it **at least** until it is safe to /// deallocate it. /// /// For further information, refer to the documentation of /// [`retire_local_unchecked`][`Reclaim::retire_local_unchecked`]. /// /// # Safety /// /// The same caveats as with [`retire_local`][`Reclaim::retire_local`] /// apply. unsafe fn retire_unchecked<T, N: Unsigned>(unlinked: Unlinked<T, Self, N>); /// Retires a raw marked pointer to a record. /// /// # Safety /// /// The same caveats as with [`retire_local_raw`][`Reclaim::retire_local_raw`] /// apply. /// /// # Panics /// /// In debug mode, this function panics if `ptr` is `null`. unsafe fn retire_raw<T, N: Unsigned>(ptr: MarkedPtr<T, N>) { debug_assert!(!ptr.is_null()); Self::retire_unchecked(Unlinked::from_marked_ptr(ptr)); } } //////////////////////////////////////////////////////////////////////////////////////////////////// // Reclaim (trait) //////////////////////////////////////////////////////////////////////////////////////////////////// /// A trait, which constitutes the foundation for the [`GlobalReclaim`] trait. /// /// This trait is specifically intended to be fully compatible with `#[no_std]` /// environments. /// This is expressed by the requirement to explicitly pass references to thread /// local state or storage when calling functions that retire records. /// /// If a reclamation scheme does not require or deliberately chooses to avoid /// using thread local storage for the sake of simplicity or portability /// (usually at the cost of performance), it is valid to implement `Self::Local` /// as `()` and pass all retired records directly through to some global state. /// Note, that this will generally require more and also more frequent /// synchronization. /// For cases in which `Local` is defined to be `()`, there exists a blanket /// implementation of [`GlobalReclaim]. pub unsafe trait Reclaim where Self: Sized + 'static, { /// The type used for storing all relevant thread local state. type Local: Sized; /// Every record allocates this type alongside itself to store additional /// reclamation scheme specific data. /// When no such data is required, `()` is the recommended choice. type RecordHeader: Default + Sync + Sized; /// Retires a record and caches it **at least** until it is safe to /// deallocate it. /// /// How to determine that no other thread can possibly have any (protected) /// reference to a record depends on the respective reclamation scheme. /// /// # Safety /// /// The caller has to guarantee that the record is **fully** unlinked from /// any data structure it was previously inserted in: /// There must be no way for another thread to acquire a *new* reference to /// the given `unlinked` record. /// /// While an [`Unlinked`] value can only safely be obtained by atomic /// operations that do in fact remove a value from its place in memory (i.e. /// *swap* or *compare-and-swap*), this is only the *necessary* condition /// for safe reclamation, but not always *sufficient*. /// When a unique address to heap allocated memory is inserted in more than /// one element of a shared data structure, it is still possible for other /// threads to access this address even if its unlinked from one spot. /// /// This invariant also mandates, that correct synchronization of atomic /// operations around calls to functions that retire records is ensured. /// Consider the following (incorrect) example: /// /// ```ignore /// # use core::sync::atomic::Ordering::{Relaxed}; /// # use reclaim::Unlinked; /// /// let g = Atomic::from(Owned::new(1)); /// /// // thread 1 /// let expected = g.load_unprotected(Relaxed); // reads &1 /// let unlinked = g /// .compare_exchange(expected, Owned::null(), Relaxed, Relaxed) /// .unwrap(); /// /// unsafe { unlinked.retire() }; /// /// // thread 2 /// if let Some(shared) = g.load(Relaxed, &mut guard) { /// assert_eq!(*shared, &1); // !!! may read freed memory /// } /// ``` /// /// In this example, the invariant can not be guaranteed to be maintained, /// due to the incorrect (relaxed) memory orderings. /// Thread 1 can potentially unlink the shared value, retire and reclaim it, /// without the `compare_exchange` operation ever becoming visible to /// thread 2. /// The thread could then proceed to load and read the previous /// value instead of the inserted `null`, accessing freed memory. unsafe fn retire_local<T: 'static, N: Unsigned>( local: &Self::Local, unlinked: Unlinked<T, Self, N>, ); /// Retires a record and caches it **at least** until it is safe to /// deallocate it. /// /// How to determine that no other thread can possibly have any (protected) /// reference to a record depends on the respective reclamation scheme. /// /// # Safety /// /// The same restrictions as with the [`retire_local`][Reclaim::retire_local] /// function apply here as well. /// /// In addition to these invariants, this method additionally requires the /// caller to ensure any `Drop` implementation for `T` or any contained type /// does not access any **non-static** references. /// The `reclaim` interface makes no guarantees about the precise time a /// retired record is actually reclaimed. /// Hence, it is not possible to ensure any references stored within the /// record have not become invalid at that point. unsafe fn retire_local_unchecked<T, N: Unsigned>( local: &Self::Local, unlinked: Unlinked<T, Self, N>, ); /// Retires a raw marked pointer to a record. /// /// # Safety /// /// The same restrictions as with [`retire_local_unchecked`][Reclaim::retire_local_unchecked] /// apply. /// Since this function accepts a raw pointer, no type level checks on the validity are possible /// and are hence the responsibility of the caller. /// /// # Panics /// /// In debug mode, this function panics if `ptr` is `null`. unsafe fn retire_local_raw<T, N: Unsigned>(local: &Self::Local, ptr: MarkedPtr<T, N>) { debug_assert!(!ptr.is_null()); Self::retire_local_unchecked(local, Unlinked::from_marked_ptr(ptr)); } } //////////////////////////////////////////////////////////////////////////////////////////////////// // Protect (trait) //////////////////////////////////////////////////////////////////////////////////////////////////// /// A trait for guard types that *protect* a specific value from reclamation /// during the lifetime of the protecting guard. /// /// # Examples /// /// ``` /// use core::sync::atomic::Ordering::Relaxed; /// /// use reclaim::typenum::U0; /// use reclaim::prelude::*; /// // `Leaking` implements both `Protect` and `ProtectRegion` /// use reclaim::leak::Guard; /// /// type Atomic<T> = reclaim::leak::Atomic<T, U0>; /// /// let atomic = Atomic::new(1); /// /// let mut guard = Guard::new(); /// let shared = atomic.load(Relaxed, &mut guard).unwrap(); /// assert_eq!(&*shared, &1); /// ``` pub unsafe trait Protect where Self: Clone + Sized, { /// The reclamation scheme associated with this type of guard type Reclaimer: Reclaim; /// Converts the guard into a [`Guarded`] by fusing it with a value loaded /// from `atomic`. /// /// # Errors /// /// If the value loaded from `atomic` is `null`, this method instead `self` /// again, wrapped in an [`Err`]. #[inline] fn try_fuse<T, N: Unsigned>( mut self, atomic: &Atomic<T, Self::Reclaimer, N>, order: Ordering, ) -> Result<Guarded<T, Self, N>, Self> { if let Marked::Value(shared) = self.protect(atomic, order) { let ptr = Shared::into_marked_non_null(shared); Ok(Guarded { guard: self, ptr }) } else { Err(self) } } /// Releases any current protection that may be provided by the guard. /// /// By borrowing `self` mutably it is ensured that no loaded values /// protected by this guard can be used after calling this method. /// If `Self` additionally implements [`ProtectRegion`], this is a no-op fn release(&mut self); /// Atomically takes a snapshot of `atomic` and returns a protected /// [`Shared`] reference wrapped in a [`Marked`] to it. /// /// The loaded value is stored within `self`. If the value of `atomic` is /// `null` or a pure tag (marked `null` pointer), no protection has to be /// established. Any previously protected value will be overwritten and be /// no longer protected, regardless of the loaded value. /// /// # Panics /// /// *May* panic if `order` is [`Release`][release] or [`AcqRel`][acq_rel]. /// /// [release]: core::sync::atomic::Ordering::Release /// [acq_rel]: core::sync::atomic::Ordering::AcqRel fn protect<T, N: Unsigned>( &mut self, atomic: &Atomic<T, Self::Reclaimer, N>, order: Ordering, ) -> Marked<Shared<T, Self::Reclaimer, N>>; /// Atomically takes a snapshot of `atomic` and returns a protected /// [`Shared`] reference wrapped in a [`Marked`] to it, **if** the loaded /// value is equal to `expected`. /// /// A *successfully* loaded value is stored within `self`. If the value of /// `atomic` is `null` or a pure tag (marked `null` pointer), no protection /// has to be established. After a *successful* load, any previously /// protected value will be overwritten and be no longer protected, /// regardless of the loaded value. In case of a unsuccessful load, the /// previously protected value does not change. /// /// # Errors /// /// This method returns an [`Err(NotEqualError)`][NotEqualError] result, if /// the atomically loaded snapshot from `atomic` does not match the /// `expected` value. /// /// # Panics /// /// *May* panic if `order` is [`Release`][release] or [`AcqRel`][acq_rel]. /// /// [release]: core::sync::atomic::Ordering::Release /// [acq_rel]: core::sync::atomic::Ordering::AcqRel fn protect_if_equal<T, N: Unsigned>( &mut self, atomic: &Atomic<T, Self::Reclaimer, N>, expected: MarkedPtr<T, N>, order: Ordering, ) -> AcquireResult<T, Self::Reclaimer, N>; } //////////////////////////////////////////////////////////////////////////////////////////////////// // ProtectRegion (trait) //////////////////////////////////////////////////////////////////////////////////////////////////// /// A trait for guard types that protect any values loaded during their /// existence and lifetime. /// /// # Examples /// /// ``` /// use core::sync::atomic::Ordering::Relaxed; /// /// use reclaim::typenum::U0; /// use reclaim::prelude::*; /// // `Leaking` implements both `Protect` and `ProtectRegion` /// use reclaim::leak::Guard; /// /// type Atomic<T> = reclaim::leak::Atomic<T, U0>; /// /// let atomic = Atomic::new(1); /// let other = Atomic::new(0); /// /// let guard = Guard::new(); /// let shared1 = atomic.load(Relaxed, &guard).unwrap(); /// let shared0 = other.load(Relaxed, &guard).unwrap(); /// assert_eq!(&*shared1, &1); /// assert_eq!(&*shared0, &0); /// ``` pub unsafe trait ProtectRegion where Self: Protect, { } //////////////////////////////////////////////////////////////////////////////////////////////////// // AcquireResult //////////////////////////////////////////////////////////////////////////////////////////////////// /// Result type for [`acquire_if_equal`][Protect::acquire_if_equal] operations. pub type AcquireResult<'g, T, R, N> = Result<Marked<Shared<'g, T, R, N>>, NotEqualError>; //////////////////////////////////////////////////////////////////////////////////////////////////// // NotEqualError //////////////////////////////////////////////////////////////////////////////////////////////////// /// A zero-size marker type that represents the failure state of an /// [`acquire_if_equal`][Protect::acquire_if_equal] operation. #[derive(Clone, Copy, Debug, Default, Eq, Ord, PartialEq, PartialOrd)] pub struct NotEqualError; impl fmt::Display for NotEqualError { #[inline] fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "acquired value does not match `expected`.") } } #[cfg(feature = "std")] impl Error for NotEqualError {} //////////////////////////////////////////////////////////////////////////////////////////////////// // Record //////////////////////////////////////////////////////////////////////////////////////////////////// /// A record type that is associated with a specific reclamation scheme. /// /// Whenever a new [`Owned`] or (non-null) [`Atomic`] is created, a value of /// this type is allocated on the heap as a wrapper for the desired record. /// The record and its header are never directly exposed to the data structure /// using a given memory reclamation scheme and should only be accessed by the /// reclamation scheme itself. pub struct Record<T, R: Reclaim> { /// The record's header header: R::RecordHeader, /// The record's wrapped (inner) element elem: T, } impl<T, R: Reclaim> Record<T, R> { /// Creates a new record with the specified `elem` and a default header. #[inline] pub fn new(elem: T) -> Self { Self { header: Default::default(), elem } } /// Creates a new record with the specified `elem` and `header`. #[inline] pub fn with_header(elem: T, header: R::RecordHeader) -> Self { Self { header, elem } } /// Returns a reference to the record's header. #[inline] pub fn header(&self) -> &R::RecordHeader { &self.header } /// Returns a reference to the record's element. #[inline] pub fn elem(&self) -> &T { &self.elem } /// Calculates the address of the [`Record`] for the given pointer to a /// wrapped non-nullable `elem` and returns the resulting pointer. /// /// # Safety /// /// The `elem` pointer must be a valid pointer to an instance of `T` that /// was constructed as part of a [`Record`]. Otherwise, the pointer /// arithmetic used to determine the address will result in a pointer to /// unrelated memory, which is likely to lead to undefined behaviour. #[inline] pub unsafe fn from_raw_non_null(elem: NonNull<T>) -> NonNull<Self> { Self::from_raw(elem.as_ptr()) } /// Calculates the address of the [`Record`] for the given pointer to a /// wrapped `elem` and returns the resulting pointer. /// /// # Safety /// /// The `elem` pointer must be a valid pointer to an instance of `T` that /// was constructed as part of a [`Record`]. Otherwise, the pointer /// arithmetic used to determine the address will result in a pointer to /// unrelated memory, which is likely to lead to undefined behaviour. #[inline] pub unsafe fn from_raw(elem: *mut T) -> NonNull<Self> { let addr = (elem as usize) - Self::offset_elem(); NonNull::new_unchecked(addr as *mut _) } /// Returns a reference to the header for the record at the pointed-to /// location of the pointer `elem`. /// /// # Safety /// /// The pointer `elem` must be a valid pointer to an instance of `T` that /// was allocated as part of a `Record`. /// Otherwise, the pointer arithmetic used to calculate the header's address /// will be incorrect and lead to undefined behavior. #[inline] pub unsafe fn header_from_raw<'a>(elem: *mut T) -> &'a R::RecordHeader { let header = (elem as usize) - Self::offset_elem() + Self::offset_header(); &*(header as *mut _) } /// Returns a reference to the header for the record at the pointed-to /// location of the non-nullable pointer `elem`. /// /// # Safety /// /// The pointer `elem` must be a valid pointer to an instance of `T` that /// was allocated as part of a `Record`. /// Otherwise, the pointer arithmetic used to calculate the header's address /// will be incorrect and lead to undefined behavior. #[inline] pub unsafe fn header_from_raw_non_null<'a>(elem: NonNull<T>) -> &'a R::RecordHeader { let header = (elem.as_ptr() as usize) - Self::offset_elem() + Self::offset_header(); &*(header as *mut _) } /// Returns the offset in bytes from the address of a record to its header /// field. #[inline] pub fn offset_header() -> usize { // FIXME: the offset_of! macro is unsound, this allows at least avoiding using it // in many cases until a better solution becomes available // https://internals.rust-lang.org/t/pre-rfc-add-a-new-offset-of-macro-to-core-mem/9273 if mem::size_of::<R::RecordHeader>() == 0 { 0 } else { offset_of!(Self, header) } } /// Returns the offset in bytes from the address of a record to its element /// field. #[inline] pub fn offset_elem() -> usize { // FIXME: the offset_of! macro is currently, this allows at least avoiding using it // in many cases until a better solution becomes available // https://internals.rust-lang.org/t/pre-rfc-add-a-new-offset-of-macro-to-core-mem/9273 if mem::size_of::<R::RecordHeader>() == 0 { 0 } else { offset_of!(Self, elem) } } } //////////////////////////////////////////////////////////////////////////////////////////////////// // Guarded //////////////////////////////////////////////////////////////////////////////////////////////////// /// A guard type fused with a protected value. #[derive(Debug)] pub struct Guarded<T, G, N: Unsigned> { guard: G, ptr: MarkedNonNull<T, N>, } impl<T, G: Protect, N: Unsigned> Guarded<T, G, N> { /// Returns a [`Shared`] reference borrowed from the [`Guarded`]. #[inline] pub fn shared(&self) -> Shared<T, G::Reclaimer, N> { Shared { inner: self.ptr, _marker: PhantomData } } /// Converts the [`Guarded`] into the internally stored guard. /// /// If `G` does not implement [`ProtectRegion`], the returned guard is /// guaranteed to be [`released`][Protect::release] before being returned. #[inline] pub fn into_guard(self) -> G { let mut guard = self.guard; guard.release(); guard } } //////////////////////////////////////////////////////////////////////////////////////////////////// // Owned //////////////////////////////////////////////////////////////////////////////////////////////////// /// A pointer type for heap allocated values similar to `Box`. /// /// `Owned` values function like marked pointers and are also guaranteed to /// allocate the appropriate [`RecordHeader`][Reclaim::RecordHeader] type /// for its generic [`Reclaim`] parameter alongside their actual content. #[derive(Eq, Ord, PartialEq, PartialOrd)] pub struct Owned<T, R: Reclaim, N: Unsigned> { inner: MarkedNonNull<T, N>, _marker: PhantomData<(T, R)>, } //////////////////////////////////////////////////////////////////////////////////////////////////// // Shared //////////////////////////////////////////////////////////////////////////////////////////////////// /// A shared reference to a value that is actively protected from reclamation by /// other threads. /// /// `Shared` values have similar semantics to shared references (`&'g T`), i.e. /// they can be trivially copied, cloned and (safely) de-referenced. /// However, they do retain potential mark bits of the atomic value from which /// they were originally read. /// They are also usually borrowed from guard values implementing the /// [`Protect`] trait. pub struct Shared<'g, T, R, N> { inner: MarkedNonNull<T, N>, _marker: PhantomData<(&'g T, R)>, } //////////////////////////////////////////////////////////////////////////////////////////////////// // Unlinked //////////////////////////////////////////////////////////////////////////////////////////////////// /// A reference to a value that has been removed from its previous location in /// memory and is hence no longer reachable by other threads. /// /// `Unlinked` values are the result of (successful) atomic *swap* or /// *compare-and-swap* operations on [`Atomic`] values. /// They are move-only types, but they don't have full ownership semantics, /// either. /// Dropping an `Unlinked` value without explicitly retiring it almost certainly /// results in a memory leak. /// /// The safety invariants around retiring `Unlinked` references are explained /// in detail in the documentation for [`retire_local`][Reclaim::retire_local]. #[derive(Eq, Ord, PartialEq, PartialOrd)] #[must_use = "unlinked values are meant to be retired, otherwise a memory leak is highly likely"] pub struct Unlinked<T, R, N> { inner: MarkedNonNull<T, N>, _marker: PhantomData<(T, R)>, } //////////////////////////////////////////////////////////////////////////////////////////////////// // Unprotected //////////////////////////////////////////////////////////////////////////////////////////////////// /// A reference to a value loaded from an [`Atomic`] that is not actively /// protected from reclamation. /// /// `Unprotected` values can not be safely de-referenced under usual /// circumstances (i.e. other threads can retire and reclaim unlinked records). /// They do, however, have stronger guarantees than raw (marked) pointers: /// Since are loaded from [`Atomic`] values they must (at least at one point) /// have been *valid* references. #[derive(Eq, Ord, PartialEq, PartialOrd)] pub struct Unprotected<T, R, N> { inner: MarkedNonNull<T, N>, _marker: PhantomData<R>, }