src/main/java/com/google/devtools/build/lib/skyframe/FileSystemValueCheckerInferringAncestors.java

// Copyright 2021 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.skyframe;

import static com.google.common.collect.ImmutableList.toImmutableList;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
import com.google.common.util.concurrent.Futures;
import com.google.devtools.build.lib.actions.FileStateType;
import com.google.devtools.build.lib.actions.FileStateValue;
import com.google.devtools.build.lib.concurrent.ExecutorUtil;
import com.google.devtools.build.lib.server.FailureDetails;
import com.google.devtools.build.lib.server.FailureDetails.DiffAwareness.Code;
import com.google.devtools.build.lib.server.FailureDetails.FailureDetail;
import com.google.devtools.build.lib.util.AbruptExitException;
import com.google.devtools.build.lib.util.DetailedExitCode;
import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
import com.google.devtools.build.lib.vfs.Dirent;
import com.google.devtools.build.lib.vfs.FileStateKey;
import com.google.devtools.build.lib.vfs.RootedPath;
import com.google.devtools.build.lib.vfs.SyscallCache;
import com.google.devtools.build.skyframe.Differencer.DiffWithDelta.Delta;
import com.google.devtools.build.skyframe.ImmutableDiff;
import com.google.devtools.build.skyframe.InMemoryGraph;
import com.google.devtools.build.skyframe.InMemoryNodeEntry;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.Version;
import java.io.IOException;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicInteger;
import javax.annotation.Nullable;

/**
 * A helper class to find dirty {@link FileStateValue} and {@link DirectoryListingStateValue} nodes
 * based on a potentially incomplete diffs.
 *
 * <p>Infers directories from files meaning that it will work for diffs which exclude entries for
 * affected ancestor entries of nodes. It is also resilient to diffs which report only a root of
 * deleted subtree.
 */
public final class FileSystemValueCheckerInferringAncestors {
  @Nullable private final TimestampGranularityMonitor tsgm;
  private final InMemoryGraph inMemoryGraph;
  private final Map<RootedPath, NodeVisitState> nodeStates;
  private final SyscallCache syscallCache;
  private final SkyValueDirtinessChecker skyValueDirtinessChecker;

  private final Set<SkyKey> valuesToInvalidate = Sets.newConcurrentHashSet();
  private final ConcurrentMap<SkyKey, Delta> valuesToInject = new ConcurrentHashMap<>();

  private static final class NodeVisitState {

    private NodeVisitState(boolean collectMaybeDeletedChildren) {
      if (collectMaybeDeletedChildren) {
        maybeDeletedChildren = ConcurrentHashMap.newKeySet();
      }
    }

    private final AtomicInteger childrenToProcess = new AtomicInteger();
    // non-volatile since childrenToProcess ensures happens-before relationship.
    private boolean needsToBeVisited;

    private volatile boolean isInferredDirectory;
    private volatile Set<String> maybeDeletedChildren;

    void markInferredDirectory() {
      isInferredDirectory = true;
      // maybeTypeChangedChildren is used to figure out if the entry is a directory, since we
      // already inferred it, we can stop collecting those.
      maybeDeletedChildren = null;
    }

    void addMaybeDeletedChild(String child) {
      Set<String> localMaybeDeletedChildren = maybeDeletedChildren;
      if (localMaybeDeletedChildren != null) {
        localMaybeDeletedChildren.add(child);
      }
    }

    boolean signalFinishedChild(boolean needsToBeVisited) {
      // The order is important, we must update this.needsToBeVisited before decrementing
      // childrenToProcess -- that operation ensures this change is visible to other threads doing
      // the same (including this thread picking up a true set by another one).
      if (needsToBeVisited) {
        this.needsToBeVisited = true;
      }
      int childrenLeft = childrenToProcess.decrementAndGet();
      // If we hit 0, we know that all other threads have set and propagated needsToBeVisited.
      return childrenLeft == 0 && this.needsToBeVisited;
    }
  }

  private FileSystemValueCheckerInferringAncestors(
      @Nullable TimestampGranularityMonitor tsgm,
      InMemoryGraph inMemoryGraph,
      Map<RootedPath, NodeVisitState> nodeStates,
      SyscallCache syscallCache,
      SkyValueDirtinessChecker skyValueDirtinessChecker) {
    this.tsgm = tsgm;
    this.nodeStates = nodeStates;
    this.syscallCache = syscallCache;
    this.skyValueDirtinessChecker = skyValueDirtinessChecker;
    this.inMemoryGraph = inMemoryGraph;
  }

