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

Java VM freezes with very simple program

    XMLWordPrintable

    Details

    • Subcomponent:
    • CPU:
      x86_64
    • OS:
      linux

      Description

      FULL PRODUCT VERSION :
      java version "1.8.0_121"
      Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
      Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)


      FULL OS VERSION :
      Peppermint Linux 7 64 bit

      EXTRA RELEVANT SYSTEM CONFIGURATION :
      AMD quad core processor

      A DESCRIPTION OF THE PROBLEM :
      The Java VM freezes two lines after printing "max 10000 => 10" and can only be killed with kill -9. If AWT windows are added to the program, they also freeze.

      This does not happen with similar simple programs.

      THE PROBLEM WAS REPRODUCIBLE WITH -Xint FLAG: No

      THE PROBLEM WAS REPRODUCIBLE WITH -server FLAG: No

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      javac main.java
      java main

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      VM should be killable normally and interruptible with Ctrl+C.
      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.util.*;
      import java.util.zip.*;
      import java.util.List;
      import java.util.regex.*;
      import java.util.concurrent.*;
      import java.util.concurrent.atomic.*;
      import java.util.concurrent.locks.*;
      import javax.swing.*;
      import javax.swing.event.*;
      import javax.swing.text.*;
      import javax.swing.table.*;
      import java.io.*;
      import java.net.*;
      import java.lang.reflect.*;
      import java.lang.ref.*;
      import java.lang.management.*;
      import java.security.*;
      import java.security.spec.*;
      import java.awt.*;
      import java.awt.event.*;
      import java.awt.image.*;
      import javax.imageio.*;
      import java.math.*;
      public class main {


      static int n = 1000000;
      static String a = repeat('a', n) + repeat('b', n);
      static String b = repeat('a', n+10) + repeat('b', n-10);

      public static void main(final String[] args) throws Exception {
        for (int max = 0; max <= 20; max++)
          test(max);
        test(100);
        test(1000);
        test(10000);
        test(100000);
        test(1000000);
        test(10000000);
        test(100000000);
      }

      static void test(int max) {
        long startTime = sysNow();
        System.out.println("max " + max + " => " + leven_limited(a, b, max));
        System.out.println((sysNow()-startTime) + " ms");
      }


      static long sysNow() {
        return System.nanoTime()/1000000;
      }
      static int leven_limited(String left, String right, int threshold) {
        if (--threshold < 0) return 0;

        int n = left.length(); // length of left
        int m = right.length(); // length of right

        // if one string is empty, the edit distance is necessarily the length
        // of the other
        if (n == 0) {
            return m <= threshold ? m : threshold+1;
        } else if (m == 0) {
            return n <= threshold ? n : threshold+1;
        }

        if (n > m) {
            // swap the two strings to consume less memory
            final String tmp = left;
            left = right;
            right = tmp;
            n = m;
            m = right.length();
        }

        int[] p = new int[n + 1]; // 'previous' cost array, horizontally
        int[] d = new int[n + 1]; // cost array, horizontally
        int[] tempD; // placeholder to assist in swapping p and d

        // fill in starting table values
        final int boundary = Math.min(n, threshold) + 1;
        for (int i = 0; i < boundary; i++) {
            p[i] = i;
        }
        // these fills ensure that the value above the rightmost entry of our
        // stripe will be ignored in following loop iterations
        Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
        Arrays.fill(d, Integer.MAX_VALUE);

        // iterates through t
        for (int j = 1; j <= m; j++) {
            final char rightJ = right.charAt(j - 1); // jth character of right
            d[0] = j;

            // compute stripe indices, constrain to array size
            final int min = Math.max(1, j - threshold);
            final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(
                    n, j + threshold);

            // the stripe may lead off of the table if s and t are of different
            // sizes
            if (min > max) {
                return threshold+1;
            }

            // ignore entry left of leftmost
            if (min > 1) {
                d[min - 1] = Integer.MAX_VALUE;
            }

            // iterates through [min, max] in s
            for (int i = min; i <= max; i++) {
                if (left.charAt(i - 1) == rightJ) {
                    // diagonally left and up
                    d[i] = p[i - 1];
                } else {
                    // 1 + minimum of cell to the left, to the top, diagonally
                    // left and up
                    d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
                }
            }

            // copy current distance counts to 'previous row' distance counts
            tempD = p;
            p = d;
            d = tempD;
        }

        // if p[n] is greater than the threshold, there's no guarantee on it
        // being the correct
        // distance
        if (p[n] <= threshold) {
            return p[n];
        }
        return threshold+1;
      }
        static String repeat(char c, int n) {
          n = Math.max(n, 0);
          char[] chars = new char[n];
          for (int i = 0; i < n; i++)
            chars[i] = c;
          return new String(chars);
        }

      }

      ---------- END SOURCE ----------

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                thartmann Tobias Hartmann
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: