Clean up the ParkingLot uparking API a bit
[WebKit-https.git] / Source / WTF / wtf / ParkingLot.h
1 /*
2  * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef WTF_ParkingLot_h
27 #define WTF_ParkingLot_h
28
29 #include <chrono>
30 #include <functional>
31 #include <wtf/Atomics.h>
32 #include <wtf/ScopedLambda.h>
33 #include <wtf/Threading.h>
34
35 namespace WTF {
36
37 class ParkingLot {
38     ParkingLot() = delete;
39     ParkingLot(const ParkingLot&) = delete;
40
41 public:
42     typedef std::chrono::steady_clock Clock;
43     
44     // Parks the thread in a queue associated with the given address, which cannot be null. The
45     // parking only succeeds if the validation function returns true while the queue lock is held.
46     // If validation returns false, it will unlock the internal parking queue and then it will
47     // return without doing anything else. If validation returns true, it will enqueue the thread,
48     // unlock the parking queue lock, call the beforeSleep function, and then it will sleep so long
49     // as the thread continues to be on the queue and the timeout hasn't fired. Finally, this
50     // returns true if we actually got unparked or false if the timeout was hit. Note that
51     // beforeSleep is called with no locks held, so it's OK to do pretty much anything so long as
52     // you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll() though.
53     // It's useful to use beforeSleep() to unlock some mutex in the implementation of
54     // Condition::wait().
55     template<typename ValidationFunctor, typename BeforeSleepFunctor>
56     static bool parkConditionally(
57         const void* address,
58         ValidationFunctor&& validation,
59         BeforeSleepFunctor&& beforeSleep,
60         Clock::time_point timeout)
61     {
62         return parkConditionallyImpl(
63             address,
64             scopedLambda<bool()>(std::forward<ValidationFunctor>(validation)),
65             scopedLambda<void()>(std::forward<BeforeSleepFunctor>(beforeSleep)),
66             timeout);
67     }
68
69     // Simple version of parkConditionally() that covers the most common case: you want to park
70     // indefinitely so long as the value at the given address hasn't changed.
71     template<typename T, typename U>
72     static bool compareAndPark(const Atomic<T>* address, U expected)
73     {
74         return parkConditionally(
75             address,
76             [address, expected] () -> bool {
77                 U value = address->load();
78                 return value == expected;
79             },
80             [] () { },
81             Clock::time_point::max());
82     }
83
84     // Unparks one thread from the queue associated with the given address, which cannot be null.
85     // Returns true if there may still be other threads on that queue, or false if there definitely
86     // are no more threads on the queue.
87     struct UnparkResult {
88         bool didUnparkThread { false };
89         bool mayHaveMoreThreads { false };
90     };
91     WTF_EXPORT_PRIVATE static UnparkResult unparkOne(const void* address);
92
93     // Unparks one thread from the queue associated with the given address, and calls the given
94     // functor while the address is locked. Reports to the callback whether any thread got unparked
95     // and whether there may be any other threads still on the queue. This is an expert-mode version
96     // of unparkOne() that allows for really good thundering herd avoidance in adaptive mutexes.
97     // Without this, a lock implementation that uses unparkOne() has to have some trick for knowing
98     // if there are still threads parked on the queue, so that it can set some bit in its lock word
99     // to indicate that the next unlock() also needs to unparkOne(). But there is a race between
100     // manipulating that bit and some other thread acquiring the lock. It's possible to work around
101     // that race - see Rusty Russel's well-known usersem library - but it's not pretty. This form
102     // allows that race to be completely avoided, since there is no way that a thread can be parked
103     // while the callback is running.
104     template<typename CallbackFunctor>
105     static void unparkOne(const void* address, CallbackFunctor&& callback)
106     {
107         unparkOneImpl(address, scopedLambda<void(UnparkResult)>(std::forward<CallbackFunctor>(callback)));
108     }
109
110     // Unparks every thread from the queue associated with the given address, which cannot be null.
111     WTF_EXPORT_PRIVATE static void unparkAll(const void* address);
112
113     // Locks the parking lot and walks all of the parked threads and the addresses they are waiting
114     // on. Threads that are on the same queue are guaranteed to be walked from first to last, but the
115     // queues may be randomly interleaved. For example, if the queue for address A1 has T1 and T2 and
116     // the queue for address A2 has T3 and T4, then you might see iteration orders like:
117     //
118     // A1,T1 A1,T2 A2,T3 A2,T4
119     // A2,T3 A2,T4 A1,T1 A1,T2
120     // A1,T1 A2,T3 A1,T2 A2,T4
121     // A1,T1 A2,T3 A2,T4 A1,T2
122     //
123     // As well as many other possible interleavings that all have T1 before T2 and T3 before T4 but are
124     // otherwise unconstrained. This method is useful primarily for debugging. It's also used by unit
125     // tests.
126     template<typename CallbackFunctor>
127     static void forEach(CallbackFunctor&& callback)
128     {
129         forEachImpl(scopedLambda<void(ThreadIdentifier, const void*)>(std::forward<CallbackFunctor>(callback)));
130     }
131
132 private:
133     WTF_EXPORT_PRIVATE static bool parkConditionallyImpl(
134         const void* address,
135         const ScopedLambda<bool()>& validation,
136         const ScopedLambda<void()>& beforeSleep,
137         Clock::time_point timeout);
138     
139     WTF_EXPORT_PRIVATE static void unparkOneImpl(
140         const void* address, const ScopedLambda<void(UnparkResult)>& callback);
141
142     WTF_EXPORT_PRIVATE static void forEachImpl(const ScopedLambda<void(ThreadIdentifier, const void*)>&);
143 };
144
145 } // namespace WTF
146
147 using WTF::ParkingLot;
148
149 #endif // WTF_ParkingLot_h
150