Re: [boost] [intrusive] Possible bug in bstree_algorithms.hpp

Subject: Re: [boost] [intrusive] Possible bug in bstree_algorithms.hpp
From: Lars Hagström (lars_at_[hidden])
Date: 2014-09-15 09:29:17

>
> I realized that once the size of a inserted block is modified tree
> invariants might be broken because imultiset is ordered by size. Tree
> invariants should be checked before the end of the function, after
> m_imultiset is fixed with erase+insert or replace, when tree invariants
> should have been restored. Maybe the code is confusing but the idea is to
> avoid removing (and rebalancing) the tree if it's not strictly needed. I
> guess code could be simplified to be more readable and maintainable (I've
> improved readability a bit in the last commits). Remove checks after size
> modification and add it at the end the function.
>
>
Okay, I'm glad I asked, before we got further down that avenue... So, back
to square one.
Anyway, I've now just got checks at the beginning and end of
priv_deallocate, and the checks do not fail. However, I did keep my logs in
priv_check_and_allocate and priv_deallocate, and from my logs it looks like
one block is deallocated twice. So my current theory is that there is
something in the intrusive vector that causes a double deallocation.
At the end of my email is the log and the call stack for this.

I could set up a VM on for example Digital Ocean and get everything up and
>> running, and give you the password and some instructions?
>>
>
> That would be quite efficient, yes ;-)
>

Okay, we'll do that then. What is your preferred development environment? I
was going to set up an Ubuntu box with boost from git. I can set up VNC
with some GUI, or I could just leave you with the command line :-)
I'd like to make this as easy as I can for you, since I do need the bug
fixed :-)