  @VisibleForTesting
  @SuppressWarnings("ReferenceEquality")
  public static ImmutableDiff getDiffWithInferredAncestors(
      @Nullable TimestampGranularityMonitor tsgm,
      InMemoryGraph inMemoryGraph,
      Iterable<FileStateKey> modifiedKeys,
      int nThreads,
      SyscallCache syscallCache,
      SkyValueDirtinessChecker skyValueDirtinessChecker)
      throws InterruptedException, AbruptExitException {
    Map<RootedPath, NodeVisitState> nodeStates = makeNodeVisitStates(modifiedKeys);
    return new FileSystemValueCheckerInferringAncestors(
            tsgm,
            inMemoryGraph,
            Collections.unmodifiableMap(nodeStates),
            syscallCache,
            skyValueDirtinessChecker)
        .processEntries(nThreads);
  }

  private static Map<RootedPath, NodeVisitState> makeNodeVisitStates(
      Iterable<FileStateKey> modifiedKeys) {
    Map<RootedPath, NodeVisitState> nodeStates = new HashMap<>();
    for (FileStateKey fileStateKey : modifiedKeys) {
      RootedPath top = fileStateKey.argument();
      // Start with false since the reported diff does not mean we are adding a child.
      boolean lastCreated = false;
      for (RootedPath path = top; path != null; path = path.getParentDirectory()) {
        @Nullable NodeVisitState existingState = nodeStates.get(path);
        NodeVisitState state;
        // We disable the optimization which detects whether directory still exists based on the
        // list of deleted children and listing. It is possible for the diff to report a deleted
        // directory without listing all of the files under it as deleted.
        if (existingState == null) {
          state = new NodeVisitState(/*collectMaybeDeletedChildren=*/ path != top);
          nodeStates.put(path, state);
        } else {
          state = existingState;
          if (path == top) {
            state.maybeDeletedChildren = null;
          }
        }
        if (lastCreated) {
          state.childrenToProcess.incrementAndGet();
        }
        lastCreated = existingState == null;
      }
    }
    return nodeStates;
  }

  private ImmutableDiff processEntries(int nThreads)
      throws InterruptedException, AbruptExitException {
    ExecutorService executor = Executors.newFixedThreadPool(nThreads);

    // Materialize all leaves before scheduling them -- otherwise, we could race with the
    // processing code which decrements childrenToProcess.
    ImmutableList<Callable<Void>> leaves =
        nodeStates.entrySet().stream()
            .filter(e -> e.getValue().childrenToProcess.get() == 0)
            .<Callable<Void>>map(
                e ->
                    () -> {
                      processEntry(e.getKey(), e.getValue());
                      return null;
                    })
            .collect(toImmutableList());

    List<Future<Void>> futures = executor.invokeAll(leaves);

    if (ExecutorUtil.interruptibleShutdown(executor)) {
      throw new InterruptedException();
    }

    for (Future<?> future : futures) {
      try {
        Futures.getDone(future);
      } catch (ExecutionException e) {
        if (e.getCause() instanceof StatFailedException) {
          throw new AbruptExitException(
              DetailedExitCode.of(
                  FailureDetail.newBuilder()
                      .setMessage(e.getCause().getMessage())
                      .setDiffAwareness(
                          FailureDetails.DiffAwareness.newBuilder().setCode(Code.DIFF_STAT_FAILED))
                      .build()),
              e);
        }
        throw new IllegalStateException(e);
      }
    }

    return new ImmutableDiff(valuesToInvalidate, valuesToInject);
  }

  private void processEntry(RootedPath path, NodeVisitState state) throws StatFailedException {
    NodeVisitState rootParentSentinel = new NodeVisitState(/*collectMaybeDeletedChildren=*/ false);

    while (state != rootParentSentinel) {
      RootedPath parentPath = path.getParentDirectory();
      NodeVisitState parentState =
          parentPath != null ? nodeStates.get(parentPath) : rootParentSentinel;
      boolean visitParent =
          visitEntry(path, state.isInferredDirectory, state.maybeDeletedChildren, parentState);
      boolean processParent = parentState.signalFinishedChild(visitParent);

      if (!processParent) {
        // This is a tree, only one child can trigger parent processing.
        return;
      }

      state = parentState;
      path = path.getParentDirectory();
    }
  }

