debug container mutex association

[François Dumont]

On 14/09/2016 11:00, Jonathan Wakely wrote:
> On 13/09/16 22:37 +0200, François Dumont wrote:
>> Hi
>>
>>    When I proposed to change std::hash for pointers my plan was to 
>> use this approach for the debug containers. So here is the patch 
>> leveraging on this technique to avoid going through _Hash_impl to 
>> hash address and get mutex index from it. I think it is obious that 
>> new access is faster so I didn't wrote a performance test to 
>> demonstrate it.
>
> Is this actually a bottleneck that needs to be made faster?
>
> I know it's nice if Debug Mode isn't very slow, but you've already
> made it much better, and performance is not the primary goal of Debug
> Mode.

Sure but my approach is that if I can make something faster then I just 
try. I considered that making this mode faster will allow its usage in 
an even more extended way.

>
>> diff --git a/libstdc++-v3/config/abi/pre/gnu.ver 
>> b/libstdc++-v3/config/abi/pre/gnu.ver
>> index 9b5bb23..c9a253e 100644
>> --- a/libstdc++-v3/config/abi/pre/gnu.ver
>> +++ b/libstdc++-v3/config/abi/pre/gnu.ver
>> @@ -1947,6 +1947,21 @@ GLIBCXX_3.4.23 {
>>     _ZNSsC[12]ERKSs[jmy]RKSaIcE;
>>     _ZNSbIwSt11char_traitsIwESaIwEEC[12]ERKS2_mRKS1_;
>>
>> +    # __gnu_debug::_Safe_sequence_base
>> + _ZN11__gnu_debug19_Safe_sequence_base18_M_detach_singularEm;
>
> The 'm' here should be [jmy] because std::size_t mangles differently
> on different targets.
>
>> + _ZN11__gnu_debug19_Safe_sequence_base22_M_revalidate_singularEm;
>> +    _ZN11__gnu_debug19_Safe_sequence_base12_M_get_mutexEm;
>> +    _ZN11__gnu_debug19_Safe_sequence_base7_M_swapERS0_m;
>> +
>> +    # __gnu_debug::_Safe_iterator_base
>> + 
>> _ZN11__gnu_debug19_Safe_iterator_base9_M_attachEPNS_19_Safe_sequence_baseEbm;
>> +    _ZN11__gnu_debug19_Safe_iterator_base9_M_detachEm;
>> +
>> +    # __gnu_debug::_Safe_unordered_container_base and 
>> _Safe_local_iterator_base
>> + _ZN11__gnu_debug30_Safe_unordered_container_base7_M_swapERS0_m;
>> + 
>> _ZN11__gnu_debug25_Safe_local_iterator_base9_M_attachEPNS_19_Safe_sequence_baseEbm;
>> +    _ZN11__gnu_debug25_Safe_local_iterator_base9_M_detachEm;
>> +
>> } GLIBCXX_3.4.22;
>
> It's unfortunate to have to export and maintain new symbols when we
> don't offer the same level of ABI guarantee for Debug Mode  :-(

Yes, I have been told that Debug ABI compatibility was not guaranteed 
but at the same time if we don't do so abi-check is failing. Couldn't we 
have a special section in gnu.ver for unversioned symbols like those ?

>
>> @@ -174,6 +191,18 @@ namespace __gnu_debug
>>             const _Safe_iterator_base* __last)
>>   { return __first->_M_can_compare(*__last); }
>>
>> +  // Compute power of 2 not greater than __n.
>> +  template<size_t __n>
>> +    struct _Lowest_power_of_two
>> +    {
>> +      static const size_t __val
>> +        = _Lowest_power_of_two< (__n >> 1) >::__val + 1;
>> +    };
>> +
>> +  template<>
>> +    struct _Lowest_power_of_two<1>
>> +    { static const size_t __val = 1; };
>
> The lowest power of two not greater than 1 is 2^0, but this gives the
> result 1.
>
> Similarly, the lowest power of two not greater than 2 is 2^1, i.e. 1.

Indeed, when writing the test case I decided to return 1 rather than 0 
for the _Lowest_power_of_two<1> specialization.It gave a better 
container instance - mutex mapping. But I forgot to change its name.

>
> And the name is misleading, it doesn't compute a power of two, it
> computes the base-2 logarithm (then adds one), so it's a compile-time
> version of floor(log2(n))+1.
>
>> @@ -123,6 +125,36 @@ namespace __gnu_debug
>>       template<typename _Predicate>
>>     void
>>     _M_transfer_from_if(_Safe_sequence& __from, _Predicate __pred);
>> +
>> +      static _GLIBCXX_CONSTEXPR std::size_t
>> +      _S_alignment() _GLIBCXX_NOEXCEPT
>> +      { return _Lowest_power_of_two<__alignof(_Sequence)>::__val; }
>
> This function is called "alignment" but it returns log2(alignof(T))+1

