[Bug c++/113960] New: std::map with std::vector as input overwrites itself with c++20, on s390x platform

[Bug c++/113960] New: std::map with std::vector as input overwrites itself with c++20, on s390x platform

[miladfarca at gmail dot com]

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

            Bug ID: 113960
           Summary: std::map with std::vector as input overwrites itself
                    with c++20, on s390x platform
           Product: gcc
           Version: 13.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: miladfarca at gmail dot com
  Target Milestone: ---
              Host: s390x
            Target: s390x

```
#include <map>
#include <vector>
#include <iostream>

int main(){
 std::vector<unsigned short> v1 = {1}; 
 std::vector<unsigned short> v2 = {2};

 std::map<std::vector<unsigned short>, int> m;
 m[v1] = 1;
 m[v2] = 2; // this overwrites m[v1]

 std::cout << m.size() << std::endl; // prints 1, should be 2

 return 0;
}

```
Compile with `g++ std=c++20`. Output is correct with c++17. Tested on g++
12.2.1 and g++ 13.2.1

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[sjames at gcc dot gnu.org]

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

Sam James <sjames at gcc dot gnu.org> changed:

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

--- Comment #1 from Sam James <sjames at gcc dot gnu.org> ---
I can reproduce it w/ 13.2.1 20231216 although I'd prefer to leave it to
someone else to confirm...

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2024-02-19
      Known to fail|                            |12.3.0, 13.2.1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
works fine on x86_64-linux.  Confirmed on s390x-linux with

g++-13 (SUSE Linux) 13.2.1 20230912 [revision
b96e66fd4ef3e36983969fb8cdd1956f551a074b]

and

g++-12 (SUSE Linux) 12.3.0

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[stefansf at linux dot ibm.com]

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

--- Comment #3 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
This seems to be a bug in the three way comparison introduced with C++20.  The
bug happens while deciding whether key v2 already exists in the map or not.

template<typename _InputIter1, typename _InputIter2, typename _Comp>
  constexpr auto
  lexicographical_compare_three_way(_InputIter1 __first1,
                                    _InputIter1 __last1,
                                    _InputIter2 __first2,
                                    _InputIter2 __last2,
                                    _Comp __comp)
  -> decltype(__comp(*__first1, *__first2))
  {
    // concept requirements
    __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
    __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
    __glibcxx_requires_valid_range(__first1, __last1);
    __glibcxx_requires_valid_range(__first2, __last2);

    using _Cat = decltype(__comp(*__first1, *__first2));
    static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);

    if (!std::__is_constant_evaluated())
      if constexpr (same_as<_Comp, __detail::_Synth3way>
                    || same_as<_Comp, compare_three_way>)
        if constexpr (__is_byte_iter<_InputIter1>)
          if constexpr (__is_byte_iter<_InputIter2>)
            {
              const auto [__len, __lencmp] = _GLIBCXX_STD_A::
                __min_cmp(__last1 - __first1, __last2 - __first2);
              if (__len)
                {
                  const auto __c
                    = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
                  if (__c != 0)
                    return __c;
                }
              return __lencmp;
            }

__len equals 1 since both vectors have length 1.  However, memcmp should be
called with the number of bytes and not the number of elements of the vector. 
That means memcmp is called with two pointers to MEMs of unsigned shorts 1 and
2 where the high-bytes equal 0 and therefore memcmp returns with 0 on
big-endian targets.  Ultimately __lencmp is returned which itself equals
std::strong_ordering::equal rendering v2 replacing v1.

Fixed by

diff --git a/libstdc++-v3/include/bits/stl_algobase.h
b/libstdc++-v3/include/bits/stl_algobase.h
index d534e02871f..6ebece315f7 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1867,8 +1867,10 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
                  __min_cmp(__last1 - __first1, __last2 - __first2);
                if (__len)
                  {
+                   const auto __len_bytes = __len * sizeof (*first1);
                    const auto __c
-                     = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
+                     = __builtin_memcmp(&*__first1, &*__first2, __len_bytes)
+                       <=> 0;
                    if (__c != 0)
                      return __c;
                  }

