qreadwritelock.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Copyright (C) 2016 Intel Corporation.
** Copyright (C) 2016 Olivier Goffart <ogoffart@woboq.com>
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
 
#include "qplatformdefs.h"
#include "qreadwritelock.h"
 
#include "qmutex.h"
#include "qthread.h"
#include "qwaitcondition.h"
#include "qreadwritelock_p.h"
#include "qelapsedtimer.h"
#include "private/qfreelist_p.h"
#include "private/qlocking_p.h"
 
#include <algorithm>
 
QT_BEGIN_NAMESPACE
 
/*
 * Implementation details of QReadWriteLock:
 *
 * Depending on the valued of d_ptr, the lock is in the following state:
 *  - when d_ptr == 0x0: Unlocked (no readers, no writers) and non-recursive.
 *  - when d_ptr & 0x1: If the least significant bit is set, we are locked for read.
 *    In that case, d_ptr>>4 represents the number of reading threads minus 1. No writers
 *    are waiting, and the lock is not recursive.
 *  - when d_ptr == 0x2: We are locked for write and nobody is waiting. (no contention)
 *  - In any other case, d_ptr points to an actual QReadWriteLockPrivate.
 */
 
namespace {
 
using ms = std::chrono::milliseconds;
 
enum {
    StateMask = 0x3,
    StateLockedForRead = 0x1,
    StateLockedForWrite = 0x2,
};
const auto dummyLockedForRead = reinterpret_cast<QReadWriteLockPrivate *>(quintptr(StateLockedForRead));
const auto dummyLockedForWrite = reinterpret_cast<QReadWriteLockPrivate *>(quintptr(StateLockedForWrite));
inline bool isUncontendedLocked(const QReadWriteLockPrivate *d)
{ return quintptr(d) & StateMask; }
}
 
QReadWriteLock::QReadWriteLock(RecursionMode recursionMode)
    : d_ptr(recursionMode == Recursive ? new QReadWriteLockPrivate(true) : nullptr)
{
    Q_ASSERT_X(!(quintptr(d_ptr.loadRelaxed()) & StateMask), "QReadWriteLock::QReadWriteLock", "bad d_ptr alignment");
}
 
QReadWriteLock::~QReadWriteLock()
{
    auto d = d_ptr.loadAcquire();
    if (isUncontendedLocked(d)) {
        qWarning("QReadWriteLock: destroying locked QReadWriteLock");
        return;
    }
    delete d;
}
 
void QReadWriteLock::lockForRead()
{
    if (d_ptr.testAndSetAcquire(nullptr, dummyLockedForRead))
        return;
    tryLockForRead(-1);
}
 
bool QReadWriteLock::tryLockForRead()
{
    return tryLockForRead(0);
}
 
bool QReadWriteLock::tryLockForRead(int timeout)
{
    // Fast case: non contended:
    QReadWriteLockPrivate *d;
    if (d_ptr.testAndSetAcquire(nullptr, dummyLockedForRead, d))
        return true;
 
    while (true) {
        if (d == nullptr) {
            if (!d_ptr.testAndSetAcquire(nullptr, dummyLockedForRead, d))
                continue;
            return true;
        }
 
        if ((quintptr(d) & StateMask) == StateLockedForRead) {
            // locked for read, increase the counter
            const auto val = reinterpret_cast<QReadWriteLockPrivate *>(quintptr(d) + (1U<<4));
            Q_ASSERT_X(quintptr(val) > (1U<<4), "QReadWriteLock::tryLockForRead()",
                       "Overflow in lock counter");
            if (!d_ptr.testAndSetAcquire(d, val, d))
                continue;
            return true;
        }
 
        if (d == dummyLockedForWrite) {
            if (!timeout)
                return false;
 
            // locked for write, assign a d_ptr and wait.
            auto val = QReadWriteLockPrivate::allocate();
            val->writerCount = 1;
            if (!d_ptr.testAndSetOrdered(d, val, d)) {
                val->writerCount = 0;
                val->release();
                continue;
            }
            d = val;
        }
        Q_ASSERT(!isUncontendedLocked(d));
        // d is an actual pointer;
 
        if (d->recursive)
            return d->recursiveLockForRead(timeout);
 
        auto lock = qt_unique_lock(d->mutex);
        if (d != d_ptr.loadRelaxed()) {
            // d_ptr has changed: this QReadWriteLock was unlocked before we had
            // time to lock d->mutex.
            // We are holding a lock to a mutex within a QReadWriteLockPrivate
            // that is already released (or even is already re-used). That's ok
            // because the QFreeList never frees them.
            // Just unlock d->mutex (at the end of the scope) and retry.
            d = d_ptr.loadAcquire();
            continue;
        }
        return d->lockForRead(lock, timeout);
    }
}
 
