UB in Default impl of GenericArray

[Robbepop]

Today I was running cargo miri test on one of my projects that is using the generic-array crate internally. The cargo miri test runs tests of the project using the Rust MIR interpreter miri. Due to execution the tool is sometimes able to detect undefined behaviour in Rust code upon execution - however, there might be false positives.

The output of miri's execution:

error: Undefined Behavior: type validation failed: encountered uninitialized bytes at .value.data.parent1.parent1.data, but expected a valid enum discriminant
   --> /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/maybe_uninit.rs:502:34
    |
502 |         ManuallyDrop::into_inner(self.value)
    |                                  ^^^^^^^^^^ type validation failed: encountered uninitialized bytes at .value.data.parent1.parent1.data, but expected a valid enum discriminant
    |
    = 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::mem::MaybeUninit::<generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>>::assume_init` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/maybe_uninit.rs:502:34
    = note: inside `std::mem::uninitialized::<generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/mod.rs:664:5
    = note: inside `generic_array::ArrayBuilder::<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at /home/.cargo/registry/src/gh.neting.cc-1ecc6299db9ec823/generic-array-0.13.2/src/lib.rs:187:38
    = note: inside `<generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>> as generic_array::sequence::GenericSequence<std::option::Option<storage2::lazy::entry::Entry<u8>>>>::generate::<[closure@DefId(32:51 ~ generic_array[53b7]::impls[0]::{{impl}}[0]::default[0]::{{closure}}[0])]>` at /home/.cargo/registry/src/gh.neting.cc-1ecc6299db9ec823/generic-array-0.13.2/src/lib.rs:344:35
    = note: inside `generic_array::impls::<impl std::default::Default for generic_array::GenericArray<std::option::Option<storage2::lazy::entry::Entry<u8>>, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>>::default` at /home/.cargo/registry/src/gh.neting.cc-1ecc6299db9ec823/generic-array-0.13.2/src/impls.rs:17:9
note: inside `storage2::lazy::lazy_array::EntryArray::<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at core/src/storage2/lazy/lazy_array.rs:109:22
   --> core/src/storage2/lazy/lazy_array.rs:109:22
    |
109 |             entries: Default::default(),
    |                      ^^^^^^^^^^^^^^^^^^
note: inside `<storage2::lazy::lazy_array::EntryArray<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>> as std::default::Default>::default` at core/src/storage2/lazy/lazy_array.rs:119:9
   --> core/src/storage2/lazy/lazy_array.rs:119:9
    |
119 |         Self::new()
    |         ^^^^^^^^^^^
