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