QThreadPool: supersede cancel() with tryTake()

The cancel() function added in 5b11e43e for Qt 5.5 suffers from a
number of problems:

First, if runnable->autoDelete() is true, then the function suffers
from the ABA problem (see documentation written for trytake()).

Second, if runnable->autoDelete() is false, due to cancel() throwing
away crucial information instead of returning it, the caller cannot
know whether the runnable was canceled (and thus has to be deleted),
wasn't found or is currently executing (and thus mustn't be deleted),
or has finished executing (and can be used to extract the result).

Deprecate this dangerous API and replace it with the much more useful
Private::stealRunnable(), promoted to public API and renamed to
tryTake() for consistency with the rest of Qt.

Described the various caveats in the function's documentation.

[ChangeLog][QtCore][QThreadPool] The cancel() function suffers from
several subtle issues and has been replaced with a new tryTake()
function.

Change-Id: I93125935614087efa24b3e3969dd6718aeabaa4f
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>

4 files changed, 130 insertions, 18 deletions

diff --git a/src/corelib/thread/qthreadpool.cpp b/src/corelib/thread/qthreadpool.cpp
index 2ecf8f729a..e45aaec103 100644
--- a/src/corelib/thread/qthreadpool.cpp
+++ b/src/corelib/thread/qthreadpool.cpp
@@ -316,22 +316,39 @@ void QThreadPoolPrivate::clear()
 }
 
 /*!
-    \internal
-    Searches for \a runnable in the queue, removes it from the queue and
-    returns \c true if it was found in the queue
+    \since 5.9
+
+    Attempts to remove the specified \a runnable from the queue if it is not yet started.
+    If the runnable had not been started, returns \c true, and ownership of \a runnable
+    is transferred to the caller (even when \c{runnable->autoDelete() == true}).
+    Otherwise returns \c false.
+
+    \note If \c{runnable->autoDelete() == true}, this function may remove the wrong
+    runnable. This is known as the \l{https://en.wikipedia.org/wiki/ABA_problem}{ABA problem}:
+    the original \a runnable may already have executed and has since been deleted.
+    The memory is re-used for another runnable, which then gets removed instead of
+    the intended one. For this reason, we recommend calling this function only for
+    runnables that are not auto-deleting.
+
+    \sa start(), QRunnable::autoDelete()
 */
