Summary: | WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits | ||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Filip Pizlo <fpizlo> | ||||||||||||||||||||||||||||||||
Component: | Web Template Framework | Assignee: | Filip Pizlo <fpizlo> | ||||||||||||||||||||||||||||||||
Status: | RESOLVED FIXED | ||||||||||||||||||||||||||||||||||
Severity: | Normal | CC: | achristensen, andersca, barraclough, basile_clement, benjamin, commit-queue, ggaren, mark.lam, mhahnenb, mmirman, msaboff, nrotem, oliver, saam, sam | ||||||||||||||||||||||||||||||||
Priority: | P2 | ||||||||||||||||||||||||||||||||||
Version: | 528+ (Nightly build) | ||||||||||||||||||||||||||||||||||
Hardware: | All | ||||||||||||||||||||||||||||||||||
OS: | All | ||||||||||||||||||||||||||||||||||
Bug Depends on: | 147545 | ||||||||||||||||||||||||||||||||||
Bug Blocks: | 147841 | ||||||||||||||||||||||||||||||||||
Attachments: |
|
Description
Filip Pizlo
2015-08-04 17:06:38 PDT
Created attachment 258237 [details]
ByteLock.cpp
Created attachment 258238 [details]
ByteLock.h
Created attachment 258239 [details]
ParkingLot.cpp
Created attachment 258240 [details]
ParkingLot.h
Created attachment 258430 [details]
work in progress
Created attachment 258454 [details]
it does things
But mostly it just deadlocks a lot, for now.
Created attachment 258459 [details]
passing tests
albeit with rehashing disabled
Created attachment 258560 [details]
might be done
Created attachment 258569 [details]
writing more tests and stuff
Created attachment 258588 [details]
wrote more tests
It's failing some of the tests I wrote.
Created attachment 258589 [details]
it works
Have to finish up the various build systems but I think it's done.
Created attachment 258650 [details]
it has tests even
Comment on attachment 258650 [details]
it has tests even
Is there a reason you have not deleted wtf/ByteSpinLock.h? I don't see anyone else using it except ConcurrentJITLock.h.
Created attachment 258652 [details]
the patch
Created attachment 258671 [details]
the patch
Attachment 258671 [details] did not pass style-queue:
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:51: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:71: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:101: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:115: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Source/WTF/wtf/ParkingLot.cpp:541: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Source/WTF/wtf/ParkingLot.cpp:570: Place brace on its own line for function definitions. [whitespace/braces] [4]
Total errors found: 6 in 18 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 258678 [details]
the patch
Fix build.
Attachment 258678 [details] did not pass style-queue:
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:51: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:71: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:101: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp:115: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Source/WTF/wtf/ParkingLot.cpp:542: Place brace on its own line for function definitions. [whitespace/braces] [4]
ERROR: Source/WTF/wtf/ParkingLot.cpp:571: Place brace on its own line for function definitions. [whitespace/braces] [4]
Total errors found: 6 in 18 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Comment on attachment 258678 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=258678&action=review r=me with comments for your consideration. > Source/WTF/wtf/ByteLock.cpp:34 > +static bool verbose = false; nit: Should this be a static const? > Source/WTF/wtf/ParkingLot.cpp:43 > +bool verbose = false; nit: should this be a static const? > Source/WTF/wtf/ParkingLot.cpp:52 > + ThreadIdentifier threadIdentifier; In the project, we’ve been gradually migrating to use std::thread::id. So we want to introduce new usage of the old ThreadIdentifier? Or should we just start using std::thread::id instead? > Source/WTF/wtf/ParkingLot.cpp:259 > + std::sort(buckets.begin(), buckets.end()); > + for (Bucket* bucket : buckets) > + bucket->lock.lock(); Hmmm … ensuring ordered locking by using the bucket addresses as the lock rank. Nice trick. > Source/WTF/wtf/ParkingLot.cpp:284 > + // We try to ensure that the size of the hashtable used for thread queues is always large enough > + // to avoid collisions. So, since we started a new thread, we may need to increase the size of the > + // hashtable. This does just that. Note that we never free the old spine, since we never lock > + // around spine accesses (i.e. the "hashtable" global variable). I wish that we don’t have to leak the old hashtable, but I see that this is necessary for correctness because we want enqueue() and dequeue() to be able to get to the desired bucket without first acquiring a common lock. And there’s no way to tell when all threads are done with the old hashtable. > Source/WTF/wtf/ParkingLot.h:31 > +#include <wtf/DataLog.h> Shouldn’t you put this #include <wtf/DataLog.h> in ParkingLot.cpp and ByteLock.cpp instead? > Source/WTF/wtf/ParkingLot.h:32 > +#include <wtf/StringPrintStream.h> Ditto. Put in ParkingLot.cpp and ByteLock.cpp instead? > Source/WTF/wtf/ParkingLot.h:57 > + template<typename T, typename U> > + static bool compareAndPark(const Atomic<T>* address, U expected) > + { > + return parkConditionally( > + address, > + [address, expected] () -> bool { > + U value = address->load(); > + return value == expected; > + }); > + } When would we ever want T to be different from U? In the lambda function, we expect to load a value of type U from the address of Atomic<T>*. According to Atomics.h, Atomic<T>::load will always return a value of type T. (In reply to comment #19) > Comment on attachment 258678 [details] > the patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=258678&action=review > > r=me with comments for your consideration. > > > Source/WTF/wtf/ByteLock.cpp:34 > > +static bool verbose = false; > > nit: Should this be a static const? Yes it should! > > > Source/WTF/wtf/ParkingLot.cpp:43 > > +bool verbose = false; > > nit: should this be a static const? It should be a const bool. It's already "static" because it's inside an anonymous namespace. > > > Source/WTF/wtf/ParkingLot.cpp:52 > > + ThreadIdentifier threadIdentifier; > > In the project, we’ve been gradually migrating to use std::thread::id. So > we want to introduce new usage of the old ThreadIdentifier? Or should we > just start using std::thread::id instead? Hmmm. I'll keep using ThreadIdentifier for now just because Threading.h still does use it. > > > Source/WTF/wtf/ParkingLot.cpp:259 > > + std::sort(buckets.begin(), buckets.end()); > > + for (Bucket* bucket : buckets) > > + bucket->lock.lock(); > > Hmmm … ensuring ordered locking by using the bucket addresses as the lock > rank. Nice trick. > > > Source/WTF/wtf/ParkingLot.cpp:284 > > + // We try to ensure that the size of the hashtable used for thread queues is always large enough > > + // to avoid collisions. So, since we started a new thread, we may need to increase the size of the > > + // hashtable. This does just that. Note that we never free the old spine, since we never lock > > + // around spine accesses (i.e. the "hashtable" global variable). > > I wish that we don’t have to leak the old hashtable, but I see that this is > necessary for correctness because we want enqueue() and dequeue() to be able > to get to the desired bucket without first acquiring a common lock. And > there’s no way to tell when all threads are done with the old hashtable. Right. This is why the hashtable spine is separate from the Bucket objects. The Bucket objects are big because of the 64-byte padding to prevent false sharing (like, my MBP has 64-byte cache lines) and because they hold all of the interesting state. The spines are small. The fact that we resize the hashtable at least 2x each time means that the leaking of the spines causes at worst a 2x increase in spine memory usage, which is fine since the spines are tiny compared to the total sizes of the Buckets. > > > Source/WTF/wtf/ParkingLot.h:31 > > +#include <wtf/DataLog.h> > > Shouldn’t you put this #include <wtf/DataLog.h> in ParkingLot.cpp and > ByteLock.cpp instead? Ooops, this is leftover from when I had debug code in ParkingLot.h. I'll remove. > > > Source/WTF/wtf/ParkingLot.h:32 > > +#include <wtf/StringPrintStream.h> > > Ditto. Put in ParkingLot.cpp and ByteLock.cpp instead? Ditto, will remove. > > > Source/WTF/wtf/ParkingLot.h:57 > > + template<typename T, typename U> > > + static bool compareAndPark(const Atomic<T>* address, U expected) > > + { > > + return parkConditionally( > > + address, > > + [address, expected] () -> bool { > > + U value = address->load(); > > + return value == expected; > > + }); > > + } > > When would we ever want T to be different from U? In the lambda function, > we expect to load a value of type U from the address of Atomic<T>*. > According to Atomics.h, Atomic<T>::load will always return a value of type T. This is because of code like: Atomic<uint8_t> thing; ... ParkingLot::compareAndPark(&thing, 0) If we didn't have U, this would fail to compile because "0" is an int and not a uint8_t. In fact, even if we did: ParkingLot::compareAndPark(&thing, 0u) then it would still not compile because unsigned and uint8_t are not the same. This is why U is separate - it allows "expected" to be a constant and the code will compile fine so long as that constant (or variable) has an appropriate operator==. Landed in http://trac.webkit.org/changeset/188280 Build fix for at least GTK and Windows in http://trac.webkit.org/changeset/188284 (In reply to comment #22) > Build fix for at least GTK and Windows in > http://trac.webkit.org/changeset/188284 Thank you! |