Insert into Indexmap randomly fails

[SamJBarney]

Out of every 4 test runs I get the following error at least once:

thread 'block::block::tests::potential_block_states::retrieves_state_correctly' panicked at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\indexmap-2.2.6\src\map\core.rs:45:35:
index out of bounds: the len is 0 but the index is 0
stack backtrace:
   0:     0x7ff73c49eaf8 - std::backtrace_rs::backtrace::dbghelp64::trace
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\..\..\backtrace\src\backtrace\dbghelp64.rs:91
   1:     0x7ff73c49eaf8 - std::backtrace_rs::backtrace::trace_unsynchronized
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\..\..\backtrace\src\backtrace\mod.rs:66    
   2:     0x7ff73c49eaf8 - std::sys_common::backtrace::_print_fmt
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\sys_common\backtrace.rs:68
   3:     0x7ff73c49eaf8 - std::sys_common::backtrace::_print::impl$0::fmt
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\sys_common\backtrace.rs:44
   4:     0x7ff73c4bca59 - core::fmt::rt::Argument::fmt
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\fmt\rt.rs:165
   5:     0x7ff73c4bca59 - core::fmt::write
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\fmt\mod.rs:1157
   6:     0x7ff73c49afa1 - std::io::Write::write_fmt<alloc::vec::Vec<u8,alloc::alloc::Global> >
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\io\mod.rs:1832
   7:     0x7ff73c49e8d6 - std::sys_common::backtrace::print
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\sys_common\backtrace.rs:34
   8:     0x7ff73c4a10f8 - std::panicking::default_hook::closure$1
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:271
   9:     0x7ff73c4a0cdd - std::panicking::default_hook
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:295
  10:     0x7ff73c385e22 - alloc::boxed::impl$50::call
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\alloc\src\boxed.rs:2036
  11:     0x7ff73c385e22 - test::test_main::closure$0
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\test\src\lib.rs:137
  12:     0x7ff73c4a1657 - alloc::boxed::impl$50::call
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\alloc\src\boxed.rs:2036
  13:     0x7ff73c4a1657 - std::panicking::rust_panic_with_hook
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:799
  14:     0x7ff73c4a14e7 - std::panicking::begin_panic_handler::closure$0
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:664
  15:     0x7ff73c49f46f - std::sys_common::backtrace::__rust_end_short_backtrace<std::panicking::begin_panic_handler::closure_env$0,never$> 
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\sys_common\backtrace.rs:171
  16:     0x7ff73c4a1198 - std::panicking::begin_panic_handler
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:652
  17:     0x7ff73c4ccb74 - core::panicking::panic_fmt
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\panicking.rs:72
  18:     0x7ff73c4cccfe - core::panicking::panic_bounds_check
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\panicking.rs:275
  19:     0x7ff73c330adc - indexmap::map::core::equivalent::closure$0<opencraft_api::util::resource_location::ResourceLocation,alloc::sync::Arc<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::alloc::Global>,opencraft_api::util::resource_location::Reso
                               at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\indexmap-2.2.6\src\map\core.rs:45      
  20:     0x7ff73c332297 - hashbrown::raw::inner::RawTableInner::find_or_find_insert_slot_inner
                               at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\hashbrown-0.14.5\src\raw\mod.rs:1983   
  21:     0x7ff73c330c55 - indexmap::map::core::IndexMapCore<opencraft_api::util::resource_location::ResourceLocation,alloc::sync::Arc<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::alloc::Global> >::find_or_insert
                               at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\indexmap-2.2.6\src\map\core\raw.rs:67  
  22:     0x7ff73c330c55 - indexmap::map::core::IndexMapCore<opencraft_api::util::resource_location::ResourceLocation,alloc::sync::Arc<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::alloc::Global> >::insert_full<opencraft_api::util::resource_location
                               at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\indexmap-2.2.6\src\map\core.rs:338     
  23:     0x7ff73c3228aa - indexmap::map::IndexMap<opencraft_api::util::resource_location::ResourceLocation,alloc::sync::Arc<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::alloc::Global>,std::hash::random::RandomState>::insert_full
                               at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\indexmap-2.2.6\src\map.rs:415
  24:     0x7ff73c3228aa - indexmap::map::IndexMap<opencraft_api::util::resource_location::ResourceLocation,alloc::sync::Arc<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::alloc::Global>,std::hash::random::RandomState>::insert
                               at C:\Users\samjb\.cargo\registry\src\index.crates.io-6f17d22bba15001f\indexmap-2.2.6\src\map.rs:398
  25:     0x7ff73c3228aa - opencraft_api::registry::simple_registry::SimpleRegistry<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::sync::Arc<dyn$<opencraft_api::block::block_state::block_state_def::BlockStateDef>,alloc::alloc::Global> >::register<dyn
                               at C:\Users\samjb\Projects\Rust\opencraft-api\src\registry\simple_registry.rs:126
  26:     0x7ff73c33583d - opencraft_api::block::block::tests::setup_registry
                               at C:\Users\samjb\Projects\Rust\opencraft-api\src\block\block.rs:226
  27:     0x7ff73c3343df - opencraft_api::block::block::tests::potential_block_states::retrieves_state_correctly
                               at C:\Users\samjb\Projects\Rust\opencraft-api\src\block\block.rs:278
  28:     0x7ff73c32da0d - opencraft_api::block::block::tests::potential_block_states::retrieves_state_correctly::closure$0
                               at C:\Users\samjb\Projects\Rust\opencraft-api\src\block\block.rs:277
  29:     0x7ff73c32da0d - core::ops::function::FnOnce::call_once<opencraft_api::block::block::tests::potential_block_states::retrieves_state_correctly::closure_env$0,tuple$<> >
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081\library\core\src\ops\function.rs:250
  30:     0x7ff73c38c8c0 - core::ops::function::FnOnce::call_once
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\ops\function.rs:250
  31:     0x7ff73c38c8c0 - test::__rust_begin_short_backtrace<enum2$<core::result::Result<tuple$<>,alloc::string::String> >,enum2$<core::result::Result<tuple$<>,alloc::string::String> > (*)()>
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\test\src\lib.rs:623
  32:     0x7ff73c38b7e2 - test::run_test::closure$0
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\test\src\lib.rs:569
  33:     0x7ff73c34b7eb - test::run_test::closure$1
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\test\src\lib.rs:597
  34:     0x7ff73c34b7eb - std::sys_common::backtrace::__rust_begin_short_backtrace<test::run_test::closure_env$1,tuple$<> >
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\sys_common\backtrace.rs:155
  35:     0x7ff73c35117d - std::thread::impl$0::spawn_unchecked_::closure$2::closure$0
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\thread\mod.rs:542
  36:     0x7ff73c35117d - core::panic::unwind_safe::impl$25::call_once
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\panic\unwind_safe.rs:272
  37:     0x7ff73c35117d - std::panicking::try::do_call
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:559
  38:     0x7ff73c35117d - std::panicking::try
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panicking.rs:523
  39:     0x7ff73c35117d - std::panic::catch_unwind
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\panic.rs:149
  40:     0x7ff73c35117d - std::thread::impl$0::spawn_unchecked_::closure$2
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\thread\mod.rs:541
  41:     0x7ff73c35117d - core::ops::function::FnOnce::call_once<std::thread::impl$0::spawn_unchecked_::closure_env$2<test::run_test::closure_env$1,tuple$<> >,tuple$<> >
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\core\src\ops\function.rs:250
  42:     0x7ff73c4ac87d - alloc::boxed::impl$48::call_once
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\alloc\src\boxed.rs:2022
  43:     0x7ff73c4ac87d - alloc::boxed::impl$48::call_once
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\alloc\src\boxed.rs:2022
  44:     0x7ff73c4ac87d - std::sys::pal::windows::thread::impl$0::new::thread_start
                               at /rustc/129f3b9964af4d4a709d1383930ade12dfe7c081/library\std\src\sys\pal\windows\thread.rs:52
  45:     0x7ffd7f82257d - BaseThreadInitThunk
  46:     0x7ffd815aaf28 - RtlUserThreadStart

