39
\$\begingroup\$

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 <condition_variable>

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 < xtd::fast_recursive_mutex >;
            using scoped_lock = std::lock_guard < xtd::fast_recursive_mutex >;

            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 do_exclusive_trylock(unique_lock& lk);
            void do_lock_shared(unique_lock& lk);
            bool do_try_lock_shared(unique_lock& lk);
            void do_unlock_shared(scoped_lock& lk);

            void take_exclusive_lock();
            bool someone_has_exclusive_lock() const;
            bool no_one_has_any_lock() const;
            unsigned number_of_readers() const;
            bool maximal_number_of_readers_reached() const;
            void clear_lock_status();
            void increment_readers();
            void decrement_readers();

            static const unsigned m_write_entered = 1U << (sizeof(unsigned)*CHAR_BIT - 1);
            static const unsigned m_num_readers = ~m_write_entered;
        };
    }

    /// <summary> A shared_mutex implemented to C++17 STL specification.
    /// 
    /// This is a Readers-Writer mutex with writer priority. Optional native_handle_type and
    /// native_handle members are not implemented.
    /// 
    /// For detailed documentation, see: http://en.cppreference.com/w/cpp/thread/shared_mutex. </summary>
    class shared_mutex : public detail::shared_mutex_base {
    public:
        shared_mutex() = default;
        shared_mutex(const shared_mutex&) = delete;
        ~shared_mutex() = default;

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

        /// <summary> Obtains an exclusive lock of this mutex. </summary>
        void lock();

        /// <summary> Attempts to exclusively lock this mutex. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock();

        /// <summary> Unlocks the exclusive lock on this mutex. </summary>
        void unlock();

        /// <summary> Obtains a shared lock on this mutex. Other threads may also hold a shared lock simultaneously. </summary>
        void lock_shared();

        /// <summary> Attempts to obtain a shared lock for this mutex. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock_shared();

        /// <summary> Unlocks the shared lock on this mutex. </summary>
        void unlock_shared();
    };

    /// <summary> This is a non-standard class which is essentially the same as `shared_mutex` but
    /// it allows a thread to recursively obtain write locks as long as the unlock count matches
    /// the lock-count. </summary>
    class recursive_shared_mutex : public detail::shared_mutex_base {
    public:
        recursive_shared_mutex() = default;
        recursive_shared_mutex(const recursive_shared_mutex&) = delete;
        ~recursive_shared_mutex() = default;

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

        /// <summary> Obtains an exclusive lock of this mutex. For recursive calls will always obtain the
        /// lock. </summary>
        void lock();

        /// <summary> Attempts to exclusively lock this mutex. For recursive calls will always obtain the
        /// lock. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock();

        /// <summary> Unlocks the exclusive lock on this mutex. </summary>
        void unlock();

        /// <summary> Obtains a shared lock on this mutex. Other threads may also hold a shared lock simultaneously. </summary>
        void lock_shared();

        /// <summary> Attempts to obtain a shared lock for this mutex. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock_shared();

        /// <summary> Unlocks the shared lock on this mutex. </summary>
        void unlock_shared();

        /// <summary> Number recursive write locks. </summary>
        /// <returns> The total number of write locks. </returns>
        int num_write_locks();

        /// <summary> Query if this object is exclusively locked by me. </summary>
        /// <returns> true if locked by me, false if not. </returns>
        bool is_locked_by_me();

    private:
        std::thread::id m_write_thread;
        int m_write_recurses = 0;
    };
}

shared_mutex.cpp

#include "pch/pch.hpp"
#include "xtd/shared_mutex.hpp"

#include <thread>

namespace xtd {

    // ------------------------------------------------------------------------
    // class: shared_mutex_base
    // ------------------------------------------------------------------------
    namespace detail {

