segfault with resize, deleted_key and value_type of boost::shared_ptr

[Andrew King]

Hi, I am getting a random segfault with google::dense_hash_map and I am wondering what the problem is ...

I am using the release 0.4

my class definition ...

    typedef google::dense_hash_map<
        int,
        boost::shared_ptr<MyClass>,
        boost::hash<int>
        > MyClassMap;

MyClass just stores lots of things by value inside boost::tuples, and a pointer to another class (although this is not deleted in any destructor).

I use myClassMap.set_empty_key(-1);
and myClassMap.set_deleted_key(-2);

I go through and delete the values quite commonly.

The values are always inserted with an ascending key (eg. ++key);

After the program has been running for a long time, I get a crash on doing an insert ...

the call stack looks like this ...

#10 0x085e1bfe in ~shared_ptr (this=0xec7b1238) at
#11 0x085e1c2a in ~pair (this=0xec7b1234) at
#12 0x085e3d82 in google::dense_hashtable<std::pair<int const, boost::shared_ptr<MyClass> >, int, boost::hash<int>, google::dense_hash_map<int, boost::shared_ptr<MyClass>, boost::hash<int>, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::SelectKey, std::equal_to<int>, std::allocator<boost::shared_ptr<<MyClass> > >::destroy_buckets (this=0xffffc520,
    first=61, last=64)
    at sparsehash-0.4/src/google/sparsehash/densehashtable.h:293
#13 0x085e1da7 in ~dense_hashtable (this=0xffffc520)
    at sparsehash-0.4/src/google/sparsehash/densehashtable.h:583
#14 0x085e7243 in google::dense_hashtable<std::pair<int const, boost::shared_ptr<MyClass> >, int, boost::hash<int>, google::dense_hash_map<int, boost::shared_ptr<Tibra::Reflex::MyClass>, boost::hash<int>, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::SelectKey, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::maybe_shrink (this=0xf4f1ba08)
    at sparsehash-0.4/src/google/sparsehash/densehashtable.h:446
#15 0x085e5951 in google::dense_hashtable<std::pair<int const, boost::shared_ptr<MyClass> >, int, boost::hash<int>, google::dense_hash_map<int, boost::shared_ptr<MyClass>, boost::hash<int>, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::SelectKey, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::resize_delta (this=0xf4f1ba08,
    delta=1, min_buckets_wanted=0)
    at sparsehash-0.4/src/google/sparsehash/densehashtable.h:455
#16 0x085e47a7 in google::dense_hashtable<std::pair<int const, boost::shared_ptr<MyClass> >, int, boost::hash<int>, google::dense_hash_map<int, boost::shared_ptr<Tibra::Reflex::MyClass>, boost::hash<int>, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::SelectKey, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::insert (this=0xf4f1ba08,
    obj=@0xffffc6b0)
    at sparsehash-0.4/src/google/sparsehash/densehashtable.h:724
#17 0x085e29b2 in google::dense_hash_map<int, boost::shared_ptr<MyClass>, boost::hash<int>, std::equal_to<int>, std::allocator<boost::shared_ptr<MyClass> > >::insert (this=0xf4f1ba08,
    obj=@0xffffc6b0) at sparsehash-0.4/src/google/dense_hash_map:201


destroy_buckets looks like it goes through and calls destructors manually on each item being moved. I don't think boost::shared_ptr's like their destructors being called? The object with the destructor being called should already have been deleted?

Can anyone see the problem with what I am doing? Is it possible to resize a google::dense_hash_map with value_type of boost::shared_ptr<T> correctly with items that have previously been deleted?

Cheers,
Andrew

[Craig Silverstein]

I believe your problem is that shared_ptr<> is not a Plain Old Data
type. For dense_hash_map, both the key and value must be POD.

craig

[Andrew King]

The changelog for version 0.4 says:

* Remove POD requirement for keys and values! (austern)

Is this not actually true?

Cheers,
Andrew

[Craig Silverstein]

} * Remove POD requirement for keys and values! (austern)

Ahem, *mumble* I had forgotten about that. You're absolutely right.

Looking at the stack trace, it looks like the problem is with the
interaction between dense_hash_map and shared_ptr. I don't know
anything about boost, but it may not be safe to use in the way you're
using it. Can you copy shared_ptr's around, and delete the old one,
and have everything be ok?

The crash is happening at resize time: we're copying all the stuff
from the old hashtable to a new, bigger one, and then deleting the old
one. That's where the crash is happening. Does copying a shared_ptr
transfer ownership or something, so that deleting the old one is no
longer safe?

I'm not saying the problem is with the hashtable code, but the use of
boost as the value type -- especially given the fact the boost
destructor is what is triggering the crash -- does make it a bit hard
to disentangle the possible causes.

Would it be possible to rejigger your application so it uses something
other than a shared_ptr, to see if it causes the same problems?

Alternately, you can just run this through gdb and see what this looks
like during ~shared_ptr. Maybe there will be obvious corruption, or
something else that points what might be going wrong.

craig

[Craig Silverstein]

} I'm not saying the problem is with the hashtable code, but the use
} of

I meant, I'm not saying the problem is *not* with the hashtable code.
Too many negatives.

If you can't debug this, and are open to making the source available,
maybe you can put it up somewhere so we can try to reproduce the
problem here.

craig

[Wes Chow]

Some of these pointer values look fishy to me.. the one starting with
0xffff in frame #17 particular (and #13). Are you sure there isn't some
sort of memory corruption going on in another part of the program?

> destroy_buckets looks like it goes through and calls destructors
> manually on each item being moved. I don't think boost::shared_ptr's
> like their destructors being called? The object with the destructor
> being called should already have been deleted?

This should be ok as long as the destructor is only called once (ie, we
don't call both the destructor and then delete to free up the memory).

> Can anyone see the problem with what I am doing? Is it possible to
> resize a google::dense_hash_map with value_type of boost::shared_ptr<T>
> correctly with items that have previously been deleted?

It works in my simple test code, and I'm sure that we have a more
complicated setup like yours somewhere in our production code which runs
fine. (or maybe we're in for a nasty surprise soon!)

Wes

[Craig Silverstein]

} Some of these pointer values look fishy to me.. the one starting
} with 0xffff in frame #17 particular (and #13). Are you sure there
} isn't some sort of memory corruption going on in another part of the
} program?

These are stack-allocated objects. The one in #13 is expected: we
grow the hasthable by creating a new one on the stack as scratch
space, and it's the one getting destroyed.

In #17, it looks like the insert that's being done is of a
stack-allocated object as well. That should be fine; I don't think
that would cause any problems.

craig

[Andrew King]

I have done a bit more unit testing of the particular piece of code in
question, and can't get it to segfault, despite doing all possible
combinations of operations. Seems like there is memory corruption
somewhere else ...