Re: debug container mutex association

[Jonathan Wakely <jwakely at redhat dot com>]

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.

> 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  :-(

> @@ -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.

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

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

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

> +  __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?

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.

>   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?