On Thu, 28 Nov 2024 at 18:59, Jonathan Wakely <jwak...@redhat.com> wrote:
>
> The standard says that it's undefined to swap two containers if the
> allocators are not equal and do not propagate. This ensures that swap is
> always O(1) and non-throwing, but has other undesirable consequences
> such as LWG 2152. The 2016 paper P0178 ("Allocators and swap") proposed
> making the non-member swap handle non-equal allocators, by performing an
> O(n) deep copy when needed. This ensures that a.swap(b) is still O(1)
> and non-throwing, but swap(a, b) is valid for all values of the type.
>
> This change implements that for std::basic_stacktrace. The member swap
> is changed so that for the undefined case (where we can't swap the
> allocators, but can't swap storage separately from the allocators) we
> just return without changing either object. This ensures that with
> assertions disabled we don't separate allocated storage from the
> allocator that can free it.
>
> For the non-member swap, perform deep copies of the two ranges, avoiding
> reallocation if there is already sufficient capacity.
>
> libstdc++-v3/ChangeLog:
>
> * include/std/stacktrace (basic_stacktrace::swap): Refactor so
> that the undefined case is a no-op when assertions are disabled.
> (swap): Remove precondition and perform deep copies when member
> swap would be undefined.
> * testsuite/19_diagnostics/stacktrace/stacktrace.cc: Check
> swapping with unequal, non-propagating allocators.
> ---
>
> As part of my ongoing quest to reduce the undefined behaviour surface in
> the library, this helps to avoid UB when swapping stacktrace objects.
>
> This is an RFC to see if people like the idea. If we do it here, we
> could do it for other containers too.
>
> For the common case there should be no additional cost, because the
> 'if constexpr' conditions will be true and swap(a, b) will just call
> a.swap(b) unconditionally, which will swap the contents unconditionally.
> We only do extra work in the cases that are currently undefined.
>
> Tested x86_64-linux.
>
> libstdc++-v3/include/std/stacktrace | 77 ++++++++++++++++---
> .../19_diagnostics/stacktrace/stacktrace.cc | 23 ++++++
> 2 files changed, 90 insertions(+), 10 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/stacktrace
> b/libstdc++-v3/include/std/stacktrace
> index f94a424e4cf..ab0788cde08 100644
> --- a/libstdc++-v3/include/std/stacktrace
> +++ b/libstdc++-v3/include/std/stacktrace
> @@ -476,15 +476,79 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> }
>
> // [stacktrace.basic.mod], modifiers
> +
> + /** Exchange the contents of two stacktrace objects
> + *
> + * @pre The allocators must propagate on swap or must be equal.
> + */
> void
> swap(basic_stacktrace& __other) noexcept
> {
> - std::swap(_M_impl, __other._M_impl);
> if constexpr (_AllocTraits::propagate_on_container_swap::value)
> - std::swap(_M_alloc, __other._M_alloc);
> + {
> + using std::swap;
> + swap(_M_alloc, __other._M_alloc);
> + }
> else if constexpr (!_AllocTraits::is_always_equal::value)
> {
> - __glibcxx_assert(_M_alloc == __other._M_alloc);
> + if (_M_alloc != __other._M_alloc)
> + {
> + __glibcxx_assert(_M_alloc == __other._M_alloc);
> + // If assertions are disabled but the allocators are unequal,
> + // we can't swap pointers, so just erroneously return.
> + return;
> + }
> + }
> + std::swap(_M_impl, __other._M_impl);
> + }
> +
> + // [stacktrace.basic.nonmem], non-member functions
> +
> + /** Exchange the contents of two stacktrace objects
> + *
> + * Unlike the `swap` member function, this can be used with unequal
> + * and non-propagating allocators. If the storage cannot be efficiently
> + * swapped then the stacktrace_entry elements will be exchanged
> + * one-by-one, reallocating if needed.
> + */
> + friend void
> + swap(basic_stacktrace& __a, basic_stacktrace& __b)
> + noexcept(_AllocTraits::propagate_on_container_swap::value
> + || _AllocTraits::is_always_equal::value)
> + {
> + if constexpr (_AllocTraits::propagate_on_container_swap::value
> + || _AllocTraits::is_always_equal::value)
> + __a.swap(__b);
> + else if (__a._M_alloc == __b._M_alloc) [[likely]]
> + __a.swap(__b);
> + else // O(N) swap for non-equal non-propagating allocators
> + {
> + basic_stacktrace* __p[2]{ std::__addressof(__a),
> + std::__addressof(__b) };
> + if (__p[0]->size() > __p[1]->size())
> + std::swap(__p[0], __p[1]);
> + basic_stacktrace& __a = *__p[0]; // shorter sequence
> + basic_stacktrace& __b = *__p[1]; // longer sequence
> +
> + const auto __a_sz = __a.size();
> + auto __a_begin = __a._M_impl._M_frames;
> + auto __a_end = __a._M_impl._M_frames + __a_sz;
> + auto __b_begin = __b._M_impl._M_frames;
> +
> + if (__a._M_impl._M_capacity < __b.size())
> + {
> + // Reallocation needed.
> + basic_stacktrace __tmp(__b, __a._M_alloc);
> + std::copy(__a_begin, __a_end, __b_begin);
> + __b._M_impl._M_resize(__a_sz, __b._M_alloc);
> + std::swap(__tmp._M_impl, __a._M_impl);
> + return;
> + }
> +
> + // Exchange contents in-place.
> + auto __mid = std::swap_ranges(__a_begin, __a_end, __b_begin);
> + std::__relocate_a(__mid, __b_begin + __a_sz, __a_end,
> __a._M_alloc);
Oops, this should be __b_begin + __b.size() for the second argument.
> + std::swap(__a._M_impl._M_size, __b._M_impl._M_size);
> }
> }
>
> @@ -659,13 +723,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> // basic_stacktrace typedef names
> using stacktrace = basic_stacktrace<allocator<stacktrace_entry>>;
>
> - // [stacktrace.basic.nonmem], non-member functions
> - template<typename _Allocator>
> - inline void
> - swap(basic_stacktrace<_Allocator>& __a, basic_stacktrace<_Allocator>&
> __b)
> - noexcept(noexcept(__a.swap(__b)))
> - { __a.swap(__b); }
> -
> inline ostream&
> operator<<(ostream& __os, const stacktrace_entry& __f)
> {
> diff --git a/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
> b/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
> index ee1a6d221e3..8e784071b29 100644
> --- a/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
> +++ b/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
> @@ -393,6 +393,29 @@ test_swap()
> VERIFY( s1.get_allocator().get_personality() == 2 );
> VERIFY( s2.get_allocator().get_personality() == 1 );
> }
> +
> + {
> + using Alloc
> + = __gnu_test::propagating_allocator<std::stacktrace_entry, false>;
> + using Stacktrace = std::basic_stacktrace<Alloc>;
> +
> + Stacktrace s1 = Stacktrace::current(Alloc{1});
> + Stacktrace s2(Alloc{2});
> + const Stacktrace s3 = s1;
> + swap(s1, s2);
> + VERIFY( s1.empty() );
> + VERIFY( s2 == s3 );
> + VERIFY( s1.get_allocator().get_personality() == 1 );
> + VERIFY( s2.get_allocator().get_personality() == 2 );
> +
> + s1 = s3;
> + s2 = Stacktrace();
> + swap(s1, s2);
> + VERIFY( s1.empty() );
> + VERIFY( s2 == s3 );
> + VERIFY( s1.get_allocator().get_personality() == 1 );
> + VERIFY( s2.get_allocator().get_personality() == 2 );
> + }
> }
>
> void
> --
> 2.47.0
>
