Why does LinkedLists in std library contain a marker?

help
1 
pub struct LinkedList<T> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>,
}

Why does LinkedLists in std library contain a marker ? What is its purpose?

If it would want to express the semantic that LinkedList owns T so that it could make drop checker be sound, it is unnecessary ever since RFC 1238. see: PhantomData - The Rustonomicon

1 Like
2

LinkedList, along with a few other standard library types including HashMap, Box, or Vec, uses the unstable (and unsafe) attribute #[may_dangle] on their Drop implementation to get a more lenient drop-check behavior. With that attribute being used, it’s necessary to add a PhantomData that allows the dropcheck to know that dropping LinkedList<T> will still drop a value of type T, whilst – in contrast with the situation if the #[may_dangle] wasn’t used at all – it will also know that dropping a LinkedList<T> will not result in arbitrary access to values of type T.

This has the effect that e.g.

  • dropping a LinkedList<&'a u8> will be allowed even after the pointed-to u8 has already gone out of scope – Rust Playground
    • this would not be allowed if LinkedList didn’t use #[may_dangle] attribute
  • dropping a LinkedList<Foo<'a>> will not be allowed for a type struct Foo<'a>(&'a u8) if the struct Foo has a custom Drop implementation (which is necessary for soundness since this drop implementation could dereference the &'a u8 reference) – Rust Playground
    • without the PhantomData in LinkedList, this second point would not be ensured (in the presence of #[may_dangle]) and such a dropping action would be unsoundly allowed

To see a concrete unsoundness exploitation example of missing such a PhantomData marker, see this issue that I had semi-recently opened because BTreeMap had missed the necessary marker: Too lenient `#[may_dangle]` on `BTreeMap`; misses `PhantomData` for dropck · Issue #99408 · rust-lang/rust · GitHub – and feel free to also look at the simple PR that fixes it: Add `PhantomData` marker for dropck to `BTreeMap` by steffahn · Pull Request #99413 · rust-lang/rust · GitHub

I haven’t actually read the RFC you linked to, but at a glance it seems like #[may_dangle] might be the current syntax for what that RFC calls “unguarded-escape-hatch”.

12 Likes
4

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.