blob: c23f0f7cd210acb8e5b008326feda7ffca73d6d2 [file] [log] [blame]
// Copyright 2022 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.util.concurrent.MoreExecutors.directExecutor;
import static com.google.devtools.build.lib.skyframe.ArtifactConflictFinder.NUM_JOBS;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableMap;
import com.google.common.util.concurrent.Futures;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.common.util.concurrent.ListeningExecutorService;
import com.google.common.util.concurrent.MoreExecutors;
import com.google.common.util.concurrent.ThreadFactoryBuilder;
import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
import com.google.devtools.build.lib.actions.ActionLookupValue;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.ArtifactPrefixConflictException;
import com.google.devtools.build.lib.actions.MutableActionGraph;
import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
import com.google.devtools.build.lib.concurrent.ExecutorUtil;
import com.google.devtools.build.lib.concurrent.Sharder;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.profiler.Profiler;
import com.google.devtools.build.lib.profiler.SilentCloseable;
import com.google.devtools.build.lib.skyframe.ArtifactConflictFinder.ActionConflictsAndStats;
import com.google.devtools.build.lib.skyframe.ArtifactConflictFinder.ConflictException;
import com.google.devtools.build.lib.vfs.PathFragment;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Executors;
/**
* An incremental artifact conflict finder that maintains a running state.
*
* <p>Once an ActionLookupKey is analyzed, its actions are registered with this conflict finder
* before execution. The internal action graph accumulates these actions in order to detect a
* conflict later on. There should be one instance of this class per build.
*/
@ThreadSafe
public final class IncrementalArtifactConflictFinder {
private final MutableActionGraph threadSafeMutableActionGraph;
public final ConcurrentMap<String, Object> pathFragmentTrieRoot;
private final ListeningExecutorService executorService;
private IncrementalArtifactConflictFinder(MutableActionGraph threadSafeMutableActionGraph) {
this.threadSafeMutableActionGraph = threadSafeMutableActionGraph;
this.pathFragmentTrieRoot = new ConcurrentHashMap<>();
this.executorService =
MoreExecutors.listeningDecorator(
Executors.newFixedThreadPool(
NUM_JOBS,
new ThreadFactoryBuilder()
.setNameFormat("IncrementalArtifactConflictFinder %d")
.build()));
}
static IncrementalArtifactConflictFinder createWithActionGraph(
MutableActionGraph threadSafeMutableActionGraph) {
return new IncrementalArtifactConflictFinder(threadSafeMutableActionGraph);
}
ActionConflictsAndStats findArtifactConflicts(
Sharder<ActionLookupValue> actionLookupValues, boolean strictConflictChecks)
throws InterruptedException {
ConcurrentMap<ActionAnalysisMetadata, ConflictException> temporaryBadActionMap =
new ConcurrentHashMap<>();
try (SilentCloseable c =
Profiler.instance().profile("IncrementalArtifactConflictFinder.findArtifactConflicts")) {
constructActionGraphAndArtifactList(
executorService,
threadSafeMutableActionGraph,
pathFragmentTrieRoot,
actionLookupValues,
strictConflictChecks,
temporaryBadActionMap);
}
return ActionConflictsAndStats.create(
ImmutableMap.copyOf(temporaryBadActionMap), threadSafeMutableActionGraph.getSize());
}
private static void constructActionGraphAndArtifactList(
ListeningExecutorService executorService,
MutableActionGraph actionGraph,
ConcurrentMap<String, Object> pathFragmentTrieRoot,
Sharder<ActionLookupValue> actionLookupValues,
boolean strictConflictChecks,
ConcurrentMap<ActionAnalysisMetadata, ConflictException> badActionMap)
throws InterruptedException {
// The max number of shards is NUM_JOBS.
List<ListenableFuture<Void>> futures = new ArrayList<>(NUM_JOBS);
for (List<ActionLookupValue> shard : actionLookupValues) {
futures.add(
executorService.submit(
() ->
actionRegistration(
shard,
actionGraph,
pathFragmentTrieRoot,
strictConflictChecks,
badActionMap)));
}
// Now wait on the futures.
try {
Futures.whenAllComplete(futures).call(() -> null, directExecutor()).get();
} catch (ExecutionException e) {
throw new IllegalStateException("Unexpected exception", e);
}
}
void shutdown() throws InterruptedException {
if (!executorService.isShutdown() && ExecutorUtil.uninterruptibleShutdown(executorService)) {
throw new InterruptedException();
}
}
private static Void actionRegistration(
List<ActionLookupValue> values,
MutableActionGraph actionGraph,
ConcurrentMap<String, Object> pathFragmentTrieRoot,
boolean strictConflictChecks,
ConcurrentMap<ActionAnalysisMetadata, ConflictException> badActionMap) {
for (ActionLookupValue value : values) {
for (ActionAnalysisMetadata action : value.getActions()) {
try {
actionGraph.registerAction(action);
} catch (ActionConflictException e) {
// It may be possible that we detect a conflict for the same action more than once, if
// that action belongs to multiple aspect values. In this case we will harmlessly
// overwrite the badActionMap entry.
badActionMap.put(action, new ConflictException(e));
// We skip the rest of the loop, and do not add the path->artifact mapping for this
// artifact below -- we don't need to check it since this action is already in
// error.
continue;
} catch (InterruptedException e) {
// Bail.
Thread.currentThread().interrupt();
return null;
}
for (Artifact output : action.getOutputs()) {
checkOutputPrefix(
actionGraph, strictConflictChecks, pathFragmentTrieRoot, output, badActionMap);
}
}
}
return null;
}
/**
* Fits the path segments into the existing trie.
*
* <p>A conceptual path segment TrieNode can be:
*
* <ul>
* <li>an Artifact if it's a leaf node, or
* <li>a {@code ConcurrentMap<String, Object>} if it's a non-leaf node. The mapping is from a
* path segment to another trie node.
* </ul>
*
* <p>We do this instead of creating a proper wrapper TrieNode data structure to save memory, as
* the trie is expected to get quite large.
*/
private static void checkOutputPrefix(
MutableActionGraph actionGraph,
boolean strictConflictCheck,
ConcurrentMap<String, Object> root,
Artifact newArtifact,
ConcurrentMap<ActionAnalysisMetadata, ConflictException> badActionMap) {
Object existingTrieNode = root;
PathFragment newArtifactPathFragment = newArtifact.getExecPath();
Iterator<String> newPathIter = newArtifactPathFragment.segments().iterator();
while (newPathIter.hasNext() && !(existingTrieNode instanceof Artifact)) {
String newSegment = newPathIter.next();
boolean isFinalSegmentOfNewPath = !newPathIter.hasNext();
@SuppressWarnings("unchecked")
ConcurrentMap<String, Object> existingNonLeafNode =
(ConcurrentMap<String, Object>) existingTrieNode;
Object matchingChildNode =
existingNonLeafNode.computeIfAbsent(
newSegment,
isFinalSegmentOfNewPath
? unused -> newArtifact
: unused -> new ConcurrentHashMap<String, Object>());
// By the time we arrive in this method, we know for sure that there can't be any exact
// matches in the paths since that would have been an ActionConflictException.
boolean newPathIsPrefixOfExisting =
!(matchingChildNode instanceof Artifact) && isFinalSegmentOfNewPath;
boolean existingPathIsPrefixOfNew =
matchingChildNode instanceof Artifact && !isFinalSegmentOfNewPath;
if (existingPathIsPrefixOfNew || newPathIsPrefixOfExisting) {
Artifact conflictingExistingArtifact = getOwningArtifactFromTrie(matchingChildNode);
ActionAnalysisMetadata priorAction =
Preconditions.checkNotNull(
actionGraph.getGeneratingAction(conflictingExistingArtifact),
conflictingExistingArtifact);
ActionAnalysisMetadata currentAction =
Preconditions.checkNotNull(actionGraph.getGeneratingAction(newArtifact), newArtifact);
if (strictConflictCheck || priorAction.shouldReportPathPrefixConflict(currentAction)) {
ConflictException exception =
new ConflictException(
new ArtifactPrefixConflictException(
conflictingExistingArtifact.getExecPath(),
newArtifactPathFragment,
priorAction.getOwner().getLabel(),
currentAction.getOwner().getLabel()));
badActionMap.put(priorAction, exception);
badActionMap.put(currentAction, exception);
}
// If 2 paths collide, we need to update the Trie to contain only the shorter one.
// This is required for correctness: the set of subsequent paths that could conflict with
// the longer path is a subset of that of the shorter path.
if (newPathIsPrefixOfExisting) {
existingNonLeafNode.put(newSegment, newArtifact);
}
break;
}
existingTrieNode = matchingChildNode;
}
}
// TODO(b/214389062) Fix the issue with SolibSymlinkAction before launch.
private static Artifact getOwningArtifactFromTrie(Object trieNode) {
Preconditions.checkArgument(
trieNode instanceof Artifact || trieNode instanceof ConcurrentHashMap);
if (trieNode instanceof Artifact) {
return (Artifact) trieNode;
}
Object nodeIter = trieNode;
while (!(nodeIter instanceof Artifact)) {
// Just pick the first path available down the Trie.
for (Object value : ((ConcurrentHashMap<?, ?>) nodeIter).values()) {
nodeIter = value;
break;
}
}
return (Artifact) nodeIter;
}
}