FOP-2157: Deadlock in CompareUtil class; patch by Jacopo Cappellato based on original proposal by Morten Knudsen.

git-svn-id: https://svn.apache.org/repos/asf/xmlgraphics/fop/trunk@1630586 13f79535-47bb-0310-9956-ffa450edef68

2 files changed, 120 insertions, 0 deletions

diff --git a/src/java/org/apache/fop/util/CompareUtil.java b/src/java/org/apache/fop/util/CompareUtil.java
index c539ba416..6829336db 100644
--- a/src/java/org/apache/fop/util/CompareUtil.java
+++ b/src/java/org/apache/fop/util/CompareUtil.java
@@ -24,17 +24,39 @@ package org.apache.fop.util;
  */
 public final class CompareUtil {
 
+    private static final Object TIE_LOCK = new Object();
+
     private CompareUtil() {
     }
 
     /**
      * Compares two objects for equality.
+     * In order to prevent lock-ordering deadlocks the following strategy is used:
+     * when two non null objects are passed to the method, the comparison
+     * is done by calling the {@link Object#equals(Object)} method of the object
+     * with the lower hash code ({@link System#identityHashCode(Object)});
+     * in the rare case that two different objects have the same hash code, a lock
+     * is used.
      *
      * @param o1 an object
      * @param o2 another object
      * @return true if either o1 and o2 are null or if o1.equals(o2)
      */
     public static boolean equal(Object o1, Object o2) {
+        int o1Hash = System.identityHashCode(o1);
+        int o2Hash = System.identityHashCode(o1);
+        if (o1Hash == o2Hash && o1 != o2 && o1Hash != 0) {
+            // in the rare case of different objects with the same hash code,
+            // the tieLock object is used to synchronize access
+            synchronized (TIE_LOCK) {
+                return o1.equals(o2);
+            }
+        }
+        if (o1Hash > o2Hash) {
+            Object tmp = o1;
+            o1 = o2;
+            o2 = tmp;
+        }
         return o1 == null ? o2 == null : o1 == o2 || o1.equals(o2);
     }
 
diff --git a/test/java/org/apache/fop/util/CompareUtilTestCase.java b/test/java/org/apache/fop/util/CompareUtilTestCase.java
new file mode 100644
index 000000000..e0f769afc
--- /dev/null
+++ b/test/java/org/apache/fop/util/CompareUtilTestCase.java
@@ -0,0 +1,98 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.util;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Vector;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+
+public class CompareUtilTestCase {
+
+    @Test
+    public void testEqual() {
+        int numberOfParallelThreads = Runtime.getRuntime().availableProcessors();
+        long numberOfEqualOperations = 100;
+        double probabilityOf12 = 0.5;
+
+        ExecutorService executor = Executors.newFixedThreadPool(numberOfParallelThreads);
+
+        final Vector object1 = new Vector();
+        object1.add(new Object());
+        object1.add(new Object());
+        object1.add(new Object());
+        object1.add(new Object());
+        object1.add(new Object());
+        final Vector object2 = new Vector();
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        object2.add(new Object());
+        final boolean areEqual = object1.equals(object2);
+        final AtomicBoolean wrongResult = new AtomicBoolean(false);
+
+        Runnable equal12 = new Runnable() {
+            public void run() {
+                if (areEqual != CompareUtil.equal(object1, object2)) {
+                    wrongResult.set(true);
+                }
+            }
+        };
+        Runnable equal21 = new Runnable() {
+            public void run() {
+                if (areEqual != CompareUtil.equal(object2, object1)) {
+                    wrongResult.set(true);
+                }
+            }
+        };
+
+        List<Future<?>> futures = new ArrayList<Future<?>>();
+        for (int i = 1; i <= numberOfEqualOperations; i++) {
+            Runnable randomTask = Math.random() < probabilityOf12 ? equal12 : equal21;
+            futures.add(executor.submit(randomTask));
+        }
+
+        Exception exception = null;
+        try {
+            for (Future<?> future : futures) {
+                future.get();
+            }
+        } catch (Exception e) {
+            exception = e;
+        }
+
+        assertNull(exception);
+        assertFalse(wrongResult.get());
+    }
+}