Pull to refresh

Динамический поиск потенциальных взаимоблокировок

Reading time 6 min
Views 7.4K
Здравствуйте. Некоторое время назад начал заниматься сопровождением довольно объемного программного продукта. Правка за правкой и как-то незаметно ко мне подкрались взаимоблокировки. Я быстро выяснил источник проблем — это вложенные блокировки. По незнанию основ программного продукта я неявно нарушил порядок вложения блокировок. Но найти вручную источник проблем не удалось.

Боржоми пить поздно, причитать насчёт архитектуры бессмысленно. Подключаем тяжелую артиллерию.


Итак, классическая проблема (псевдокод):
object m1;
object m2;

// thread 1
quard<> g1(m1);
....
// ожидаем освобождения m2 потоком thread 2 
quard<> g2(m2);

// thread 2
quard<> g2(m2);
....
// ожидаем освобождения m2 потоком thread 1
quard<> g1(m1);


Если бы ресурсы блокировались одновременно или в одинаковой последовательности взаимоблокировки бы не произошло.

Идея.


Пусть класс блокировщик составляет граф последовательности блокировок объектов и когда при очередной вставке будет обнаружена циклическая ссылка это и будет искомая потенциальная взаимоблокировка.
Пример:
где то в коде потока: guard(m1) --> guard(m2)
где то в коде потока: guard(m2) --> guard(m1)!!! alarm!!! обнаружена циклическая ссылка.

Реализация


Делать реализацию графов самостоятельно это тяжко. Я задействовал «boost/graph».
Для учёта возможности блокировки в потоках модулей DLL — «boost/interprocess».
Расписывать внутреннее устройство смысла нет. Некоторые основные пункты:
  • для каждого потока хранится свой список текущих блокировок, для игнорирования реентабельных блокировок
  • граф хранится в разделяемой памяти процесса

Использование тривиально:
#define ENABLE_DEADLOCK_CHECKER
/**/
#include "deadlock_checker.h"

static deadlock_checker_main_t deadlock_checker_main;

/*класс блокировщик ресурса*/
class guard
{
     guard()
  {
    deadlock_checker_t::push(this);
  } 
    ~guard()
  {
    deadlock_checker_t::pop(this);
  } 
};


P.S. Всё закончилось хорошо. Я отловил deadlock. Познал дао сего программного продукта и отключил модуль контроля за ненадобностью.

рабочий код

/*
*	динамический поиск  потенциальных взаимо- блокировок. 
*/
#pragma once
#include <assert.h>
#include <stack>
#include <map>
#include <vector>
#include <boost/thread/mutex.hpp>
#include <boost/thread/tss.hpp>
#include <boost/thread/once.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/filesystem.hpp>
#include <boost/interprocess/managed_shared_memory.hpp>
#ifdef _DEBUG
//#define ENABLE_DEADLOCK_CHECKER
#endif
namespace deadlock_checker
{

    inline unsigned long get_current_process_id()
    {  
        return GetCurrentProcessId(); 
    }

    /**интерфейс глобального графа*/
    template<typename T>
    struct deadlock_graph_i
    {
       /**вставка ребра графа
      * @return true если обнаружена циклическая ссылка
      */
        virtual bool _cdecl insert(const void* locker_child, const void* locker_root) = 0;
    };
    /**реализация глобального графа*/
    template<typename T>
    class deadlock_graph : public deadlock_graph_i<T>
    {
        struct cycle_detector : public ::boost::dfs_visitor<>
        {
            cycle_detector(bool& has_cycle) 
                : m_has_cycle(has_cycle) { }

