Using a range for loop and erasing an item may cause mem error

vagetablechicken commented 4 years ago

Describe the bug https://github.com/apache/incubator-doris/blob/367b4c058c2c2c5da921f7227b83f0abb95a9198/be/src/olap/txn_manager.cpp#L419-L440

To Reproduce Steps to reproduce the behavior:

Create a simple test
```
#include <map>
```

int main(){ std::map<int,std::map<int,int> > m; m[0][2]=0; m[1][3]=1;

for(auto& it: m){
    auto ita=it.second.find(2);
    if(ita != it.second.end()) it.second.erase(2);
    if(it.second.empty()){
        m.erase(it.first);
    }
}
return 0;

}

2. g++ -ggdb main.cpp -std=c++11 && valgrind ./a.out
3. Output:

==13382== Memcheck, a memory error detector ==13382== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==13382== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info ==13382== Command: ./a.out ==13382== ==13382== Invalid read of size 8 ==13382== at 0x4EDD640: local_Rb_tree_increment (tree.cc:62) ==13382== by 0x4EDD640: std::_Rb_tree_increment(std::_Rb_tree_node_base) (tree.cc:85) ==13382== by 0x4011F6: std::_Rb_tree_iterator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >::operator++() (stl_tree.h:287) ==13382== by 0x400D39: main (main.cpp:9) ==13382== Address 0x5ab1c98 is 24 bytes inside a block of size 88 free'd ==13382== at 0x4C2B44D: operator delete(void) (vg_replace_malloc.c:586) ==13382== by 0x403F8D: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::deallocate(std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, unsigned long) (new_allocator.h:125) ==13382== by 0x403BF2: std::allocator_traits<std::allocator<std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > > >::deallocate(std::allocator<std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >&, std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, unsigned long) (alloc_traits.h:462) ==13382== by 0x402E40: std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_put_node(std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >) (stl_tree.h:592) ==13382== by 0x401A4D: std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_drop_node(std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >) (stl_tree.h:659) ==13382== by 0x403B7B: std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_erase_aux(std::_Rb_tree_const_iterator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >) (stl_tree.h:2477) ==13382== by 0x402DC7: std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_erase_aux(std::_Rb_tree_const_iterator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::_Rb_tree_const_iterator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >) (stl_tree.h:2491) ==13382== by 0x4019DB: std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::erase(int const&) (stl_tree.h:2502) ==13382== by 0x4012EA: std::map<int, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::erase(int const&) (stl_map.h:1063) ==13382== by 0x400D2A: main (main.cpp:13) ==13382== Block was alloc'd at ==13382== at 0x4C2A4C3: operator new(unsigned long) (vg_replace_malloc.c:344) ==13382== by 0x403FE1: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::allocate(unsigned long, void const) (new_allocator.h:111) ==13382== by 0x403C2E: std::allocator_traits<std::allocator<std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > > >::allocate(std::allocator<std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >&, unsigned long) (alloc_traits.h:436) ==13382== by 0x402F96: std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_get_node() (stl_tree.h:588) ==13382== by 0x401B76: std::_Rb_tree_node<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_create_node<std::piecewise_construct_t const&, std::tuple<int&&>, std::tuple<> >(std::piecewise_construct_t const&, std::tuple<int&&>&&, std::tuple<>&&) (stl_tree.h:642) ==13382== by 0x4014EF: std::_Rb_tree_iterator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > std::_Rb_tree<int, std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > >, std::_Select1st<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::_M_emplace_hint_unique<std::piecewise_construct_t const&, std::tuple<int&&>, std::tuple<> >(std::_Rb_tree_const_iterator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > >, std::piecewise_construct_t const&, std::tuple<int&&>&&, std::tuple<>&&) (stl_tree.h:2398) ==13382== by 0x401065: std::map<int, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > >, std::less, std::allocator<std::pair<int const, std::map<int, int, std::less, std::allocator<std::pair<int const, int> > > > > >::operator (stl_map.h:512) ==13382== by 0x400BDF: main (main.cpp:6) ==13382== ==13382== ==13382== HEAP SUMMARY: ==13382== in use at exit: 0 bytes in 0 blocks ==13382== total heap usage: 5 allocs, 5 frees, 72,960 bytes allocated ==13382== ==13382== All heap blocks were freed -- no leaks are possible ==13382== ==13382== For counts of detected and suppressed errors, rerun with: -v ==13382== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

**Additional context**
We met a core in production env

Aborted at 1578365820 (unix time) try "date -d @1578365820" if you are using GNU date *** PC: @ 0x2d086c4 std::_Rb_tree_increment()

SIGSEGV (@0x18) received by PID 337483 (TID 0x7f5f94512700) from PID 24; stack trace: *** @ 0x7f600c05b250 (unknown)

@          0x2d086c4 std::_Rb_tree_increment()

@           0xe7929f doris::TxnManager::force_rollback_tablet_related_txns()

@          0x1391698 doris::TaskWorkerPool::_drop_tablet_worker_thread_callback()

@     0x7f600be11dc5 start_thread

@     0x7f600c11d73d __clone


Maybe this mem error is the reason.

vagetablechicken commented 4 years ago

Based on https://en.cppreference.com/w/cpp/language/range-for, I produce code equivalent to the following:

    for(auto beg=m.begin(), end=m.end(); beg !=end; ++beg){
        auto ita=(*beg).second.find(2);
        if(ita != (*beg).second.end()) (*beg).second.erase(2);
        if((*beg).second.empty()){
            m.erase((*beg).first);
        }
    }

The valgrind report is the same like 'range for statement'. So I infer that using a range for loop and erasing an item can't avoid iterator invalidation. Although, I can't confirm how range for statement runs. Maybe the stl sources have the answer.

imay commented 4 years ago

@vagetablechicken

You're right, this is a bug. Could you please help us fix it.

vagetablechicken commented 4 years ago

@imay OK, I will fix it.

apache / doris

Using a range for loop and erasing an item may cause mem error #2697