C++11: Lock Leveling

• Download RAIILevelLock.zip - 6.4 KB Requires Visual C++ Compiler November 2012 CTP

Introduction

This article introduces the use of lock leveling to prevent deadlocks. Lock leveling is also known as lock ordering, lock ranking and lock hierarchies. Lock leveling always acquire the locks in relative order to prevent deadlocks. Let us look at a simple deadlock example.

void Thread1()
{
    Lock lock1(A);
    {
        Lock lock2(B);
        {...}
    }
}

void Thread2()
{
    Lock lock1(B);
    {
        Lock lock2(A);
        {...}
    }
}

If Thread1 holds lock A while waiting to hold lock B and at the same time Thread2 holds lock B while waiting to hold lock A, both threads fail to get the second lock they want, thus a deadlock occurs.

void Thread1()
{
    Lock lock1(A,B);
    {
        ...
    }
}

void Thread2()
{
    Lock lock1(B,A);
    {
        ...
    }
}

If we could acquire all the locks at the same time in an atomic operation as shown above, we could solve the problem. However that is not possible. One obvious way to solve this is to always take locks in relative order. One way is to encapsulate the CRITICAL_SECTION in a CritSectLock class and use the address of the CRITICAL_SECTION as a unique relative number. Then lock these critical section objects using a RAII lock class which will always sort the instances of critical section class before acquiring the lock, so they will always be acquired in the same order. This RAII lock class will release the locks in its destructor. The order of releasing the locks does not matter as releasing the locks does not result in a deadlock. The next section shows CritSectLock class.

CritSectLock class

#pragma once
#define WIN32_LEAN_AND_MEAN
#include <windows.h>

class CritSectLock
{
public:
    CritSectLock(void)
    {
        InitializeCriticalSection(&m_cs);
    }

    ~CritSectLock(void)
    {
        DeleteCriticalSection(&m_cs);
    }

    void Enter()
    {
        EnterCriticalSection(&m_cs);
    }

    void Leave()
    {
        LeaveCriticalSection(&m_cs);
    }

    CRITICAL_SECTION* GetInternalCritSect()
    {
        return &m_cs;
    }

private:
    /*  Do not make the Copying constructor and Assignment operator public!
        We are not supposed to make a copy of CRITICAL_SECTION or move it around, 
        unless you make your CRITICAL_SECTION member a pointer.   */
    // Copy constructor
    CritSectLock(CritSectLock&) {}
    // Assignment operator
    CritSectLock& operator=(CritSectLock&) {}

    CRITICAL_SECTION m_cs;
};

CritSectLock is a typical class encapsulating the CRITICAL_SECTION. The copy constructor and assignment operator are made private because we are not supposed to make a copy of CRITICAL_SECTION or move it around. C++11 delete (shown below) could be used to prevent the compiler to generate a default version of these functions but VS2012 compiler does not recognize the keyword.

// Copy constructor
CritSectLock(CritSectLock&) = delete
// Assignment operator
CritSectLock& operator=(CritSectLock&) = delete

RAII lock leveling class

The RAII lock leveling class adds all the critical sections to a vector and lock them after sorting in its constructor and unlocks them in its destructor.

#pragma once
#include "CritSectLock.h"
#include <vector>
#include <algorithm>
#include <functional>

// sort comparer functor
struct CritSectLockComp : public std::binary_function<CRITICAL_SECTION*, CRITICAL_SECTION*, bool>
{
    bool operator()( CRITICAL_SECTION* a, CRITICAL_SECTION* b )
    {
        return ( a < b );
    }
};

class Lock
{
public:
    template<typename... Args>
    Lock(Args&&... args)
    {
        Recurse(std::forward<Args>(args)...);
    }

    template<typename T, typename... Args>
    void Recurse(T&& lock, Args&&... args)
    {
        Add(std::forward<T>(lock));
        Recurse(args...);
    }

    void Recurse()
    {
        LockAll();
    }

    void Add(CRITICAL_SECTION* crit)
    {
        m_vec.push_back(crit);
    }

    void Add(CritSectLock& crit)
    {
        m_vec.push_back(crit.GetInternalCritSect());
    }

    ~Lock(void)
    {
        for(size_t i=0; i<m_vec.size(); ++i)
        {
            LeaveCriticalSection(m_vec[i]);
        }
    }

private:
    void LockAll()
    {
        if(std::is_sorted(m_vec.begin(),m_vec.end())==false)
            std::sort(m_vec.begin(),m_vec.end(), CritSectLockComp());

        for(size_t i=0; i<m_vec.size(); ++i)
        {
            EnterCriticalSection(m_vec[i]);
        }
    }

    std::vector<CRITICAL_SECTION*> m_vec;
};

The variadic constructor delegate its work to a Recurse function because the constructor cannot be called recursively as it will construct a new instance, in other words, critical section is added to the vector of that new instance. There is 2 overloaded Add functions, one takes in a CRITICAL_SECTION pointer while the other takes in CritSectLock instance. rvalue reference and std::forward is used for perfect forwarding. Before sorting, we did a check whether the vector is already sorted with new standard library function, std::is_sorted.

This is an example on how to use the RAII lock class with CritSectLock.

#include "Lock.h"

int main()
{
    CritSectLock a;
    CritSectLock b;
    Lock lock(b,a);
	
    // do your stuff here
	
    return 0;
}

References

• Concurrent Programming on Windows by Joe Duffy
• C++ Coding Standards by Herb Sutter and Andrei Alexandrescu