boost::shared_mutex
or std::shared_mutex
(C++17) can be used for single writer, multiple reader access. As an educational exercise, I put together a simple implementation that uses spinlocking and has other limitations (eg. fairness policy), but is obviously not intended to be used in real applications.
The idea is that the mutex keeps a reference count that is zero if no thread holds the lock. If > 0, the value represents the number of readers that have access. If -1, a single writer has access.
Is this a correct implementation (in particular with the used, minimal, memory orderings) that is free of data races ?
#include <atomic>
class my_shared_mutex {
std::atomic<int> refcount{0};
public:
void lock() // write lock
{
int val;
do {
val = 0; // Can only take a write lock when refcount == 0
} while (!refcount.compare_exchange_weak(val, -1, std::memory_order_acquire));
// can memory_order_relaxed be used if only a single thread takes write locks ?
}
void unlock() // write unlock
{
refcount.store(0, std::memory_order_release);
}
void lock_shared() // read lock
{
int val;
do {
do {
val = refcount.load(std::memory_order_relaxed);
} while (val == -1); // spinning until the write lock is released
} while (!refcount.compare_exchange_weak(val, val+1, std::memory_order_acquire));
}
void unlock_shared() // read unlock
{
// This must be a release operation (see answer)
refcount.fetch_sub(1, std::memory_order_relaxed);
}
};
(CAS = Compare And Swap = C++
compare_exchange_weak
function, which on x86 will typically compile to an x86lock cmpxchg
instruction which can only run when it owns the cache line in Exclusive or Modified MESI state).lock_shared
looks good: spinning read-only attempting a CAS only when it looks possible is better for performance than spinning on CAS or atomic increment. You already needed to do a read-only check to avoid changing-1
to0
and unlocking a write-lock.On x86, put a
_mm_pause()
in the retry path of the spin loop to avoid memory-order mis-speculation pipeline nukes when exiting the read-only spin loop, and steal fewer resources from the other hyperthread while spinning. (Use awhile()
loop, notdo{}while()
, so the pause only runs after failing once.pause
on Skylake and later waits about 100 cycles so avoid it in the fast-path.)I think
unlock_shared
should be usingmo_release
, notmo_relaxed
, since it needs to order the loads from the shared data structure to make sure a writer doesn't start writing before the loads from the reader critical section happen. (LoadStore reordering is a thing on weakly-ordered architectures, even though x86 only does StoreLoad reordering.) A Release operation will order preceding loads and keep them inside the critical section.No, you still need to keep the writes inside the critical section, so the CAS still needs to Synchronize With (in C++ terminology) release-stores from
unlock_shared
.https://preshing.com/20120913/acquire-and-release-semantics/ has a nice image that shows the 1-way barrier effect of a release-store or acquire-load.