[Bug c++/111685] New: Segfault while sorting on array element address

[Bug c++/111685] New: Segfault while sorting on array element address

[knoepfel at fnal dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

            Bug ID: 111685
           Summary: Segfault while sorting on array element address
           Product: gcc
           Version: 13.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: knoepfel at fnal dot gov
  Target Milestone: ---

The following file (`sort-bug.cpp`) results in a segmentation violation:

```
#include <algorithm>
#include <array>
#include <cassert>
#include <vector>

int main()
{
  std::vector vnums{1, 5, 4};
  std::array anums{1, 5, 4};
  int nums[] = {1, 5, 4};

  auto cmp = [](auto&& a, auto&& b) { return &a < &b; };

  std::sort(vnums.begin(), vnums.end(), cmp);
  std::sort(anums.begin(), anums.end(), cmp); // segfault
  std::sort(nums, nums + 3, cmp);             // segfault
}
```

*Expected result*: the `vnums`, `anums`, and `nums` variables remain unaltered
after the invocation to `std::sort`.

*Compiler info*:

- Target: x86_64-pc-linux-gnu
- Configured with:
/scratch/workspace/art-build-base/v13_02_00-e28/SLF7/build/gcc/v13_1_0/src/gcc-13.1.0/configure
--enable-__cxa_atexit --enable-checking=release
--enable-compressed-debug-sections=all
--enable-languages=c,c++,fortran,go,objc,obj-c++ --enable-libstdcxx-time=rt
--enable-plugin --enable-stage1-checking=all --enable-threads=posix
--prefix=/scratch/workspace/art-build-base/v13_02_00-e28/SLF7/build/gcc/v13_1_0/Linux64bit+3.10-2.17
--with-system-zlib --enable-lto --with-zstd --enable-link-serialization=15
- Thread model: posix
- Supported LTO compression algorithms: zlib zstd
- gcc version 13.1.0 (GCC) 

*Compiler/runtime command*: `g++ sort-bug.cpp -o sort-bug -std=c++20 -pedantic
-Werror -Wall; ./sort-bug`

[Bug libstdc++/111685] Segfault while sorting on array element address

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
IIRC this happens if the cmp is defined incorrectly.

[Bug libstdc++/111685] Segfault while sorting on array element address

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
And it is definitely defined incorrectly.

Adding a printf in the cmp:
        __builtin_printf("%p:%p\n", &a, &b);

Gives:
0x12072b0:0x12072b0
0x12072b4:0x12072b0
0x7ffe9afcec9c:0x12072b0
0x12072b8:0x12072b0
0x7ffe9afcec9c:0x12072b4

Which means libstdc++ is calling the cmp on a temporary and you not getting the
correct thing.

[Bug libstdc++/111685] Segfault while sorting on array element address

[knoepfel at fnal dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #3 from Kyle Knoepfel <knoepfel at fnal dot gov> ---
@Andrew Pinski, yes I surmised as much.  My difficulty, though, is in
understanding if this is the correct behavior according to the standard's
specification of std::sort, which presumably is reasonably summarized in the
type requirements listed at https://en.cppreference.com/w/cpp/algorithm/sort. 
Which formal requirements/preconditions are being violated by cmp?

[Bug libstdc++/111685] Segfault while sorting on array element address

[knoepfel at fnal dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

Kyle Knoepfel <knoepfel at fnal dot gov> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |---

--- Comment #4 from Kyle Knoepfel <knoepfel at fnal dot gov> ---
@Andrew Pinski described what has happened, but not whether that is the
expected behavior of the standard.  See comment #3.

[Bug libstdc++/111685] Segfault while sorting on array element address

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
With -fsanitize=address we get this at runtime:
```
=================================================================
==1==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fc69190003c
at pc 0x000000402d20 bp 0x7ffdf89976f0 sp 0x7ffdf89976e8
READ of size 4 at 0x7fc69190003c thread T0
    #0 0x402d1f in void std::__unguarded_linear_insert<int*,
__gnu_cxx::__ops::_Val_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}> >(int*,
__gnu_cxx::__ops::_Val_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}>)
(/app/output.s+0x402d1f) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
    #1 0x40222f in void std::__insertion_sort<int*,
__gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}> >(int*,
int*, __gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}>)
(/app/output.s+0x40222f) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
    #2 0x401c23 in void std::__final_insertion_sort<int*,
__gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}> >(int*,
int*, __gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}>)
(/app/output.s+0x401c23) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
    #3 0x401875 in void std::__sort<int*,
__gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}> >(int*,
int*, __gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}>)
(/app/output.s+0x401875) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
    #4 0x401653 in void std::sort<int*, main::{lambda(auto:1&&,
auto:2&&)#1}>(int*, int*, main::{lambda(auto:1&&, auto:2&&)#1})
(/app/output.s+0x401653) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
    #5 0x401506 in main (/app/output.s+0x401506) (BuildId:
644c16636015edebcd5c5ddf005f8c7778b15662)
    #6 0x7fc693b93082 in __libc_start_main
(/lib/x86_64-linux-gnu/libc.so.6+0x24082) (BuildId:
1878e6b475720c7c51969e69ab2d276fae6d1dee)
    #7 0x40122d in _start (/app/output.s+0x40122d) (BuildId:
644c16636015edebcd5c5ddf005f8c7778b15662)

Address 0x7fc69190003c is located in stack of thread T0 at offset 60 in frame
    #0 0x4012f5 in main (/app/output.s+0x4012f5) (BuildId:
644c16636015edebcd5c5ddf005f8c7778b15662)

  This frame has 5 object(s):
    [32, 33) '<unknown>'
    [48, 49) 'cmp' (line 13)
    [64, 76) 'anums' (line 10) <== Memory access at offset 60 underflows this
variable
    [96, 108) 'nums' (line 11)
    [128, 152) 'vnums' (line 9)
HINT: this may be a false positive if your program uses some custom stack
unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (/app/output.s+0x402d1f)
(BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662) in void
std::__unguarded_linear_insert<int*,
__gnu_cxx::__ops::_Val_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}> >(int*,
__gnu_cxx::__ops::_Val_comp_iter<main::{lambda(auto:1&&, auto:2&&)#1}>)
Shadow bytes around the buggy address:
  0x7fc6918ffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc6918ffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc6918ffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc6918fff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc6918fff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x7fc691900000: f1 f1 f1 f1 f8 f2 01[f2]00 04 f2 f2 00 04 f2 f2
  0x7fc691900080: 00 00 00 f3 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x7fc691900100: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc691900180: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc691900200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7fc691900280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==1==ABORTING
```

[Bug libstdc++/111685] Segfault while sorting on array element address

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1814

is exactly where a temp copy is created. Is that valid for std::sort, I am
pretty sure it is.

[Bug libstdc++/111685] Segfault while sorting on array element address

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

Xi Ruoyao <xry111 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xry111 at gcc dot gnu.org

--- Comment #7 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
[alg.sorting] p3:

For algorithms other than those described in 28.7.3, comp shall
induce a strict weak ordering on the values.

Note the terminology "values".  I cannot find the definition of "value" in the
standard, but I'm pretty sure the "values" must be independent to "their
addresses" or the entire standard would become completely unreasonable (note
that rvalues has no addresses at all).

[Bug libstdc++/111685] Segfault while sorting on array element address

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The standard only defines sorting in terms of comparisons on "every iterator i
pointing to the sequence", which seems to preclude using a temporary object on
the stack that is outside the sequence.

That said, the comparison object seems like nonsense and I don't see any great
need to support this case.

We could define the linear insertion in terms of swaps, something like:

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __unguarded_linear_insert(_RandomAccessIterator __last,
                              _Compare __comp)
    {
      _RandomAccessIterator __next = __last;
      --__next;
      while (__comp(*__last, __next))
        {
          std::iter_swap(__last, __next);
          __last = __next;
          --__next;
        }
    }

However, that would perform 3N copies, where the current code does N.

Alternatively, find the partition point first and then do N copies, something
like:

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __unguarded_linear_insert(_RandomAccessIterator __last,
                              _Compare __comp)
    {
      _RandomAccessIterator __next = __last;
      --__next;
      while (__comp(*__last, __next))
        --__next;
      typename iterator_traits<_RandomAccessIterator>::value_type
        __val = _GLIBCXX_MOVE(*__last);
      _RandomAccessIterator __prev = __last;
      --__prev;
      while (__prev != __next)
        {
          *__last = _GLIBCXX_MOVE(*__prev);
          __last = __prev;
        }
      *__last = _GLIBCXX_MOVE(__val);
    }

But this traverses the sequence twice, where the original does it in one
traversal.

[Bug libstdc++/111685] Segfault while sorting on array element address

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The sketches above are completely untested (and incorrect) but just
demonstrating the ideas.

[Bug libstdc++/111685] Segfault while sorting on array element address

[fchelnokov at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #10 from Fedor Chelnokov <fchelnokov at gmail dot com> ---
It seems that both libc++ and MS STL implement std::sort without a temporary
object passed to cmp, because they are fine with compiling the following code
in constant expression (where unrelated pointers cannot be compared):

consteval void foo() {
  std::array<int,3> nums{1, 5, 4};
  auto cmp = [](auto& a, auto& b) { return &a < &b; };
  std::sort(nums.begin(), nums.end(), cmp);
}

Online demo: https://godbolt.org/z/jdecfP6c4

Is it right that their implementations are less optimal because of no temporary
object?

[Bug libstdc++/111685] Segfault while sorting on array element address

[knoepfel at fnal dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

Kyle Knoepfel <knoepfel at fnal dot gov> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |INVALID
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #11 from Kyle Knoepfel <knoepfel at fnal dot gov> ---
@Xi Ruoyao's comment above re. strict weak ordering of values and not object
addresses is persuasive.  Thank you for your time and for clarifying my
misconceptions.

[Bug libstdc++/111685] Segfault while sorting on array element address

[fchelnokov at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685

--- Comment #12 from Fedor Chelnokov <fchelnokov at gmail dot com> ---
Related discussion: https://stackoverflow.com/q/77224270/7325599