Non-deterministic results starting from 68fede8a9ad8c094664525622270da6966821b1f

I've diagnosed a failure in one of our internal crate to be caused by upgrading twox-hash from 1.3.0 to 1.4.1. It appears that computing the hash of the same data yield different hashes starting from 68fede8.

I don't have a reproduction yet, but I'm currently looking into it.

Hmm. It’s always possible, but would be pretty surprising! We have (what I hope is) a pretty comprehensive test suite that compares our results against the C implementation for arbitrary blobs of bytes and non-aligned parts of those bytes. This is in addition to the standard unit tests that one would expect.

Please keep up updated and sorry for any inconvenience!

I have a repro :). See below:

#[cfg(test)]
mod tests {
    use twox_hash::XxHash32;
    use std::hash::Hasher;

    fn xxhash32<T: AsRef<[u8]>>(buf: T) -> u64 {
        let mut xx = XxHash32::default();
        xx.write(buf.as_ref());
        xx.finish()
    }

    #[test]
    fn test_repro() {
        let v1 = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
        let h1 = xxhash32(&v1);
        let v2 = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
        let v2_unaligned = v2.split_at(2).1;
        let h2 = xxhash32(&v2_unaligned);
        assert_eq!(h1, h2);
    }
}

This is Cargo's output:

thread 'log::tests::test_repro' panicked at 'assertion failed: `(left == right)`
  left: `138735893`,
 right: `4213300049`'

The alignment appears to be the issue here.

This is on an Intel 64-bits CPU, running on Linux. I also reproduced on a MacBook Pro. This is with Rust 1.35.0.

I have a repro

This repro appears to be missing the imports and uses functions that are not defined. Could you please double check the code and edit it to a complete example?

It would also be good to include your platform (Windows / Mac / Linux), your bitness (16-, 32-, 64-bit), and what CPU you have.

Full repro: https://gist.github.com/xavierd/76009599e219a49c0c18fbc44790413d#file-bug-rs

This is on an Intel 64-bits CPU, running on Linux.

Just reproduced on a MacBook Pro. Forgot to add, this is with rust 1.35.0.

Initial investigation shows that the first two bytes are unaligned and are stored in the buffer. The next 16 bytes are aligned and treated as 4 x u32. It’s unclear why the existing tests don’t cover this.

I think this comment:

// Surprisingly, if we still have bytes in the buffer here, we
// don't do anything with them yet! This matches the C
// implementation.

is wrong. The C code will make sure the buffer is processed later in the right order (i.e. things in buffer gets calculated before processing aligned chunks that are after the unaligned bytes).

An easy fix to this would be changing XxHash::write to just:

 fn write(&mut self, bytes: &[u8]) {
     self.buffer_bytes(bytes);
     self.total_len += bytes.len() as u32;
 }

However, I suspect that would lead to perf regressions. I'm currently running benchmarks and figuring out a proper fix.

I think this comment:

Entirely possible, thus my use of “surprisingly” there 😉 . I said that based on my tests which showed that we matched the C “in every case”. I also want to figure out why these tests aren’t triggering this case, which they definitely should.

The tests do not seem to use unaligned access at the beginning of the buffer?

Benchmark shows the simple fix is 3x slower on large chunk of data (but slightly faster on tiny data), somehow as expected. I'm trying to write a proper fix.

The tests do not seem to use unaligned access at the beginning of the buffer?

I’m not following you. This test generates a random Vec<u8> and a random index into that data. It then starts a slice from that index.

twox-hash/comparison/src/lib.rs

Lines 77 to 83 in 40b60e8

    
           fn same_results_as_c_with_offset_for_32_bit(seed: u32, (data, offset) in data_and_offset()) { 
        
               let data = &data[offset..]; 
        
               let our_result = hash_once(XxHash32::with_seed(seed), data); 
        
               let their_result = c_xxhash::hash32(data, seed); 
        
               our_result == their_result as u64 
        
           }

Inserting the data from this reproduction into the same code causes a failure:

    let seed = 0;
    let data = vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
    let offset = 2;

    let data = &data[offset..];
    let our_result = hash_once(XxHash32::with_seed(seed), data);
    let their_result = c_xxhash::hash32(data, seed);

    assert_eq!(our_result, their_result as u64);

Well, looks like something is totally broken with the tests:

   #[test]
    fn same_results_as_c_with_offset_for_32_bit(seed: u32, (data, offset) in data_and_offset()) {
        false
    }

test same_results_as_c_with_offset_for_32_bit ... ok

superb.

It seems you need to use prop_assert_eq! instead. It's not quickcheck that returns a bool.

It seems non-trivial to fix it while keeping using the aligned memory access (ingest_chunks).

I believe both the C code and the old Rust code (at d0a8d72) do unaligned memory access:

The C code uses the XXH_read* API to do so. The old Rust code uses unsafe code, which actually looks undefined:

// number_streams.rs
impl<'a> Iterator for $name<'a> {
    type Item = $number_type;
    fn next(&mut self) -> Option<$number_type> {
        if self.start >= self.end { return None }
        let v: $number_type = unsafe { ptr::read(self.start) }; // <--- UB: should use `ptr::read_unaligned`
        self.start = unsafe { self.start.offset(1) };
        Some(v)
    }
    ...
}
));

I don't know what's the elegant way to fix it and am giving up now. I hope you can come up with something neat :)

I’ve opened #32 as a fix for right now, in order to get correct results. Could you try that with your original case to see if it works there?

Looking at the code, I believe it works. However, it'd cause visible perf regression (because of copying bytes to buffer unnecessarily) if it's unaligned. Do you plan to have a fix that restores the perf? I think read_unaligned has to be used directly or indirectly to achieve that.

Do you plan to have a fix that restores the perf

Yes, but I do not have plan for how yet.

Ideally, most people are using this as a one-shot hash from data allocated on a boundary, so they won’t even notice the problem.

I’m going to release this as 1.4.2, yank 1.4.0 and 1.4.1 due to the incorrect results, and open a new issue to track better handling of the unaligned data. Seem reasonable?

Sounds good to me.

In our use case, we have a customized file format that stores Vec<Bytes>. The Bytes portion uses xxhash for checksum and can be large. Unaligned access is common therefore important. So I'd like to see it fixed soon. I might want to try again fixing it.

Created new issue #33

	fn same_results_as_c_with_offset_for_32_bit(seed: u32, (data, offset) in data_and_offset()) {
	let data = &data[offset..];
	let our_result = hash_once(XxHash32::with_seed(seed), data);
	let their_result = c_xxhash::hash32(data, seed);

	our_result == their_result as u64
	}