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

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.

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.

@kripken

@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.

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

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.

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

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)

@kripken

@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;

@kripken

@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

@mtb0x1

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;
       }

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.

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.

Fix stack-use-after-scope on Windows in Precompute (WebAssembly#6643)

Navigation Menu

Repository navigation

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

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

kripken commented on Jun 1, 2024

mtb0x1 commented on Jun 1, 2024

cyk2018 commented on Jun 3, 2024

kripken commented on Jun 3, 2024

cyk2018 commented on Jun 4, 2024

radekdoulik commented on Jun 4, 2024

radekdoulik commented on Jun 4, 2024

mtb0x1 commented on Jun 4, 2024

kripken commented on Jun 4, 2024

mtb0x1 commented on Jun 4, 2024

kripken commented on Jun 4, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions