Merge branch 'master' of scm.dev.nokia.troll.no:qt/oslo-staging-1 into master-integration

* 'master' of scm.dev.nokia.troll.no:qt/oslo-staging-1: (39 commits)
  Whitespace change
  Fix for coding conventions.
  Fix resource leak in QCLuceneStandardAnalyzer::QCLuceneStandardAnalyzer.
  Fix resource leak in QCLuceneStopAnalyzer::QCLuceneStopAnalyzer.
  Assistant: Get rid of bogus warning.
  add missing license header
  Add inter-process binary shader cache for MeeGo
  Track average wait times under our maximum spin time threshold
  Store and track spin times in nanosecond resolution
  Optimize adaptive spinning mutex code
  Improve QMutex contention performance on Linux
  Improve QMutex contention performance on Mac OS X
  Disable spinning under lock contention on single CPU machines
  Remove unnecessary testAndSetAcquire from QMutex::lockInternal()
  Move contender count maintenance to QMutexPrivate
  test contention when using 2 mutexes
  Ensure that every thread does contend in the contention tests
  Add baseline test data to measure test overhead
  Test contention performance for long (10ms) critical sections
  Add a benchmark for contended and uncontended QMutex performance
  ...

4 files changed, 162 insertions, 60 deletions

diff --git a/src/corelib/thread/qmutex.cpp b/src/corelib/thread/qmutex.cpp
index b85a22d..1009f7b 100644
--- a/src/corelib/thread/qmutex.cpp
+++ b/src/corelib/thread/qmutex.cpp
@@ -45,6 +45,7 @@
 
 #ifndef QT_NO_THREAD
 #include "qatomic.h"
+#include "qelapsedtimer.h"
 #include "qthread.h"
 #include "qmutex_p.h"
 
@@ -157,15 +158,12 @@ void QMutex::lock()
             return;
         }
 
-        bool isLocked = d->contenders.fetchAndAddAcquire(1) == 0;
+        bool isLocked = d->contenders.testAndSetAcquire(0, 1);
         if (!isLocked) {
             // didn't get the lock, wait for it
             isLocked = d->wait();
             Q_ASSERT_X(isLocked, "QMutex::lock",
                        "Internal error, infinite wait has timed out.");
-
-            // don't need to wait for the lock anymore
-            d->contenders.deref();
         }
 
         d->owner = self;
@@ -174,8 +172,7 @@ void QMutex::lock()
         return;
     }
 
-
-    bool isLocked = d->contenders == 0 && d->contenders.testAndSetAcquire(0, 1);
+    bool isLocked = d->contenders.testAndSetAcquire(0, 1);
     if (!isLocked) {
         lockInternal();
     }
@@ -211,7 +208,7 @@ bool QMutex::tryLock()
             return true;
         }
 
-        bool isLocked = d->contenders == 0 && d->contenders.testAndSetAcquire(0, 1);
+        bool isLocked = d->contenders.testAndSetAcquire(0, 1);
         if (!isLocked) {
             // some other thread has the mutex locked, or we tried to
             // recursively lock an non-recursive mutex
@@ -224,13 +221,7 @@ bool QMutex::tryLock()
         return isLocked;
     }
 
-    bool isLocked = d->contenders == 0 && d->contenders.testAndSetAcquire(0, 1);
-    if (!isLocked) {
-        // some other thread has the mutex locked, or we tried to
-        // recursively lock an non-recursive mutex
-        return isLocked;
-    }
-    return isLocked;
+    return d->contenders.testAndSetAcquire(0, 1);
 }
 
 /*! \overload
@@ -269,13 +260,10 @@ bool QMutex::tryLock(int timeout)
             return true;
         }
 
-        bool isLocked = d->contenders.fetchAndAddAcquire(1) == 0;
+        bool isLocked = d->contenders.testAndSetAcquire(0, 1);
         if (!isLocked) {
             // didn't get the lock, wait for it
             isLocked = d->wait(timeout);
-
-            // don't need to wait for the lock anymore
-            d->contenders.deref();
             if (!isLocked)
                 return false;
         }
@@ -286,17 +274,9 @@ bool QMutex::tryLock(int timeout)
         return true;
     }
 
-    bool isLocked = d->contenders.fetchAndAddAcquire(1) == 0;
-    if (!isLocked) {
-        // didn't get the lock, wait for it
-        isLocked = d->wait(timeout);
-
-        // don't need to wait for the lock anymore
-        d->contenders.deref();
-        if (!isLocked)
-            return false;
-    }
-    return true;
+    return (d->contenders.testAndSetAcquire(0, 1)
+            // didn't get the lock, wait for it
+            || d->wait(timeout));
 }
 
 
@@ -310,7 +290,6 @@ bool QMutex::tryLock(int timeout)
 void QMutex::unlock()
 {
     QMutexPrivate *d = static_cast<QMutexPrivate *>(this->d);
-
     if (d->recursive) {
         if (!--d->count) {
             d->owner = 0;
@@ -451,37 +430,57 @@ void QMutex::unlock()
 void QMutex::lockInternal()
 {
     QMutexPrivate *d = static_cast<QMutexPrivate *>(this->d);
-    int spinCount = 0;
-    int lastSpinCount = d->lastSpinCount;
 
-    enum { AdditionalSpins = 20, SpinCountPenalizationDivisor = 4 };
-    const int maximumSpinCount = lastSpinCount + AdditionalSpins;
+    if (QThread::idealThreadCount() == 1) {
+        // don't spin on single cpu machines
+        bool isLocked = d->wait();
+        Q_ASSERT_X(isLocked, "QMutex::lock",
+                   "Internal error, infinite wait has timed out.");
+        Q_UNUSED(isLocked);
+        return;
+    }
 
+    QElapsedTimer elapsedTimer;
+    elapsedTimer.start();
     do {
-        if (spinCount++ > maximumSpinCount) {
-            // puts("spinning useless, sleeping");
-            bool isLocked = d->contenders.fetchAndAddAcquire(1) == 0;
-            if (!isLocked) {
-
-                // didn't get the lock, wait for it
-                isLocked = d->wait();
-                Q_ASSERT_X(isLocked, "QMutex::lock",
-                            "Internal error, infinite wait has timed out.");
-
-                // don't need to wait for the lock anymore
-                d->contenders.deref();
+        qint64 spinTime = elapsedTimer.nsecsElapsed();
+        if (spinTime > d->maximumSpinTime) {
+            // didn't get the lock, wait for it, since we're not going to gain anything by spinning more
+            elapsedTimer.start();
+            bool isLocked = d->wait();
+            Q_ASSERT_X(isLocked, "QMutex::lock",
+                       "Internal error, infinite wait has timed out.");
+            Q_UNUSED(isLocked);
+
+            qint64 maximumSpinTime = d->maximumSpinTime;
+            qint64 averageWaitTime = d->averageWaitTime;
+            qint64 actualWaitTime = elapsedTimer.nsecsElapsed();
+            if (actualWaitTime < (QMutexPrivate::MaximumSpinTimeThreshold * 3 / 2)) {
+                // measure the wait times
+                averageWaitTime = d->averageWaitTime = qMin((averageWaitTime + actualWaitTime) / 2, qint64(QMutexPrivate::MaximumSpinTimeThreshold));
             }
-            // decrease the lastSpinCount since we didn't actually get the lock by spinning
-            spinCount = -d->lastSpinCount / SpinCountPenalizationDivisor;
-            break;
+
+            // adjust the spin count when spinning does not benefit contention performance
+            if ((spinTime + actualWaitTime) - qint64(QMutexPrivate::MaximumSpinTimeThreshold) >= qint64(QMutexPrivate::MaximumSpinTimeThreshold)) {
+                // long waits, stop spinning
+                d->maximumSpinTime = 0;
+            } else {
+                // allow spinning if wait times decrease, but never spin more than the average wait time (otherwise we may perform worse)
+                d->maximumSpinTime = qBound(qint64(averageWaitTime * 3 / 2), maximumSpinTime / 2, qint64(QMutexPrivate::MaximumSpinTimeThreshold));
+            }
+            return;
         }
+        // be a good citizen... yielding lets something else run if there is something to run, but may also relieve memory pressure if not
+        QThread::yieldCurrentThread();
     } while (d->contenders != 0 || !d->contenders.testAndSetAcquire(0, 1));
 
-    // adjust the last spin lock count
-    lastSpinCount = d->lastSpinCount;
-    d->lastSpinCount = spinCount >= 0
-                        ? qMax(lastSpinCount, spinCount)
-                        : lastSpinCount + spinCount;
+    // spinning is working, do not change the spin time (unless we are using much less time than allowed to spin)
+    qint64 maximumSpinTime = d->maximumSpinTime;
+    qint64 spinTime = elapsedTimer.nsecsElapsed();
+    if (spinTime < maximumSpinTime / 2) {
+        // we are using much less time than we need, adjust the limit
+        d->maximumSpinTime = qBound(qint64(d->averageWaitTime * 3 / 2), maximumSpinTime / 2, qint64(QMutexPrivate::MaximumSpinTimeThreshold));
+    }
 }
 
 /*!
diff --git a/src/corelib/thread/qmutex_p.h b/src/corelib/thread/qmutex_p.h
index 6126423..9d40bea 100644
--- a/src/corelib/thread/qmutex_p.h
+++ b/src/corelib/thread/qmutex_p.h
@@ -58,6 +58,10 @@
 #include <QtCore/qnamespace.h>
 #include <QtCore/qmutex.h>
 
+#if defined(Q_OS_MAC)
+# include <mach/semaphore.h>
+#endif
+
 QT_BEGIN_NAMESPACE
 
 class QMutexPrivate : public QMutexData {
@@ -65,15 +69,19 @@ public:
     QMutexPrivate(QMutex::RecursionMode mode);
     ~QMutexPrivate();
 
-    ulong self();
     bool wait(int timeout = -1);
     void wakeUp();
 
-    volatile int lastSpinCount;
+    // 1ms = 1000000ns
+    enum { MaximumSpinTimeThreshold = 1000000 };
+    volatile qint64 maximumSpinTime;
+    volatile qint64 averageWaitTime;
     Qt::HANDLE owner;
     uint count;
 
-#if defined(Q_OS_UNIX)
+#if defined(Q_OS_MAC)
+    semaphore_t mach_semaphore;
+#elif defined(Q_OS_UNIX) && !defined(Q_OS_LINUX)
     volatile bool wakeup;
     pthread_mutex_t mutex;
     pthread_cond_t cond;
diff --git a/src/corelib/thread/qmutex_unix.cpp b/src/corelib/thread/qmutex_unix.cpp
index 7e7ef22..0e09ea0 100644
--- a/src/corelib/thread/qmutex_unix.cpp
+++ b/src/corelib/thread/qmutex_unix.cpp
@@ -53,30 +53,116 @@
 #undef wakeup
 #endif
 
+#if defined(Q_OS_MAC)
+# include <mach/mach.h>
+# include <mach/task.h>
+#elif defined(Q_OS_LINUX)
+# include <linux/futex.h>
+# include <sys/syscall.h>
+# include <unistd.h>
+#endif
+
 QT_BEGIN_NAMESPACE
 
+#if !defined(Q_OS_MAC) && !defined(Q_OS_LINUX)
 static void report_error(int code, const char *where, const char *what)
 {
     if (code != 0)
         qWarning("%s: %s failure: %s", where, what, qPrintable(qt_error_string(code)));
 }
+#endif
 
 
 QMutexPrivate::QMutexPrivate(QMutex::RecursionMode mode)
-    : QMutexData(mode), lastSpinCount(0), owner(0), count(0), wakeup(false)
+    : QMutexData(mode), maximumSpinTime(MaximumSpinTimeThreshold), averageWaitTime(0), owner(0), count(0)
 {
+#if defined(Q_OS_MAC)
+    kern_return_t r = semaphore_create(mach_task_self(), &mach_semaphore, SYNC_POLICY_FIFO, 0);
+    if (r != KERN_SUCCESS)
+        qWarning("QMutex: failed to create semaphore, error %d", r);
+#elif !defined(Q_OS_LINUX)
+    wakeup = false;
     report_error(pthread_mutex_init(&mutex, NULL), "QMutex", "mutex init");
     report_error(pthread_cond_init(&cond, NULL), "QMutex", "cv init");
+#endif
 }
 
 QMutexPrivate::~QMutexPrivate()
 {
+#if defined(Q_OS_MAC)
+    kern_return_t r = semaphore_destroy(mach_task_self(), mach_semaphore);
+    if (r != KERN_SUCCESS)
+        qWarning("QMutex: failed to destroy semaphore, error %d", r);
+#elif !defined(Q_OS_LINUX)
     report_error(pthread_cond_destroy(&cond), "QMutex", "cv destroy");
     report_error(pthread_mutex_destroy(&mutex), "QMutex", "mutex destroy");
+#endif
+}
+
+#if defined(Q_OS_MAC)
+
+bool QMutexPrivate::wait(int timeout)
+{
+    if (contenders.fetchAndAddAcquire(1) == 0) {
+        // lock acquired without waiting
+        return true;
+    }
+    bool returnValue;
+    if (timeout < 0) {
+        returnValue = semaphore_wait(mach_semaphore) == KERN_SUCCESS;
+    } else {
+        mach_timespec_t ts;
+        ts.tv_nsec = ((timeout % 1000) * 1000) * 1000;
+        ts.tv_sec = (timeout / 1000);
+        kern_return_t r = semaphore_timedwait(mach_semaphore, ts);
+        returnValue = r == KERN_SUCCESS;
+    }
+    contenders.deref();
+    return returnValue;
+}
+
+void QMutexPrivate::wakeUp()
+{
+    semaphore_signal(mach_semaphore);
+}
+
+#elif defined(Q_OS_LINUX)
+
+static inline int _q_futex(volatile int *addr, int op, int val, const struct timespec *timeout, int *addr2, int val2)
+{
+    return syscall(SYS_futex, addr, op, val, timeout, addr2, val2);
 }
 
 bool QMutexPrivate::wait(int timeout)
 {
+    while (contenders.fetchAndStoreAcquire(2) > 0) {
+        struct timespec ts, *pts = 0;
+        if (timeout >= 0) {
+            ts.tv_nsec = ((timeout % 1000) * 1000) * 1000;
+            ts.tv_sec = (timeout / 1000);
+            pts = &ts;
+        }
+        int r = _q_futex(&contenders._q_value, FUTEX_WAIT, 2, pts, 0, 0);
+        if (r != 0 && errno == ETIMEDOUT)
+            return false;
+    }
+    return true;
+}
+
+void QMutexPrivate::wakeUp()
+{
+    (void) contenders.fetchAndStoreRelease(0);
+    (void) _q_futex(&contenders._q_value, FUTEX_WAKE, 1, 0, 0, 0);
+}
+
+#else // !Q_OS_MAC && !Q_OS_LINUX
+
+bool QMutexPrivate::wait(int timeout)
+{
+    if (contenders.fetchAndAddAcquire(1) == 0) {
+        // lock acquired without waiting
+        return true;
+    }
     report_error(pthread_mutex_lock(&mutex), "QMutex::lock", "mutex lock");
     int errorCode = 0;
     while (!wakeup) {
@@ -101,6 +187,7 @@ bool QMutexPrivate::wait(int timeout)
     }
     wakeup = false;
     report_error(pthread_mutex_unlock(&mutex), "QMutex::lock", "mutex unlock");
+    contenders.deref();
     return errorCode == 0;
 }
 
@@ -112,6 +199,8 @@ void QMutexPrivate::wakeUp()
     report_error(pthread_mutex_unlock(&mutex), "QMutex::unlock", "mutex unlock");
 }
 
+#endif // !Q_OS_MAC && !Q_OS_LINUX
+
 QT_END_NAMESPACE
 
 #endif // QT_NO_THREAD
diff --git a/src/corelib/thread/qmutex_win.cpp b/src/corelib/thread/qmutex_win.cpp
index a810000..a759caa 100644
--- a/src/corelib/thread/qmutex_win.cpp
+++ b/src/corelib/thread/qmutex_win.cpp
@@ -48,7 +48,7 @@
 QT_BEGIN_NAMESPACE
 
 QMutexPrivate::QMutexPrivate(QMutex::RecursionMode mode)
-    : QMutexData(mode), lastSpinCount(0), owner(0), count(0)
+    : QMutexData(mode), maximumSpinTime(MaximumSpinTimeThreshold), averageWaitTime(0), owner(0), count(0)
 {
     event = CreateEvent(0, FALSE, FALSE, 0);
     if (!event)
@@ -60,7 +60,13 @@ QMutexPrivate::~QMutexPrivate()
 
 bool QMutexPrivate::wait(int timeout)
 {
-    return WaitForSingleObject(event, timeout < 0 ? INFINITE : timeout) ==  WAIT_OBJECT_0;
+    if (contenders.fetchAndAddAcquire(1) == 0) {
+        // lock acquired without waiting
+        return true;
+    }
+    bool returnValue = (WaitForSingleObject(event, timeout < 0 ? INFINITE : timeout) ==  WAIT_OBJECT_0);
+    contenders.deref();
+    return returnValue;
 }
 
 void QMutexPrivate::wakeUp()