Revision control
Copy as Markdown
// 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
// Qt-Security score:significant reason:default
#include "qplatformdefs.h"
#include "qreadwritelock.h"
#include "qthread.h"
#include "qreadwritelock_p.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.
*/
static auto dummyLockedForRead()
{
return reinterpret_cast<QReadWriteLockPrivate *>(QReadWriteLockPrivate::StateLockedForRead);
}
static auto dummyLockedForWrite()
{
return reinterpret_cast<QReadWriteLockPrivate *>(QReadWriteLockPrivate::StateLockedForWrite);
}
static inline bool isUncontendedLocked(const QReadWriteLockPrivate *d)
{
return quintptr(d) & QReadWriteLockPrivate::StateMask;
}
/*! \class QReadWriteLock
\inmodule QtCore
\brief The QReadWriteLock class provides read-write locking.
\threadsafe
\ingroup thread
A read-write lock is a synchronization tool for protecting
resources that can be accessed for reading and writing. This type
of lock is useful if you want to allow multiple threads to have
simultaneous read-only access, but as soon as one thread wants to
write to the resource, all other threads must be blocked until
the writing is complete.
In many cases, QReadWriteLock is a direct competitor to QMutex.
QReadWriteLock is a good choice if there are many concurrent
reads and writing occurs infrequently.
Example:
\snippet code/src_corelib_thread_qreadwritelock.cpp lock
\snippet code/src_corelib_thread_qreadwritelock.cpp 0
To ensure that writers aren't blocked forever by readers, readers
attempting to obtain a lock will not succeed if there is a blocked
writer waiting for access, even if the lock is currently only
accessed by other readers. Also, if the lock is accessed by a
writer and another writer comes in, that writer will have
priority over any readers that might also be waiting.
Like QMutex, a QReadWriteLock can be recursively locked by the
same thread when constructed with \l{QReadWriteLock::Recursive} as
\l{QReadWriteLock::RecursionMode}. In such cases,
unlock() must be called the same number of times lockForWrite() or
lockForRead() was called. Note that the lock type cannot be
changed when trying to lock recursively, i.e. it is not possible
to lock for reading in a thread that already has locked for
writing (and vice versa).
\sa QReadLocker, QWriteLocker, QMutex, QSemaphore
*/
/*!
\enum QReadWriteLock::RecursionMode
\since 4.4
\value Recursive In this mode, a thread can lock the same
QReadWriteLock multiple times. The QReadWriteLock won't be unlocked
until a corresponding number of unlock() calls have been made.
\value NonRecursive In this mode, a thread may only lock a
QReadWriteLock once.
\sa QReadWriteLock()
*/
/*!
\fn QReadWriteLock::QReadWriteLock(RecursionMode recursionMode)
\since 4.4
Constructs a QReadWriteLock object in the given \a recursionMode.
The default recursion mode is NonRecursive.
\sa lockForRead(), lockForWrite(), RecursionMode
*/
void *QReadWriteLock::initRecursiveHelper()
{
auto d = new QReadWriteLockPrivate(true);
Q_ASSERT_X(!(quintptr(d) & StateMask), "QReadWriteLock::QReadWriteLock", "bad d_ptr alignment");
return d;
}
/*!
\fn QReadWriteLock::~QReadWriteLock()
Destroys the QReadWriteLock object.
\warning Destroying a read-write lock that is in use may result
in undefined behavior.
*/
void QReadWriteLock::destroyRecursiveHelper(void *dd) noexcept
{
auto d = static_cast<QReadWriteLockPrivate *>(dd);
if (isUncontendedLocked(d)) {
qWarning("QReadWriteLock: destroying locked QReadWriteLock");
return;
}
delete d;
}
/*!
\fn QReadWriteLock::lockForRead()
Locks the lock for reading. This function will block the current
thread if another thread has locked for writing.
It is not possible to lock for read if the thread already has
locked for write.
\sa unlock(), lockForWrite(), tryLockForRead()
*/
/*!
\fn bool QReadWriteLock::tryLockForRead(int timeout)
Attempts to lock for reading. This function returns \c true if the
lock was obtained; otherwise it returns \c false. If another thread
has locked for writing, this function will wait for at most \a
timeout milliseconds for the lock to become available.
Note: Passing a negative number as the \a timeout is equivalent to
calling lockForRead(), i.e. this function will wait forever until
lock can be locked for reading when \a timeout is negative.
If the lock was obtained, the lock must be unlocked with unlock()
before another thread can successfully lock it for writing.
It is not possible to lock for read if the thread already has
locked for write.
\sa unlock(), lockForRead()
*/
static Q_ALWAYS_INLINE bool fastTryLock(QAtomicPointer<QReadWriteLockPrivate> &d_ptr,
QReadWriteLockPrivate *dummyValue,
QReadWriteLockPrivate *&d)
{
// Succeed fast if not contended
return d == nullptr && d_ptr.testAndSetAcquire(nullptr, dummyValue, d);
}
/*!
\fn bool QReadWriteLock::tryLockForRead(QDeadlineTimer timeout)
\overload
\since 6.6
Attempts to lock for reading. This function returns \c true if the lock was
obtained; otherwise it returns \c false. If another thread has locked for
writing, this function will wait until \a timeout expires for the lock to
become available.
If the lock was obtained, the lock must be unlocked with unlock()
before another thread can successfully lock it for writing.
It is not possible to lock for read if the thread already has
locked for write.
\sa unlock(), lockForRead()
*/
Q_NEVER_INLINE bool
QBasicReadWriteLock::contendedTryLockForRead(QDeadlineTimer timeout, void *dd)
{
auto d = static_cast<QReadWriteLockPrivate *>(dd);
while (true) {
qYieldCpu();
if (d == nullptr) {
if (fastTryLock(d_ptr, dummyLockedForRead(), d))
return true;
continue;
}
if ((quintptr(d) & StateMask) == StateLockedForRead) {
// locked for read, increase the counter
const auto val = reinterpret_cast<QReadWriteLockPrivate *>(quintptr(d) + Counter);
Q_ASSERT_X(quintptr(val) > Counter, "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; acquire its contents
d = d_ptr.loadAcquire();
if (!d || isUncontendedLocked(d))
continue;
if (d->recursive)
return d->recursiveLockForRead(timeout);
auto lock = qt_unique_lock(d->mutex);
if (QReadWriteLockPrivate *dd = d_ptr.loadAcquire(); d != dd) {
// 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 = dd;
continue;
}
return d->lockForRead(lock, timeout);
}
}
/*!
\fn QReadWriteLock::lockForWrite()
Locks the lock for writing. This function will block the current
thread if another thread (including the current) has locked for
reading or writing (unless the lock has been created using the
\l{QReadWriteLock::Recursive} mode).
It is not possible to lock for write if the thread already has
locked for read.
\sa unlock(), lockForRead(), tryLockForWrite()
*/
/*!
\fn QReadWriteLock::tryLockForWrite(int timeout)
Attempts to lock for writing. This function returns \c true if the
lock was obtained; otherwise it returns \c false. If another thread
has locked for reading or writing, this function will wait for at
most \a timeout milliseconds for the lock to become available.
Note: Passing a negative number as the \a timeout is equivalent to
calling lockForWrite(), i.e. this function will wait forever until
lock can be locked for writing when \a timeout is negative.
If the lock was obtained, the lock must be unlocked with unlock()
before another thread can successfully lock it.
It is not possible to lock for write if the thread already has
locked for read.
\sa unlock(), lockForWrite()
*/
/*!
\fn bool QReadWriteLock::tryLockForWrite(QDeadlineTimer timeout)
\overload
\since 6.6
Attempts to lock for writing. This function returns \c true if the lock was
obtained; otherwise it returns \c false. If another thread has locked for
reading or writing, this function will wait until \a timeout expires for
the lock to become available.
If the lock was obtained, the lock must be unlocked with unlock()
before another thread can successfully lock it.
It is not possible to lock for write if the thread already has
locked for read.
\sa unlock(), lockForWrite()
*/
Q_NEVER_INLINE bool
QBasicReadWriteLock::contendedTryLockForWrite(QDeadlineTimer timeout, void *dd)
{
auto d = static_cast<QReadWriteLockPrivate *>(dd);
while (true) {
qYieldCpu();
if (d == nullptr) {
if (fastTryLock(d_ptr, dummyLockedForWrite(), d))
return true;
continue;
}
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; acquire its contents
d = d_ptr.loadAcquire();
if (!d || isUncontendedLocked(d))
continue;
if (d->recursive)
return d->recursiveLockForWrite(timeout);
auto lock = qt_unique_lock(d->mutex);
if (QReadWriteLockPrivate *dd = d_ptr.loadAcquire(); d != dd) {
// 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 = dd;
continue;
}
return d->lockForWrite(lock, timeout);
}
}
/*!
\internal
\since 6.12
Returns a flag mask describing this QReadWriteLock. This function is
necessary for user code built with Thread Sanitizer, because it can't tell
from inline what type of lock a contended QReadWriteLock is locked for.
This function is always present in QtCore, whether it was compiled for TSan
or not.
*/
quintptr QBasicReadWriteLock::describeLockInternal(void *dd) noexcept
{
return QReadWriteLockPrivate::describeState(dd);
}
/*!
\fn void QReadWriteLock::unlock()
Unlocks the lock.
Attempting to unlock a lock that is not locked is an error, and will result
in program termination.
\sa lockForRead(), lockForWrite(), tryLockForRead(), tryLockForWrite()
*/
void QBasicReadWriteLock::contendedUnlock(void *dd)
{
auto d = static_cast<QReadWriteLockPrivate *>(dd);
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) > Counter); //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)
{
using std::chrono::steady_clock;
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)
{
using std::chrono::steady_clock;
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);
}
/*!
\class QReadLocker
\inmodule QtCore
\brief The QReadLocker class is a convenience class that
simplifies locking and unlocking read-write locks for read access.
\threadsafe
\ingroup thread
The purpose of QReadLocker (and QWriteLocker) is to simplify
QReadWriteLock locking and unlocking. Locking and unlocking
statements or in exception handling code is error-prone and
difficult to debug. QReadLocker can be used in such situations
to ensure that the state of the lock is always well-defined.
Here's an example that uses QReadLocker to lock and unlock a
read-write lock for reading:
\snippet code/src_corelib_thread_qreadwritelock.cpp lock
\snippet code/src_corelib_thread_qreadwritelock.cpp 1
It is equivalent to the following code:
\snippet code/src_corelib_thread_qreadwritelock.cpp lock
\snippet code/src_corelib_thread_qreadwritelock.cpp 2
The QMutexLocker documentation shows examples where the use of a
locker object greatly simplifies programming.
\sa QWriteLocker, QReadWriteLock
*/
/*!
\fn QReadLocker::QReadLocker(QReadWriteLock *lock)
Constructs a QReadLocker and locks \a lock for reading. The lock
will be unlocked when the QReadLocker is destroyed. If \c lock is
zero, QReadLocker does nothing.
\sa QReadWriteLock::lockForRead()
*/
/*!
\fn QReadLocker::~QReadLocker()
Destroys the QReadLocker and unlocks the lock that was passed to
the constructor.
\sa QReadWriteLock::unlock()
*/
/*!
\fn void QReadLocker::unlock()
Unlocks the lock associated with this locker.
\sa QReadWriteLock::unlock()
*/
/*!
\fn void QReadLocker::relock()
Relocks an unlocked lock.
\sa unlock()
*/
/*!
\fn QReadWriteLock *QReadLocker::readWriteLock() const
Returns a pointer to the read-write lock that was passed
to the constructor.
*/
/*!
\class QWriteLocker
\inmodule QtCore
\brief The QWriteLocker class is a convenience class that
simplifies locking and unlocking read-write locks for write access.
\threadsafe
\ingroup thread
The purpose of QWriteLocker (and QReadLocker) is to simplify
QReadWriteLock locking and unlocking. Locking and unlocking
statements or in exception handling code is error-prone and
difficult to debug. QWriteLocker can be used in such situations
to ensure that the state of the lock is always well-defined.
Here's an example that uses QWriteLocker to lock and unlock a
read-write lock for writing:
\snippet code/src_corelib_thread_qreadwritelock.cpp lock
\snippet code/src_corelib_thread_qreadwritelock.cpp 3
It is equivalent to the following code:
\snippet code/src_corelib_thread_qreadwritelock.cpp lock
\snippet code/src_corelib_thread_qreadwritelock.cpp 4
The QMutexLocker documentation shows examples where the use of a
locker object greatly simplifies programming.
\sa QReadLocker, QReadWriteLock
*/
/*!
\fn QWriteLocker::QWriteLocker(QReadWriteLock *lock)
Constructs a QWriteLocker and locks \a lock for writing. The lock
will be unlocked when the QWriteLocker is destroyed. If \c lock is
zero, QWriteLocker does nothing.
\sa QReadWriteLock::lockForWrite()
*/
/*!
\fn QWriteLocker::~QWriteLocker()
Destroys the QWriteLocker and unlocks the lock that was passed to
the constructor.
\sa QReadWriteLock::unlock()
*/
/*!
\fn void QWriteLocker::unlock()
Unlocks the lock associated with this locker.
\sa QReadWriteLock::unlock()
*/
/*!
\fn void QWriteLocker::relock()
Relocks an unlocked lock.
\sa unlock()
*/
/*!
\fn QReadWriteLock *QWriteLocker::readWriteLock() const
Returns a pointer to the read-write lock that was passed
to the constructor.
*/
QT_END_NAMESPACE