error: Undefined Behavior: attempting a read access using <981690> at alloc412474[0x0], but that tag does not exist in the borrow stack for this location.

[michaelgrigoryan25]

The rustfft::accuracy test_planned_fft_forward_f32 reports undefined behavior, and from what it seems like, it is coming from butterfles.rs. Here is the full stacktrace generated by rust-lang/miri:

FAIL [   3.042s] rustfft::accuracy test_planned_fft_forward_f32         

--- STDOUT:              rustfft::accuracy test_planned_fft_forward_f32 ---

running 1 test
test test_planned_fft_forward_f32 ... 
--- STDERR:              rustfft::accuracy test_planned_fft_forward_f32 ---
error: Undefined Behavior: attempting a read access using <981690> at alloc412474[0x0], but that tag does not exist in the borrow stack for this location
   --> /root/build/src/array_utils.rs:64:9
    |
64  |         *self.ptr.add(index)
    |         ^^^^^^^^^^^^^^^^^^^^
    |         |
    |         attempting a read access using <981690> at alloc412474[0x0], but that tag does not exist in the borrow stack for this location
    |         this error occurs as part of an access at alloc412474[0x0..0x8]
    |
    = 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: <981690> was created by a SharedReadOnly retag at offsets [0x0..0x20]
   --> /root/build/src/array_utils.rs:37:18
    |
37  |             ptr: slice.as_ptr(),
    |                  ^^^^^^^^^^^^^^
help: <981690> was later invalidated at offsets [0x0..0x20] by a Unique FnEntry retag inside this call
   --> /root/build/src/algorithm/butterflies.rs:221:1
    |
221 | boilerplate_fft_butterfly!(Butterfly4, 4, |this: &Butterfly4<_>| this.direction);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: BACKTRACE:
    = note: inside `rustfft::array_utils::RawSlice::<rustfft::num_complex::Complex<f32>>::load` at /root/build/src/array_utils.rs:64:9
note: inside `rustfft::algorithm::butterflies::Butterfly4::<f32>::perform_fft_contiguous` at /root/build/src/algorithm/butterflies.rs:240:26
   --> /root/build/src/algorithm/butterflies.rs:240:26
    |
240 |         let mut value0 = input.load(0);
    |                          ^^^^^^^^^^^^^
note: inside `rustfft::algorithm::butterflies::Butterfly4::<f32>::perform_fft_butterfly` at /root/build/src/algorithm/butterflies.rs:17:17
   --> /root/build/src/algorithm/butterflies.rs:221:1
    |
221 | boilerplate_fft_butterfly!(Butterfly4, 4, |this: &Butterfly4<_>| this.direction);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at /root/build/src/algorithm/butterflies.rs:61:21
   --> /root/build/src/algorithm/butterflies.rs:221:1
    |
221 | boilerplate_fft_butterfly!(Butterfly4, 4, |this: &Butterfly4<_>| this.direction);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `rustfft::array_utils::iter_chunks::<rustfft::num_complex::Complex<f32>, [closure@<rustfft::algorithm::butterflies::Butterfly4<f32> as rustfft::Fft<f32>>::process_with_scratch::{closure#0}]>` at /root/build/src/array_utils.rs:155:9
   --> /root/build/src/array_utils.rs:155:9
    |
155 |         chunk_fn(head);
    |         ^^^^^^^^^^^^^^
note: inside `<rustfft::algorithm::butterflies::Butterfly4<f32> as rustfft::Fft<f32>>::process_with_scratch` at /root/build/src/algorithm/butterflies.rs:60:30
   --> /root/build/src/algorithm/butterflies.rs:221:1
    |
221 | boilerplate_fft_butterfly!(Butterfly4, 4, |this: &Butterfly4<_>| this.direction);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `rustfft::algorithm::Radix4::<f32>::perform_fft_out_of_place` at /root/build/src/algorithm/radix4.rs:117:9
   --> /root/build/src/algorithm/radix4.rs:117:9
    |
117 |         self.base_fft.process_with_scratch(spectrum, &mut []);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at /root/build/src/common.rs:126:21
   --> /root/build/src/algorithm/radix4.rs:145:1
    |
145 | boilerplate_fft_oop!(Radix4, |this: &Radix4<_>| this.len);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `rustfft::array_utils::iter_chunks::<rustfft::num_complex::Complex<f32>, [closure@<rustfft::algorithm::Radix4<f32> as rustfft::Fft<f32>>::process_with_scratch::{closure#0}]>` at /root/build/src/array_utils.rs:155:9
   --> /root/build/src/array_utils.rs:155:9
    |
155 |         chunk_fn(head);
    |         ^^^^^^^^^^^^^^
note: inside `<rustfft::algorithm::Radix4<f32> as rustfft::Fft<f32>>::process_with_scratch` at /root/build/src/common.rs:125:30
   --> /root/build/src/algorithm/radix4.rs:145:1
    |
145 | boilerplate_fft_oop!(Radix4, |this: &Radix4<_>| this.len);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `rustfft::algorithm::BluesteinsAlgorithm::<f32>::new` at /root/build/src/algorithm/bluesteins_algorithm.rs:85:9
   --> /root/build/src/algorithm/bluesteins_algorithm.rs:85:9
    |
85  |         inner_fft.process_with_scratch(&mut inner_fft_input, &mut inner_fft_scratch);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `ControlCache::<f32>::plan_fft` at tests/accuracy.rs:103:18
   --> tests/accuracy.rs:103:18
    |
