Utilities for creating a lock hierarchy?

Question

According to the answers found in Threads and simple Dead lock cure and also Herb Sutter the key to avoiding deadlock is by using lock hierarchies.

Are there any good C++ libraries that provide support for this? I can't find any in Boost or Poco.

Ideally it would be a system that allows one to define the hierarchy at compile-time. Perhaps it would look like this:

template<class LowerLevelMutex>
class RankedMutex { ... };

class BottomMutex { ... };

typedef RankedMutex<BottomMutex> L1Mutex;
typedef RankedMutex<L1Mutex> L2Mutex;
typedef RankedMutex<L2Mutex> L3Mutex;
// ...

Answer 1

Yes, lock hierarchies can effectively prevent deadlocks; of course whether you can actually define a hierarchy for your program (especially, in the presence of plugins) is another matter entirely.

The basic blocks are simple:

• Each mutex should have a level (either determined at compile-time or run-time)
• Each thread should only ever acquire mutex in ascending or descending level (decide once)

I hope I can do the idea justice, please consider the example implementation below a sketch; it has never been compiled/tested.

A basic mutex:

template <typename Mutex, size_t Level>
class HierarchicalMutex {
public:
    friend class LevelManager;

    void lock() {
        LevelManager::Lock(*this);
    }

    void unlock() {
        LevelManager::Unlock(*this);
    }

private:
    size_t previous;
    Mutex mutex;
}; // class HierarchicalMutex

template <typename Mutex, size_t Level>
size_t level(HierarchicalMutex<Mutex,Level> const&) { return Level; }

The LevelManager's role is simply to ensure that level transitions happen in correct order.

class LevelManager {
public:
    //
    // Single Mutex locking
    //
    template <typename M>
    static void Lock(M& m) {
        m.previous = LevelUp(level(m));
        m.mutex.lock();
    }

    template <typename M>
    static void Unlock(M& m) {
        m.mutex.unlock();
        LevelDown(level(m), m.previous);
    }

    //
    // Multiple Mutexes Group Locking
    //
    // Note: those should expose a "size_t level(M const&)" function,
    //       and calls to lock/unlock should appropriately call
    //       this manager to raise/lower the current level.
    //
    // Note: mutexes acquired as a group
    //       should be released with the same group.
    //
    template <typename M>
    static void Lock(std::array_ref<M*> mutexes) { // I wish this type existed
        using std::begin; using std::end;

        auto begin = begin(mutexes);
        auto end = end(mutexes);

        end = std::remove_if(begin, end, [](M const* m) { return m == 0; });

        if (begin == end) { return; }

        Sort(begin, end);

        size_t const previous = LevelUp(level(*std::prev(end)));

        for (; begin != end; ++begin) {
            begin->previous = previous;
            begin->mutex.lock();
        }
    }

    template <typename M>
    static void Unlock(std::array_ref<M*> mutexes) {
        using std::begin; using std::end;

        auto begin = begin(mutexes);
        auto end = end(mutexes);

        end = std::remove_if(begin, end, [](M const* m) { return m == 0; });

        if (begin == end) { return; }

        Sort(begin, end);

        std::reverse(begin, end);

        for (auto it = begin; it != end; ++it) { it->mutex.unlock(); }

        LevelDown(level(*begin), begin->previous);
    }

private:
    static __thread size_t CurrentLevel = 0;

    template <typename It>
    static void Sort(It begin, It end) {
        using Ref = typename std::iterator_traits<It>::const_reference;

        auto const sorter = [](Ref left, Ref right) {
            return std::tie(level(left), left) < std::tie(level(right), right);
        };

        std::sort(begin, end, sorter);
    }

    static size_t LevelUp(size_t const to) {
        if (CurrentLevel >= to) { throw LockHierarchyViolation(); }
        CurrentLevel = to;
    }

    static void LevelDown(size_t const from, size_t const to) {
        if (CurrentLevel != from) { throw LockHierarchyViolation(); }
        CurrentLevel = to;
    }
}; // class LevelManager

For kicks, I implemented the possibility to lock multiples locks of the same level in a single shot.