  /**
   * Visits the given node and return whether the type of it may have changed.
   *
   * <p>Returns false if we know that the type has not changed. It may however return true if the
   * type has not changed.
   *
   * @param isInferredDirectory whether the node was already inferred as a directory from children.
   * @param maybeDeletedChildren if not null, exhaustive list of all children which may have their
   *     file system type changed (including deletions).
   */
  private boolean visitEntry(
      RootedPath path,
      boolean isInferredDirectory,
      @Nullable Set<String> maybeDeletedChildren,
      NodeVisitState parentState)
      throws StatFailedException {
    FileStateKey key = FileStateValue.key(path);
    @Nullable InMemoryNodeEntry fsvNode = inMemoryGraph.getIfPresent(key);
    @Nullable FileStateValue oldFsv = fsvNode != null ? (FileStateValue) fsvNode.toValue() : null;
    if (oldFsv == null) {
      visitUnknownEntry(key, isInferredDirectory, parentState);
      parentState.addMaybeDeletedChild(path.getRootRelativePath().getBaseName());
      return true;
    }

    if (isInferredDirectory
        || (maybeDeletedChildren != null
            && listingHasEntriesOutsideOf(path, maybeDeletedChildren))) {
      parentState.markInferredDirectory();
      if (oldFsv.getType().isDirectory()) {
        return false;
      }
      Version directoryFileStateNodeMtsv =
          skyValueDirtinessChecker.getMaxTransitiveSourceVersionForNewValue(
              key, FileStateValue.DIRECTORY_FILE_STATE_NODE);
      valuesToInject.put(
          key, Delta.justNew(FileStateValue.DIRECTORY_FILE_STATE_NODE, directoryFileStateNodeMtsv));
      parentListingKey(path).ifPresent(valuesToInvalidate::add);
      return true;
    }

    @Nullable FileStateValue newFsv = injectAndGetNewFileStateValueIfDirty(path, fsvNode, oldFsv);
    if (newFsv.getType().exists()) {
      parentState.markInferredDirectory();
    } else if (oldFsv.getType().exists()) {
      // exists -> not exists -- deletion.
      parentState.addMaybeDeletedChild(path.getRootRelativePath().getBaseName());
    }

    boolean typeChanged = newFsv.getType() != oldFsv.getType();
    if (typeChanged) {
      parentListingKey(path).ifPresent(valuesToInvalidate::add);
    }
    return typeChanged;
  }

  /**
   * Injects the new file state value if dirty. Returns the old file state value if not dirty and
   * the new file state value if dirty.
   */
  private FileStateValue injectAndGetNewFileStateValueIfDirty(
      RootedPath path, InMemoryNodeEntry oldFsvNode, FileStateValue oldFsv)
      throws StatFailedException {
    Preconditions.checkState(oldFsv != null, "Unexpected null FileStateValue.");
    @Nullable Version oldMtsv = oldFsvNode.getMaxTransitiveSourceVersion();
    SkyValueDirtinessChecker.DirtyResult dirtyResult =
        skyValueDirtinessChecker.check(oldFsvNode.getKey(), oldFsv, oldMtsv, syscallCache, tsgm);
    if (!dirtyResult.isDirty()) {
      return oldFsv;
    }
    @Nullable FileStateValue newFsv = (FileStateValue) dirtyResult.getNewValue();
    if (newFsv == null) {
      throw new StatFailedException(path, new IOException("Filesystem access failed."));
    }
    @Nullable Version newMtsv = dirtyResult.getNewMaxTransitiveSourceVersion();
    if (newMtsv == null && !skyValueDirtinessChecker.nullMaxTransitiveSourceVersionOk()) {
      throw new StatFailedException(path, new IOException("Filesystem access failed."));
    }

    valuesToInject.put(oldFsvNode.getKey(), Delta.justNew(newFsv, newMtsv));
    return newFsv;
  }

