[Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc

[Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc

[nathan at gcc dot gnu.org]

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

            Bug ID: 94823
           Summary: modulo arithmetic bug in random.tcc
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: nathan at gcc dot gnu.org
  Target Milestone: ---

I think there's a bug in libstdc++v3/include/bits/random.tcc, found by ubsan's
(over conservative) unsigned overflow checker.  This time, a true positive.

there's a bunch of code like:

 for (size_t __k = 0; __k < __m; ++__k)
        {
          _Type __arg = (__begin[__k % __n]
                         ^ __begin[(__k + __p) % __n]
                         ^ __begin[(__k - 1) % __n]); // this line

... calculate stuff
          __begin[(__k + __p) % __n] += __r1;
          __begin[(__k + __q) % __n] += __r2;
          __begin[__k % __n] = __r2;
        } 

AFAICT we're treating __begin as a circular buffer length __n.  __n has no
special properties.  The marked line is presuming that '(V mod 2^n) mod __n' is
the same as '(V mod __n)'  which is not true in general.  In particular when
__k is zero we're taking '(2^64 - 1) mod __n', which is not necessarily __n -
1, the last position in the buffer, right?

I don't know if the prior line __k + __p can overflow too. If it can't then I
think the marked line should be:
   __begin[(__k + __n - 1) % __n]

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[hiraditya at msn dot com]

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

AK <hiraditya at msn dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hiraditya at msn dot com

--- Comment #1 from AK <hiraditya at msn dot com> ---
Here's the partial stack trace in case it helps

```
in bits/random.tcc:3274:20: runtime error: unsigned integer overflow: 0 - 1
cannot be represented in type 'unsigned long'

in void std::seed_seq::generate<unsigned int*>(unsigned int*, unsigned int*) 

in std::enable_if<std::is_class<std::seed_seq>::value, void>::type
__gnu_cxx::simd_fast_mersenne_twister_engine<unsigned int, 19937ul, 122ul,
18ul, 1ul, 11ul, 1ul, 3758096367u, 3724462975u, 3220897791u, 3221225462u, 1u,
0u, 0u, 331998852u>::seed<std::seed_seq>(std::seed_seq&) ext/random.tcc:110

in __gnu_cxx::simd_fast_mersenne_twister_engine<unsigned int, 19937ul, 122ul,
18ul, 1ul, 11ul, 1ul, 3758096367u, 3724462975u, 3220897791u, 3221225462u, 1u,
0u, 0u, 331998852u>::simd_fast_mersenne_twister_engine<std::seed_seq,
void>(std::seed_seq&) ext/random:104
```

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |WONTFIX
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note there are two loops here where we could have an issue but ....

In the first loop, it is ok usage because __k will be only 0 when the array
will be filled with the same data (0x8b8b8b8bu) so that usage does not matter.

The second loop is where it might matter but __k will never be 0 as __m is will
either be greater than or equal to __n.

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
>In particular when __k is zero we're taking '(2^64 - 1) mod __n', which is not necessarily __n - 1, the last position in the buffer, right?

Yes that is correct except when __k is 0, then __begin will the same values so
it does not matter in the end ...
      std::fill(__begin, __end, _Type(0x8b8b8b8bu));

.....
      for (size_t __k = 0; __k < __m; ++__k)
        {
          _Type __arg = (__begin[__k % __n]
                         ^ __begin[(__k + __p) % __n]
                         ^ __begin[(__k - 1) % __n]);

So when __k == 0, then all three of those loads will be _Type(0x8b8b8b8bu)
really; no matter what the values of __n, __p will be.

So it does not matter in the end.

The rest will be similar.

__n can never be 0 because of:
      if (__begin == __end)
        return;

If __n is a value which is greater than SSIZE_MAX, that would be an undefined
case (__begin  > __end).

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[hiraditya at msn dot com]

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

--- Comment #4 from AK <hiraditya at msn dot com> ---
Makes sense. Thanks for the explanation.

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[hiraditya at msn dot com]

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

--- Comment #5 from AK <hiraditya at msn dot com> ---
> So when __k == 0, then all three of those loads will be _Type(0x8b8b8b8bu) really; no matter what the values of __n, __p will be.


Will it be a good idea to add the explanation in comments, as this may be
tricky for someone to comprehend in future?

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[nathan at gcc dot gnu.org]

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

Nathan Sidwell <nathan at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |NEW
   Last reconfirmed|                            |2020-04-29
     Ever confirmed|0                           |1
         Resolution|WONTFIX                     |---

--- Comment #6 from Nathan Sidwell <nathan at gcc dot gnu.org> ---
Reopening. Such subtlety should be commented upon in the code.

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Despite the code being correct, I think it would be better to hoist this branch
out of the loop:

          if (__k == 0)
            __r2 += __s;
          else if (__k <= __s)
            __r2 += __kn + _M_v[__k - 1];
          else
            __r2 += __kn;

We can do the k=0 case first, where we know that (k+p)%n==p and (k+q)%n==q,
and we also know that for that first iteration begin[0]^begin[q]^begin[n-1] is
simply 0x8b8b8b8bu because every element has that value:

    // k == 0, every element in [begin,end) equals 0x8b8b8b8bu
      {
        uint_least32_t __r1 = 1371501266u;
        uint_least32_t __r2 = __r1 + __s;
        __begin[__p] += __r1;
        __begin[__q] += __r2;
        __begin[0] = __r2;
      }

The we can loop up to __s+1

    for (size_t __k = 1; __k <= __s; ++__k)
      ...

And then up to m

    for (size_t __k = __s + 1; __k < __m; ++__k)
      ...

This unasks the question of whether begin[-1ul % n] is the right element or has
the right value.

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS 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:3ee44d4c518d61c6bbf75fcf280edc6ce5326ce0

commit r11-3759-g3ee44d4c518d61c6bbf75fcf280edc6ce5326ce0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Oct 9 16:10:31 2020 +0100

    libstdc++: Fix incorrect results in std::seed_seq::generate [PR 97311]

    This ensures that intermediate results are done in uint32_t values,
    meeting the requirement for operations to be done modulo 2^32.

    If the target doesn't define __UINT32_TYPE__ then substitute uint32_t
    with a class type that uses uint_least32_t and masks the value to
    UINT32_MAX.

    I've also split the first loop that goes from k=0 to k<m into three
    loops, for k=0, [1,s] and [s+1,m). This avoids branching for those three
    cases in the body of the loop, and also avoids the concerns in PR 94823
    regarding the k-1 index when k==0.

    libstdc++-v3/ChangeLog:

            PR libstdc++/97311
            * include/bits/random.tcc (seed_seq::generate): Use uint32_t for
            calculations. Also split the first loop into three loops to
            avoid branching on k on every iteration, resolving PR 94823.
            * testsuite/26_numerics/random/seed_seq/97311.cc: New test.
            * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-erro
            line number.

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for gcc 11.

[Bug libstdc++/94823] modulo arithmetic bug in random.tcc

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

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

commit r13-1783-gdf118d7ba138cacb17203d4a1b5f27730347cc77
Author: Jason Merrill <jason@redhat.com>
Date:   Wed Jul 20 18:15:31 2022 -0400

    c++: defaulted ctor with DMI in union [PR94823]

    CWG2084 clarifies that a variant member with a non-trivial constructor does
    not make the union's defaulted default constructor deleted if another
    variant member has a default member initializer.

            DR 2084
            PR c++/94823

    gcc/cp/ChangeLog:

            * method.cc (walk_field_subobs): Fix DMI in union case.

    gcc/testsuite/ChangeLog:

            * g++.dg/cpp0x/nsdmi-union7.C: New test.