Add caching of computed file digests based on file metadata.

This change modifies DigestUtils to add a cache of (path, inode, mtime,
size) to the digest of the file for those digests that are computed by
reading the file contents.

The cache itself is optional because relying on file metadata to cache
the file digests could lead to correctness issues.  Enabling the cache
is exposed via a new (undocumented) --cache_computed_file_digests flag
that we can use post-release to tune the built-in values if they prove
to be incorrect or problematic.

For Bazel, enable this cache unconditionally because the rest of
Bazel already relies on mtimes and other file metadata to determine
changes to files.

The rationale for this change is performance: once we have lost the
in-memory file metadata (e.g. because of a flag flip), Bazel has to
redigest all of the output files to recompute action cache keys.  For
a pathological case of rebuilding a large app with 5GB of outputs and
then flipping the --[no]check_visibility flag on the command line, we
get the following numbers before this change:

____Elapsed time: 11.170s, Critical Path: 8.34s
____Elapsed time: 11.027s, Critical Path: 8.20s
____Elapsed time: 11.084s, Critical Path: 7.46s
____Elapsed time: 11.051s, Critical Path: 6.61s
____Elapsed time: 11.211s, Critical Path: 7.81s
____Elapsed time: 10.884s, Critical Path: 8.20s
____Elapsed time: 11.385s, Critical Path: 8.12s
____Elapsed time: 11.723s, Critical Path: 8.18s
____Elapsed time: 11.327s, Critical Path: 7.73s
____Elapsed time: 11.028s, Critical Path: 7.89s

And after this change:

____Elapsed time: 4.294s, Critical Path: 0.27s
____Elapsed time: 4.376s, Critical Path: 0.83s
____Elapsed time: 8.083s, Critical Path: 0.52s
____Elapsed time: 4.302s, Critical Path: 0.64s
____Elapsed time: 4.282s, Critical Path: 0.37s
____Elapsed time: 4.219s, Critical Path: 0.61s
____Elapsed time: 4.214s, Critical Path: 0.97s
____Elapsed time: 4.185s, Critical Path: 0.71s
____Elapsed time: 7.962s, Critical Path: 4.30s
____Elapsed time: 4.149s, Critical Path: 1.03s

--
PiperOrigin-RevId: 150351444
MOS_MIGRATED_REVID=150351444

1 files changed, 136 insertions, 8 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/actions/DigestUtilsTest.java b/src/test/java/com/google/devtools/build/lib/actions/DigestUtilsTest.java
index 70d2f40b22..b37eb4c830 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/DigestUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/DigestUtilsTest.java
@@ -16,10 +16,13 @@ package com.google.devtools.build.lib.actions;
 
 import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNotSame;
 import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
 
 import com.google.common.base.Strings;
+import com.google.common.cache.CacheStats;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.testutil.TestThread;
 import com.google.devtools.build.lib.testutil.TestUtils;
@@ -29,15 +32,16 @@ import com.google.devtools.build.lib.vfs.FileSystem.HashFunction;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.io.IOException;
 import java.util.Arrays;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicInteger;
