1 files changed, 273 insertions, 0 deletions
diff --git a/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp b/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp
new file mode 100644
index 000000000..c67e1e081
--- /dev/null
+++ b/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp
@@ -0,0 +1,273 @@
+/*
+ * 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. AND ITS CONTRIBUTORS ``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 ITS 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.
+ */
+
+#include "config.h"
+#include <condition_variable>
+#include <mutex>
+#include <thread>
+#include <wtf/DataLog.h>
+#include <wtf/HashSet.h>
+#include <wtf/ListDump.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+
+using namespace WTF;
+
+namespace TestWebKitAPI {
+
+namespace {
+
+struct SingleLatchTest {
+    void initialize(unsigned numThreads)
+    {
+        // This implements a fair (FIFO) semaphore, and it starts out unavailable.
+        semaphore.store(0);
+        
+        for (unsigned i = numThreads; i--;) {
+            threads.append(
+                createThread(
+                    "Parking Test Thread",
+                    [&] () {
+                        EXPECT_NE(0u, currentThread());
+
+                        down();
+
+                        std::lock_guard<std::mutex> locker(lock);
+                        awake.add(currentThread());
+                        lastAwoken = currentThread();
+                        condition.notify_one();
+                    }));
+        }
+    }
+
+    void unparkOne(unsigned singleUnparkIndex)
+    {
+        EXPECT_EQ(0u, lastAwoken);
+        
+        unsigned numWaitingOnAddress = 0;
+        Vector<ThreadIdentifier, 8> queue;
+        ParkingLot::forEach(
+            [&] (ThreadIdentifier threadIdentifier, const void* address) {
+                if (address != &semaphore)
+                    return;
+
+                queue.append(threadIdentifier);
+
+                numWaitingOnAddress++;
+            });
+
+        EXPECT_LE(numWaitingOnAddress, threads.size() - singleUnparkIndex);
+
+        up();
+
+        {
+            std::unique_lock<std::mutex> locker(lock);
+            while (awake.size() < singleUnparkIndex + 1)
+                condition.wait(locker);
+            EXPECT_NE(0u, lastAwoken);
+            if (!queue.isEmpty() && queue[0] != lastAwoken) {
+                dataLog("Woke up wrong thread: queue = ", listDump(queue), ", last awoken = ", lastAwoken, "\n");
+                EXPECT_EQ(queue[0], lastAwoken);
+            }
+            lastAwoken = 0;
+        }
+    }
+
+    void finish(unsigned numSingleUnparks)
+    {
+        unsigned numWaitingOnAddress = 0;
+        ParkingLot::forEach(
+            [&] (ThreadIdentifier, const void* address) {
+                if (address != &semaphore)
+                    return;
+                
+                numWaitingOnAddress++;
+            });
+        
+        EXPECT_LE(numWaitingOnAddress, threads.size() - numSingleUnparks);
+
+        semaphore.store(threads.size() - numSingleUnparks);
+        ParkingLot::unparkAll(&semaphore);
+
+        numWaitingOnAddress = 0;
+        ParkingLot::forEach(
+            [&] (ThreadIdentifier, const void* address) {
+                if (address != &semaphore)
+                    return;
+            
+                numWaitingOnAddress++;
+            });
+
+        EXPECT_EQ(0u, numWaitingOnAddress);
+    
+        {
+            std::unique_lock<std::mutex> locker(lock);
+            while (awake.size() < threads.size())
+                condition.wait(locker);
+        }
+
+        for (ThreadIdentifier threadIdentifier : threads)
+            waitForThreadCompletion(threadIdentifier);
+    }
+
+    // Semaphore operations.
+    void down()
+    {
+        for (;;) {
+            int oldSemaphoreValue = semaphore.load();
+            int newSemaphoreValue = oldSemaphoreValue - 1;
+            if (!semaphore.compareExchangeWeak(oldSemaphoreValue, newSemaphoreValue))
+                continue;
+            
+            if (oldSemaphoreValue > 0) {
+                // We acquired the semaphore. Done.
+                return;
+            }
+            
+            // We need to wait.
+            if (ParkingLot::compareAndPark(&semaphore, newSemaphoreValue).wasUnparked) {
+                // We did wait, and then got woken up. This means that someone who up'd the semaphore
+                // passed ownership onto us.
+                return;
+            }
+
+            // We never parked, because the semaphore value changed. Undo our decrement and try again.
+            for (;;) {
+                int oldSemaphoreValue = semaphore.load();
+                if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
+                    break;
+            }
+        }
+    }
+    void up()
+    {
+        int oldSemaphoreValue;
+        for (;;) {
+            oldSemaphoreValue = semaphore.load();
+            if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
+                break;
+        }
+
+        // Check if anyone was waiting on the semaphore. If they were, then pass ownership to them.
+        if (oldSemaphoreValue < 0)
+            ParkingLot::unparkOne(&semaphore);
+    }
+    
+    Atomic<int> semaphore;
+    std::mutex lock;
+    std::condition_variable condition;
+    HashSet<ThreadIdentifier> awake;
+    Vector<ThreadIdentifier> threads;
+    ThreadIdentifier lastAwoken { 0 };
+};
+
+void runParkingTest(unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
+{
+    std::unique_ptr<SingleLatchTest[]> tests = std::make_unique<SingleLatchTest[]>(numLatches);
+
+    for (unsigned latchIndex = numLatches; latchIndex--;)
+        tests[latchIndex].initialize(numThreads);
+
+    for (unsigned unparkIndex = 0; unparkIndex < numSingleUnparks; ++unparkIndex) {
+        std::this_thread::sleep_for(std::chrono::microseconds(delay));
+        for (unsigned latchIndex = numLatches; latchIndex--;)
+            tests[latchIndex].unparkOne(unparkIndex);
+    }
+
+    for (unsigned latchIndex = numLatches; latchIndex--;)
+        tests[latchIndex].finish(numSingleUnparks);
+}
+
+void repeatParkingTest(unsigned numRepeats, unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
+{
+    while (numRepeats--)
+        runParkingTest(numLatches, delay, numThreads, numSingleUnparks);
+}
+
+} // anonymous namespace
+
+TEST(WTF_ParkingLot, UnparkAllOneFast)
+{
+    repeatParkingTest(10000, 1, 0, 1, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkAllHundredFast)
+{
+    repeatParkingTest(100, 1, 0, 100, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkOneOneFast)
+{
+    repeatParkingTest(1000, 1, 0, 1, 1);
+}
+
+TEST(WTF_ParkingLot, UnparkOneHundredFast)
+{
+    repeatParkingTest(20, 1, 0, 100, 100);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAllFast)
+{
+    repeatParkingTest(50, 1, 0, 100, 50);
+}
+
+TEST(WTF_ParkingLot, UnparkAllOne)
+{
+    repeatParkingTest(100, 1, 10000, 1, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkAllHundred)
+{
+    repeatParkingTest(100, 1, 10000, 100, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkOneOne)
+{
+    repeatParkingTest(10, 1, 10000, 1, 1);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFifty)
+{
+    repeatParkingTest(1, 1, 10000, 50, 50);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAll)
+{
+    repeatParkingTest(2, 1, 10000, 100, 50);
+}
+
+TEST(WTF_ParkingLot, HundredUnparkAllOneFast)
+{
+    repeatParkingTest(100, 100, 0, 1, 0);
+}
+
+TEST(WTF_ParkingLot, HundredUnparkAllOne)
+{
+    repeatParkingTest(1, 100, 10000, 1, 0);
+}
+
+} // namespace TestWebKitAPI
+