note: inside `storage2::lazy::lazy_array::LazyArray::<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at core/src/storage2/lazy/lazy_array.rs:182:45
   --> core/src/storage2/lazy/lazy_array.rs:182:45
    |
182 |             cached_entries: UnsafeCell::new(Default::default()),
    |                                             ^^^^^^^^^^^^^^^^^^
note: inside `<storage2::lazy::lazy_array::LazyArray<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>> as std::default::Default>::default` at core/src/storage2/lazy/lazy_array.rs:165:9
   --> core/src/storage2/lazy/lazy_array.rs:165:9
    |
165 |         Self::new()
    |         ^^^^^^^^^^^
note: inside `storage2::collections::smallvec::SmallVec::<u8, typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UInt<typenum::uint::UTerm, typenum::bit::B1>, typenum::bit::B0>, typenum::bit::B0>>::new` at core/src/storage2/collections/smallvec/mod.rs:79:20
   --> core/src/storage2/collections/smallvec/mod.rs:79:20
    |
79  |             elems: Default::default(),
    |                    ^^^^^^^^^^^^^^^^^^
note: inside `storage2::collections::smallvec::tests::first_last_of_empty` at core/src/storage2/collections/smallvec/tests.rs:61:19
   --> core/src/storage2/collections/smallvec/tests.rs:61:19
    |
61  |     let mut vec = <SmallVec<u8, U4>>::new();
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at core/src/storage2/collections/smallvec/tests.rs:60:1
   --> core/src/storage2/collections/smallvec/tests.rs:60:1
    |
60  | / fn first_last_of_empty() {
61  | |     let mut vec = <SmallVec<u8, U4>>::new();
62  | |     assert_eq!(vec.first(), None);
63  | |     assert_eq!(vec.first_mut(), None);
64  | |     assert_eq!(vec.last(), None);
65  | |     assert_eq!(vec.last_mut(), None);
66  | | }
    | |_^
    = note: inside `<[closure@core/src/storage2/collections/smallvec/tests.rs:60:1: 66:2] as std::ops::FnOnce<()>>::call_once - shim` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ops/function.rs:232:5
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ops/function.rs:232:5
    = note: inside `test::__rust_begin_short_backtrace::<fn()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:517:5
    = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:508:30
    = note: inside `<[closure@DefId(38:631 ~ test[140d]::run_test[0]::{{closure}}[2]) 0:fn()] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/ops/function.rs:232:5
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/boxed.rs:1008:9
    = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:318:9
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:331:40
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:274:15
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:14
    = note: inside `test::run_test_in_process` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:541:18
    = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:450:39
    = note: inside `test::run_test::run_test_inner` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:475:13
    = note: inside `test::run_test` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:505:28
    = note: inside `test::run_tests::<[closure@DefId(38:230 ~ test[140d]::console[0]::run_tests_console[0]::{{closure}}[2]) 0:&mut test::console::ConsoleTestState, 1:&mut std::boxed::Box<dyn test::formatters::OutputFormatter>]>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:284:13
    = note: inside `test::run_tests_console` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/console.rs:280:5
    = note: inside `test::test_main` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:120:15
    = note: inside `test::test_main_static` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libtest/lib.rs:139:5
    = note: inside `main`
    = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:34
    = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:73
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<[closure@DefId(1:6025 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/sys_common/backtrace.rs:130:5
    = note: inside closure at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:13
    = note: inside `std::panicking::r#try::do_call::<[closure@DefId(1:6024 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:331:40
    = note: inside `std::panicking::r#try::<i32, [closure@DefId(1:6024 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:274:15
    = note: inside `std::panic::catch_unwind::<[closure@DefId(1:6024 ~ std[1995]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:14
    = note: inside `std::rt::lang_start_internal` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:51:25
    = note: inside `std::rt::lang_start::<()>` at /home/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:5
    = note: this error originates in an attribute macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

So it seems to be a problem with uninitialized data in the Default implementation of GenericArray where it is using a ManuallyDrop with uninitialized data.

This is the test code that triggered the UB of my crate that is using generic-array:
https://github.com/paritytech/ink/blob/redo-init-and-flush/core/src/storage2/collections/smallvec/tests.rs#L60

I belive the problem is somewhere in this method:
https://github.com/fizyk20/generic-array/blob/master/src/lib.rs#L207
The array field is of type MaybeUninit and during the loop in fn generate (same file) the underlying array is initialized. However, in the linked method no call to assume_init is made and instead a core::mem::ptr::read is performed on the potentially uninitialized array contents. This doesn't necessarily need to be wrong, however, it could be that it confuses miri.

[novacrazy]

Ouch. Okay, I'll prioritize fixing these UB issues tomorrow.

[Robbepop]

Just added a comment:

This is the test code that triggered the UB of my crate that is using generic-array:
https://github.com/paritytech/ink/blob/redo-init-and-flush/core/src/storage2/collections/smallvec/tests.rs#L60

I belive the problem is somewhere in this method:
https://github.com/fizyk20/generic-array/blob/master/src/lib.rs#L207
The array field is of type MaybeUninit and during the loop in fn generate (same file) the underlying array is initialized. However, in the linked method no call to assume_init is made and instead a core::mem::ptr::read is performed on the potentially uninitialized array contents. This doesn't necessarily need to be wrong, however, it could be that it confuses miri.

Note that we could eventually make use of the https://crates.io/crates/array_init crate since its purpose is to initialize arrays which effectively is happening in this routine. I have also implicitely tested the array_init crate using miri and it seems to be working fine without UB.

I have also tried to run cargo miri test directly on generic-array but unfortunately for some reason miri did nothing there.

[novacrazy]

Would you try adding the latest master branch to your project to double check that the current changes fix your issue? Running miri on generic-array's own tests as of the latest master branch is all good. (aside from panicking stuff that is unimplemented in miri)

Replace:
generic-array = "0.13"
with
generic-array = { git = "https://github.com/fizyk20/generic-array" }
in your Cargo.toml

[Robbepop]

I can confirm using your branch I no longer see the undefined behaviour via cargo miri test. :)

[novacrazy]

Should be fixed in 0.14.0. Please reopen if the issue persists.

[twitchyliquid64]

I'll note that on Rust 1.48.0 on embedded arm systems, specifically ARM thumbv7em-none-eabihf, 0.13.0 now panics if you call default(). Unclear if it always panics or only when the structure doesnt align to a word. Upgrading to 0.14.0 fixes the problem.