src/main/java/com/google/devtools/build/lib/vfs/DigestUtils.java

// Copyright 2014 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.vfs;

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.stats.CacheStats;
import com.github.benmanes.caffeine.cache.stats.ConcurrentStatsCounter;
import com.github.benmanes.caffeine.cache.stats.StatsCounter;
import com.google.common.base.Preconditions;
import com.google.protobuf.ByteString;
import com.google.protobuf.UnsafeByteOperations;
import java.io.IOException;
import java.util.HexFormat;
import javax.annotation.Nullable;

/**
 * Utility class for getting 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.
 */
public class DigestUtils {
  // Typical size for a digest byte array.
  public static final int ESTIMATED_SIZE = 32;

  private static final HexFormat HEX_FORMAT = HexFormat.of();

  /**
   * The digest of a file together with the metadata of the file it was computed from, for files
   * where we don't have fast digests.
   *
   * <p>The cache holds one such value per file. A lookup only uses the digest if the file's current
   * metadata still matches, which is derived from many properties of the file metadata in an
   * attempt to detect most file changes.
   *
   * <p>The metadata lives in the value rather than the key so that a file that changes does not
   * leave a stale entry behind. The change time only moves forward, so a file's old metadata can
   * never be observed again.
   */
  private static final class CachedDigest {
    private final long nodeId;
    private final long changeTime;
    private final long size;
    private final byte[] digest;

    private CachedDigest(FileStatus status, byte[] digest) throws IOException {
      this.nodeId = status.getNodeId();
      this.changeTime = status.getLastChangeTimeNanos();
      this.size = status.getSize();
      this.digest = digest;
    }

    /** Returns whether the digest is still valid for a file with the given metadata. */
    private boolean matches(FileStatus status) throws IOException {
      return nodeId == status.getNodeId()
          && changeTime == status.getLastChangeTimeNanos()
          && size == status.getSize();
    }
  }

  /**
   * The cache together with its statistics counter.
   *
   * <p>Hits and misses are recorded by {@link #manuallyComputeDigest} itself, through {@code
   * stats}, so that a present but stale entry counts as a miss. The cache records evictions into
   * the same counter.
   */
  private record DigestCache(Cache<PathFragment, CachedDigest> cache, StatsCounter stats) {
    private static DigestCache create(long maximumSize) {
      var stats = new ConcurrentStatsCounter();
      return new DigestCache(
          Caffeine.newBuilder().maximumSize(maximumSize).recordStats(() -> stats).build(), stats);
    }
  }

  /**
   * 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.github.benmanes.caffeine.cache.LoadingCache} because
   * our keys represent the paths as path fragments, 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.
   */
  @Nullable private static DigestCache globalCache = null;

  /** Private constructor to prevent instantiation of utility class. */
  private 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) {
    globalCache = maximumSize == 0 ? null : DigestCache.create(maximumSize);
  }

  /**
   * Clears the cache contents without changing its size. No-op if the cache hasn't yet been
   * initialized.
   */
  public static void clearCache() {
    DigestCache cache = globalCache;
    if (cache != null) {
      cache.cache().invalidateAll();
    }
  }

  /**
   * 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() {
    DigestCache cache = globalCache;
    Preconditions.checkNotNull(cache, "configureCache() must have been called with a size >= 0");
    return cache.cache().stats();
  }

  /**
   * Gets the digest of {@code path}, using a constant-time xattr call if the filesystem supports
   * it, and calculating the digest manually otherwise.
   *
   * <p>If {@link Path#getFastDigest} has already been attempted and was not available, call {@link
   * #manuallyComputeDigest} to skip an additional attempt to obtain the fast digest.
   *
   * @param path the file path
   * @param status a recently obtained file status, if available. Used to skip a stat.
   */
  public static byte[] getDigestWithManualFallback(
      Path path, XattrProvider xattrProvider, @Nullable FileStatus status) throws IOException {
    byte[] digest = xattrProvider.getFastDigest(path);
    return digest != null ? digest : manuallyComputeDigest(path, status);
  }

  /**
   * Calculates a digest manually (i.e., assuming that a fast digest can't obtained).
   *
   * @param path the file path
   * @param status a recently obtained file status, if available. Used to skip a stat.
   */
  public static byte[] manuallyComputeDigest(Path path, @Nullable FileStatus status)
      throws IOException {
    // Attempt a cache lookup if the cache is enabled.
    DigestCache cache = globalCache;
    PathFragment key = null;
    if (cache != null) {
      if (status == null) {
        status = path.stat();
      }
      key = path.asFragment();
      // Look up through the map view, which informs the eviction policy but does not record
      // statistics, so that only a usable digest counts as a hit.
      CachedDigest cached = cache.cache().asMap().get(key);
      if (cached != null && cached.matches(status)) {
        cache.stats().recordHits(1);
        return cached.digest;
      }
      cache.stats().recordMisses(1);
    }

    byte[] digest = path.getDigest();

    Preconditions.checkNotNull(digest, "Missing digest for %s", path);
    if (cache != null) {
      cache.cache().put(key, new CachedDigest(status, digest));
    }
    return digest;
  }

  /**
   * Combines two digests into one such that swapping the arguments results in the same result. May
   * clobber either argument.
   */
  public static byte[] combineUnordered(byte[] lhs, byte[] rhs) {
    int n = rhs.length;
    if (lhs.length >= n) {
      for (int i = 0; i < n; i++) {
        // Use + as in Guava's Hashing.combineUnordered.
        // This has a number of advantages over XOR, which was used in the past:
        // * Identical inputs will not cancel each other out.
        // * Due to the carry, addition isn't a linear operation on the level of bit vectors.
        //   This prevents adversaries from producing linear combinations (i.e., subsets of input
        //   sets) that collide with other inputs.
        lhs[i] += rhs[i];
      }
      return lhs;
    }
    return combineUnordered(rhs, lhs);
  }

  /** Returns the lowercase hex encoding of the given bytes. */
  public static ByteString toHexByteString(byte[] bytes) {
    byte[] hex = new byte[2 * bytes.length];
    for (int i = 0; i < bytes.length; i++) {
      hex[2 * i] = (byte) HEX_FORMAT.toHighHexDigit(bytes[i]);
      hex[2 * i + 1] = (byte) HEX_FORMAT.toLowHexDigit(bytes[i]);
    }
    return UnsafeByteOperations.unsafeWrap(hex);
  }
}