SEGV在海合会的std :: unordered_map

Question

我在GCC遇到SEGV 4.7.2的unordered_map

在find()它调用_M_find_node，进而调用_M_find_before_node，传递桶数目，则关键我们重新搜索，以及哈希码。

在_M_find_before_node，它查找第一个节点在桶中的问题：

_BaseNode* __prev_p = _M_buckets[__n]; 

，然后得到以下这个节点：

_Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); 

的问题是，__prev_p->_M_nxt为null; _M_equals试图解引用它并导致seg错误。

我不是100％在unordered_map的内部工作线索 - 是否要求桶中的第一个节点的_M_nxt是非空的，或者这是一个错误？

有问题的代码是在这里：

// Find the node whose key compares equal to k in the bucket n. Return nullptr 
    // if no node is found. 
    template<typename _Key, typename _Value, 
     typename _Allocator, typename _ExtractKey, typename _Equal, 
     typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
     bool __chc, bool __cit, bool __uk> 
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 
      _Equal, _H1, _H2, _Hash, _RehashPolicy, 
      __chc, __cit, __uk>::_BaseNode* 
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 
      _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 
    _M_find_before_node(size_type __n, const key_type& __k, 
      typename _Hashtable::_Hash_code_type __code) const 
    { 
     _BaseNode* __prev_p = _M_buckets[__n]; 
     if (!__prev_p) 
    return nullptr; 
     _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); // __p is null here!! 
     for (;; __p = __p->_M_next()) 
    { 
     if (this->_M_equals(__k, __code, __p)) 
     return __prev_p; 
     if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n) 
     break; 
     __prev_p = __p; 
    } 
     return nullptr; 
    } 

Answer 1

更换

我不是100％在unordered_map的内部工作线索 - 是否需要一个桶的第一个节点_M_nxt非空，或者这是一个错误？

的问题显然是专门针对GCC的实现，但我敢肯定，如果_M_buckets[__n]非null，则_M_buckets[__n]->_M_nxt应该是非空了。

即，如果存储桶为空，则为_M_buckets[__n]==nullptr，如果存储桶不空，则_M_buckets[__n]->_M_nxt是存储桶中的第一个节点。

尝试使用-D_GLIBCXX_DEBUG进行构建，看看它是否可以识别您的代码存在问题，但可能存在一个错误，但它更可能以某种方式损坏了容器或者错误地使用了它。

Answer 2

除非你已经检测到GCC std::unorderd_map执行一个错误，你的错误的最可能的原因是你不喜欢的东西：

std::unorderd_map<MyKey, MyValue> my_map; 
auto it = my_map.find(some_key); // if some_key was not found, it == my_map.end() 
do something with *it;   // kaboom! derefence of past-the-end iterator 

如果是这样的情况下，

if (it != my_map.end()) { 
    do something with *it; 
} 

Answer 3

问题现在已经很老了，但我最近也遇到过同样的问题，下面是如何重现它的示例代码。

#include <chrono> 
#include <iostream> 
#include <thread> 
#include <unordered_map> 

int main() 
{ 
    std::unordered_map< std::string, int > m_Map{}; 

    m_Map.insert(std::make_pair("a", 0x61)); 
    auto count{1000u}; 

    auto t_remove = std::thread([&m_Map, &count]() { 

     while (1) 
     { 
     m_Map.erase("a"); 
     std::this_thread::sleep_for(std::chrono::nanoseconds(count)); 
     if(count > 10) 
     { 
      count-=10; 
     } 
     else 
     { 
      count = 1000u; 
     } 
     m_Map.insert(std::make_pair("a", 0x61)); 
     } 
    }); 

    while (1) 
    { 
     auto it = m_Map.find("a"); 

     if (it != m_Map.end()) 
     { 
     std::cerr << "Map has a " << it->first << " = " << it->second << "\n"; 
     } 
     else 
     { 
     std::cerr << "Map does not have a \"a\"\n"; 
     } 
    } 

    t_remove.join(); 
    return 0; 
} 

在几次迭代（GDB）之后的结果：

Thread 1 "find_stress_tes" received signal SIGSEGV, Segmentation fault. 
0x000000000040505b in std::__detail::_Equal_helper<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int>, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, unsigned long, true>::_S_equals (__eq=..., __extract=..., __k="a", __c=4993892634952068459, __n=0x0) 
    at /usr/include/c++/5/bits/hashtable_policy.h:1322 
1322  { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); } 
(gdb) bt 
#0 0x000000000040505b in std::__detail::_Equal_helper<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int>, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, unsigned long, true>::_S_equals (__eq=..., __extract=..., __k="a", __c=4993892634952068459, __n=0x0) 
    at /usr/include/c++/5/bits/hashtable_policy.h:1322 
#1 0x0000000000404b2a in std::__detail::_Hashtable_base<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int>, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >::_M_equals (this=0x7fffffffdd40, __k="a", 
    __c=4993892634952068459, __n=0x0) at /usr/include/c++/5/bits/hashtable_policy.h:1704 
#2 0x00000000004044ef in std::_Hashtable<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int> >, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node (this=0x7fffffffdd40, __n=1, 
    __k="a", __code=4993892634952068459) at /usr/include/c++/5/bits/hashtable.h:1433 
#3 0x0000000000403e50 in std::_Hashtable<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int> >, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_node (this=0x7fffffffdd40, __bkt=1, __key="a", 
    __c=4993892634952068459) at /usr/include/c++/5/bits/hashtable.h:632 
#4 0x000000000040392b in std::_Hashtable<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int> >, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::find (this=0x7fffffffdd40, __k="a") 
    at /usr/include/c++/5/bits/hashtable.h:1307 
#5 0x0000000000403675 in std::unordered_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, int> > >::find (this=0x7fffffffdd40, 
    __x="a") at /usr/include/c++/5/bits/unordered_map.h:615 
#6 0x000000000040184b in main() at ../find_stress_test/main.cpp:40 

原因说起来很简单，并发访问，解决方案将是同步的。

我希望能帮到别人;）