-bool QThreadPoolPrivate::stealRunnable(QRunnable *runnable)
+bool QThreadPool::tryTake(QRunnable *runnable)
 {
+    Q_D(QThreadPool);
+
     if (runnable == 0)
         return false;
     {
-        QMutexLocker locker(&mutex);
-        QVector<QPair<QRunnable *, int> >::iterator it = queue.begin();
-        QVector<QPair<QRunnable *, int> >::iterator end = queue.end();
+        QMutexLocker locker(&d->mutex);
+
+        auto it = d->queue.begin();
+        auto end = d->queue.end();
 
         while (it != end) {
             if (it->first == runnable) {
-                queue.erase(it);
+                d->queue.erase(it);
+                if (runnable->autoDelete())
+                    --runnable->ref; // undo ++ref in start()
                 return true;
             }
             ++it;
@@ -349,10 +366,10 @@ bool QThreadPoolPrivate::stealRunnable(QRunnable *runnable)
      */
 void QThreadPoolPrivate::stealAndRunRunnable(QRunnable *runnable)
 {
-    if (!stealRunnable(runnable))
+    Q_Q(QThreadPool);
+    if (!q->tryTake(runnable))
         return;
-    const bool autoDelete = runnable->autoDelete();
-    bool del = autoDelete && !--runnable->ref;
+    const bool del = runnable->autoDelete() && !runnable->ref; // tryTake already deref'ed
 
     runnable->run();
 
@@ -642,24 +659,23 @@ void QThreadPool::clear()
     d->clear();
 }
 
+#if QT_DEPRECATED_SINCE(5, 9)
 /*!
     \since 5.5
+    \obsolete use tryTake() instead, but note the different deletion rules.
 
     Removes the specified \a runnable from the queue if it is not yet started.
     The runnables for which \l{QRunnable::autoDelete()}{runnable->autoDelete()}
     returns \c true are deleted.
 
-    \sa start()
+    \sa start(), tryTake()
 */
 void QThreadPool::cancel(QRunnable *runnable)
 {
-    Q_D(QThreadPool);
-    if (!d->stealRunnable(runnable))
-        return;
-    if (runnable->autoDelete() && !--runnable->ref) {
+    if (tryTake(runnable) && runnable->autoDelete() && !runnable->ref) // tryTake already deref'ed
         delete runnable;
-    }
 }
+#endif
 
 QT_END_NAMESPACE
 
diff --git a/src/corelib/thread/qthreadpool.h b/src/corelib/thread/qthreadpool.h
index 0ad63c5ac3..74a8c28fc8 100644
--- a/src/corelib/thread/qthreadpool.h
+++ b/src/corelib/thread/qthreadpool.h
@@ -83,7 +83,12 @@ public:
     bool waitForDone(int msecs = -1);
 
     void clear();
+
+#if QT_DEPRECATED_SINCE(5, 9)
+    QT_DEPRECATED_X("use tryTake(), but note the different deletion rules")
     void cancel(QRunnable *runnable);
+#endif
+    bool tryTake(QRunnable *runnable) Q_REQUIRED_RESULT;
 };
 
 QT_END_NAMESPACE
diff --git a/src/corelib/thread/qthreadpool_p.h b/src/corelib/thread/qthreadpool_p.h
index ea8127efef..4a9f9e5cfa 100644
--- a/src/corelib/thread/qthreadpool_p.h
+++ b/src/corelib/thread/qthreadpool_p.h
@@ -82,7 +82,6 @@ public:
     void reset();
     bool waitForDone(int msecs);
     void clear();
-    bool stealRunnable(QRunnable *runnable);
     void stealAndRunRunnable(QRunnable *runnable);
 
     mutable QMutex mutex;
diff --git a/tests/auto/corelib/thread/qthreadpool/tst_qthreadpool.cpp b/tests/auto/corelib/thread/qthreadpool/tst_qthreadpool.cpp
index 5b7242fddb..fdc4ecb5c8 100644
--- a/tests/auto/corelib/thread/qthreadpool/tst_qthreadpool.cpp
+++ b/tests/auto/corelib/thread/qthreadpool/tst_qthreadpool.cpp
@@ -89,6 +89,7 @@ private slots:
     void waitForDone();
     void clear();
     void cancel();
+    void tryTake();
     void waitForDoneTimeout();
     void destroyingWaitsForTasksToFinish();
     void stressTest();
@@ -1042,6 +1043,97 @@ void tst_QThreadPool::cancel()
     delete runnables[runs-1];
 }
 
+void tst_QThreadPool::tryTake()
+{
+    QSemaphore sem(0);
+    QSemaphore startedThreads(0);
+
+    class SemaphoreReleaser
+    {
+        QSemaphore &sem;
+        int n;
+        Q_DISABLE_COPY(SemaphoreReleaser)
+    public:
+        explicit SemaphoreReleaser(QSemaphore &sem, int n)
+            : sem(sem), n(n) {}
+
+        ~SemaphoreReleaser()
+        {
+            sem.release(n);
+        }
+    };
+
+    class BlockingRunnable : public QRunnable
+    {
+    public:
+        QSemaphore &sem;
+        QSemaphore &startedThreads;
+        QAtomicInt &dtorCounter;
+        QAtomicInt &runCounter;
+        int dummy;
+
+        explicit BlockingRunnable(QSemaphore &s, QSemaphore &started, QAtomicInt &c, QAtomicInt &r)
+            : sem(s), startedThreads(started), dtorCounter(c), runCounter(r) {}
+
+        ~BlockingRunnable()
+        {
+            dtorCounter.fetchAndAddRelaxed(1);
+        }
+
+        void run() override
+        {
+            startedThreads.release();
+            runCounter.fetchAndAddRelaxed(1);
+            sem.acquire();
+            count.ref();
+        }
+    };
+
+    enum {
+        MaxThreadCount = 3,
+        OverProvisioning = 2,
+        Runs = MaxThreadCount * OverProvisioning
+    };
+
+    QThreadPool threadPool;
+    threadPool.setMaxThreadCount(MaxThreadCount);
+    BlockingRunnable *runnables[Runs];
+
+    // ensure that the QThreadPool doesn't deadlock if any of the checks fail
+    // and cause an early return:
+    const SemaphoreReleaser semReleaser(sem, Runs);
+
+    count.store(0);
+    QAtomicInt dtorCounter = 0;
+    QAtomicInt runCounter = 0;
+    for (int i = 0; i < Runs; i++) {
+        runnables[i] = new BlockingRunnable(sem, startedThreads, dtorCounter, runCounter);
+        runnables[i]->setAutoDelete(i != 0 && i != Runs - 1); // one which will run and one which will not
+        QVERIFY(!threadPool.tryTake(runnables[i])); // verify NOOP for jobs not in the queue
+        threadPool.start(runnables[i]);
+    }
+    // wait for all worker threads to have started up:
+    QVERIFY(startedThreads.tryAcquire(MaxThreadCount, 60*1000 /* 1min */));
+
+    for (int i = 0; i < MaxThreadCount; ++i) {
+        // check taking runnables doesn't work once they were started:
+        QVERIFY(!threadPool.tryTake(runnables[i]));
+    }
+    for (int i = MaxThreadCount; i < Runs ; ++i) {
+        QVERIFY(threadPool.tryTake(runnables[i]));
+        delete runnables[i];
+    }
+
+    runnables[0]->dummy = 0; // valgrind will catch this if tryTake() is crazy enough to delete currently running jobs
+    QCOMPARE(dtorCounter.load(), int(Runs - MaxThreadCount));
+    sem.release(MaxThreadCount);
+    threadPool.waitForDone();
+    QCOMPARE(runCounter.load(), int(MaxThreadCount));
+    QCOMPARE(count.load(), int(MaxThreadCount));
+    QCOMPARE(dtorCounter.load(), int(Runs - 1));
+    delete runnables[0]; // if the pool deletes them then we'll get double-free crash
+}
+
 void tst_QThreadPool::destroyingWaitsForTasksToFinish()
 {
     QTime total, pass;