Trait Linked

pub unsafe trait Linked<L> {
    type Handle;

    // Required methods
    fn into_ptr(r: Self::Handle) -> NonNull<Self>;
    unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle;
    unsafe fn links(ptr: NonNull<Self>) -> NonNull<L>;
}

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 implementors 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:

use cordyceps::list;

struct Entry {
    links: list::Links<Self>,
    data: usize,
}

The naive implementation of links for this Entry type might look like this:

use cordyceps::Linked;
use core::ptr::NonNull;


unsafe impl Linked<list::Links<Self>> for Entry {
    // ...

    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.¹

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};

unsafe impl Linked<list::Links<Self>> for Entry {
    // ...

    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 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, 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 {
    // ...

    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.² Therefore, Linked::links should generally be implemented using 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. ↩

Required Associated Types

type Handle

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.

Required Methods

fn into_ptr(r: Self::Handle) -> NonNull<Self>

Convert a Self::Handle to a raw pointer to Self, taking ownership of it in the process.

unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle

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 links(ptr: NonNull<Self>) -> NonNull<L>

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 for details on how to correctly implement this method.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors