diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
index b856829..0d069fb 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
@@ -21,7 +21,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
 import com.google.devtools.build.lib.actions.cache.ActionCache;
-import com.google.devtools.build.lib.actions.cache.DigestUtils;
+import com.google.devtools.build.lib.actions.cache.MetadataDigestUtils;
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
 import com.google.devtools.build.lib.actions.cache.Protos.ActionCacheStatistics.MissReason;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -159,7 +159,7 @@
     for (Artifact artifact : actionInputs.toList()) {
       mdMap.put(artifact.getExecPathString(), getMetadataMaybe(metadataHandler, artifact));
     }
-    return !Arrays.equals(DigestUtils.fromMetadata(mdMap), entry.getFileDigest());
+    return !Arrays.equals(MetadataDigestUtils.fromMetadata(mdMap), entry.getFileDigest());
   }
 
   private void reportCommand(EventHandler handler, Action action) {
@@ -347,7 +347,8 @@
     }
     Map<String, String> usedEnvironment =
         computeUsedEnv(action, clientEnv, remoteDefaultPlatformProperties);
-    if (!Arrays.equals(entry.getUsedClientEnvDigest(), DigestUtils.fromEnv(usedEnvironment))) {
+    if (!Arrays.equals(
+        entry.getUsedClientEnvDigest(), MetadataDigestUtils.fromEnv(usedEnvironment))) {
       reportClientEnv(handler, action, usedEnvironment);
       actionCache.accountMiss(MissReason.DIFFERENT_ENVIRONMENT);
       return true;
diff --git a/src/main/java/com/google/devtools/build/lib/actions/BUILD b/src/main/java/com/google/devtools/build/lib/actions/BUILD
index e9299ef..2887382 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/actions/BUILD
@@ -51,7 +51,7 @@
             "LocalHostResourceFallback.java",
             "MiddlemanType.java",
             "ResourceSet.java",
-            "cache/DigestUtils.java",
+            "cache/MetadataDigestUtils.java",
         ],
     ),
     deps = [
@@ -213,14 +213,12 @@
         "FileStateValue.java",
         "FileValue.java",
         "InconsistentFilesystemException.java",
-        "cache/DigestUtils.java",
+        "cache/MetadataDigestUtils.java",
     ],
     deps = [
         ":artifacts",
         ":has_digest",
-        "//src/main/java/com/google/devtools/build/lib/clock",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
-        "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
         "//src/main/java/com/google/devtools/build/lib/util",
         "//src/main/java/com/google/devtools/build/lib/util:var_int",
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java b/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
index 5d3369a..aae6b76 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FileArtifactValue.java
@@ -20,12 +20,12 @@
 import com.google.common.base.Preconditions;
 import com.google.common.hash.HashFunction;
 import com.google.common.io.BaseEncoding;
-import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.util.BigIntegerFingerprint;
 import com.google.devtools.build.lib.util.Fingerprint;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
index 2de2969..f7b7b0a 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
@@ -87,7 +87,7 @@
 
     public Entry(String key, Map<String, String> usedClientEnv, boolean discoversInputs) {
       actionKey = key;
-      this.usedClientEnvDigest = DigestUtils.fromEnv(usedClientEnv);
+      this.usedClientEnvDigest = MetadataDigestUtils.fromEnv(usedClientEnv);
       files = discoversInputs ? new ArrayList<String>() : null;
       mdMap = new HashMap<>();
     }
@@ -141,7 +141,7 @@
      */
     public byte[] getFileDigest() {
       if (digest == null) {
-        digest = DigestUtils.fromMetadata(mdMap);
+        digest = MetadataDigestUtils.fromMetadata(mdMap);
         mdMap = null;
       }
       return digest;
@@ -182,7 +182,9 @@
           .append("\n");
       builder.append("      digestKey = ");
       if (digest == null) {
-        builder.append(formatDigest(DigestUtils.fromMetadata(mdMap))).append(" (from mdMap)\n");
+        builder
+            .append(formatDigest(MetadataDigestUtils.fromMetadata(mdMap)))
+            .append(" (from mdMap)\n");
       } else {
         builder.append(formatDigest(digest)).append("\n");
       }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
index f9fec40..87bacdc 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
@@ -26,6 +26,7 @@
 import com.google.devtools.build.lib.util.PersistentMap;
 import com.google.devtools.build.lib.util.StringIndexer;
 import com.google.devtools.build.lib.util.VarInt;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.UnixGlob;
 import java.io.ByteArrayOutputStream;
@@ -381,14 +382,14 @@
       VarInt.putVarInt(actionKeyBytes.length, sink);
       sink.write(actionKeyBytes);
 
-      DigestUtils.write(entry.getFileDigest(), sink);
+      MetadataDigestUtils.write(entry.getFileDigest(), sink);
 
       VarInt.putVarInt(entry.discoversInputs() ? files.size() : NO_INPUT_DISCOVERY_COUNT, sink);
       for (String file : files) {
         VarInt.putVarInt(indexer.getOrCreateIndex(file), sink);
       }
 
-      DigestUtils.write(entry.getUsedClientEnvDigest(), sink);
+      MetadataDigestUtils.write(entry.getUsedClientEnvDigest(), sink);
 
       return sink.toByteArray();
     } catch (IOException e) {
@@ -410,7 +411,7 @@
       source.get(actionKeyBytes);
       String actionKey = new String(actionKeyBytes, ISO_8859_1);
 
-      byte[] digest = DigestUtils.read(source);
+      byte[] digest = MetadataDigestUtils.read(source);
 
       int count = VarInt.getVarInt(source);
       if (count != NO_INPUT_DISCOVERY_COUNT && count < 0) {
@@ -430,7 +431,7 @@
         files = builder.build();
       }
 
-      byte[] usedClientEnvDigest = DigestUtils.read(source);
+      byte[] usedClientEnvDigest = MetadataDigestUtils.read(source);
 
       if (source.remaining() > 0) {
         throw new IOException("serialized entry data has not been fully decoded");
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataDigestUtils.java b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataDigestUtils.java
new file mode 100644
index 0000000..4071b63
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataDigestUtils.java
@@ -0,0 +1,85 @@
+// Copyright 2020 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.actions.cache;
+
+import com.google.devtools.build.lib.actions.FileArtifactValue;
+import com.google.devtools.build.lib.util.Fingerprint;
+import com.google.devtools.build.lib.util.VarInt;
+import com.google.devtools.build.lib.vfs.DigestUtils;
+import java.io.IOException;
+import java.io.OutputStream;
+import java.nio.ByteBuffer;
+import java.util.Map;
+import javax.annotation.Nullable;
+
+/** Utility class for digests/metadata relating to the action cache. */
+public final class MetadataDigestUtils {
+  private MetadataDigestUtils() {}
+
+  /**
+   * @param source the byte buffer source.
+   * @return the digest from the given buffer.
+   */
+  public static byte[] read(ByteBuffer source) {
+    int size = VarInt.getVarInt(source);
+    byte[] bytes = new byte[size];
+    source.get(bytes);
+    return bytes;
+  }
+
+  /** Write the digest to the output stream. */
+  public static void write(byte[] digest, OutputStream sink) throws IOException {
+    VarInt.putVarInt(digest.length, sink);
+    sink.write(digest);
+  }
+
+  /**
+   * @param mdMap A collection of (execPath, FileArtifactValue) pairs. Values may be null.
+   * @return an <b>order-independent</b> digest from the given "set" of (path, metadata) pairs.
+   */
+  public static byte[] fromMetadata(Map<String, FileArtifactValue> mdMap) {
+    byte[] result = new byte[1]; // reserve the empty string
+    // Profiling showed that MessageDigest engine instantiation was a hotspot, so create one
+    // instance for this computation to amortize its cost.
+    Fingerprint fp = new Fingerprint();
+    for (Map.Entry<String, FileArtifactValue> entry : mdMap.entrySet()) {
+      result = DigestUtils.xor(result, getDigest(fp, entry.getKey(), entry.getValue()));
+    }
+    return result;
+  }
+
+  /**
+   * @param env A collection of (String, String) pairs.
+   * @return an order-independent digest of the given set of pairs.
+   */
+  public static byte[] fromEnv(Map<String, String> env) {
+    byte[] result = new byte[0];
+    Fingerprint fp = new Fingerprint();
+    for (Map.Entry<String, String> entry : env.entrySet()) {
+      fp.addString(entry.getKey());
+      fp.addString(entry.getValue());
+      result = DigestUtils.xor(result, fp.digestAndReset());
+    }
+    return result;
+  }
+
+  private static byte[] getDigest(Fingerprint fp, String execPath, @Nullable FileArtifactValue md) {
+    fp.addString(execPath);
+    if (md != null) {
+      md.addTo(fp);
+    }
+    return fp.digestAndReset();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/exec/RunfilesTreeUpdater.java b/src/main/java/com/google/devtools/build/lib/exec/RunfilesTreeUpdater.java
index 188bc2b..3316af9 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/RunfilesTreeUpdater.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/RunfilesTreeUpdater.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.util.io.OutErr;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.io.IOException;
@@ -80,7 +81,9 @@
       // symbolic link, it is likely a symbolic link to the input manifest, so we cannot trust it as
       // an up-to-date check.
       if (!outputManifest.isSymbolicLink()
-          && Arrays.equals(outputManifest.getDigest(), inputManifest.getDigest())) {
+          && Arrays.equals(
+              DigestUtils.getDigestWithManualFallbackWhenSizeUnknown(outputManifest),
+              DigestUtils.getDigestWithManualFallbackWhenSizeUnknown(inputManifest))) {
         return;
       }
     } catch (IOException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SpawnLogContext.java b/src/main/java/com/google/devtools/build/lib/exec/SpawnLogContext.java
index 7223b86..e5116f0 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SpawnLogContext.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SpawnLogContext.java
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
 import com.google.devtools.build.lib.util.io.MessageOutputStream;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.build.lib.vfs.Dirent;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -92,7 +93,7 @@
         ActionInput input = e.getValue();
         Path inputPath = execRoot.getRelative(input.getExecPathString());
         if (inputPath.isDirectory()) {
-          listDirectoryContents(inputPath, (file) -> builder.addInputs(file), metadataProvider);
+          listDirectoryContents(inputPath, builder::addInputs, metadataProvider);
         } else {
           Digest digest = computeDigest(input, null, metadataProvider);
           builder.addInputsBuilder().setPath(input.getExecPathString()).setDigest(digest);
@@ -110,7 +111,7 @@
     for (Map.Entry<Path, ActionInput> e : existingOutputs.entrySet()) {
       Path path = e.getKey();
       if (path.isDirectory()) {
-        listDirectoryContents(path, (file) -> builder.addActualOutputs(file), metadataProvider);
+        listDirectoryContents(path, builder::addActualOutputs, metadataProvider);
       } else {
         File.Builder outputBuilder = builder.addActualOutputsBuilder();
         outputBuilder.setPath(path.relativeTo(execRoot).toString());
@@ -233,9 +234,11 @@
       path = execRoot.getRelative(input.getExecPath());
     }
     // Compute digest manually.
+    long fileSize = path.getFileSize();
     return digest
-        .setHash(HashCode.fromBytes(path.getDigest()).toString())
-        .setSizeBytes(path.getFileSize())
+        .setHash(
+            HashCode.fromBytes(DigestUtils.getDigestWithManualFallback(path, fileSize)).toString())
+        .setSizeBytes(fileSize)
         .build();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/remote/util/DigestUtil.java b/src/main/java/com/google/devtools/build/lib/remote/util/DigestUtil.java
index 1b294af..5066f3c 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/util/DigestUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/util/DigestUtil.java
@@ -21,10 +21,10 @@
 import com.google.common.hash.HashCode;
 import com.google.common.hash.HashingOutputStream;
 import com.google.common.io.BaseEncoding;
-import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
 import com.google.devtools.build.lib.remote.common.RemoteCacheClient.ActionKey;
 import com.google.devtools.build.lib.vfs.DigestHashFunction;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.protobuf.Message;
 import java.io.ByteArrayOutputStream;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java
index c819b1f..beb0553 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java
@@ -19,7 +19,6 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.io.BaseEncoding;
-import com.google.devtools.build.lib.actions.FileStateValue.RegularFileStateValue;
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.RuleDefinition;
@@ -251,8 +250,9 @@
   public static String fileValueToMarkerValue(FileValue fileValue) throws IOException {
     Preconditions.checkArgument(fileValue.isFile() && !fileValue.isSpecialFile());
     // Return the file content digest in hex. fileValue may or may not have the digest available.
-    byte[] digest = ((RegularFileStateValue) fileValue.realFileStateValue()).getDigest();
+    byte[] digest = fileValue.realFileStateValue().getDigest();
     if (digest == null) {
+      // Fast digest not available, or it would have been in the FileValue.
       digest = fileValue.realRootedPath().asPath().getDigest();
     }
     return BaseEncoding.base16().lowerCase().encode(digest);
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
index 520e02c..ca38d5f 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CacheFileDigestsModule.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CacheFileDigestsModule.java
@@ -17,10 +17,10 @@
 import com.google.common.base.Preconditions;
 import com.google.common.cache.CacheStats;
 import com.google.common.flogger.GoogleLogger;
-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.vfs.DigestUtils;
 
 /** Enables the caching of file digests in {@link DigestUtils}. */
 public class CacheFileDigestsModule extends BlazeModule {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
index 13c78e1..5499dce 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
@@ -36,9 +36,9 @@
 import com.google.devtools.build.lib.actions.FilesetManifest;
 import com.google.devtools.build.lib.actions.FilesetManifest.RelativeSymlinkBehavior;
 import com.google.devtools.build.lib.actions.FilesetOutputSymlink;
-import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.build.lib.vfs.Dirent;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigest;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
index 78d2bc9..81a05fe 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
@@ -29,7 +29,7 @@
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.HasDigest;
-import com.google.devtools.build.lib.actions.cache.DigestUtils;
+import com.google.devtools.build.lib.actions.cache.MetadataDigestUtils;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
 import com.google.devtools.build.lib.util.Fingerprint;
@@ -131,7 +131,7 @@
   @AutoCodec.VisibleForSerialization
   static final TreeArtifactValue EMPTY =
       new TreeArtifactValue(
-          DigestUtils.fromMetadata(ImmutableMap.of()),
+          MetadataDigestUtils.fromMetadata(ImmutableMap.of()),
           ImmutableSortedMap.of(),
           /*archivedRepresentation=*/ null,
           /*entirelyRemote=*/ false);
diff --git a/src/main/java/com/google/devtools/build/lib/ssd/BUILD b/src/main/java/com/google/devtools/build/lib/ssd/BUILD
index 9069ec7..85fb315 100644
--- a/src/main/java/com/google/devtools/build/lib/ssd/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/ssd/BUILD
@@ -13,7 +13,7 @@
     srcs = glob(["*.java"]),
     deps = [
         "//src/main/java/com/google/devtools/build/lib:runtime",
-        "//src/main/java/com/google/devtools/build/lib/actions:file_metadata",
+        "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:guava",
     ],
diff --git a/src/main/java/com/google/devtools/build/lib/ssd/SsdModule.java b/src/main/java/com/google/devtools/build/lib/ssd/SsdModule.java
index 2e73896..219329e 100644
--- a/src/main/java/com/google/devtools/build/lib/ssd/SsdModule.java
+++ b/src/main/java/com/google/devtools/build/lib/ssd/SsdModule.java
@@ -14,9 +14,9 @@
 package com.google.devtools.build.lib.ssd;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.runtime.BlazeModule;
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
+import com.google.devtools.build.lib.vfs.DigestUtils;
 import com.google.devtools.common.options.OptionsBase;
 
 /**
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/BUILD b/src/main/java/com/google/devtools/build/lib/vfs/BUILD
index be8dc58..70a2769 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/vfs/BUILD
@@ -51,7 +51,6 @@
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
-        "//src/main/java/com/google/devtools/build/lib/util:TestType",
         "//src/main/java/com/google/devtools/build/lib/util:filetype",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:guava",
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java b/src/main/java/com/google/devtools/build/lib/vfs/DigestUtils.java
similarity index 79%
rename from src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
rename to src/main/java/com/google/devtools/build/lib/vfs/DigestUtils.java
index addd5f0..24edd82 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/DigestUtils.java
@@ -11,7 +11,7 @@
 // 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.actions.cache;
+package com.google.devtools.build.lib.vfs;
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
@@ -19,21 +19,10 @@
 import com.google.common.cache.CacheBuilder;
 import com.google.common.cache.CacheStats;
 import com.google.common.primitives.Longs;
-import com.google.devtools.build.lib.actions.FileArtifactValue;
-import com.google.devtools.build.lib.clock.BlazeClock;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
-import com.google.devtools.build.lib.util.Fingerprint;
-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;
-import java.util.Map;
 import java.util.concurrent.atomic.AtomicBoolean;
-import javax.annotation.Nullable;
 
 /**
  * Utility class for getting digests of files.
@@ -152,7 +141,7 @@
    * provide it via extended attribute.
    */
   private static byte[] getDigestInExclusiveMode(Path path) throws IOException {
-    long startTime = BlazeClock.nanoTime();
+    long startTime = Profiler.nanoTimeMaybe();
     synchronized (DIGEST_LOCK) {
       Profiler.instance().logSimpleTask(startTime, ProfilerTask.WAIT, path.getPathString());
       return getDigestInternal(path);
@@ -160,14 +149,14 @@
   }
 
   private static byte[] getDigestInternal(Path path) throws IOException {
-    long startTime = BlazeClock.nanoTime();
+    long startTime = System.nanoTime();
     byte[] digest = path.getDigest();
 
     // When using multi-threaded digesting, it makes no sense to use the throughput of a single
     // digest operation to determine whether a read was abnormally slow (as the scheduler might just
     // have preferred other reads).
     if (!MULTI_THREADED_DIGEST.get()) {
-      long millis = (BlazeClock.nanoTime() - startTime) / 1000000;
+      long millis = (System.nanoTime() - startTime) / 1000000;
       if (millis > SLOW_READ_MILLIS && (path.getFileSize() / millis) < SLOW_READ_THROUGHPUT) {
         System.err.printf(
             "Slow read: a %d-byte read from %s took %d ms.%n", path.getFileSize(), path, millis);
@@ -231,6 +220,20 @@
   }
 
   /**
+   * Gets the digest of {@code path}, using a constant-time xattr call if the filesystem supports
+   * it, and calculating the digest manually otherwise.
+   *
+   * <p>Unlike {@link #getDigestWithManualFallback}, will not rate-limit manual digesting of files,
+   * so only use this method if the file size is truly unknown and you don't expect many concurrent
+   * manual digests of large files.
+   *
+   * @param path Path of the file.
+   */
+  public static byte[] getDigestWithManualFallbackWhenSizeUnknown(Path path) throws IOException {
+    return getDigestWithManualFallback(path, -1);
+  }
+
+  /**
    * Calculates the digest manually.
    *
    * @param path Path of the file.
@@ -271,64 +274,8 @@
     return digest;
   }
 
-  /**
-   * @param source the byte buffer source.
-   * @return the digest from the given buffer.
-   * @throws IOException if the byte buffer is incorrectly formatted.
-   */
-  public static byte[] read(ByteBuffer source) throws IOException {
-    int size = VarInt.getVarInt(source);
-    byte[] bytes = new byte[size];
-    source.get(bytes);
-    return bytes;
-  }
-
-  /** Write the digest to the output stream. */
-  public static void write(byte[] digest, OutputStream sink) throws IOException {
-    VarInt.putVarInt(digest.length, sink);
-    sink.write(digest);
-  }
-
-  /**
-   * @param mdMap A collection of (execPath, FileArtifactValue) pairs. Values may be null.
-   * @return an <b>order-independent</b> digest from the given "set" of (path, metadata) pairs.
-   */
-  public static byte[] fromMetadata(Map<String, FileArtifactValue> mdMap) {
-    byte[] result = new byte[1]; // reserve the empty string
-    // Profiling showed that MessageDigest engine instantiation was a hotspot, so create one
-    // instance for this computation to amortize its cost.
-    Fingerprint fp = new Fingerprint();
-    for (Map.Entry<String, FileArtifactValue> entry : mdMap.entrySet()) {
-      result = xor(result, getDigest(fp, entry.getKey(), entry.getValue()));
-    }
-    return result;
-  }
-
-  /**
-   * @param env A collection of (String, String) pairs.
-   * @return an order-independent digest of the given set of pairs.
-   */
-  public static byte[] fromEnv(Map<String, String> env) {
-    byte[] result = new byte[0];
-    Fingerprint fp = new Fingerprint();
-    for (Map.Entry<String, String> entry : env.entrySet()) {
-      fp.addString(entry.getKey());
-      fp.addString(entry.getValue());
-      result = xor(result, fp.digestAndReset());
-    }
-    return result;
-  }
-
-  private static byte[] getDigest(Fingerprint fp, String execPath, @Nullable FileArtifactValue md) {
-    fp.addString(execPath);
-    if (md != null) {
-      md.addTo(fp);
-    }
-    return fp.digestAndReset();
-  }
-
   /** Compute lhs ^= rhs bitwise operation of the arrays. May clobber either argument. */
-  private static byte[] xor(byte[] lhs, byte[] rhs) {
+  public static byte[] xor(byte[] lhs, byte[] rhs) {
     int n = rhs.length;
     if (lhs.length >= n) {
       for (int i = 0; i < n; i++) {
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/Path.java b/src/main/java/com/google/devtools/build/lib/vfs/Path.java
index 58bb000..91e2722 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/Path.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/Path.java
@@ -766,7 +766,11 @@
   }
 
   /**
-   * Returns the digest of the file denoted by the current path, following symbolic links.
+   * Returns the digest of the file denoted by the current path, following symbolic links. Is not
+   * guaranteed to call {@link #getFastDigest} internally, even if a fast digest is likely
+   * available. Callers should prefer {@link DigestUtils#getDigestWithManualFallback} to this method
+   * unless they know that a fast digest is unavailable and do not need the other features
+   * (disk-read rate-limiting, global cache) that {@link DigestUtils} provides.
    *
    * @return a new byte array containing the file's digest
    * @throws IOException if the digest could not be computed for any reason
@@ -802,7 +806,7 @@
         } else {
           hasher.putChar('-');
         }
-        hasher.putBytes(path.getDigest());
+        hasher.putBytes(DigestUtils.getDigestWithManualFallback(path, stat.getSize()));
       } else if (stat.isDirectory()) {
         hasher.putChar('d').putUnencodedChars(path.getDirectoryDigest());
       } else if (stat.isSymbolicLink()) {
@@ -816,7 +820,7 @@
               } else {
                 hasher.putChar('-');
               }
-              hasher.putBytes(resolved.getDigest());
+              hasher.putBytes(DigestUtils.getDigestWithManualFallbackWhenSizeUnknown(resolved));
             } else {
               // link to a non-file: include the link itself in the hash
               hasher.putChar('l').putUnencodedChars(link.toString());