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>
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "qplatformdefs.h"
#include "qreadwritelock.h"
 
#include "qthread.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.
 */
 
using namespace QReadWriteLockStates;
namespace {
 
using steady_clock = std::chrono::steady_clock;
 
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; }
}
 
static bool contendedTryLockForRead(QAtomicPointer<QReadWriteLockPrivate> &d_ptr,
                                    QDeadlineTimer timeout, QReadWriteLockPrivate *d);
static bool contendedTryLockForWrite(QAtomicPointer<QReadWriteLockPrivate> &d_ptr,
                                     QDeadlineTimer timeout, QReadWriteLockPrivate *d);
 
QReadWriteLockPrivate *QReadWriteLock::initRecursive()
{
    auto d = new QReadWriteLockPrivate(true);
    Q_ASSERT_X(!(quintptr(d) & StateMask), "QReadWriteLock::QReadWriteLock", "bad d_ptr alignment");
    return d;
}
 
void QReadWriteLock::destroyRecursive(QReadWriteLockPrivate *d)
{
    if (isUncontendedLocked(d)) {
        qWarning("QReadWriteLock: destroying locked QReadWriteLock");
        return;
    }
    delete d;
}
 
bool QReadWriteLock::tryLockForRead(QDeadlineTimer timeout)
{
    // Fast case: non contended:
    QReadWriteLockPrivate *d = d_ptr.loadRelaxed();
    if (d == nullptr && d_ptr.testAndSetAcquire(nullptr, dummyLockedForRead, d))
        return true;
    return contendedTryLockForRead(d_ptr, timeout, d);
}
 
Q_NEVER_INLINE static bool contendedTryLockForRead(QAtomicPointer<QReadWriteLockPrivate> &d_ptr,
                                                   QDeadlineTimer timeout, QReadWriteLockPrivate *d)
{
    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.hasExpired())
                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);
    }
}
 
bool QReadWriteLock::tryLockForWrite(QDeadlineTimer timeout)
{
    // Fast case: non contended:
    QReadWriteLockPrivate *d = d_ptr.loadRelaxed();
    if (d == nullptr && d_ptr.testAndSetAcquire(nullptr, dummyLockedForWrite, d))
        return true;
    return contendedTryLockForWrite(d_ptr, timeout, d);
}
 
Q_NEVER_INLINE static bool contendedTryLockForWrite(QAtomicPointer<QReadWriteLockPrivate> &d_ptr,
                                                    QDeadlineTimer timeout, QReadWriteLockPrivate *d)
{
    while (true) {
        if (d == nullptr) {
            if (!d_ptr.testAndSetAcquire(d, dummyLockedForWrite, d))
                continue;
            return true;
        }
 
        if (isUncontendedLocked(d)) {
            if (timeout.hasExpired())
                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;
    }
}
 
bool QReadWriteLockPrivate::lockForRead(std::unique_lock<std::mutex> &lock, QDeadlineTimer timeout)
{
    Q_ASSERT(!mutex.try_lock()); // mutex must be locked when entering this function
 
    while (waitingWriters || writerCount) {
        if (timeout.hasExpired())
            return false;
        if (!timeout.isForever()) {
            waitingReaders++;
            readerCond.wait_until(lock, timeout.deadline<steady_clock>());
        } else {
            waitingReaders++;
            readerCond.wait(lock);
        }
        waitingReaders--;
    }
    readerCount++;
    Q_ASSERT(writerCount == 0);
    return true;
}
 
bool QReadWriteLockPrivate::lockForWrite(std::unique_lock<std::mutex> &lock, QDeadlineTimer timeout)
{
    Q_ASSERT(!mutex.try_lock()); // mutex must be locked when entering this function
 
    while (readerCount || writerCount) {
        if (timeout.hasExpired()) {
            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;
        }
        if (!timeout.isForever()) {
            waitingWriters++;
            writerCond.wait_until(lock, timeout.deadline<steady_clock>());
        } 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(QDeadlineTimer 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(QDeadlineTimer 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 QReadWriteLockFreeListConstants : QFreeListDefaultConstants
{
    enum { BlockCount = 4, MaxIndex=0xffff };
    static const int Sizes[BlockCount];
};
Q_CONSTINIT const int
        QReadWriteLockFreeListConstants::Sizes[QReadWriteLockFreeListConstants::BlockCount] = {
            16, 128, 1024, QReadWriteLockFreeListConstants::MaxIndex - (16 + 128 + 1024)
        };
 
typedef QFreeList<QReadWriteLockPrivate, QReadWriteLockFreeListConstants> QReadWriteLockFreeList;
Q_GLOBAL_STATIC(QReadWriteLockFreeList, qrwl_freelist);
}
 
QReadWriteLockPrivate *QReadWriteLockPrivate::allocate()
{
    int i = qrwl_freelist->next();
    QReadWriteLockPrivate *d = &(*qrwl_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);
    qrwl_freelist->release(id);
}
 
QT_END_NAMESPACE