  private void visitUnknownEntry(
      FileStateKey key, boolean isInferredDirectory, NodeVisitState parentState)
      throws StatFailedException {
    RootedPath path = key.argument();
    // Run stats on unknown files in order to preserve the parent listing if present unless we
    // already know it has changed.
    Optional<DirectoryListingStateValue.Key> parentListingKey = parentListingKey(path);
    @Nullable DirectoryListingStateValue parentListing = null;
    if (parentListingKey.isPresent()) {
      @Nullable InMemoryNodeEntry entry = inMemoryGraph.getIfPresent(parentListingKey.get());
      parentListing =
          entry != null && entry.isDone() ? (DirectoryListingStateValue) entry.getValue() : null;
    }

    // No listing/we already know it has changed -- nothing to gain from stats anymore.
    if (parentListing == null || valuesToInvalidate.contains(parentListingKey.get())) {
      if (isInferredDirectory) {
        parentState.markInferredDirectory();
      }
      valuesToInvalidate.add(key);
      parentListingKey.ifPresent(valuesToInvalidate::add);
      return;
    }

    // We don't take advantage of isInferredDirectory because we set it only in cases of a present
    // descendant/done listing which normally cannot exist without having FileStateValue for
    // ancestors.
    @Nullable FileStateValue newValue = injectAndGetNewFileStateValueForUnknownEntry(path, key);

    if (isInferredDirectory || newValue.getType().exists()) {
      parentState.markInferredDirectory();
    }

    @Nullable
    Dirent dirent =
        parentListing.getDirents().maybeGetDirent(path.getRootRelativePath().getBaseName());
    @Nullable Dirent.Type typeInListing = dirent != null ? dirent.getType() : null;
    if (!Objects.equals(typeInListing, direntTypeFromFileStateType(newValue.getType()))) {
      valuesToInvalidate.add(parentListingKey.get());
    }
  }

  /** Injects the new file state value for unknown entry. */
  private FileStateValue injectAndGetNewFileStateValueForUnknownEntry(RootedPath path, SkyKey key)
      throws StatFailedException {
    @Nullable
    FileStateValue newValue =
        (FileStateValue) skyValueDirtinessChecker.createNewValue(path, syscallCache, tsgm);
    if (newValue == null) {
      throw new StatFailedException(path, new IOException("Filesystem access failed."));
    }
    Version newMtsv =
        skyValueDirtinessChecker.getMaxTransitiveSourceVersionForNewValue(key, newValue);
    if (newMtsv == null && !skyValueDirtinessChecker.nullMaxTransitiveSourceVersionOk()) {
      throw new StatFailedException(path, new IOException("Filesystem access failed."));
    }
    valuesToInject.put(key, Delta.justNew(newValue, newMtsv));
    return newValue;
  }

  private boolean listingHasEntriesOutsideOf(RootedPath path, Set<String> allAffectedEntries) {
    // TODO(192010830): Try looking up BUILD files if there is no listing -- this is a lookup we
    //  can speculatively try since those files are often checked against.
    @Nullable
    InMemoryNodeEntry nodeEntry = inMemoryGraph.getIfPresent(DirectoryListingStateValue.key(path));
    @Nullable
    DirectoryListingStateValue listing =
        nodeEntry != null && nodeEntry.isDone()
            ? (DirectoryListingStateValue) nodeEntry.getValue()
            : null;
    if (listing == null) {
      return false;
    }
    for (Dirent entry : listing.getDirents()) {
      if (!allAffectedEntries.contains(entry.getName())) {
        return true;
      }
    }
    return false;
  }

  private static Optional<DirectoryListingStateValue.Key> parentListingKey(RootedPath path) {
    return Optional.ofNullable(path.getParentDirectory()).map(DirectoryListingStateValue::key);
  }

  @Nullable
  private static Dirent.Type direntTypeFromFileStateType(FileStateType type) {
    switch (type) {
      case NONEXISTENT:
        return null;
      case REGULAR_FILE:
        return Dirent.Type.FILE;
      case SPECIAL_FILE:
        return Dirent.Type.UNKNOWN;
      case SYMLINK:
        return Dirent.Type.SYMLINK;
      case DIRECTORY:
        return Dirent.Type.DIRECTORY;
    }
    throw new AssertionError();
  }

  private static class StatFailedException extends Exception {
    StatFailedException(RootedPath path, IOException cause) {
      super(String.format("Failed to stat: '%s' while computing diff", path.asPath()), cause);
    }
  }
}