Work around MyersDiff infinite loop in PatchListLoader

This infinite loop is happening for some files when the PatchListLoader
is computing the differences between 2 commits. It first showed up[1] in
the mergeability checks done in background and was easy to work around
by killing the thread using Javamelody and abandoning the faulty commits.

The issue showed up again, when upgrading from 2.9.x to 2.10: the online
reindexer getting stuck because of that infinite loop and this time, no
easy work around.

Use a similar approach that was done in intraline diff to work around
the MyersDiff infinite loop. Instead of returning a timeout error
message when the infinite loop is detected, fallback to a diff algorithm
that does not use MyersDiff. Returning a timeout error was not an option
because the failing operation is not always triggered by a user.

From the user perspective, the only difference when the infinite loop
is detected is that the files in the commit will not be compared
in-depth, which will result in bigger edit regions.

[1]https://groups.google.com/d/msg/repo-discuss/ZtiCilM3wFA/LijfZ4YkLHsJ

Change-Id: Ib00de070dd8df1722d4ade0a83c0ffa8eaa37f8e

5 files changed, 82 insertions, 5 deletions

diff --git a/Documentation/config-gerrit.txt b/Documentation/config-gerrit.txt
index f174b28229..3368db9f58 100644
--- a/Documentation/config-gerrit.txt
+++ b/Documentation/config-gerrit.txt
@@ -706,6 +706,25 @@ See also link:cmd-flush-caches.html[gerrit flush-caches].
 
 ==== [[cache_options]]Cache Options
 
+[[cache.diff.timeout]]cache.diff.timeout::
++
+Maximum number of milliseconds to wait for diff data before giving up and
+falling back on a simpler diff algorithm that will not be able to break down
+modified regions into smaller ones. This is a work around for an infinite loop
+bug in the default difference algorithm implementation.
++
+Values should use common unit suffixes to express their setting:
++
+* ms, milliseconds
+* s, sec, second, seconds
+* m, min, minute, minutes
+* h, hr, hour, hours
+
++
+If a unit suffix is not specified, `milliseconds` is assumed.
++
+Default is 5 seconds.
+
 [[cache.diff_intraline.timeout]]cache.diff_intraline.timeout::
 +
 Maximum number of milliseconds to wait for intraline difference data
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/Reindex.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/Reindex.java
index c0cf8f9222..161efc1ed6 100644
--- a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/Reindex.java
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/Reindex.java
@@ -70,6 +70,7 @@ import com.google.gerrit.server.index.IndexModule;
 import com.google.gerrit.server.index.IndexModule.IndexType;
 import com.google.gerrit.server.mail.ReplacePatchSetSender;
 import com.google.gerrit.server.notedb.NoteDbModule;
+import com.google.gerrit.server.patch.DiffExecutorModule;
 import com.google.gerrit.server.patch.PatchListCacheImpl;
 import com.google.gerrit.server.project.ChangeControl;
 import com.google.gerrit.server.project.CommentLinkInfo;
