[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[fdumont at gcc dot gnu.org]

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

--- Comment #2 from François Dumont <fdumont at gcc dot gnu.org> ---
Is there any unmentioned prerequisite to reproduce this bug ? I cannot.

Maybe thanks to PR11477 this PR could be closed too.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2019-04-29 00:00:00         |2024-1-24

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
No, they're not fixed by PR 112477.

/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/debug/safe_iterator.h:222:
In function:
    gnu_debug::_Safe_iterator<_Iterator, _Sequence, 
    _Category>::_Safe_iterator(gnu_debug::_Safe_iterator<_Iterator, 
    _Sequence, _Category>&&) [with _Iterator = gnu_cxx::
    normal_iterator<short int*, std::vector<short int, std::allocator<short 
    int> > >; _Sequence = std::debug::vector<short int, std::allocator<short 
    int> >; _Category = std::forward_iterator_tag]

Error: attempt to copy-construct an iterator from a singular iterator.

Objects involved in the operation:
    iterator "this" @ 0x7ffdca543c20 {
      type = gnu_cxx::normal_iterator<short*, std::vector<short,
std::allocator<short> > > (mutable iterator);
      state = singular (value-initialized);
    }
    iterator "other" @ 0x7ffdca543bf0 {
      type = gnu_cxx::normal_iterator<short*, std::vector<short,
std::allocator<short> > > (mutable iterator);
      state = singular;
    }
FAIL: 20_util/specialized_algorithms/pstl/uninitialized_copy_move.cc 
-std=gnu++17 execution test




You need Intel TBB installed to run those tests:

// { dg-require-effective-target tbb_backend }

Otherwise grepping for them in libstdc++.sum will show them as UNSUPPORTED.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2024-01-24 00:00:00         |2019-04-29 0:00

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
In testsuite/util/pstl/test_utils.h we have:

template <typename IsReverse>
struct reverse_invoker
{
    template <typename... Rest>
    void
    operator()(Rest&&... rest)
    {
        // Random-access iterator
        iterator_invoker<std::random_access_iterator_tag,
IsReverse>()(std::forward<Rest>(rest)...);

        // Forward iterator
        iterator_invoker<std::forward_iterator_tag,
IsReverse>()(std::forward<Rest>(rest)...);

        // Bidirectional iterator
        iterator_invoker<std::bidirectional_iterator_tag,
IsReverse>()(std::forward<Rest>(rest)...);
    }
};

This is called with rvalue iterators e.g.

TestUtils::invoke_on_all_policies(check_minelement(), wseq.seq.cbegin(),
wseq.seq.cend());

In the body of reverse_invoker::operator() we forward them as rvalues which
causes them to be moved into the by-value parameters of
iterator_invoker<random_access_iterator_tag, R>::operator()

Then we forward them again, which causes them to be moved again. The debug
iterators abort at this point, because they're singular after the first move.

So the problem is that a moved-from __debug::vector::iterator is singular, and
therefore can't be moved or copied. I wonder if that's really what we want, or
if a moved-from iterator should have the value-initialized state instead of a
singular state.

The standard is clear that a singular iterator cannot be copied or moved,
unless it was value-initialized, see [iterator.requirements.general] p7.

In any case, the PSTL test harness should probably not be using moved-from
iterators more than once.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://github.com/llvm/llv
                   |                            |m-project/issues/80126

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Reported upstream: https://github.com/llvm/llvm-project/issues/80126

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Some of the tests FAIL for different reasons:

/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_algo.h:2051:
In function:
    _FIter std::upper_bound(_FIter, _FIter, const _Tp&, _Compare) [with
    _FIter = gnu_debug::_Safe_iterator<gnu_cxx::normal_iterator<Num<float>*,
    vector<Num<float>, allocator<Num<float> > > >, debug::vector<Num<float>,
    allocator<Num<float> > >, random_access_iterator_tag>; _Tp = Num<float>;
    _Compare = main()::<lambda(Num<float>, Num<float>)>]

Error: elements in iterator range [first, last) are not partitioned by the
predicate __comp and value __val.

Objects involved in the operation:
    iterator "first" @ 0x7ffda0426810 {
      type = gnu_cxx::normal_iterator<Num<float>*, std::vector<Num<float>,
std::allocator<Num<float> > > > (mutable iterator);
      state = dereferenceable (start-of-sequence);
      references sequence with type 'std::debug::vector<Num<float>,
std::allocator<Num<float> > >' @ 0x7ffda0427730
    }
    iterator "last" @ 0x7ffda0426840 {
      type = gnu_cxx::normal_iterator<Num<float>*, std::vector<Num<float>,
std::allocator<Num<float> > > > (mutable iterator);
      state = dereferenceable;
      references sequence with type 'std::debug::vector<Num<float>,
std::allocator<Num<float> > >' @ 0x7ffda0427730
    }
FAIL: 25_algorithms/pstl/alg_sorting/partial_sort.cc  -std=gnu++17 execution
test

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
__pstl::__tbb_backend::__merge_func::split_merging (which should be a reserved
name) does:

        if (__nx < __ny)
        {
            __ym = _M_ys + __ny / 2;

            if (_x_orig)
                __xm = std::upper_bound(_M_x_beg + _M_xs, _M_x_beg + _M_xe,
*(_M_x_beg + __ym), _M_comp) - _M_x_beg;
            else
                __xm = std::upper_bound(_M_z_beg + _M_xs, _M_z_beg + _M_xe,
*(_M_z_beg + __ym), _M_comp) - _M_z_beg;
        }

which aborts because the range is not correctly sorted w.r.t _M_comp, as
required by upper_bound.

The range looks like this:

$1 = std::__cxx1998::vector of length 1284, capacity 1284 = {{val = 0}, {val =
5290}, {val = 9862}, {val = 8699}, {val = 5471}, {val = 4810}, {
    val = 6176}, {val = 1400}, {val = 5025}, {val = 3246}, {val = 2547}, {val =
8814}, {val = 2463}, {val = 8800}, {val = 3074}, {val = 5741}, {
    val = 5234}, {val = 736}, {val = 4895}, {val = 6803}, {val = 2363}, {val =
5351}, {val = 6719}, {val = 7967}, {val = 732}, {val = 1399}, {val = 7586}, 
  {val = 4659}, {val = 3800}, {val = 6956}, {val = 4087}, {val = 9090}, {val =
2293}, {val = 8702}, {val = 2263}, {val = 7765}, {val = 3233}, {
    val = 8440}, {val = 3918}, {val = 8259}, {val = 6439}, {val = 6465}, {val =
6794}, {val = 3656}, {val = 10018}, {val = 4621}, {val = 9397}, {
    val = 4973}, {val = 584}, {val = 9046}, {val = 6530}, {val = 2474}, {val =
4118}, {val = 2970}, {val = 162}, {val = 4850}, {val = 9401}, {val = 7748}, 
  {val = 9509}, {val = 2923}, {val = 4425}, {val = 8349}, {val = 6766}, {val =
6719}, {val = 6773}, {val = 3783}, {val = 4205}, {val = 4759}, {
    val = 6976}, {val = 8123}, {val = 2739}, {val = 3136}, {val = 4309}, {val =
4286}, {val = 6792}, {val = 4048}, {val = 8908}, {val = 664}, {
    val = 3774}, {val = 9019}, {val = 9710}, {val = 111}, {val = 1214}, {val =
8581}, {val = 2996}, {val = 6409}, {val = 3152}, {val = 7150}, {
    val = 3878}, {val = 7415}, {val = 10073}, {val = 3057}, {val = 238}, {val =
1314}, {val = 9776}, {val = 7011}, {val = 5097}, {val = 8734}, {
    val = 6524}, {val = 1794}, {val = 6578}, {val = 9263}, {val = 9962}, {val =
5640}, {val = 3271}, {val = 1229}, {val = 4441}, {val = 6932}, {
    val = 1893}, {val = 2968}, {val = 425}, {val = 6356}, {val = 2994}, {val =
6671}, {val = 4658}, {val = 743}, {val = 2801}, {val = 2563}, {val = 7893}, 
  {val = 1433}, {val = 4731}, {val = 2441}, {val = 4490}, {val = 4970}, {val =
8787}, {val = 3987}, {val = 6734}, {val = 3605}, {val = 7474}, {
    val = 2979}, {val = 152}, {val = 8805}, {val = 1964}, {val = 10114}, {val =
4166}, {val = 10267}, {val = 6096}, {val = 3360}, {val = 1673}, {
    val = 2742}, {val = 6328}, {val = 7130}, {val = 9098}, {val = 4075}, {val =
8554}, {val = 8509}, {val = 9850}, {val = 1077}, {val = 794}, {
    val = 7465}, {val = 2510}, {val = 5525}, {val = 4659}, {val = 1753}, {val =
216}, {val = 3167}, {val = 493}, {val = 1704}, {val = 1525}, {val = 7967}, 
  {val = 4683}, {val = 6709}, {val = 6493}, {val = 1400}, {val = 1297}, {val =
5412}, {val = 6420}, {val = 7394}, {val = 8772}, {val = 2846}, {
    val = 10136}, {val = 9853}, {val = 9976}, {val = 3709}, {val = 8682}, {val
= 8252}, {val = 1939}, {val = 8253}, {val = 4082}, {val = 7765}, {
    val = 5439}, {val = 1345}, {val = 3012}, {val = 4851}, {val = 3098}, {val =
8260}, {val = 2771}, {val = 3591}, {val = 4717}, {val = 9328}, {
    val = 1279}, {val = 9401}, {val = 5758}, {val = 2525}, {val = 5554}, {val =
1809}, {val = 7937}, {val = 1696}, {val = 9203}, {val = 1183}...}


This is indeed not partitioned:

(gdb) p __val
$2 = (const Num<float> &) @0x7ffff7994e28: {val = 687}
(gdb) p __first[46]
$4 = (Num<float> &) @0x7ffff79930c8: {val = 9397}
(gdb) p __first[47]
$5 = (Num<float> &) @0x7ffff79930cc: {val = 4973}
(gdb) p __first[48]
$6 = (Num<float> &) @0x7ffff79930d0: {val = 584}   <--------
(gdb) p __first[49]
$7 = (Num<float> &) @0x7ffff79930d4: {val = 9046}

I think this needs to be reported upstream too.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
https://github.com/llvm/llvm-project/issues/80136

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[frs.dumont at gmail dot com]

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

--- Comment #9 from frs.dumont at gmail dot com ---
Here is the reason of the 
20_util/specialized_algorithms/pstl/uninitialized_copy_move.cc FAIL.

Maybe it fixes some other tests too, I need to run all of them.

     libstdc++: Do not forward arguments several times [PR90276]

     Forwarding several times the same arguments results in UB. It is 
detected
     by the _GLIBCXX_DEBUG mode as an attempt to use a singular iterator 
which has
     been moved.

     libstdc++-v3/ChangeLog

             PR libstdc++/90276
             * testsuite/util/pstl/test_utils.h: Remove std::forward<> 
calls when
             done several times on the same arguments.

Ok to commit ?

François


On 31/01/2024 14:11, redi at gcc dot gnu.org wrote:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90276
>
> Jonathan Wakely <redi at gcc dot gnu.org> changed:
>
>             What    |Removed                     |Added
> ----------------------------------------------------------------------------
>             See Also|                            |https://github.com/llvm/llv
>                     |                            |m-project/issues/80136
>

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
And another one:
https://github.com/llvm/llvm-project/issues/80217

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:723a7c1ad29523b9ddff53c7b147bffea56fbb63

commit r14-8743-g723a7c1ad29523b9ddff53c7b147bffea56fbb63
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jan 31 10:41:49 2024 +0000

    libstdc++: Avoid reusing moved-from iterators in PSTL tests [PR90276]

    The reverse_invoker utility for PSTL tests uses forwarding references for
    all parameters, but some of those parameters get forwarded to move
    constructors which then leave the objects in a moved-from state. When
    the parameters are forwarded a second time that results in making new
    copies of moved-from iterators.  For libstdc++ debug mode iterators, the
    moved-from state is singular, which means copying them will abort at
    runtime.

    The fix is to make copies of iterator arguments instead of forwarding
    them.

    The callers of reverse_invoker::operator() also forward the iterators
    multiple times, but that's OK because reverse_invoker accepts them by
    forwarding reference but then breaks the chain of forwarding and copies
    them as lvalues.

    libstdc++-v3/ChangeLog:

            PR libstdc++/90276
            * testsuite/util/pstl/test_utils.h (reverse_invoker): Do not use
            perfect forwarding for iterator arguments.

--- Comment #12 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

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

commit r14-8744-ga6286584e5536d1853a851b8c2ac3196956e3068
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Feb 1 10:06:15 2024 +0000

    libstdc++: Fix invalid order in PSTL inplace_merge test [PR90276]

    This looks like a typo in the upstream test that causes a failure in
    debug mode. It has been reported upstream.

    libstdc++-v3/ChangeLog:

            PR libstdc++/90276
            * testsuite/25_algorithms/pstl/alg_merge/inplace_merge.cc: Fix
            comparison function to use less-than instead of equality.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:723a7c1ad29523b9ddff53c7b147bffea56fbb63

commit r14-8743-g723a7c1ad29523b9ddff53c7b147bffea56fbb63
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jan 31 10:41:49 2024 +0000

    libstdc++: Avoid reusing moved-from iterators in PSTL tests [PR90276]

    The reverse_invoker utility for PSTL tests uses forwarding references for
    all parameters, but some of those parameters get forwarded to move
    constructors which then leave the objects in a moved-from state. When
    the parameters are forwarded a second time that results in making new
    copies of moved-from iterators.  For libstdc++ debug mode iterators, the
    moved-from state is singular, which means copying them will abort at
    runtime.

    The fix is to make copies of iterator arguments instead of forwarding
    them.

    The callers of reverse_invoker::operator() also forward the iterators
    multiple times, but that's OK because reverse_invoker accepts them by
    forwarding reference but then breaks the chain of forwarding and copies
    them as lvalues.

    libstdc++-v3/ChangeLog:

            PR libstdc++/90276
            * testsuite/util/pstl/test_utils.h (reverse_invoker): Do not use
            perfect forwarding for iterator arguments.

--- Comment #12 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

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

commit r14-8744-ga6286584e5536d1853a851b8c2ac3196956e3068
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Feb 1 10:06:15 2024 +0000

    libstdc++: Fix invalid order in PSTL inplace_merge test [PR90276]

    This looks like a typo in the upstream test that causes a failure in
    debug mode. It has been reported upstream.

    libstdc++-v3/ChangeLog:

            PR libstdc++/90276
            * testsuite/25_algorithms/pstl/alg_merge/inplace_merge.cc: Fix
            comparison function to use less-than instead of equality.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The remaining failures are:

25_algorithms/pstl/alg_nonmodifying/nth_element.cc
25_algorithms/pstl/alg_sorting/includes.cc
25_algorithms/pstl/alg_sorting/minmax_element.cc
25_algorithms/pstl/alg_sorting/partial_sort.cc
25_algorithms/pstl/alg_sorting/set_difference.cc
25_algorithms/pstl/alg_sorting/set_intersection.cc
25_algorithms/pstl/alg_sorting/set_symmetric_difference.cc
25_algorithms/pstl/alg_sorting/set_union.cc

But they're all timeouts except for partial_sort.cc which is analyzed above,
starting from comment 6.

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:3c04a1533b32362c7c28fc32b05623dda45a1b44

commit r13-8304-g3c04a1533b32362c7c28fc32b05623dda45a1b44
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jan 31 10:41:49 2024 +0000

    libstdc++: Avoid reusing moved-from iterators in PSTL tests [PR90276]

    The reverse_invoker utility for PSTL tests uses forwarding references for
    all parameters, but some of those parameters get forwarded to move
    constructors which then leave the objects in a moved-from state. When
    the parameters are forwarded a second time that results in making new
    copies of moved-from iterators.  For libstdc++ debug mode iterators, the
    moved-from state is singular, which means copying them will abort at
    runtime.

    The fix is to make copies of iterator arguments instead of forwarding
    them.

    The callers of reverse_invoker::operator() also forward the iterators
    multiple times, but that's OK because reverse_invoker accepts them by
    forwarding reference but then breaks the chain of forwarding and copies
    them as lvalues.

    libstdc++-v3/ChangeLog:

            PR libstdc++/90276
            * testsuite/util/pstl/test_utils.h (reverse_invoker): Do not use
            perfect forwarding for iterator arguments.

    (cherry picked from commit 723a7c1ad29523b9ddff53c7b147bffea56fbb63)

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[cvs-commit at gcc dot gnu.org]

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

--- Comment #15 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:39d37ffbf890334b16ffb56da9fe00f0daa87f16

commit r12-10145-g39d37ffbf890334b16ffb56da9fe00f0daa87f16
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jan 31 10:41:49 2024 +0000

    libstdc++: Avoid reusing moved-from iterators in PSTL tests [PR90276]

    The reverse_invoker utility for PSTL tests uses forwarding references for
    all parameters, but some of those parameters get forwarded to move
    constructors which then leave the objects in a moved-from state. When
    the parameters are forwarded a second time that results in making new
    copies of moved-from iterators.  For libstdc++ debug mode iterators, the
    moved-from state is singular, which means copying them will abort at
    runtime.

    The fix is to make copies of iterator arguments instead of forwarding
    them.

    The callers of reverse_invoker::operator() also forward the iterators
    multiple times, but that's OK because reverse_invoker accepts them by
    forwarding reference but then breaks the chain of forwarding and copies
    them as lvalues.

    libstdc++-v3/ChangeLog:

            PR libstdc++/90276
            * testsuite/util/pstl/test_utils.h (reverse_invoker): Do not use
            perfect forwarding for iterator arguments.

    (cherry picked from commit 723a7c1ad29523b9ddff53c7b147bffea56fbb63)

[Bug libstdc++/90276] PSTL tests fail in Debug Mode

[redi at gcc dot gnu.org]

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

--- Comment #16 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Two patches posted:
https://gcc.gnu.org/pipermail/gcc-patches/2024-June/655274.html
https://gcc.gnu.org/pipermail/gcc-patches/2024-June/655273.html