Your definition of operator!= for the allocator test_alloc violates the allocator requirements, which impose that != behaves the same as the negation of == (see Table 28 — Allocator requirements, [allocator.requirements]). This violates causes undefined behaviour. Therefore it seems to me as if this is an invalid bug report.

Indeed. Splicing lists has a precondition that l1.get_allocator() == l2.get_allocator(), and so we check:

  if (l1.get_allocator() != l2.get_allocator())
    abort();

and obviously that fails for your invalid allocator type.

Created attachment 35901 [details]
main.ii

Updating with a valid ==/!= operator pair and state handling, apologies for the original bad test case.
gcc output is the same verbatim as above.

However, sort still aborts with any allocator that provides ==/!= operators based on internal state that is non-default.


sort contains a default constructed list __carry, which will have a different allocator instance to the parent list if an allocator was passed in on construction -
list.tcc:402
        list __carry;

__carry is then spliced with the parent list -
list.tcc:409
	    __carry.splice(__carry.begin(), *this, begin());


A check then occurs if the two allocators are equal -
stl_list.h:1374
	if (this != &__x)
	  _M_check_equal_allocators(__x);

allocator.h:188
      static bool
      _S_do_it(const _Alloc& __one, const _Alloc& __two)
      { return __one != __two; }


This final check will fail if the != operator for the allocator is dependent on internal state comparison, which has differs from the default.

This appears to be incorrect, unless I'm misunderstanding the purpose of the ==/!= operators for allocators?

If this is still considered an issue, I would suggest that __carry be copy constructed.

I've verified with 5.1 as well now, and the abort still occurs

(In reply to Marc Di Luzio from comment #3)
> If this is still considered an issue, I would suggest that __carry be copy
> constructed.

No, it needs to be constructed empty, but with the same allocator:

    list __carry(get_allocator());

Unfortunately so does every element of the array __tmp:

    list __tmp[64] = { get_allocator(), get_allocator(), get_allocator(),...

So we need something ugly like this:

--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -398,6 +398,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
          }
       }
 
+#define _GLIBCXX_REPEAT_8(_X) _X, _X, _X, _X, _X, _X, _X, _X
+
   template<typename _Tp, typename _Alloc>
     void
     list<_Tp, _Alloc>::
@@ -407,8 +409,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
          && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
       {
-        list __carry;
-        list __tmp[64];
+        list __carry(get_allocator());
+        list __tmp[64] = {
+           _GLIBCXX_REPEAT_8(_GLIBCXX_REPEAT_8(list(get_allocator())))
+       };
         list * __fill = &__tmp[0];
         list * __counter;
 
@@ -484,8 +488,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
            && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
          {
-           list __carry;
-           list __tmp[64];
+           list __carry(get_allocator());
+           list __tmp[64] = {
+               _GLIBCXX_REPEAT_8(_GLIBCXX_REPEAT_8(list(get_allocator())))
+           };
            list * __fill = &__tmp[0];
            list * __counter;
 
@@ -511,6 +517,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
            swap(*(__fill - 1));
          }
       }
+#undef _GLIBCXX_REPEAT_8
 
 _GLIBCXX_END_NAMESPACE_CONTAINER
 } // namespace std

A candidate patch has been posted to https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00217.html

With that fix your testcase segfaults, because you allocate n bytes not n*sizeof(Tp).

*** Bug 78371 has been marked as a duplicate of this bug. ***

The ugly fix in Comment #6 should be performant, if, well, ugly.

It may be worth considering holding the nodes via a different type. There's no real reason why the temporary holders need to be a `list` or have a copy of the allocator as long as we make sure that everything in there is spliced back into *this when we exit sort() (by exception or normal return).

Speaking of exceptions, merge() appears to have exception safety problems. I'll file a separate bug.

(In reply to Jonathan Wakely from comment #7)
> A candidate patch has been posted to
> https://gcc.gnu.org/ml/gcc-patches/2015-07/msg00217.html
> 
> With that fix your testcase segfaults, because you allocate n bytes not
> n*sizeof(Tp).

adding "patch" keyword

Are you still working on this, Jonathan?

Yes.

Any chance we can merge the proposed patch on this? This still triggers in GCC-10.2.1, and the proposed patch works if applied to both `sort()` and `sort(cmp)` implementations in `include/bits/list.tcc`.

Version Info:
gcc (GCC) 10.2.1 20201125 (Red Hat 10.2.1-9)

GCC 11.1 has been released, retargeting bugs to GCC 11.2.

Fixed downstream in my fork: https://gitlab.com/jonathan-wakely/gcc/-/commit/18d78721bf3afaed243252a01a4f4909c17531b2

The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:ff7793bea465019683b3a07d7ffceb6eae22def5

commit r12-4082-gff7793bea465019683b3a07d7ffceb6eae22def5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue May 25 14:33:15 2021 +0100

    libstdc++: Allow stateful allocators in std::list::sort [PR 66742]
    
    The temporary lists used by std::list::sort are default constructed,
    which means they use default constructed allocators. The sort operation
    is defined in terms of merge and splice operations, which have undefined
    behaviour (and abort) if the allocators do not compare equal. This means
    it is not possible to sort a list that uses an allocator that compares
    unequal to an default constructed allocator.
    
    The solution is to avoid using temporary std::list objects at all. We do
    not need to be able to allocate memory because no nodes are allocated,
    only spliced from one list to another. That means the temporary lists
    don't need an allocator at all, so whether it would compare equal
    doesn't matter.
    
    Instead of temporary std::list objects, we can just use a collection of
    _List_node_base objects that nodes can be spliced onto as needed. Those
    objects are wrapped in a _Scratch_list type that implements the splicing
    and merging operations used by list::sort.
    
    We also don't need to update the list size during the sort, because
    sorting doesn't alter the number of nodes. Although we move nodes in and
    out of the scratch lists, at the end of the function all nodes are back
    in the original std::list and the scratch lists are empty.  So for the
    cxx11 ABI we can avoid the _M_size modifications usually done when
    splicing nodes.
    
    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/66742
            * include/bits/list.tcc (list::sort()): Use _Scratch_list
            objects for splicing and merging.
            (list::sort(StrictWeakOrdering)): Likewise.
            * include/bits/stl_list.h (__detail::_Scratch_list): New type.
            * src/c++98/list.cc (_List_node_base::_M_transfer): Add
            assertion for --enable-libstdcxx-debug library.
            * testsuite/23_containers/list/operations/66742.cc: New test.

Fixed for GCC 12.

My fix caused a regression for this (IMHO dumb) case:

#include <list>
struct X {
  bool operator<(X&) /* non-const */ { return false; }
};
struct Cmp {
  bool operator()(X&, X&) /* non-const */ { return false; }
};
int main() {
  std::list<X> l;
  l.sort();
  Cmp c;
  l.sort(c);
}

The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:1e7a269856fd67aff78ac874bec96d31a54b2fd9

commit r12-4873-g1e7a269856fd67aff78ac874bec96d31a54b2fd9
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Nov 2 10:21:01 2021 +0000

    libstdc++: Fix regression in std::list::sort [PR66742]
    
    The standard does not require const-correct comparisons in list::sort.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/66742
            * include/bits/list.tcc (list::sort): Use mutable iterators for
            comparisons.
            * include/bits/stl_list.h (_Scratch_list::_Ptr_cmp): Likewise.
            * testsuite/23_containers/list/operations/66742.cc: Check
            non-const comparisons.

GCC 12.1 is being released, retargeting bugs to GCC 12.2.

This was fixed for 12.1