Can you give the patch a try?

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[stefansf at linux dot ibm.com]

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

Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jwakely at redhat dot com

--- Comment #4 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
While giving it a second thought maybe something like

const auto __len_bytes
  = __len * std::min (sizeof (*__first1),
                      sizeof (*__first2));

would be more appropriate since AFAICT the types _InputIter1 and _InputIter2
are not related to each other w.r.t. to their pointed size.  Maybe Jonathan can
shed some light on this?

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
But it's guarded by:

        if constexpr (__is_byte_iter<_InputIter1>)
          if constexpr (__is_byte_iter<_InputIter2>)

This condition is only supposed to be true when sizeof(*__first1) == 1 and
sizeof(*__first2) == 1

We can only use memcmp if we're comparing single bytes as unsigned values (and
if the iterators are pointers to contiguous memory, not e.g. segmented
iterators like std::deque's, or not even random access iterators, like
std::list's).

For std::vector<unsigned short> we should not use this code at all.

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[stefansf at linux dot ibm.com]

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

--- Comment #6 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
Guard __is_byte_iter checks for contiguous bytes which I guess is fine for
std::vector and then checks for __is_memcmp_ordered which is fine for
big-endian targets in conjunction with unsigned integers.  From
cpp_type_traits.h we have:

  // Whether memcmp can be used to determine ordering for a type
  // e.g. in std::lexicographical_compare or three-way comparisons.
  // True for unsigned integer-like types where comparing each byte in turn
  // as an unsigned char yields the right result. This is true for all
  // unsigned integers on big endian targets, but only unsigned narrow
  // character types (and std::byte) on little endian targets.
  template<typename _Tp, bool _TreatAsBytes =
#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
        __is_integer<_Tp>::__value
#else
        __is_byte<_Tp>::__value
#endif

Thus using memcmp here is fine, however, I'm still a bit unsure whether we
really have to take the minimum of *__first1 and *__first2 since I haven't
found any size-relation between those types.

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ohhh, I forgot I did that, sorry!

Yeah, the memcmp code wasn't updated to match the different behaviour of
__is_byte_iter for BE.

We can't use memcmp if the sizes are different. We don't want to use the min,
we want to guard that code with the sizes being the same, then we can just use
len*sizeof(*first1) because we know it's the same as sizeof(*first2).

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1824,8 +1824,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
     }

 #if __cpp_lib_three_way_comparison
-  // Iter points to a contiguous range of unsigned narrow character type
-  // or std::byte, suitable for comparison by memcmp.
+  // Iter points to a contiguous range of unsigned narrow character type,
+  // or std::byte, or big-endian unsigned integers, suitable for comparison
+  // by memcmp.
   template<typename _Iter>
     concept __is_byte_iter = contiguous_iterator<_Iter>
       && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
@@ -1879,14 +1880,16 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
        if constexpr (same_as<_Comp, __detail::_Synth3way>
                      || same_as<_Comp, compare_three_way>)
          if constexpr (__is_byte_iter<_InputIter1>)
