Bug 177839 – bmalloc mutex should be adaptive

• Status: REOPENED
• Component: bmalloc

[Filip Pizlo]

Patch forthcoming.

[Filip Pizlo]

@Yusuke: I was originally going to use os_unfair_lock and suggest futexes for Linux.  Unfortunately, using os_unfair_lock was a regression, but using WordLock was fine.  So, I'm about to post a patch that pulls WTF's WordLock into bmalloc.  The code is horribly duplicated, but I don't want this change to be blocked on the larger question of how to layer WTF and bmalloc.

I still think that the most performant solution for Linux is futexes.  I think we should explore making WTF::WordLock/bmalloc::Mutex use futexes on Linux.  I don't think we could do the same with WTF::Lock, since WTF::Lock has some fairness guarantees that futexes can't easily give you.

[Filip Pizlo]

Created attachment 322615 [details]
the patch

[Build Bot]

Attachment 322615 [details] did not pass style-queue:


ERROR: Source/bmalloc/bmalloc/BPlatform.h:218:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/bmalloc/bmalloc/StaticMutex.h:61:  try_lock is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 2 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Comment on attachment 322615 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=322615&action=review

> Source/bmalloc/bmalloc/BPlatform.h:218
> +//#define BUSE_OS_UNFAIR_LOCK 1

Ooops!  I will remove.

[Michael Saboff]

Comment on attachment 322615 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=322615&action=review

r=me

> Source/WTF/wtf/LockAlgorithmInlines.h:36
> +// NOTE: It's a bug to us any memory order other than seq_cst in this code. The cost of seq_cst fencing

*use*

> Source/WTF/wtf/WordLock.cpp:79
> +// NOTE: It's a bug to us any memory order other than seq_cst in this code. The cost of seq_cst fencing

*use*

> Source/bmalloc/bmalloc/StaticMutex.cpp:69
> +// NOTE: It's a bug to us any memory order other than seq_cst in this code. The cost of seq_cst fencing

*use*

[Geoffrey Garen]

Comment on attachment 322615 [details]
the patch

What are the MallocBench results for this change?

Or other benchmark results?

What's the motivation here?

[Filip Pizlo]

(In reply to Michael Saboff from comment #5)
> Comment on attachment 322615 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=322615&action=review
> 
> r=me
> 
> > Source/WTF/wtf/LockAlgorithmInlines.h:36
> > +// NOTE: It's a bug to us any memory order other than seq_cst in this code. The cost of seq_cst fencing
> 
> *use*
> 
> > Source/WTF/wtf/WordLock.cpp:79
> > +// NOTE: It's a bug to us any memory order other than seq_cst in this code. The cost of seq_cst fencing
> 
> *use*
> 
> > Source/bmalloc/bmalloc/StaticMutex.cpp:69
> > +// NOTE: It's a bug to us any memory order other than seq_cst in this code. The cost of seq_cst fencing
> 
> *use*

Fixed.  Thanks!

[Filip Pizlo]

(In reply to Geoffrey Garen from comment #6)
> Comment on attachment 322615 [details]
> the patch
> 
> What are the MallocBench results for this change?

How do I run it?

> 
> Or other benchmark results?

Neutral on in-browser JetStream.

> 
> What's the motivation here?

1) Don't waste CPU cycles if the lock is held for a while for whatever reason.
2) Reduce the amount of sched_yield activity we see when profiling.

[Filip Pizlo]

Created attachment 322731 [details]
patch for landing

[Build Bot]

Attachment 322731 [details] did not pass style-queue:


ERROR: Source/bmalloc/bmalloc/StaticMutex.h:61:  try_lock is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 1 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 322733 [details]
patch for landing

[Build Bot]

Attachment 322733 [details] did not pass style-queue:


ERROR: Source/bmalloc/bmalloc/StaticMutex.h:61:  try_lock is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 1 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 322760 [details]
patch for landing

maybe it will build now?

[Build Bot]

Attachment 322760 [details] did not pass style-queue:


ERROR: Source/bmalloc/bmalloc/StaticMutex.h:61:  try_lock is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 1 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Landed in https://trac.webkit.org/changeset/222893/webkit

[Radar WebKit Bug Importer]

<rdar://problem/34826960>

[Matt Lewis]

This caused multiple API Crashes on macOS testers:

  WTF_ParkingLot.UnparkAllHundred
  WTF_ParkingLot.UnparkAllHundredFast
  WTF_ParkingLot.UnparkOneFiftyThenFiftyAll
  WTF_ParkingLot.UnparkOneFiftyThenFiftyAllFast

https://build.webkit.org/builders/Apple%20El%20Capitan%20Debug%20WK2%20%28Tests%29/builds/3443/steps/run-api-tests/logs/stdio
https://build.webkit.org/builders/Apple%20El%20Capitan%20Debug%20WK2%20%28Tests%29/builds/3443




Crash Thread:
Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   libsystem_pthread.dylib             0x00007fff94386c21 _pthread_cond_updateval + 43
1   libsystem_pthread.dylib             0x00007fff94384540 _pthread_cond_signal + 633
2   libc++.1.dylib                      0x00007fff97ebe641 std::__1::condition_variable::notify_one() + 9
3   TestWTF                             0x0000000104e81b6e bmalloc::StaticMutex::unlockSlow() + 1582 (StaticMutex.cpp:261)
4   TestWTF                             0x0000000104df1894 bmalloc::StaticMutex::unlock() + 68 (StaticMutex.h:103)
5   TestWTF                             0x0000000104e6df71 bmalloc::Deallocator::deallocateSlowCase(void*) + 321 (Deallocator.cpp:94)
6   TestWTF                             0x0000000104df1d14 bmalloc::Deallocator::deallocate(void*) + 68 (Deallocator.h:81)
7   TestWTF                             0x0000000104df1cba bmalloc::Cache::deallocate(bmalloc::HeapKind, void*) + 90 (Cache.h:104)
8   TestWTF                             0x0000000104df103b bmalloc::api::free(void*, bmalloc::HeapKind) + 27 (bmalloc.h:79)
9   TestWTF                             0x0000000104df0aa7 WTF::fastFree(void*) + 23 (FastMalloc.cpp:281)
10  TestWTF                             0x0000000104e193b5 WTF::(anonymous namespace)::ThreadData::operator delete(void*) + 21 (ParkingLot.cpp:49)
11  TestWTF                             0x0000000104e19372 WTF::ThreadSafeRefCounted<WTF::(anonymous namespace)::ThreadData>::deref() const + 82 (ThreadSafeRefCounted.h:71)
12  TestWTF                             0x0000000104e19314 void WTF::derefIfNotNull<WTF::(anonymous namespace)::ThreadData>(WTF::(anonymous namespace)::ThreadData*) + 52 (RefPtr.h:46)
13  TestWTF                             0x0000000104e192d3 WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>::~RefPtr() + 83 (RefPtr.h:69)
14  TestWTF                             0x0000000104e14105 WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>::~RefPtr() + 21 (RefPtr.h:69)
15  TestWTF                             0x0000000104e1a08f WTF::VectorDestructor<true, WTF::RefPtr<WTF::(anonymous namespace)::ThreadData> >::destruct(WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>*, WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>*) + 47 (Vector.h:59)
16  TestWTF                             0x0000000104e19ffd WTF::VectorTypeOperations<WTF::RefPtr<WTF::(anonymous namespace)::ThreadData> >::destruct(WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>*, WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>*) + 29 (Vector.h:225)
17  TestWTF                             0x0000000104e19fb3 WTF::Vector<WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>, 8ul, WTF::CrashOnOverflow, 16ul, WTF::FastMalloc>::~Vector() + 67 (Vector.h:631)
18  TestWTF                             0x0000000104e14845 WTF::Vector<WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>, 8ul, WTF::CrashOnOverflow, 16ul, WTF::FastMalloc>::~Vector() + 21 (Vector.h:634)
19  TestWTF                             0x0000000104e145c4 WTF::ParkingLot::unparkCount(void const*, unsigned int) + 420 (ParkingLot.cpp:789)
20  TestWTF                             0x0000000104e1486a WTF::ParkingLot::unparkAll(void const*) + 26 (ParkingLot.cpp:794)
21  TestWTF                             0x0000000104c702bf TestWebKitAPI::(anonymous namespace)::SingleLatchTest::finish(unsigned int) + 303 (ParkingLot.cpp:112)
22  TestWTF                             0x0000000104c6f9e2 TestWebKitAPI::(anonymous namespace)::runParkingTest(unsigned int, unsigned int, unsigned int, unsigned int) + 1122 (ParkingLot.cpp:199)
23  TestWTF                             0x0000000104c6f312 TestWebKitAPI::(anonymous namespace)::repeatParkingTest(unsigned int, unsigned int, unsigned int, unsigned int, unsigned int) + 66 (ParkingLot.cpp:205)
24  TestWTF                             0x0000000104c6f34a TestWebKitAPI::WTF_ParkingLot_UnparkAllHundredFast_Test::TestBody() + 42 (ParkingLot.cpp:219)
25  TestWTF                             0x0000000104e8c48a testing::Test::Run() + 154 (gtest.cc:2101)
26  TestWTF                             0x0000000104e8cd6d testing::internal::TestInfoImpl::Run() + 189 (gtest.cc:2318)
27  TestWTF                             0x0000000104e8d90d testing::TestCase::Run() + 205 (gtest.cc:2419)
28  TestWTF                             0x0000000104e93892 testing::internal::UnitTestImpl::RunAllTests() + 898 (gtest.cc:4023)
29  TestWTF                             0x0000000104e93509 testing::UnitTest::Run() + 25 (gtest.cc:3687)
30  TestWTF                             0x0000000104d4aece TestWebKitAPI::TestsController::run(int, char**) + 174 (TestsController.cpp:84)
31  TestWTF                             0x0000000104e82e92 main + 450 (mainMac.mm:52)
32  libdyld.dylib                       0x00007fff957745ad start + 1