[cuviper]

Is it always those exact numbers, the len is 0 but the index is 0? That backtrace looks like the raw table thinks it has an item, but the vector is empty.

Is there anything else "weird" going on during your tests, like panics? I'm guessing that we might get into a bad state if some user code like Hash or Equivalent panicked, and then you continued using the map elsewhere. I hope even then that it's not UB-bad though.

Is your test suite available for others to run to reproduce this problem?

[cuviper]

Also, can your tests run under cargo miri? And if so, does that report any problems?

[SamJBarney]

I'm thinking it may have to do with me using Lazy to wrap the object that contains the indexmap. I'm gonna rework my code to not use it and see if that makes a difference. If it doesn't I'll make my test suite available so you can take a look at what's going on.

Currently on a windows box, so miri isn't available. I'll see if I can wrangle a linux or mac setup

[SamJBarney]

I've reworked my code to not use once_cell::sync::Lazy and this has fixed the issue. So something about Lazy is causing inconsistencies with Indexmap. Sorry for the false failure!

[cuviper]

Ok! I would still be interested in seeing the reproducer, if possible, to see if I can track down the problem in Lazy -- especially in my @rust-lang/libs role since that has also been ported to std::sync::LazyLock.

[SamJBarney]

Manged to get a branch back into the failure state: https://gitlab.com/open-craft/opencraft/-/tree/reproduction-branch?ref_type=heads

[cuviper]

I believe your static mut registries are primarily to blame, because DerefMut for Lazy doesn't do any synchronization -- having &mut Lazy already implies exclusive access by all Rust rules. Even after lazy initialization, any mutating access to your registries may be racing between threads, unless you have some other synchronization that I missed. This is what makes static mut require unsafe for all access.

For example, in setup_registry (frame 26 in your backtrace), multiple tests may be running in parallel and call that at the same time. The first BLOCK_STATES.is_locked() is an immutable Deref, so Lazy will do the right synchronization there to initialize it. However, then multiple tests may observe !is_locked() and proceed to the mutating register calls at the same time, before any of them get to the final lock().

std::sync::LazyLock does not offer DerefMut, which has some discussion in rust-lang/rust#109736. But even if it did, the safety burden would still be on you for a static mut. Alternatively, using static Mutex or static RwLock would be safe.

[SamJBarney]

Ah, so the issue was that the tests were being run in parallel. Gotcha

[cuviper]

Yes, but it is also a hazard for regular use of your API if it may be called from multiple threads.