BTree's insert_fit breaks pointer provenance rules

[RalfJung]

This code violates pointer provenance rules:

    fn insert_fit(&mut self, key: K, val: V) -> *mut V {
        debug_assert!(self.node.len() < CAPACITY);

        unsafe {
            slice_insert(self.node.keys_mut(), self.idx, key);
            slice_insert(self.node.vals_mut(), self.idx, val);
            self.node.as_leaf_mut().len += 1;

            self.node.val_mut_at(self.idx)
        }
    }

Specifically, self.node.keys_mut() returns a slice covering the previously existing elements of this node, but it is used to also access the new element one-past-the-end of the previous slice.

Either slice_insert needs to be passed a slice covering all the memory it needs to access (of type &mut [MaybeUninit<_>]), or else it needs to be passed a raw pointer (that may access the entire buffer) and a length. But keys_mut/vals_mut can only be used to access elements that already exist, not to initialize new elements.

Cc @ssomers

[ssomers]

I was surprised when I realized that, but I think it has been like that for a long time. So I wonder if you're tightening up Miri or I should check out where we went wrong recently?

[RalfJung]

I only found this when tightening Miri while debugging why #77187 broke BtreeMap (that PR should only break code that casts pointers to integers and back, with this code does not do AFAIK).

[ssomers]

Ok. The fix conflicts with #78476, so maybe it's better to add it onto that PR?

[RalfJung]

Probably, yes. I spent enough time on this for now that I should have used for the work I am paid to do. ;) So I decided to just open the issue instead of trying to fix this problem myself.

[RalfJung]

rust-lang/miri#1603 adds a flag to Miri that lets you opt-in to that more strict tracking yourself. Note that this might reject some valid code when integer-pointer casts are involved.

[spastorino]

Assigning P-high as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

[RalfJung]

FWIW, these are violations with Stacked Borrows -- but the actual impact is likely low as we barely exploit aliasing assumptions currently. So IMO there is no reason to treat this as high priority. It barely qualifies as a soundness issue, given that Stacked Borrows is purely experimental (and not RFC'd or anything).