c++ - 解释 Valgrind 输出以找出数据竞争的位置

Question

以下是运行 Helgrind 的输出，它检测数据竞争。它表明该内存位置 0x5C8AD88 在未 protected 情况下被共享。

==7568== ----------------------------------------------------------------
==7568== 
==7568== Possible data race during read of size 8 at 0x5C8AD88 by thread #3
==7568== Locks held: none
==7568==    at 0x406616: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_S_right(std::_Rb_tree_node_base*) (stl_tree.h:535)
==7568==    by 0x4102F1: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::equal_range(long const&) (stl_tree.h:1174)
==7568==    by 0x40FE1E: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::erase(long const&) (stl_tree.h:1521)
==7568==    by 0x40FA70: std::map<long, demon::Edge*, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::erase(long const&) (stl_map.h:654)
==7568==    by 0x40F599: demon::Vertex::eliminate(demon::CGraph&) (Vertex.cpp:286)
==7568==    by 0x404723: demon::CGraph::reverse_eliminate(int, demon::CGPart*) (CGraph.cpp:390)
==7568==    by 0x404959: demon::CGraph::reverse_eliminate(void*) (CGraph.cpp:441)
==7568==    by 0x40CC74: ThreadPool::execute_task(void*) (ThreadPool.cpp:156)
==7568==    by 0x4C2ED9D: ??? (in /usr/lib64/valgrind/vgpreload_helgrind-amd64-linux.so)
==7568==    by 0x4E3DE0E: start_thread (in /lib64/libpthread-2.17.so)
==7568==    by 0x59547DC: clone (in /lib64/libc-2.17.so)
==7568== 
==7568== This conflicts with a previous write of size 8 by thread #1
==7568== Locks held: none
==7568==    at 0x50CB6B0: std::_Rb_tree_insert_and_rebalance(bool, std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, std::_Rb_tree_node_base&) (in /usr/lib64/libstdc++.so.6.0.17)
==7568==    by 0x410165: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_M_insert_(std::_Rb_tree_node_base const*, std::_Rb_tree_node_base const*, std::pair<long const, demon::Edge*> const&) (stl_tree.h:981)
==7568==    by 0x40FD6D: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_M_insert_unique(std::pair<long const, demon::Edge*> const&) (stl_tree.h:1299)
==7568==    by 0x40FA28: std::map<long, demon::Edge*, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::insert(std::pair<long const, demon::Edge*> const&) (stl_map.h:523)
==7568==    by 0x40EFF4: demon::Vertex::add_in_edge(demon::Vertex*, double) (Vertex.cpp:213)
==7568==    by 0x4049AA: demon::CGraph::add_edge(demon::Vertex*, demon::Vertex*, double) (CGraph.cpp:453)
==7568==    by 0x408AB4: demon::CGBuilder::build_cg(demon::active const&, double, demon::active const&, double, demon::active const&, bool, bool) (CGBuilder.cpp:221)
==7568==    by 0x40314D: demon::binary_op(demon::active const&, double, demon::active const&, double, demon::active const&, bool, bool) (API.cpp:55)
==7568== 
==7568== Address 0x5C8AD88 is 24 bytes inside a block of size 48 alloc'd
==7568==    at 0x4C2BD37: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_helgrind-amd64-linux.so)
==7568==    by 0x4108BE: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<long const, demon::Edge*> > >::allocate(unsigned long, void const*) (new_allocator.h:94)
==7568==    by 0x410795: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_M_get_node() (stl_tree.h:369)
==7568==    by 0x410516: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_M_create_node(std::pair<long const, demon::Edge*> const&) (stl_tree.h:379)
==7568==    by 0x410146: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_M_insert_(std::_Rb_tree_node_base const*, std::_Rb_tree_node_base const*, std::pair<long const, demon::Edge*> const&) (stl_tree.h:979)
==7568==    by 0x40FD6D: std::_Rb_tree<long, std::pair<long const, demon::Edge*>, std::_Select1st<std::pair<long const, demon::Edge*> >, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::_M_insert_unique(std::pair<long const, demon::Edge*> const&) (stl_tree.h:1299)
==7568==    by 0x40FA28: std::map<long, demon::Edge*, std::less<long>, std::allocator<std::pair<long const, demon::Edge*> > >::insert(std::pair<long const, demon::Edge*> const&) (stl_map.h:523)
==7568==    by 0x40EFF4: demon::Vertex::add_in_edge(demon::Vertex*, double) (Vertex.cpp:213)
==7568==    by 0x4049AA: demon::CGraph::add_edge(demon::Vertex*, demon::Vertex*, double) (CGraph.cpp:453)
==7568==    by 0x40890F: demon::CGBuilder::build_cg(demon::active const&, double, demon::active const&, bool, bool, bool) (CGBuilder.cpp:170)
==7568==    by 0x4030D4: demon::unary_op(demon::active const&, double, demon::active const&, bool, bool, bool) (API.cpp:50)
==7568==    by 0x402629: demon::operator*(double, demon::active const&) (Active.cpp:92)
==7568== 
==7568== ----------------------------------------------------------------

此函数由线程 #1 执行。

