Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8029060

BigInteger.pow can run arbitrarily long

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: P3
    • Resolution: Duplicate
    • Affects Version/s: 7u25
    • Fix Version/s: 8
    • Component/s: core-libs
    • Labels:

      Description

      FULL PRODUCT VERSION :
      java version "1.7.0_09-icedtea"
      OpenJDK Runtime Environment (amzn-2.3.8.0.22.amzn1-i386)
      OpenJDK Client VM (build 23.7-b01, mixed mode, sharing)


      ADDITIONAL OS VERSION INFORMATION :
      OS X 10.8.5
      Linux 3.2.20-1.29.6.amzn1.i686 #1 SMP Tue Jun 12 01:20:33 UTC 2012 i686 i686 i386 GNU/Linux


      A DESCRIPTION OF THE PROBLEM :
      When BigInteger.pow() is running with large arguments, e.g. BigInteger.valueOf(5).pow(100000000), the JVM appears to freeze. After a while, no threads make visible progress (e.g. log output ceases, no response to network requests). There is no output to the GC log, and kill -3 does not produce any output.

      After investigation, my theory is that JVM is not inserting safepoint checks in the multiplication code. As pow() works its way up to large numbers, each multiplication step can take arbitrarily long (e.g. many minutes) without reaching a safepoint. This blocks GC as well as kill -3 stack trace collection, leaving the JVM in an effectively hung state.

      This is a very nasty bug because it is almost impossible to diagnose. Once the system is stuck, I have not identified any means for collecting stack traces or other information to narrow down the problem.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Simply execute the attached code.

      This code launches a background thread which waits 5 seconds and then starts an enormous BigInteger computation. In the foreground, it then repeatedly allocates a series of 100,000 1K blocks, logging the elapsed time for each 100MB series. During the 5 second period, each 100MB series runs in about 20 milliseconds on my MacBook Pro. Once the BigInteger computation begins, we begin to see long pauses interleaved. In one test, the pauses were successively 175ms, 997ms, 2927ms, 4222ms, and 22617ms (at which point I aborted the test). This is consistent with BigInteger.pow() invoking a series of ever-larger multiply operations, each taking successively longer to reach a safepoint.




      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The foreground thread should execute at a steady pace. The background computation is not allocating much memory, so it should have no impact (other than to compete for CPU time).
      ACTUAL -
      As described above: GC pause times increases rapidly as the BigInteger.pow() computation progresses.

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      // Spawn a background thread to compute an enormous number.
      new Thread(){ @Override public void run() {
        try {
          Thread.sleep(5000);
        } catch (InterruptedException ex) {
        }
        BigInteger.valueOf(5).pow(100000000);
      }}.start();

      // Loop, allocating memory and periodically logging progress, so illustrate GC pause times.
      byte[] b;
      for (int outer = 0; ; outer++) {
        long startMs = System.currentTimeMillis();
        for (int inner = 0; inner < 100000; inner++) {
          b = new byte[1000];
        }

        System.out.println("Iteration " + outer + " took " + (System.currentTimeMillis() - startMs) + " ms");
      }
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      No workaround, other than being careful never to force BigInteger to multiply large values.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              bpb Brian Burkhalter
              Reporter:
              alanb Alan Bateman
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: