public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc
@ 2020-04-28 14:55 nathan at gcc dot gnu.org
2020-04-28 20:56 ` [Bug libstdc++/94823] " hiraditya at msn dot com
` (9 more replies)
0 siblings, 10 replies; 11+ messages in thread
From: nathan at gcc dot gnu.org @ 2020-04-28 14:55 UTC (permalink / raw)
To: gcc-bugs
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]
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
@ 2020-04-28 20:56 ` hiraditya at msn dot com
2020-04-28 22:36 ` pinskia at gcc dot gnu.org
` (8 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: hiraditya at msn dot com @ 2020-04-28 20:56 UTC (permalink / raw)
To: gcc-bugs
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
```
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
2020-04-28 20:56 ` [Bug libstdc++/94823] " hiraditya at msn dot com
@ 2020-04-28 22:36 ` pinskia at gcc dot gnu.org
2020-04-28 22:40 ` pinskia at gcc dot gnu.org
` (7 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: pinskia at gcc dot gnu.org @ 2020-04-28 22:36 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
2020-04-28 20:56 ` [Bug libstdc++/94823] " hiraditya at msn dot com
2020-04-28 22:36 ` pinskia at gcc dot gnu.org
@ 2020-04-28 22:40 ` pinskia at gcc dot gnu.org
2020-04-29 0:27 ` hiraditya at msn dot com
` (6 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: pinskia at gcc dot gnu.org @ 2020-04-28 22:40 UTC (permalink / raw)
To: gcc-bugs
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).
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (2 preceding siblings ...)
2020-04-28 22:40 ` pinskia at gcc dot gnu.org
@ 2020-04-29 0:27 ` hiraditya at msn dot com
2020-04-29 2:09 ` hiraditya at msn dot com
` (5 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: hiraditya at msn dot com @ 2020-04-29 0:27 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (3 preceding siblings ...)
2020-04-29 0:27 ` hiraditya at msn dot com
@ 2020-04-29 2:09 ` hiraditya at msn dot com
2020-04-29 12:57 ` nathan at gcc dot gnu.org
` (4 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: hiraditya at msn dot com @ 2020-04-29 2:09 UTC (permalink / raw)
To: gcc-bugs
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?
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (4 preceding siblings ...)
2020-04-29 2:09 ` hiraditya at msn dot com
@ 2020-04-29 12:57 ` nathan at gcc dot gnu.org
2020-10-09 14:59 ` redi at gcc dot gnu.org
` (3 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: nathan at gcc dot gnu.org @ 2020-04-29 12:57 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (5 preceding siblings ...)
2020-04-29 12:57 ` nathan at gcc dot gnu.org
@ 2020-10-09 14:59 ` redi at gcc dot gnu.org
2020-10-09 16:05 ` cvs-commit at gcc dot gnu.org
` (2 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: redi at gcc dot gnu.org @ 2020-10-09 14:59 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (6 preceding siblings ...)
2020-10-09 14:59 ` redi at gcc dot gnu.org
@ 2020-10-09 16:05 ` cvs-commit at gcc dot gnu.org
2020-10-09 16:07 ` redi at gcc dot gnu.org
2022-07-21 21:21 ` cvs-commit at gcc dot gnu.org
9 siblings, 0 replies; 11+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2020-10-09 16:05 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (7 preceding siblings ...)
2020-10-09 16:05 ` cvs-commit at gcc dot gnu.org
@ 2020-10-09 16:07 ` redi at gcc dot gnu.org
2022-07-21 21:21 ` cvs-commit at gcc dot gnu.org
9 siblings, 0 replies; 11+ messages in thread
From: redi at gcc dot gnu.org @ 2020-10-09 16:07 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* [Bug libstdc++/94823] modulo arithmetic bug in random.tcc
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
` (8 preceding siblings ...)
2020-10-09 16:07 ` redi at gcc dot gnu.org
@ 2022-07-21 21:21 ` cvs-commit at gcc dot gnu.org
9 siblings, 0 replies; 11+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2022-07-21 21:21 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2022-07-21 21:21 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-04-28 14:55 [Bug libstdc++/94823] New: modulo arithmetic bug in random.tcc nathan at gcc dot gnu.org
2020-04-28 20:56 ` [Bug libstdc++/94823] " hiraditya at msn dot com
2020-04-28 22:36 ` pinskia at gcc dot gnu.org
2020-04-28 22:40 ` pinskia at gcc dot gnu.org
2020-04-29 0:27 ` hiraditya at msn dot com
2020-04-29 2:09 ` hiraditya at msn dot com
2020-04-29 12:57 ` nathan at gcc dot gnu.org
2020-10-09 14:59 ` redi at gcc dot gnu.org
2020-10-09 16:05 ` cvs-commit at gcc dot gnu.org
2020-10-09 16:07 ` redi at gcc dot gnu.org
2022-07-21 21:21 ` cvs-commit 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).