BTreeSet causes UB by having (partially) dangling shared reference

[RalfJung]

The following code causes UB (found by a patched miri enforcing validity invariants):

    let mut b = std::collections::BTreeSet::new();
    b.insert(42);

What happens is that BTreeSet::new sets the root node to a pointer to a static EMPTY_ROOT_NODE shared for this purpose by all B-trees that has type LeafNode<(), ()>. That step is okay.

However, in the next step, insert calls ensure_root_is_owned which indirectly turns this ptr into &LeafNode<i32, ()>. The trouble is that LeafNode<i32, ()> is bigger than LeafNode<(), ()>, so this reference is partially dangling: Its beginning points to allocated memory (the static EMPTY_ROOT_NODE), but that allocated memory ends "too early". The invariant that &LeafNode<i32, ()> be dereferencable for mem::size_of::<LeafNode<i32, ()>>() bytes is violated. Since we are passing dereferencable(n) to LLVM with n set to the full size of the struct, this means we have UB not just according to our own validity rules, but according to LLVM's rules.

[aturon]

cc @gankro

[Gankra]

Good catch, and very interesting. I wasn't aware that this was a thing. When was this semantic decided/documented?

This can be easily fixed by hoisting the ptr::eq(self, &EMPTY_ROOT_NODE as *const _ as *const _) into is_shared_root.

[Gankra]

Also: what value does that metadata have? Allowing speculative loads?

[RalfJung]

This can be easily fixed by hoisting the ptr::eq(self, &EMPTY_ROOT_NODE as *const _ as *const _) into is_shared_root.

I don't think that's enough. All the code that does read-only operations (get, for example) will likely also turn the shared root into a reference.

what value does that metadata have? Allowing speculative loads?

Exactly.

Moreover, even just enforcing the noalias annotations the way I proposed makes it UB to have dangling references.

[RalfJung]

@nikomatsakis points out there might also be alignment problems. @eddyb are there any types that have alignment bigger than pointers?

[nikomatsakis]

One possible fix -- but it'd be a big lang change -- is supporting generic statics (so that the static node can have a valid type). Of course that's not a "short term" usable thing.

[RalfJung]

Another thing @nikomatsakis suggested is to essentially use &LeafNode<(), ()> throughout the read-only operations until we determined that the node actually is non-empty. That should also work.

[Gankra]

I need to go over the code to check but I assume the “right” fix is to define an untyped base header type that LeafNode “inherits” from, just like we did in the Swift stdlib (where swift has TBAA)

[Gankra]

Deferring working on this for a bit while some other stuff lands, some notes:

the core of the right fix is to add something like this code:

    fn as_key_slice(&self) -> &'a [K] {
        // When taking a pointer to the keys, if our key has a stricter
        // alignment requirement than the shared root does, then the pointer
        // would be out of bounds, which LLVM assumes will not happen. If the
        // alignment is more strict, we need to make an empty slice that doesn't
        // use an out of bounds pointer.
        if mem::align_of::<K>() > mem::align_of::<LeafPrefix>() && self.is_shared_root() {
            &[]
        } else {
            // Here either it's not the root, or the alignment is less strict,
            // in which case the keys pointer will point "one-past-the-end" of
            // the node, which is allowed by LLVM.
            unsafe {
                slice::from_raw_parts(
                    &(*self.node as *const LeafNode<K, V>).keys as *const K,
                    self.len()
                )
            }
        }
    }

to btree::node::Root, and introduce an untyped header/prefix as I discussed above. The annoying part is going through all the code and making perfectly sure nothing casts to a Leaf prematurely.

[RalfJung]

the core of the right fix is to add something like this code:

I am not sure why comparing the alignments is enough to guarantee that things are in-bounds (I assume "the pointer" which is out of bounds is self.node, but that's not clear either). And anyway wouldn't it be much simpler to just return &[] whenever self.len() == 0? Determining the len should be possible even for the "untyped header".

[Gankra]

The idea is we're trying to avoid any additional checks.

Alignment differences determine padding, which in turn determines if the keys would be placed within the bounds of the LeafPrefix's size.