Here is the log from my test run. The assertion that fails is one that I
added, which checks that block is not in m_imultiset at the start of
priv_deallocate. If I remove that assert the
BOOST_ASSERT(priv_is_allocated_block(block)); will fail.
...
priv_deallocate: 0x7ffff20b17c0
Allocated priv_check_and_allocate = 0x7ffff20b18b0
Allocated priv_check_and_allocate = 0x7ffff20b17c0
Allocated priv_check_and_allocate = 0x7ffff20ac210
Allocated priv_check_and_allocate = *0x7ffff20ac240*
Allocated priv_check_and_allocate = 0x7ffff20ad4c0
priv_deallocate: 0x7ffff20ac210
Allocated priv_check_and_allocate = 0x7ffff20ac210
Allocated priv_check_and_allocate = 0x7ffff20ad4f0
Allocated priv_check_and_allocate = 0x7ffff20ad560
Allocated priv_check_and_allocate = 0x7ffff20ad590
priv_deallocate: 0x7ffff20ad4c0
priv_deallocate: *0x7ffff20ac240*
priv_deallocate: 0x7ffff20ac210
Allocated priv_check_and_allocate = 0x7ffff20ad4c0
Allocated priv_check_and_allocate = 0x7ffff20ad5c0
Allocated priv_check_and_allocate = 0x7ffff20ac210
Allocated priv_check_and_allocate = *0x7ffff20ac240*
Allocated priv_check_and_allocate = 0x7ffff20ad690
priv_deallocate: 0x7ffff20ad560
priv_deallocate: 0x7ffff20ad590
priv_deallocate: 0x7ffff20ad4f0
priv_deallocate: 0x7ffff20ad4c0
Allocated priv_check_and_allocate = 0x7ffff20ad6c0
Allocated priv_check_and_allocate = 0x7ffff20ad6f0
priv_deallocate: 0x7ffff20ad6c0
Allocated priv_check_and_allocate = 0x7ffff20ad6c0
Allocated priv_expand_both_sides = 0x7ffff20ad500
Allocated priv_check_and_allocate = 0x7ffff20ad720
Allocated priv_check_and_allocate = 0x7ffff20ad4c0
Allocated priv_check_and_allocate = 0x7ffff20ac3f0
Allocated priv_check_and_allocate = 0x7ffff20ac420
priv_deallocate: *0x7ffff20ac240*
priv_deallocate: *0x7ffff20ac240*
dots_configuration_check:
/home/lars/boost/modular-boost/boost/interprocess/mem_algo/rbtree_best_fit.hpp:1361:
void boost::interprocess::rbtree_best_fit<MutexFamily, VoidMutex,
MemAlignment>::priv_deallocate(void*) [with MutexFamily =
boost::interprocess::mutex_family; VoidPointer =
boost::interprocess::offset_ptr<void>; long unsigned int MemAlignment =
0ul]: Assertion `!found' failed.

And here is the backtrace:
(gdb) bt
#0  0x00007ffff5b0cd67 in raise () from /usr/lib/libc.so.6
#1  0x00007ffff5b0e118 in abort () from /usr/lib/libc.so.6
#2  0x00007ffff5b05bdd in __assert_fail_base () from /usr/lib/libc.so.6
#3  0x00007ffff5b05c92 in __assert_fail () from /usr/lib/libc.so.6
#4  0x00007ffff74b549e in
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>,
0ul>::priv_deallocate (this=0x7ffff205d010, addr=0x7ffff20ac240) at
/home/lars/boost/modular-boost/boost/interprocess/mem_algo/rbtree_best_fit.hpp:1361
#5  0x00007ffff74b3d65 in
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>,
0ul>::deallocate (this=0x7ffff205d010, addr=0x7ffff20ac240) at
/home/lars/boost/modular-boost/boost/interprocess/mem_algo/rbtree_best_fit.hpp:1337
#6  0x00007ffff74b1f09 in
boost::interprocess::segment_manager_base<boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>
>::deallocate (this=0x7ffff205d010, addr=0x7ffff20ac240) at
/home/lars/boost/modular-boost/boost/interprocess/segment_manager.hpp:225
#7  0x00007ffff74b0165 in boost::interprocess::allocator<int,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >::deallocate (this=0x7ffff20ad5f8,
ptr=...) at
/home/lars/boost/modular-boost/boost/interprocess/allocators/allocator.hpp:157
#8  0x00007ffff74aee8a in
boost::container::container_detail::vector_alloc_holder<boost::interprocess::allocator<int,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >,
boost::container::container_detail::integral_constant<unsigned int, 2u>
>::~vector_alloc_holder (this=0x7ffff20ad5f8, __in_chrg=<optimized out>) at
/home/lars/boost/modular-boost/boost/container/vector.hpp:332
#9  0x00007ffff74addb4 in boost::container::vector<int,
boost::interprocess::allocator<int,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> > >::~vector (this=0x7ffff20ad5f8,
__in_chrg=<optimized out>) at
/home/lars/boost/modular-boost/boost/container/vector.hpp:790
#10 0x00007ffff74b3f4c in
Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm::~MemberMappingDescriptionShm
(this=0x7ffff20ad5f0, __in_chrg=<optimized out>) at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_shm_repository.h:341
#11 0x00007ffff74b3fa6 in
boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >::destroy (this=0x7fffffffdc90, ptr=...)
at
/home/lars/boost/modular-boost/boost/interprocess/allocators/allocator.hpp:268
#12 0x00007ffff74b2096 in
boost::container::allocator_traits<boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >
>::priv_destroy<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm>
(a=..., p=0x7ffff20ad5f0) at
/home/lars/boost/modular-boost/boost/container/allocator_traits.hpp:300
#13 0x00007ffff74b0282 in
boost::container::allocator_traits<boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >
>::destroy<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm>
(a=..., p=0x7ffff20ad5f0) at
/home/lars/boost/modular-boost/boost/container/allocator_traits.hpp:242
#14 0x00007ffff754ef75 in
boost::container::container_detail::scoped_destructor_n<boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> > >::~scoped_destructor_n
(this=0x7fffffffd440, __in_chrg=<optimized out>) at
/home/lars/boost/modular-boost/boost/container/detail/destroyers.hpp:207
#15 0x00007ffff7545f80 in
boost::container::vector<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >
>::priv_forward_range_insert_expand_backwards<boost::container::container_detail::insert_copy_proxy<boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >,
Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm*> >
(this=0x7fffffffdc90, new_start=0x7ffff20ad500, new_capacity=8,
pos=0x7ffff20ad680, n=1, insert_range_proxy=...) at
/home/lars/boost/modular-boost/boost/container/vector.hpp:2697
#16 0x00007ffff753d3bf in
boost::container::vector<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >
>::priv_forward_range_insert_no_capacity<boost::container::container_detail::insert_copy_proxy<boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >,
Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm*> >
(this=0x7fffffffdc90, pos=..., n=1, insert_range_proxy=...) at
/home/lars/boost/modular-boost/boost/container/vector.hpp:2024
#17 0x00007ffff7539b67 in
boost::container::vector<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >
>::priv_push_back<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm>
(this=0x7fffffffdc90, u=...) at
/home/lars/boost/modular-boost/boost/container/vector.hpp:1885
#18 0x00007ffff753755b in
boost::container::vector<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::allocator<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm,
boost::interprocess::segment_manager<char,
boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>,
boost::interprocess::iset_index> >
>::push_back<Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm>
(this=0x7fffffffdc90, u=...) at
/home/lars/boost/modular-boost/boost/container/vector.hpp:1424
#19 0x00007ffff75363ff in
Safir::Dob::Typesystem::Internal::PropertyMappingDescriptionShm::AddMemberMapping
(this=0x7fffffffdc60, mmShm=...) at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_shm_repository.h:445
#20 0x00007ffff7534221 in
Safir::Dob::Typesystem::Internal::RepositoryShm::CreateShmCopyOfRepository
(srcRepository=..., shmRepositoryName="DOTS_REPOSITORY", sharedMemory=...)
at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_shm_repository.cpp:147
#21 0x00007ffff74ab395 in
Safir::Dob::Typesystem::Internal::RepositoryKeeper::Create
(this=0x7ffff77d2000
<Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_repository_keeper.cpp:172
#22 0x00007ffff53c2d7e in
Safir::Utilities::StartupSynchronizerImpl::FirstStart (this=0x648860,
synchronized=0x7ffff77d2000
<Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
at
/home/lars/safir_sdk_core/src/lluf/lluf_startup_synchronizer.ss/src/StartupSynchronizer.cpp:181
#23 0x00007ffff53c2bb6 in Safir::Utilities::StartupSynchronizerImpl::Start
(this=0x648860, synchronized=0x7ffff77d2000
<Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
at
/home/lars/safir_sdk_core/src/lluf/lluf_startup_synchronizer.ss/src/StartupSynchronizer.cpp:154
#24 0x00007ffff53bfefa in Safir::Utilities::StartupSynchronizer::Start
(this=0x7ffff77d2008
<Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance+8>,
synchronized=0x7ffff77d2000
<Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
at
/home/lars/safir_sdk_core/src/lluf/lluf_startup_synchronizer.ss/src/StartupSynchronizer.cpp:423
#25 0x00007ffff74aac9b in
Safir::Dob::Typesystem::Internal::RepositoryKeeper::Initialize
(sharedMemorySize=10485760, paths=std::vector of length 1, capacity 1 =
{...}) at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_repository_keeper.cpp:53
#26 0x00007ffff74d205f in
Safir::Dob::Typesystem::Internal::InitHelper::Init () at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_init_helper.h:60
#27 0x00007ffff74d4837 in boost::call_once<void (*)()> (flag=...,
f=0x7ffff74d2015 <Safir::Dob::Typesystem::Internal::InitHelper::Init()>) at
/home/lars/boost/modular-boost/boost/thread/pthread/once_atomic.hpp:149
#28 0x00007ffff74d25d6 in Safir::Dob::Typesystem::Internal::Init () at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_init_helper.h:106
#29 0x00007ffff74c6605 in DotsC_NumberOfTypeIds () at
/home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_kernel.cpp:123
#30 0x0000000000419b7d in CheckConfigurationDotsKernel::SimpleCheck () at
/home/lars/safir_sdk_core/src/dots/dots_configuration_check.ss/src/dots_configuration_check.cpp:108
#31 0x0000000000419b56 in CheckConfigurationDotsKernel::Run (cmd=...) at
/home/lars/safir_sdk_core/src/dots/dots_configuration_check.ss/src/dots_configuration_check.cpp:99
#32 0x000000000041428a in main (argc=1, argv=0x7fffffffe628) at
/home/lars/safir_sdk_core/src/dots/dots_configuration_check.ss/src/dots_configuration_check.cpp:235
(gdb)

I checked out scoped_destructor_n at #14, and m_n in there is in fact 2,
which means that AllocTraits::destroy(...) will be called twice.

/Lars