United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-7063674 Wrong results from basic comparisons after calls to Long.bitCount(long)
JDK-7063674 : Wrong results from basic comparisons after calls to Long.bitCount(long)

Details
Type:
Bug
Submit Date:
2011-07-07
Status:
Closed
Updated Date:
2013-07-31
Project Name:
JDK
Resolved Date:
2012-06-16
Component:
hotspot
OS:
linux
Sub-Component:
compiler
CPU:
x86
Priority:
P3
Resolution:
Fixed
Affected Versions:
6u26
Fixed Versions:
hs24 (b14)

Related Reports
Backport:
Backport:
Backport:
Backport:
Backport:
Backport:
Backport:
Backport:
Relates:
Relates:

Sub Tasks

Description
FULL PRODUCT VERSION :
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)

Also occurs on a JDK 7 install we have:
java version "1.7.0"
Java(TM) SE Runtime Environment (build 1.7.0-b147)
Java HotSpot(TM) 64-Bit Server VM (build 21.0-b17, mixed mode)



FULL OS VERSION :
Linux 2.6.18-238.12.1.el5 #1 SMP Tue May 31 13:22:04 EDT 2011 x86_64 x86_64 x86_64 GNU/Linux

EXTRA RELEVANT SYSTEM CONFIGURATION :
Doesn't occur on all CPUs. But we have verified it on:
Quad-Core AMD Opteron(tm) Processor 8347 and Intel(R) Xeon(R) CPU           E5520

A DESCRIPTION OF THE PROBLEM :
After a certain number of calls to a particular method, Math.min() returns the incorrect result. We have made a small test case, where Math.min(1,2) returns 2!!!

Investigating some JVM options we discovered that the problem does not occur when using -XX:-UsePopCountInstruction. Which leads us to believe the problem is related to the use of the Long.bitCount method. If so, this could be a serious security bug, given the amount of bit shifting that goes on in encryption code.

I had tried to simplify the example somewhat, but on smaller examples I didn't observe the problem on JDK7.


THE PROBLEM WAS REPRODUCIBLE WITH -Xint FLAG: No

THE PROBLEM WAS REPRODUCIBLE WITH -server FLAG: Did not try

REGRESSION.  Last worked in version 6

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The attached example has a loop which calls our method with random numbers which it then discards the result of, it then calls the method with known inputs and an expected result. If the result is not the expected one we print out the number of iterations that were correct before this call and the incorrect return value. In addition we hard code a check inside the method the arguments we are testing detect the incorrect behavior, printing out the exact variables involved in the incorrect Math.min call.

Run the example class (PopCountBug) on CPUs which have the pop count instruction, if the bug presents itself then a few lines of output will be written. If the bug does not occur then there will be no output.

$ #here we are using 1.6 update 26, the bug occurs after 6748 iterations
$ #we also print out the values of the problematic variables, and the result of the Math.min call
$ usr/local/java/jdk1.6.0_26/bin/java PopCountBug
scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
6748
3

$ #same thing with an early access JDK 7
$ /usr/local/java/jdk1.7.0/bin/java PopCountBug
scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
6493
3

$ #here we try Java 1.6 update 13, on which the bug does not occur
$ /usr/local/java/jdk1.6.0_13/bin/java PopCountBug

EXPECTED VERSUS ACTUAL BEHAVIOR :
Expected no output
$ usr/local/java/jdk1.6.0_26/bin/java PopCountBug

Actual:
$ usr/local/java/jdk1.6.0_26/bin/java PopCountBug
scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
6748
3
REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;
import java.io.*;
import java.util.zip.*;

public class PopCountBug {

  public static void main(String args[]) throws IOException {
    Random r = new Random(42);
    for (int i = 0; i < 10000000; i++) {
      score(r.nextLong(), r.nextLong(), r.nextLong(), r.nextLong());
      int res = score(19331613728L, 6237928679L, 272696352L, 8385412327L);
      if (res != 2) {
        System.out.println(i);
        System.out.println(res);
        return;
      }
    }
  }

  static final long sMask = (1L << 35) - 1;
  private static int score(final long r0, final long r1, final long template0, final long template1) {
    final long diff = simpleDiff(r0, r1, template0, template1) & sMask;
    final int exactScore = Long.bitCount(diff);
    if (exactScore <= 2) {
      return exactScore;
    }
    final long diffDel = diff & simpleDiff(r0 >>> 1, r1 >>> 1, template0, template1);
    final int scoreDel = Long.bitCount(diffDel);
    final long diffIns = diff & simpleDiff(r0, r1, template0 >>> 1, template1 >>> 1);
    final int scoreIns = Long.bitCount(diffIns);
    final int minA =  Math.min(scoreDel, scoreIns);
    final int bestScore = Math.min(exactScore, minA + 1);
    if (r0 == 19331613728L && bestScore != 2) {
      System.out.println("scoreDel: " + scoreDel + " scoreIns: "+ scoreIns + " min(scoreDel, scoreIns): " + minA);
    }

    return (int) bestScore;
  }

