[Bug libstdc++/60037] New: SIGFPE in std::generate_canonical<unsigned int...>

[Bug libstdc++/60037] New: SIGFPE in std::generate_canonical<unsigned int...>

[ppluzhnikov at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

            Bug ID: 60037
           Summary: SIGFPE in std::generate_canonical<unsigned int...>
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ppluzhnikov at google dot com

When
libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/operators/values.cc
is built with -O0, I get a crash:

Program received signal SIGFPE, Arithmetic exception.
0x0000000000401b07 in std::generate_canonical<unsigned int, 32ul,
std::mersenne_twister_engine<unsigned long, 32ul, 624ul, 397ul, 31ul,
2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul,
1812433253ul> > (__urng=...)
    at
/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/random.tcc:3480
3480          return __sum / __tmp;
(gdb) bt
#0  0x0000000000401b07 in std::generate_canonical<unsigned int, 32ul,
std::mersenne_twister_engine<unsigned long, 32ul, 624ul, 397ul, 31ul,
2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul,
1812433253ul> > (__urng=...)
    at
/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/random.tcc:3480
#1  0x00000000004018d9 in
std::__detail::_Adaptor<std::mersenne_twister_engine<unsigned long, 32ul,
624ul, 397ul, 31ul, 2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul,
4022730752ul, 18ul, 1812433253ul>, unsigned int>::operator()
(this=0x7fffffff9020)
    at /build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/random.h:190
#2  0x0000000000401785 in __gnu_cxx::hypergeometric_distribution<unsigned
int>::operator()<std::mersenne_twister_engine<unsigned long, 32ul, 624ul,
397ul, 31ul, 2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul,
4022730752ul, 18ul, 1812433253ul> > (
    this=0x7fffffffab40, __urng=..., __param=...) at
/gcc-svn/libstdc++-v3/include/ext/random.tcc:1328
#3  0x00000000004016fb in __gnu_cxx::hypergeometric_distribution<unsigned
int>::operator()<std::mersenne_twister_engine<unsigned long, 32ul, 624ul,
397ul, 31ul, 2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul,
4022730752ul, 18ul, 1812433253ul> > (
    this=0x7fffffffab40, __urng=...) at
/gcc-svn/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/ext/random:3016
#4  0x0000000000401642 in
std::_Bind<__gnu_cxx::hypergeometric_distribution<unsigned int>
(std::mersenne_twister_engine<unsigned long, 32ul, 624ul, 397ul, 31ul,
2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul,
1812433253ul>)>::__call<unsigned int, , 0ul>(std::tuple<>&&,
std::_Index_tuple<0ul>) (this=0x7fffffffab40, __args=<unknown type in
/gcc-svn/build/x86_64-unknown-linux-gnu/libstdc++-v3/testsuite/./values.exe, CU
0x0, DIE 0x445d>)
    at
/gcc-svn/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/functional:1264
#5  0x0000000000401578 in
std::_Bind<__gnu_cxx::hypergeometric_distribution<unsigned int>
(std::mersenne_twister_engine<unsigned long, 32ul, 624ul, 397ul, 31ul,
2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul,
1812433253ul>)>::operator()<, unsigned int>() (this=0x7fffffffab40) at
/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/functional:1323
#6  0x0000000000400d4c in __gnu_test::testDiscreteDist<100ul, 100000ul,
std::_Bind<__gnu_cxx::hypergeometric_distribution<>(std::mersenne_twister_engine<long
unsigned int, 32ul, 624ul, 397ul, 31ul, 2567483615ul, 11ul, 4294967295ul, 7ul,
2636928640ul, 15ul, 4022730752ul, 18ul, 1812433253ul>)>,
test01()::<lambda(int)>
>(std::_Bind<__gnu_cxx::hypergeometric_distribution<unsigned
int>(std::mersenne_twister_engine<long unsigned int, 32ul, 624ul, 397ul, 31ul,
2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul,
1812433253ul>)> &, <lambda(int)>) (f=..., pdf=...) at
/gcc-svn/libstdc++-v3/testsuite/util/testsuite_random.h:50
#7  0x0000000000400aa9 in test01 () at
/gcc-svn/libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/operators/values.cc:42
#8  0x0000000000400b72 in main () at
/gcc-svn/libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/operators/values.cc:58


AFAICT, this is happening because:

3461      template<typename _RealType, size_t __bits,
3462           typename _UniformRandomNumberGenerator>
3463        _RealType
3464        generate_canonical(_UniformRandomNumberGenerator& __urng)
3465        {
3466          const size_t __b
3467        =
std::min(static_cast<size_t>(std::numeric_limits<_RealType>::digits),
3468                       __bits);
3469          const long double __r = static_cast<long double>(__urng.max())
3470                    - static_cast<long double>(__urng.min()) + 1.0L;
3471          const size_t __log2r = std::log(__r) / std::log(2.0L);
3472          size_t __k = std::max<size_t>(1UL, (__b + __log2r - 1UL) /
__log2r);
3473          _RealType __sum = _RealType(0);
3474          _RealType __tmp = _RealType(1);
3475          for (; __k != 0; --__k)
3476        {
3477          __sum += _RealType(__urng() - __urng.min()) * __tmp;
3478          __tmp *= __r;
3479        }
3480          return __sum / __tmp;
3481        }
3482
3483    _GLIBCXX_END_NAMESPACE_VERSION
3484    } // namespace

