On Fri, 20 Dec 2024, Patrick Palka wrote:
> On Fri, 20 Dec 2024, Giuseppe D'Angelo wrote:
>
> > Hello,
> >
> > On 20/12/2024 13:23, Giuseppe D'Angelo wrote:
> > > Hi,
> > >
> > > The implementation of ranges::is_permutation may create a dangling
> > > reference, which then results (sometimes) in a crash. A minimal example
> > > that shows the problem under ASAN is https://gcc.godbolt.org/z/7bP9nE8fK
>
> D'oh, good catch..
>
> > >
> > > The attached patch fixes it. I've tested on Linux x86-64. Adding a
> > > negative test for this is somehow challenging (how do you test you're
> > > not using a dangling reference?), but running the modified test under
> > > ASAN shows the fix in place.
>
> I'd expect a constexpr version of the test to reliably fail as soon as
> it encounters the UB.
>
> > >
> > > Do you need me to create a report on bugzilla and cross-reference it
> > > from the patch?
>
> That'd be good since we'll probably want to backport the fix to the
> release branches and the PR could reflect that.
>
> > Better patch attached.
> >
> > Thanks,
> > --
> > Giuseppe D'Angelo
> >
>
> > Subject: [PATCH] libstdc++: fix a dangling reference crash in
> > ranges::is_permutation
> >
> > The code was caching the result of `invoke(proj, *it)` in a local
> > `auto &&` variable. The problem is that this may create dangling
> > references, for instance in case `proj` is `std::identity` (the common
> > case) and `*it` produces a prvalue.
> >
> > Rather than finding a "creative" solution (e.g. use the value category
> > of `*it`, and the return type of calling the projection on that, to
> > determine whether we can keep a reference or we need a value), get rid
> > of the caching and call `invoke` as needed. In the common case the
> > projection is cheap, and we are allowed to dereference the same iterator
> > more than once (they're forward). This also sounds more correct because
> > we pass the correct value category (obtained from applying the
> > projection to the iterator) to the comparator.
>
> Makes sense, but it might be preferable for sake of QoI to fix this
> without introducing extra dereferences or projection applications
> if possible.
>
> auto&& is supposed to perform lifetime extension, but that only happens
> for an outermost temporary and not any temporaries within a
> subexpression IIUC. So how about if we use a second auto&& for the
> *__scan subexpression so that lifetime extension occurs there?
>
> >
> > libstdc++-v3/ChangeLog:
> >
> > * include/bits/ranges_algo.h (__is_permutation_fn): Do not cache
> > the projection result in a local variable, as that may create
> > dangling references.
> > * testsuite/25_algorithms/is_permutation/constined.cc: Add a
> > test with a range returning prvalues.
> >
> > Signed-off-by: Giuseppe D'Angelo <giuseppe.dang...@kdab.com>
> > ---
> > libstdc++-v3/include/bits/ranges_algo.h | 3 +--
> > .../25_algorithms/is_permutation/constrained.cc | 11 +++++++++++
> > 2 files changed, 12 insertions(+), 2 deletions(-)
> >
> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> > b/libstdc++-v3/include/bits/ranges_algo.h
> > index 772bf4dd997..4d3c4325e2c 100644
> > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > @@ -567,9 +567,8 @@ namespace ranges
> >
> > for (auto __scan = __first1; __scan != __last1; ++__scan)
> > {
> > - auto&& __proj_scan = std::__invoke(__proj1, *__scan);
> > auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool {
> > - return std::__invoke(__pred, __proj_scan,
>
> If we go with the second auto&& approach then we should perfect forward
> __proj_scan here as you alluded to. That might seem unsafe at first
> glance (if say the project returns an rvalue) but since the predicate is
> regular_invocable it mustn't modify its arguments IIUC.
N.B. that we currently don't perfect forward __proj_scan here is a
minor bug separate from the dangling reference bug.
The predicate's constraints permit invocability with
iter_reference_t<I1> not necessarily with iter_reference_t<I1>&,
but here we're currently invoking it with the latter.
>
> > + return std::__invoke(__pred, std::__invoke(__proj1, *__scan),
> > std::forward<_Tp>(__arg));
> > };
> > if (__scan != ranges::find_if(__first1, __scan,
> > diff --git
> > a/libstdc++-v3/testsuite/25_algorithms/is_permutation/constrained.cc
> > b/libstdc++-v3/testsuite/25_algorithms/is_permutation/constrained.cc
> > index 2fbebe37609..4981d2c07ce 100644
> > --- a/libstdc++-v3/testsuite/25_algorithms/is_permutation/constrained.cc
> > +++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/constrained.cc
> > @@ -19,6 +19,7 @@
> >
> > #include <algorithm>
> > #include <iterator>
> > +#include <ranges>
> > #include <testsuite_hooks.h>
> > #include <testsuite_iterators.h>
> >
> > @@ -76,10 +77,20 @@ test03()
> > while (std::next_permutation(std::begin(cx), std::end(cx)));
> > }
> >
> > +void
> > +test04()
> > +{
> > + int x[] = { 4, 3, 2, 1 };
> > + auto y = std::views::iota(1, 5);
> > + VERIFY( ranges::is_permutation(x, y) );
> > + VERIFY( ranges::is_permutation(y, x) );
> > +}
> > +
> > int
> > main()
> > {
> > test01();
> > test02();
> > test03();
> > + test04();
> > }
> > --
> > 2.34.1
> >
>