-           if constexpr (__is_byte_iter<_InputIter2>)
+           if constexpr (__is_byte_iter<_InputIter2>
+                           && sizeof(*__first1) == sizeof(*__first2))
              {
                const auto [__len, __lencmp] = _GLIBCXX_STD_A::
                  __min_cmp(__last1 - __first1, __last2 - __first2);
                if (__len)
                  {
+                   const auto __blen = __len * sizeof(*__first1);
                    const auto __c
-                     = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
+                     = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
                    if (__c != 0)
                      return __c;
                  }

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[stefansf at linux dot ibm.com]

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

--- Comment #9 from Stefan Schulze Frielinghaus <stefansf at linux dot ibm.com> ---
(In reply to Jonathan Wakely from comment #7)
> We can't use memcmp if the sizes are different. We don't want to use the
> min, we want to guard that code with the sizes being the same, then we can
> just use len*sizeof(*first1) because we know it's the same as
> sizeof(*first2).

Hehe I was about to add another comment.  I just confused myself with taking
the minimum but we rather need to ensure that we are walking over same sized
integers.

LGTM

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oh I already defined a __is_memcmp_ordered_with trait, which does the same-size
check. I think that's what should be used here.

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1824,11 +1824,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
     }

 #if __cpp_lib_three_way_comparison
-  // Iter points to a contiguous range of unsigned narrow character type
-  // or std::byte, suitable for comparison by memcmp.
-  template<typename _Iter>
-    concept __is_byte_iter = contiguous_iterator<_Iter>
-      && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
+  // Both iterators refer to contiguous ranges of unsigned narrow characters,
+  // or std::byte, or big-endian unsigned integers, suitable for comparison
+  // using memcmp.
+  template<typename _Iter1, typename _Iter2>
+    concept __memcmp_ordered_with
+      = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
+                                 iter_value_t<_Iter2>>::__value)
+         && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;

   // Return a struct with two members, initialized to the smaller of x and y
   // (or x if they compare equal) and the result of the comparison x <=> y.
@@ -1878,20 +1881,20 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       if (!std::__is_constant_evaluated())
        if constexpr (same_as<_Comp, __detail::_Synth3way>
                      || same_as<_Comp, compare_three_way>)