            template <class Edge, class Graph>
            void back_edge(Edge, Graph&) { m_has_cycle = true; 
            }
        protected:
            bool& m_has_cycle;
        };
        typedef ::boost::adjacency_list<::boost::mapS, ::boost::mapS, ::boost::bidirectionalS,
            ::boost::property<::boost::vertex_color_t, ::boost::default_color_type> > Graph;
        typedef typename ::boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
        typedef typename ::boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
        typedef const void* type_value;
    public:
        ::boost::mutex _mutex; 
        Graph _graph;
        ::std::map<type_value, vertex_descriptor> _vertex;
    public:
        deadlock_graph()
        {
        }
       /**вставка ребра графа
      * @return true если обнаружена циклическая ссылка
      */
        bool _cdecl insert(const void* locker_child, const void* locker_root)
        {
            using namespace ::boost;
            using namespace ::std;
            mutex::scoped_lock scoped_lock(_mutex);

            if(_vertex.end() == _vertex.find(locker_child))
            {
                _vertex.insert(make_pair(locker_child, add_vertex(_graph) ));
            }

            if(_vertex.end() == _vertex.find(locker_root))
            {
                _vertex.insert(make_pair(locker_root, add_vertex(_graph) ));
            }
            vertex_descriptor vertex_child = _vertex[locker_child];
            pair<edge_descriptor, bool> ret = add_edge(vertex_child,_vertex[locker_root],_graph);
            if(ret.second)
            {
                bool has_cycle = false;
                cycle_detector vis(has_cycle);
                //_color_map.resize(num_vertices(_graph)); //= color_map(num_vertices(_graph));
                //::std::fill(_color_map.begin(),_color_map.end(),white_color);

                graph_traits<Graph>::vertex_iterator vi, vi_end;
                for (tie(vi, vi_end) = vertices(_graph); vi != vi_end; ++vi)
                    get(vertex_color, _graph)[*vi] = white_color;

                depth_first_visit(_graph, vertex_child, vis,
                    get(vertex_color, _graph) );
                if(has_cycle)
                {
                    // зачищаем граф, для построения заново.
                    _graph.clear();
                    _vertex.clear();

                }
                return !has_cycle;
            }
            return true;
        }

    };
    inline char const* deadlock_shared_key()
    {
        return "1958EF20-6689-4e7b-9C53-3C115BCCF465";
    }
    /**главный граф, область видимости : процесс*/
    template<typename T>
    class main
    {
        deadlock_graph<T> _graph;
    public:
        main()
        {
            using namespace boost::interprocess;
            char process_id_str[20];
            if(0 != _itoa_s(get_current_process_id(),process_id_str,sizeof(process_id_str),10))
            {
                throw ::std::runtime_error(__FUNCTION__);
            }

            managed_shared_memory shmem(open_or_create, deadlock_shared_key(), 1024);    
            shmem.construct<deadlock_graph<T>*>(process_id_str)(&_graph);

        }
    };
    /**глобальный интерфейс*/
    template<typename T>
    class checker
    {
    private:
        /**инициализатор глобальной ссылки на главный граф.*/
        struct main_ref
        {
            deadlock_graph_i<T>* & _graph_ptr;
        public:
            main_ref(deadlock_graph_i<T>* & graph_ptr)
                : _graph_ptr(graph_ptr)
            {
            }
            void operator()() const
            {
                using namespace boost::interprocess;
                char process_id_str[20];
                if(0 != _itoa_s(get_current_process_id(),process_id_str,boost::size(process_id_str),10))
                {
                    throw ::std::runtime_error(__FUNCTION__);
                }
                managed_shared_memory shmem(open_read_only, deadlock_shared_key());    
                _graph_ptr = *shmem.find<deadlock_graph<T>*>(process_id_str).first;
                if(!_graph_ptr)
                {
                    throw ::std::runtime_error(__FUNCTION__);
                }
            }
        };
    private:
        /**стек блокировок,  данные для текущего потока*/
        static boost::thread_specific_ptr<::std::stack<void*> > _stack;
        /**глобальный граф, область видимости : процесс*/
        static deadlock_graph_i<T>* _graph_ptr;
        static boost::once_flag     _graph_flag;
    public:
        /**извещение об начале блокировки ресурса "locker"*/
        static bool push(void* locker)
        {
            // флаг обнаружения циклической ссылки 
            bool cycle_error = false;
            init_thread();
            ::std::stack<void*>* lockers = _stack.get();
            assert(lockers && lockers->size() < 8);
            if(lockers->size() > 0)
            {
                void* locker_root = lockers->top();
                if(locker_root != locker)
                {
                    // логируем потенциальную взаимо-блокировку.
                    char const * filename = ".\\Data\\deadlock.log";
                    if(!::boost::filesystem::is_regular_file(filename))
                    {
                        // вставляем ребро в граф.
                        cycle_error = !_graph_ptr->insert(locker,locker_root);
                        assert(!cycle_error && "потенциальный deadlock");
                        if(cycle_error)
                        {
                            ::std::ofstream file(filename);
                            if(file.is_open())
                            {
                                file << "обнаружена потенциальный deadlock" << ::std::endl;
                            }
                        }
                    }
                }
            }
            lockers->push(locker);
            return cycle_error;
        };
        /**извещение об окончании блокировки ресурса "locker"*/
        static void pop(void* locker = 0)
        {
            ::std::stack<void*>* lockers = _stack.get();
            assert(lockers && !lockers->empty());
            assert(!locker || lockers->top() == locker);
            if(!lockers->empty())
            {
                lockers->pop();
            };
        };
    private:
        /**инициализация данных для текущего потока */
        static void init_thread()
        {
            if(!_stack.get())
            {
                boost::call_once(_graph_flag, main_ref(_graph_ptr));
                _stack.reset(new ::std::stack<T*>);
            }
        }
    };


    template<typename T>
    boost::thread_specific_ptr<::std::stack<void*> > checker<T>::_stack;
    template<typename T>
    deadlock_graph_i<T>* checker<T>::_graph_ptr;
    template<typename T>
    boost::once_flag       checker<T>::_graph_flag;

    /**пустая реализация*/
    template<>
    class checker<bool>
    {
    public:
        static bool push(void* /*locker*/, char* /*name*/)
        {
            return true;
        }
        /***/
        static bool push(void* /*locker*/)
        {
            return true;
        };
        /***/
        static void pop(void* /*locker*/ = 0)
        {
        };
    };
    /**пустая реализация*/
    template<>
    class main<bool>
    {
    };
}

#if defined(ENABLE_DEADLOCK_CHECKER)
typedef deadlock_checker::checker<void> deadlock_checker_t;
typedef deadlock_checker::main<void> deadlock_checker_main_t;
#else
typedef deadlock_checker::checker<bool> deadlock_checker_t;
typedef deadlock_checker::main<bool> deadlock_checker_main_t;
#endif


Tags:
Hubs:
+8
Comments 7
Comments Comments 7

Articles