wasm-opt(Windows): child not found in parent, UNREACHABLE executed

[mtb0x1]

I am facing a bug I can reproduce only on Windows (on Linux no warning and everything seems to be fine).

Binaryen version : 117
Command to reproduce :

wasm-opt --enable-reference-types --enable-bulk-memory --strip -O3 core.wasm -o core_opt.wasm

Result :

child not found in parent
UNREACHABLE executed at D:\a\binaryen\binaryen\src\passes\Precompute.cpp:838!

• Using a release build (with MSVC) of HEAD(f8086ad) results into the same error message. (tested only on Windows)
• Using Binaryen version 116, no issues on Windows and Linux.
• Wasm file core.zip.
• Source code of the wasm file can be found here.

[kripken]

Very strange that there would be a windows-specific bug. Perhaps undefined behavior in some C++ STL stuff?

I don't have a windows machine so this would be hard for me to investigate. Can you perhaps reduce this with wasm-reduce? A tiny testcase might be much easier to reason about.

[mtb0x1]

@kripken I did some digging and found out that -O2 and -O3 cause this behavior (-O1 works fine). bisecting commits lead me to this commit 141f7ca (someone already made a comment on the commit but he didn't follow up I guess).

I will see what I can do for/with wasm-reduce.

[cyk2018]

It seems item (with index i) in your stack is not the child of item(with index i - 1).

[kripken]

I don't have a guess as to what could be going wrong in the code, very strange - there should be no way for the child not to have a proper parent. That this only happens on windows makes me wonder if this is a compiler bug. Which compilers do you see this with? I'd be especially interested in comparing MSVC, clang, and clang+libc++ (the last would not be using the system C++ libraries).

Reducing could still help here, but if this is a compiler bug then the more important thing might be to narrow this down to which compiler and version it happens on.

[cyk2018]

Yes, very strange! maybe we can wait for more information.

[radekdoulik]

I see it when using wasm-opt from binaryen version_117 on windows too:

  [1/5] Building C object CMakeFiles/dotnet.native.dir/driver.c.o
  [2/5] Building C object CMakeFiles/dotnet.native.dir/corebindings.c.o
  [3/5] Building C object CMakeFiles/dotnet.native.dir/runtime.c.o
  [4/5] Building C object CMakeFiles/dotnet.native.dir/pinvoke.c.o
  [5/5] Linking C executable dotnet.native.js
  FAILED: dotnet.native.js 
  C:\Windows\system32\cmd.exe /C "cd . && D:\a\_work\1\s\src\mono\browser\emsdk\emscripten\emcc.bat -O3 -DNDEBUG @D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/src/emcc-default.rsp @D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/src/emcc-link.rsp -O2 -s EXPORT_ES6=1 -lexports.js -msimd128 --emit-symbol-map --pre-js D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/src/es6/dotnet.es6.pre.js --js-library D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/src/es6/dotnet.es6.lib.js --extern-post-js D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/src/es6/dotnet.es6.extpost.js CMakeFiles/dotnet.native.dir/runtime.c.o CMakeFiles/dotnet.native.dir/corebindings.c.o CMakeFiles/dotnet.native.dir/driver.c.o CMakeFiles/dotnet.native.dir/pinvoke.c.o -o dotnet.native.js  D:/a/_work/1/s/.packages/microsoft.netcore.runtime.icu.transport/9.0.0-preview.6.24304.1/runtimes/browser-wasm/native/lib/libicuuc.a  D:/a/_work/1/s/.packages/microsoft.netcore.runtime.icu.transport/9.0.0-preview.6.24304.1/runtimes/browser-wasm/native/lib/libicui18n.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-component-hot_reload-static.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-component-debugger-static.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-component-diagnostics_tracing-stub-static.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-component-marshal-ilgen-static.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-ee-interp.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmonosgen-2.0.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-icall-table.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-wasm-eh-js.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-wasm-simd.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-profiler-aot.a  D:/a/_work/1/s/artifacts/bin/mono/browser.wasm.Release/libmono-profiler-browser.a  wasm-bundled-timezones.a  libSystem.Native.a  libSystem.Globalization.Native.a  libSystem.IO.Compression.Native.a && C:\Windows\system32\cmd.exe /C "cd /D D:\a\_work\1\s\artifacts\bin\native\net9.0-browser-Release-wasm && D:\a\_work\1\s\src\mono\browser\emsdk\bin\wasm-opt --enable-exception-handling --enable-simd --enable-bulk-memory --strip-dwarf D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/dotnet.native.wasm -o D:/a/_work/1/s/artifacts/bin/native/net9.0-browser-Release-wasm/dotnet.native.wasm""
  child not found in parent
  UNREACHABLE executed at D:\a\_work\1\s\src\passes\Precompute.cpp:838!
emcc : error : 'D:/a/_work/1/s/src/mono/browser/emsdk\bin\wasm-opt --strip-target-features --post-emscripten -O2 --low-memory-unused --zero-filled-memory --pass-arg=directize-initial-contents-immutable dotnet.native.wasm -o dotnet.native.wasm -g --mvp-features --enable-bulk-memory --enable-mutable-globals --enable-sign-ext --enable-simd' failed (returned 57005) [D:\a\_work\1\s\src\mono\browser\browser.proj]
##[error]emcc(0,0): error : (NETCORE_ENGINEERING_TELEMETRY=Build) 'D:/a/_work/1/s/src/mono/browser/emsdk\bin\wasm-opt --strip-target-features --post-emscripten -O2 --low-memory-unused --zero-filled-memory --pass-arg=directize-initial-contents-immutable dotnet.native.wasm -o dotnet.native.wasm -g --mvp-features --enable-bulk-memory --enable-mutable-globals --enable-sign-ext --enable-simd' failed (returned 57005)

[radekdoulik]

@kripken I did some digging and found out that -O2 and -O3 cause this behavior (-O1 works fine). bisecting commits lead me to this commit 141f7ca (someone already made a comment on the commit but he didn't follow up I guess).

I will see what I can do for/with wasm-reduce.

the -O1 works, because it doesn't hit the path with partially precompute

canPartiallyPrecompute = getPassOptions().optimizeLevel >= 2;

[mtb0x1]

@kripken

Just to make sure there is no miscommunication, the issue happens with :

• v117 (even v116 + up to 141f7ca)
• Available release version from this repo (unmodified)
• Debug/Release of HEAD built with MSVC 22 14.40.33807

So I guess this isn't a compiler issue since official release is built with mingw(?) and my version with MSVC.

I tried my best using wasm-reduce but I wasn't able to produce any useful result.

So I went through the rabbit hole of trying to debug this issue : (Disclaimer my C++ and Windows skills are a bit Rust-y and I might be missing things here)

• Stepping into debug mode and walking through execution ends up every-time in trap.
• Trying to debug 'print' using dump function, leads to scrambled output (multi-threading).
• I applied few changes as per the diff below, indicate a use after free. (or at least this what I observed)

Patch : (activate thread sanitizer + change the builtin trap for msvc compatibility )

diff --git a/CMakeLists.txt b/CMakeLists.txt
index fef45bfca..ec7375d46 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -204,6 +204,7 @@ if(MSVC)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index fef45bfca..ec7375d46 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -204,6 +204,7 @@ if(MSVC)
   if(NOT CMAKE_CXX_COMPILER_ID MATCHES "Clang")
     # multi-core build.
     add_compile_flag("/MP")
+       add_compile_flag("/fsanitize=address")
     if(CMAKE_CXX_COMPILER_VERSION VERSION_LESS "19.0")
       # VS2013 and older explicitly need /arch:sse2 set, VS2015 no longer has that option, but always enabled.
       add_compile_flag("/arch:sse2")
diff --git a/src/parser/CMakeLists.txt b/src/parser/CMakeLists.txt
index 9c54646e7..86c5f5a52 100644
--- a/src/parser/CMakeLists.txt
+++ b/src/parser/CMakeLists.txt
@@ -1,3 +1,6 @@
+if(MSVC)
+       add_compile_options(/bigobj)
+endif()
 FILE(GLOB parser_HEADERS *.h)
 set(parser_SOURCES
  context-decls.cpp
diff --git a/src/support/utilities.cpp b/src/support/utilities.cpp
index f051a1871..0e80b3ede 100644
--- a/src/support/utilities.cpp
+++ b/src/support/utilities.cpp
@@ -37,7 +37,8 @@ wasm::handle_unreachable(const char* msg, const char* file, unsigned line) {
   std::cerr << "!\n";
 #if __has_feature(address_sanitizer) || defined(__SANITIZE_ADDRESS__)
   __sanitizer_print_stack_trace();
-  __builtin_trap();
+  //__builtin_trap();
+  __debugbreak();
 #endif
 #endif
   abort();

Result :

=================================================================
==7356==ERROR: AddressSanitizer: stack-use-after-scope on address 0x009d8e7fe958 at pc 0x7ff7264d57eb bp 0x009d8e7fe7e0 sp 0x009d8e7fe7e8
READ of size 8 at 0x009d8e7fe958 thread T3
    #0 0x7ff7264d57ea in std::vector<class wasm::Expression **, class std::allocator<class wasm::Expression **>>::size(void) const C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\vector:1873
    #1 0x7ff7264d40cf in wasm::SmallVector<class wasm::Expression **, 4>::size(void) const C:\Users\user\Downloads\binaryen\src\support\small_vector.h:130
    #2 0x7ff727c86137 in wasm::SmallVector<class wasm::Expression **, 4>::end(void) C:\Users\user\Downloads\binaryen\src\support\small_vector.h:234
    #3 0x7ff727c871a9 in wasm::Precompute::getChildPointerInImmediateParent(class wasm::SmallVector<class wasm::Expression *, 10> const &, unsigned int, class wasm::Function *) C:\Users\user\Downloads\binaryen\src\passes\Precompute.cpp:861
    #4 0x7ff727c8c2a9 in wasm::Precompute::partiallyPrecompute(class wasm::Function *) C:\Users\user\Downloads\binaryen\src\passes\Precompute.cpp:595
    #5 0x7ff727c85772 in wasm::Precompute::doWalkFunction(class wasm::Function *) C:\Users\user\Downloads\binaryen\src\passes\Precompute.cpp:254
    #6 0x7ff727cd0d20 in wasm::Walker<struct wasm::Precompute, struct wasm::UnifiedExpressionVisitor<struct wasm::Precompute, void>>::walkFunctionInModule(class wasm::Function *, class wasm::Module *) C:\Users\user\Downloads\binaryen\src\wasm-traversal.h:189
    #7 0x7ff727c90c8f in wasm::WalkerPass<struct wasm::PostWalker<struct wasm::Precompute, struct wasm::UnifiedExpressionVisitor<struct wasm::Precompute, void>>>::runOnFunction(class wasm::Module *, class wasm::Function *) C:\Users\user\Downloads\binaryen\src\pass.h:551
    #8 0x7ff7268914ef in wasm::PassRunner::runPassOnFunction(class wasm::Pass *, class wasm::Function *) C:\Users\user\Downloads\binaryen\src\passes\pass.cpp:954
    #9 0x7ff726893421 in <lambda_04b97331b9ec1119494c5a0faab8c543>::operator() C:\Users\user\Downloads\binaryen\src\passes\pass.cpp:862
    #10 0x7ff72689e542 in std::invoke<<lambda_04b97331b9ec1119494c5a0faab8c543> &> C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\type_traits:1705
    #11 0x7ff7268937b9 in std::_Func_impl_no_alloc<<lambda_04b97331b9ec1119494c5a0faab8c543>,enum wasm::ThreadWorkState>::_Do_call C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\functional:876
    #12 0x7ff726d10a15 in std::_Func_class<enum wasm::ThreadWorkState>::operator()(void) const C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\functional:920
    #13 0x7ff726d0acbc in wasm::Thread::mainLoop(void *) C:\Users\user\Downloads\binaryen\src\support\threads.cpp:86
    #14 0x7ff726d0ed38 in std::invoke<void (__cdecl *)(void *), class wasm::Thread *>(void (__cdecl *&&)(void *), class wasm::Thread *&&) C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\type_traits:1715
    #15 0x7ff726d0e0b5 in std::thread::_Invoke<class std::tuple<void (__cdecl *)(void *), class wasm::Thread *>, 0, 1>(void *) C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\thread:60
    #16 0x7ffcbe11300f  (C:\windows\SYSTEM32\ucrtbased.dll+0x1800b300f)
    #17 0x7ffcbb6c48fe in __asan::AsanThread::ThreadStart(unsigned __int64) D:\a\_work\1\s\src\vctools\asan\llvm\compiler-rt\lib\asan\asan_thread.cpp:299
    #18 0x7ffd388c7343  (C:\windows\System32\KERNEL32.DLL+0x180017343)
    #19 0x7ffd39ca26b0  (C:\windows\SYSTEM32\ntdll.dll+0x1800526b0)

Address 0x009d8e7fe958 is located in stack of thread T3 at offset 88 in frame
    #0 0x7ff727c86e1f in wasm::Precompute::getChildPointerInImmediateParent(class wasm::SmallVector<class wasm::Expression *, 10> const &, unsigned int, class wasm::Function *) C:\Users\user\Downloads\binaryen\src\passes\Precompute.cpp:853

  This frame has 3 object(s):
    [32, 104) 'compiler temporary' <== Memory access at offset 88 is inside this variable
    [48, 64) '<begin>$L0'
    [64, 80) '<end>$L0' <== Memory access at offset 88 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp, SEH and C++ exceptions *are* supported)
Thread T3 created by T0 here:
    #0 0x7ffcbb6c6607 in __asan_wrap_CreateThread D:\a\_work\1\s\src\vctools\asan\llvm\compiler-rt\lib\asan\asan_win.cpp:167
    #1 0x7ffcbe11387e  (C:\windows\SYSTEM32\ucrtbased.dll+0x1800b387e)
    #2 0x7ff726d0e263 in std::thread::_Start<void (__cdecl &)(void *), class wasm::Thread *>(void (__cdecl &)(void *), class wasm::Thread *&&) C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\thread:78
    #3 0x7ff726d0c724 in std::thread::thread<void (__cdecl &)(void *), class wasm::Thread *, 0>(void (__cdecl &)(void *), class wasm::Thread *&&) C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\thread:93
    #4 0x7ff726d0efb3 in std::make_unique<class std::thread, void (__cdecl &)(void *), class wasm::Thread *, 0>(void (__cdecl &)(void *), class wasm::Thread *&&) C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\memory:3595
    #5 0x7ff726d0a794 in wasm::Thread::Thread(class wasm::ThreadPool *) C:\Users\user\Downloads\binaryen\src\support\threads.cpp:52
    #6 0x7ff726d0ee84 in std::make_unique<class wasm::Thread, class wasm::ThreadPool *, 0>(class wasm::ThreadPool *&&) C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\memory:3595
    #7 0x7ff726d0b1c9 in wasm::ThreadPool::initialize(unsigned __int64) C:\Users\user\Downloads\binaryen\src\support\threads.cpp:127
    #8 0x7ff726d0b7f6 in wasm::ThreadPool::get(void) C:\Users\user\Downloads\binaryen\src\support\threads.cpp:162
    #9 0x7ff7268929db in <lambda_07723b71396d3cfe857ad57e745497f6>::operator() C:\Users\user\Downloads\binaryen\src\passes\pass.cpp:846
    #10 0x7ff7268905ad in wasm::PassRunner::run(void) C:\Users\user\Downloads\binaryen\src\passes\pass.cpp:883
    #11 0x7ff726b85d05 in wasm::WalkerPass<struct wasm::PostWalker<struct wasm::FunctionValidator, struct wasm::Visitor<struct wasm::FunctionValidator, void>>>::run(class wasm::Module *) C:\Users\user\Downloads\binaryen\src\pass.h:536
    #12 0x7ff726b854f8 in wasm::WalkerPass<struct wasm::PostWalker<struct wasm::FunctionValidator, struct wasm::Visitor<struct wasm::FunctionValidator, void>>>::run(struct wasm::PassRunner *, class wasm::Module *) C:\Users\user\Downloads\binaryen\src\pass.h:546
    #13 0x7ff726b8b560 in wasm::FunctionValidator::validate(struct wasm::PassRunner *) C:\Users\user\Downloads\binaryen\src\wasm\wasm-validator.cpp:230
    #14 0x7ff726adfb64 in wasm::WasmValidator::validate(class wasm::Module &, unsigned int) C:\Users\user\Downloads\binaryen\src\wasm\wasm-validator.cpp:4041
    #15 0x7ff726ae024f in wasm::WasmValidator::validate(class wasm::Module &, struct wasm::PassOptions const &) C:\Users\user\Downloads\binaryen\src\wasm\wasm-validator.cpp:4088
    #16 0x7ff726558875 in main C:\Users\user\Downloads\binaryen\src\tools\wasm-opt.cpp:298
    #17 0x7ff7292af218 in invoke_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:78
    #18 0x7ff7292af161 in __scrt_common_main_seh D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288
    #19 0x7ff7292af01d in __scrt_common_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:330
    #20 0x7ff7292af28d in mainCRTStartup D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_main.cpp:16
    #21 0x7ffd388c7343  (C:\windows\System32\KERNEL32.DLL+0x180017343)
    #22 0x7ffd39ca26b0  (C:\windows\SYSTEM32\ntdll.dll+0x1800526b0)

SUMMARY: AddressSanitizer: stack-use-after-scope C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.40.33807\include\vector:1873 in std::vector<class wasm::Expression **, class std::allocator<class wasm::Expression **>>::size(void) const
Shadow bytes around the buggy address:
  0x022157f7fcd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x022157f7fce0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x022157f7fcf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x022157f7fd00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x022157f7fd10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x022157f7fd20: f1 f1 f1 f1 f8 f8 f8 f8 f8 f8 f8[f8]f8 f2 f2 f2
  0x022157f7fd30: f2 00 00 f2 f2 f2 f2 00 00 f3 f3 f3 f3 00 00 00
  0x022157f7fd40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x022157f7fd50: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f1 f1
  0x022157f7fd60: f1 f1 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x022157f7fd70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==7356==ABORTING

[kripken]

Interesting, thanks for investigating @mtb0x1 ...

Perhaps this is UB due to how the stack works on windows somehow, I'm really not sure. I don't get an error with ASan on Linux on that file with the command from the top comment, at least. But the ASan error line does point to a for loop with a stack allocation, so maybe that is the issue? I'm not an expert on that but I recall the rules are subtle. Does this diff help?

diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 295d86b40..434d5a486 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -857,8 +857,11 @@ private:
       return &func->body;
     }
 
+    assert(index < stack.size());
     auto* child = stack[index];
-    for (auto** currChild : ChildIterator(stack[index - 1]).children) {
+    assert(index - 1 < stack.size());
+    auto parentChildren = ChildIterator(stack[index - 1]).children;
+    for (auto** currChild : parentChildren) {
       if (*currChild == child) {
         return currChild;
       }

[mtb0x1]

I submitted a PR before seeing your comment, so yeah I confirm the use after free is on ChildIterator.
my fix is slightly different that your suggestion.

[kripken]

Sounds good, thanks for the PR. I guess in C++ the stack allocation really does not live til the end of the loop... mysterious that only on windows does this end up noticeable.