I've been looking for an implementation of a recursive shared mutex to handle a very special data tree inside a heavy multi-threaded application.Because boost and the stdlib does not have this special type, I wrote one myself. However, I am not sure if I missed something...You find the full implementation with tests at github. Tested with GCC 5.4.FeaturesRecursive for exclusive ownership with lock and lock_shared.Recursive for sharable ownership with lock_shared.Threads trying to get exclusive ownership have a higher priority then new threads trying to get sharable ownership.Maximum waiting writers, level of ownerships: uint32::max recursive_shared_mutex.hpp/* * Copyright (c) 2017 Toni Neubert, all rights reserved. */#pragma once#include <atomic>#include <mutex>#include <thread>#include <unordered_map>class RecursiveSharedMutex {public:    /**     * @brief Constructs the mutex.     */    RecursiveSharedMutex();    /**     * @brief Locks the mutex for exclusive write access for this thread.     *              Blocks execution as long as write access is not available:     *              * other thread has write access     *              * other threads try to get write access     *              * other threads have read access     *     *              A thread may call lock repeatedly.     *              Ownership will only be released after the thread makes a matching number of calls to unlock.     */    void lock();    /**     * @brief Locks the mutex for sharable read access.     *              Blocks execution as long as read access is not available:     *              * other thread has write access     *              * other threads try to get write access     *     *              A thread may call lock repeatedly.     *              Ownership will only be released after the thread makes a matching number of calls to unlock_shared.     */    void lock_shared();    /**     * @brief Unlocks the mutex for this thread if its level of ownership is 1. Otherwise reduces the level of ownership     *              by 1.     */    void unlock();    /**     * @brief Unlocks the mutex for this thread if its level of ownership is 1. Otherwise reduces the level of ownership     *              by 1.     */    void unlock_shared();private:    /// Protects data access of mutex.    std::mutex _mtx;    /// Number of threads waiting for exclusive write access.    std::atomic<uint32_t> _waitingWriters;    /// Thread id of writer.    std::atomic<std::thread::id> _writerThreadId;    /// Level of ownership of writer thread.    uint32_t _writersOwnership;    /// Level of ownership of reader threads.    std::unordered_map<std::thread::id, uint32_t> _readersOwnership;};recursive_shared_mutex.cpp/* * Copyright (c) 2017 Toni Neubert, all rights reserved. */#include recursive_shared_mutex.hpp#include <cassert>RecursiveSharedMutex::RecursiveSharedMutex() :    _waitingWriters(0),    _writersOwnership(1) {}void RecursiveSharedMutex::lock() {    // Case 1:    // * Thread has no ownership.    // * Zero readers, no writer.    // -> The thread gets exclusive ownership as writer.    // Case 2:    // * Thread has no ownership.    // * Many readers, no writer.    // -> Gets exclusive ownership as writer and waits until last reader is unlocked.    // Case 3:    // * Thread has no ownership.    // * Zero readers, one writer.    // -> Gets exclusive ownership as writer after other writer thread is unlocked.    // Case 4:    // * Thread has no ownership.    // * Zero readers, one writer.    // * Many threads try to get exclusive ownership.    // -> Various attempts until exclusive ownership as writer has been acquired. The acquisition order is arbitrarily.    // Case 5:    // * Thread has exclusive ownership.    // * Zero readers, one writer.    // -> Increases threads level of ownership.    // Case 6:    // * Thread has sharable ownership.    // -> Deadlock.    auto threadId = std::this_thread::get_id();    {        // Increase level of ownership if thread has already exclusive ownership.        std::lock_guard<std::mutex> lock(_mtx);        if (_writerThreadId == threadId) {            ++_writersOwnership;            return;        }    }    // Notify the new waiting writer.    assert(_waitingWriters != 0x7fffffff);    _waitingWriters += 1;    for (;;) {        // Attempt to get exclusive ownership.        std::thread::id emptyThreadId;        if (_writerThreadId.compare_exchange_weak(emptyThreadId, threadId)) {            for (;;) {                // Wait until no readers exist.                std::lock_guard<std::mutex> lock(_mtx);                if (_readersOwnership.size() == 0) {                    // Notify a waiting writer is gone.                    --_waitingWriters;                    return;                }            }        }    }}void RecursiveSharedMutex::lock_shared() {    // Case 1:    // * Thread has/has no ownership.    // * Zero/Many readers, no writer.    // -> The thread gets shared ownership as reader.    // Case 2:    // * Thread has no ownership.    // * Zero readers, one writer.    // -> Waits until writer thread unlocked. The thread gets shared ownership as reader.    // Case 3:    // * Thread has sharable ownership.    // * Many readers, no writer.    // -> Increases threads level of ownership.    // Case 4:    // * Thread has exclusive ownership.    // * Zero readers, one writer.    // -> Increases threads level of ownership.    // Case 5:    // * Thread has no ownership.    // * Zero/Many readers, one/no writer.    // * Many threads try to get exclusive ownership.    // -> Waits until all exclusive ownership requests are handled. The thread gets shared ownership as reader.    auto threadId = std::this_thread::get_id();    {        // Increase level of ownership if thread has already exclusive ownership.        std::lock_guard<std::mutex> lock(_mtx);        // As writer.        if (_writerThreadId == threadId) {            ++_writersOwnership;            return;        }        // As reader.        if (_readersOwnership.count(threadId) != 0) {            ++_readersOwnership[threadId];            return;        }    }    for (;;) {        std::lock_guard<std::mutex> lock(_mtx);        // Wait until no writer is waiting or writing.        if (_waitingWriters.load() != 0 || _writerThreadId != std::thread::id()) {            continue;        }        // Add new reader ownership.        _readersOwnership.insert(std::make_pair(threadId, 1));        return;    }}void RecursiveSharedMutex::unlock() {    // Case 1:    // * Thread has exclusive ownership.    // -> If threads level of ownership is 0, releases exclusive ownership otherwise decrements threads level of    //      ownership.    // Case 2:    // * Thread has no/has sharable ownership.    // -> In debug mode: Assert will terminate program.    // -> In release mode: Undefined behaviour! Case 1 will occur.    assert(std::this_thread::get_id() == _writerThreadId);    std::lock_guard<std::mutex> lock(_mtx);    {        // Decrease writer threads level of ownership if not 1.        if (_writersOwnership != 1) {            --_writersOwnership;            return;        }    }    // Reset threads ownership.    _writerThreadId = std::thread::id();}void RecursiveSharedMutex::unlock_shared() {    // Case 1:    // * Thread has sharable ownership.    // -> If reader threads level of ownership is 0, releases sharable ownership otherwise decrements reader threads    //    level of ownership.    // Case 2:    // * Thread has exclusive ownership.    // -> Decrements threads level of ownership.    // Case 3:    // * Thread has no ownership.    // -> In debug mode: Assert will terminate program.    // -> In release mode: Undefined behaviour!    // Reduce readers recursive depth.    // Remove reader from map if depth == 0.    auto threadId = std::this_thread::get_id();    std::lock_guard<std::mutex> lock(_mtx);    // Decrease writer threads level of ownership if not 1.    if (_writerThreadId == threadId) {        --_writersOwnership;        return;    }    assert(_readersOwnership.count(threadId) == 1);    // Decrease threads level of ownership if not 1.    if (_readersOwnership[threadId] != 1) {        --_readersOwnership[threadId];        return;    }    // Remove readers ownership.    _readersOwnership.erase(threadId);}
Recursive shared mutex
c++;multithreading;thread safety