summaryrefslogtreecommitdiff
path: root/Source/WTF/benchmarks
diff options
context:
space:
mode:
Diffstat (limited to 'Source/WTF/benchmarks')
-rw-r--r--Source/WTF/benchmarks/ConditionSpeedTest.cpp245
-rw-r--r--Source/WTF/benchmarks/LockFairnessTest.cpp129
-rw-r--r--Source/WTF/benchmarks/LockSpeedTest.cpp200
-rw-r--r--Source/WTF/benchmarks/ToyLocks.h508
4 files changed, 1082 insertions, 0 deletions
diff --git a/Source/WTF/benchmarks/ConditionSpeedTest.cpp b/Source/WTF/benchmarks/ConditionSpeedTest.cpp
new file mode 100644
index 000000000..cb1d101e8
--- /dev/null
+++ b/Source/WTF/benchmarks/ConditionSpeedTest.cpp
@@ -0,0 +1,245 @@
+/*
+ * 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.
+ */
+
+// On Mac, you can build this like so:
+// clang++ -o ConditionSpeedTest Source/WTF/benchmarks/ConditionSpeedTest.cpp -O3 -W -ISource/WTF -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11
+
+#include "config.h"
+
+#include <mutex>
+#include <thread>
+#include <unistd.h>
+#include <wtf/Condition.h>
+#include <wtf/CurrentTime.h>
+#include <wtf/DataLog.h>
+#include <wtf/Deque.h>
+#include <wtf/Lock.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/StringPrintStream.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+#include <wtf/Vector.h>
+
+namespace {
+
+const bool verbose = false;
+
+unsigned numProducers;
+unsigned numConsumers;
+unsigned maxQueueSize;
+unsigned numMessagesPerProducer;
+
+NO_RETURN void usage()
+{
+ printf("Usage: ConditionSpeedTest lock|mutex|all <num producers> <num consumers> <max queue size> <num messages per producer>\n");
+ exit(1);
+}
+
+template<typename Functor, typename ConditionType, typename LockType>
+void wait(ConditionType& condition, LockType& lock, const Functor& predicate)
+{
+ while (!predicate())
+ condition.wait(lock);
+}
+
+template<typename LockType, typename ConditionType, typename NotifyFunctor, typename NotifyAllFunctor>
+void runTest(
+ unsigned numProducers,
+ unsigned numConsumers,
+ unsigned maxQueueSize,
+ unsigned numMessagesPerProducer,
+ const NotifyFunctor& notify,
+ const NotifyAllFunctor& notifyAll)
+{
+ Deque<unsigned> queue;
+ bool shouldContinue = true;
+ LockType lock;
+ ConditionType emptyCondition;
+ ConditionType fullCondition;
+
+ Vector<ThreadIdentifier> consumerThreads;
+ Vector<ThreadIdentifier> producerThreads;
+
+ Vector<unsigned> received;
+ LockType receivedLock;
+
+ for (unsigned i = numConsumers; i--;) {
+ ThreadIdentifier threadIdentifier = createThread(
+ "Consumer thread",
+ [&] () {
+ for (;;) {
+ unsigned result;
+ unsigned mustNotify = false;
+ {
+ std::unique_lock<LockType> locker(lock);
+ wait(
+ emptyCondition, lock,
+ [&] () {
+ if (verbose)
+ dataLog(toString(currentThread(), ": Checking consumption predicate with shouldContinue = ", shouldContinue, ", queue.size() == ", queue.size(), "\n"));
+ return !shouldContinue || !queue.isEmpty();
+ });
+ if (!shouldContinue && queue.isEmpty())
+ return;
+ mustNotify = queue.size() == maxQueueSize;
+ result = queue.takeFirst();
+ }
+ notify(fullCondition, mustNotify);
+
+ {
+ std::lock_guard<LockType> locker(receivedLock);
+ received.append(result);
+ }
+ }
+ });
+ consumerThreads.append(threadIdentifier);
+ }
+
+ for (unsigned i = numProducers; i--;) {
+ ThreadIdentifier threadIdentifier = createThread(
+ "Producer Thread",
+ [&] () {
+ for (unsigned i = 0; i < numMessagesPerProducer; ++i) {
+ bool mustNotify = false;
+ {
+ std::unique_lock<LockType> locker(lock);
+ wait(
+ fullCondition, lock,
+ [&] () {
+ if (verbose)
+ dataLog(toString(currentThread(), ": Checking production predicate with shouldContinue = ", shouldContinue, ", queue.size() == ", queue.size(), "\n"));
+ return queue.size() < maxQueueSize;
+ });
+ mustNotify = queue.isEmpty();
+ queue.append(i);
+ }
+ notify(emptyCondition, mustNotify);
+ }
+ });
+ producerThreads.append(threadIdentifier);
+ }
+
+ for (ThreadIdentifier threadIdentifier : producerThreads)
+ waitForThreadCompletion(threadIdentifier);
+
+ {
+ std::lock_guard<LockType> locker(lock);
+ shouldContinue = false;
+ }
+ notifyAll(emptyCondition);
+
+ for (ThreadIdentifier threadIdentifier : consumerThreads)
+ waitForThreadCompletion(threadIdentifier);
+
+ RELEASE_ASSERT(numProducers * numMessagesPerProducer == received.size());
+ std::sort(received.begin(), received.end());
+ for (unsigned messageIndex = 0; messageIndex < numMessagesPerProducer; ++messageIndex) {
+ for (unsigned producerIndex = 0; producerIndex < numProducers; ++producerIndex)
+ RELEASE_ASSERT(messageIndex == received[messageIndex * numProducers + producerIndex]);
+ }
+}
+
+template<typename LockType, typename ConditionType, typename NotifyFunctor, typename NotifyAllFunctor>
+void runBenchmark(
+ const char* name,
+ const NotifyFunctor& notify,
+ const NotifyAllFunctor& notifyAll)
+{
+ double before = monotonicallyIncreasingTimeMS();
+
+ runTest<LockType, ConditionType>(
+ numProducers,
+ numConsumers,
+ maxQueueSize,
+ numMessagesPerProducer,
+ notify,
+ notifyAll);
+
+ double after = monotonicallyIncreasingTimeMS();
+
+ printf("%s: %.3lf ms.\n", name, after - before);
+}
+
+} // anonymous namespace
+
+int main(int argc, char** argv)
+{
+ WTF::initializeThreading();
+
+ if (argc != 6
+ || sscanf(argv[2], "%u", &numProducers) != 1
+ || sscanf(argv[3], "%u", &numConsumers) != 1
+ || sscanf(argv[4], "%u", &maxQueueSize) != 1
+ || sscanf(argv[5], "%u", &numMessagesPerProducer) != 1)
+ usage();
+
+ bool didRun = false;
+ if (!strcmp(argv[1], "lock") || !strcmp(argv[1], "all")) {
+ runBenchmark<Lock, Condition>(
+ "WTF Lock NotifyOne",
+ [&] (Condition& condition, bool mustNotify) {
+ condition.notifyOne();
+ },
+ [&] (Condition& condition) {
+ condition.notifyAll();
+ });
+ runBenchmark<Lock, Condition>(
+ "WTF Lock NotifyAll",
+ [&] (Condition& condition, bool mustNotify) {
+ if (mustNotify)
+ condition.notifyAll();
+ },
+ [&] (Condition& condition) {
+ condition.notifyAll();
+ });
+ didRun = true;
+ }
+ if (!strcmp(argv[1], "mutex") || !strcmp(argv[1], "all")) {
+ runBenchmark<Mutex, ThreadCondition>(
+ "Platform Mutex NotifyOne",
+ [&] (ThreadCondition& condition, bool mustNotify) {
+ condition.signal();
+ },
+ [&] (ThreadCondition& condition) {
+ condition.broadcast();
+ });
+ runBenchmark<Mutex, ThreadCondition>(
+ "Platform Mutex NotifyAll",
+ [&] (ThreadCondition& condition, bool mustNotify) {
+ if (mustNotify)
+ condition.broadcast();
+ },
+ [&] (ThreadCondition& condition) {
+ condition.broadcast();
+ });
+ didRun = true;
+ }
+
+ if (!didRun)
+ usage();
+
+ return 0;
+}
+
diff --git a/Source/WTF/benchmarks/LockFairnessTest.cpp b/Source/WTF/benchmarks/LockFairnessTest.cpp
new file mode 100644
index 000000000..f08321c0f
--- /dev/null
+++ b/Source/WTF/benchmarks/LockFairnessTest.cpp
@@ -0,0 +1,129 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+// On Mac, you can build this like so:
+// xcrun clang++ -o LockFairnessTest Source/WTF/benchmarks/LockFairnessTest.cpp -O3 -W -ISource/WTF -ISource/WTF/benchmarks -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11 -fvisibility=hidden
+
+#include "config.h"
+
+#include "ToyLocks.h"
+#include <thread>
+#include <unistd.h>
+#include <wtf/CommaPrinter.h>
+#include <wtf/CurrentTime.h>
+#include <wtf/DataLog.h>
+#include <wtf/HashMap.h>
+#include <wtf/Lock.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+#include <wtf/Vector.h>
+#include <wtf/WordLock.h>
+#include <wtf/text/CString.h>
+
+namespace {
+
+NO_RETURN void usage()
+{
+ printf("Usage: LockFairnessTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num threads> <seconds per test> <microseconds in critical section>\n");
+ exit(1);
+}
+
+unsigned numThreads;
+double secondsPerTest;
+unsigned microsecondsInCriticalSection;
+
+struct Benchmark {
+ template<typename LockType>
+ static void run(const char* name)
+ {
+ LockType lock;
+ std::unique_ptr<unsigned[]> counts = std::make_unique<unsigned[]>(numThreads);
+ std::unique_ptr<ThreadIdentifier[]> threads = std::make_unique<ThreadIdentifier[]>(numThreads);
+
+ volatile bool keepGoing = true;
+
+ lock.lock();
+
+ for (unsigned threadIndex = numThreads; threadIndex--;) {
+ counts[threadIndex] = 0;
+ threads[threadIndex] = createThread(
+ "Benchmark Thread",
+ [&, threadIndex] () {
+ if (!microsecondsInCriticalSection) {
+ while (keepGoing) {
+ lock.lock();
+ counts[threadIndex]++;
+ lock.unlock();
+ }
+ return;
+ }
+
+ while (keepGoing) {
+ lock.lock();
+ counts[threadIndex]++;
+ usleep(microsecondsInCriticalSection);
+ lock.unlock();
+ }
+ });
+ }
+
+ sleepMS(100);
+ lock.unlock();
+
+ sleep(secondsPerTest);
+
+ keepGoing = false;
+ lock.lock();
+
+ dataLog(name, ": ");
+ CommaPrinter comma;
+ for (unsigned threadIndex = numThreads; threadIndex--;)
+ dataLog(comma, counts[threadIndex]);
+ dataLog("\n");
+
+ lock.unlock();
+ for (unsigned threadIndex = numThreads; threadIndex--;)
+ waitForThreadCompletion(threads[threadIndex]);
+ }
+};
+
+} // anonymous namespace
+
+int main(int argc, char** argv)
+{
+ WTF::initializeThreading();
+
+ if (argc != 5
+ || sscanf(argv[2], "%u", &numThreads) != 1
+ || sscanf(argv[3], "%lf", &secondsPerTest) != 1
+ || sscanf(argv[4], "%u", &microsecondsInCriticalSection) != 1)
+ usage();
+
+ runEverything<Benchmark>(argv[1]);
+
+ return 0;
+}
diff --git a/Source/WTF/benchmarks/LockSpeedTest.cpp b/Source/WTF/benchmarks/LockSpeedTest.cpp
new file mode 100644
index 000000000..545d2e0b0
--- /dev/null
+++ b/Source/WTF/benchmarks/LockSpeedTest.cpp
@@ -0,0 +1,200 @@
+/*
+ * Copyright (C) 2015-2016 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.
+ */
+
+// On Mac, you can build this like so:
+// xcrun clang++ -o LockSpeedTest Source/WTF/benchmarks/LockSpeedTest.cpp -O3 -W -ISource/WTF -ISource/WTF/benchmarks -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11 -fvisibility=hidden
+
+#include "config.h"
+
+#include "ToyLocks.h"
+#include <thread>
+#include <unistd.h>
+#include <wtf/CurrentTime.h>
+#include <wtf/DataLog.h>
+#include <wtf/HashMap.h>
+#include <wtf/Lock.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+#include <wtf/Vector.h>
+#include <wtf/WordLock.h>
+#include <wtf/text/CString.h>
+
+namespace {
+
+unsigned numThreadGroups;
+unsigned numThreadsPerGroup;
+unsigned workPerCriticalSection;
+unsigned workBetweenCriticalSections;
+double secondsPerTest;
+
+NO_RETURN void usage()
+{
+ printf("Usage: LockSpeedTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num thread groups> <num threads per group> <work per critical section> <work between critical sections> <spin limit> <seconds per test>\n");
+ exit(1);
+}
+
+template<typename Type>
+struct WithPadding {
+ Type value;
+ char buf[300]; // It's best if this isn't perfect to avoid false sharing.
+};
+
+HashMap<CString, Vector<double>> results;
+
+void reportResult(const char* name, double value)
+{
+ dataLogF("%s: %.3lf KHz\n", name, value);
+ results.add(name, Vector<double>()).iterator->value.append(value);
+}
+
+struct Benchmark {
+ template<typename LockType>
+ static void run(const char* name)
+ {
+ std::unique_ptr<WithPadding<LockType>[]> locks = std::make_unique<WithPadding<LockType>[]>(numThreadGroups);
+ std::unique_ptr<WithPadding<double>[]> words = std::make_unique<WithPadding<double>[]>(numThreadGroups);
+ std::unique_ptr<ThreadIdentifier[]> threads = std::make_unique<ThreadIdentifier[]>(numThreadGroups * numThreadsPerGroup);
+
+ volatile bool keepGoing = true;
+
+ double before = monotonicallyIncreasingTime();
+
+ Lock numIterationsLock;
+ uint64_t numIterations = 0;
+
+ for (unsigned threadGroupIndex = numThreadGroups; threadGroupIndex--;) {
+ words[threadGroupIndex].value = 0;
+
+ for (unsigned threadIndex = numThreadsPerGroup; threadIndex--;) {
+ threads[threadGroupIndex * numThreadsPerGroup + threadIndex] = createThread(
+ "Benchmark thread",
+ [threadGroupIndex, &locks, &words, &keepGoing, &numIterationsLock, &numIterations] () {
+ double localWord = 0;
+ double value = 1;
+ unsigned myNumIterations = 0;
+ while (keepGoing) {
+ locks[threadGroupIndex].value.lock();
+ for (unsigned j = workPerCriticalSection; j--;) {
+ words[threadGroupIndex].value += value;
+ words[threadGroupIndex].value *= 1.01;
+ value = words[threadGroupIndex].value;
+ }
+ locks[threadGroupIndex].value.unlock();
+ for (unsigned j = workBetweenCriticalSections; j--;) {
+ localWord += value;
+ localWord *= 1.01;
+ value = localWord;
+ }
+ myNumIterations++;
+ }
+ LockHolder locker(numIterationsLock);
+ numIterations += myNumIterations;
+ });
+ }
+ }
+
+ sleep(secondsPerTest);
+ keepGoing = false;
+
+ for (unsigned threadIndex = numThreadGroups * numThreadsPerGroup; threadIndex--;)
+ waitForThreadCompletion(threads[threadIndex]);
+
+ double after = monotonicallyIncreasingTime();
+
+ reportResult(name, numIterations / (after - before) / 1000);
+ }
+};
+
+unsigned rangeMin;
+unsigned rangeMax;
+unsigned rangeStep;
+unsigned* rangeVariable;
+
+bool parseValue(const char* string, unsigned* variable)
+{
+ unsigned myRangeMin;
+ unsigned myRangeMax;
+ unsigned myRangeStep;
+ if (sscanf(string, "%u-%u:%u", &myRangeMin, &myRangeMax, &myRangeStep) == 3) {
+ if (rangeVariable) {
+ fprintf(stderr, "Can only have one variable with a range.\n");
+ return false;
+ }
+
+ rangeMin = myRangeMin;
+ rangeMax = myRangeMax;
+ rangeStep = myRangeStep;
+ rangeVariable = variable;
+ return true;
+ }
+
+ if (sscanf(string, "%u", variable) == 1)
+ return true;
+
+ return false;
+}
+
+} // anonymous namespace
+
+int main(int argc, char** argv)
+{
+ WTF::initializeThreading();
+
+ if (argc != 8
+ || !parseValue(argv[2], &numThreadGroups)
+ || !parseValue(argv[3], &numThreadsPerGroup)
+ || !parseValue(argv[4], &workPerCriticalSection)
+ || !parseValue(argv[5], &workBetweenCriticalSections)
+ || !parseValue(argv[6], &toyLockSpinLimit)
+ || sscanf(argv[7], "%lf", &secondsPerTest) != 1)
+ usage();
+
+ if (rangeVariable) {
+ dataLog("Running with rangeMin = ", rangeMin, ", rangeMax = ", rangeMax, ", rangeStep = ", rangeStep, "\n");
+ for (unsigned value = rangeMin; value <= rangeMax; value += rangeStep) {
+ dataLog("Running with value = ", value, "\n");
+ *rangeVariable = value;
+ runEverything<Benchmark>(argv[1]);
+ }
+ } else
+ runEverything<Benchmark>(argv[1]);
+
+ for (auto& entry : results) {
+ printf("%s = {", entry.key.data());
+ bool first = true;
+ for (double value : entry.value) {
+ if (first)
+ first = false;
+ else
+ printf(", ");
+ printf("%.3lf", value);
+ }
+ printf("};\n");
+ }
+
+ return 0;
+}
diff --git a/Source/WTF/benchmarks/ToyLocks.h b/Source/WTF/benchmarks/ToyLocks.h
new file mode 100644
index 000000000..43ad7960a
--- /dev/null
+++ b/Source/WTF/benchmarks/ToyLocks.h
@@ -0,0 +1,508 @@
+/*
+ * Copyright (C) 2015-2016 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 ToyLocks_h
+#define ToyLocks_h
+
+#include <thread>
+#include <wtf/Atomics.h>
+#include <wtf/Lock.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/WordLock.h>
+
+#if defined(EXTRA_LOCKS) && EXTRA_LOCKS
+#include <synchronic>
+#endif
+
+namespace {
+
+unsigned toyLockSpinLimit = 40;
+
+// This is the old WTF::SpinLock class, included here so that we can still compare our new locks to a
+// spinlock baseline.
+class YieldSpinLock {
+public:
+ YieldSpinLock()
+ {
+ m_lock.store(0, std::memory_order_relaxed);
+ }
+
+ void lock()
+ {
+ while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
+ std::this_thread::yield();
+ }
+
+ void unlock()
+ {
+ m_lock.store(0, std::memory_order_release);
+ }
+
+ bool isLocked() const
+ {
+ return m_lock.load(std::memory_order_acquire);
+ }
+
+private:
+ Atomic<unsigned> m_lock;
+};
+
+class PauseSpinLock {
+public:
+ PauseSpinLock()
+ {
+ m_lock.store(0, std::memory_order_relaxed);
+ }
+
+ void lock()
+ {
+ while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
+ asm volatile ("pause");
+ }
+
+ void unlock()
+ {
+ m_lock.store(0, std::memory_order_release);
+ }
+
+ bool isLocked() const
+ {
+ return m_lock.load(std::memory_order_acquire);
+ }
+
+private:
+ Atomic<unsigned> m_lock;
+};
+
+#if defined(EXTRA_LOCKS) && EXTRA_LOCKS
+class TransactionalSpinLock {
+public:
+ TransactionalSpinLock()
+ {
+ m_lock = 0;
+ }
+
+ void lock()
+ {
+ for (;;) {
+ unsigned char result;
+ unsigned expected = 0;
+ unsigned desired = 1;
+ asm volatile (
+ "xacquire; lock; cmpxchgl %3, %2\n\t"
+ "sete %1"
+ : "+a"(expected), "=q"(result), "+m"(m_lock)
+ : "r"(desired)
+ : "memory");
+ if (result)
+ return;
+ std::this_thread::yield();
+ }
+ }
+
+ void unlock()
+ {
+ asm volatile (
+ "xrelease; movl $0, %0"
+ :
+ : "m"(m_lock)
+ : "memory");
+ }
+
+ bool isLocked() const
+ {
+ return m_lock;
+ }
+
+private:
+ unsigned m_lock;
+};
+
+class SynchronicLock {
+public:
+ SynchronicLock()
+ : m_locked(0)
+ {
+ }
+
+ void lock()
+ {
+ for (;;) {
+ int state = 0;
+ if (m_locked.compare_exchange_weak(state, 1, std::memory_order_acquire))
+ return;
+ m_sync.wait_for_change(m_locked, state, std::memory_order_relaxed);
+ }
+ }
+
+ void unlock()
+ {
+ m_sync.notify_one(m_locked, 0, std::memory_order_release);
+ }
+
+ bool isLocked()
+ {
+ return m_locked.load();
+ }
+
+private:
+ std::atomic<int> m_locked;
+ std::experimental::synchronic<int> m_sync;
+};
+#endif
+
+template<typename StateType>
+class BargingLock {
+public:
+ BargingLock()
+ {
+ m_state.store(0);
+ }
+
+ void lock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
+ return;
+
+ lockSlow();
+ }
+
+ void unlock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
+ return;
+
+ unlockSlow();
+ }
+
+ bool isLocked() const
+ {
+ return m_state.load(std::memory_order_acquire) & isLockedBit;
+ }
+
+private:
+ NEVER_INLINE void lockSlow()
+ {
+ for (unsigned i = toyLockSpinLimit; i--;) {
+ StateType currentState = m_state.load();
+
+ if (!(currentState & isLockedBit)
+ && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
+ return;
+
+ if (currentState & hasParkedBit)
+ break;
+
+ std::this_thread::yield();
+ }
+
+ for (;;) {
+ StateType currentState = m_state.load();
+
+ if (!(currentState & isLockedBit)
+ && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
+ return;
+
+ m_state.compareExchangeWeak(isLockedBit, isLockedBit | hasParkedBit);
+
+ ParkingLot::compareAndPark(&m_state, isLockedBit | hasParkedBit);
+ }
+ }
+
+ NEVER_INLINE void unlockSlow()
+ {
+ ParkingLot::unparkOne(
+ &m_state,
+ [this] (ParkingLot::UnparkResult result) -> intptr_t {
+ if (result.mayHaveMoreThreads)
+ m_state.store(hasParkedBit);
+ else
+ m_state.store(0);
+ return 0;
+ });
+ }
+
+ static const StateType isLockedBit = 1;
+ static const StateType hasParkedBit = 2;
+
+ Atomic<StateType> m_state;
+};
+
+template<typename StateType>
+class ThunderLock {
+public:
+ ThunderLock()
+ {
+ m_state.store(Unlocked);
+ }
+
+ void lock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
+ return;
+
+ lockSlow();
+ }
+
+ void unlock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
+ return;
+
+ unlockSlow();
+ }
+
+ bool isLocked() const
+ {
+ return m_state.load(std::memory_order_acquire) != Unlocked;
+ }
+
+private:
+ NEVER_INLINE void lockSlow()
+ {
+ for (unsigned i = toyLockSpinLimit; i--;) {
+ State currentState = m_state.load();
+
+ if (currentState == Unlocked
+ && m_state.compareExchangeWeak(Unlocked, Locked))
+ return;
+
+ if (currentState == LockedAndParked)
+ break;
+
+ std::this_thread::yield();
+ }
+
+ for (;;) {
+ if (m_state.compareExchangeWeak(Unlocked, Locked))
+ return;
+
+ m_state.compareExchangeWeak(Locked, LockedAndParked);
+ ParkingLot::compareAndPark(&m_state, LockedAndParked);
+ }
+ }
+
+ NEVER_INLINE void unlockSlow()
+ {
+ if (m_state.exchange(Unlocked) == LockedAndParked)
+ ParkingLot::unparkAll(&m_state);
+ }
+
+ enum State : StateType {
+ Unlocked,
+ Locked,
+ LockedAndParked
+ };
+
+ Atomic<State> m_state;
+};
+
+template<typename StateType>
+class CascadeLock {
+public:
+ CascadeLock()
+ {
+ m_state.store(Unlocked);
+ }
+
+ void lock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
+ return;
+
+ lockSlow();
+ }
+
+ void unlock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
+ return;
+
+ unlockSlow();
+ }
+
+ bool isLocked() const
+ {
+ return m_state.load(std::memory_order_acquire) != Unlocked;
+ }
+
+private:
+ NEVER_INLINE void lockSlow()
+ {
+ for (unsigned i = toyLockSpinLimit; i--;) {
+ State currentState = m_state.load();
+
+ if (currentState == Unlocked
+ && m_state.compareExchangeWeak(Unlocked, Locked))
+ return;
+
+ if (currentState == LockedAndParked)
+ break;
+
+ std::this_thread::yield();
+ }
+
+ State desiredState = Locked;
+ for (;;) {
+ if (m_state.compareExchangeWeak(Unlocked, desiredState))
+ return;
+
+ desiredState = LockedAndParked;
+ m_state.compareExchangeWeak(Locked, LockedAndParked);
+ ParkingLot::compareAndPark(&m_state, LockedAndParked);
+ }
+ }
+
+ NEVER_INLINE void unlockSlow()
+ {
+ if (m_state.exchange(Unlocked) == LockedAndParked)
+ ParkingLot::unparkOne(&m_state);
+ }
+
+ enum State : StateType {
+ Unlocked,
+ Locked,
+ LockedAndParked
+ };
+
+ Atomic<State> m_state;
+};
+
+class HandoffLock {
+public:
+ HandoffLock()
+ {
+ m_state.store(0);
+ }
+
+ void lock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
+ return;
+
+ lockSlow();
+ }
+
+ void unlock()
+ {
+ if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
+ return;
+
+ unlockSlow();
+ }
+
+ bool isLocked() const
+ {
+ return m_state.load(std::memory_order_acquire) & isLockedBit;
+ }
+
+private:
+ NEVER_INLINE void lockSlow()
+ {
+ for (;;) {
+ unsigned state = m_state.load();
+
+ if (!(state & isLockedBit)) {
+ if (m_state.compareExchangeWeak(state, state | isLockedBit))
+ return;
+ continue;
+ }
+
+ if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
+ bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit).wasUnparked;
+ m_state.exchangeAndAdd(-parkedCountUnit);
+ if (result)
+ return;
+ }
+ }
+ }
+
+ NEVER_INLINE void unlockSlow()
+ {
+ for (;;) {
+ unsigned state = m_state.load();
+
+ if (!(state >> parkedCountShift)) {
+ RELEASE_ASSERT(state == isLockedBit);
+ if (m_state.compareExchangeWeak(isLockedBit, 0))
+ return;
+ continue;
+ }
+
+ if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
+ // We unparked someone. There are now running and they hold the lock.
+ return;
+ }
+
+ // Nobody unparked. Maybe there isn't anyone waiting. Just try again.
+ }
+ }
+
+ static const unsigned isLockedBit = 1;
+ static const unsigned parkedCountShift = 1;
+ static const unsigned parkedCountUnit = 1 << parkedCountShift;
+
+ Atomic<unsigned> m_state;
+};
+
+template<typename Benchmark>
+void runEverything(const char* what)
+{
+ if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
+ Benchmark::template run<YieldSpinLock>("YieldSpinLock");
+ if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
+ Benchmark::template run<PauseSpinLock>("PauseSpinLock");
+#if defined(EXTRA_LOCKS) && EXTRA_LOCKS
+ if (!strcmp(what, "transactionalspinlock") || !strcmp(what, "all"))
+ Benchmark::template run<TransactionalSpinLock>("TransactionalSpinLock");
+ if (!strcmp(what, "synchroniclock") || !strcmp(what, "all"))
+ Benchmark::template run<SynchronicLock>("SynchronicLock");
+#endif
+ if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
+ Benchmark::template run<WordLock>("WTFWordLock");
+ if (!strcmp(what, "lock") || !strcmp(what, "all"))
+ Benchmark::template run<Lock>("WTFLock");
+ if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
+ Benchmark::template run<BargingLock<uint8_t>>("ByteBargingLock");
+ if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
+ Benchmark::template run<BargingLock<uint32_t>>("WordBargingLock");
+ if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
+ Benchmark::template run<ThunderLock<uint8_t>>("ByteThunderLock");
+ if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
+ Benchmark::template run<ThunderLock<uint32_t>>("WordThunderLock");
+ if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
+ Benchmark::template run<CascadeLock<uint8_t>>("ByteCascadeLock");
+ if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
+ Benchmark::template run<CascadeLock<uint32_t>>("WordCascadeLock");
+ if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
+ Benchmark::template run<HandoffLock>("HandoffLock");
+ if (!strcmp(what, "mutex") || !strcmp(what, "all"))
+ Benchmark::template run<Mutex>("PlatformMutex");
+}
+
+} // anonymous namespace
+
+#endif // ToyLocks_h
+
View Lorry Controller Status