| // 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.skyframe; |
| |
| import com.google.common.base.MoreObjects; |
| import com.google.common.base.MoreObjects.ToStringHelper; |
| import com.google.common.collect.ImmutableList; |
| import com.google.common.collect.ImmutableSet; |
| import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible; |
| import com.google.devtools.build.lib.util.Preconditions; |
| |
| import java.util.Collections; |
| import java.util.List; |
| |
| /** |
| * Data the NodeEntry uses to maintain its state before it is done building. It allows the {@link |
| * NodeEntry} to keep the current state of the entry across invalidation and successive evaluations. |
| * A done node does not contain any of this data. However, if a node is marked dirty, its entry |
| * acquires a new {@link DirtyBuildingState} object, which persists until it is done again. |
| * |
| * <p>This class should be considered a private inner class of {@link InMemoryNodeEntry} -- no other |
| * classes should instantiate a {@code BuildingState} object or call any of its methods directly. It |
| * is in a separate file solely to keep the {@link NodeEntry} class readable. In particular, the |
| * caller must synchronize access to this class. |
| * |
| * <p>During its life, a node can go through states as follows: |
| * |
| * <ol> |
| * <li>Non-existent |
| * <li>Just created ({@link #isEvaluating} is false) |
| * <li>Evaluating ({@link #isEvaluating} is true) |
| * <li>Done (meaning this buildingState object is null) |
| * <li>Just created (when it is dirtied during evaluation) |
| * <li>Reset (just before it is re-evaluated) |
| * <li>Evaluating |
| * <li>Done |
| * </ol> |
| * |
| * <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch} and |
| * {@link NodeEntry#addReverseDepAndCheckIfDone} methods to be separate. All callers have to call |
| * both methods in that order if they want to create a node. The second method calls {@link |
| * #startEvaluating}, which transitions the current node to the "evaluating" state and returns true |
| * only the first time it was called. A caller that gets "true" back from that call must start the |
| * evaluation of this node, while any subsequent callers must not. |
| * |
| * <p>An entry is set to "evaluating" as soon as it is scheduled for evaluation. Thus, even a node |
| * that is never actually built (for instance, a dirty node that is verified as clean) is in the |
| * "evaluating" state until it is done. |
| */ |
| @ThreadCompatible |
| class BuildingState { |
| /** |
| * The number of dependencies that are known to be done in a {@link NodeEntry} if it is already |
| * evaluating, and a sentinel (-1) indicating that it has not yet started evaluating otherwise. |
| * There is a potential check-then-act race here during evaluation, so we need to make sure that |
| * when this is increased, we always check if the new value is equal to the number of required |
| * dependencies, and if so, we must re-schedule the node for evaluation. |
| * |
| * <p>There are two potential pitfalls here: 1) If multiple dependencies signal this node in close |
| * succession, this node should be scheduled exactly once. 2) If a thread is still working on this |
| * node, it should not be scheduled. |
| * |
| * <p>The first problem is solved by the {@link #signalDep} method, which also returns if the node |
| * needs to be re-scheduled, and ensures that only one thread gets a true return value. |
| * |
| * <p>The second problem is solved by first adding the newly discovered deps to a node's {@link |
| * InMemoryNodeEntry#directDeps}, and then looping through the direct deps and registering this |
| * node as a reverse dependency. This ensures that the signaledDeps counter can only reach {@link |
| * InMemoryNodeEntry#directDeps#numElements} on the very last iteration of the loop, i.e., the |
| * thread is not working on the node anymore. Note that this requires that there is no code after |
| * the loop in {@code ParallelEvaluator.Evaluate#run}. |
| */ |
| int signaledDeps = -1; |
| |
| /** |
| * The set of reverse dependencies that are registered before the node has finished building. Upon |
| * building, these reverse deps will be signaled and then stored in the permanent {@link |
| * InMemoryNodeEntry#reverseDeps}. |
| */ |
| protected Object reverseDepsToSignal = ImmutableList.of(); |
| private List<Object> reverseDepsDataToConsolidate = null; |
| |
| private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL = |
| new ReverseDepsUtilImpl<BuildingState>() { |
| @Override |
| void setReverseDepsObject(BuildingState container, Object object) { |
| container.reverseDepsToSignal = object; |
| } |
| |
| @Override |
| void setDataToConsolidate(BuildingState container, List<Object> dataToConsolidate) { |
| container.reverseDepsDataToConsolidate = dataToConsolidate; |
| } |
| |
| @Override |
| Object getReverseDepsObject(BuildingState container) { |
| return container.reverseDepsToSignal; |
| } |
| |
| @Override |
| List<Object> getDataToConsolidate(BuildingState container) { |
| return container.reverseDepsDataToConsolidate; |
| } |
| |
| @Override |
| public void consolidateReverseDeps(BuildingState container) { |
| // #consolidateReverseDeps is only supported for node entries, not building states. |
| throw new UnsupportedOperationException(); |
| } |
| }; |
| |
| /** Returns whether all known children of this node have signaled that they are done. */ |
| final boolean isReady(int numDirectDeps) { |
| Preconditions.checkState(signaledDeps <= numDirectDeps, "%s %s", numDirectDeps, this); |
| return signaledDeps == numDirectDeps; |
| } |
| |
| /** |
| * Returns true if the entry is marked dirty, meaning that at least one of its transitive |
| * dependencies is marked changed. |
| * |
| * @see NodeEntry#isDirty() |
| */ |
| boolean isDirty() { |
| return false; |
| } |
| |
| /** |
| * Returns true if the entry is known to require re-evaluation. |
| * |
| * @see NodeEntry#isChanged() |
| */ |
| boolean isChanged() { |
| return false; |
| } |
| |
| /** |
| * Helper method to assert that node has finished building, as far as we can tell. We would |
| * actually like to check that the node has been evaluated, but that is not available in this |
| * context. |
| */ |
| protected void checkFinishedBuildingWhenAboutToSetValue() { |
| Preconditions.checkState(isEvaluating(), "not started building %s", this); |
| Preconditions.checkState(!isDirty(), "not done building %s", this); |
| } |
| |
| /** |
| * Puts the node in the "evaluating" state if it is not already in it. Returns true if the node |
| * wasn't already evaluating and false otherwise. Should only be called by {@link |
| * NodeEntry#addReverseDepAndCheckIfDone}. |
| */ |
| final boolean startEvaluating() { |
| boolean result = !isEvaluating(); |
| if (result) { |
| signaledDeps = 0; |
| } |
| return result; |
| } |
| |
| final boolean isEvaluating() { |
| return signaledDeps > -1; |
| } |
| |
| /** |
| * Increments the number of children known to be finished. Returns true if the number of children |
| * finished is equal to the number of known children. |
| * |
| * <p>If the node is dirty and checking its deps for changes, this also updates dirty state as |
| * needed, via {@link #signalDepInternal}. |
| * |
| * @see NodeEntry#signalDep(Version) |
| */ |
| final boolean signalDep(boolean childChanged, int numDirectDeps) { |
| Preconditions.checkState(isEvaluating(), this); |
| signaledDeps++; |
| signalDepInternal(childChanged, numDirectDeps); |
| return isReady(numDirectDeps); |
| } |
| |
| void signalDepInternal(boolean childChanged, int numDirectDeps) {} |
| |
| /** |
| * Returns reverse deps to signal that have been registered this build. |
| * |
| * @see NodeEntry#getReverseDeps() |
| */ |
| final ImmutableSet<SkyKey> getReverseDepsToSignal() { |
| return REVERSE_DEPS_UTIL.getReverseDeps(this); |
| } |
| |
| /** |
| * Adds a reverse dependency that should be notified when this entry is done. |
| * |
| * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey) |
| */ |
| final void addReverseDepToSignal(SkyKey newReverseDep) { |
| REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep)); |
| } |
| |
| /** @see NodeEntry#removeReverseDep(SkyKey) */ |
| final void removeReverseDepToSignal(SkyKey reverseDep) { |
| REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); |
| } |
| |
| protected ToStringHelper getStringHelper() { |
| return MoreObjects.toStringHelper(this) |
| .add("hash", System.identityHashCode(this)) |
| .add("signaledDeps/evaluating state", signaledDeps) |
| .add("reverseDepsToSignal", REVERSE_DEPS_UTIL.toString(this)); |
| } |
| @Override |
| public final String toString() { |
| return getStringHelper().toString(); |
| } |
| } |