| // Copyright 2016 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 static com.google.common.base.Preconditions.checkState; |
| import static java.lang.Math.min; |
| |
| import com.google.common.annotations.VisibleForTesting; |
| import com.google.common.base.MoreObjects; |
| import com.google.common.collect.ImmutableSet; |
| import com.google.devtools.build.lib.unsafe.UnsafeProvider; |
| import com.google.devtools.build.skyframe.NodeEntry.DirtyState; |
| import com.google.devtools.build.skyframe.NodeEntry.DirtyType; |
| import java.util.List; |
| import javax.annotation.Nullable; |
| import sun.misc.Unsafe; |
| |
| /** |
| * State for a node that has been dirtied, and will be checked to see if it needs re-evaluation, and |
| * either marked clean or re-evaluated. |
| * |
| * <p>This class is public only for the benefit of alternative graph implementations outside of the |
| * package. |
| */ |
| public abstract class DirtyBuildingState implements PriorityTracker { |
| private static final int NOT_EVALUATING_SENTINEL = -1; |
| |
| static DirtyBuildingState create( |
| DirtyType dirtyType, |
| GroupedDeps lastBuildDirectDeps, |
| SkyValue lastBuildValue, |
| boolean hasLowFanout) { |
| return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue, hasLowFanout); |
| } |
| |
| static DirtyBuildingState createNew(boolean hasLowFanout) { |
| return new FullDirtyBuildingState(DirtyType.CHANGE, null, null, hasLowFanout); |
| } |
| |
| /** |
| * The state of a dirty node. A node is marked dirty in the DirtyBuildingState constructor, and |
| * goes into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link |
| * DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node was |
| * itself changed or not. Never null. |
| */ |
| private DirtyState dirtyState; |
| |
| /** |
| * The number of dependencies that are known to be done in a {@link NodeEntry}. |
| * |
| * <p>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>To solve the first problem, the {@link NodeEntry#signalDep} method 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 |
| * GroupedDeps#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 |
| * {@link ParallelEvaluator.Evaluate#run}. |
| */ |
| private int signaledDeps = NOT_EVALUATING_SENTINEL; |
| |
| /** |
| * The number of external dependencies (in contrast to the number of internal dependencies which |
| * are tracked in NodeEntry). We never keep information about external dependencies across |
| * Skyframe calls. |
| */ |
| // We do not strictly require a counter here; all external deps from one SkyFunction evaluation |
| // pass are registered as a single logical dependency, and the SkyFunction is only re-evaluated if |
| // all of them complete. Therefore, we only need a single bit to track this fact. If the mere |
| // existence of this field turns out to be a significant memory burden, we could change the |
| // implementation by moving to a single-bit approach, and then store that bit as part of the |
| // dirtyState field, e.g., by adding a REBUILDING_WAITING_FOR_EXTERNAL_DEPS enum value, as this |
| // can only happen during evaluation. |
| private int externalDeps; |
| |
| /** |
| * Priority information packed into 32-bits. |
| * |
| * <p>Packing is used because Java lacks support for native short operations and masking |
| * operations are needed to fit 1-bit of information about whether the {@link SkyKey} has low |
| * fanout. This field has the following layout. |
| * |
| * <ol> |
| * <li><i>Has Low Fanout</i> (1-bit) - 1 if {@link SkyKey#hasLowFanout} is true for the |
| * underlying key. |
| * <li><i>Depth</i> (15-bits) - the current estimated depth. |
| * <li><i>Restart Count</i> (16-bits, unsigned) - incremented when this node restarts. |
| * </ol> |
| */ |
| private volatile int priority = HAS_LOW_FANOUT_MASK; |
| |
| /** |
| * The dependencies requested (with group markers) last time the node was built (and below, the |
| * value last time the node was built). They will be compared to dependencies requested on this |
| * build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null, |
| * it means that this node is being built for the first time. See {@link |
| * InMemoryNodeEntry#directDeps} for more on dependency group storage. |
| * |
| * <p>Public only for the use of alternative graph implementations. |
| */ |
| @Nullable |
| public abstract GroupedDeps getLastBuildDirectDeps() throws InterruptedException; |
| |
| /** |
| * The number of groups of the dependencies requested last time when the node was built. |
| * |
| * <p>Getting the number of last-built dependencies should not throw {@link InterruptedException}. |
| */ |
| protected abstract int getNumOfGroupsInLastBuildDirectDeps(); |
| |
| /** The number of total dependencies requested the last time the node was built. */ |
| public abstract int getNumElementsInLastBuildDirectDeps(); |
| |
| /** |
| * The value of the node the last time it was built. |
| * |
| * <p>Public only for the use of alternative graph implementations. |
| */ |
| @Nullable |
| public abstract SkyValue getLastBuildValue() throws InterruptedException; |
| |
| /** |
| * Group of children to be checked next in the process of determining if this entry needs to be |
| * re-evaluated. Used by {@link DirtyBuildingState#getNextDirtyDirectDeps} and {@link #signalDep}. |
| */ |
| protected int dirtyDirectDepIndex; |
| |
| /** |
| * Constructor. |
| * |
| * @param hasLowFanout indicates that this node is not expected to have high dependency fanout. |
| * Satisfied by by {@link SkyKey#hasLowFanout}. |
| */ |
| protected DirtyBuildingState(DirtyType dirtyType, boolean hasLowFanout) { |
| dirtyState = dirtyType.getInitialDirtyState(); |
| // We need to iterate through the deps to see if they have changed, or to remove them if one |
| // has. Initialize the iterating index. |
| dirtyDirectDepIndex = 0; |
| if (!hasLowFanout) { |
| this.priority = 0; |
| } |
| } |
| |
| /** Returns true if this state does have information about a previously built version. */ |
| protected abstract boolean isDirty(); |
| |
| final void markChanged() { |
| checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this); |
| checkState(dirtyDirectDepIndex == 0, "Unexpected evaluation: %s", this); |
| dirtyState = DirtyState.NEEDS_REBUILDING; |
| } |
| |
| final void markForceRebuild() { |
| if (dirtyState == DirtyState.CHECK_DEPENDENCIES) { |
| dirtyState = DirtyState.NEEDS_REBUILDING; |
| } |
| } |
| |
| final void forceRebuild(int numTemporaryDirectDeps) { |
| checkState(numTemporaryDirectDeps + externalDeps == signaledDeps, this); |
| checkState( |
| (dirtyState == DirtyState.CHECK_DEPENDENCIES |
| && getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex) |
| || dirtyState == DirtyState.NEEDS_FORCED_REBUILDING, |
| this); |
| dirtyState = DirtyState.FORCED_REBUILDING; |
| } |
| |
| final boolean isEvaluating() { |
| return signaledDeps > NOT_EVALUATING_SENTINEL; |
| } |
| |
| final boolean isChanged() { |
| return dirtyState == DirtyState.NEEDS_REBUILDING |
| || dirtyState == DirtyState.NEEDS_FORCED_REBUILDING |
| || dirtyState == DirtyState.REBUILDING |
| || dirtyState == DirtyState.FORCED_REBUILDING; |
| } |
| |
| private void checkFinishedBuildingWhenAboutToSetValue() { |
| checkState( |
| dirtyState == DirtyState.VERIFIED_CLEAN |
| || dirtyState == DirtyState.REBUILDING |
| || dirtyState == DirtyState.FORCED_REBUILDING, |
| "not done building %s", |
| this); |
| } |
| |
| /** |
| * Signals that a child is done. |
| * |
| * <p>If this node is not yet known to need rebuilding, sets {@link #dirtyState} to {@link |
| * DirtyState#NEEDS_REBUILDING} if the child has changed, and {@link DirtyState#VERIFIED_CLEAN} if |
| * the child has not changed and this was the last child to be checked (as determined by {@code |
| * isReady} and comparing {@link #dirtyDirectDepIndex} and {@link |
| * DirtyBuildingState#getNumOfGroupsInLastBuildDirectDeps()}. |
| */ |
| final void signalDep( |
| InMemoryNodeEntry entry, Version childVersion, @Nullable SkyKey childForDebugging) { |
| // Synchronization isn't needed here because the only caller is InMemoryNodeEntry, which does it |
| // through the synchronized method signalDep. |
| checkState(isEvaluating(), "%s %s", entry, childForDebugging); |
| signaledDeps++; |
| if (isChanged()) { |
| return; |
| } |
| |
| // childVersion > version.lastEvaluated() means the child has changed since the last evaluation. |
| boolean childChanged = !childVersion.atMost(entry.version.lastEvaluated()); |
| if (childChanged) { |
| dirtyState = DirtyState.NEEDS_REBUILDING; |
| } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES |
| && isReady(entry.getNumTemporaryDirectDeps()) |
| && getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex) { |
| // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was the |
| // last block of deps to be checked. |
| dirtyState = DirtyState.VERIFIED_CLEAN; |
| } |
| } |
| |
| final void addExternalDep() { |
| checkState(isEvaluating()); |
| externalDeps++; |
| } |
| |
| /** |
| * Returns true if {@code newValue}.equals the value from the last time this node was built. |
| * Should only be used by {@link NodeEntry#setValue}. |
| * |
| * <p>Changes in direct deps do <i>not</i> force this to return false. Only the value is |
| * considered. |
| */ |
| final boolean unchangedFromLastBuild(SkyValue newValue) throws InterruptedException { |
| checkFinishedBuildingWhenAboutToSetValue(); |
| return !(newValue instanceof NotComparableSkyValue) |
| && getLastBuildValue() != null |
| && getLastBuildValue().equals(newValue); |
| } |
| |
| /** |
| * Returns true if the deps requested during this evaluation ({@code directDeps}) are exactly |
| * those requested the last time this node was built, in the same order. |
| */ |
| final boolean depsUnchangedFromLastBuild(GroupedDeps directDeps) throws InterruptedException { |
| checkFinishedBuildingWhenAboutToSetValue(); |
| return getLastBuildDirectDeps().equals(directDeps); |
| } |
| |
| final boolean noDepsLastBuild() { |
| return getNumOfGroupsInLastBuildDirectDeps() == 0; |
| } |
| |
| /** Returns the {@link DirtyState} as documented by {@link NodeEntry#getDirtyState}. */ |
| final DirtyState getDirtyState() { |
| return dirtyState; |
| } |
| |
| /** |
| * Gets the next children to be re-evaluated to see if this dirty node needs to be re-evaluated. |
| * |
| * <p>See {@link NodeEntry#getNextDirtyDirectDeps}. |
| */ |
| final List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException { |
| checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this); |
| checkState(dirtyDirectDepIndex < getNumOfGroupsInLastBuildDirectDeps(), this); |
| return getLastBuildDirectDeps().getDepGroup(dirtyDirectDepIndex++); |
| } |
| |
| /** |
| * Returns the remaining direct deps that have not been checked. If {@code preservePosition} is |
| * true, this method is non-mutating. If {@code preservePosition} is false, the caller must |
| * process the returned set, and so subsequent calls to this method will return the empty set. |
| */ |
| ImmutableSet<SkyKey> getAllRemainingDirtyDirectDeps(boolean preservePosition) |
| throws InterruptedException { |
| if (getLastBuildDirectDeps() == null) { |
| return ImmutableSet.of(); |
| } |
| ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder(); |
| for (int ind = dirtyDirectDepIndex; ind < getNumOfGroupsInLastBuildDirectDeps(); ind++) { |
| result.addAll(getLastBuildDirectDeps().getDepGroup(ind)); |
| } |
| if (!preservePosition) { |
| dirtyDirectDepIndex = getNumOfGroupsInLastBuildDirectDeps(); |
| } |
| return result.build(); |
| } |
| |
| /** |
| * Resets counters that track evaluation state. May only be called when its corresponding node has |
| * no outstanding unsignaled deps, because otherwise this resetting and that signalling would |
| * race. |
| */ |
| final void resetForRestartFromScratch() { |
| checkState( |
| dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this); |
| signaledDeps = 0; |
| externalDeps = 0; |
| dirtyDirectDepIndex = 0; |
| |
| // Resets the evaluation count. |
| int snapshot; |
| do { |
| snapshot = priority; |
| } while (!UNSAFE.compareAndSwapInt( |
| this, PRIORITY_OFFSET, snapshot, snapshot & ~EVALUATION_COUNT_MASK)); |
| } |
| |
| protected void markRebuilding() { |
| checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this); |
| dirtyState = DirtyState.REBUILDING; |
| } |
| |
| void startEvaluating() { |
| checkState(!isEvaluating(), this); |
| signaledDeps = 0; |
| } |
| |
| /** Returns whether all known children of this node have signaled that they are done. */ |
| boolean isReady(int numDirectDeps) { |
| // Avoids calling Preconditions.checkState because it showed up in garbage profiles due to |
| // boxing of the int format args. |
| if (signaledDeps > numDirectDeps + externalDeps) { |
| throw new IllegalStateException(String.format("%s %s %s", numDirectDeps, externalDeps, this)); |
| } |
| return signaledDeps == numDirectDeps + externalDeps; |
| } |
| |
| /** |
| * A bound on depth to avoid overflow. |
| * |
| * <p>The maximum observed depth in our benchmark is ~150. |
| */ |
| @VisibleForTesting static final int DEPTH_SATURATION_BOUND = 512; |
| |
| /** |
| * A bound on evaluation count to avoid overflow. |
| * |
| * <p>The maximum observed evaluation count in our benchmark is 4. |
| */ |
| @VisibleForTesting static final int EVALUATION_COUNT_SATURATION_BOUND = 32; |
| |
| @Override |
| public int getPriority() { |
| int snapshot = priority; |
| |
| // Fanout occupies the top-most bit. Shifts it over one bit so later computations don't need to |
| // consider negative priority values. Since this is the highest set bit, low-fanout nodes |
| // always have higher priority than high-fanout nodes. |
| int fanoutAdjustment = (snapshot & HAS_LOW_FANOUT_MASK) >>> 1; |
| int depth = min((snapshot & DEPTH_MASK) >> DEPTH_BIT_OFFSET, DEPTH_SATURATION_BOUND); |
| int evaluationCount = min(snapshot & EVALUATION_COUNT_MASK, EVALUATION_COUNT_SATURATION_BOUND); |
| |
| // This formula was found to produce good results in our benchmark. There's no deep rationale |
| // behind it. It's likely possible to improve it, but iterating is slow. |
| return fanoutAdjustment + depth + evaluationCount * evaluationCount; |
| } |
| |
| @Override |
| public int depth() { |
| return (priority & DEPTH_MASK) >> DEPTH_BIT_OFFSET; |
| } |
| |
| @Override |
| public void updateDepthIfGreater(int proposedDepth) { |
| // Shifts the input for comparison instead of the snapshot, which might otherwise need to be |
| // shifted repeatedly. |
| proposedDepth = (proposedDepth << DEPTH_BIT_OFFSET) & DEPTH_MASK; |
| int snapshot; |
| do { |
| snapshot = priority; |
| if (proposedDepth <= (snapshot & DEPTH_MASK)) { |
| return; |
| } |
| } while (!UNSAFE.compareAndSwapInt( |
| this, PRIORITY_OFFSET, snapshot, (snapshot & ~DEPTH_MASK) | proposedDepth)); |
| } |
| |
| @Override |
| public void incrementEvaluationCount() { |
| UNSAFE.getAndAddInt(this, PRIORITY_OFFSET, ONE_EVALUATION); |
| } |
| |
| protected MoreObjects.ToStringHelper getStringHelper() { |
| int snapshot = priority; |
| return MoreObjects.toStringHelper(this) |
| .add("dirtyState", dirtyState) |
| .add("signaledDeps", signaledDeps) |
| .add("externalDeps", externalDeps) |
| .add("dirtyDirectDepIndex", dirtyDirectDepIndex) |
| .add("has low fanout", (snapshot & HAS_LOW_FANOUT_MASK) != 0) |
| .add("depth", (snapshot & DEPTH_MASK) >> DEPTH_BIT_OFFSET) |
| .add("evaluation count", (snapshot & EVALUATION_COUNT_MASK)); |
| } |
| |
| @Override |
| public String toString() { |
| return getStringHelper().toString(); |
| } |
| |
| private static class FullDirtyBuildingState extends DirtyBuildingState { |
| private final GroupedDeps lastBuildDirectDeps; |
| private final SkyValue lastBuildValue; |
| |
| private FullDirtyBuildingState( |
| DirtyType dirtyType, |
| GroupedDeps lastBuildDirectDeps, |
| SkyValue lastBuildValue, |
| boolean hasLowFanout) { |
| super(dirtyType, hasLowFanout); |
| this.lastBuildDirectDeps = lastBuildDirectDeps; |
| checkState( |
| !dirtyType.equals(DirtyType.DIRTY) || getNumOfGroupsInLastBuildDirectDeps() > 0, |
| "%s is being marked dirty but has no children that could have dirtied it", |
| this); |
| this.lastBuildValue = lastBuildValue; |
| } |
| |
| @Override |
| protected boolean isDirty() { |
| return lastBuildDirectDeps != null; |
| } |
| |
| @Override |
| public SkyValue getLastBuildValue() { |
| return lastBuildValue; |
| } |
| |
| @Override |
| public GroupedDeps getLastBuildDirectDeps() { |
| return lastBuildDirectDeps; |
| } |
| |
| @Override |
| protected int getNumOfGroupsInLastBuildDirectDeps() { |
| return lastBuildDirectDeps == null ? 0 : lastBuildDirectDeps.numGroups(); |
| } |
| |
| @Override |
| public int getNumElementsInLastBuildDirectDeps() { |
| return lastBuildDirectDeps.numElements(); |
| } |
| |
| @Override |
| protected MoreObjects.ToStringHelper getStringHelper() { |
| return super.getStringHelper() |
| .add("lastBuildDirectDeps", lastBuildDirectDeps) |
| .add("lastBuildValue", lastBuildValue); |
| } |
| } |
| |
| // Masks for `priority`. |
| private static final int HAS_LOW_FANOUT_MASK = 0x8000_0000; |
| |
| private static final int DEPTH_MASK = 0x7FFF_0000; |
| private static final int DEPTH_BIT_OFFSET = 16; |
| |
| private static final int EVALUATION_COUNT_MASK = 0xFFFF; |
| private static final int ONE_EVALUATION = 1; |
| |
| static { |
| checkState(Integer.numberOfTrailingZeros(DEPTH_MASK) == DEPTH_BIT_OFFSET); |
| checkState( |
| Integer.numberOfTrailingZeros(EVALUATION_COUNT_MASK) |
| == Integer.numberOfTrailingZeros(ONE_EVALUATION)); |
| } |
| |
| private static final Unsafe UNSAFE = UnsafeProvider.unsafe(); |
| |
| private static final long PRIORITY_OFFSET; |
| |
| static { |
| try { |
| PRIORITY_OFFSET = |
| UNSAFE.objectFieldOffset(DirtyBuildingState.class.getDeclaredField("priority")); |
| } catch (ReflectiveOperationException e) { |
| throw new ExceptionInInitializerError(e); |
| } |
| } |
| } |