[4.8/4.9 Regression] Infinite loop generated with >=O2

Bug #1395019 reported by Margarita Manterola on 2014-11-21
10
This bug affects 1 person
Affects Status Importance Assigned to Milestone
gcc
Fix Released
Medium
gcc-4.8 (Ubuntu)
Undecided
Unassigned

Bug Description

After some conditional blocks, it's possible that an infinite loop is generated.

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

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://gcc.gnu.org/viewcvs/gcc/branches/gcc-4_8-branch/gcc/tree-vrp.c?view=patch&r1=205608&r2=205607&pathrev=205608

This has already affected a separate package, that needed to workaround the problem:
https://bugs.launchpad.net/ubuntu/+source/krb5/+bug/1347147

And is now causing issues for users that run into this problem as well.

Please apply the patch to the gcc-4.8 version shipped on trusty and on utopic.

CVE References

In , Cj-gcc (cj-gcc) wrote :

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) {
 if (size > sl->capacity) {
  int higher = sl->capacity;
  if (size > (int)MAX_CAPACITY/2) {
   higher = MAX_CAPACITY;
  }
  else {
   while (size > higher) {
    higher *= 2;
   }
  }
  sl->capacity = higher;
  sl->list = lst_realloc(sl->list, sl->capacity);
 }
}

Compiling that:
$ x86_64-pc-linux-gnu-gcc-4.8.2 -Os -S -o test.s test.c

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:
https://gitweb.torproject.org/tor.git/blob/e65b54ec75e3c9e9ada33c8f3ee868d1bea167f5:/src/common/container.c#l61
TOR bug: https://trac.torproject.org/projects/tor/ticket/10259

Reduced by o11c (https://gist.github.com/o11c/7729355) and got help from pinskia.

void smartlist_ensure_capacity(int *capacity, int size) {
  int higher = *capacity;
  if (size > higher) {
    if (size <= 16) {
      while (size > higher) {
 higher *= 2;
      }
    }
  }
}

compiled with -O2, VRP1 seems guilty.

Full runtime testcase:
__attribute__((noinline, noclone)) int
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)
        __builtin_abort ();
      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)
        __builtin_abort ();
    }
  return 0;
}

Started with r188776 or r188780.

In , Rguenth (rguenth) wrote :

I will have a looksee.

Created attachment 31350
gcc49-pr59358.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 , Rguenth (rguenth) wrote :

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).

Author: jakub
Date: Mon Dec 2 22:41:23 2013
New Revision: 205607

URL: http://gcc.gnu.org/viewcvs?rev=205607&root=gcc&view=rev
Log:
 PR tree-optimization/59358
 * tree-vrp.c (union_ranges): To check for the partially
 overlapping ranges or adjacent ranges, also compare *vr0max
 with vr1max.

 * gcc.c-torture/execute/pr59358.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr59358.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

Author: jakub
Date: Mon Dec 2 22:44:05 2013
New Revision: 205608

URL: http://gcc.gnu.org/viewcvs?rev=205608&root=gcc&view=rev
Log:
 PR tree-optimization/59358
 * tree-vrp.c (union_ranges): To check for the partially
 overlapping ranges or adjacent ranges, also compare *vr0max
 with vr1max.

 * gcc.c-torture/execute/pr59358.c: New test.

Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-vrp.c

Fixed.

Author: jakub
Date: Tue Dec 3 07:30:48 2013
New Revision: 205619

URL: http://gcc.gnu.org/viewcvs?rev=205619&root=gcc&view=rev
Log:
 PR tree-optimization/59358
 * tree-vrp.c (union_ranges): To check for the partially
 overlapping ranges or adjacent ranges, also compare *vr0max
 with vr1max.

 * gcc.c-torture/execute/pr59358.c: New test.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.c-torture/execute/pr59358.c

Changed in gcc:
importance: Unknown → Medium
status: Unknown → Fix Released
Matthias Klose (doko) wrote :

