Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

AddressSanitizer/Valgrind raises a new-delete-type-mismatch for BTreeDelete #2127

Closed
brofranks opened this issue Nov 16, 2021 · 1 comment
Closed

AddressSanitizer/Valgrind raises a new-delete-type-mismatch for BTreeDelete #2127

brofranks opened this issue Nov 16, 2021 · 1 comment
Labels
bug - triage Bugs with unknown causes that require further investigation

Comments

@brofranks
Copy link
Member

brofranks commented Nov 16, 2021 •
edited
Loading

In the below stress test of the btree_delete class AddressSanitizer raises a new-delete-type-mismatch error:

TEST(BTreeDelete, EraseStress) {
    using test_set = btree_delete_set<int, detail::comparator<int>, std::allocator<int>, 2>;

    test_set t;

    int N = 1000;

    std::vector<int> data;
    std::set<int> expected_set;
    for (int i = 0; i < N; i++) {
        data.push_back(i);
        expected_set.insert(i);
        t.insert(i);
    }
    std::random_device rd;
    std::mt19937 generator(rd());

    shuffle(data.begin(), data.end(), generator);

    for (int i = 0; i < N; i++) {
        EXPECT_EQ(expected_set.size(), t.size());

        expected_set.erase(data[i]);
        t.erase(data[i]);

        EXPECT_TRUE(std::equal(expected_set.begin(), expected_set.end(), t.begin()));
    }
}

The error gets raised on this line triggered by the t.erase(data[i]); line.

Observations:

  • The following simple test passes:
TEST(BTreeDelete, EraseBasic) {
    using test_set = btree_delete_set<int, detail::comparator<int>, std::allocator<int>, 2>;
    test_set t;

    int N = 10;

    for (int i = 0; i <= N; i++) {
        t.insert(i);
    }

    for (int i = 0; i <= N; i++) {
        EXPECT_EQ((std::size_t)(N + 1 - i), t.size());
        t.erase(i);
    }

    EXPECT_TRUE(t.empty());
}
  • The same error gets raised for regular bucket size (16) so it is not a problem specific to small bucket sizes.
  • It doesn't seem to be related to parallelism — the test sequentially inserts tuples then removes tuples in a random order from the BTree and happens independently of CTest -j value (as expected).
  • The actual AddressSanitizer trace looks like:
19: Test command: /home/brody/tmp/tmp.CLNCss5bCn/cmake-build-debug-plang4-sanitizer/src/tests/test_btree_delete
19: Test timeout computed to be: 1500
19: BTreeDelete
19: Number of threads: 1[0.00273714ms]
19: Number of threads: 2[0.00293957ms]
19: Number of threads: 3[0.00223969ms]
19: Number of threads: 4[0.00239481ms]
19: Number of threads: 5[0.00187961ms]
19: Number of threads: 6[0.00186057ms]
19: Number of threads: 7[0.0017573ms]
19: Number of threads: 8[0.00211329ms]
19: 	OK (8024/8024)	ParallelScaling
19: 	OK (6021/6021)	Parallel
19: 	OK (49648302/49648302)	ChunkSplitStress
19: 0, 1, 2, 
19: 3, 4, 5, 6, 
19: 7, 8, 9, 10, 
19: 11, 12, 13, 14, 
19: 15, 16, 17, 18, 
19: 19, 20, 21, 22, 
19: 23, 24, 25, 26, 
19: 27, 28, 29, 30, 
19: 31, 32, 33, 34, 
19: 35, 36, 37, 38, 
19: 39, 40, 41, 42, 
19: 43, 44, 45, 46, 
19: 47, 48, 49, 50, 
19: 51, 52, 53, 54, 
19: 55, 56, 57, 58, 
19: 59, 60, 61, 62, 
19: 63, 64, 65, 66, 
19: 67, 68, 69, 70, 
19: 71, 72, 73, 74, 
19: 75, 76, 77, 78, 
19: 79, 80, 81, 82, 
19: 83, 
19: 84, 
19: 85, 
19: 86, 
19: 87, 88, 89, 90, 
19: 91, 92, 93, 94, 
19: 95, 96, 
19: 97, 98, 99, 
19: 	OK (100/100)	ChunkSplit
19: 	OK (4/4)	Clear
19: 	OK (5250/5250)	Load
19: 	OK (8/8)	BoundaryEmpty
19: 	OK (5/5)	BoundaryTest
19: 	OK (501500/501500)	IteratorStress
19: 	OK (13/13)	IteratorBasic
19: 	OK (1/1)	IteratorEmpty
19: 	OK (2/2)	Merge
19: =================================================================
19: ==506732==ERROR: AddressSanitizer: new-delete-type-mismatch on 0x6070002aaba0 in thread T0:
19:   object passed to delete has wrong type:
19:   size of the allocated type:   72 bytes;
19:   size of the deallocated type: 40 bytes.
19:     #0 0x7f7fd6f0208f in operator delete(void*, unsigned long) (/lib64/libasan.so.6+0xb308f)
19:     #1 0x489829 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::merge(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1913
19:     #2 0x47dc2a in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::merge_into_left_sibling(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1858
19:     #3 0x46e4ed in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::merge_or_rebalance(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1836
19:     #4 0x455dda in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::erase(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1672
19:     #5 0x447443 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::erase(int const&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1602
19:     #6 0x415635 in souffle::test::test_BTreeDelete_EraseStress::run() /home/brody/tmp/tmp.CLNCss5bCn/src/tests/btree_delete_test.cpp:367
19:     #7 0x403a2a in main /home/brody/tmp/tmp.CLNCss5bCn/src/tests/test.h:250
19:     #8 0x7f7fd68f6081 in __libc_start_main (/lib64/libc.so.6+0x27081)
19:     #9 0x4036cd in _start (/home/brody/tmp/tmp.CLNCss5bCn/cmake-build-debug-plang4-sanitizer/src/tests/test_btree_delete+0x4036cd)
19: 
19: 0x6070002aaba0 is located 0 bytes inside of 72-byte region [0x6070002aaba0,0x6070002aabe8)
19: allocated by thread T0 here:
19:     #0 0x7f7fd6f01027 in operator new(unsigned long) (/lib64/libasan.so.6+0xb2027)
19:     #1 0x47f99d in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::split(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, int, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:368
19:     #2 0x46ff9f in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::rebalance_or_split(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, int, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:516
19:     #3 0x490e4b in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::insert_inner(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, unsigned int, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, int const&, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:604
19:     #4 0x48a8e2 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::grow_parent(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:568
19:     #5 0x47fdc8 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::split(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, int, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:399
19:     #6 0x46ff9f in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::rebalance_or_split(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, int, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:516
19:     #7 0x4578b6 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::insert(int const&, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::btree_operation_hints<1u>&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1393
19:     #8 0x4475da in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::insert(int const&) /home/brody/tmp/tmp.CLNCss5bCn/src/include/souffle/datastructure/BTreeDelete.h:1170
19:     #9 0x4150c0 in souffle::test::test_BTreeDelete_EraseStress::run() /home/brody/tmp/tmp.CLNCss5bCn/src/tests/btree_delete_test.cpp:356
19:     #10 0x403a2a in main /home/brody/tmp/tmp.CLNCss5bCn/src/tests/test.h:250
19:     #11 0x7f7fd68f6081 in __libc_start_main (/lib64/libc.so.6+0x27081)
19: 
19: SUMMARY: AddressSanitizer: new-delete-type-mismatch (/lib64/libasan.so.6+0xb308f) in operator delete(void*, unsigned long)
19: ==506732==HINT: if you don't care about these errors you may set ASAN_OPTIONS=new_delete_type_mismatch=0
19: ==506732==ABORTING
Failed
  • And for Valgrind:
==2310542== HEAP SUMMARY:
==2310542==     in use at exit: 5,800 bytes in 12 blocks
==2310542==   total heap usage: 3,471,378 allocs, 3,471,366 frees, 867,906,847 bytes allocated
==2310542== 
==2310542== LEAK SUMMARY:
==2310542==    definitely lost: 0 bytes in 0 blocks
==2310542==    indirectly lost: 0 bytes in 0 blocks
==2310542==      possibly lost: 2,128 bytes in 7 blocks
==2310542==    still reachable: 3,672 bytes in 5 blocks
==2310542==         suppressed: 0 bytes in 0 blocks
==2310542== Rerun with --leak-check=full to see details of leaked memory
@brofranks brofranks added the bug - triage Bugs with unknown causes that require further investigation label Nov 16, 2021
@brofranks
Copy link
Member Author

Adding a virtual destructor to struct node was able to fix the issue but there is now a new, possibly worse, heap-use-after-free issue. See below:

19: =================================================================
19: ==2350799==ERROR: AddressSanitizer: heap-use-after-free on address 0x60400018e1f1 at pc 0x55f06c3e87fa bp 0x7ffc864d8620 sp 0x7ffc864d8610
19: READ of size 1 at 0x60400018e1f1 thread T0
19:     #0 0x55f06c3e87f9 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::base::isInner() const /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:149
19:     #1 0x55f06c3e942d in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator::operator++() /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:983
19:     #2 0x55f06c3fcfbf in bool std::__equal<false>::equal<std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator>(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator) /usr/include/c++/10/bits/stl_algobase.h:1106
19:     #3 0x55f06c3ec216 in bool std::__equal_aux1<std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator>(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator) /usr/include/c++/10/bits/stl_algobase.h:1156
19:     #4 0x55f06c3d1d59 in bool std::__equal_aux<std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator>(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator) /usr/include/c++/10/bits/stl_algobase.h:1164
19:     #5 0x55f06c3bf31a in bool std::equal<std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator>(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator) /usr/include/c++/10/bits/stl_algobase.h:1414
19:     #6 0x55f06c38a763 in souffle::test::test_BTreeDelete_EraseStress::run() /home/brody/tmp/tmp.XHF9Uq6KHd/src/tests/btree_delete_test.cpp:372
19:     #7 0x55f06c378074 in main /home/brody/tmp/tmp.XHF9Uq6KHd/src/tests/test.h:250
19:     #8 0x7f4608dadcb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
19:     #9 0x55f06c377ced in _start (/home/brody/tmp/tmp.XHF9Uq6KHd/cmake-build-debug-sanitizer/src/tests/test_btree_delete+0xdced)
19: 
19: 0x60400018e1f1 is located 33 bytes inside of 48-byte region [0x60400018e1d0,0x60400018e200)
19: freed by thread T0 here:
19:     #0 0x7f46093d3f8f in operator delete(void*, unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:172
19:     #1 0x55f06c3cdbaa in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::leaf_node::~leaf_node() /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:898
19:     #2 0x55f06c3e852e in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::inner_node::~inner_node() /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:885
19:     #3 0x55f06c3e85ff in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::inner_node::~inner_node() /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:891
19:     #4 0x55f06c406769 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::merge(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1915
19:     #5 0x55f06c3f9adc in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::merge_with_right_sibling(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator&, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1852
19:     #6 0x55f06c3e8dc1 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::merge_or_rebalance(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1813
19:     #7 0x55f06c3cec76 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::erase(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::iterator&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1674
19:     #8 0x55f06c3bec35 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::erase(int const&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1604
19:     #9 0x55f06c38a6b1 in souffle::test::test_BTreeDelete_EraseStress::run() /home/brody/tmp/tmp.XHF9Uq6KHd/src/tests/btree_delete_test.cpp:370
19:     #10 0x55f06c378074 in main /home/brody/tmp/tmp.XHF9Uq6KHd/src/tests/test.h:250
19:     #11 0x7f4608dadcb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
19: 
19: previously allocated by thread T0 here:
19:     #0 0x7f46093d2f27 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:99
19:     #1 0x55f06c3fbab0 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::split(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, int, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:369
19:     #2 0x55f06c3eab35 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node::rebalance_or_split(souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node**, souffle::OptimisticReadWriteLock&, int, std::vector<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*, std::allocator<souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::node*> >&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:516
19:     #3 0x55f06c3d086a in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::insert(int const&, souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::btree_operation_hints<1u>&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1395
19:     #4 0x55f06c3bee0c in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::insert(int const&) /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:1172
19:     #5 0x55f06c38a089 in souffle::test::test_BTreeDelete_EraseStress::run() /home/brody/tmp/tmp.XHF9Uq6KHd/src/tests/btree_delete_test.cpp:356
19:     #6 0x55f06c378074 in main /home/brody/tmp/tmp.XHF9Uq6KHd/src/tests/test.h:250
19:     #7 0x7f4608dadcb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
19: 
19: SUMMARY: AddressSanitizer: heap-use-after-free /home/brody/tmp/tmp.XHF9Uq6KHd/src/include/souffle/datastructure/BTreeDelete.h:149 in souffle::detail::btree_delete<int, souffle::detail::comparator<int>, std::allocator<int>, 2u, souffle::detail::linear_search, true, souffle::detail::comparator<int>, souffle::detail::updater<int> >::base::isInner() const
19: Shadow bytes around the buggy address:
19:   0x0c0880029be0: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
19:   0x0c0880029bf0: fa fa 00 00 00 00 00 fa fa fa fd fd fd fd fd fa
19:   0x0c0880029c00: fa fa fd fd fd fd fd fa fa fa 00 00 00 00 00 fa
19:   0x0c0880029c10: fa fa 00 00 00 00 00 fa fa fa fd fd fd fd fd fa
19:   0x0c0880029c20: fa fa 00 00 00 00 00 fa fa fa 00 00 00 00 00 00
19: =>0x0c0880029c30: fa fa fd fd fd fd fd fd fa fa fd fd fd fd[fd]fd
19:   0x0c0880029c40: fa fa fd fd fd fd fd fd fa fa fd fd fd fd fd fd
19:   0x0c0880029c50: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fd
19:   0x0c0880029c60: fa fa 00 00 00 00 00 fa fa fa fd fd fd fd fd fa
19:   0x0c0880029c70: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 fa
19:   0x0c0880029c80: fa fa fd fd fd fd fd fa fa fa 00 00 00 00 00 fa
19: Shadow byte legend (one shadow byte represents 8 application bytes):
19:   Addressable:           00
19:   Partially addressable: 01 02 03 04 05 06 07 
19:   Heap left redzone:       fa
19:   Freed heap region:       fd
19:   Stack left redzone:      f1
19:   Stack mid redzone:       f2
19:   Stack right redzone:     f3
19:   Stack after return:      f5
19:   Stack use after scope:   f8
19:   Global redzone:          f9
19:   Global init order:       f6
19:   Poisoned by user:        f7
19:   Container overflow:      fc
19:   Array cookie:            ac
19:   Intra object redzone:    bb
19:   ASan internal:           fe
19:   Left alloca redzone:     ca
19:   Right alloca redzone:    cb
19:   Shadow gap:              cc
19: ==2350799==ABORTING

brofranks added a commit to brofranks/souffle-dev that referenced this issue Nov 17, 2021
@brofranks
Add a virtual destructor for BTreeDelete node to fix new-delete-type-…
93d931e 
…mismatch souffle-lang#2127
@brofranks brofranks mentioned this issue Nov 17, 2021
Closed
@julienhenry julienhenry mentioned this issue Jun 17, 2022
Merged
b-scholz pushed a commit that referenced this issue Aug 5, 2022
Merge pull request #2287 from julienhenry/fix-btree-destructor
66b96fd 
fix btree destructors #2127
@quentin quentin closed this as completed Nov 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug - triage Bugs with unknown causes that require further investigation
Projects
None yet
Milestone
No milestone
2 participants
@quentin @brofranks