103 |         Arc::new(BluesteinsAlgorithm::new(len, inner_fft))
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `test_planned_fft_forward_f32` at tests/accuracy.rs:117:23
   --> tests/accuracy.rs:117:23
    |
117 |         let control = cache.plan_fft(len);
    |                       ^^^^^^^^^^^^^^^^^^^
note: inside closure at tests/accuracy.rs:112:1
   --> tests/accuracy.rs:112:1
    |
111 |   #[test]
    |   ------- in this procedural macro expansion
112 | / fn test_planned_fft_forward_f32() {
113 | |     let direction = FftDirection::Forward;
114 | |     let cache: ControlCache<f32> = ControlCache::new(TEST_MAX, direction);
115 | |
...   |
123 | |     }
124 | | }
    | |_^
    = note: this error originates in the macro `boilerplate_fft_butterfly` which comes from the expansion of the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error

[WalterSmuts]

but the Stacked Borrows rules it violated are still experimental

Note: the stacked borrow rules are still pretty experimental. I haven't investigated the issue further, but if someone makes the effort they should keep in mind that this could be a false positive.

[michaelgrigoryan25]

Definitely could be a false positive, agree.

[HEnquist]

I tried this quickly yesterday and got the same error on *self.ptr.add(index) in array_utils.rs, but called from a completely different place. The stuff in array_utils.rs is quite simple, don't really see how it could manage to do something unexpected. Especially while still producing the correct results in all tests.

[ejmahler]

Is this running within miri? If so, it's possible that we're relying on some undefined behavior that ends up producing the correct result in final compiled code.

[ejmahler]

One obvious source of undefined behavior is that we deliberately create an aliasing mutable pointer. butterflies.rs line 16:

pub(crate) unsafe fn perform_fft_butterfly(&self, buffer: &mut [Complex<T>]) {
    self.perform_fft_contiguous(RawSlice::new(buffer), RawSliceMut::new(buffer));
}

I wanted to reuse the same code for inplace and out of place butterflies, since aside from which pointer you're writing to it's always the same logic. So this little bit has been chugging away for 2 and a half years to just pass a single pointer to the underlying code as both the immutable input and mutable output. That way, the in-place transform can go through this path, and the out-of-place transform can directly call self.perform_fft_contiguous.

It's a night-and-day convenience improvement, but I wouldn't be the least bit surprised if this was the underlying problem miri was complaining about. If so, we should find a way to move away from this code.

[michaelgrigoryan25]

Is this running within miri? If so, it's possible that we're relying on some undefined behavior that ends up producing the correct result in final compiled code.

Exactly. This code was indeed running inside of miri.

[WalterSmuts]

Is this running within miri? If so, it's possible that we're relying on some undefined behavior that ends up producing the correct result in final compiled code.

I'm not sure this is valid reasoning. If things are "working" during UB for a set of tests, on a set of platforms for a specific configurations, it does not mean it will work for other untested tests, platforms or configurations. From the wiki:

In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior, for which the language specification does not prescribe a result, and implementation-defined behavior that defers to the documentation of another component of the platform (such as the ABI or the translator documentation).

I believe you're arguing that the behaviour is "defined" by the tests, even though the compiler hits something it determines as UB. AFAIK it's much more complicated than that.

UB is an indication that some invariant IS being broken. It working for a set of specific configurations does not rule out all configurations. It could be that it will produce incorrect results when:

• Compiler optimisations are applied
• Targeting a different platform
• Running with untested input
• Slight changes are made to the source code, subtly changing the output binary
• Using a different version of rustc
• Just compiling again (I don't think the compiler is necessarily deterministic)

I'm not convinced that this is not a false positive though. But if this IS UB, then it's definitely something that should be addressed.

[michaelgrigoryan25]

To add to @WalterSmuts's comments, this might also be unsound behavior (though I highly doubt that miri would have reported such a case). From "Behavior considered undefined" in Rust's documentation:

unsafe code that satisfies this property for any safe client is called sound; if unsafe code can be misused by safe code to exhibit undefined behavior, it is unsound.

Deterministic compilation is not quite there yet, but there is a moderate amount of work being put into it. Check out https://github.com/rust-lang/rust/labels/A-reproducibility.

[WalterSmuts]

I've looked a bit into this and it stems from the RawSlice and RawSliceMut structs in the array_utils module. From the documentation:

/// A RawSliceMut is a normal mutable slice, but aliasable. Its functionality is severely limited.
#[derive(Copy, Clone)]
pub struct RawSliceMut<T> {
    ptr: *mut T,
    slice_len: usize,
}

This seems to intentionally violate a pretty fundamental invariant in rust. AFAICT it's to de-duplicate the logic that does the in-place and out of place fft's.

[ejmahler]

I'm open to fixing this. I'm resistant to (but still not entirely ruling out) re-duplicating all of that code, because of the maintenance burden it'd place on the butterfly portion of the project. But if there's another solution I'll gladly take it.

[WalterSmuts]

I don't think this issue should be closed.

[groscoe2]

@ejmahler I believe I've figured out a good solution to remove the usage of RawSlice and RawSliceMut from butterflies.rs and put together PR #113. Please let me know what you think!

[ejmahler]

PR merged! Thanks to @michaelgrigoryan25 for reporting this, thanks to @WalterSmuts and @HEnquist for contributing some research, and thanks to @groscoe2 for implementing the solution!