please re-check with the gcc-4.8 package in the ubuntu-toolchain-r/ppa PPA. This is a backport candidate for trusty.

Hello Margarita, or anyone else affected,

Accepted gcc-4.8 into trusty-proposed. The package will build now and be available at https://launchpad.net/ubuntu/+source/gcc-4.8/4.8.4-2ubuntu1~14.04 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation how to enable and use -proposed. Your feedback will aid us getting this update out to other Ubuntu users.

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 verification-needed to verification-done. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed. In either case, details of your testing will help us make a better decision.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance!

tags: added: verification-needed
Matthias Klose (doko) wrote :

fixed in 4.8.4-2ubuntu1~14.04

tags: added: verification-done
removed: verification-needed
Launchpad Janitor (janitor) wrote :
Download full text (19.4 KiB)

This bug was fixed in the package gcc-4.8 - 4.8.4-2ubuntu1~14.04

---------------
gcc-4.8 (4.8.4-2ubuntu1~14.04) trusty-proposed; urgency=medium

  * SRU LP: #1311866.
  * Fix PR tree-optimization/63341 (wrong code, rs6000).
  * Allow to turn off -Wformat using Wno-format. LP: #1401836.
  * Fix PR target/60693 (x86, ice on valid code). LP: #1378737.
  * Fix PR tree-optimization/61964 (wrong code). LP: #1347147.
  * Fix GCC miscompilation with boost::asio::io_service::work. LP: #1338693.
  * 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 wrong-code issue in the little endian vector API (ppc64el).
    LP: #1311128.
  * Fix PR tree-optimization/59358 (wrong code). LP: #1395019.
  * 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.

gcc-4.8 (4.8.4-2ubuntu1) vivid; urgency=medium

  * Merge with Debian; remaining changes:
    - Build from the upstream source.

gcc-4.8 (4.8.4-2) unstable; urgency=medium

  * Update to SVN 20150426 (r222448) from the gcc-4_8-branch.
    - Fix PR libstdc++/60966, PR c/61553, PR middle-end/63704,
      PR target/61413 (ARM), PR target/64358 (RS6000), PR target/64479 (SH),
      PR target/64409 (x86), PR rtl-optimization/64037, PR c++/64487,
      PR c++/64251, PR c++/64297, PR fortran/63733, PR fortran/64244,
      PR c/64766, PR target/64882, PR rtl-optimization/61058,
      PR middle-end/43631, PR tree-optimization/64563, PR target/64513,
      PR middle-end/57748, PR middle-end/57748, PR target/64795,
      PR fortran/64528, PR fortran/56867, PR fortran/57023, PR c/57653,
      PR tree-optimization/63844 (OpenMP), PR middle-end/64199 (ice on valid),
      PR tree-optimization/64493 (ice on valid), PR tree-optimization/64495
      (wrong code), PR tree-optimization/56273 (diagnostics),
      PR tree-optimization/59124 (diagnostic), PR tree-optimization/64277
      (diagnostic), PR lto/65015, PR target/65163 (SH), PR target/64113 (ALPHA,
      link failure), PR rtl-optimization/64557, PR rtl-optimization/63475
      (ALPHA, wrong code), PR rtl-optimization/63483 (ALPHA, wrong code),
      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 tree-optimization/61634 (ice on valid), PR target/65196 (AVR),
      PR tree-optimization/63593 (ice on valid),
      PR tree-optimization/65063 (wrong code), PR target/65286 (rs6000),
      PR 65138/target (rs6000), PR target/53988 (SH), PR target/59593 (ARM),
      PR target/64453 (ARM), PR middle-end/65409 (ice on valid),
      PR tree-optimization/65388, PR fortran/65024 (ice),
      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 gcc-4.8 (Ubuntu):
status: New → Fix Released

The verification of the Stable Release Update for gcc-4.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 ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.