Bug 147665

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 FrameworkAssignee: 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 Flags
ByteLock.cpp
none
ByteLock.h
none
ParkingLot.cpp
none
ParkingLot.h
none
work in progress
none
it does things
none
passing tests
none
might be done
none
writing more tests and stuff
none
wrote more tests
none
it works
none
it has tests even
none
the patch
none
the patch
none
the patch mark.lam: review+

Description Filip Pizlo 2015-08-04 17:06:38 PDT
Patch forthcoming after https://bugs.webkit.org/show_bug.cgi?id=147545 lands.
Comment 1 Filip Pizlo 2015-08-04 17:07:34 PDT
Created attachment 258237 [details]
ByteLock.cpp
Comment 2 Filip Pizlo 2015-08-04 17:07:51 PDT
Created attachment 258238 [details]
ByteLock.h
Comment 3 Filip Pizlo 2015-08-04 17:08:10 PDT
Created attachment 258239 [details]
ParkingLot.cpp
Comment 4 Filip Pizlo 2015-08-04 17:08:27 PDT
Created attachment 258240 [details]
ParkingLot.h
Comment 5 Filip Pizlo 2015-08-06 18:40:35 PDT
Created attachment 258430 [details]
work in progress
Comment 6 Filip Pizlo 2015-08-06 22:00:09 PDT
Created attachment 258454 [details]
it does things

But mostly it just deadlocks a lot, for now.
Comment 7 Filip Pizlo 2015-08-06 22:59:13 PDT
Created attachment 258459 [details]
passing tests

albeit with rehashing disabled
Comment 8 Filip Pizlo 2015-08-07 21:58:10 PDT
Created attachment 258560 [details]
might be done
Comment 9 Filip Pizlo 2015-08-08 11:21:27 PDT
Created attachment 258569 [details]
writing more tests and stuff
Comment 10 Filip Pizlo 2015-08-08 20:31:41 PDT
Created attachment 258588 [details]
wrote more tests

It's failing some of the tests I wrote.
Comment 11 Filip Pizlo 2015-08-08 20:42:42 PDT
Created attachment 258589 [details]
it works

Have to finish up the various build systems but I think it's done.
Comment 12 Filip Pizlo 2015-08-10 14:12:48 PDT
Created attachment 258650 [details]
it has tests even
Comment 13 Mark Lam 2015-08-10 14:33:56 PDT
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.
Comment 14 Filip Pizlo 2015-08-10 14:34:56 PDT
Created attachment 258652 [details]
the patch
Comment 15 Filip Pizlo 2015-08-10 16:24:15 PDT
Created attachment 258671 [details]
the patch
Comment 16 WebKit Commit Bot 2015-08-10 16:26:22 PDT
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.
Comment 17 Filip Pizlo 2015-08-10 18:03:14 PDT
Created attachment 258678 [details]
the patch

Fix build.
Comment 18 WebKit Commit Bot 2015-08-10 18:05:34 PDT
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 19 Mark Lam 2015-08-11 12:18:19 PDT
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.
Comment 20 Filip Pizlo 2015-08-11 12:31:57 PDT
(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==.
Comment 21 Filip Pizlo 2015-08-11 12:52:17 PDT
Landed in http://trac.webkit.org/changeset/188280
Comment 22 Alex Christensen 2015-08-11 13:21:59 PDT
Build fix for at least GTK and Windows in http://trac.webkit.org/changeset/188284
Comment 23 Filip Pizlo 2015-08-11 14:02:01 PDT
(In reply to comment #22)
> Build fix for at least GTK and Windows in
> http://trac.webkit.org/changeset/188284

Thank you!