[4.8/4.9 Regression] Infinite loop generated with >=O2
Affects  Status  Importance  Assigned to  Milestone  

 gcc 
Fix Released

Medium


 gcc4.8 (Ubuntu) 
Undecided

Unassigned 
Bug Description
After some conditional blocks, it's possible that an infinite loop is generated.
See: https:/
This problem was fixed back in December 2013 in the 4.8 branch as well as the trunk branch. However, the trusty package ended up without the fix.
This is the patch that is missing:
https:/
This has already affected a separate package, that needed to workaround the problem:
https:/
And is now causing issues for users that run into this problem as well.
Please apply the patch to the gcc4.8 version shipped on trusty and on utopic.
CVE References
In GCC Bugzilla #59358, Glisse6 (glisse6) wrote :  #2 
void smartlist_
int higher = *capacity;
if (size > higher) {
if (size <= 16) {
while (size > higher) {
higher *= 2;
}
}
}
}
compiled with O2, VRP1 seems guilty.
In GCC Bugzilla #59358, Jakubgcc (jakubgcc) wrote :  #3 
Full runtime testcase:
__attribute_
foo (int *x, int y)
{
int z = *x;
if (y > z && y <= 16)
while (y > z)
z *= 2;
return z;
}
int
main ()
{
int i;
for (i = 1; i < 17; i++)
{
int j = foo (&i, 16);
int k;
if (i >= 8 && i <= 15)
k = 16 + (i  8) * 2;
else if (i >= 4 && i <= 7)
k = 16 + (i  4) * 4;
else if (i == 3)
k = 24;
else
k = 16;
if (j != k)
j = foo (&i, 7);
if (i >= 7)
k = i;
else if (i >= 4)
k = 8 + (i  4) * 2;
else if (i == 3)
k = 12;
else
k = 8;
if (j != k)
}
return 0;
}
In GCC Bugzilla #59358, Jakubgcc (jakubgcc) wrote :  #6 
Created attachment 31350
gcc49pr59358.patch
Untested fix. The problem is with:
Meeting
[INF, y_5(D) + 1] EQUIVALENCES: { z_4 } (1 elements)
and
[INF(OVF), 30]
to
[INF(OVF), y_5(D) + 1] EQUIVALENCES: { } (0 elements)
Found new range for z_1: [INF(OVF), y_5(D) + 1]
Because one of the maximum is symbolic, y_5(D) + 1 and 30 are effectively uncomparable (operand_less_p doesn't return 1 for either order of those).
Apparently union_ranges implicitly assumes certain ordering based on earlier tests, like from
else if ((maxeq  operand_less_p (vr1max, *vr0max) == 1)
&& (mineq  operand_less_p (*vr0min, vr1min) == 1))
being false it assumes that if
else if ((operand_less_p (vr1min, *vr0max) == 1
 operand_equal_p (vr1min, *vr0max, 0))
&& operand_less_p (*vr0min, vr1min) == 1
is true then operand_less_p (*vr0max, vr1max) == 1, but that is not guaranteed.
In GCC Bugzilla #59358, Rguenth (rguenth) wrote :  #7 
Meeting
[INF, y_6(D) + 1] EQUIVALENCES: { z_5 } (1 elements)
and
[INF(OVF), 30]
to
[INF(OVF), y_6(D) + 1] EQUIVALENCES: { } (0 elements)
Found new range for z_1: [INF(OVF), y_6(D) + 1]
is obviously wrong. We run into
else if ((operand_less_p (*vr0min, vr1max) == 1
 operand_equal_p (*vr0min, vr1max, 0))
&& operand_less_p (vr1min, *vr0min) == 1)
{
/* ( [ ) ] or ( )[ ] */
if (*vr0type == VR_RANGE
&& vr1type == VR_RANGE)
*vr0min = vr1min;
where INF < 30 and INF(OVF) < INF. But we have vr0max and vr1max unordered.
Thus we fail to verify that, assuming we've catched this case via
else if ((maxeq  operand_less_p (vr1max, *vr0max) == 1)
&& (mineq  operand_less_p (*vr0min, vr1min) == 1))
{
/* [ ( ) ] or [( ) ] or [ ( )] */
...
else if ((maxeq  operand_less_p (*vr0max, vr1max) == 1)
&& (mineq  operand_less_p (vr1min, *vr0min) == 1))
{
/* ( [ ] ) or ([ ] ) or ( [ ]) */
Fixing that does
Meeting
[INF, y_6(D) + 1] EQUIVALENCES: { z_5 } (1 elements)
and
[INF(OVF), 30]
to
VARYING
optimally we'd be able to extract a conservative integer range from
the symbolic range  [INF, +INF  1] in this case  and meet them
to [INF(OVF), +INF  1] (assuming that y_6 did not overflow).
In GCC Bugzilla #59358, Jakubgcc (jakubgcc) wrote :  #8 
Author: jakub
Date: Mon Dec 2 22:41:23 2013
New Revision: 205607
URL: http://
Log:
PR treeoptimizati
* treevrp.c (union_ranges): To check for the partially
overlapping ranges or adjacent ranges, also compare *vr0max
with vr1max.
* gcc.ctorture/
Added:
trunk/
Modified:
trunk/
trunk/
trunk/
In GCC Bugzilla #59358, Jakubgcc (jakubgcc) wrote :  #9 
Author: jakub
Date: Mon Dec 2 22:44:05 2013
New Revision: 205608
URL: http://
Log:
PR treeoptimizati
* treevrp.c (union_ranges): To check for the partially
overlapping ranges or adjacent ranges, also compare *vr0max
with vr1max.
* gcc.ctorture/
Modified:
branches/
branches/
branches/
In GCC Bugzilla #59358, Jakubgcc (jakubgcc) wrote :  #11 
Author: jakub
Date: Tue Dec 3 07:30:48 2013
New Revision: 205619
URL: http://
Log:
PR treeoptimizati
* treevrp.c (union_ranges): To check for the partially
overlapping ranges or adjacent ranges, also compare *vr0max
with vr1max.
* gcc.ctorture/
Added:
branches/
Changed in gcc:  
importance:  Unknown → Medium 
status:  Unknown → Fix Released 
Matthias Klose (doko) wrote :  #12 
please recheck with the gcc4.8 package in the ubuntu
Hello Margarita, or anyone else affected,
Accepted gcc4.8 into trustyproposed. The package will build now and be available at https:/
Please help us by testing this new package. See https:/
If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, and change the tag from verificationneeded to verificationdone. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification
Further information regarding the verification process can be found at https:/
tags:  added: verificationneeded 
Matthias Klose (doko) wrote :  #14 
fixed in 4.8.42ubuntu1~
tags: 
added: verificationdone removed: verificationneeded 
Launchpad Janitor (janitor) wrote :  #15 
This bug was fixed in the package gcc4.8  4.8.42ubuntu1~

gcc4.8 (4.8.4
* SRU LP: #1311866.
* Fix PR treeoptimizati
* Allow to turn off Wformat using Wnoformat. LP: #1401836.
* Fix PR target/60693 (x86, ice on valid code). LP: #1378737.
* Fix PR treeoptimizati
* Fix GCC miscompilation with boost::
* Fix PR target/61208 (POWER, wrong code). LP: #1322287.
* Fix ABI incompatibility between POWER and Z HTM builtins and intrinsics.
LP: #1320292.
* Fix PR c++/61046 (ice on invalid code). LP: #1313102.
* Fix wrongcode issue in the little endian vector API (ppc64el).
LP: #1311128.
* Fix PR treeoptimizati
* Fix ice on ARM32. LP: #1268893.
* Don't apply the backport for PR61841 for trusty, causing link failures.
* Fix wrong code for vector doubleword extract (POWER). LP: #1437467.
gcc4.8 (4.8.42ubuntu1) vivid; urgency=medium
* Merge with Debian; remaining changes:
 Build from the upstream source.
gcc4.8 (4.8.42) unstable; urgency=medium
* Update to SVN 20150426 (r222448) from the gcc4_8branch.
 Fix PR libstdc++/60966, PR c/61553, PR middleend/63704,
PR target/61413 (ARM), PR target/64358 (RS6000), PR target/64479 (SH),
PR target/64409 (x86), PR rtloptimizatio
PR c++/64251, PR c++/64297, PR fortran/63733, PR fortran/64244,
PR c/64766, PR target/64882, PR rtloptimizatio
PR middleend/43631, PR treeoptimizati
PR middleend/57748, PR middleend/57748, PR target/64795,
PR fortran/64528, PR fortran/56867, PR fortran/57023, PR c/57653,
PR treeoptimizati
PR treeoptimizati
(wrong code), PR treeoptimizati
PR treeoptimizati
(diagnostic), PR lto/65015, PR target/65163 (SH), PR target/64113 (ALPHA,
link failure), PR rtloptimizatio
(ALPHA, wrong code), PR rtloptimizatio
PR target/64452 (AVR), PR target/64387 (x86, ice on valid),
PR target/64979 (wrong code), PR target/64580 (rs6000),
PR fortran/63744 (rejects valid), PR lto/65193 (ice on valid),
PR treeoptimizati
PR treeoptimizati
PR treeoptimizati
PR 65138/target (rs6000), PR target/53988 (SH), PR target/59593 (ARM),
PR target/64453 (ARM), PR middleend/65409 (ice on valid),
PR treeoptimizati
PR fortran/60898 (ice on valid), PR fortran/61138, PR libgfortran/60956,
PR libstdc++/65279, PR libstdc++/65543, PR target/65849, PR target/65456,
PR target/65787, PR c++/65727, PR c++/65721, PR fortran/56674,
PR fortran/58813, PR fortran/590...
Changed in gcc4.8 (Ubuntu):  
status:  New → Fix Released 
The verification of the Stable Release Update for gcc4.8 has completed successfully and the package has now been released to updates. Subsequently, the Ubuntu Stable Release Updates Team is being unsubscribed and will not receive messages about this bug report. In the event that you encounter a regression using the package from updates please report a new bug using ubuntubug and tag the bug report regressionupdate so we can easily find any regressions.
So, we have the following code:
void *lst_realloc(void *, int);
typedef struct smartlist_t {
void **list;
int num_used;
int capacity;
} smartlist_t;
#define MAX_CAPACITY 32
void smartlist_ensure_capacity(smartlist_t *sl, int size) {CAPACITY/2) {sl>list, sl>capacity);
if (size > sl>capacity) {
int higher = sl>capacity;
if (size > (int)MAX_
higher = MAX_CAPACITY;
}
else {
while (size > higher) {
higher *= 2;
}
}
sl>capacity = higher;
sl>list = lst_realloc(
}
}
Compiling that:pclinuxgnugcc4.8.2 Os S o test.s test.c
$ x86_64
Gives:
pushq %rbx
cmpl 12(%rdi), %esi
movq %rdi, %rbx
jle .L1
cmpl $16, %esi
jg .L3
.L4:
jmp .L4 < unexpected infinite loop if size <= capacity/2
.L3:
movl $32, 12(%rdi)
movq (%rdi), %rdi
movl $32, %esi
call lst_realloc
movq %rax, (%rbx)
.L1:
popq %rbx
ret
Originally from the smartlist_ensure_capacity() function from TOR:/gitweb.torproject.org/tor.git/blob/e65b54ec75e3c9e9ada33c8f3ee868d1bea167f5:/src/common/container.c#l61 /trac.torproject.org/projects/tor/ticket/10259
https:/
TOR bug: https:/
Reduced by o11c (https://gist.github.com/o11c/7729355 ) and got help from pinskia.