public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop
@ 2024-03-16 3:55 angelo.landi at outlook dot com
2024-03-16 4:02 ` [Bug libstdc++/114359] " pinskia at gcc dot gnu.org
` (8 more replies)
0 siblings, 9 replies; 10+ messages in thread
From: angelo.landi at outlook dot com @ 2024-03-16 3:55 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
Bug ID: 114359
Summary: std::binomial_distribution hangs in infinite loop
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: angelo.landi at outlook dot com
Target Milestone: ---
Created attachment 57715
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57715&action=edit
minimal example to expose the issue
Due to an integer overflow: in any std::binomial_distribution<IntType>
initialized with 2^n trials with n >= (bit size of IntType) - 2, operator()
will be stuck in the do-while(__reject) loop forever.
The issue was originally found on StackOverflow by user Floyd Everest:
https://stackoverflow.com/questions/75179395/stdbinomial-distribution-hangs-forever-with-certain-inputs/75179982
You can find a more detailed explanation of the issue in my answer to that
post:
https://stackoverflow.com/questions/75179395/stdbinomial-distribution-hangs-forever-with-certain-inputs/75179982#75179982
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
@ 2024-03-16 4:02 ` pinskia at gcc dot gnu.org
2024-03-16 5:08 ` angelo.landi at outlook dot com
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2024-03-16 4:02 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> Due to an integer overflow
Hmm, I don't think this is an integer overflow but rather due to wrapping. Yes
there is a difference as overflow is undefined behavior while wrapping is
defined.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
2024-03-16 4:02 ` [Bug libstdc++/114359] " pinskia at gcc dot gnu.org
@ 2024-03-16 5:08 ` angelo.landi at outlook dot com
2024-03-16 10:10 ` redi at gcc dot gnu.org
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: angelo.landi at outlook dot com @ 2024-03-16 5:08 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
--- Comment #2 from Angelo Landi <angelo.landi at outlook dot com> ---
(In reply to Andrew Pinski from comment #1)
> > Due to an integer overflow
>
> Hmm, I don't think this is an integer overflow but rather due to wrapping.
> Yes there is a difference as overflow is undefined behavior while wrapping
> is defined.
Indeed; separating the cases for unsigned and signed integers, only the first
has the (conditionally) well-defined behaviour described, while the latter has
undefined behaviour.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
2024-03-16 4:02 ` [Bug libstdc++/114359] " pinskia at gcc dot gnu.org
2024-03-16 5:08 ` angelo.landi at outlook dot com
@ 2024-03-16 10:10 ` redi at gcc dot gnu.org
2024-03-16 10:18 ` redi at gcc dot gnu.org
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2024-03-16 10:10 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Last reconfirmed| |2024-03-16
Status|UNCONFIRMED |NEW
Ever confirmed|0 |1
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
` (2 preceding siblings ...)
2024-03-16 10:10 ` redi at gcc dot gnu.org
@ 2024-03-16 10:18 ` redi at gcc dot gnu.org
2024-03-18 13:40 ` redi at gcc dot gnu.org
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2024-03-16 10:18 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This seems to fix it:
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -1503,7 +1503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// sqrt(pi / 2)
const double __spi_2 = 1.2533141373155002512078826424055226L;
_M_s1 = std::sqrt(__np * __1p) * (1 + _M_d1 / (4 * __np));
- _M_s2 = std::sqrt(__np * __1p) * (1 + _M_d2 / (4 * _M_t * __1p));
+ _M_s2 = std::sqrt(__np * __1p) * (1 + _M_d2 / (4 * (_M_t * __1p)));
_M_c = 2 * _M_d1 / __np;
_M_a1 = std::exp(_M_c) * _M_s1 * __spi_2;
const double __a12 = _M_a1 + _M_s2 * __spi_2;
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
` (3 preceding siblings ...)
2024-03-16 10:18 ` redi at gcc dot gnu.org
@ 2024-03-18 13:40 ` redi at gcc dot gnu.org
2024-03-19 16:00 ` cvs-commit at gcc dot gnu.org
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2024-03-18 13:40 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
` (4 preceding siblings ...)
2024-03-18 13:40 ` redi at gcc dot gnu.org
@ 2024-03-19 16:00 ` cvs-commit at gcc dot gnu.org
2024-03-19 16:02 ` redi at gcc dot gnu.org
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2024-03-19 16:00 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
--- Comment #4 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:07e03761a7fc1626a6a74ed957e117f56981558c
commit r14-9551-g07e03761a7fc1626a6a74ed957e117f56981558c
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Mon Mar 18 13:22:17 2024 +0000
libstdc++: Fix infinite loop in std::binomial_distribution [PR114359]
The multiplication (4 * _M_t * __1p) can wraparound to zero if _M_t is
unsigned and 4 * _M_t wraps to zero. The third operand has type double,
so do the second multiplication first, so that we aren't multiplying
integers.
libstdc++-v3/ChangeLog:
PR libstdc++/114359
* include/bits/random.tcc (binomial_distribution::param_type):
Ensure arithmetic is done as type double.
* testsuite/26_numerics/random/binomial_distribution/114359.cc: New
test.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
` (5 preceding siblings ...)
2024-03-19 16:00 ` cvs-commit at gcc dot gnu.org
@ 2024-03-19 16:02 ` redi at gcc dot gnu.org
2024-05-14 9:52 ` cvs-commit at gcc dot gnu.org
2024-05-14 9:56 ` redi at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2024-03-19 16:02 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|--- |12.4
--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk so far.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
` (6 preceding siblings ...)
2024-03-19 16:02 ` redi at gcc dot gnu.org
@ 2024-05-14 9:52 ` cvs-commit at gcc dot gnu.org
2024-05-14 9:56 ` redi at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2024-05-14 9:52 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
--- Comment #6 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:71e941b0e329d3a316e465569c92e08788a68614
commit r13-8771-g71e941b0e329d3a316e465569c92e08788a68614
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Mon Mar 18 13:22:17 2024 +0000
libstdc++: Fix infinite loop in std::binomial_distribution [PR114359]
The multiplication (4 * _M_t * __1p) can wraparound to zero if _M_t is
unsigned and 4 * _M_t wraps to zero. The third operand has type double,
so do the second multiplication first, so that we aren't multiplying
integers.
libstdc++-v3/ChangeLog:
PR libstdc++/114359
* include/bits/random.tcc (binomial_distribution::param_type):
Ensure arithmetic is done as type double.
* testsuite/26_numerics/random/binomial_distribution/114359.cc: New
test.
(cherry picked from commit 07e03761a7fc1626a6a74ed957e117f56981558c)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
` (7 preceding siblings ...)
2024-05-14 9:52 ` cvs-commit at gcc dot gnu.org
@ 2024-05-14 9:56 ` redi at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: redi at gcc dot gnu.org @ 2024-05-14 9:56 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114359
--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 13.3 and 14.1 so far, I still plan to backport this to gcc-12 too.
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2024-05-14 9:56 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-03-16 3:55 [Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop angelo.landi at outlook dot com
2024-03-16 4:02 ` [Bug libstdc++/114359] " pinskia at gcc dot gnu.org
2024-03-16 5:08 ` angelo.landi at outlook dot com
2024-03-16 10:10 ` redi at gcc dot gnu.org
2024-03-16 10:18 ` redi at gcc dot gnu.org
2024-03-18 13:40 ` redi at gcc dot gnu.org
2024-03-19 16:00 ` cvs-commit at gcc dot gnu.org
2024-03-19 16:02 ` redi at gcc dot gnu.org
2024-05-14 9:52 ` cvs-commit at gcc dot gnu.org
2024-05-14 9:56 ` redi at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).