Click here to Skip to main content
Click here to Skip to main content

C++11: Lock Leveling

, 17 Feb 2013
Rate this:
Please Sign up or sign in to vote.
Implement lock leveling on Windows critical sections

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Shao Voon Wong
Software Developer
Singapore Singapore

Currently into areas like 3D graphics and application security. Hoping to revisit the cryptography and design pattern topics if time permits.


Comments and Discussions

 
GeneralMy vote of 3 Pinmemberhatemtaleb28-Aug-13 7:34 
GeneralRe: My vote of 3 PinmemberWong Shao Voon30-Oct-13 15:33 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 17 Feb 2013
Article Copyright 2013 by Shao Voon Wong
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid