Strange Miri error with pointer offset out of bounds in primal-sieve

[saethlin]

I've been running cargo miri test on a lot of crates. Usually when Miri says it has found undefined behavior I can at least get some idea of what's going on, but I'm really stumped on this one.

I ran cargo miri test on primal-estimate on the latest commit (Miri is very slow, so whether the primal-sieve test suite detects this I don't have the patience to wait for it at the moment). I get an error that says:

   --> /home/ben/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:307:18
    |
307 |         unsafe { intrinsics::offset(self, count) as *mut T }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pointer arithmetic failed: alloc117012 has size 32768, so pointer to 3 bytes starting at offset 32766 is out-of-bounds
    |
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

    = note: inside `std::ptr::mut_ptr::<impl *mut u8>::offset` at /home/ben/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:307:18
    = note: inside `primal_sieve::wheel::wheel30::hardcoded_sieve` at /tmp/primal/primal-sieve/src/wheel/wheel30.rs:822:31
    = note: inside `<primal_sieve::wheel::wheel30::Wheel30 as primal_sieve::wheel::Wheel>::hardcoded_sieve` at /tmp/primal/primal-sieve/src/wheel/wheel30.rs:23:9
    = note: inside `primal_sieve::wheel::State::<primal_sieve::wheel::wheel30::Wheel30>::sieve_hardcoded` at /tmp/primal/primal-sieve/src/wheel/mod.rs:210:13
    = note: inside `primal::StreamingSieve::small_primes_sieve::<primal_sieve::wheel::wheel30::Wheel30>` at /tmp/primal/primal-sieve/src/streaming/mod.rs:200:13
    = note: inside `primal::StreamingSieve::next` at /tmp/primal/primal-sieve/src/streaming/mod.rs:251:9
    = note: inside `primal::Sieve::new` at /tmp/primal/primal-sieve/src/sieve.rs:69:45
note: inside `tests::nth_prime` at primal-estimate/src/lib.rs:212:21
   --> primal-estimate/src/lib.rs:212:21
    |
212 |         let sieve = Sieve::new(1_000_000);
    |                     ^^^^^^^^^^^^^^^^^^^^^

What really confuses me is the pointer to 3 bytes. As far as I can tell the pointer in use here is a *const u8. But this error seems to suggest that it's a *const [u8; 3]. I'm probably just getting lost in the implementation of hardcoded_sieve.

If this Miri error is correct, I think this is UB. Rust permits computing the one-past-the-end pointer, but not dereferencing it. But I think the error message says the pointer is straddling the end of the array, so it doesn't qualify as a one-past-the-end pointer, even though its pointee extends one byte past the end of what I think is an array of u8.

I don't think there is a dereference of a pointer at an invalid offset. The test suite passes with Address Sanitizer.

If this is confusing to you as well, do you think there is anything Miri could say that would make this easier to understand?

[cuviper]

That call at wheel30.rs:822 is p.offset(prime_ * 4 + 3), so I think this is where the pointer to 3 bytes comes from. I used some dbg! prints to see that we have prime_ == 0 in the failing case, and with p only two bytes from the end of the allocation, then indeed p.offset(3) is invalid.

I don't think there is a dereference of a pointer at an invalid offset.

I think wrapping_offset suits this case, where a pointer may stray out of bounds as long as its not dereferenced. That could potentially have a performance impact, assuming LLVM is making any sense of all this wheel logic. Another alternative is to allocate some unused padding, so we have room for the maximal offset to go past the end of the real data.

[saethlin]

I did a find-and-replace to wrapping_offset and I don't find any consistent change in the benchmarks, just small spurious changes.

Though I can't figure out how to operate the generators. I'm very much a drive-by contributor here, so while I wouldn't mind learning how this all works, it might be faster for you to make the change yourself 😅.

[cuviper]

If you could check #36, that would be great!