1/*
2 * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include <condition_variable>
28#include <mutex>
29#include <thread>
30#include <wtf/DataLog.h>
31#include <wtf/HashSet.h>
32#include <wtf/ListDump.h>
33#include <wtf/ParkingLot.h>
34#include <wtf/Threading.h>
35#include <wtf/ThreadingPrimitives.h>
36
37namespace TestWebKitAPI {
38
39namespace {
40
41struct SingleLatchTest {
42 void initialize(unsigned numThreads)
43 {
44 // This implements a fair (FIFO) semaphore, and it starts out unavailable.
45 semaphore.store(0);
46
47 for (unsigned i = numThreads; i--;) {
48 threads.append(
49 Thread::create(
50 "Parking Test Thread",
51 [&] () {
52 down();
53
54 std::lock_guard<std::mutex> locker(lock);
55 awake.add(Thread::current());
56 lastAwoken = &Thread::current();
57 condition.notify_one();
58 }));
59 }
60 }
61
62 void unparkOne(unsigned singleUnparkIndex)
63 {
64 EXPECT_TRUE(nullptr == lastAwoken);
65
66 unsigned numWaitingOnAddress = 0;
67 Vector<RefPtr<Thread>, 8> queue;
68 ParkingLot::forEach(
69 [&] (Thread& thread, const void* address) {
70 if (address != &semaphore)
71 return;
72
73 queue.append(&thread);
74
75 numWaitingOnAddress++;
76 });
77
78 EXPECT_LE(numWaitingOnAddress, threads.size() - singleUnparkIndex);
79
80 up();
81
82 {
83 std::unique_lock<std::mutex> locker(lock);
84 while (awake.size() < singleUnparkIndex + 1)
85 condition.wait(locker);
86 EXPECT_TRUE(nullptr != lastAwoken);
87 if (!queue.isEmpty() && queue[0] != lastAwoken) {
88 dataLog("Woke up wrong thread: queue = ", listDump(queue), ", last awoken = ", lastAwoken, "\n");
89 EXPECT_EQ(queue[0], lastAwoken);
90 }
91 lastAwoken = nullptr;
92 }
93 }
94
95 void finish(unsigned numSingleUnparks)
96 {
97 unsigned numWaitingOnAddress = 0;
98 ParkingLot::forEach(
99 [&] (Thread&, const void* address) {
100 if (address != &semaphore)
101 return;
102
103 numWaitingOnAddress++;
104 });
105
106 EXPECT_LE(numWaitingOnAddress, threads.size() - numSingleUnparks);
107
108 semaphore.store(threads.size() - numSingleUnparks);
109 ParkingLot::unparkAll(&semaphore);
110
111 numWaitingOnAddress = 0;
112 ParkingLot::forEach(
113 [&] (Thread&, const void* address) {
114 if (address != &semaphore)
115 return;
116
117 numWaitingOnAddress++;
118 });
119
120 EXPECT_EQ(0u, numWaitingOnAddress);
121
122 {
123 std::unique_lock<std::mutex> locker(lock);
124 while (awake.size() < threads.size())
125 condition.wait(locker);
126 }
127
128 for (auto& thread : threads)
129 thread->waitForCompletion();
130 }
131
132 // Semaphore operations.
133 void down()
134 {
135 for (;;) {
136 int oldSemaphoreValue = semaphore.load();
137 int newSemaphoreValue = oldSemaphoreValue - 1;
138 if (!semaphore.compareExchangeWeak(oldSemaphoreValue, newSemaphoreValue))
139 continue;
140
141 if (oldSemaphoreValue > 0) {
142 // We acquired the semaphore. Done.
143 return;
144 }
145
146 // We need to wait.
147 if (ParkingLot::compareAndPark(&semaphore, newSemaphoreValue).wasUnparked) {
148 // We did wait, and then got woken up. This means that someone who up'd the semaphore
149 // passed ownership onto us.
150 return;
151 }
152
153 // We never parked, because the semaphore value changed. Undo our decrement and try again.
154 for (;;) {
155 int oldSemaphoreValue = semaphore.load();
156 if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
157 break;
158 }
159 }
160 }
161 void up()
162 {
163 int oldSemaphoreValue;
164 for (;;) {
165 oldSemaphoreValue = semaphore.load();
166 if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
167 break;
168 }
169
170 // Check if anyone was waiting on the semaphore. If they were, then pass ownership to them.
171 if (oldSemaphoreValue < 0)
172 ParkingLot::unparkOne(&semaphore);
173 }
174
175 Atomic<int> semaphore;
176 std::mutex lock;
177 std::condition_variable condition;
178 HashSet<Ref<Thread>> awake;
179 Vector<Ref<Thread>> threads;
180 RefPtr<Thread> lastAwoken;
181};
182
183void runParkingTest(unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
184{
185 std::unique_ptr<SingleLatchTest[]> tests = std::make_unique<SingleLatchTest[]>(numLatches);
186
187 for (unsigned latchIndex = numLatches; latchIndex--;)
188 tests[latchIndex].initialize(numThreads);
189
190 for (unsigned unparkIndex = 0; unparkIndex < numSingleUnparks; ++unparkIndex) {
191 std::this_thread::sleep_for(std::chrono::microseconds(delay));
192 for (unsigned latchIndex = numLatches; latchIndex--;)
193 tests[latchIndex].unparkOne(unparkIndex);
194 }
195
196 for (unsigned latchIndex = numLatches; latchIndex--;)
197 tests[latchIndex].finish(numSingleUnparks);
198}
199
200void repeatParkingTest(unsigned numRepeats, unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
201{
202 while (numRepeats--)
203 runParkingTest(numLatches, delay, numThreads, numSingleUnparks);
204}
205
206} // anonymous namespace
207
208TEST(WTF_ParkingLot, UnparkAllOneFast)
209{
210 repeatParkingTest(10000, 1, 0, 1, 0);
211}
212
213TEST(WTF_ParkingLot, UnparkAllHundredFast)
214{
215 repeatParkingTest(100, 1, 0, 100, 0);
216}
217
218TEST(WTF_ParkingLot, UnparkOneOneFast)
219{
220 repeatParkingTest(1000, 1, 0, 1, 1);
221}
222
223TEST(WTF_ParkingLot, UnparkOneHundredFast)
224{
225 repeatParkingTest(20, 1, 0, 100, 100);
226}
227
228TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAllFast)
229{
230 repeatParkingTest(50, 1, 0, 100, 50);
231}
232
233TEST(WTF_ParkingLot, UnparkAllOne)
234{
235 repeatParkingTest(100, 1, 10000, 1, 0);
236}
237
238TEST(WTF_ParkingLot, UnparkAllHundred)
239{
240 repeatParkingTest(100, 1, 10000, 100, 0);
241}
242
243TEST(WTF_ParkingLot, UnparkOneOne)
244{
245 repeatParkingTest(10, 1, 10000, 1, 1);
246}
247
248TEST(WTF_ParkingLot, UnparkOneFifty)
249{
250 repeatParkingTest(1, 1, 10000, 50, 50);
251}
252
253TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAll)
254{
255 repeatParkingTest(2, 1, 10000, 100, 50);
256}
257
258TEST(WTF_ParkingLot, HundredUnparkAllOneFast)
259{
260 repeatParkingTest(100, 100, 0, 1, 0);
261}
262
263TEST(WTF_ParkingLot, HundredUnparkAllOne)
264{
265 repeatParkingTest(1, 100, 10000, 1, 0);
266}
267
268} // namespace TestWebKitAPI
269
270