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

7 files changed, 602 insertions, 11 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java b/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
index 508ee8920a..aaf8b1d459 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
@@ -13,14 +13,21 @@
 // limitations under the License.
 package com.google.devtools.build.lib.actions.cache;
 
+import com.google.common.cache.Cache;
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.CacheStats;
 import com.google.common.io.BaseEncoding;
+import com.google.common.primitives.Longs;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.LoggingUtil;
+import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.VarInt;
+import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import java.io.IOException;
 import java.io.OutputStream;
 import java.nio.ByteBuffer;
@@ -31,6 +38,12 @@ import java.util.logging.Level;
 /**
  * Utility class for getting md5 digests of files.
  *
+ * <p>This class implements an optional cache of file digests when the computation of the digests is
+ * costly (i.e. when {@link Path#getFastDigest()} is not available). The cache can be enabled via
+ * the {@link #configureCache(long)} function, but note that enabling this cache might have an
+ * impact on correctness because not all changes to files can be purely detected from their
+ * metadata.
+ *
  * <p>Note that this class is responsible for digesting file metadata in an order-independent
  * manner. Care must be taken to do this properly. The digest must be a function of the set of
  * (path, metadata) tuples. While the order of these pairs must not matter, it would <b>not</b> be
@@ -45,6 +58,76 @@ public class DigestUtils {
   private static final Object DIGEST_LOCK = new Object();
   private static final AtomicBoolean MULTI_THREADED_DIGEST = new AtomicBoolean(false);
 
+  /**
+   * Keys used to cache the values of the digests for files where we don't have fast digests.
+   *
+   * <p>The cache keys are derived from many properties of the file metadata in an attempt to be
+   * able to detect most file changes.
+   */
+  private static class CacheKey {
+    /** Path to the file. */
+    private final PathFragment path;
+
+    /** File system identifier of the file (typically the inode number). */
+    private final long nodeId;
+
+    /** Last modification time of the file. */
+    private final long modifiedTime;
+
+    /** Size of the file. */
+    private final long size;
+
+    /**
+     * Constructs a new cache key.
+     *
+     * @param path path to the file
+     * @param status file status data from which to obtain the cache key properties
+     * @throws IOException if reading the file status data fails
+     */
+    public CacheKey(Path path, FileStatus status) throws IOException {
+      this.path = path.asFragment();
+      this.nodeId = status.getNodeId();
+      this.modifiedTime = status.getLastModifiedTime();
+      this.size = status.getSize();
+    }
+
+    @Override
+    public boolean equals(Object object) {
+      if (object == this) {
+        return true;
+      } else if (!(object instanceof CacheKey)) {
+        return false;
+      } else {
+        CacheKey key = (CacheKey) object;
+        return path.equals(key.path)
+            && nodeId == key.nodeId
+            && modifiedTime == key.modifiedTime
+            && size == key.size;
+      }
+    }
+
+    @Override
+    public int hashCode() {
+      int result = 17;
+      result = 31 * result + path.hashCode();
+      result = 31 * result + Longs.hashCode(nodeId);
+      result = 31 * result + Longs.hashCode(modifiedTime);
+      result = 31 * result + Longs.hashCode(size);
+      return result;
+    }
+  }
+
+  /**
+   * Global cache of files to their digests.
+   *
+   * <p>This is null when the cache is disabled.
+   *
+   * <p>Note that we do not use a {@link com.google.common.cache.LoadingCache} because our keys
+   * represent the paths as strings, not as {@link Path} instances. As a result, the loading
+   * function cannot actually compute the digests of the files so we have to handle this externally.
+   */
+  private static volatile Cache<CacheKey, byte[]> globalCache = null;
+
   /** Private constructor to prevent instantiation of utility class. */
   private DigestUtils() {}
 
@@ -76,6 +159,35 @@ public class DigestUtils {
   }
 
   /**
+   * Enables the caching of file digests based on file status data.
+   *
+   * <p>If the cache was already enabled, this causes the cache to be reinitialized thus losing all
+   * contents. If the given size is zero, the cache is disabled altogether.
+   *
+   * @param maximumSize maximumSize of the cache in number of entries
+   */
+  public static void configureCache(long maximumSize) {
+    if (maximumSize == 0) {
+      globalCache = null;
+    } else {
+      globalCache = CacheBuilder.newBuilder().maximumSize(maximumSize).recordStats().build();
+    }
+  }
+
+  /**
+   * Obtains cache statistics.
+   *
+   * <p>The cache must have previously been enabled by a call to {@link #configureCache(long)}.
+   *
+   * @return an immutable snapshot of the cache statistics
+   */
+  public static CacheStats getCacheStats() {
+    Cache<CacheKey, byte[]> cache = globalCache;
+    Preconditions.checkNotNull(cache, "configureCache() must have been called with a size >= 0");
+    return cache.stats();
+  }
+
+  /**
    * Enable or disable multi-threaded digesting even for large files.
    */
   public static void setMultiThreadedDigest(boolean multiThreadedDigest) {
@@ -104,19 +216,45 @@ public class DigestUtils {
       digest = null;
     }
 
+    // At this point, either we could not get a fast digest or the fast digest we got is corrupt.
+    // Attempt a cache lookup if the cache is enabled and return the cached digest if found.
+    Cache<CacheKey, byte[]> cache = globalCache;
+    CacheKey key = null;
+    if (cache != null && digest == null) {
+      key = new CacheKey(path, path.stat());
+      digest = cache.getIfPresent(key);
+    }
     if (digest != null) {
       return digest;
-    } else if (fileSize > 4096 && !MULTI_THREADED_DIGEST.get()) {
+    }
+
+    // All right, we have neither a fast nor a cached digest. Let's go through the costly process of
+    // computing it from the file contents.
+    if (fileSize > 4096 && !MULTI_THREADED_DIGEST.get()) {
       // We'll have to read file content in order to calculate the digest. In that case
       // it would be beneficial to serialize those calculations since there is a high
       // probability that MD5 will be requested for multiple output files simultaneously.
       // Exception is made for small (<=4K) files since they will not likely to introduce
       // significant delays (at worst they will result in two extra disk seeks by
       // interrupting other reads).
-      return getDigestInExclusiveMode(path);
+      digest = getDigestInExclusiveMode(path);
     } else {
-      return getDigestInternal(path);
+      digest = getDigestInternal(path);
     }
+
+    Preconditions.checkNotNull(
+        digest,
+        "We should have gotten a digest for %s at this point but we still don't have one",
+        path);
+    if (cache != null) {
+      Preconditions.checkNotNull(
+          key,
+          "We should have computed a cache key earlier for %s because the cache is enabled and we"
+              + " did not get a fast digest for this file, but we don't have a key here",
+          path);
+      cache.put(key, digest);
+    }
+    return digest;
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java b/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
index c32e3835ef..336715a479 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
@@ -45,6 +45,7 @@ public final class BazelMain {
           com.google.devtools.build.lib.ssd.SsdModule.class,
           com.google.devtools.build.lib.worker.WorkerModule.class,
           com.google.devtools.build.lib.remote.RemoteModule.class,
+          com.google.devtools.build.lib.runtime.CacheFileDigestsModule.class,
           com.google.devtools.build.lib.standalone.StandaloneModule.class,
           com.google.devtools.build.lib.sandbox.SandboxModule.class,
           com.google.devtools.build.lib.runtime.BuildSummaryStatsModule.class,
diff --git a/src/main/java/com/google/devtools/build/lib/exec/ExecutionOptions.java b/src/main/java/com/google/devtools/build/lib/exec/ExecutionOptions.java
index b8b2ac2509..7766b6c7a0 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/ExecutionOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/ExecutionOptions.java
@@ -205,4 +205,17 @@ public class ExecutionOptions extends OptionsBase {
     help = "Print the contents of the SpawnActionContext and ContextProviders maps."
   )
   public boolean debugPrintActionContexts;
+
+  @Option(
+    name = "cache_computed_file_digests",
+    defaultValue = "50000",
+    category = "undocumented",
+    help =
+        "If greater than 0, configures Blaze to cache file digests in memory based on their "
+            + "metadata instead of recomputing the digests from disk every time they are needed. "
+            + "Setting this to 0 ensures correctness because not all file changes can be noted "
+            + "from file metadata. When not 0, the number indicates the size of the cache as the "
+            + "number of file digests to be cached."
+  )
+  public long cacheSizeForComputedFileDigests;
 }
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CacheFileDigestsModule.java b/src/main/java/com/google/devtools/build/lib/runtime/CacheFileDigestsModule.java
new file mode 100644
index 0000000000..1c94bd8a17
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CacheFileDigestsModule.java
@@ -0,0 +1,93 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// Licensed 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.
+
+package com.google.devtools.build.lib.runtime;
+
+import com.google.common.cache.CacheStats;
+import com.google.devtools.build.lib.actions.cache.DigestUtils;
+import com.google.devtools.build.lib.buildtool.BuildRequest;
+import com.google.devtools.build.lib.exec.ExecutionOptions;
+import com.google.devtools.build.lib.exec.ExecutorBuilder;
+import com.google.devtools.build.lib.util.Preconditions;
+import java.util.logging.Logger;
+
+/** Enables the caching of file digests in {@link DigestUtils}. */
+public class CacheFileDigestsModule extends BlazeModule {
+
+  private static final Logger log = Logger.getLogger(CacheFileDigestsModule.class.getName());
+
+  /** Stats gathered at the beginning of a command, to compute deltas on completion. */
+  private CacheStats stats;
+
+  /**
+   * Last known size of the cache. Changes to this value cause the cache to be reinitialized. null
+   * if we don't know anything about the last value yet (i.e. before any command has been run).
+   */
+  private Long lastKnownCacheSize;
+
+  public CacheFileDigestsModule() {}
+
+  /**
+   * Adds a line to the log with cache statistics.
+   *
+   * @param message message to prefix to the written line
+   * @param stats the cache statistics to be logged
+   */
+  private static void logStats(String message, CacheStats stats) {
+    log.info(
+        message
+            + ": hit count="
+            + stats.hitCount()
+            + ", miss count="
+            + stats.missCount()
+            + ", hit rate="
+            + stats.hitRate()
+            + ", eviction count="
+            + stats.evictionCount());
+  }
+
+  @Override
+  public void executorInit(CommandEnvironment env, BuildRequest request, ExecutorBuilder builder) {
+    super.executorInit(env, request, builder);
+
+    ExecutionOptions options = request.getOptions(ExecutionOptions.class);
+    if (lastKnownCacheSize == null
+        || options.cacheSizeForComputedFileDigests != lastKnownCacheSize) {
+      log.info("Reconfiguring cache with size=" + options.cacheSizeForComputedFileDigests);
+      DigestUtils.configureCache(options.cacheSizeForComputedFileDigests);
+      lastKnownCacheSize = options.cacheSizeForComputedFileDigests;
+    }
+
+    if (options.cacheSizeForComputedFileDigests == 0) {
+      stats = null;
+      log.info("Disabled cache");
+    } else {
+      stats = DigestUtils.getCacheStats();
+      logStats("Accumulated cache stats before command", stats);
+    }
+  }
+
+  @Override
+  public void afterCommand() {
+    super.afterCommand();
+
+    if (stats != null) {
+      CacheStats newStats = DigestUtils.getCacheStats();
+      Preconditions.checkNotNull(newStats, "The cache is enabled so we must get some stats back");
+      logStats("Accumulated cache stats after command", newStats);
+      logStats("Cache stats for finished command", newStats.minus(stats));
+      stats = null; // Silence stats until next command that uses the executor.
+    }
+  }
+}
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);
+  }
 }
diff --git a/src/test/shell/integration/BUILD b/src/test/shell/integration/BUILD
index 729af75b84..a2f7fe9156 100644
--- a/src/test/shell/integration/BUILD
+++ b/src/test/shell/integration/BUILD
@@ -46,6 +46,13 @@ sh_test(
 )
 
 sh_test(
+    name = "execution_phase_tests",
+    size = "large",
+    srcs = ["execution_phase_tests.sh"],
+    data = [":test-deps"],
+)
+
+sh_test(
     name = "experimental_ui_test",
     size = "large",
     srcs = ["experimental_ui_test.sh"],
diff --git a/src/test/shell/integration/execution_phase_tests.sh b/src/test/shell/integration/execution_phase_tests.sh
new file mode 100755
index 0000000000..baf2433cd0
--- /dev/null
+++ b/src/test/shell/integration/execution_phase_tests.sh
@@ -0,0 +1,211 @@
+#!/bin/bash
+#
+# Copyright 2017 The Bazel Authors. All rights reserved.
+#
+# Licensed 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.
+#
+# execution_phase_tests.sh: miscellaneous integration tests of Bazel for
+# behaviors that affect the execution phase.
+#
+
+# Load the test setup defined in the parent directory
+CURRENT_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
+source "${CURRENT_DIR}/../integration_test_setup.sh" \
+  || { echo "integration_test_setup.sh not found!" >&2; exit 1; }
+
+#### HELPER FUNCTIONS ##################################################
+
+function set_up() {
+    cd ${WORKSPACE_DIR}
+}
+
+function tear_down() {
+    bazel shutdown
+}
+
+# Looks for the last occurrence of a log message in a log file.
+#
+# This assumes the use of java.util.logging.SimpleFormatter, which splits
+# the context of a log entry and the log message itself in two lines.
+#
+# TODO(jmmv): We should have functionality in unittest.bash to check the
+# contents of the Bazel's client log in a way that allows us to test for
+# only the messages printed by the last-run command.
+function assert_last_log() {
+  local context="${1}"; shift
+  local message="${1}"; shift
+  local log="${1}"; shift
+  local fail_message="${1}"; shift
+
+  if ! grep -A1 "${context}" "${log}" | tail -n1 | grep -q "${message}" ; then
+    cat "${log}" >>"${TEST_log}"  # Help debugging when we fail.
+    fail "${fail_message}"
+  fi
+}
+
+# Asserts that the last dump of cache stats in the log matches the given
+# metric and value.
+function assert_cache_stats() {
+  local metric="${1}"; shift
+  local exp_value="${1}"; shift
+
+  local java_log="$(bazel info output_base 2>/dev/null)/java.log"
+  local last="$(grep -A1 "CacheFileDigestsModule" "${java_log}" | tail -n1)"
+  [ -n "${last}" ] || fail "Could not find cache stats in log"
+  if ! echo "${last}" | grep -q "${metric}=${exp_value}"; then
+    echo "Last cache stats: ${last}" >>"${TEST_log}"
+    fail "${metric} was not ${exp_value}"
+  fi
+}
+
+#### TESTS #############################################################
+
+function test_cache_computed_file_digests_behavior() {
+  mkdir -p package || fail "mkdir failed"
+  cat >package/BUILD <<EOF
+genrule(
+  name = "foo",
+  srcs = ["foo.in"],
+  outs = ["foo.out"],
+  cmd = "cat \$(location foo.in) >\$@",
+)
+
+genrule(
+  name = "bar",
+  srcs = ["bar.in", ":foo"],
+  outs = ["bar.out"],
+  cmd = "cat \$(location bar.in) \$(location :foo) >\$@",
+)
+EOF
+  touch package/foo.in package/bar.in
+
+  bazel build package:bar >>"${TEST_log}" 2>&1 || fail "Should build"
+  # We cannot make any robust assertions on the first run because of implicit
+  # dependencies we have no control about.
+
+  # Rebuilding without changes should yield hits for everything.  Run this
+  # multiple times to ensure the reported statistics are not accumulated.
+  for run in 1 2 3; do
+    bazel build package:bar >>"${TEST_log}" 2>&1 || fail "Should build"
+    assert_cache_stats "hit count" 1  # stable-status.txt
+    assert_cache_stats "miss count" 1  # volatile-status.txt
+  done
+
+  # Throw away the in-memory Skyframe state by flipping a flag.  We expect hits
+  # for the previous outputs, which are used to query the action cache.
+  bazel build --nocheck_visibility package:bar >>"${TEST_log}" 2>&1 \
+      || fail "Should build"
+  assert_cache_stats "hit count" 3  # stable-status.txt foo.out bar.out
+  assert_cache_stats "miss count" 1  # volatile-status.txt
+
+  # Change the size of the cache and retry the same build.  We expect no hits
+  # because resizing the cache invalidates all of its contents.
+  bazel build --cache_computed_file_digests=100 package:bar \
+      >>"${TEST_log}" 2>&1 || fail "Should build"
+  assert_cache_stats "hit count" 0
+  assert_cache_stats "miss count" 4  # {stable,volatile}-status* {foo,bar}.out
+
+  # Run a non-build command, which should not interfere with the cache.
+  bazel info >>"${TEST_log}" 2>&1 || fail "Should run"
+  assert_cache_stats "hit count" 0  # Same as previous command; unmodified.
+  assert_cache_stats "miss count" 4  # Same as previous command; unmodified.
+
+  # Rebuild without changes one more time with the new size of the cache to
+  # ensure the cache is not reset across runs with the flag override.
+  bazel build --nocheck_visibility --cache_computed_file_digests=100 \
+      package:bar >>"${TEST_log}" 2>&1 || fail "Should build"
+  assert_cache_stats "hit count" 3  # stable-status.txt foo.out bar.out
+  assert_cache_stats "miss count" 1  # volatile-status.txt
+}
+
+function test_cache_computed_file_digests_uncaught_changes() {
+  local timestamp=201703151112.13  # Fixed timestamp to mark our file with.
+
+  mkdir -p package || fail "mkdir failed"
+  cat >package/BUILD <<EOF
+genrule(
+  name = "foo",
+  srcs = ["foo.in"],
+  outs = ["foo.out"],
+  cmd = "echo foo >\$@ && touch -t ${timestamp} \$@",
+)
+EOF
+  touch package/foo.in
+
+  # Build the target once to populate the action cache, then update a file to a
+  # known timestamp, and rebuild the target to recompute our internal digests
+  # cache.
+  bazel build package:foo >>"${TEST_log}" 2>&1 || fail "Should build"
+  local output_file="$(find bazel-out/ -name foo.out)"
+  touch -t "${timestamp}" "${output_file}"
+  bazel build package:foo >>"${TEST_log}" 2>&1 || fail "Should build"
+
+  # Modify the content of a file in the action cache in a way that bypasses the
+  # logic to cache file digests: replace the file's content with new contents of
+  # the same length; avoid modifying the inode number; and respect the previous
+  # timestamp.
+  function log_metadata_for_test_debugging() {
+      echo "${1} ${2} modifying it in place:"
+      stat "${output_file}"
+      if which md5sum >/dev/null; then  # macOS and possibly others.
+          md5sum "${output_file}"
+      elif which md5 >/dev/null; then  # Linux and possibly others.
+          md5 "${output_file}"
+      fi
+  }
+  log_metadata_for_test_debugging "${output_file}" before >>"${TEST_log}"
+  chmod +w "${output_file}"
+  echo bar >"${output_file}"  # Contents must match length in genrule.
+  chmod -w "${output_file}"
+  touch -t "${timestamp}" "${output_file}"
+  log_metadata_for_test_debugging "${output_file}" after >>"${TEST_log}"
+
+  # Assert all hits after discarding the in-memory Skyframe state while
+  # modifying the on-disk state in a way that bypasses the digests cache
+  # functionality.
+  bazel build --nocheck_visibility package:foo >>"${TEST_log}" 2>&1 \
+      || fail "Should build"
+  [[ "$(cat "${output_file}")" == bar ]] \
+      || fail "External change to action cache misdetected"
+
+  # For completeness, make the changes to the same output file visibile and
+  # ensure Blaze notices them.  This is to sanity-check that we actually
+  # modified the right output file above.
+  touch "${output_file}"
+  bazel build package:foo >>"${TEST_log}" 2>&1 || fail "Should build"
+  [[ "$(cat "${output_file}")" == foo ]] \
+      || fail "External change to action cache not detected"
+}
+
+function test_cache_computed_file_digests_ui() {
+  mkdir -p package || fail "mkdir failed"
+  echo "cc_library(name = 'foo', srcs = ['foo.cc'])" >package/BUILD
+  echo "int foo(void) { return 0; }" >package/foo.cc
+
+  local java_log="$(bazel info output_base 2>/dev/null)/java.log"
+
+  bazel build package:foo >>"${TEST_log}" 2>&1 || fail "Should build"
+  assert_last_log "CacheFileDigestsModule" "Cache stats" "${java_log}" \
+    "Digests cache not enabled by default"
+
+  bazel build --cache_computed_file_digests=0 package:foo >>"${TEST_log}" 2>&1 \
+      || fail "Should build"
+  assert_last_log "CacheFileDigestsModule" "Disabled cache" "${java_log}" \
+      "Digests cache not disabled as requested"
+
+  bazel build package:foo >>"${TEST_log}" 2>&1 || fail "Should build"
+  assert_last_log "CacheFileDigestsModule" "Cache stats" "${java_log}" \
+      "Digests cache not reenabled"
+}
+
+run_suite "Integration tests of ${PRODUCT_NAME} using the execution phase."