4
\$\begingroup\$

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.

Features

  • Recursive 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);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I recommend having a look at this one as well. \$\endgroup\$ – Incomputable Apr 25 '17 at 15:19
  • \$\begingroup\$ The github link is out of date. Can you update it? Thanks. \$\endgroup\$ – Brannon May 30 '18 at 23:09
  • \$\begingroup\$ Sorry, the repo doesn't exist anymore. \$\endgroup\$ – Viatorus Jun 3 '18 at 5:35
  • \$\begingroup\$ I had asked about the repo to see if you had a separate license there or if you wanted this to fall under CodeReview's Creative Commons license. \$\endgroup\$ – Brannon Jun 5 '18 at 1:46
  • \$\begingroup\$ CRs Creative Commons Licence. \$\endgroup\$ – Viatorus Jun 6 '18 at 6:10
2
\$\begingroup\$

One thought I had on this: wouldn't it play nicer if there was a thread yield outside the mutex in the tight for-loops? Or perhaps we scale up to that?

I've also been using this try_lock addition;

bool RecursiveSharedMutex::try_lock() {
    auto threadId = std::this_thread::get_id();
    std::thread::id emptyThreadId;
    std::lock_guard<std::mutex> lock(_mtx);

    if (_writerThreadId == threadId) {
        ++_writersOwnership;
        return true;
    }

    if (_readersOwnership.size() == 0 && _writerThreadId.compare_exchange_weak(emptyThreadId, threadId))
        return true;

    return false;
}
\$\endgroup\$

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.