[Bug libstdc++/111685] Segfault while sorting on array element address
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 --- Comment #12 from Fedor Chelnokov --- Related discussion: https://stackoverflow.com/q/77224270/7325599
[Bug libstdc++/111685] Segfault while sorting on array element address
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 Kyle Knoepfel changed: What|Removed |Added Resolution|--- |INVALID Status|UNCONFIRMED |RESOLVED --- Comment #11 from Kyle Knoepfel --- @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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685
--- Comment #10 from Fedor Chelnokov ---
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 nums{1, 5, 4};
auto cmp = [](auto& a, auto& b) { return < };
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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 --- Comment #9 from Jonathan Wakely --- The sketches above are completely untested (and incorrect) but just demonstrating the ideas.
[Bug libstdc++/111685] Segfault while sorting on array element address
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685
--- Comment #8 from Jonathan Wakely ---
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
_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
_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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 Xi Ruoyao changed: What|Removed |Added CC||xry111 at gcc dot gnu.org --- Comment #7 from Xi Ruoyao --- [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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 --- Comment #6 from Andrew Pinski --- 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685
--- Comment #5 from Andrew Pinski ---
With -fsanitize=address we get this at runtime:
```
=
==1==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fc69190003c
at pc 0x00402d20 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)
(/app/output.s+0x402d1f) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
#1 0x40222f in void std::__insertion_sort >(int*,
int*, __gnu_cxx::__ops::_Iter_comp_iter)
(/app/output.s+0x40222f) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
#2 0x401c23 in void std::__final_insertion_sort >(int*,
int*, __gnu_cxx::__ops::_Iter_comp_iter)
(/app/output.s+0x401c23) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
#3 0x401875 in void std::__sort >(int*,
int*, __gnu_cxx::__ops::_Iter_comp_iter)
(/app/output.s+0x401875) (BuildId: 644c16636015edebcd5c5ddf005f8c7778b15662)
#4 0x401653 in void std::sort(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) ''
[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)
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
=>0x7fc69190: 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 Kyle Knoepfel changed: What|Removed |Added Status|RESOLVED|UNCONFIRMED Resolution|INVALID |--- --- Comment #4 from Kyle Knoepfel --- @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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 --- Comment #3 from Kyle Knoepfel --- @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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685
Andrew Pinski changed:
What|Removed |Added
Status|UNCONFIRMED |RESOLVED
Resolution|--- |INVALID
--- Comment #2 from Andrew Pinski ---
And it is definitely defined incorrectly.
Adding a printf in the cmp:
__builtin_printf("%p:%p\n", , );
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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 --- Comment #1 from Andrew Pinski --- IIRC this happens if the cmp is defined incorrectly.