        void shared_mutex_base::do_exclusive_lock(unique_lock &lk){
            while (someone_has_exclusive_lock()) {
                m_exclusive_release.wait(lk);
            }

            take_exclusive_lock(); // We hold the mutex, there is no race here.

            while (number_of_readers() > 0) {
                m_shared_release.wait(lk);
            }
        }

        bool shared_mutex_base::do_exclusive_trylock(unique_lock &lk){
            if (lk.owns_lock() && no_one_has_any_lock()) {
                take_exclusive_lock();
                return true;
            }
            return false;
        }

        void shared_mutex_base::do_lock_shared(unique_lock& lk) {
            while (someone_has_exclusive_lock() || maximal_number_of_readers_reached()) {
                m_exclusive_release.wait(lk);
            }
            increment_readers();
        }

        bool shared_mutex_base::do_try_lock_shared(unique_lock& lk) {
            if (lk.owns_lock() && !someone_has_exclusive_lock() &&
                !maximal_number_of_readers_reached()) {
                increment_readers();
                return true;
            }
            return false;
        }

        void shared_mutex_base::do_unlock_shared(scoped_lock& lk) {
            decrement_readers();

            if (someone_has_exclusive_lock()) { // Some one is waiting for us to unlock...
                if (number_of_readers() == 0) {
                    // We were the last one they were waiting for, release one thread waiting
                    // for
                    // all shared locks to clear.
                    m_shared_release.notify_one();
                }
            }
            else {
                // Nobody is waiting for shared locks to clear, if we were at the max
                // capacity,
                // release one thread waiting to obtain a shared lock in lock_shared().
                if (number_of_readers() == m_num_readers - 1)
                    m_exclusive_release.notify_one();
            }
        }

        void shared_mutex_base::take_exclusive_lock() { m_state |= m_write_entered; }

        bool shared_mutex_base::someone_has_exclusive_lock() const {
            return (m_state & m_write_entered) != 0;
        }

        bool shared_mutex_base::no_one_has_any_lock() const { return m_state != 0; }

        unsigned shared_mutex_base::number_of_readers() const {
            return m_state & m_num_readers;
        }

        bool shared_mutex_base::maximal_number_of_readers_reached() const {
            return number_of_readers() == m_num_readers;
        }

        void shared_mutex_base::clear_lock_status() { m_state = 0; }

        void shared_mutex_base::increment_readers() {
            unsigned num_readers = number_of_readers() + 1;
            m_state &= ~m_num_readers;
            m_state |= num_readers;
        }

        void shared_mutex_base::decrement_readers() {
            unsigned num_readers = number_of_readers() - 1;
            m_state &= ~m_num_readers;
            m_state |= num_readers;
        }
    }

    // ------------------------------------------------------------------------
    // class: shared_mutex
    // ------------------------------------------------------------------------
    static_assert(std::is_standard_layout<shared_mutex>::value,
                  "Shared mutex must be standard layout");

