Incorrect and inconsistent behaviour using HashSet::into_iter

[andrewhickman]

The following code occasionally fails:

    for i in 0..10000 {
        let mut lhs = vec![604, 986, 436, 379, 59, 423, 391, 434, 375, 486, 64, 851, 631, 89];
        lhs.sort();

        let mut iset = im::HashSet::new();
        for &i in &lhs {
            iset.insert(i);
        }

        let mut rhs: Vec<_> = iset.clone().into_iter().collect();
        rhs.sort();

        if lhs != rhs {
            println!("iteration: {}", i);
            println!("lhs: {:?}", &lhs);
            println!("rhs: {:?}", &rhs);
            panic!();
        }
    }

It seems values are sometimes skipped in the IntoInterator implementation of HashSet.

The behaviour is not consistent but 10000 iterations is usually enough to reproduce it, outputting something like

iteration: 3370
lhs: [59, 64, 89, 375, 379, 391, 423, 434, 436, 486, 604, 631, 851, 986]
rhs: [64, 375]

[andrewhickman]

Running under valgrind I get the following error

==8723== Conditional jump or move depends on uninitialised value(s)
==8723==    at 0x3601B4: <im::nodes::hamt::Drain<A> as core::iter::iterator::Iterator>::next (hamt.rs:641)
==8723==    by 0x36042C: <im::nodes::hamt::Drain<A> as core::iter::iterator::Iterator>::next (hamt.rs:639)
==8723==    by 0x36042C: <im::nodes::hamt::Drain<A> as core::iter::iterator::Iterator>::next (hamt.rs:639)
==8723==    by 0x36042C: <im::nodes::hamt::Drain<A> as core::iter::iterator::Iterator>::next (hamt.rs:639)
==8723==    by 0x21A1E4: <im::hash::set::ConsumingIter<A> as core::iter::iterator::Iterator>::next (set.rs:823)
==8723==    by 0x1C20A2: <alloc::vec::Vec<T>>::extend_desugared (vec.rs:1908)
==8723==    by 0x1D3900: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::spec_extend (vec.rs:1805)
==8723==    by 0x1D8588: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::from_iter (vec.rs:1800)
==8723==    by 0x1D909E: <alloc::vec::Vec<T> as core::iter::traits::FromIterator<T>>::from_iter (vec.rs:1700)
==8723==    by 0x216ECE: core::iter::iterator::Iterator::collect (iterator.rs:1476)
==8723==    by 0x319353: im::hash::set::test::insert_and_clone_into_iter::{{closure}} (set.rs:1072)
==8723==    by 0x3190E4: core::ops::function::impls::<impl core::ops::function::Fn<A> for &F>::call (function.rs:247)

I'm not sure of the exact cause but replacing the calls to mem::uninitialized() with mem::zeroed() in src\nodes\unsafe_chunks\sparse_chunk.rs makes the warnings go away and fixes the issue.

[bodil]

Likely a bug in the unsafe chunk code which fails to initialise some allocated memory before use. This should be a fun one to track down...

[bodil]

The mem:zeroed() patch doesn't seem to solve the issue, and I can't for the life of me find anything wrong with the implementation of SparseChunk, so I'm leaning towards a bug in hash collision handling, which I think must be the only other thing that could be nondeterministic in this way.

[bodil]

I'm still not quite sure what was causing this, though Valgrind wasn't lying. I ended up simplifying the iterators in question, which got rid of the Valgrind warnings and the bug. As a bonus, iteration speed was probably increased by a tiny factor too.

[Eh2406]

If this was reading undefined memory, should the problematic versions be yanked and maybe a security advisory be issued?

[bodil]

I don't have any reason to believe it was reading uninitialised memory in any meaningful way, though I also didn't really find a satisfying answer to what was going on. The bug was manifesting in code from std, but may have been due to some weird interaction with some of the unsafe code I removed when fixing it.

I'm still not disinclined to yank all minor versions previous to the fix, though... I think I'll go ahead and do that.