diff options
Diffstat (limited to 'src/main/java')
4 files changed, 439 insertions, 377 deletions
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java index d0d2573af7..ad16c38a88 100644 --- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java +++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java @@ -123,7 +123,7 @@ public class BuildingState { private boolean reverseDepIsSingleObject = false; private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL = - new ReverseDepsUtil<BuildingState>() { + new ReverseDepsUtilImpl<BuildingState>() { @Override void setReverseDepsObject(BuildingState container, Object object) { container.reverseDepsToSignal = object; diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java index 8c1fa7f119..261c836344 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java @@ -98,14 +98,14 @@ public class InMemoryNodeEntry implements NodeEntry { * are O(N). Originally reverseDeps was a HashSet, but because of memory consumption we switched * to a list. * - * <p>Internally, ReverseDepsUtil consolidates this data periodically, and when the set of reverse - * deps is requested. While this operation is not free, it can be done more effectively than - * trying to remove/check each dirty reverse dependency individually (O(N) each time). + * <p>Internally, ReverseDepsUtilImpl consolidates this data periodically, and when the set of + * reverse deps is requested. While this operation is not free, it can be done more effectively + * than trying to remove/check each dirty reverse dependency individually (O(N) each time). */ private List<Object> reverseDepsDataToConsolidate = null; protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL = - new ReverseDepsUtil<InMemoryNodeEntry>() { + new ReverseDepsUtilImpl<InMemoryNodeEntry>() { @Override void setReverseDepsObject(InMemoryNodeEntry container, Object object) { container.reverseDeps = object; @@ -209,16 +209,23 @@ public class InMemoryNodeEntry implements NodeEntry { return ValueWithMetadata.getMaybeErrorInfo(value); } + /** + * Puts entry in "done" state, as checked by {@link #isDone}. Subclasses that override one should + * override the other. + */ + protected void markDone() { + buildingState = null; + } + protected synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() { // Get reverse deps that need to be signaled. ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal(); - REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal); + getReverseDepsUtil().addReverseDeps(this, reverseDepsToSignal); // Force consistency check. - REVERSE_DEPS_UTIL.getReverseDeps(this); + getReverseDepsUtil().getReverseDeps(this); this.directDeps = buildingState.getFinishedDirectDeps().compress(); - // Set state of entry to done. - buildingState = null; + markDone(); if (!keepEdges()) { this.directDeps = null; @@ -257,15 +264,19 @@ public class InMemoryNodeEntry implements NodeEntry { return setStateFinishedAndReturnReverseDeps(); } + protected ReverseDepsUtil<InMemoryNodeEntry> getReverseDepsUtil() { + return REVERSE_DEPS_UTIL; + } + @Override public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) { if (reverseDep != null) { if (keepEdges()) { - REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep); + getReverseDepsUtil().maybeCheckReverseDepNotPresent(this, reverseDep); } if (isDone()) { if (keepEdges()) { - REVERSE_DEPS_UTIL.addReverseDeps(this, ImmutableList.of(reverseDep)); + getReverseDepsUtil().addReverseDeps(this, ImmutableList.of(reverseDep)); } } else { // Parent should never register itself twice in the same build. @@ -284,10 +295,10 @@ public class InMemoryNodeEntry implements NodeEntry { Preconditions.checkNotNull(reverseDep, this); Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this); if (!isDone()) { - REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); + getReverseDepsUtil().removeReverseDep(this, reverseDep); buildingState.addReverseDepToSignal(reverseDep); } else { - REVERSE_DEPS_UTIL.checkReverseDep(this, reverseDep); + getReverseDepsUtil().checkReverseDep(this, reverseDep); } return addReverseDepAndCheckIfDone(null); } @@ -297,7 +308,7 @@ public class InMemoryNodeEntry implements NodeEntry { if (!keepEdges()) { return; } - REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep); + getReverseDepsUtil().removeReverseDep(this, reverseDep); } @Override @@ -308,7 +319,7 @@ public class InMemoryNodeEntry implements NodeEntry { @Override public synchronized Iterable<SkyKey> getReverseDeps() { assertKeepEdges(); - Iterable<SkyKey> reverseDeps = REVERSE_DEPS_UTIL.getReverseDeps(this); + Iterable<SkyKey> reverseDeps = getReverseDepsUtil().getReverseDeps(this); if (isDone()) { return reverseDeps; } else { @@ -349,7 +360,7 @@ public class InMemoryNodeEntry implements NodeEntry { buildingState = BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value); value = null; - return new MarkedDirtyResult(REVERSE_DEPS_UTIL.getReverseDeps(this)); + return new MarkedDirtyResult(getReverseDepsUtil().getReverseDeps(this)); } // 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 @@ -452,7 +463,7 @@ public class InMemoryNodeEntry implements NodeEntry { .add("lastChangedVersion", lastChangedVersion) .add("lastEvaluatedVersion", lastEvaluatedVersion) .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps)) - .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this)) + .add("reverseDeps", getReverseDepsUtil().toString(this)) .add("buildingState", buildingState) .toString(); } @@ -469,7 +480,7 @@ public class InMemoryNodeEntry implements NodeEntry { nodeEntry.value = value; nodeEntry.lastChangedVersion = this.lastChangedVersion; nodeEntry.lastEvaluatedVersion = this.lastEvaluatedVersion; - REVERSE_DEPS_UTIL.addReverseDeps(nodeEntry, REVERSE_DEPS_UTIL.getReverseDeps(this)); + getReverseDepsUtil().addReverseDeps(nodeEntry, getReverseDepsUtil().getReverseDeps(this)); nodeEntry.directDeps = directDeps; nodeEntry.buildingState = null; return nodeEntry; diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java index 86c39ab2e5..219758b30d 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java +++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java @@ -1,4 +1,4 @@ -// Copyright 2014 The Bazel Authors. All rights reserved. +// Copyright 2015 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. @@ -13,376 +13,33 @@ // limitations under the License. package com.google.devtools.build.skyframe; -import com.google.common.base.MoreObjects; -import com.google.common.base.Preconditions; -import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Interner; -import com.google.common.collect.Interners; -import com.google.common.collect.Iterables; -import com.google.common.collect.Lists; -import com.google.devtools.build.lib.collect.CompactHashSet; -import java.util.ArrayList; import java.util.Collection; -import java.util.HashSet; -import java.util.List; -import java.util.Set; - -import javax.annotation.Nullable; /** - * A utility class that allows us to keep the reverse dependencies as an array list instead of a - * set. This is more memory-efficient. At the same time it allows us to group the removals and - * uniqueness checks so that it also performs well. + * A utility interface for dealing with reverse deps in NodeEntry and BuildingState implementations. * - * <p>The reason of this class it to share non-trivial code between BuildingState and NodeEntry. We - * could simply make those two classes extend this class instead, but we would be less - * memory-efficient since object memory alignment does not cross classes (you would have two memory - * alignments, one for the base class and one for the extended one). + * <p>The reason for this interface is to abstract out dealing with reverse deps, which is subject + * to various non-trivial and fairly ugly memory/performance optimizations. * - * <p>This class is public only for the benefit of alternative graph implementations outside of the - * package. + * <p>This interface is public only for the benefit of alternative graph implementations outside of + * the package. */ -public abstract class ReverseDepsUtil<T> { - - static final int MAYBE_CHECK_THRESHOLD = 10; - - private static final Interner<KeyToConsolidate> consolidateInterner = Interners.newWeakInterner(); - - abstract void setReverseDepsObject(T container, Object object); - - abstract void setSingleReverseDep(T container, boolean singleObject); - - abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate); - - abstract Object getReverseDepsObject(T container); - - abstract boolean isSingleReverseDep(T container); - - abstract List<Object> getDataToConsolidate(T container); - - private enum ConsolidateOp { - CHECK, - ADD, - REMOVE - } - - /** - * Opaque container for a pending operation on the reverse deps set. We use subclasses to save - * 8 bytes of memory instead of keeping a field in this class, and we store - * {@link ConsolidateOp#CHECK} operations as the bare {@link SkyKey} in order to save the wrapper - * object in that case. - */ - private abstract static class KeyToConsolidate { - // Do not access directly -- use the {@link #key} static accessor instead. - protected final SkyKey key; - - /** Do not call directly -- use the {@link #create} static method instead. */ - private KeyToConsolidate(SkyKey key) { - this.key = key; - } - - @Override - public String toString() { - return MoreObjects.toStringHelper(this).add("key", key).toString(); - } - - /** Gets which operation was delayed for the given object. */ - static ConsolidateOp op(Object obj) { - if (obj instanceof SkyKey) { - return ConsolidateOp.CHECK; - } - if (obj instanceof KeyToRemove) { - return ConsolidateOp.REMOVE; - } - Preconditions.checkState(obj instanceof KeyToAdd, obj); - return ConsolidateOp.ADD; - } - - /** Gets the key whose operation was delayed for the given object. */ - static SkyKey key(Object obj) { - if (obj instanceof SkyKey) { - return (SkyKey) obj; - } - Preconditions.checkState(obj instanceof KeyToConsolidate, obj); - return ((KeyToConsolidate) obj).key; - } - - static Object create(SkyKey key, ConsolidateOp op) { - switch (op) { - case CHECK: - return key; - case REMOVE: - return consolidateInterner.intern(new KeyToRemove(key)); - case ADD: - return consolidateInterner.intern(new KeyToAdd(key)); - default: - throw new IllegalStateException(op + ", " + key); - } - } - - @Override - public boolean equals(Object obj) { - if (obj == null) { - return false; - } - return this.getClass() == obj.getClass() && this.key.equals(((KeyToConsolidate) obj).key); - } - - @Override - public int hashCode() { - // Overridden in subclasses. - throw new UnsupportedOperationException(key.toString()); - } - } - - private static final class KeyToAdd extends KeyToConsolidate { - KeyToAdd(SkyKey key) { - super(key); - } - - @Override - public int hashCode() { - return key.hashCode(); - } - } - - private static final class KeyToRemove extends KeyToConsolidate { - KeyToRemove(SkyKey key) { - super(key); - } - - @Override - public int hashCode() { - return 42 + 37 * key.hashCode(); - } - } - - private void maybeDelayReverseDepOp(T container, Iterable<SkyKey> reverseDeps, ConsolidateOp op) { - List<Object> consolidations = getDataToConsolidate(container); - int currentReverseDepSize = getCurrentReverseDepSize(container); - if (consolidations == null) { - consolidations = new ArrayList<>(currentReverseDepSize); - setDataToConsolidate(container, consolidations); - } - for (SkyKey reverseDep : reverseDeps) { - consolidations.add(KeyToConsolidate.create(reverseDep, op)); - } - // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized. - if (consolidations.size() == currentReverseDepSize) { - consolidateData(container); - } - } - +public interface ReverseDepsUtil<T> { + void addReverseDeps(T container, Collection<SkyKey> reverseDeps); /** - * We check that the reverse dependency is not already present. We only do that if reverseDeps is - * small, so that it does not impact performance. We do not check if there are delayed data to - * consolidate, since then presence or absence is not known. + * Checks that the reverse dependency is not already present. Implementations may choose not to + * perform this check, or only to do it if reverseDeps is small, so that it does not impact + * performance. */ - void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) { - if (getDataToConsolidate(container) != null) { - return; - } - if (isSingleReverseDep(container)) { - Preconditions.checkState( - !getReverseDepsObject(container).equals(reverseDep), - "Reverse dep %s already present in %s", - reverseDep, - container); - return; - } - @SuppressWarnings("unchecked") - List<SkyKey> asList = (List<SkyKey>) getReverseDepsObject(container); - if (asList.size() < MAYBE_CHECK_THRESHOLD) { - Preconditions.checkState( - !asList.contains(reverseDep), - "Reverse dep %s already present in %s for %s", - reverseDep, - asList, - container); - } - } - - private int getCurrentReverseDepSize(T container) { - return isSingleReverseDep(container) - ? 1 - : ((List<SkyKey>) getReverseDepsObject(container)).size(); - } - - /** - * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are - * dominant over the number of nodes. - * - * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the - * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because - * we also have a decent number of nodes for which the reverseDeps are huge (for example almost - * everything depends on BuildInfo node). - * - * <p>We also optimize for the case where we have only one dependency. In that case we keep the - * object directly instead of a wrapper list. - */ - @SuppressWarnings("unchecked") - public void addReverseDeps(T container, Collection<SkyKey> newReverseDeps) { - if (newReverseDeps.isEmpty()) { - return; - } - List<Object> dataToConsolidate = getDataToConsolidate(container); - if (dataToConsolidate != null) { - maybeDelayReverseDepOp(container, newReverseDeps, ConsolidateOp.ADD); - return; - } - Object reverseDeps = getReverseDepsObject(container); - int reverseDepsSize = isSingleReverseDep(container) ? 1 : ((List<SkyKey>) reverseDeps).size(); - int newSize = reverseDepsSize + newReverseDeps.size(); - if (newSize == 1) { - overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(newReverseDeps)); - } else if (reverseDepsSize == 0) { - overwriteReverseDepsList(container, Lists.newArrayList(newReverseDeps)); - } else if (reverseDepsSize == 1) { - List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize); - newList.add((SkyKey) reverseDeps); - newList.addAll(newReverseDeps); - overwriteReverseDepsList(container, newList); - } else { - ((List<SkyKey>) reverseDeps).addAll(newReverseDeps); - } - } - - void checkReverseDep(T container, SkyKey reverseDep) { - maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.CHECK); - } - - /** - * See {@code addReverseDeps} method. - */ - void removeReverseDep(T container, SkyKey reverseDep) { - maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.REMOVE); - } - - ImmutableSet<SkyKey> getReverseDeps(T container) { - consolidateData(container); - - // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side - // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted, - // and we can't handle that right now. - if (isSingleReverseDep(container)) { - return ImmutableSet.of((SkyKey) getReverseDepsObject(container)); - } else { - @SuppressWarnings("unchecked") - List<SkyKey> reverseDeps = (List<SkyKey>) getReverseDepsObject(container); - ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps); - Preconditions.checkState(set.size() == reverseDeps.size(), - "Duplicate reverse deps present in %s: %s. %s", this, reverseDeps, container); - return set; - } - } - - private void consolidateData(T container) { - List<Object> dataToConsolidate = getDataToConsolidate(container); - if (dataToConsolidate == null) { - return; - } - setDataToConsolidate(container, null); - Object reverseDeps = getReverseDepsObject(container); - if (isSingleReverseDep(container)) { - Preconditions.checkState( - dataToConsolidate.size() == 1, - "dataToConsolidate not size 1 even though only one rdep: %s %s %s", - dataToConsolidate, - reverseDeps, - container); - Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate); - SkyKey key = KeyToConsolidate.key(keyToConsolidate); - switch (KeyToConsolidate.op(keyToConsolidate)) { - case REMOVE: - overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); - // Fall through to check. - case CHECK: - Preconditions.checkState( - key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, container); - break; - case ADD: - throw new IllegalStateException( - "Shouldn't delay add if only one element: " - + keyToConsolidate - + ", " - + reverseDeps - + ", " - + container); - default: - throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + container); - } - return; - } - List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; - Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList); - - if (reverseDepsAsSet.size() != reverseDepsAsList.size()) { - // We're about to crash. Try to print an informative error message. - Set<SkyKey> seen = new HashSet<>(); - List<SkyKey> duplicates = new ArrayList<>(); - for (SkyKey key : reverseDepsAsList) { - if (!seen.add(key)) { - duplicates.add(key); - } - } - throw new IllegalStateException( - (reverseDepsAsList.size() - reverseDepsAsSet.size()) - + " duplicates: " - + duplicates - + " for " - + container); - } - for (Object keyToConsolidate : dataToConsolidate) { - SkyKey key = KeyToConsolidate.key(keyToConsolidate); - switch (KeyToConsolidate.op(keyToConsolidate)) { - case CHECK: - Preconditions.checkState( - reverseDepsAsSet.contains(key), - "%s %s %s", - keyToConsolidate, - reverseDepsAsSet, - container); - break; - case REMOVE: - Preconditions.checkState( - reverseDepsAsSet.remove(key), "%s %s %s", keyToConsolidate, reverseDeps, container); - break; - case ADD: - Preconditions.checkState( - reverseDepsAsSet.add(key), "%s %s %s", keyToConsolidate, reverseDeps, container); - break; - default: - throw new IllegalStateException( - keyToConsolidate + ", " + reverseDepsAsSet + ", " + container); - } - } + void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep); - if (reverseDepsAsSet.isEmpty()) { - overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); - } else if (reverseDepsAsSet.size() == 1) { - overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(reverseDepsAsSet)); - } else { - overwriteReverseDepsList(container, new ArrayList<>(reverseDepsAsSet)); - } - } + void checkReverseDep(T container, SkyKey reverseDep); - String toString(T container) { - return MoreObjects.toStringHelper("ReverseDeps") - .add("reverseDeps", getReverseDepsObject(container)) - .add("singleReverseDep", isSingleReverseDep(container)) - .add("dataToConsolidate", getDataToConsolidate(container)) - .toString(); - } + void removeReverseDep(T container, SkyKey reverseDep); - private void overwriteReverseDepsWithObject(T container, SkyKey newObject) { - setReverseDepsObject(container, newObject); - setSingleReverseDep(container, true); - } + ImmutableSet<SkyKey> getReverseDeps(T container); - private void overwriteReverseDepsList(T container, List<SkyKey> list) { - setReverseDepsObject(container, list); - setSingleReverseDep(container, false); - } + String toString(T container); } diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java new file mode 100644 index 0000000000..11af1005a7 --- /dev/null +++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtilImpl.java @@ -0,0 +1,394 @@ +// 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.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Interner; +import com.google.common.collect.Interners; +import com.google.common.collect.Iterables; +import com.google.common.collect.Lists; +import com.google.devtools.build.lib.collect.CompactHashSet; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import javax.annotation.Nullable; + +/** + * A utility class that allows us to keep the reverse dependencies as an array list instead of a + * set. This is more memory-efficient. At the same time it allows us to group the removals and + * uniqueness checks so that it also performs well. + * + * <p>The reason for making this a separate class is to share non-trivial code between BuildingState + * and NodeEntry. We could simply make those two classes extend this class instead, but we would be + * less memory-efficient since object memory alignment does not cross classes (you would have two + * memory alignments, one for the base class and one for the extended one). + * + */ +public abstract class ReverseDepsUtilImpl<T> implements ReverseDepsUtil<T> { + + static final int MAYBE_CHECK_THRESHOLD = 10; + + private static final Interner<KeyToConsolidate> consolidateInterner = Interners.newWeakInterner(); + + abstract void setReverseDepsObject(T container, Object object); + + abstract void setSingleReverseDep(T container, boolean singleObject); + + abstract void setDataToConsolidate(T container, @Nullable List<Object> dataToConsolidate); + + abstract Object getReverseDepsObject(T container); + + abstract boolean isSingleReverseDep(T container); + + abstract List<Object> getDataToConsolidate(T container); + + private enum ConsolidateOp { + CHECK, + ADD, + REMOVE + } + + /** + * Opaque container for a pending operation on the reverse deps set. We use subclasses to save + * 8 bytes of memory instead of keeping a field in this class, and we store + * {@link ConsolidateOp#CHECK} operations as the bare {@link SkyKey} in order to save the wrapper + * object in that case. + */ + private abstract static class KeyToConsolidate { + // Do not access directly -- use the {@link #key} static accessor instead. + protected final SkyKey key; + + /** Do not call directly -- use the {@link #create} static method instead. */ + private KeyToConsolidate(SkyKey key) { + this.key = key; + } + + @Override + public String toString() { + return MoreObjects.toStringHelper(this).add("key", key).toString(); + } + + /** Gets which operation was delayed for the given object. */ + static ConsolidateOp op(Object obj) { + if (obj instanceof SkyKey) { + return ConsolidateOp.CHECK; + } + if (obj instanceof KeyToRemove) { + return ConsolidateOp.REMOVE; + } + Preconditions.checkState(obj instanceof KeyToAdd, obj); + return ConsolidateOp.ADD; + } + + /** Gets the key whose operation was delayed for the given object. */ + static SkyKey key(Object obj) { + if (obj instanceof SkyKey) { + return (SkyKey) obj; + } + Preconditions.checkState(obj instanceof KeyToConsolidate, obj); + return ((KeyToConsolidate) obj).key; + } + + static Object create(SkyKey key, ConsolidateOp op) { + switch (op) { + case CHECK: + return key; + case REMOVE: + return consolidateInterner.intern(new KeyToRemove(key)); + case ADD: + return consolidateInterner.intern(new KeyToAdd(key)); + default: + throw new IllegalStateException(op + ", " + key); + } + } + + @Override + public boolean equals(Object obj) { + if (obj == null) { + return false; + } + return this.getClass() == obj.getClass() && this.key.equals(((KeyToConsolidate) obj).key); + } + + @Override + public int hashCode() { + // Overridden in subclasses. + throw new UnsupportedOperationException(key.toString()); + } + } + + private static final class KeyToAdd extends KeyToConsolidate { + KeyToAdd(SkyKey key) { + super(key); + } + + @Override + public int hashCode() { + return key.hashCode(); + } + } + + private static final class KeyToRemove extends KeyToConsolidate { + KeyToRemove(SkyKey key) { + super(key); + } + + @Override + public int hashCode() { + return 42 + 37 * key.hashCode(); + } + } + + private void maybeDelayReverseDepOp(T container, Iterable<SkyKey> reverseDeps, ConsolidateOp op) { + List<Object> consolidations = getDataToConsolidate(container); + int currentReverseDepSize = getCurrentReverseDepSize(container); + if (consolidations == null) { + consolidations = new ArrayList<>(currentReverseDepSize); + setDataToConsolidate(container, consolidations); + } + for (SkyKey reverseDep : reverseDeps) { + consolidations.add(KeyToConsolidate.create(reverseDep, op)); + } + // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized. + if (consolidations.size() == currentReverseDepSize) { + consolidateData(container); + } + } + + /** + * We only check if reverse deps is small and there are no delayed data to consolidate, since + * then presence or absence would not be known. + */ + @Override + public void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) { + if (getDataToConsolidate(container) != null) { + return; + } + if (isSingleReverseDep(container)) { + Preconditions.checkState( + !getReverseDepsObject(container).equals(reverseDep), + "Reverse dep %s already present in %s", + reverseDep, + container); + return; + } + @SuppressWarnings("unchecked") + List<SkyKey> asList = (List<SkyKey>) getReverseDepsObject(container); + if (asList.size() < MAYBE_CHECK_THRESHOLD) { + Preconditions.checkState( + !asList.contains(reverseDep), + "Reverse dep %s already present in %s for %s", + reverseDep, + asList, + container); + } + } + + private int getCurrentReverseDepSize(T container) { + return isSingleReverseDep(container) + ? 1 + : ((List<SkyKey>) getReverseDepsObject(container)).size(); + } + + /** + * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are + * dominant over the number of nodes. + * + * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the + * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because + * we also have a decent number of nodes for which the reverseDeps are huge (for example almost + * everything depends on BuildInfo node). + * + * <p>We also optimize for the case where we have only one dependency. In that case we keep the + * object directly instead of a wrapper list. + */ + @SuppressWarnings("unchecked") + public void addReverseDeps(T container, Collection<SkyKey> newReverseDeps) { + if (newReverseDeps.isEmpty()) { + return; + } + List<Object> dataToConsolidate = getDataToConsolidate(container); + if (dataToConsolidate != null) { + maybeDelayReverseDepOp(container, newReverseDeps, ConsolidateOp.ADD); + return; + } + Object reverseDeps = getReverseDepsObject(container); + int reverseDepsSize = isSingleReverseDep(container) ? 1 : ((List<SkyKey>) reverseDeps).size(); + int newSize = reverseDepsSize + newReverseDeps.size(); + if (newSize == 1) { + overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(newReverseDeps)); + } else if (reverseDepsSize == 0) { + overwriteReverseDepsList(container, Lists.newArrayList(newReverseDeps)); + } else if (reverseDepsSize == 1) { + List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize); + newList.add((SkyKey) reverseDeps); + newList.addAll(newReverseDeps); + overwriteReverseDepsList(container, newList); + } else { + ((List<SkyKey>) reverseDeps).addAll(newReverseDeps); + } + } + + @Override + public void checkReverseDep(T container, SkyKey reverseDep) { + maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.CHECK); + } + + /** + * See {@code addReverseDeps} method. + */ + @Override + public void removeReverseDep(T container, SkyKey reverseDep) { + maybeDelayReverseDepOp(container, ImmutableList.of(reverseDep), ConsolidateOp.REMOVE); + } + + @Override + public ImmutableSet<SkyKey> getReverseDeps(T container) { + consolidateData(container); + + // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side + // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted, + // and we can't handle that right now. + if (isSingleReverseDep(container)) { + return ImmutableSet.of((SkyKey) getReverseDepsObject(container)); + } else { + @SuppressWarnings("unchecked") + List<SkyKey> reverseDeps = (List<SkyKey>) getReverseDepsObject(container); + ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps); + Preconditions.checkState( + set.size() == reverseDeps.size(), + "Duplicate reverse deps present in %s: %s. %s", + this, + reverseDeps, + container); + return set; + } + } + + private void consolidateData(T container) { + List<Object> dataToConsolidate = getDataToConsolidate(container); + if (dataToConsolidate == null) { + return; + } + setDataToConsolidate(container, null); + Object reverseDeps = getReverseDepsObject(container); + if (isSingleReverseDep(container)) { + Preconditions.checkState( + dataToConsolidate.size() == 1, + "dataToConsolidate not size 1 even though only one rdep: %s %s %s", + dataToConsolidate, + reverseDeps, + container); + Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate); + SkyKey key = KeyToConsolidate.key(keyToConsolidate); + switch (KeyToConsolidate.op(keyToConsolidate)) { + case REMOVE: + overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); + // Fall through to check. + case CHECK: + Preconditions.checkState( + key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, container); + break; + case ADD: + throw new IllegalStateException( + "Shouldn't delay add if only one element: " + + keyToConsolidate + + ", " + + reverseDeps + + ", " + + container); + default: + throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + container); + } + return; + } + List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps; + Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList); + + if (reverseDepsAsSet.size() != reverseDepsAsList.size()) { + // We're about to crash. Try to print an informative error message. + Set<SkyKey> seen = new HashSet<>(); + List<SkyKey> duplicates = new ArrayList<>(); + for (SkyKey key : reverseDepsAsList) { + if (!seen.add(key)) { + duplicates.add(key); + } + } + throw new IllegalStateException( + (reverseDepsAsList.size() - reverseDepsAsSet.size()) + + " duplicates: " + + duplicates + + " for " + + container); + } + for (Object keyToConsolidate : dataToConsolidate) { + SkyKey key = KeyToConsolidate.key(keyToConsolidate); + switch (KeyToConsolidate.op(keyToConsolidate)) { + case CHECK: + Preconditions.checkState( + reverseDepsAsSet.contains(key), + "%s %s %s", + keyToConsolidate, + reverseDepsAsSet, + container); + break; + case REMOVE: + Preconditions.checkState( + reverseDepsAsSet.remove(key), "%s %s %s", keyToConsolidate, reverseDeps, container); + break; + case ADD: + Preconditions.checkState( + reverseDepsAsSet.add(key), "%s %s %s", keyToConsolidate, reverseDeps, container); + break; + default: + throw new IllegalStateException( + keyToConsolidate + ", " + reverseDepsAsSet + ", " + container); + } + } + + if (reverseDepsAsSet.isEmpty()) { + overwriteReverseDepsList(container, ImmutableList.<SkyKey>of()); + } else if (reverseDepsAsSet.size() == 1) { + overwriteReverseDepsWithObject(container, Iterables.getOnlyElement(reverseDepsAsSet)); + } else { + overwriteReverseDepsList(container, new ArrayList<>(reverseDepsAsSet)); + } + } + + @Override + public String toString(T container) { + return MoreObjects.toStringHelper("ReverseDeps") + .add("reverseDeps", getReverseDepsObject(container)) + .add("singleReverseDep", isSingleReverseDep(container)) + .add("dataToConsolidate", getDataToConsolidate(container)) + .toString(); + } + + private void overwriteReverseDepsWithObject(T container, SkyKey newObject) { + setReverseDepsObject(container, newObject); + setSingleReverseDep(container, true); + } + + private void overwriteReverseDepsList(T container, List<SkyKey> list) { + setReverseDepsObject(container, list); + setSingleReverseDep(container, false); + } +} |