[Filip Pizlo]

(In reply to Matt Lewis from comment #17)
> This caused multiple API Crashes on macOS testers:
> 
>   WTF_ParkingLot.UnparkAllHundred
>   WTF_ParkingLot.UnparkAllHundredFast
>   WTF_ParkingLot.UnparkOneFiftyThenFiftyAll
>   WTF_ParkingLot.UnparkOneFiftyThenFiftyAllFast
> 
> https://build.webkit.org/builders/
> Apple%20El%20Capitan%20Debug%20WK2%20%28Tests%29/builds/3443/steps/run-api-
> tests/logs/stdio
> https://build.webkit.org/builders/
> Apple%20El%20Capitan%20Debug%20WK2%20%28Tests%29/builds/3443
> 
> 
> 
> 
> Crash Thread:
> Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
> 0   libsystem_pthread.dylib             0x00007fff94386c21
> _pthread_cond_updateval + 43
> 1   libsystem_pthread.dylib             0x00007fff94384540
> _pthread_cond_signal + 633
> 2   libc++.1.dylib                      0x00007fff97ebe641
> std::__1::condition_variable::notify_one() + 9
> 3   TestWTF                             0x0000000104e81b6e
> bmalloc::StaticMutex::unlockSlow() + 1582 (StaticMutex.cpp:261)
> 4   TestWTF                             0x0000000104df1894
> bmalloc::StaticMutex::unlock() + 68 (StaticMutex.h:103)
> 5   TestWTF                             0x0000000104e6df71
> bmalloc::Deallocator::deallocateSlowCase(void*) + 321 (Deallocator.cpp:94)
> 6   TestWTF                             0x0000000104df1d14
> bmalloc::Deallocator::deallocate(void*) + 68 (Deallocator.h:81)
> 7   TestWTF                             0x0000000104df1cba
> bmalloc::Cache::deallocate(bmalloc::HeapKind, void*) + 90 (Cache.h:104)
> 8   TestWTF                             0x0000000104df103b
> bmalloc::api::free(void*, bmalloc::HeapKind) + 27 (bmalloc.h:79)
> 9   TestWTF                             0x0000000104df0aa7
> WTF::fastFree(void*) + 23 (FastMalloc.cpp:281)
> 10  TestWTF                             0x0000000104e193b5 WTF::(anonymous
> namespace)::ThreadData::operator delete(void*) + 21 (ParkingLot.cpp:49)
> 11  TestWTF                             0x0000000104e19372
> WTF::ThreadSafeRefCounted<WTF::(anonymous namespace)::ThreadData>::deref()
> const + 82 (ThreadSafeRefCounted.h:71)
> 12  TestWTF                             0x0000000104e19314 void
> WTF::derefIfNotNull<WTF::(anonymous namespace)::ThreadData>(WTF::(anonymous
> namespace)::ThreadData*) + 52 (RefPtr.h:46)
> 13  TestWTF                             0x0000000104e192d3
> WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>::~RefPtr() + 83
> (RefPtr.h:69)
> 14  TestWTF                             0x0000000104e14105
> WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>::~RefPtr() + 21
> (RefPtr.h:69)
> 15  TestWTF                             0x0000000104e1a08f
> WTF::VectorDestructor<true, WTF::RefPtr<WTF::(anonymous
> namespace)::ThreadData> >::destruct(WTF::RefPtr<WTF::(anonymous
> namespace)::ThreadData>*, WTF::RefPtr<WTF::(anonymous
> namespace)::ThreadData>*) + 47 (Vector.h:59)
> 16  TestWTF                             0x0000000104e19ffd
> WTF::VectorTypeOperations<WTF::RefPtr<WTF::(anonymous
> namespace)::ThreadData> >::destruct(WTF::RefPtr<WTF::(anonymous
> namespace)::ThreadData>*, WTF::RefPtr<WTF::(anonymous
> namespace)::ThreadData>*) + 29 (Vector.h:225)
> 17  TestWTF                             0x0000000104e19fb3
> WTF::Vector<WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>, 8ul,
> WTF::CrashOnOverflow, 16ul, WTF::FastMalloc>::~Vector() + 67 (Vector.h:631)
> 18  TestWTF                             0x0000000104e14845
> WTF::Vector<WTF::RefPtr<WTF::(anonymous namespace)::ThreadData>, 8ul,
> WTF::CrashOnOverflow, 16ul, WTF::FastMalloc>::~Vector() + 21 (Vector.h:634)
> 19  TestWTF                             0x0000000104e145c4
> WTF::ParkingLot::unparkCount(void const*, unsigned int) + 420
> (ParkingLot.cpp:789)
> 20  TestWTF                             0x0000000104e1486a
> WTF::ParkingLot::unparkAll(void const*) + 26 (ParkingLot.cpp:794)
> 21  TestWTF                             0x0000000104c702bf
> TestWebKitAPI::(anonymous namespace)::SingleLatchTest::finish(unsigned int)
> + 303 (ParkingLot.cpp:112)
> 22  TestWTF                             0x0000000104c6f9e2
> TestWebKitAPI::(anonymous namespace)::runParkingTest(unsigned int, unsigned
> int, unsigned int, unsigned int) + 1122 (ParkingLot.cpp:199)
> 23  TestWTF                             0x0000000104c6f312
> TestWebKitAPI::(anonymous namespace)::repeatParkingTest(unsigned int,
> unsigned int, unsigned int, unsigned int, unsigned int) + 66
> (ParkingLot.cpp:205)
> 24  TestWTF                             0x0000000104c6f34a
> TestWebKitAPI::WTF_ParkingLot_UnparkAllHundredFast_Test::TestBody() + 42
> (ParkingLot.cpp:219)
> 25  TestWTF                             0x0000000104e8c48a
> testing::Test::Run() + 154 (gtest.cc:2101)
> 26  TestWTF                             0x0000000104e8cd6d
> testing::internal::TestInfoImpl::Run() + 189 (gtest.cc:2318)
> 27  TestWTF                             0x0000000104e8d90d
> testing::TestCase::Run() + 205 (gtest.cc:2419)
> 28  TestWTF                             0x0000000104e93892
> testing::internal::UnitTestImpl::RunAllTests() + 898 (gtest.cc:4023)
> 29  TestWTF                             0x0000000104e93509
> testing::UnitTest::Run() + 25 (gtest.cc:3687)
> 30  TestWTF                             0x0000000104d4aece
> TestWebKitAPI::TestsController::run(int, char**) + 174
> (TestsController.cpp:84)
> 31  TestWTF                             0x0000000104e82e92 main + 450
> (mainMac.mm:52)
> 32  libdyld.dylib                       0x00007fff957745ad start + 1

I know what’s wrong. I can fix it in a couple hours. I’m ok with this being rolled out.

[Matt Lewis]

Reverted r222893 for reason:

This caused multiple API failures.

Committed r222919: <http://trac.webkit.org/changeset/222919>

[Filip Pizlo]

(In reply to Matt Lewis from comment #19)
> Reverted r222893 for reason:
> 
> This caused multiple API failures.
> 
> Committed r222919: <http://trac.webkit.org/changeset/222919>

Thanks for fixing that.  The problem was an ancient WordLock bug.  We never fixed it because WordLock is used so sparingly in WTF.  The fix was just to avoid doing the notify_one-after-unlock optimization in unlockSlow.

[Filip Pizlo]

Relanded in https://trac.webkit.org/changeset/222945/webkit

[WebKit Commit Bot]

Re-opened since this is blocked by bug 178818

[Saam Barati]

Created attachment 324866 [details]
crashlog

This made WasmBench crash. Attaching crashlog.

[Filip Pizlo]

(In reply to Saam Barati from comment #23)
> Created attachment 324866 [details]
> crashlog
> 
> This made WasmBench crash. Attaching crashlog.

Wow. That’s a crazy crash!

I wonder why the crash log has no crash address. Am I just not reading it right?

[Saam Barati]

(In reply to Filip Pizlo from comment #24)
> (In reply to Saam Barati from comment #23)
> > Created attachment 324866 [details]
> > crashlog
> > 
> > This made WasmBench crash. Attaching crashlog.
> 
> Wow. That’s a crazy crash!
> 
> I wonder why the crash log has no crash address. Am I just not reading it
> right?

Nope, I was wondering the same thing about it. Let me see if I can grab a different crashtrace

[Saam Barati]

(In reply to Saam Barati from comment #25)
> (In reply to Filip Pizlo from comment #24)
> > (In reply to Saam Barati from comment #23)
> > > Created attachment 324866 [details]
> > > crashlog
> > > 
> > > This made WasmBench crash. Attaching crashlog.
> > 
> > Wow. That’s a crazy crash!
> > 
> > I wonder why the crash log has no crash address. Am I just not reading it
> > right?
> 
> Nope, I was wondering the same thing about it. Let me see if I can grab a
> different crashtrace

All the crash traces I have show SEGV with no address. Very weird indeed.

[Filip Pizlo]

(In reply to Saam Barati from comment #26)
> (In reply to Saam Barati from comment #25)
> > (In reply to Filip Pizlo from comment #24)
> > > (In reply to Saam Barati from comment #23)
> > > > Created attachment 324866 [details]
> > > > crashlog
> > > > 
> > > > This made WasmBench crash. Attaching crashlog.
> > > 
> > > Wow. That’s a crazy crash!
> > > 
> > > I wonder why the crash log has no crash address. Am I just not reading it
> > > right?
> > 
> > Nope, I was wondering the same thing about it. Let me see if I can grab a
> > different crashtrace
> 
> All the crash traces I have show SEGV with no address. Very weird indeed.

I just ran on my own machine.  No crashes!

[Filip Pizlo]

I'm going to reland this based on the fact that I cannot repro any WasmBench crash.  I've tried both with and without HAVE_PTHREAD_MACHDEP_H.

[Filip Pizlo]

Created attachment 335336 [details]
patch for landing

[EWS Watchlist]

Attachment 335336 [details] did not pass style-queue:


ERROR: Source/bmalloc/bmalloc/StaticMutex.h:61:  try_lock is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 1 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Landed in https://trac.webkit.org/changeset/229436/webkit

[WebKit Commit Bot]

Re-opened since this is blocked by bug 183542

[Filip Pizlo]

What seems to be happening is that there is both:

- particularly bad bmalloc lock contention when running parallel compiler threads, and
- the WordLock algorithm is significantly worse than a spinlock at handling high contention.

Alternatively, it may mean that B3 compilation calls bmalloc so much that the uncontended lock+unlock speed difference between an adaptive lock and a spinlock matters.