    void shared_mutex::lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        do_exclusive_lock(lk);
    }

    bool shared_mutex::try_lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        return do_exclusive_trylock(lk);
    }

    void shared_mutex::unlock() {
        {
            std::lock_guard<xtd::fast_recursive_mutex> lg(m_mutex);
            // We released an exclusive lock, no one else has a lock.
            clear_lock_status();
        }
        m_exclusive_release.notify_all();
    }

    void shared_mutex::lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        do_lock_shared(lk);
    }

    bool shared_mutex::try_lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        return do_try_lock_shared(lk);
    }

    void shared_mutex::unlock_shared() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        do_unlock_shared(_);
    }

    // ------------------------------------------------------------------------
    // class: recursive_shared_mutex
    // ------------------------------------------------------------------------
    void recursive_shared_mutex::lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        if (m_write_recurses == 0) {
            do_exclusive_lock(lk);
        }
        else {
            if (m_write_thread == std::this_thread::get_id()) {
                if (m_write_recurses ==
                    std::numeric_limits<decltype(m_write_recurses)>::max()) {
                    throw std::system_error(
                        EOVERFLOW, std::system_category(),
                        "Too many recursions in recursive_shared_mutex!");
                }
            }
            else {
                // Different thread trying to get a lock.
                do_exclusive_lock(lk);
                assert(m_write_recurses == 0);
            }
        }
        m_write_recurses++;
        m_write_thread = std::this_thread::get_id();
    }

    bool recursive_shared_mutex::try_lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        if ((lk.owns_lock() && m_write_recurses > 0 && m_write_thread == std::this_thread::get_id()) ||
            do_exclusive_trylock(lk)) {
            m_write_recurses++;
            m_write_thread = std::this_thread::get_id();
            return true;
        }
        return false;
    }

    void recursive_shared_mutex::unlock() {
        bool notify_them = false;
        {
            std::lock_guard<xtd::fast_recursive_mutex> lg(m_mutex);
            if (m_write_recurses == 0) {
                throw std::system_error(ENOLCK, std::system_category(),
                                        "Unlocking a unlocked mutex!");
            }
            m_write_recurses--;
            if (m_write_recurses == 0) {
                // We released an exclusive lock, no one else has a lock.
                clear_lock_status();
                notify_them = true;
            }
        }
        if (notify_them) {
            m_exclusive_release.notify_all();
        }
    }

    void recursive_shared_mutex::lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        do_lock_shared(lk);
    }

    bool recursive_shared_mutex::try_lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        return do_try_lock_shared(lk);
    }

    void recursive_shared_mutex::unlock_shared() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        return do_unlock_shared(_);
    }

    int recursive_shared_mutex::num_write_locks() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        return m_write_recurses;
    }

    bool recursive_shared_mutex::is_locked_by_me() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        return m_write_recurses > 0 && m_write_thread == std::this_thread::get_id();
    }
}

The implementation is based on the reference implementation in this working paper.

| improve this question | | | | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Any reason for avoiding the boost library's implementation of this? \$\endgroup\$ – D. Jurcau Jun 10 '16 at 5:59
  • 1
    \$\begingroup\$ For various reasons outside of my control, boost is not available for the project. \$\endgroup\$ – Emily L. Jun 11 '16 at 7:03
  • \$\begingroup\$ On a side note sizeof(unsigned)*CHAR_BIT - 1 should be equivalent to std::numeric_limits<int>::digits if I'm not mistaken. \$\endgroup\$ – Morwenn Dec 29 '16 at 18:06
16
+100
\$\begingroup\$

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<xtd::fast_recursive_mutex> _(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?

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ I'm a bit confused about what impact having reached max readers before the first exclusive lock does in your issue example. Say the readers are overflowing and we get an exclusive lock request, new read requests are queued up on m_exclusive_release and readers monotonically go to 0 and exclusive lock is obtained. So this doesn't really affect your example going forward. \$\endgroup\$ – Emily L. Dec 29 '16 at 4:15
  • \$\begingroup\$ That said, I agree with you it is random if the exclusive or a shared waiter goes first into the exclusive region. If there are an infinite number of threads waiting for a shared lock then the time until the exclusive lock thread gets a time slice from the OS may be unbounded. However I expect a reasonable OS to put the notified threads in a queue to run "soon" (I recall something about threads blocking on IO operations (and signals) get top priority in windows and linux but don't quote me on that). So I would expect it to be delayed by at most num waiting readers. But yeah that's still bad. \$\endgroup\$ – Emily L. Dec 29 '16 at 4:31
  • 2
    \$\begingroup\$ About pushing shared locking into a base class yes and no. It would have the correct behaviour but the current design is also bad in the sense that they should not share a base class at all. Rather composition should be used for reducing code duplication as inheritance implies that they should be Liskov substitutable which is kind of wrong as they have different semantics on exclusive locking. At the time I made this I wanted both classes to completely specify their interfaces to make it easy on my colleagues trying to use them, so they don't have to keep looking into superclass definitions. \$\endgroup\$ – Emily L. Dec 29 '16 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.