-         if constexpr (__is_byte_iter<_InputIter1>)
-           if constexpr (__is_byte_iter<_InputIter2>)
-             {
-               const auto [__len, __lencmp] = _GLIBCXX_STD_A::
-                 __min_cmp(__last1 - __first1, __last2 - __first2);
-               if (__len)
-                 {
-                   const auto __c
-                     = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
-                   if (__c != 0)
-                     return __c;
-                 }
-               return __lencmp;
-             }
+         if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
+           {
+             const auto [__len, __lencmp] = _GLIBCXX_STD_A::
+               __min_cmp(__last1 - __first1, __last2 - __first2);
+             if (__len)
+               {
+                 const auto __blen = __len * sizeof(*__first1);
+                 const auto __c
+                   = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
+                 if (__c != 0)
+                   return __c;
+               }
+             return __lencmp;
+           }

       while (__first1 != __last1)
        {

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[miladfarca at gmail dot com]

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

--- Comment #12 from mfarca <miladfarca at gmail dot com> ---
I've applied the above patch directly to
`/usr/include/c++/12/bits/stl_algobase.h` under my fedora 36 env with gcc
12.2.1 and it solved the problem.

[Bug target/113960] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[miladfarca at gmail dot com]

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

--- Comment #13 from mfarca <miladfarca at gmail dot com> ---
Would you please backport this to 12 when the patch lands?

[Bug target/113960] [11/12/13/14 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|std::map with std::vector   |[11/12/13/14 Regression]
                   |as input overwrites itself  |std::map with std::vector
                   |with c++20, on s390x        |as input overwrites itself
                   |platform                    |with c++20, on s390x
                   |                            |platform
   Target Milestone|---                         |11.5

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Yes, definitely.

[Bug target/113960] [11/12/13/14 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org

[Bug target/113960] [11/12/13/14 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[cvs-commit at gcc dot gnu.org]

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

--- Comment #15 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:f5cdda8acb06c20335855ed353ab9a441c12128a

commit r14-9242-gf5cdda8acb06c20335855ed353ab9a441c12128a
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Feb 27 17:50:34 2024 +0000

    libstdc++: Fix conditions for using memcmp in
std::lexicographical_compare_three_way [PR113960]

    The change in r11-2981-g2f983fa69005b6 meant that
    std::lexicographical_compare_three_way started to use memcmp for
    unsigned integers on big endian targets, but for that to be valid we
    need the two value types to have the same size and we need to use that
    size to compute the length passed to memcmp.

    I already defined a __is_memcmp_ordered_with trait that does the right
    checks, std::lexicographical_compare_three_way just needs to use it.

    libstdc++-v3/ChangeLog:

            PR libstdc++/113960
            * include/bits/stl_algobase.h (__is_byte_iter): Replace with ...
            (__memcmp_ordered_with): New concept.
            (lexicographical_compare_three_way): Use __memcmp_ordered_with
            instead of __is_byte_iter. Use correct length for memcmp.
            *
testsuite/25_algorithms/lexicographical_compare_three_way/113960.cc:
            New test.

[Bug target/113960] [11/12/13 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[cvs-commit at gcc dot gnu.org]

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

--- Comment #16 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:3a16060d605a087fb4cf0bc3b53ed93b5875cd62

commit r13-8377-g3a16060d605a087fb4cf0bc3b53ed93b5875cd62
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Feb 27 17:50:34 2024 +0000

    libstdc++: Fix conditions for using memcmp in
std::lexicographical_compare_three_way [PR113960]

    The change in r11-2981-g2f983fa69005b6 meant that
    std::lexicographical_compare_three_way started to use memcmp for
    unsigned integers on big endian targets, but for that to be valid we
    need the two value types to have the same size and we need to use that
    size to compute the length passed to memcmp.

    I already defined a __is_memcmp_ordered_with trait that does the right
    checks, std::lexicographical_compare_three_way just needs to use it.

    libstdc++-v3/ChangeLog:

            PR libstdc++/113960
            * include/bits/stl_algobase.h (__is_byte_iter): Replace with ...
            (__memcmp_ordered_with): New concept.
            (lexicographical_compare_three_way): Use __memcmp_ordered_with
            instead of __is_byte_iter. Use correct length for memcmp.
            *
testsuite/25_algorithms/lexicographical_compare_three_way/113960.cc:
            New test.

    (cherry picked from commit f5cdda8acb06c20335855ed353ab9a441c12128a)

[Bug target/113960] [11/12 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13 Regression]       |[11/12 Regression] std::map
                   |std::map with std::vector   |with std::vector as input
                   |as input overwrites itself  |overwrites itself with
                   |with c++20, on s390x        |c++20, on s390x platform
                   |platform                    |

--- Comment #17 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 13.3 and 14.1 so far ...

[Bug target/113960] [11/12 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[cvs-commit at gcc dot gnu.org]

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

--- Comment #18 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:6f5dcea85a31845ec6f4b6886734b0f02e013718

commit r12-10251-g6f5dcea85a31845ec6f4b6886734b0f02e013718
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Feb 27 17:50:34 2024 +0000

    libstdc++: Fix conditions for using memcmp in
std::lexicographical_compare_three_way [PR113960]

    The change in r11-2981-g2f983fa69005b6 meant that
    std::lexicographical_compare_three_way started to use memcmp for
    unsigned integers on big endian targets, but for that to be valid we
    need the two value types to have the same size and we need to use that
    size to compute the length passed to memcmp.

    I already defined a __is_memcmp_ordered_with trait that does the right
    checks, std::lexicographical_compare_three_way just needs to use it.

    libstdc++-v3/ChangeLog:

            PR libstdc++/113960
            * include/bits/stl_algobase.h (__is_byte_iter): Replace with ...
            (__memcmp_ordered_with): New concept.
            (lexicographical_compare_three_way): Use __memcmp_ordered_with
            instead of __is_byte_iter. Use correct length for memcmp.
            *
testsuite/25_algorithms/lexicographical_compare_three_way/113960.cc:
            New test.

    (cherry picked from commit f5cdda8acb06c20335855ed353ab9a441c12128a)

[Bug target/113960] [11/12 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[redi at gcc dot gnu.org]

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

--- Comment #19 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #17)
> Fixed for 13.3 and 14.1 so far ...

and 12.4 now too.

[Bug target/113960] [11 Regression] std::map with std::vector as input overwrites itself with c++20, on s390x platform

[miladfarca at gmail dot com]

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

--- Comment #20 from mfarca <miladfarca at gmail dot com> ---
Thank you for your help Jonathan.