void QReadWriteLock::lockForWrite()
{
    tryLockForWrite(-1);
}
 
bool QReadWriteLock::tryLockForWrite()
{
    return tryLockForWrite(0);
}
 
bool QReadWriteLock::tryLockForWrite(int timeout)
{
    // Fast case: non contended:
    QReadWriteLockPrivate *d;
    if (d_ptr.testAndSetAcquire(nullptr, dummyLockedForWrite, d))
        return true;
 
    while (true) {
        if (d == nullptr) {
            if (!d_ptr.testAndSetAcquire(d, dummyLockedForWrite, d))
                continue;
            return true;
        }
 
        if (isUncontendedLocked(d)) {
            if (!timeout)
                return false;
 
            // locked for either read or write, assign a d_ptr and wait.
            auto val = QReadWriteLockPrivate::allocate();
            if (d == dummyLockedForWrite)
                val->writerCount = 1;
            else
                val->readerCount = (quintptr(d) >> 4) + 1;
            if (!d_ptr.testAndSetOrdered(d, val, d)) {
                val->writerCount = val->readerCount = 0;
                val->release();
                continue;
            }
            d = val;
        }
        Q_ASSERT(!isUncontendedLocked(d));
        // d is an actual pointer;
 
        if (d->recursive)
            return d->recursiveLockForWrite(timeout);
 
        auto lock = qt_unique_lock(d->mutex);
        if (d != d_ptr.loadRelaxed()) {
            // The mutex was unlocked before we had time to lock the mutex.
            // We are holding to a mutex within a QReadWriteLockPrivate that is already released
            // (or even is already re-used) but that's ok because the QFreeList never frees them.
            d = d_ptr.loadAcquire();
            continue;
        }
        return d->lockForWrite(lock, timeout);
    }
}
 
void QReadWriteLock::unlock()
{
    QReadWriteLockPrivate *d = d_ptr.loadAcquire();
    while (true) {
        Q_ASSERT_X(d, "QReadWriteLock::unlock()", "Cannot unlock an unlocked lock");
 
        // Fast case: no contention: (no waiters, no other readers)
        if (quintptr(d) <= 2) { // 1 or 2 (StateLockedForRead or StateLockedForWrite)
            if (!d_ptr.testAndSetOrdered(d, nullptr, d))
                continue;
            return;
        }
 
        if ((quintptr(d) & StateMask) == StateLockedForRead) {
            Q_ASSERT(quintptr(d) > (1U<<4)); //otherwise that would be the fast case
            // Just decrease the reader's count.
            auto val = reinterpret_cast<QReadWriteLockPrivate *>(quintptr(d) - (1U<<4));
            if (!d_ptr.testAndSetOrdered(d, val, d))
                continue;
            return;
        }
 
        Q_ASSERT(!isUncontendedLocked(d));
 
        if (d->recursive) {
            d->recursiveUnlock();
            return;
        }
 
        const auto lock = qt_scoped_lock(d->mutex);
        if (d->writerCount) {
            Q_ASSERT(d->writerCount == 1);
            Q_ASSERT(d->readerCount == 0);
            d->writerCount = 0;
        } else {
            Q_ASSERT(d->readerCount > 0);
            d->readerCount--;
            if (d->readerCount > 0)
                return;
        }
 
        if (d->waitingReaders || d->waitingWriters) {
            d->unlock();
        } else {
            Q_ASSERT(d_ptr.loadRelaxed() == d); // should not change when we still hold the mutex
            d_ptr.storeRelease(nullptr);
            d->release();
        }
        return;
    }
}
 
QReadWriteLock::StateForWaitCondition QReadWriteLock::stateForWaitCondition() const
{
    QReadWriteLockPrivate *d = d_ptr.loadAcquire();
    switch (quintptr(d) & StateMask) {
    case StateLockedForRead: return LockedForRead;
    case StateLockedForWrite: return LockedForWrite;
    }
 
    if (!d)
        return Unlocked;
    const auto lock = qt_scoped_lock(d->mutex);
    if (d->writerCount > 1)
        return RecursivelyLocked;
    else if (d->writerCount == 1)
        return LockedForWrite;
    return LockedForRead;
 
}
 
bool QReadWriteLockPrivate::lockForRead(std::unique_lock<QtPrivate::mutex> &lock, int timeout)
{
    Q_ASSERT(!mutex.try_lock()); // mutex must be locked when entering this function
 
    QElapsedTimer t;
    if (timeout > 0)
        t.start();
 
    while (waitingWriters || writerCount) {
        if (timeout == 0)
            return false;
        if (timeout > 0) {
            auto elapsed = t.elapsed();
            if (elapsed > timeout)
                return false;
            waitingReaders++;
            readerCond.wait_for(lock, ms{timeout - elapsed});
        } else {
            waitingReaders++;
            readerCond.wait(lock);
        }
        waitingReaders--;
    }
    readerCount++;
    Q_ASSERT(writerCount == 0);
    return true;
}
 
