Recursive shared_mutex implementation

I found myself in need of a Readers-Writer mutex. With C++17 TR2 support not yet available in our compiler, I set out to implement std::shared_mutex so that we have an easy upgrade path to the STL implementation once we get C++17 support, rather than rolling my own API.

I put all classes intended to implement or supplement STL functionality in a namespace xtd short for "eXtended sTD". Reason being that when/if proper support arrives we can just swap xtd for std and be running the STL implementation.

In addition to std::shared_mutex, we also need a Reader-Writer mutex that allows recursive locking for writers. Readers are always recursive any way. This is implemented as xtd::recursive_shared_mutex this class has no equivalent in standard C++, but has the same API as std::shared_mutex with some extensions.

In the code below, I use a custom class called xtd::fast_recursive_mutex, this class is a fully compatible, drop-in-replacement for std::recursive_mutex, but it uses CRITICAL_SECTION on windows for faster locking than std::recursive_mutex (at least on our compiler).

I'm interested in a review of correctness and any gross inefficiencies of the classes.

xtd/shared_mutex.hpp

```
#pragma once
#include "fast_recursive_mutex.hpp"
#include

namespace xtd {

namespace detail {
class shared_mutex_base {
public:
shared_mutex_base() = default;
shared_mutex_base(const shared_mutex_base&) = delete;
~shared_mutex_base() = default;

shared_mutex_base& operator = (const shared_mutex_base&) = delete;

protected:
using unique_lock = std::unique_lock ;
using scoped_lock = std::lock_guard ;

xtd::fast_recursive_mutex m_mutex;
std::condition_variable_any m_exclusive_release;
std::condition_variable_any m_shared_release;
unsigned m_state = 0;

void do_exclusive_lock(unique_lock& lk);
bool

Easy Stuff you already know.

Probably part of your automated scripts to build new files.

#pragma once

But for new comers I would point out the more standard include guards are compatible everywhere.

Don't be lazy

std::lock_guard _(m_mutex);

Though not technically wrong as an identifier (_). How many people do you think know the rules about them that well? Also you use lk nearly everywhere else, why change up the style right at the end?

Opinion based Comments

When you have standard constructor/destructor but you disable copying, then I would group them that way as well. I would put the constructor/destructor together and then the copy operators together:

shared_mutex() = default;
shared_mutex(const shared_mutex&) = delete;
~shared_mutex() = default;

shared_mutex& operator = (const shared_mutex&) = delete;

I would have done this:

shared_mutex() = default;
~shared_mutex() = default;

// Disable copy semantics.
shared_mutex(const shared_mutex&) = delete;
shared_mutex& operator = (const shared_mutex&) = delete;

Don't like your state

You combine two pieces of state into a single variable m_state. Which makes reading the code harder. Optimize for readability or put some more comments around the code here:

It took me a few minutes to work out what you are achieving here. A nice comment would have been nice.

static const unsigned m_write_entered = 1U << (sizeof(unsigned)*CHAR_BIT - 1);
            static const unsigned m_num_readers = ~m_write_entered;
                            //    ^^^^^^^^^^^^^  don't like that name it needs "max" in it.

Basically, you use these constants to help combine the state into m_state where the top bit is used to indicate an exclusive lock and all the other bits are used to count the number of shared locks.

Bug

bool shared_mutex_base::no_one_has_any_lock() const { return m_state != 0; }
                                                                    ^^^^ Should that not be `==`?

Issue

You use m_exclusive_release for threads waiting for an exclusive lock in do_exclusive_lock() and as an overflow list for threads trying to get a shared lock in do_lock_shared(). Depending on your semantics on the priority of exclusive locks this may not work as you intended.

I would expect threads waiting for an exclusive locks to get priority over those waiting for a shared locks; but any waiting thread has an equal opportunity to grab a lock when the current exclusive lock releases.

Thus several, but not necessarily all, threads waiting for shared locks may be able to get locks before the thread needing an exclusive lock gets an opportunity to grab the lock. Thus the exclusive lock may need to wait again.

Scenario:

• We have a lot of threads with shared locks and reached the maximum.

• We add one (or a couple) more shared_locks.

These are queued up on m_exclusive_release.

• We now have a thread that wants an exclusive lock and gets it.

Now waiting on m_shared_release for all the shared locks to be released.

• We now have a thread that wants an exclusive lock (but it is already taken).

So this thread is put on the m_exclusive_release list (with one or more threads waiting for a shared lock).

As the threads with shared locks finish their work they call do_unlock_shared() until there are no more shared locks left. This forces a call to m_shared_release.notify_one(); and the first thread with an exclusive lock (waiting on m_shared_release) is released and runs normally until it releases the lock with a call to unlock() which calls m_exclusive_release.notify_all();. This releases all the threads attempting to get a shared_lock and all the threads attempts to get an exclusive lock. You can not tell which thread will get a lock first so it is random if an exclusive lock is next to get the lock.

Because of this exclusive locks may be starved of resources as they may have to wait for shared locks to be released twice before they get the opportunity to run.

I am pretty sure you will never deadlock or actually prevent an exclusive lock from happening but I don't see this as favorable behavior.

Design

Would the shared locking not work the same on both shared_mutex and recursive_shared_mutex? Could you not push that code into a shared base class?

StackExchange Code Review Q#95993, answer score: 16