BwTree

BwTree copied to clipboard

I am probably doing something wrong here, but when I try to add a bunch of strongs to the BwTree I get a segfault. It behaves as expected with integers. Please forgive the C-like use of your class -- I'm much more of a C programmer than a C++ programmer.

using std::string;
 
#define MAX_WORD 512
int main(int argc, char **argv)
{
        /* usual thing: insert every word into the keyval */


        FILE *dict;
        char buffer[MAX_WORD];
        int count=0;
        wangziqi2013::bwtree::BwTree<string,int> tree;

        tree.UpdateThreadLocal(1);
        tree.AssignGCID(0);

        dict = fopen(argv[1], "r");

        while (fgets(buffer, MAX_WORD, dict) != NULL) {
                string s(buffer);
                tree.Insert(s, count++);
        }
}

It runs for a few iterations then eventually stops:

Insert                  (136C4A3765D49570): Leaf Insert delta CAS succeed
Insert                  (136C4A3765D49570): Insert called 
LoadNodeID              (136C4A3765D49570): Loading NodeID = 1
TakeNodeSnapshot        (136C4A3765D49570): Is leaf node? - 0 
Traverse                (136C4A3765D49570): Successfully loading root node ID
NavigateInnerNode       (136C4A3765D49570): Navigating inner node delta chain...
NavigateInnerNode       (136C4A3765D49570): Find target ID = 111 in insert delta
LoadNodeID              (136C4A3765D49570): Loading NodeID = 111
TakeNodeSnapshot        (136C4A3765D49570): Is leaf node? - 1
*** glibc detected *** ./simple: double free or corruption (fasttop): 0x0000000001949dc0 ***  

The core file is hairy, but I can post the full thing if you think it will be helpful. here are the first few frames:

#1  0x00002adf9a65ac75 in abort () from /lib64/libc.so.6
#2  0x00002adf9a6973a7 in __libc_message () from /lib64/libc.so.6
#3  0x00002adf9a69cdee in malloc_printerr () from /lib64/libc.so.6
#4  0x00002adf9a69fc3d in _int_free () from /lib64/libc.so.6
#5  0x0000000000404d12 in std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>::~pair() ()
    at /blues/gpfs/home/software/spack/opt/spack/linux-x86_64/gcc-5.3.0/gcc-6.1.0-q2zosj3igepi3pjnqt74bwazmptr5gpj/include/c++/6.1.0/bits/stl_pair.h:147
#6  0x000000000040cdbc in wangziqi2013::bwtree::BwTree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::less<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::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<int>, std::hash<int> >::ElasticNode<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> >::~ElasticNode() () at src/bwtree.h:2132
#7  0x000000000040a090 in wangziqi2013::bwtree::BwTree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::less<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::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<int>, std::hash<int> >::LeafNode::~LeafNode() () at src/bwtree.h:2468
#8  0x0000000000409304 in wangziqi2013::bwtree::BwTree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::less<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::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<int>, std::hash<int> >::EpochManager::FreeEpochDeltaChain(wangziqi2013::bwtree::BwTree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::less<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::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<int>, std::hash<int> >::BaseNode const*) ()
    at src/bwtree.h:8251
#9  0x0000000000407694 in wangziqi2013::bwtree::BwTree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::less<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::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<int>, std::hash<int> >::PerformGC(int) ()
    at src/bwtree.h:9436

@roblatham00 Looks like the GC has problem with freeing memory properly (or failed to initialize, imo). I will take a look into this issue.

Discussions on our end were wondering if I made a mistake by declaring the string inside the while loop. What does BwTree expect from the caller with respect to scope and lifetimes?

@roblatham00 The bug is not related to the scope of the string, but rather has something to do with the destructor. I have narrowed down the cause of the bug, and it seems to me that this happens at the first GC cycle, during the destructor call of a leaf base node.

I was traveling outside of the US recently and may not be able to response very quickly. My apology here. I will notify you once I resolve the GC problem.

BTW, the design goal is to fully support C++ object semantics, but there are implementation issues with that (e.g. BwTree moves Key/Value objects frequently compared with other indices, and therefore the usage of non-POD types as keys or values might suffer from performance loss).

We are bumping into this issue now that we are scaling up a bit. Any progress on this bug? Anything we can do to help debug? thanks.