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/constrained.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.
> + 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
>
