Repository navigation
BTree's insert_fit breaks pointer provenance rules #78477
Description
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
Activity
ssomers commentedon Oct 28, 2020
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 commentedon Oct 28, 2020
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 commentedon Oct 28, 2020
Ok. The fix conflicts with #78476, so maybe it's better to add it onto that PR?
RalfJung commentedon Oct 28, 2020
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 commentedon Oct 28, 2020
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 commentedon Oct 28, 2020
Assigning
P-highas discussed as part of the Prioritization Working Group procedure and removingI-prioritize.RalfJung commentedon Oct 28, 2020
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).
Rollup merge of rust-lang#78480 - ssomers:btree-alias, r=Mark-Simulacrum