at line 3475, we have __r=4294967296, __tmp=1, __k=1.

On line 3478, __tmp (which is unsigned int) overflows and becomes 0,
and on line 3480 we divide by zero and get SIGFPE.

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[ppluzhnikov at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

--- Comment #1 from ppluzhnikov at gcc dot gnu.org ---
Author: ppluzhnikov
Date: Mon Feb  3 06:48:48 2014
New Revision: 207416

URL: http://gcc.gnu.org/viewcvs?rev=207416&root=gcc&view=rev
Log:
xfail ext/random/hypergeometric_distribution/operators/values.cc due to
PR 60037: SIGFPE when the test is built without optimization.

Modified:
   
branches/google/main/contrib/testsuite-management/x86_64-grtev4-linux-gnu.xfail

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[ro at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

Rainer Orth <ro at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-02-07
                 CC|                            |ro at gcc dot gnu.org
            Version|unknown                     |4.9.0
   Target Milestone|---                         |4.9.0
     Ever confirmed|0                           |1

--- Comment #2 from Rainer Orth <ro at gcc dot gnu.org> ---
I'm seeing the same on Solaris 10 and 11/x86.

  Rainer

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
ubsan sees it too

/home/jwakely/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/random.tcc:3480:20:
runtime error: division by zero
FAIL: ext/random/hypergeometric_distribution/operators/values.cc execution test

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
clang's ubsan finds two errors

/home/jwakely/src/gcc/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/random.tcc:3478:
runtime error: value 4.29497e+09 is outside the range of representable values
of type 'unsigned int'
/home/jwakely/src/gcc/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/bits/random.tcc:3480:20:
runtime error: division by zero

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

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

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ed, could you take a look at this please?

These testcases are invalid as std::generate_canonical must be instantiated for
floating-point types, not unsigned int:

ext/random/hypergeometric_distribution/operators/serialize.cc
ext/random/hypergeometric_distribution/operators/values.cc

Do we need a new __generate_canonical for int types?

Also, we should fix all the bogus references to clauses in the standard for the
non-standard distributions:

---
a/libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/operators/equal.cc
+++
b/libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/operators/equal.cc
@@ -20,7 +20,7 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.

-// 26.5.8.4.5 Class template rice_distribution [rand.dist.ext.hypergeometric]
+// Class template hypergeometric_distribution

 #include <ext/random>
 #include <testsuite_hooks.h>

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60037

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.0                       |4.9.1

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.0 has been released

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.1                       |4.9.2

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.1 has been released.

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |3dw4rd at verizon dot net

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> ---
To further clarify, the problem is that hypergeometric_distribution is using:

    std::__detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
      __aurng(__urng);

where result_type is an *integer* type, and that is not Ok, because _Adaptor
just forwards to generate_canonical, which wants a *floting point* type as
first template argument. I suspect that something as simple as:

    std::__detail::_Adaptor<_UniformRandomNumberGenerator, double>
      __aurng(__urng);

could be most of the fix (in a couple other places, for discrete distributions,
I ended up using _Adaptor exactly like that) but the implementor (ie, Ed) of
hypergeometric_distribution should really look into it.

Eventually, we should remember to add a static_assert to _Adaptor of the form:

       static_assert(std::is_floating_point<_DInputType>::value,
            "template argument not a floating point type");

Ed, can you please have a look?

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[paolo.carlini at oracle dot com]

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

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> ---
In fact, eventually, we should add the static_assert to generate_canonical too.

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[emsr at gcc dot gnu.org]

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

--- Comment #10 from emsr at gcc dot gnu.org ---
Lookng.  Sorry I was AFK for a while.

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[emsr at gcc dot gnu.org]

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

--- Comment #11 from emsr at gcc dot gnu.org ---
Patch posted.

I must have been nuts.

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[emsr at gcc dot gnu.org]

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

--- Comment #12 from emsr at gcc dot gnu.org ---
Author: emsr
Date: Tue Jul 29 14:56:45 2014
New Revision: 213207

URL: https://gcc.gnu.org/viewcvs?rev=213207&root=gcc&view=rev
Log:
2014-07-29  Ed Smith-Rowland  <3dw4rd@verizon.net>

    PR libstdc++/60037 - SIGFPE in std::generate_canonical<unsigned int...>
    * include/bits/random.h (_Adaptor): static_assert for non floating-point
    result type.
    * include/bits/random.tcc (generate_canonical): Ditto.
    * include/ext/random.tcc (hypergeometric_distribution::operator()):
    Use double as a rng result type.
    * testsuite/26_numerics/random/pr60037-neg.cc: New.
    * testsuite/ext/random/hypergeometric_distribution/pr60037.cc: New.


Added:
    trunk/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
   
trunk/libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/pr60037.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/random.h
    trunk/libstdc++-v3/include/bits/random.tcc
    trunk/libstdc++-v3/include/ext/random.tcc

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[emsr at gcc dot gnu.org]

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

emsr at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #13 from emsr at gcc dot gnu.org ---
Fixed on trunk.

OK also for 4.9?

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[redi at gcc dot gnu.org]

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

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Yes, OK for 4.9 - thanks again

[Bug libstdc++/60037] SIGFPE in std::generate_canonical<unsigned int...>

[emsr at gcc dot gnu.org]

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

--- Comment #15 from emsr at gcc dot gnu.org ---
Author: emsr
Date: Wed Jul 30 00:25:17 2014
New Revision: 213231

URL: https://gcc.gnu.org/viewcvs?rev=213231&root=gcc&view=rev
Log:
2014-07-29  Ed Smith-Rowland  <3dw4rd@verizon.net>

    PR libstdc++/60037 - SIGFPE in std::generate_canonical<unsigned int...>
    * include/bits/random.h (_Adaptor): static_assert for non floating-point
    result type.
    * include/bits/random.tcc (generate_canonical): Ditto.
    * include/ext/random.tcc (hypergeometric_distribution::operator()):
    Use double as a rng result type.
    * testsuite/26_numerics/random/pr60037-neg.cc: New.
    * testsuite/ext/random/hypergeometric_distribution/pr60037.cc: New.


Added:
   
branches/gcc-4_9-branch/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
   
branches/gcc-4_9-branch/libstdc++-v3/testsuite/ext/random/hypergeometric_distribution/pr60037.cc
Modified:
    branches/gcc-4_9-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_9-branch/libstdc++-v3/include/bits/random.h
    branches/gcc-4_9-branch/libstdc++-v3/include/bits/random.tcc
    branches/gcc-4_9-branch/libstdc++-v3/include/ext/random.tcc