Miri failure in btree::map::test_iter_min_max test
RalfJung opened this issue · 18 comments
btree::map::test_iter_min_max recently started failing in Miri:
error: Undefined Behavior: not granting access to tag <untagged> because incompatible item is protected: [Unique for <26146034> (call 7514376)]
--> /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/ptr/non_null.rs:121:9
|
121 | &*self.as_ptr()
| ^^^^^^^^^^^^^^^ not granting access to tag <untagged> because incompatible item is protected: [Unique for <26146034> (call 7514376)]
|
= help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
= help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
= note: inside `std::ptr::NonNull::<alloc::collections::btree::node::LeafNode<i32, i32>>::as_ref` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/ptr/non_null.rs:121:9
= note: inside `alloc::collections::btree::node::NodeRef::<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>::as_leaf` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:321:18
= note: inside `alloc::collections::btree::node::NodeRef::<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>::len` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:293:9
= note: inside `alloc::collections::btree::node::Handle::<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>, alloc::collections::btree::node::marker::Edge>::new_edge` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:802:30
= note: inside `alloc::collections::btree::node::Handle::<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>::forget_node_type` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/node.rs:1361:18
= note: inside `alloc::collections::btree::navigate::<impl alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>>::next_kv` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:16:24
= note: inside closure at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:132:26
= note: inside `alloc::collections::btree::navigate::replace::<alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>, alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::LeafOrInternal>, alloc::collections::btree::node::marker::KV>, [closure@alloc::collections::btree::navigate::<impl alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut<'a>, K, V, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>>::next_unchecked::{{closure}}#0]>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:88:28
= note: inside `alloc::collections::btree::navigate::<impl alloc::collections::btree::node::Handle<alloc::collections::btree::node::NodeRef<alloc::collections::btree::node::marker::Mut, i32, i32, alloc::collections::btree::node::marker::Leaf>, alloc::collections::btree::node::marker::Edge>>::next_unchecked` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/navigate.rs:131:22
= note: inside `std::collections::btree_map::RangeMut::<i32, i32>::next_unchecked` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/map.rs:1904:18
= note: inside `<std::collections::btree_map::IterMut<i32, i32> as std::iter::Iterator>::next` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/map.rs:1457:35
= note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::next` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/liballoc/collections/btree/map.rs:1810:9
= note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::fold::<&mut i32, [closure@std::iter::Iterator::min_by::fold::{{closure}}#0 0:for<'r, 's> fn(&'r &mut i32, &'s &mut i32) -> std::cmp::Ordering {<&mut i32 as std::cmp::Ord>::cmp}]>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2021:29
= note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::fold_first::<[closure@std::iter::Iterator::min_by::fold::{{closure}}#0 0:for<'r, 's> fn(&'r &mut i32, &'s &mut i32) -> std::cmp::Ordering {<&mut i32 as std::cmp::Ord>::cmp}]>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2061:14
= note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::min_by::<for<'r, 's> fn(&'r &mut i32, &'s &mut i32) -> std::cmp::Ordering {<&mut i32 as std::cmp::Ord>::cmp}>` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2627:9
= note: inside `<std::collections::btree_map::ValuesMut<i32, i32> as std::iter::Iterator>::min` at /home/travis/build/RalfJung/miri-test-libstd/rust-src-patched/src/libcore/iter/traits/iterator.rs:2499:9
note: inside `btree::map::test_iter_min_max` at alloc_miri_test/../liballoc/tests/btree/map.rs:343:16
--> alloc_miri_test/../liballoc/tests/btree/map.rs:343:16
|
343 | assert_eq!(a.values_mut().min(), Some(&mut 24));
| ^^^^^^^^^^^^^^^^^^^^
note: inside closure at alloc_miri_test/../liballoc/tests/btree/map.rs:313:1
--> alloc_miri_test/../liballoc/tests/btree/map.rs:313:1
|
313 | / fn test_iter_min_max() {
314 | | let mut a = BTreeMap::new();
315 | | assert_eq!(a.iter().min(), None);
316 | | assert_eq!(a.iter().max(), None);
... |
344 | | assert_eq!(a.values_mut().max(), Some(&mut 42));
345 | | }
| |_^
(Sorry for the bad spacing, Travis logs are like that...)
Oops, I forgot about Miri while testing. But it baffles me that it fails.
More accurately, the recent test never succeeded (under Miri). The failing part is unrelated to the main change in #73627, I just added lines for the iterators values and values_mut (which are not in ascending order so couldn't be optimized) to cover more iterators. And it turns out the default implementation of min and max does not play nice for these iterators. A line a.values_mut().max(); added to the old test case test_values_mut in rust e093b65 (the base of #73627) fails similarly.
So what next? I could take out these testing lines from #73627 since they're not directly related to the change, create a new test case, but will probably not understand what is wrong.
PS it's only values_mut that suffers, not values.
PS2 it's not values_mut per sé, a.iter_mut().map(|(_,v)| v).min() suffers the same fate
PS3 it only happens with at least 2 elements iterated
@ssomers could you share an MRE demonstrating the problem, ideally unrelated to your changes? Then I can investigate.
#[test]
fn test_iter_mut_map_min() {
let mut a = BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
a.iter_mut().map(|(_,v)| v).min();
}
Nope, that was not minimal. It fails even without the map.
PS Which is what the new test tests earlier, but then it succeeds, because the optimization replaces the failing default implementation.
This seems to pass Miri on the playground though?
fn main() {
let mut a = std::collections::BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
a.iter_mut().min();
}This fails:
fn main() {
let mut a = std::collections::BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
a.iter_mut().map(|(_,v)| v).min();
}So I'll make that the one to investigate. Thanks!
I think it succeeds on playground because #73627 is already on there and that inadvertently fixed IterMut::min. It succeeds on playground's beta too, so the actual bug must be recent.
Miri is nightly-only. The stable/beta/nightly selection in the left has no effect at all on the tools menu.
The protector that is being violates is of fold:
fn fold<B, F>(mut self, init: B, mut f: F) -> B
where
Self: Sized,
F: FnMut(B, Self::Item) -> B,B is &mut i32, so I believe that is the reference on whose toe something is stepping here.
The conflict is from this call to len:
rust/src/liballoc/collections/btree/node.rs
Line 816 in 9491f18
This calls as_leaf(), and that creates an &LeafNode which overlaps with a mutable reference that was previously handed out by the iterator.
Fixing len to avoid creating a reference is easy, but not sufficient. The next conflict is caused by
rust/src/liballoc/collections/btree/node.rs
Line 511 in 9491f18
Something seems to be very fundamentally wrong here: that code is creating a slice covering all keys and values, but this happens during iteration where the user also has access to some of these keys and/or values!
Here's another way to trigger the same problem:
use std::mem;
fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
// Gather all thrse references
let mut refs: Vec<&mut T> = iter.collect();
// Use them all. Twice, to be sure we got all interleavings.
for r in refs.iter_mut() {
mem::swap(dummy, r);
}
for r in refs {
mem::swap(dummy, r);
}
}
fn main() {
let mut a = std::collections::BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
test_all_refs(&mut 13, a.values_mut());
}Writing &mut iterators is tricky, and test_all_refs is a good way to ensure that the references are actually all working and not invalid due to aliasing.
I don't fundamentally understand what's wrong with (internally) creating a slice of references and handing them out to the public one by one carefully, but I mention that it is possible to avoid the slice altogether. This was a way to avoid complicated code that have been dealt with in other ways meanwhile. I'll have a look what Miri says about this and the new test nowadays.
I started in https://github.com/RalfJung/rust/tree/btree-raw to use raw pointers more, but when I realized I'd have to change all that slice code I stopped -- I don't have the time for that right now I'm afraid. And maybe getting rid of slices is indeed better. :)
I don't fundamentally understand what's wrong with (internally) creating a slice of references and handing them out to the public one by one carefully,
The problem is that the code is not doing it carefully enough. :) BTree does the equivalent of:
let mut data = [1, 2, 3];
let slice = &mut data[..];
let ptr1 = &mut slice[0]; // handing this out to the user
let slice = &mut data[..]; // Uh-oh! This slice *overlaps* with the reference the user got!
let ptr2 = &mut slice[1]; // handing this out to the user
// Now as a user, try using both ptr1 and ptr1...
mem::swap(ptr1, ptr2);
// The borrow checker says "no", because when we created the 2nd "slice", we invalidated "ptr1".BTree does the same thing, except it uses raw pointers so the borrow checker does not see what happens. When it creates the second slice, that overlaps with an existing mutable reference that was previously given to the user, and that is disallowed by the aliasing rules.
If BTree created the slice once and then kept giving out references, that would be fine. But when you create a new &mut slice (or reborrow an existing one), you are saying "this is a unique pointer to that entire array", and that is the problem.
Does this make sense?
I think I understand, but at some point I thought I understood the #133 discussion on stacked borrows and some of the stacked borrows paper (say 10%, using hexadecimal notation...), but it doesn't stick.
Replacing slices with (raw??) pointers doesn't help. I'm guessing because MaybeUninit::first_ptr(...).add(idx) temporarily creates the pointer to the first value again every time.
The code still does &self.as_leaf().vals, which creates a shared reference to the entire array.
Try &raw const (*self.as_leaf()).vals. You'll also need the patch I linked above that makes as_leaf return a raw pointer.
I can build on your as_leaf, but don't know how to feed your actual raw pointers to MaybeUninit::first_ptr.
I don't understand the previous first_ptr-based code (that I stole from elsewhere) either. It's an array of MaybeUninit thingies, so why can't we just index the array first and then cross the MaybeUninit barrier? That's what I tried and amazingly it seems to work fine. Without your fancy &raw syntax. Well, maybe that's part of MaybeUninit::get_ref.
I can build on your as_leaf, but don't know how to feed your actual raw pointers to MaybeUninit::first_ptr.
Yeah, you cannot... you have to avoid that API.
The point of that function is to avoid having to cast raw pointers. Casting raw pointers is extremely fragile, because even if the source type changes, the cast will still work. Thus I think one should try very hard to never directly cast one raw ptr type to another, and instead always go through some method which constrains what the cast can do.