@@ -191,6 +192,7 @@ public class Reindex extends SiteProgram {
 
   private Injector createSysInjector() {
     List<Module> modules = Lists.newArrayList();
+    modules.add(new DiffExecutorModule());
     modules.add(PatchListCacheImpl.module());
     AbstractModule changeIndexModule;
     switch (IndexModule.getIndexType(dbInjector)) {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/patch/DiffExecutor.java b/gerrit-server/src/main/java/com/google/gerrit/server/patch/DiffExecutor.java
index 23589e3e3a..564ca58453 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/patch/DiffExecutor.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/patch/DiffExecutor.java
@@ -23,7 +23,7 @@ import java.util.concurrent.ExecutorService;
 
 /**
  * Marker on {@link ExecutorService} used by
- * {@link IntraLineLoader}.
+ * {@link IntraLineLoader} and {@link PatchListLoader}.
  */
 @Retention(RUNTIME)
 @BindingAnnotation
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListCacheImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListCacheImpl.java
index 7b7c73108a..6c769f742a 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListCacheImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListCacheImpl.java
@@ -35,7 +35,7 @@ import java.util.concurrent.ExecutionException;
 /** Provides a cached list of {@link PatchListEntry}. */
 @Singleton
 public class PatchListCacheImpl implements PatchListCache {
-  private static final String FILE_NAME = "diff";
+  static final String FILE_NAME = "diff";
   static final String INTRA_NAME = "diff_intraline";
 
   public static Module module() {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListLoader.java b/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListLoader.java
index de36020d85..d9e796958c 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListLoader.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/patch/PatchListLoader.java
@@ -16,11 +16,13 @@
 package com.google.gerrit.server.patch;
 
 import com.google.common.base.Function;
+import com.google.common.base.Throwables;
 import com.google.common.cache.CacheLoader;
 import com.google.common.collect.FluentIterable;
 import com.google.gerrit.reviewdb.client.AccountDiffPreference.Whitespace;
 import com.google.gerrit.reviewdb.client.Patch;
 import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.config.ConfigUtil;
 import com.google.gerrit.server.config.GerritServerConfig;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.git.MergeUtil;
@@ -69,6 +71,12 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
 
 public class PatchListLoader extends CacheLoader<PatchListKey, PatchList> {
   static final Logger log = LoggerFactory.getLogger(PatchListLoader.class);
@@ -76,13 +84,23 @@ public class PatchListLoader extends CacheLoader<PatchListKey, PatchList> {
   private final GitRepositoryManager repoManager;
   private final PatchListCache patchListCache;
   private final ThreeWayMergeStrategy mergeStrategy;
+  private final ExecutorService diffExecutor;
+  private final long timeoutMillis;
+
 
   @Inject
-  PatchListLoader(GitRepositoryManager mgr, PatchListCache plc,
-      @GerritServerConfig Config cfg) {
+  PatchListLoader(GitRepositoryManager mgr,
+      PatchListCache plc,
+      @GerritServerConfig Config cfg,
+      @DiffExecutor ExecutorService de) {
     repoManager = mgr;
     patchListCache = plc;
     mergeStrategy = MergeUtil.getMergeStrategy(cfg);
+    diffExecutor = de;
+    timeoutMillis =
+        ConfigUtil.getTimeUnit(cfg, "cache", PatchListCacheImpl.FILE_NAME,
+            "timeout", TimeUnit.MILLISECONDS.convert(5, TimeUnit.SECONDS),
+            TimeUnit.MILLISECONDS);
   }
 
   @Override
@@ -164,7 +182,7 @@ public class PatchListLoader extends CacheLoader<PatchListKey, PatchList> {
         DiffEntry diffEntry = diffEntries.get(i);
         if (paths == null || paths.contains(diffEntry.getNewPath())
             || paths.contains(diffEntry.getOldPath())) {
-          FileHeader fh = df.toFileHeader(diffEntry);
+          FileHeader fh = toFileHeader(key, df, diffEntry);
           entries.add(newEntry(aTree, fh));
         }
       }
@@ -175,6 +193,44 @@ public class PatchListLoader extends CacheLoader<PatchListKey, PatchList> {
     }
   }
 
+  private FileHeader toFileHeader(PatchListKey key,
+      final DiffFormatter diffFormatter, final DiffEntry diffEntry)
+      throws IOException {
+
+    Future<FileHeader> result = diffExecutor.submit(new Callable<FileHeader>() {
+      @Override
+      public FileHeader call() throws IOException {
+        return diffFormatter.toFileHeader(diffEntry);
+      }
+    });
+
+    try {
+      return result.get(timeoutMillis, TimeUnit.MILLISECONDS);
+    } catch (InterruptedException | TimeoutException e) {
+      log.warn(timeoutMillis + " ms timeout reached for Diff loader"
+                      + " in project " + key.projectKey.get()
+                      + " on commit " + key.getNewId().name()
+                      + " on path " + diffEntry.getNewPath()
+                      + " comparing " + diffEntry.getOldId().name()
+                      + ".." + diffEntry.getNewId().name());
+      result.cancel(true);
+      return toFileHeaderWithoutMyersDiff(diffFormatter, diffEntry);
+    } catch (ExecutionException e) {
+      // If there was an error computing the result, carry it
+      // up to the caller so the cache knows this key is invalid.
+      Throwables.propagateIfInstanceOf(e.getCause(), IOException.class);
+      throw new IOException(e.getMessage(), e.getCause());
+    }
+  }
+
+  private FileHeader toFileHeaderWithoutMyersDiff(DiffFormatter diffFormatter,
+      DiffEntry diffEntry) throws IOException {
+    HistogramDiff histogramDiff = new HistogramDiff();
+    histogramDiff.setFallbackAlgorithm(null);
+    diffFormatter.setDiffAlgorithm(histogramDiff);
+    return diffFormatter.toFileHeader(diffEntry);
+  }
+
   private PatchListEntry newCommitMessage(final RawTextComparator cmp,
       final Repository db, final ObjectReader reader,
       final RevCommit aCommit, final RevCommit bCommit) throws IOException {