+import javax.annotation.CheckReturnValue;
+import org.junit.After;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 /**
  * Tests for DigestUtils.
@@ -45,6 +49,11 @@ import java.util.concurrent.TimeUnit;
 @RunWith(JUnit4.class)
 public class DigestUtilsTest {
 
+  @After
+  public void tearDown() {
+    DigestUtils.configureCache(0);
+  }
+
   private static void assertDigestCalculationConcurrency(boolean expectConcurrent,
       final boolean fastDigest, final int fileSize1, final int fileSize2,
       HashFunction hf) throws Exception {
@@ -135,8 +144,7 @@ public class DigestUtilsTest {
     }
   }
 
-  @Test
-  public void testRecoverFromMalformedDigest() throws Exception {
+  public void assertRecoverFromMalformedDigest(HashFunction... hashFunctions) throws Exception {
     final byte[] malformed = {0, 0, 0};
     FileSystem myFS = new InMemoryFileSystem(BlazeClock.instance()) {
       @Override
@@ -147,7 +155,7 @@ public class DigestUtilsTest {
     };
     Path path = myFS.getPath("/file");
     FileSystemUtils.writeContentAsLatin1(path, "a");
-    for (HashFunction hf : Arrays.asList(HashFunction.MD5, HashFunction.SHA1)) {
+    for (HashFunction hf : hashFunctions) {
       FileSystem.setDigestFunctionForTesting(hf);
       byte[] result = DigestUtils.getDigestOrFail(path, 1);
       assertArrayEquals(path.getDigest(), result);
@@ -155,4 +163,124 @@ public class DigestUtilsTest {
       assertTrue(path.isValidDigest(result));
     }
   }
+
+  @Test
+  public void testRecoverFromMalformedDigestWithoutCache() throws Exception {
+    try {
+      DigestUtils.getCacheStats();
+      fail("Digests cache should remain disabled until configureCache is called");
+    } catch (NullPointerException expected) {
+    }
+    assertRecoverFromMalformedDigest(HashFunction.MD5, HashFunction.SHA1);
+    try {
+      DigestUtils.getCacheStats();
+      fail("Digests cache was unexpectedly enabled through the test");
+    } catch (NullPointerException expected) {
+    }
+  }
+
+  @Test
+  public void testRecoverFromMalformedDigestWithCache() throws Exception {
+    DigestUtils.configureCache(10);
+    assertNotNull(DigestUtils.getCacheStats()); // Ensure the cache is enabled.
+
+    // When using the cache, we cannot run our test using different hash functions because the
+    // hash function is not part of the cache key. This is intentional: the hash function is
+    // essentially final and can only be changed for tests. Therefore, just test the same hash
+    // function twice to further exercise the cache code.
+    assertRecoverFromMalformedDigest(HashFunction.MD5, HashFunction.MD5);
+
+    assertNotNull(DigestUtils.getCacheStats()); // Ensure the cache remains enabled.
+  }
+
+  /** Helper class to assert the cache statistics. */
+  private static class CacheStatsChecker {
+    /** Cache statistics, grabbed at construction time. */
+    private final CacheStats stats;
+
+    private int expectedEvictionCount;
+    private int expectedHitCount;
+    private int expectedMissCount;
+
+    CacheStatsChecker() {
+      this.stats = DigestUtils.getCacheStats();
+    }
+
+    @CheckReturnValue
+    CacheStatsChecker evictionCount(int count) {
+      expectedEvictionCount = count;
+      return this;
+    }
+
+    @CheckReturnValue
+    CacheStatsChecker hitCount(int count) {
+      expectedHitCount = count;
+      return this;
+    }
+
+    @CheckReturnValue
+    CacheStatsChecker missCount(int count) {
+      expectedMissCount = count;
+      return this;
+    }
+
+    void check() throws Exception {
+      assertEquals(expectedEvictionCount, stats.evictionCount());
+      assertEquals(expectedHitCount, stats.hitCount());
+      assertEquals(expectedMissCount, stats.missCount());
+    }
+  }
+
+  @Test
+  public void testCache() throws Exception {
+    final AtomicInteger getFastDigestCounter = new AtomicInteger(0);
+    final AtomicInteger getDigestCounter = new AtomicInteger(0);
+
+    FileSystem tracingFileSystem =
+        new InMemoryFileSystem(BlazeClock.instance()) {
+          @Override
+          protected byte[] getFastDigest(Path path, HashFunction hashFunction) throws IOException {
+            getFastDigestCounter.incrementAndGet();
+            return null;
+          }
+
+          @Override
+          protected byte[] getDigest(Path path) throws IOException {
+            getDigestCounter.incrementAndGet();
+            return super.getDigest(path);
+          }
+        };
+
+    DigestUtils.configureCache(2);
+
+    final Path file1 = tracingFileSystem.getPath("/1.txt");
+    final Path file2 = tracingFileSystem.getPath("/2.txt");
+    final Path file3 = tracingFileSystem.getPath("/3.txt");
+    FileSystemUtils.writeContentAsLatin1(file1, "some contents");
+    FileSystemUtils.writeContentAsLatin1(file2, "some other contents");
+    FileSystemUtils.writeContentAsLatin1(file3, "and something else");
+
+    byte[] digest1 = DigestUtils.getDigestOrFail(file1, file1.getFileSize());
+    assertEquals(1, getFastDigestCounter.get());
+    assertEquals(1, getDigestCounter.get());
+    new CacheStatsChecker().evictionCount(0).hitCount(0).missCount(1).check();
+
+    byte[] digest2 = DigestUtils.getDigestOrFail(file1, file1.getFileSize());
+    assertEquals(2, getFastDigestCounter.get());
+    assertEquals(1, getDigestCounter.get());
+    new CacheStatsChecker().evictionCount(0).hitCount(1).missCount(1).check();
+
+    assertArrayEquals(digest1, digest2);
+
+    // Evict the digest for the previous file.
+    DigestUtils.getDigestOrFail(file2, file2.getFileSize());
+    DigestUtils.getDigestOrFail(file3, file3.getFileSize());
+    new CacheStatsChecker().evictionCount(1).hitCount(1).missCount(3).check();
+
+    // And now try to recompute it.
+    byte[] digest3 = DigestUtils.getDigestOrFail(file1, file1.getFileSize());
+    new CacheStatsChecker().evictionCount(2).hitCount(1).missCount(4).check();
+
+    assertArrayEquals(digest1, digest3);
+  }
 }