miri: Undefined Behavior: trying to retag from <20432167> for Unique permission in push_unchecked

[def-]

test bfs_100_2000_1 ... error: Undefined Behavior: trying to retag from <20432167> for Unique permission at alloc7796489[0x0], but that tag does not exist in the borrow stack for this location
   --> /home/deen/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/mod.rs:702:18
    |
702 |         unsafe { &mut *index.get_unchecked_mut(self) }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                  |
    |                  trying to retag from <20432167> for Unique permission at alloc7796489[0x0], but that tag does not exist in the borrow stack for this location
    |                  this error occurs as part of retag at alloc7796489[0x0..0x28]
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows 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
help: <20432167> would have been created here, but this is a zero-size retag ([0x0..0x0]) so the tag in question does not exist anywhere
   --> /home/deen/git/differential-dataflow/src/trace/implementations/merge_batcher.rs:129:23
    |
129 |     ::std::ptr::write(vec.get_unchecked_mut(len), element);
    |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `core::slice::<impl [((usize, usize), timely::order::Product<usize, u64>, isize)]>::get_unchecked_mut::<usize>` at /home/deen/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/mod.rs:702:18: 702:53
note: inside `differential_dataflow::trace::implementations::merge_batcher::push_unchecked::<((usize, usize), timely::order::Product<usize, u64>, isize)>`
   --> /home/deen/git/differential-dataflow/src/trace/implementations/merge_batcher.rs:129:23
    |
129 |     ::std::ptr::write(vec.get_unchecked_mut(len), element);
    |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `differential_dataflow::trace::implementations::merge_batcher::MergeSorter::<(usize, usize), timely::order::Product<usize, u64>, isize>::merge_by`
   --> /home/deen/git/differential-dataflow/src/trace/implementations/merge_batcher.rs:252:38
    |
252 | ...                   unsafe { push_unchecked(&mut result, (data1, time1, diff1)); }
    |                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `differential_dataflow::trace::implementations::merge_batcher::MergeSorter::<(usize, usize), timely::order::Product<usize, u64>, isize>::push`
   --> /home/deen/git/differential-dataflow/src/trace/implementations/merge_batcher.rs:186:30
    |
186 |                 let merged = self.merge_by(list1, list2);
    |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<differential_dataflow::trace::implementations::Batcher<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>> as differential_dataflow::trace::Batcher<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>>>::push_batch`
   --> /home/deen/git/differential-dataflow/src/trace/implementations/merge_batcher.rs:50:17
    |
50  |                 self.sorter.push(reference);
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<differential_dataflow::trace::rc_blanket_impls::RcBatcher<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>> as differential_dataflow::trace::Batcher<std::rc::Rc<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>>>>::push_batch`
   --> /home/deen/git/differential-dataflow/src/trace/mod.rs:421:93
    |
421 | ...y, B::Val), B::Time, B::R)>>) { self.batcher.push_batch(batch) }
    |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> /home/deen/git/differential-dataflow/src/operators/arrange/arrangement.rs:590:25
    |
590 |                         batcher.push_batch(data);
    |                         ^^^^^^^^^^^^^^^^^^^^^^^^
    = note: inside `timely::dataflow::operators::generic::InputHandleCore::<timely::order::Product<usize, u64>, std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>, timely::dataflow::channels::pact::LogPuller<timely::order::Product<usize, u64>, std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>, std::boxed::Box<dyn timely::communication::Pull<timely::communication::Message<timely::dataflow::channels::Message<timely::order::Product<usize, u64>, std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>>>>>>>::for_each::<[closure@<differential_dataflow::Collection<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, (usize, usize)> as differential_dataflow::operators::arrange::Arrange<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, usize, usize, isize>>::arrange_core<timely::dataflow::channels::pact::ExchangeCore<std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>, ((usize, usize), timely::order::Product<usize, u64>, isize), [closure@<differential_dataflow::Collection<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, (usize, usize)> as differential_dataflow::operators::arrange::Arrange<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, usize, usize, isize>>::arrange_named<differential_dataflow::trace::implementations::spine_fueled::Spine<std::rc::Rc<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>>>>::{closure#0}]>, differential_dataflow::trace::implementations::spine_fueled::Spine<std::rc::Rc<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>>>>::{closure#0}::{closure#0}::{closure#0}]>` at /home/deen/.cargo/git/checkouts/timely-dataflow-4c0cc365061cd263/b990fab/timely/src/dataflow/operators/generic/handles.rs:94:13: 94:29
    = note: inside `timely::dataflow::operators::generic::FrontieredInputHandleCore::<'_, timely::order::Product<usize, u64>, std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>, timely::dataflow::channels::pact::LogPuller<timely::order::Product<usize, u64>, std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>, std::boxed::Box<dyn timely::communication::Pull<timely::communication::Message<timely::dataflow::channels::Message<timely::order::Product<usize, u64>, std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>>>>>>>::for_each::<[closure@<differential_dataflow::Collection<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, (usize, usize)> as differential_dataflow::operators::arrange::Arrange<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, usize, usize, isize>>::arrange_core<timely::dataflow::channels::pact::ExchangeCore<std::vec::Vec<((usize, usize), timely::order::Product<usize, u64>, isize)>, ((usize, usize), timely::order::Product<usize, u64>, isize), [closure@<differential_dataflow::Collection<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, (usize, usize)> as differential_dataflow::operators::arrange::Arrange<timely::dataflow::scopes::Child<'_, timely::dataflow::scopes::Child<'_, timely::worker::Worker<timely::communication::Allocator>, usize>, timely::order::Product<usize, u64>>, usize, usize, isize>>::arrange_named<differential_dataflow::trace::implementations::spine_fueled::Spine<std::rc::Rc<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>>>>::{closure#0}]>, differential_dataflow::trace::implementations::spine_fueled::Spine<std::rc::Rc<differential_dataflow::trace::implementations::ord::OrdValBatch<usize, usize, timely::order::Product<usize, u64>, isize>>>>::{closure#0}::{closure#0}::{closure#0}]>` at /home/deen/.cargo/git/checkouts/timely-dataflow-4c0cc365061cd263/b990fab/timely/src/dataflow/operators/generic/handles.rs:139:9: 139:36
note: inside closure
   --> /home/deen/git/differential-dataflow/src/operators/arrange/arrangement.rs:588:21
    |
588 | /                     input.for_each(|cap, data| {
589 | |                         capabilities.insert(cap.retain());
590 | |                         batcher.push_batch(data);
591 | |                     });
    | |______________________^

Via MIRIFLAGS="-Zmiri-disable-isolation -Zmiri-strict-provenance" cargo miri test --no-fail-fast --workspace CC @teskje

[teskje]

Minimal repro:

unsafe fn push_unchecked<T>(vec: &mut Vec<T>, element: T) {
    debug_assert!(vec.len() < vec.capacity());
    let len = vec.len();
    ::std::ptr::write(vec.get_unchecked_mut(len), element);
    vec.set_len(len + 1);
}

fn main() {
    let mut v = Vec::with_capacity(1);
    unsafe { push_unchecked(&mut v, 1) };
    println!("{v:?}");
}

Playground link.

[teskje]

Fixed in #396. Once this warning is resolved, Miri starts complaining about consolidate_updates_slice, which is fixed in #394.