Yes, I wasn't proud about the naming.

>
> Does it need to be constexpr? Is that for std::array?

No, it is not used in std::array context. I just considered that it 
could be constexpr.

>
> You can get the same result without _Lowest_power_of_two:
>
>  static _GLIBCXX_CONSTEXPR size_t
>  _S_alignbits() _GLIBCXX_NOEXCEPT
>  { return __builtin_ctz(__alignof(_Sequence)) + 1; }
>
> But I'm not convinced the +1 is correct, see below.
>
>> @@ -46,15 +47,30 @@ namespace
>>   /** Returns different instances of __mutex depending on the passed 
>> address
>>    *  in order to limit contention without breaking current library 
>> binary
>>    *  compatibility. */
>> +  const size_t mask = 0xf;
>> +
>>   __gnu_cxx::__mutex&
>> -  get_safe_base_mutex(void* __address)
>> +  get_mutex(size_t index)
>>   {
>> -    const size_t mask = 0xf;
>>     static __gnu_cxx::__mutex safe_base_mutex[mask + 1];
>> -    const size_t index = _Hash_impl::hash(__address) & mask;
>>     return safe_base_mutex[index];
>>   }
>
> N.B. https://gcc.gnu.org/PR71312
Ok, debug mode is also impacted. Shouldn't the alignment be set on the 
__mutex type directly ?
>
>
>>
>> +  __gnu_cxx::__mutex&
>> +  get_safe_base_mutex(void* address)
>> +  {
>> +    const size_t index = _Hash_impl::hash(address) & mask;
>> +    return get_mutex(index);
>> +  }
>> +
>> +  __gnu_cxx::__mutex&
>> +  get_safe_base_mutex(void* address, std::size_t alignment)
>> +  {
>> +    const size_t index
>> +      = (reinterpret_cast<size_t>(address) >> alignment) & mask;
>> +    return get_mutex(index);
>> +  }
>
> Since the "alignment" value (which is really log2(align)+1) is always
> a positive value that means we always shift the address. But that
> means we drop the least significant bit of all pointers, even when the
> type has alignof(T)==1 and so all bits in the pointer are significant.
> Is that intentional? Is the idea to only drop bits that are always
> zero?

Yes, to make sure we get use of all available mutexes.

>
> By changing the algorithm we use to map an address to a mutex do we
> allow programs to get two different mutexes for the same object? That
> can only happen when some objects are compiled with an older GCC and
> so still use the old _M_get_mutex() function that doesn't take an
> argument. We require all objects to be rebuilt with the same compiler
> for Debug Mode (but maybe not if using __gnu_debug::vector etc.
> explicitly in normal mode?) so that's not a big deal. But it's a pity
> we have to keep the old symbols around if using them is unsafe.

Yes, it could happen even if very unlikely. I would also prefer to get 
rid of former symbols but can we ?

>
>>   void
>>   swap_its(__gnu_debug::_Safe_sequence_base& __lhs,
>>        __gnu_debug::_Safe_iterator_base*& __lhs_its,
>> @@ -70,8 +86,8 @@ namespace
>>   }
>>
>>   void
>> -  swap_seq(__gnu_debug::_Safe_sequence_base& __lhs,
>> -       __gnu_debug::_Safe_sequence_base& __rhs)
>> +  swap_seq_single(__gnu_debug::_Safe_sequence_base& __lhs,
>> +          __gnu_debug::_Safe_sequence_base& __rhs)
>>   {
>>     swap(__lhs._M_version, __rhs._M_version);
>>     swap_its(__lhs, __lhs._M_iterators,
>> @@ -81,10 +97,41 @@ namespace
>>   }
>>
>>   void
>> -  swap_ucont(__gnu_debug::_Safe_unordered_container_base& __lhs,
>> -        __gnu_debug::_Safe_unordered_container_base& __rhs)
>> +  lock_and_run(__gnu_cxx::__mutex& lhs_mutex,
>> +           __gnu_cxx::__mutex& rhs_mutex,
>> +           std::function<void()> action)
>
> Do all calls to this fit into the std::function small-object buffer,
> so we don't need to allocate memory for it?
>
I didn't consider this. I thought it was a nice way to avoid making 
lock_and_run a template function to take the lambda.

Reading this I realize that we could perhaps acheive the same without 
touching as much code. __alignof of container types will always give the 
same value on a give target no ? Does it depends on the type used to 
instantiate the container ? Isn't there some macro giving the target 
alignment that I could use ?

François