Edge * Vertex::add_in_edge( Vertex * src , double eval  )
{
        assert(src!=NULL);

    Edge *  in_et = new Edge( src, this, eval );

    in_edges.insert( std::pair<idx_t,Edge*>( src->idx , in_et ) );

    src->out_edges.insert( std::pair<idx_t,Edge*>( this->idx , in_et ) );

    //pthread_mutex_lock(&ostream_lock);

    //std::cout << "inside add_in_edge()" << std::endl;

    //std::cout << "address of new inedge " << in_et << std::endl;
    //std::cout << "address of this vertex " << this << std::endl;
    //std::cout << "address of this vertex idx " << &(this->idx) << std::endl;
    //std::cout << "address of src vertex " << src << std::endl;
    //std::cout << "address of src vertex's outedge container " << &(src->out_edges) << std::endl;
    //std::cout << "address of src vertex's inedge container " << &(src->in_edges) << std::endl;

    //pthread_mutex_unlock(&ostream_lock);

    return in_et;
}

此函数由线程 #3 执行。

dim_t Vertex::eliminate( CGraph & cg )
{
        dim_t nMults = 0;

    std::map<idx_t,Edge*>::iterator inedge_it;

    std::map<idx_t,Edge*>::iterator outedge_it;

    dim_t m =  in_edges.size();
    dim_t n  = out_edges.size();

    //std::cout << "vertex " << idx << " is in block " << prt_idx << std::endl;

    for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )

        outedge_it->second->tgt->in_edges.erase(this->idx);

    for( inedge_it=in_edges.begin() ; inedge_it!=in_edges.end() ; inedge_it++ )
    {
        inedge_it->second->src->out_edges.erase(this->idx);

        //pthread_mutex_lock(&ostream_lock);

        //std::cout << "inside eliminate()" << std::endl;

        //std::cout << "address of this edge " << inedge_it->second << std::endl;
        //std::cout << "address of this vertex " << this << std::endl;
        //std::cout << "address of this vertex idx " << &(this->idx) << std::endl;
        //std::cout << "address of src vertex " << inedge_it->second->src << std::endl;
        //std::cout << "address of src vertex's inedge container " << &(inedge_it->second->src->in_edges) << std::endl;
        //std::cout << "address of src vertex's outedge container  " << &(inedge_it->second->src->out_edges) << std::endl;

        //pthread_mutex_unlock(&ostream_lock);

        for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
        {   
            double cij = (inedge_it->second->eval)*(outedge_it->second->eval);

            nMults++;

            Edge * direct_link = NULL;

            std::map<idx_t,Edge*>::iterator direct_link_it;

            direct_link_it = inedge_it->second->src->out_edges.find(outedge_it->second->tgt->idx);

            if(direct_link_it!=inedge_it->second->src->out_edges.end())
            {
                direct_link = direct_link_it->second;
            }

            if(direct_link)
            {
                direct_link->eval += cij;

            }else
            {
                outedge_it->second->tgt->add_in_edge( inedge_it->second->src , cij );
            }
        }

        delete inedge_it->second;
    }

    for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
    {   
        delete outedge_it->second;
    }

    in_edges.clear();
    out_edges.clear();

    return nMults;
}

这是 Vertex 类的样子。它有 out_edges 和 in_edges 到分别存储出边和入边。

class Vertex 
{
public :

    //unsigned char properties;

    bool live;

    bool temporary;

    bool local;

    /**************************************
    *the unique identifier for each vertex
    **************************************/
    idx_t idx;

    /********************************************
    *which block/partition the vertex belongs to    
    *********************************************/
    idx_t prt_idx;

    /*******************************************************
    *which kind of vertex the vertex is : INDEP,INTMED,DEP
    *******************************************************/
    vertex_t kind;

    /****************************************************************
    *maps src vertex indinces to the corresponding incoming edges
    *****************************************************************/

    std::map<idx_t,Edge*> in_edges;

    /*******************************************************************
    *maps target vertex indinces to the corresponding outgoing edges
    ********************************************************************/

    std::map<idx_t,Edge*> out_edges;

    static pthread_mutex_t ostream_lock;

};//end of class

我正在尝试解释输出并找出位置 0x5C8AD88 处的变量。
输出是否表明 inedge_it->second->src->out_edges 中的变量 *out_edges*(来自函数 eliminate()) 和 src->out_edges.insert( std::pair( this->idx , in_et ) )( 来自 add_in_edge ) 是罪魁祸首？

Answer 1

答案在第三 block 输出中:

Address 0x5C8AD88 is 24 bytes inside a block of size 48 alloc'd
...
[...]::insert(std::pair<long const, demon::Edge*> const&)
demon::Vertex::add_in_edge(demon::Vertex*, double) (Vertex.cpp:213)

有问题的数据是由 add_in_edge() 在 insert() 期间创建的。你真的可以在这里停下来。数据竞争是您的 map 结构中的某个地方。果然，您的代码没有显示对 map 访问的任何锁定。您需要为对 in_edges 和 out_edges 的所有访问找出一个锁定方案。

在研究锁时，考虑从低级 pthreads 切换到 std::thread。如果您不使用 C++11，请改用 boost::thread。这些库中的互斥锁类更易于使用且不易出错。