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
#![cfg_attr(docsrs, doc = include_str!("../README.md"))]
#![cfg_attr(docsrs, feature(doc_cfg, doc_auto_cfg, doc_cfg_hide))]
#![cfg_attr(docsrs, deny(missing_docs))]
#![cfg_attr(not(any(feature = "std", test)), no_std)]
#![allow(unused_unsafe)]
#[cfg(feature = "alloc")]
extern crate alloc;
#[cfg(test)]
extern crate std;
macro_rules! feature {
(
#![$meta:meta]
$($item:item)*
) => {
$(
#[cfg($meta)]
$item
)*
}
}
pub mod list;
#[doc(inline)]
pub use list::List;
pub mod mpsc_queue;
#[doc(inline)]
pub use mpsc_queue::MpscQueue;
pub(crate) mod loom;
pub(crate) mod util;
use core::ptr::NonNull;
/// Trait implemented by types which can be members of an [intrusive collection].
///
/// In order to be part of an intrusive collection, a type must contain a
/// `Links` type that stores the pointers to other nodes in that collection. For
/// example, to be part of a [doubly-linked list], a type must contain the
/// [`list::Links`] struct, or to be part of a [MPSC queue], a type must contain
/// the [`mpsc_queue::Links`] struct.
///
/// # Safety
///
/// This is unsafe to implement because it's the implementation's responsibility
/// to ensure that types implementing this trait are valid intrusive collection
/// nodes. In particular:
///
/// - Implementations **must** ensure that implementorss are pinned in memory while they
/// are in an intrusive collection. While a given `Linked` type is in an intrusive
/// data structure, it may not be deallocated or moved to a different memory
/// location.
/// - The type implementing this trait **must not** implement [`Unpin`].
/// - Additional safety requirements for individual methods on this trait are
/// documented on those methods.
///
/// Failure to uphold these invariants will result in corruption of the
/// intrusive data structure, including dangling pointers.
///
/// # Implementing `Linked::links`
///
/// The [`Linked::links`] method provides access to a `Linked` type's `Links`
/// field through a [`NonNull`] pointer. This is necessary for a type to
/// participate in an intrusive structure, as it tells the intrusive structure
/// how to access the links to other parts of that data structure. However, this
/// method is somewhat difficult to implement correctly.
///
/// Suppose we have an entry type like this:
/// ```rust
/// use cordyceps::list;
///
/// struct Entry {
/// links: list::Links<Self>,
/// data: usize,
/// }
/// ```
///
/// The naive implementation of [`links`](Linked::links) for this `Entry` type
/// might look like this:
///
/// ```
/// use cordyceps::Linked;
/// use core::ptr::NonNull;
///
/// # use cordyceps::list;
/// # struct Entry {
/// # links: list::Links<Self>,
/// # }
///
/// unsafe impl Linked<list::Links<Self>> for Entry {
/// # type Handle = NonNull<Self>;
/// # fn into_ptr(r: Self::Handle) -> NonNull<Self> { r }
/// # unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle { ptr }
/// // ...
///
/// unsafe fn links(mut target: NonNull<Self>) -> NonNull<list::Links<Self>> {
/// // Borrow the target's `links` field.
/// let links = &mut target.as_mut().links;
/// // Convert that reference into a pointer.
/// NonNull::from(links)
/// }
/// }
/// ```
///
/// However, this implementation **is not sound** under [Stacked Borrows]! It
/// creates a temporary reference from the original raw pointer, and then
/// creates a new raw pointer from that temporary reference. Stacked Borrows
/// will reject this reborrow as unsound.[^1]
///
/// There are two ways we can implement [`Linked::links`] without creating a
/// temporary reference in this manner. The recommended one is to use the
/// [`core::ptr::addr_of_mut!`] macro, as follows:
///
/// ```
/// use core::ptr::{self, NonNull};
/// # use cordyceps::{Linked, list};
/// # struct Entry {
/// # links: list::Links<Self>,
/// # }
///
/// unsafe impl Linked<list::Links<Self>> for Entry {
/// # type Handle = NonNull<Self>;
/// # fn into_ptr(r: Self::Handle) -> NonNull<Self> { r }
/// # unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle { ptr }
/// // ...
///
/// unsafe fn links(target: NonNull<Self>) -> NonNull<list::Links<Self>> {
/// let target = target.as_ptr();
///
/// // Using the `ptr::addr_of_mut!` macro, we can offset a raw pointer to a
/// // raw pointer to a field *without* creating a temporary reference.
/// let links = ptr::addr_of_mut!((*target).links);
///
/// // `NonNull::new_unchecked` is safe to use here, because the pointer that
/// // we offset was not null, implying that the pointer produced by offsetting
/// // it will also not be null.
/// NonNull::new_unchecked(links)
/// }
/// }
/// ```
///
/// It is also possible to ensure that the struct implementing `Linked` is laid
/// out so that the `Links` field is the first member of the struct, and then
/// cast the pointer to a `Links`. Since [Rust's native type representation][repr]
/// does not guarantee the layout of struct members, it is **necessary** to ensure
/// that any struct that implements the `Linked::links` method in this manner has a
/// [`#[repr(C)]` attribute][repr-c], ensuring that its fields are laid out in the
/// order that they are defined.
///
/// For example:
///
/// ```
/// use core::ptr::NonNull;
/// use cordyceps::{Linked, list};
///
/// // This `repr(C)` attribute is *mandatory* here, as it ensures that the
/// // `links` field will *always* be the first field in the struct's in-memory
/// // representation.
/// #[repr(C)]
/// struct Entry {
/// links: list::Links<Self>,
/// data: usize,
/// }
///
/// unsafe impl Linked<list::Links<Self>> for Entry {
/// # type Handle = NonNull<Self>;
/// # fn into_ptr(r: Self::Handle) -> NonNull<Self> { r }
/// # unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle { ptr }
/// // ...
///
/// unsafe fn links(target: NonNull<Self>) -> NonNull<list::Links<Self>> {
/// // Safety: this performs a layout-dependent cast! it is only sound
/// // if the `Entry` type has a `#[repr(C)]` attribute!
/// target.cast::<list::Links<Self>>()
/// }
/// }
/// ```
///
/// In general, this approach is not recommended, and using
/// [`core::ptr::addr_of_mut!`] should be preferred in almost all cases. In
/// particular, the layout-dependent cast is more error-prone, as it requires a
/// `#[repr(C)]` attribute to avoid soundness issues. Additionally, the
/// layout-based cast does not permit a single struct to contain `Links` fields
/// for multiple intrusive data structures, as the `Links` type *must* be the
/// struct's first field.[^2] Therefore, [`Linked::links`] should generally be
/// implemented using [`addr_of_mut!`](core::ptr::addr_of_mut).
///
/// [^1]: Note that code like this is not *currently* known to result in
/// miscompiles, but it is rejected by tools like Miri as being unsound.
/// Like all undefined behavior, there is no guarantee that future Rust
/// compilers will not miscompile code like this, with disastrous results.
/// [^2]: And two different fields cannot both be the first field at the same
/// time...by definition.
///
/// [intrusive collection]: crate#intrusive-data-structures
/// [`Unpin`]: core::marker::Unpin
/// [doubly-linked list]: crate::list
/// [MSPC queue]: crate::mpsc_queue
/// [Stacked Borrows]: https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md
/// [repr]: https://doc.rust-lang.org/nomicon/repr-rust.html
/// [repr-c]: https://doc.rust-lang.org/nomicon/other-reprs.html#reprc
pub unsafe trait Linked<L> {
/// The handle owning nodes in the linked list.
///
/// This type must have ownership over a `Self`-typed value. When a `Handle`
/// is dropped, it should drop the corresponding `Linked` type.
///
/// A quintessential example of a `Handle` is [`Box`].
///
/// [`Box`]: alloc::boxed::Box
type Handle;
/// Convert a [`Self::Handle`] to a raw pointer to `Self`, taking ownership
/// of it in the process.
fn into_ptr(r: Self::Handle) -> NonNull<Self>;
/// Convert a raw pointer to `Self` into an owning [`Self::Handle`].
///
/// # Safety
///
/// This function is safe to call when:
/// - It is valid to construct a [`Self::Handle`] from a`raw pointer
/// - The pointer points to a valid instance of `Self` (e.g. it does not
/// dangle).
unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle;
/// Return the links of the node pointed to by `ptr`.
///
/// # Safety
///
/// This function is safe to call when:
/// - It is valid to construct a [`Self::Handle`] from a`raw pointer
/// - The pointer points to a valid instance of `Self` (e.g. it does not
/// dangle).
///
/// See [the trait-level documentation](#implementing-linkedlinks) for
/// details on how to correctly implement this method.
unsafe fn links(ptr: NonNull<Self>) -> NonNull<L>;
}