diff options
Diffstat (limited to 'src/main/java/com/google/devtools/build/skyframe/NodeEntry.java')
| -rw-r--r-- | src/main/java/com/google/devtools/build/skyframe/NodeEntry.java | 581 |
1 files changed, 581 insertions, 0 deletions
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java new file mode 100644 index 0000000000..243189dbcb --- /dev/null +++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java @@ -0,0 +1,581 @@ +// Copyright 2014 Google Inc. 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.annotations.VisibleForTesting; +import com.google.common.base.Objects; +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.devtools.build.lib.util.GroupedList; +import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; +import com.google.devtools.build.lib.util.Pair; + +import java.util.Collection; +import java.util.List; +import java.util.Set; + +import javax.annotation.Nullable; + +/** + * A node in the graph. All operations on this class are thread-safe. Care was taken to provide + * certain compound operations to avoid certain check-then-act races. That means this class is + * somewhat closely tied to the exact Evaluator implementation. + * + * <p>Consider the example with two threads working on two nodes, where one depends on the other, + * say b depends on a. If a completes first, it's done. If it completes second, it needs to signal + * b, and potentially re-schedule it. If b completes first, it must exit, because it will be + * signaled (and re-scheduled) by a. If it completes second, it must signal (and re-schedule) + * itself. However, if the Evaluator supported re-entrancy for a node, then this wouldn't have to + * be so strict, because duplicate scheduling would be less problematic. + * + * <p>The transient state of a {@code NodeEntry} is kept in a {@link BuildingState} object. Many of + * the methods of {@code NodeEntry} are just wrappers around the corresponding + * {@link BuildingState} methods. + * + * <p>This class is non-final only for testing purposes. + * <p>This class is public only for the benefit of alternative graph implementations outside of the + * package. + */ +public class NodeEntry { + /** + * Return code for {@link #addReverseDepAndCheckIfDone(SkyKey)}. + */ + enum DependencyState { + /** The node is done. */ + DONE, + + /** + * The node was just created and needs to be scheduled for its first evaluation pass. The + * evaluator is responsible for signaling the reverse dependency node. + */ + NEEDS_SCHEDULING, + + /** + * The node was already created, but isn't done yet. The evaluator is responsible for + * signaling the reverse dependency node. + */ + ADDED_DEP; + } + + /** Actual data stored in this entry when it is done. */ + private SkyValue value = null; + + /** + * The last version of the graph at which this node entry was changed. In {@link #setValue} it + * may be determined that the data being written to the graph at a given version is the same as + * the already-stored data. In that case, the version will remain the same. The version can be + * thought of as the latest timestamp at which this entry was changed. + */ + private Version version = MinimalVersion.INSTANCE; + + /** + * This object represents a {@link GroupedList}<SkyKey> in a memory-efficient way. It stores the + * direct dependencies of this node, in groups if the {@code SkyFunction} requested them that way. + */ + private Object directDeps = null; + + /** + * This list stores the reverse dependencies of this node that have been declared so far. + * + * <p>In case of a single object we store the object unwrapped, without the list, for + * memory-efficiency. + */ + @VisibleForTesting + protected Object reverseDeps = ImmutableList.of(); + + /** + * We take advantage of memory alignment to avoid doing a nasty {@code instanceof} for knowing + * if {@code reverseDeps} is a single object or a list. + */ + protected boolean reverseDepIsSingleObject = false; + + /** + * During the invalidation we keep the reverse deps to be removed in this list instead of directly + * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N). + * Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list. + * + * <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call + * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done + * more effectively than trying to remove each dirty reverse dependency individually (O(N) each + * time). + */ + private List<SkyKey> reverseDepsToRemove = null; + + private static final ReverseDepsUtil<NodeEntry> REVERSE_DEPS_UTIL = + new ReverseDepsUtil<NodeEntry>() { + @Override + void setReverseDepsObject(NodeEntry container, Object object) { + container.reverseDeps = object; + } + + @Override + void setSingleReverseDep(NodeEntry container, boolean singleObject) { + container.reverseDepIsSingleObject = singleObject; + } + + @Override + void setReverseDepsToRemove(NodeEntry container, List<SkyKey> object) { + container.reverseDepsToRemove = object; + } + + @Override + Object getReverseDepsObject(NodeEntry container) { + return container.reverseDeps; + } + + @Override + boolean isSingleReverseDep(NodeEntry container) { + return container.reverseDepIsSingleObject; + } + + @Override + List<SkyKey> getReverseDepsToRemove(NodeEntry container) { + return container.reverseDepsToRemove; + } + }; + + /** + * The transient state of this entry, after it has been created but before it is done. It allows + * us to keep the current state of the entry across invalidation and successive evaluations. + */ + @VisibleForTesting + protected BuildingState buildingState = new BuildingState(); + + /** + * Construct a NodeEntry. Use ONLY in Skyframe evaluation and graph implementations. + */ + public NodeEntry() { + } + + protected boolean keepEdges() { + return true; + } + + /** Returns whether the entry has been built and is finished evaluating. */ + synchronized boolean isDone() { + return buildingState == null; + } + + /** + * Returns the value stored in this entry. This method may only be called after the evaluation of + * this node is complete, i.e., after {@link #setValue} has been called. + */ + synchronized SkyValue getValue() { + Preconditions.checkState(isDone(), "no value until done. ValueEntry: %s", this); + return ValueWithMetadata.justValue(value); + } + + /** + * Returns the {@link SkyValue} for this entry and the metadata associated with it (Like events + * and errors). This method may only be called after the evaluation of this node is complete, + * i.e., after {@link #setValue} has been called. + */ + synchronized ValueWithMetadata getValueWithMetadata() { + Preconditions.checkState(isDone(), "no value until done: %s", this); + return ValueWithMetadata.wrapWithMetadata(value); + } + + /** + * Returns the value, even if dirty or changed. Returns null otherwise. + */ + public synchronized SkyValue toValue() { + if (isDone()) { + return getErrorInfo() == null ? getValue() : null; + } else if (isChanged() || isDirty()) { + return (buildingState.getLastBuildValue() == null) + ? null + : ValueWithMetadata.justValue(buildingState.getLastBuildValue()); + } + throw new AssertionError("Value in bad state: " + this); + } + + /** + * Returns an immutable iterable of the direct deps of this node. This method may only be called + * after the evaluation of this node is complete, i.e., after {@link #setValue} has been called. + * + * <p>This method is not very efficient, but is only be called in limited circumstances -- + * when the node is about to be deleted, or when the node is expected to have no direct deps (in + * which case the overhead is not so bad). It should not be called repeatedly for the same node, + * since each call takes time proportional to the number of direct deps of the node. + */ + synchronized Iterable<SkyKey> getDirectDeps() { + assertKeepEdges(); + Preconditions.checkState(isDone(), "no deps until done. ValueEntry: %s", this); + return GroupedList.<SkyKey>create(directDeps).toSet(); + } + + /** + * Returns the error, if any, associated to this node. This method may only be called after + * the evaluation of this node is complete, i.e., after {@link #setValue} has been called. + */ + @Nullable + synchronized ErrorInfo getErrorInfo() { + Preconditions.checkState(isDone(), "no errors until done. ValueEntry: %s", this); + return ValueWithMetadata.getMaybeErrorInfo(value); + } + + private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() { + // Get reverse deps that need to be signaled. + ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal(); + REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this); + REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal); + this.directDeps = buildingState.getFinishedDirectDeps().compress(); + + // Set state of entry to done. + buildingState = null; + + if (!keepEdges()) { + this.directDeps = null; + this.reverseDeps = null; + } + return reverseDepsToSignal; + } + + /** + * Returns the set of reverse deps that have been declared so far this build. Only for use in + * debugging and when bubbling errors up in the --nokeep_going case, where we need to know what + * parents this entry has. + */ + synchronized Set<SkyKey> getInProgressReverseDeps() { + Preconditions.checkState(!isDone(), this); + return buildingState.getReverseDepsToSignal(); + } + + /** + * Transitions the node from the EVALUATING to the DONE state and simultaneously sets it to the + * given value and error state. It then returns the set of reverse dependencies that need to be + * signaled. + * + * <p>This is an atomic operation to avoid a race where two threads work on two nodes, where one + * node depends on another (b depends on a). When a finishes, it signals <b>exactly</b> the set + * of reverse dependencies that are registered at the time of the {@code setValue} call. If b + * comes in before a, it is signaled (and re-scheduled) by a, otherwise it needs to do that + * itself. + * + * <p>{@code version} indicates the graph version at which this node is being written. If the + * entry determines that the new value is equal to the previous value, the entry will keep its + * current version. Callers can query that version to see if the node considers its value to have + * changed. + */ + public synchronized Set<SkyKey> setValue(SkyValue value, Version version) { + Preconditions.checkState(isReady(), "%s %s", this, value); + // This check may need to be removed when we move to a non-linear versioning sequence. + Preconditions.checkState(this.version.atMost(version), + "%s %s %s", this, version, value); + + if (isDirty() && buildingState.unchangedFromLastBuild(value)) { + // If the value is the same as before, just use the old value. Note that we don't use the new + // value, because preserving == equality is even better than .equals() equality. + this.value = buildingState.getLastBuildValue(); + } else { + // If this is a new value, or it has changed since the last build, set the version to the + // current graph version. + this.version = version; + this.value = value; + } + + return setStateFinishedAndReturnReverseDeps(); + } + + /** + * Queries if the node is done and adds the given key as a reverse dependency. The return code + * indicates whether a) the node is done, b) the reverse dependency is the first one, so the + * node needs to be scheduled, or c) the reverse dependency was added, and the node does not + * need to be scheduled. + * + * <p>This method <b>must</b> be called before any processing of the entry. This encourages + * callers to check that the entry is ready to be processed. + * + * <p>Adding the dependency and checking if the node needs to be scheduled is an atomic operation + * to avoid a race where two threads work on two nodes, where one depends on the other (b depends + * on a). In that case, we need to ensure that b is re-scheduled exactly once when a is done. + * However, a may complete first, in which case b has to re-schedule itself. Also see {@link + * #setValue}. + * + * <p>If the parameter is {@code null}, then no reverse dependency is added, but we still check + * if the node needs to be scheduled. + */ + synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) { + if (reverseDep != null) { + if (keepEdges()) { + REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this); + REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep); + } + if (isDone()) { + if (keepEdges()) { + REVERSE_DEPS_UTIL.addReverseDeps(this, ImmutableList.of(reverseDep)); + } + } else { + // Parent should never register itself twice in the same build. + buildingState.addReverseDepToSignal(reverseDep); + } + } + if (isDone()) { + return DependencyState.DONE; + } + return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING + : DependencyState.ADDED_DEP; + } + + /** + * Removes a reverse dependency. + */ + synchronized void removeReverseDep(SkyKey reverseDep) { + if (!keepEdges()) { + return; + } + REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); + if (!isDone()) { + // This is currently unnecessary -- the only time we remove a reverse dep that was added this + // build is during the clean following a build failure. In that case, this node that is not + // done will be deleted soon, so clearing the reverse dep is not required. + buildingState.removeReverseDepToSignal(reverseDep); + } + } + + /** + * Returns a copy of the set of reverse dependencies. Note that this introduces a potential + * check-then-act race; {@link #removeReverseDep} may fail for a key that is returned here. + */ + synchronized Iterable<SkyKey> getReverseDeps() { + assertKeepEdges(); + Preconditions.checkState(isDone() || buildingState.getReverseDepsToSignal().isEmpty(), + "Reverse deps should only be queried before the build has begun " + + "or after the node is done %s", this); + return REVERSE_DEPS_UTIL.getReverseDeps(this); + } + + /** + * Tell this node that one of its dependencies is now done. Callers must check the return value, + * and if true, they must re-schedule this node for evaluation. Equivalent to + * {@code #signalDep(Long.MAX_VALUE)}. Since this entry's version is less than + * {@link Long#MAX_VALUE}, informing this entry that a child of it has version + * {@link Long#MAX_VALUE} will force it to re-evaluate. + */ + synchronized boolean signalDep() { + return signalDep(/*childVersion=*/new IntVersion(Long.MAX_VALUE)); + } + + /** + * Tell this entry that one of its dependencies is now done. Callers must check the return value, + * and if true, they must re-schedule this node for evaluation. + * + * @param childVersion If this entry {@link #isDirty()} and {@code childVersion} is not at most + * {@link #getVersion()}, then this entry records that one of its children has changed since it + * was last evaluated (namely, it was last evaluated at version {@link #getVersion()} and the + * child was last evaluated at {@code childVersion}. Thus, the next call to + * {@link #getDirtyState()} will return {@link BuildingState.DirtyState#REBUILDING}. + */ + synchronized boolean signalDep(Version childVersion) { + Preconditions.checkState(!isDone(), "Value must not be done in signalDep %s", this); + return buildingState.signalDep(/*childChanged=*/!childVersion.atMost(getVersion())); + } + + /** + * Returns true if the entry is marked dirty, meaning that at least one of its transitive + * dependencies is marked changed. + */ + public synchronized boolean isDirty() { + return !isDone() && buildingState.isDirty(); + } + + /** + * Returns true if the entry is marked changed, meaning that it must be re-evaluated even if its + * dependencies' values have not changed. + */ + synchronized boolean isChanged() { + return !isDone() && buildingState.isChanged(); + } + + /** Checks that a caller is not trying to access not-stored graph edges. */ + private void assertKeepEdges() { + Preconditions.checkState(keepEdges(), "Graph edges not stored. %s", this); + } + + /** + * Marks this node dirty, or changed if {@code isChanged} is true. The node is put in the + * just-created state. It will be re-evaluated if necessary during the evaluation phase, + * but if it has not changed, it will not force a re-evaluation of its parents. + * + * @return The direct deps and value of this entry, or null if the entry has already been marked + * dirty. In the latter case, the caller should abort its handling of this node, since another + * thread is already dealing with it. + */ + @Nullable + synchronized Pair<? extends Iterable<SkyKey>, ? extends SkyValue> markDirty(boolean isChanged) { + assertKeepEdges(); + if (isDone()) { + GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps); + buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value); + Pair<? extends Iterable<SkyKey>, ? extends SkyValue> result = + Pair.of(lastDirectDeps.toSet(), value); + value = null; + directDeps = null; + return result; + } + // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty + // thread may have lost the race, but it is the caller's responsibility not to try to mark + // this node changed twice. The end result of racing markers must be a changed node, since one + // of the markers is trying to mark the node changed. + Preconditions.checkState(isChanged != isChanged(), + "Cannot mark node dirty twice or changed twice: %s", this); + Preconditions.checkState(value == null, "Value should have been reset already %s", this); + Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this); + if (isChanged) { + // If the changed marker lost the race, we just need to mark changed in this method -- all + // other work was done by the dirty marker. + buildingState.markChanged(); + } + return null; + } + + /** + * Marks this entry as up-to-date at this version. + * + * @return {@link Set} of reverse dependencies to signal that this node is done. + */ + synchronized Set<SkyKey> markClean() { + this.value = buildingState.getLastBuildValue(); + // This checks both the value and the direct deps, but since we're passing in the same value, + // the value check should be trivial. + Preconditions.checkState(buildingState.unchangedFromLastBuild(this.value), + "Direct deps must be the same as those found last build for node to be marked clean: %s", + this); + Preconditions.checkState(isDirty(), this); + Preconditions.checkState(!buildingState.isChanged(), "shouldn't be changed: %s", this); + return setStateFinishedAndReturnReverseDeps(); + } + + /** + * Forces this node to be reevaluated, even if none of its dependencies are known to have + * changed. + * + * <p>Used when an external caller has reason to believe that re-evaluating may yield a new + * result. This method should not be used if one of the normal deps of this node has changed, + * the usual change-pruning process should work in that case. + */ + synchronized void forceRebuild() { + buildingState.forceChanged(); + } + + /** + * Gets the current version of this entry. + */ + synchronized Version getVersion() { + return version; + } + + /** + * Gets the current state of checking this dirty entry to see if it must be re-evaluated. Must be + * called each time evaluation of a dirty entry starts to find the proper action to perform next, + * as enumerated by {@link BuildingState.DirtyState}. + * + * @see BuildingState#getDirtyState() + */ + synchronized BuildingState.DirtyState getDirtyState() { + return buildingState.getDirtyState(); + } + + /** + * Should only be called if the entry is dirty. During the examination to see if the entry must be + * re-evaluated, this method returns the next group of children to be checked. Callers should + * have already called {@link #getDirtyState} and received a return value of + * {@link BuildingState.DirtyState#CHECK_DEPENDENCIES} before calling this method -- any other + * return value from {@link #getDirtyState} means that this method must not be called, since + * whether or not the node needs to be rebuilt is already known. + * + * <p>Deps are returned in groups. The deps in each group were requested in parallel by the + * {@code SkyFunction} last build, meaning independently of the values of any other deps in this + * group (although possibly depending on deps in earlier groups). Thus the caller may check all + * the deps in this group in parallel, since the deps in all previous groups are verified + * unchanged. See {@link SkyFunction.Environment#getValues} for more on dependency groups. + * + * <p>The caller should register these as deps of this entry using {@link #addTemporaryDirectDeps} + * before checking them. + * + * @see BuildingState#getNextDirtyDirectDeps() + */ + synchronized Collection<SkyKey> getNextDirtyDirectDeps() { + return buildingState.getNextDirtyDirectDeps(); + } + + /** + * Returns the set of direct dependencies. This may only be called while the node is being + * evaluated, that is, before {@link #setValue} and after {@link #markDirty}. + */ + synchronized Set<SkyKey> getTemporaryDirectDeps() { + Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this); + return buildingState.getDirectDepsForBuild(); + } + + synchronized boolean noDepsLastBuild() { + return buildingState.noDepsLastBuild(); + } + + /** + * Remove dep from direct deps. This should only be called if this entry is about to be + * committed as a cycle node, but some of its children were not checked for cycles, either + * because the cycle was discovered before some children were checked; some children didn't have a + * chance to finish before the evaluator aborted; or too many cycles were found when it came time + * to check the children. + */ + synchronized void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps) { + buildingState.removeDirectDeps(unfinishedDeps); + } + + synchronized void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) { + Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this); + buildingState.addDirectDeps(helper); + } + + /** + * Returns true if the node is ready to be evaluated, i.e., it has been signaled exactly as many + * times as it has temporary dependencies. This may only be called while the node is being + * evaluated, that is, before {@link #setValue} and after {@link #markDirty}. + */ + synchronized boolean isReady() { + Preconditions.checkState(!isDone(), "can't be ready if done: %s", this); + return buildingState.isReady(); + } + + @Override + @SuppressWarnings("deprecation") + public String toString() { + return Objects.toStringHelper(this) // MoreObjects is not in Guava + .add("value", value) + .add("version", version) + .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps)) + .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this)) + .add("buildingState", buildingState).toString(); + } + + /** + * Do not use except in custom evaluator implementations! Added only temporarily. + * + * <p>Clones a NodeEntry iff it is a done node. Otherwise it fails. + */ + @Deprecated + public synchronized NodeEntry cloneNodeEntry() { + // As this is temporary, for now lets limit to done nodes + Preconditions.checkState(isDone(), "Only done nodes can be copied"); + NodeEntry nodeEntry = new NodeEntry(); + nodeEntry.value = value; + nodeEntry.version = this.version; + REVERSE_DEPS_UTIL.addReverseDeps(nodeEntry, REVERSE_DEPS_UTIL.getReverseDeps(this)); + nodeEntry.directDeps = directDeps; + nodeEntry.buildingState = null; + return nodeEntry; + } +} |