search

microsoft / mimalloc

mimalloc is a compact general purpose allocator with excellent performance.
MIT License
10.61k stars 866 forks source link

Potential deadlock reported by ThreadSanitizer #962

Open YYF233333 opened 19 hours ago

YYF233333 commented 19 hours ago

Hello, I'm trying to integrate mimalloc into godot in this PR. Everything works fine except CI report some potential deadlock when tsan is enabled. I have no idea why replacing malloc interact with lock behaviour. Is this something related to mimalloc internal or just false positive? (no deadlock found in real usage)

log ```bash ================== WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) (pid=7667) Cycle in lock order graph: M0 (0x7f6bff809c10) => M1 (0x7f6bff80bc10) => M0 Mutex M1 acquired here while holding mutex M0 in main thread: #0 pthread_mutex_lock (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5b3987a) (BuildId: ac655d01e0d87cea) #1 __gthread_mutex_lock(pthread_mutex_t*) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/x86_64-linux-gnu/c++/12/bits/gthr-default.h:749:12 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5bf5313) (BuildId: ac655d01e0d87cea) #2 __gthread_recursive_mutex_lock(pthread_mutex_t*) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/x86_64-linux-gnu/c++/12/bits/gthr-default.h:811:10 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5bf52c5) (BuildId: ac655d01e0d87cea) #3 std::recursive_mutex::lock() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/mutex:108:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5c07a75) (BuildId: ac655d01e0d87cea) #4 std::unique_lock::lock() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/unique_lock.h:139:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0xcdd62fb) (BuildId: ac655d01e0d87cea) #5 std::unique_lock::unique_lock(std::recursive_mutex&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/unique_lock.h:69:2 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0xcdd6217) (BuildId: ac655d01e0d87cea) #6 MutexLock >::MutexLock(MutexImpl const&) /home/runner/work/godot/godot/core/os/mutex.h:79:4 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0xcdd[619](https://github.com/godotengine/godot/actions/runs/11940065058/job/33281960848?pr=99427#step:17:620)5) (BuildId: ac655d01e0d87cea) #7 GDScript::_recurse_replace_function_ptrs(HashMap, DefaultTypedAllocator > > const&) const /home/runner/work/godot/godot/modules/gdscript/gdscript.cpp:1541:12 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6cd7c23) (BuildId: ac655d01e0d87cea) #8 GDScript::_recurse_replace_function_ptrs(HashMap, DefaultTypedAllocator > > const&) const /home/runner/work/godot/godot/modules/gdscript/gdscript.cpp:1553:21 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6cd7d70) (BuildId: ac655d01e0d87cea) #9 GDScriptCompiler::compile(GDScriptParser const*, GDScript*, bool) /home/runner/work/godot/godot/modules/gdscript/gdscript_compiler.cpp:3267:15 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6db262a) (BuildId: ac655d01e0d87cea) #10 GDScript::reload(bool) /home/runner/work/godot/godot/modules/gdscript/gdscript.cpp:854:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6cd2dbc) (BuildId: ac655d01e0d87cea) #11 GDScriptTests::GDScriptTest::execute_test_code(bool) /home/runner/work/godot/godot/modules/gdscript/tests/gdscript_test_runner.cpp:655:16 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6ffbf94) (BuildId: ac655d01e0d87cea) #12 GDScriptTests::GDScriptTest::run_test() /home/runner/work/godot/godot/modules/gdscript/tests/gdscript_test_runner.cpp:706:9 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6ff923a) (BuildId: ac655d01e0d87cea) #13 GDScriptTests::GDScriptTestRunner::run_tests() /home/runner/work/godot/godot/modules/gdscript/tests/gdscript_test_runner.cpp:205:42 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6ff8ca2) (BuildId: ac655d01e0d87cea) #14 GDScriptTests::DOCTEST_ANON_SUITE_8696::DOCTEST_ANON_FUNC_8697() /home/runner/work/godot/godot/./modules/gdscript/tests/gdscript_test_runner_suite.h:47:27 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x62dd04b) (BuildId: ac655d01e0d87cea) #15 doctest::Context::run() /home/runner/work/godot/godot/./thirdparty/doctest/doctest.h:7007:21 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6[621](https://github.com/godotengine/godot/actions/runs/11940065058/job/33281960848?pr=99427#step:17:622)5a3) (BuildId: ac655d01e0d87cea) #16 test_main(int, char**) /home/runner/work/godot/godot/tests/test_main.cpp:258:22 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x62e1873) (BuildId: ac655d01e0d87cea) #17 Main::test_entrypoint(int, char**, bool&) /home/runner/work/godot/godot/main/main.cpp:898:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5cd62b2) (BuildId: ac655d01e0d87cea) #18 main /home/runner/work/godot/godot/platform/linuxbsd/godot_linuxbsd.cpp:68:2 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5b9cd0e) (BuildId: ac655d01e0d87cea) Hint: use TSAN_OPTIONS=second_deadlock_stack=1 to get more informative warning message Mutex M0 acquired here while holding mutex M1 in main thread: #0 pthread_mutex_lock (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5b3987a) (BuildId: ac655d01e0d87cea) #1 __gthread_mutex_lock(pthread_mutex_t*) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/x86_64-linux-gnu/c++/12/bits/gthr-default.h:749:12 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5bf5313) (BuildId: ac655d01e0d87cea) #2 __gthread_recursive_mutex_lock(pthread_mutex_t*) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/x86_64-linux-gnu/c++/12/bits/gthr-default.h:811:10 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5bf52c5) (BuildId: ac655d01e0d87cea) #3 std::recursive_mutex::lock() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/mutex:108:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5c07a75) (BuildId: ac655d01e0d87cea) #4 std::unique_lock::lock() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/unique_lock.h:139:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0xcdd62fb) (BuildId: ac655d01e0d87cea) #5 std::unique_lock::unique_lock(std::recursive_mutex&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/unique_lock.h:69:2 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0xcdd6217) (BuildId: ac655d01e0d87cea) #6 MutexLock >::MutexLock(MutexImpl const&) /home/runner/work/godot/godot/core/os/mutex.h:79:4 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0xcdd6195) (BuildId: ac655d01e0d87cea) #7 GDScript::_recurse_replace_function_ptrs(HashMap, DefaultTypedAllocator > > const&) const /home/runner/work/godot/godot/modules/gdscript/gdscript.cpp:1541:12 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6cd7c23) (BuildId: ac655d01e0d87cea) #8 GDScript::_recurse_replace_function_ptrs(HashMap, DefaultTypedAllocator > > const&) const /home/runner/work/godot/godot/modules/gdscript/gdscript.cpp:1553:21 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6cd7d70) (BuildId: ac655d01e0d87cea) #9 GDScriptCompiler::compile(GDScriptParser const*, GDScript*, bool) /home/runner/work/godot/godot/modules/gdscript/gdscript_compiler.cpp:3267:15 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6db262a) (BuildId: ac655d01e0d87cea) #10 GDScript::reload(bool) /home/runner/work/godot/godot/modules/gdscript/gdscript.cpp:854:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6cd2dbc) (BuildId: ac655d01e0d87cea) #11 GDScriptTests::GDScriptTest::execute_test_code(bool) /home/runner/work/godot/godot/modules/gdscript/tests/gdscript_test_runner.cpp:655:16 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6ffbf94) (BuildId: ac655d01e0d87cea) #12 GDScriptTests::GDScriptTest::run_test() /home/runner/work/godot/godot/modules/gdscript/tests/gdscript_test_runner.cpp:706:9 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6ff923a) (BuildId: ac655d01e0d87cea) #13 GDScriptTests::GDScriptTestRunner::run_tests() /home/runner/work/godot/godot/modules/gdscript/tests/gdscript_test_runner.cpp:205:42 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x6ff8ca2) (BuildId: ac655d01e0d87cea) #14 GDScriptTests::DOCTEST_ANON_SUITE_8696::DOCTEST_ANON_FUNC_8697() /home/runner/work/godot/godot/./modules/gdscript/tests/gdscript_test_runner_suite.h:47:27 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x62dd04b) (BuildId: ac655d01e0d87cea) #15 doctest::Context::run() /home/runner/work/godot/godot/./thirdparty/doctest/doctest.h:7007:21 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x66215a3) (BuildId: ac655d01e0d87cea) #16 test_main(int, char**) /home/runner/work/godot/godot/tests/test_main.cpp:258:22 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x62e1873) (BuildId: ac655d01e0d87cea) #17 Main::test_entrypoint(int, char**, bool&) /home/runner/work/godot/godot/main/main.cpp:898:17 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5cd62b2) (BuildId: ac655d01e0d87cea) #18 main /home/runner/work/godot/godot/platform/linuxbsd/godot_linuxbsd.cpp:68:2 (godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5b9cd0e) (BuildId: ac655d01e0d87cea) SUMMARY: ThreadSanitizer: lock-order-inversion (potential deadlock) (/home/runner/work/godot/godot/bin/godot.linuxbsd.editor.dev.x86_64.llvm.san+0x5b3987a) (BuildId: ac655d01e0d87cea) in pthread_mutex_lock ================== ```

How I integrate: include mimalloc.h, compile src/static.c and statically link to final binary.

daanx commented 13 hours ago

Nice to see mimalloc integration in Godot! Let me know if you need further help or have suggestions.

That is a strange error (potential lock-inversion) from TSAN; I only recently added a lock to mimalloc for the Python integration but it is hardly used otherwise (it is there to protect huge abandoned segments that are allocated outside arena's). I think that may be the pthread_mutex_lock you see in the error messages? (the other locks seem from Godot itself). Since the mimalloc lock is only acquired / released internally without calling out to other code this should always be fine and not lead to lock inversion -- I think? (I will check the mimalloc code again as well to make sure the lock is always released)

So, not sure. However, since TSAN is only sampling, it might be that the mimalloc lock exposes now a lock inversion scenario in Godot that was undetected before? Or it may be just a false positive?

YYF233333 commented 8 hours ago

Both of the two locks are from godot side (std::recursive_mutex), not from mimalloc. I agree that it may be a hidden bug previously not detected in godot itself (if not false positive), because ptmalloc probably add an global lock while malloc from multi-thread, which limits the parallelism. But in mimalloc we don't have that lock (right?).

Thanks for the quick reply, I'll test if adding this lock back solve the problem. Edit: It doesn't work, sadly.