libstdc++: Make std::basic_stacktrace swappable with unequal allocators

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

On Thu, 28 Nov 2024 at 18:59, Jonathan Wakely <jwakely@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
>
  

Patch v2 fixes the bug in the slow path for swap, and improves the
test so that it fails with the old buggy code.
commit 44214429d428f4fe5a148c7636b844600a10f9a4
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Nov 28 13:59:09 2024

    libstdc++: Make std::basic_stacktrace swappable with unequal allocators
    
    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.

diff --git a/libstdc++-v3/include/std/stacktrace b/libstdc++-v3/include/std/stacktrace
index f94a424e4cf..a7d4810e886 100644
--- a/libstdc++-v3/include/std/stacktrace
+++ b/libstdc++-v3/include/std/stacktrace
@@ -476,15 +476,80 @@ _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 + __b.size(), __a_end,
+			      __a._M_alloc);
+	    std::swap(__a._M_impl._M_size, __b._M_impl._M_size);
 	  }
       }
 
@@ -659,13 +724,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..57453c4c9b5 100644
--- a/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
+++ b/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
@@ -393,6 +393,30 @@ 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::current(s2.get_allocator()); // Overwrite old content
+    s2 = Stacktrace(); // Clear content, capacity will be unchanged.
+    swap(s1, s2);
+    VERIFY( s1.empty() );
+    VERIFY( s2 == s3 );
+    VERIFY( s1.get_allocator().get_personality() == 1 );
+    VERIFY( s2.get_allocator().get_personality() == 2 );
+  }
 }
 
 void