bool QReadWriteLockPrivate::lockForWrite(std::unique_lock<QtPrivate::mutex> &lock, int timeout)
{
    Q_ASSERT(!mutex.try_lock()); // mutex must be locked when entering this function
 
    QElapsedTimer t;
    if (timeout > 0)
        t.start();
 
    while (readerCount || writerCount) {
        if (timeout == 0)
            return false;
        if (timeout > 0) {
            auto elapsed = t.elapsed();
            if (elapsed > timeout) {
                if (waitingReaders && !waitingWriters && !writerCount) {
                    // We timed out and now there is no more writers or waiting writers, but some
                    // readers were queued (probably because of us). Wake the waiting readers.
                    readerCond.notify_all();
                }
                return false;
            }
            waitingWriters++;
            writerCond.wait_for(lock, ms{timeout - elapsed});
        } else {
            waitingWriters++;
            writerCond.wait(lock);
        }
        waitingWriters--;
    }
 
    Q_ASSERT(writerCount == 0);
    Q_ASSERT(readerCount == 0);
    writerCount = 1;
    return true;
}
 
void QReadWriteLockPrivate::unlock()
{
    Q_ASSERT(!mutex.try_lock()); // mutex must be locked when entering this function
    if (waitingWriters)
        writerCond.notify_one();
    else if (waitingReaders)
        readerCond.notify_all();
}
 
static auto handleEquals(Qt::HANDLE handle)
{
    return [handle](QReadWriteLockPrivate::Reader reader) { return reader.handle == handle; };
}
 
bool QReadWriteLockPrivate::recursiveLockForRead(int timeout)
{
    Q_ASSERT(recursive);
    auto lock = qt_unique_lock(mutex);
 
    Qt::HANDLE self = QThread::currentThreadId();
 
    auto it = std::find_if(currentReaders.begin(), currentReaders.end(),
                           handleEquals(self));
    if (it != currentReaders.end()) {
        ++it->recursionLevel;
        return true;
    }
 
    if (!lockForRead(lock, timeout))
        return false;
 
    Reader r = {self, 1};
    currentReaders.append(std::move(r));
    return true;
}
 
bool QReadWriteLockPrivate::recursiveLockForWrite(int timeout)
{
    Q_ASSERT(recursive);
    auto lock = qt_unique_lock(mutex);
 
    Qt::HANDLE self = QThread::currentThreadId();
    if (currentWriter == self) {
        writerCount++;
        return true;
    }
 
    if (!lockForWrite(lock, timeout))
        return false;
 
    currentWriter = self;
    return true;
}
 
void QReadWriteLockPrivate::recursiveUnlock()
{
    Q_ASSERT(recursive);
    auto lock = qt_unique_lock(mutex);
 
    Qt::HANDLE self = QThread::currentThreadId();
    if (self == currentWriter) {
        if (--writerCount > 0)
            return;
        currentWriter = nullptr;
    } else {
        auto it = std::find_if(currentReaders.begin(), currentReaders.end(),
                               handleEquals(self));
        if (it == currentReaders.end()) {
            qWarning("QReadWriteLock::unlock: unlocking from a thread that did not lock");
            return;
        } else {
            if (--it->recursionLevel <= 0) {
                currentReaders.erase(it);
                readerCount--;
            }
            if (readerCount)
                return;
        }
    }
 
    unlock();
}
 
// The freelist management
namespace {
struct FreeListConstants : QFreeListDefaultConstants {
    enum { BlockCount = 4, MaxIndex=0xffff };
    static const int Sizes[BlockCount];
};
const int FreeListConstants::Sizes[FreeListConstants::BlockCount] = {
    16,
    128,
    1024,
    FreeListConstants::MaxIndex - (16 + 128 + 1024)
};
 
typedef QFreeList<QReadWriteLockPrivate, FreeListConstants> FreeList;
Q_GLOBAL_STATIC(FreeList, freelist);
}
 
QReadWriteLockPrivate *QReadWriteLockPrivate::allocate()
{
    int i = freelist->next();
    QReadWriteLockPrivate *d = &(*freelist)[i];
    d->id = i;
    Q_ASSERT(!d->recursive);
    Q_ASSERT(!d->waitingReaders && !d->waitingWriters && !d->readerCount && !d->writerCount);
    return d;
}
 
void QReadWriteLockPrivate::release()
{
    Q_ASSERT(!recursive);
    Q_ASSERT(!waitingReaders && !waitingWriters && !readerCount && !writerCount);
    freelist->release(id);
}
 
QT_END_NAMESPACE