Uploaded image for project: 'Jenkins'
  1. Jenkins
  2. JENKINS-27770

AdvancedQueueSorter call to sort violates the comparison contract

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed (View Workflow)
    • Priority: Minor
    • Resolution: Fixed
    • Component/s: prioritysorter-plugin
    • Labels:
      None
    • Environment:
      java 1.7.0_65, core 1.565.3, prioritysorter-plugin 2.6
    • Similar Issues:

      Description

      At random times, jobs are unable to start builds and several exceptions are thrown in the log:

      Apr 06, 2015 6:32:21 AM hudson.triggers.SafeTimerTask run
      SEVERE: Timer task hudson.model.Queue$MaintainTask@5116dc28 failed
      java.lang.IllegalArgumentException: Comparison method violates its general contract!
              at java.util.TimSort.mergeHi(TimSort.java:868)
              at java.util.TimSort.mergeAt(TimSort.java:485)
              at java.util.TimSort.mergeForceCollapse(TimSort.java:426)
              at java.util.TimSort.sort(TimSort.java:223)
              at java.util.TimSort.sort(TimSort.java:173)
              at java.util.Arrays.sort(Arrays.java:659)
              at java.util.Collections.sort(Collections.java:217)
              at jenkins.advancedqueue.sorter.AdvancedQueueSorter.sortBuildableItems(AdvancedQueueSorter.java:81)
              at hudson.model.Queue.maintain(Queue.java:1021)
              at hudson.model.Queue$MaintainTask.doRun(Queue.java:1994)
              at hudson.triggers.SafeTimerTask.run(SafeTimerTask.java:54)
              at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:471)
              at java.util.concurrent.FutureTask.runAndReset(FutureTask.java:304)
              at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.access$301(ScheduledThreadPoolExecutor.j
      ava:178)
              at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.run(ScheduledThreadPoolExecutor.java:293
      )
              at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
              at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
              at java.lang.Thread.run(Thread.java:745)
      

      The call to sortBuildableItems() calls the java.utils.Collections.sort() which had a change semantics from Java 6 to 7. Specifically there is a contract constraint in compare() that requires that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

      Since any two calls to getInQueueSince() will return different values for any BuildableItem object, it's possible that while the signs maybe the same, the absolute values are not and the exception is thrown.

      // Sort
      Collections.sort(items, new Comparator<BuildableItem>() {
      	public int compare(BuildableItem o1, BuildableItem o2) {
      		float o1weight = getCalculatedWeight(o1);
      		float o2weight = getCalculatedWeight(o2);
      		if (o1weight > o2weight) {
      			return 1;
      		}
      		if (o1weight < o2weight) {
      			return -1;
      		}
      		return (int) (o1.getInQueueSince() - o2.getInQueueSince());
      	}
      });
      

      There is a workaround by disabling timsort and reverting to the Java 6's mergesort using -Djava.util.Arrays.useLegacyMergeSort=true. The problem longterm is that the legacy sorting algorithm might go away in a future release of Java.

      Recommend changing the subtraction operation to a set of comparisons instead.

        Attachments

          Activity

          Hide
          scm_issue_link SCM/JIRA link daemon added a comment -

          Code changed in jenkins
          User: emsa23
          Path:
          src/main/java/jenkins/advancedqueue/sorter/AdvancedQueueSorter.java
          src/test/java/jenkins/advancedqueue/test/BasicTest.java
          http://jenkins-ci.org/commit/priority-sorter-plugin/52b80242c9d6d2781cb2f6c0d79937cee958d07b
          Log:
          JENKINS-27770 Makse sorter adhere to Java 7 compare contract.

          Show
          scm_issue_link SCM/JIRA link daemon added a comment - Code changed in jenkins User: emsa23 Path: src/main/java/jenkins/advancedqueue/sorter/AdvancedQueueSorter.java src/test/java/jenkins/advancedqueue/test/BasicTest.java http://jenkins-ci.org/commit/priority-sorter-plugin/52b80242c9d6d2781cb2f6c0d79937cee958d07b Log: JENKINS-27770 Makse sorter adhere to Java 7 compare contract.
          Hide
          emsa23 Magnus Sandberg added a comment -

          Fixed in 2.11

          Show
          emsa23 Magnus Sandberg added a comment - Fixed in 2.11

            People

            • Assignee:
              emsa23 Magnus Sandberg
              Reporter:
              cfs Charles Stephens
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: