Bug 147665

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!