  static long simpleDiff(final long a0, final long a1, final long b0, final long b1) {
    final long diff = (a0 ^ b0) | (a1 ^ b1);
    return diff;
  }
}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Invoking java with -XX:-UsePopCountInstruction prevents the bug from occurring.

                                    

Comments
EVALUATION

http://hg.openjdk.java.net/lambda/lambda/hotspot/rev/ccaa67adfe5b
                                     
2012-06-29
Closed as already verified during 7u40 bug verification process.
                                     
2013-07-31
EVALUATION

Introduced with JDK 7b53:

cthaling@sc14ia03:~$ /java/re/jdk/7/promoted/all/b52/binaries/linux-x64/bin/java -showversion -d64 PopCountBug
java version "1.7.0-ea"
Java(TM) SE Runtime Environment (build 1.7.0-ea-b52)
Java HotSpot(TM) 64-Bit Server VM (build 15.0-b03, mixed mode)

cthaling@sc14ia03:~$ /java/re/jdk/7/promoted/all/b53/binaries/linux-x64/bin/java -showversion -d64 PopCountBug
java version "1.7.0-ea"
Java(TM) SE Runtime Environment (build 1.7.0-ea-b53)
Java HotSpot(TM) 64-Bit Server VM (build 15.0-b04, mixed mode)

scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
5864
3

The bug is also in JDK 6 (introduced in 6u18):

cthaling@sc14ia03:~/hsx/hotspot-comp/7063674/make$ /java/re/jdk/6u17/promoted/latest/binaries/linux-amd64/bin/java -showversion -d64 -XX:-TieredCompilation -cp .. PopCountBug
java version "1.6.0_17"
Java(TM) SE Runtime Environment (build 1.6.0_17-b04)
Java HotSpot(TM) 64-Bit Server VM (build 14.3-b01, mixed mode)

cthaling@sc14ia03:~/hsx/hotspot-comp/7063674/make$ /java/re/jdk/6u18/promoted/latest/binaries/linux-amd64/bin/java -showversion -d64 -XX:-TieredCompilation -cp .. PopCountBug
java version "1.6.0_18"
Java(TM) SE Runtime Environment (build 1.6.0_18-b07)
Java HotSpot(TM) 64-Bit Server VM (build 16.0-b13, mixed mode)

scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
5839
3
                                     
2012-06-11
EVALUATION

I can reproduce this bug with our latest JDK 8 build:

cthaling@sc14ia03:~$ /java/re/jdk/8/promoted/all/b42/binaries/linux-x64/bin/java -showversion -d64 PopCountBug
java version "1.8.0-ea"
Java(TM) SE Runtime Environment (build 1.8.0-ea-b42)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b13, mixed mode)

scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
12306
3
                                     
2012-06-11
EVALUATION

We are scheduling popcnt instructions between compare and branch/conditional move instructions because AD instructs are not defined to kill flags:

  0x00007fd5708e10aa: cmp    %r8d,%r9d
  0x00007fd5708e10ad: popcnt %rcx,%rbp          ;*invokestatic bitCount
                                                ; - PopCountBug::score@76 (line 30)
  0x00007fd5708e10b2: popcnt %r11,%r9           ;*invokestatic bitCount
                                                ; - PopCountBug::score@51 (line 28)
  0x00007fd5708e10b7: cmovl  %r9d,%ebp          ;*invokestatic min

But the Intel Instruction Set Reference says for POPCNT:

Flags Affected
OF, SF, ZF, AF, CF, PF are all cleared. ZF is set if SRC = 0, otherwise ZF is cleared
                                     
2012-06-11
WORK AROUND

-XX:-UsePopCountInstruction
                                     
2012-06-11
EVALUATION

http://hg.openjdk.java.net/hsx/hotspot-comp/hotspot/rev/ccaa67adfe5b
                                     
2012-06-12
EVALUATION

http://hg.openjdk.java.net/hsx/hsx23.2/hotspot/rev/dc333950f54f
                                     
2012-06-19
EVALUATION

Verified:
$ /net/sqenfs-1.us.oracle.com/export1/comp/vm/jdk/hsx/pit/8/fastdebug/linux-amd64/bin/java -showversion -d64 PopCountBug
java version "1.8.0-ea-fastdebug"
Java(TM) SE Runtime Environment (build 1.8.0-ea-fastdebug-b43)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b14-internal-201206152110.amurillo.hs24-b14-snapshot-fastdebug, mixed mode)

$ /java/re/jdk/8/promoted/all/b42/binaries/linux-x64/bin/java -showversion -d64 PopCountBug
java version "1.8.0-ea"
Java(TM) SE Runtime Environment (build 1.8.0-ea-b42)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b13, mixed mode)

scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
14252
3
                                     
2012-06-20



Hardware and Software, Engineered to Work Together