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-08 16:40:48

Hi again,

I checked out the develop branches of intrusive and interprocess and set to
calling check() in loads of places. I get an error that I think I that I've
narrowed down to occurring in rbtree_best_fit::priv_deallocate

Here is a snippet, with all of my check calls added.

   m_header.m_imultiset.check();

   //Merge logic. First just update block sizes, then fix free blocks tree
   if(merge_with_prev || merge_with_next){
      //Merge if the previous is free
      if(merge_with_prev){
          m_header.m_imultiset.check();
         //Get the previous block
         block_ctrl *prev_block = priv_prev_block(block);
         m_header.m_imultiset.check();
         prev_block->m_size += block->m_size;
*         m_header.m_imultiset.check();  //this check fails!*
         BOOST_ASSERT(prev_block->m_size >= BlockCtrlUnits);
         m_header.m_imultiset.check();
         block_to_insert = prev_block;
      }
      m_header.m_imultiset.check();
      //Merge if the next is free

Now, to be honest, I found it a bit surprising to find the multiset
invariants being invalidated by an addition, but what do I know... Does
this make any sense at all?

Cheers
Lars

On Sun, Sep 7, 2014 at 11:03 PM, Lars Hagström <lars_at_[hidden]> wrote:

> I managed to get something to go wrong in Debug mode too (no idea if its
> the same problem, though). An assertion triggered:
>
> dots_configuration_check:
> /usr/include/boost/interprocess/mem_algo/rbtree_best_fit.hpp:1347: 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 `priv_is_allocated_block(block)' failed.
>
> I've also got a rather lengthy call stack for you:
>
> #0  0x00007ffff5b14d67 in raise () from /usr/lib/libc.so.6
> #1  0x00007ffff5b16118 in abort () from /usr/lib/libc.so.6
> #2  0x00007ffff5b0dbdd in __assert_fail_base () from /usr/lib/libc.so.6
> #3  0x00007ffff5b0dc92 in __assert_fail () from /usr/lib/libc.so.6
> #4  0x00007ffff74bd246 in
> boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
> boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>,
> 0ul>::priv_deallocate (this=0x7ffff2065010, addr=0x7ffff20b4240) at
> /usr/include/boost/interprocess/mem_algo/rbtree_best_fit.hpp:1347
> #5  0x00007ffff74bbbf7 in
> boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
> boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>,
> 0ul>::deallocate (this=0x7ffff2065010, addr=0x7ffff20b4240) at
> /usr/include/boost/interprocess/mem_algo/rbtree_best_fit.hpp:1336
> #6  0x00007ffff74b9def 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=0x7ffff2065010, addr=0x7ffff20b4240) at
> /usr/include/boost/interprocess/segment_manager.hpp:225
> #7  0x00007ffff74b80f5 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=0x7ffff20b55f8,
> ptr=...) at /usr/include/boost/interprocess/allocators/allocator.hpp:157
> #8  0x00007ffff74b6e1a 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=0x7ffff20b55f8, __in_chrg=<optimized out>) at
> /usr/include/boost/container/vector.hpp:332
> #9  0x00007ffff74b5d44 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=0x7ffff20b55f8,
> __in_chrg=<optimized out>) at /usr/include/boost/container/vector.hpp:790
> #10 0x00007ffff74bbdde in
> Safir::Dob::Typesystem::Internal::MemberMappingDescriptionShm::~MemberMappingDescriptionShm
> (this=0x7ffff20b55f0, __in_chrg=<optimized out>) at
> /home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_shm_repository.h:341
> #11 0x00007ffff74bbe38 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=0x7fffffffdd10, ptr=...)
> at /usr/include/boost/interprocess/allocators/allocator.hpp:268
> #12 0x00007ffff74b9f7c 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=0x7ffff20b55f0) at
> /usr/include/boost/container/allocator_traits.hpp:300
> #13 0x00007ffff74b8212 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=0x7ffff20b55f0) at
> /usr/include/boost/container/allocator_traits.hpp:242
> #14 0x00007ffff7555d13 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=0x7fffffffd4c0, __in_chrg=<optimized out>) at
> /usr/include/boost/container/detail/destroyers.hpp:207
> #15 0x00007ffff754cd1e 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=0x7fffffffdd10, new_start=0x7ffff20b5500, new_capacity=8,
> pos=0x7ffff20b5680, n=1, insert_range_proxy=...) at
> /usr/include/boost/container/vector.hpp:2697
> #16 0x00007ffff754415d 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=0x7fffffffdd10, pos=..., n=1, insert_range_proxy=...) at
> /usr/include/boost/container/vector.hpp:2024
> #17 0x00007ffff7540905 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=0x7fffffffdd10, u=...) at /usr/include/boost/container/vector.hpp:1885
> #18 0x00007ffff753e2f9 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=0x7fffffffdd10, u=...) at /usr/include/boost/container/vector.hpp:1424
> #19 0x00007ffff753d19d in
> Safir::Dob::Typesystem::Internal::PropertyMappingDescriptionShm::AddMemberMapping
> (this=0x7fffffffdce0, mmShm=...) at
> /home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_shm_repository.h:445
> #20 0x00007ffff753afbf 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 0x00007ffff74b3325 in
> Safir::Dob::Typesystem::Internal::RepositoryKeeper::Create
> (this=0x7ffff77d2940
> <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 0x00007ffff53cad4e in
> Safir::Utilities::StartupSynchronizerImpl::FirstStart (this=0x648860,
> synchronized=0x7ffff77d2940
> <Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
> at
> /home/lars/safir_sdk_core/src/lluf/lluf_startup_synchronizer.ss/src/StartupSynchronizer.cpp:181
> #23 0x00007ffff53cab86 in Safir::Utilities::StartupSynchronizerImpl::Start
> (this=0x648860, synchronized=0x7ffff77d2940
> <Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
> at
> /home/lars/safir_sdk_core/src/lluf/lluf_startup_synchronizer.ss/src/StartupSynchronizer.cpp:154
> #24 0x00007ffff53c7eca in Safir::Utilities::StartupSynchronizer::Start
> (this=0x7ffff77d2948
> <Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance+8>,
> synchronized=0x7ffff77d2940
> <Safir::Dob::Typesystem::Internal::RepositoryKeeper::Instance()::instance>)
> at
> /home/lars/safir_sdk_core/src/lluf/lluf_startup_synchronizer.ss/src/StartupSynchronizer.cpp:423
> #25 0x00007ffff74b2c2b 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 0x00007ffff74d8deb 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 0x00007ffff74db5c3 in boost::call_once<void (*)()> (flag=...,
> f=0x7ffff74d8da1 <Safir::Dob::Typesystem::Internal::InitHelper::Init()>) at
> /usr/include/boost/thread/pthread/once_atomic.hpp:149
> #28 0x00007ffff74d9362 in Safir::Dob::Typesystem::Internal::Init () at
> /home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_init_helper.h:106
> #29 0x00007ffff74cd391 in DotsC_NumberOfTypeIds () at
> /home/lars/safir_sdk_core/src/dots/dots_kernel.ss/src/dots_kernel.cpp:123
> #30 0x0000000000419b5d in CheckConfigurationDotsKernel::SimpleCheck () at
> /home/lars/safir_sdk_core/src/dots/dots_configuration_check.ss/src/dots_configuration_check.cpp:108
> #31 0x0000000000419b36 in CheckConfigurationDotsKernel::Run (cmd=...) at
> /home/lars/safir_sdk_core/src/dots/dots_configuration_check.ss/src/dots_configuration_check.cpp:99
> #32 0x000000000041426a in main (argc=1, argv=0x7fffffffe6a8) at
> /home/lars/safir_sdk_core/src/dots/dots_configuration_check.ss/src/dots_configuration_check.cpp:235
> (gdb)
>
> Could this be the same issue?
>
> /Lars
>
> On Sun, Sep 7, 2014 at 7:38 PM, Lars Hagström <lars_at_[hidden]> wrote:
>
>> Yeah, I think that seems a likely explanation.
>> I'm not sure that I'll be able to produce something minimal that exhibits
>> the problem. But the product I'm working on is open source, and the problem
>> occurs during the build process of the code, so depending on your
>> environment it should be fairly easy to replicate.
>>
>> But before we go down that path I'll have a look at it and see if I can
>> find anything. Is there anything special that I should look at?
>>
>> /Lars
>>
>> On Sun, Sep 7, 2014 at 11:24 AM, Ion Gaztañaga <igaztanaga_at_[hidden]>
>> wrote:
>>
>>> El 06/09/2014 22:09, Lars Hagström escribió:
>>>
>>>> Hi,
>>>>
>>>> I've just upgraded to boost 1.56 and I've run into a problem. I get an
>>>> infinite loop inside insert_equal_lower_bound_check(...) in
>>>> bstree_algorithms.hpp.
>>>> I'm using that file indirectly through Boost.Interprocess.
>>>>
>>>> I've not been able to penetrate exactly what that function does or
>>>> whether
>>>> there is indeed a bug in it. But I did look at the version that was in
>>>> 1.55
>>>> (called insert_equal_check_impl(...) there), and to me it looks like
>>>> there
>>>> is at least one unexpected change:
>>>>
>>>
>>> I think the bug might be earlier, it seems that tree invariants were
>>> somehow broken and effects appear later in this function.
>>>
>>> Any chance to get a test case with the problem?
>>>
>>> Best,
>>>
>>> Ion
>>>
>>> _______________________________________________
>>> Unsubscribe & other changes: http://lists.boost.org/
>>> mailman/listinfo.cgi/boost
>>>
>>
>>
>