Bug 147665 – WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Filip Pizlo]

Patch forthcoming after https://bugs.webkit.org/show_bug.cgi?id=147545 lands.

[Filip Pizlo]

Created attachment 258237 [details]
ByteLock.cpp

[Filip Pizlo]

Created attachment 258238 [details]
ByteLock.h

[Filip Pizlo]

Created attachment 258239 [details]
ParkingLot.cpp

[Filip Pizlo]

Created attachment 258240 [details]
ParkingLot.h

[Filip Pizlo]

Created attachment 258430 [details]
work in progress

[Filip Pizlo]

Created attachment 258454 [details]
it does things

But mostly it just deadlocks a lot, for now.

[Filip Pizlo]

Created attachment 258459 [details]
passing tests

albeit with rehashing disabled

[Filip Pizlo]

Created attachment 258560 [details]
might be done

[Filip Pizlo]

Created attachment 258569 [details]
writing more tests and stuff

[Filip Pizlo]

Created attachment 258588 [details]
wrote more tests

It's failing some of the tests I wrote.

[Filip Pizlo]

Created attachment 258589 [details]
it works

Have to finish up the various build systems but I think it's done.

[Filip Pizlo]

Created attachment 258650 [details]
it has tests even

[Mark Lam]

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.

[Filip Pizlo]

Created attachment 258652 [details]
the patch

[Filip Pizlo]

Created attachment 258671 [details]
the patch

[WebKit Commit Bot]

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.

[Filip Pizlo]

Created attachment 258678 [details]
the patch

Fix build.

[WebKit Commit Bot]

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.

[Mark Lam]

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.

[Filip Pizlo]

(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==.

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/188280

[Alex Christensen]

Build fix for at least GTK and Windows in http://trac.webkit.org/changeset/188284

[Filip Pizlo]

(In reply to comment #22)
> Build fix for at least GTK and Windows in
> http://trac.webkit.org/changeset/188284

Thank you!