blob: 60ece94d019f30c58458c2c0b9b445a27091150d [file] [log] [blame]
// 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.ImmutableCollection;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* 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>We could simply make {@link InMemoryNodeEntry} extend this class, 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). We could also merge this
* functionality directly into {@link InMemoryNodeEntry} at the cost of increasing its size and
* complexity even more.
*
* <p>The operations {@link #addReverseDep}, {@link #checkReverseDep}, and {@link #removeReverseDep}
* here are optimized for a done entry. Done entries rarely have rdeps added and removed, but do
* have {@link Op#CHECK} operations performed frequently. As well, done node entries may never have
* their data forcibly consolidated, since their reverse deps will only be retrieved as a whole if
* they are marked dirty. Thus, we consolidate periodically.
*
* <p>{@link InMemoryNodeEntry} manages pending reverse dep operations on a marked-dirty or
* initially evaluating node itself, using similar logic tuned to those cases, and calls into {@link
* #consolidateDataAndReturnNewElements} when transitioning to done.
*/
abstract class ReverseDepsUtility {
/**
* Returns the {@link Op} to store bare instead of wrapping in {@link KeyToConsolidate}.
*
* <p>We can store one type of operation bare in order to save memory. For done nodes, most
* operations are {@link Op#CHECK}. For nodes on their initial build and nodes not keeping reverse
* deps, most are {@link Op#ADD}.
*/
static Op getOpToStoreBare(InMemoryNodeEntry entry) {
DirtyBuildingState dirtyBuildingState = entry.dirtyBuildingState;
if (dirtyBuildingState == null) {
return Op.CHECK;
}
return entry.keepsEdges() && dirtyBuildingState.isDirty() ? Op.CHECK : Op.ADD;
}
private static void maybeDelayReverseDepOp(InMemoryNodeEntry entry, SkyKey reverseDep, Op op) {
List<Object> consolidations = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
int currentReverseDepSize = getCurrentReverseDepSize(entry);
if (consolidations == null) {
consolidations = new ArrayList<>(currentReverseDepSize);
entry.setReverseDepsDataToConsolidateForReverseDepsUtil(consolidations);
}
consolidations.add(KeyToConsolidate.create(reverseDep, op, entry));
// TODO(janakr): Should we consolidate more aggressively? This threshold can be customized.
if (consolidations.size() >= currentReverseDepSize) {
consolidateData(entry);
}
}
private static boolean isSingleReverseDep(InMemoryNodeEntry entry) {
return !(entry.getReverseDepsRawForReverseDepsUtil() instanceof List);
}
@SuppressWarnings("unchecked") // Cast to list.
private static int getCurrentReverseDepSize(InMemoryNodeEntry entry) {
return isSingleReverseDep(entry)
? 1
: ((List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil()).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") // Cast to SkyKey and List.
static void addReverseDep(InMemoryNodeEntry entry, SkyKey newReverseDep) {
List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
if (dataToConsolidate != null) {
maybeDelayReverseDepOp(entry, newReverseDep, Op.ADD);
return;
}
Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
int reverseDepsSize = isSingleReverseDep(entry) ? 1 : ((List<SkyKey>) reverseDeps).size();
if (reverseDepsSize == 0) {
entry.setSingleReverseDepForReverseDepsUtil(newReverseDep);
} else if (reverseDepsSize == 1) {
List<SkyKey> newList = Lists.newArrayListWithExpectedSize(2);
newList.add((SkyKey) reverseDeps);
newList.add(newReverseDep);
entry.setReverseDepsForReverseDepsUtil(newList);
} else {
((List<SkyKey>) reverseDeps).add(newReverseDep);
}
}
static void checkReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) {
maybeDelayReverseDepOp(entry, reverseDep, Op.CHECK);
}
/** See {@link #addReverseDep} method. */
static void removeReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) {
maybeDelayReverseDepOp(entry, reverseDep, Op.REMOVE);
}
static void removeReverseDepsMatching(InMemoryNodeEntry entry, Set<SkyKey> deletedKeys) {
consolidateData(entry);
ImmutableSet<SkyKey> currentReverseDeps =
ImmutableSet.copyOf(getReverseDeps(entry, /*checkConsistency=*/ true));
writeReverseDepsSet(entry, Sets.difference(currentReverseDeps, deletedKeys));
}
static ImmutableCollection<SkyKey> getReverseDeps(
InMemoryNodeEntry entry, boolean checkConsistency) {
consolidateData(entry);
// 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(entry)) {
return ImmutableSet.of((SkyKey) entry.getReverseDepsRawForReverseDepsUtil());
} else {
@SuppressWarnings("unchecked")
List<SkyKey> reverseDeps = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
if (!checkConsistency) {
return ImmutableList.copyOf(reverseDeps);
}
ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
Preconditions.checkState(
set.size() == reverseDeps.size(),
"Duplicate reverse deps present in %s: %s",
reverseDeps,
entry);
return set;
}
}
static Set<SkyKey> returnNewElements(InMemoryNodeEntry entry) {
return consolidateDataAndReturnNewElements(entry, /*mutateObject=*/ false);
}
@SuppressWarnings("unchecked") // List and bare SkyKey casts.
private static Set<SkyKey> consolidateDataAndReturnNewElements(
InMemoryNodeEntry entry, boolean mutateObject) {
List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
if (dataToConsolidate == null) {
return ImmutableSet.of();
}
// On a node's initial build (or if not keeping rdeps), we don't need to build up two different
// sets for "all reverse deps" and "new reverse deps" - they are all new.
Op opToStoreBare = getOpToStoreBare(entry);
boolean allRdepsAreNew = opToStoreBare == Op.ADD;
Set<SkyKey> allReverseDeps;
Set<SkyKey> newReverseDeps;
Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
if (isSingleReverseDep(entry)) {
Preconditions.checkState(!allRdepsAreNew, entry);
allReverseDeps = CompactHashSet.create((SkyKey) reverseDeps);
newReverseDeps = CompactHashSet.create();
} else {
List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
if (allRdepsAreNew) {
Preconditions.checkState(reverseDepsAsList.isEmpty(), entry);
allReverseDeps = null;
newReverseDeps = CompactHashSet.createWithExpectedSize(dataToConsolidate.size());
} else {
allReverseDeps = getReverseDepsSet(entry, reverseDepsAsList);
newReverseDeps = CompactHashSet.create();
}
}
for (Object keyToConsolidate : dataToConsolidate) {
SkyKey key = KeyToConsolidate.key(keyToConsolidate);
switch (KeyToConsolidate.op(keyToConsolidate, opToStoreBare)) {
case CHECK:
Preconditions.checkState(!allRdepsAreNew, entry);
Preconditions.checkState(
allReverseDeps.contains(key),
"Reverse dep not present: %s %s %s %s",
keyToConsolidate,
allReverseDeps,
dataToConsolidate,
entry);
Preconditions.checkState(
newReverseDeps.add(key),
"Duplicate new reverse dep: %s %s %s %s",
keyToConsolidate,
allReverseDeps,
dataToConsolidate,
entry);
break;
case REMOVE:
if (!allRdepsAreNew) {
Preconditions.checkState(
allReverseDeps.remove(key),
"Reverse dep to be removed not present: %s %s %s %s",
keyToConsolidate,
allReverseDeps,
dataToConsolidate,
entry);
}
Preconditions.checkState(
newReverseDeps.remove(key),
"Reverse dep to be removed not present: %s %s %s %s",
keyToConsolidate,
newReverseDeps,
dataToConsolidate,
entry);
break;
case REMOVE_OLD:
Preconditions.checkState(!allRdepsAreNew, entry);
Preconditions.checkState(
allReverseDeps.remove(key),
"Reverse dep to be removed not present: %s %s %s %s",
keyToConsolidate,
allReverseDeps,
dataToConsolidate,
entry);
Preconditions.checkState(
!newReverseDeps.contains(key),
"Reverse dep shouldn't have been added to new: %s %s %s %s",
keyToConsolidate,
allReverseDeps,
dataToConsolidate,
entry);
break;
case ADD:
if (!allRdepsAreNew) {
Preconditions.checkState(
allReverseDeps.add(key),
"Duplicate reverse deps: %s %s %s %s",
keyToConsolidate,
reverseDeps,
dataToConsolidate,
entry);
}
Preconditions.checkState(
newReverseDeps.add(key),
"Duplicate new reverse deps: %s %s %s %s",
keyToConsolidate,
reverseDeps,
dataToConsolidate,
entry);
break;
}
}
if (mutateObject) {
entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
writeReverseDepsSet(entry, allRdepsAreNew ? newReverseDeps : allReverseDeps);
}
return newReverseDeps;
}
static Set<SkyKey> consolidateDataAndReturnNewElements(InMemoryNodeEntry entry) {
return consolidateDataAndReturnNewElements(entry, /*mutateObject=*/ true);
}
@SuppressWarnings("unchecked") // Casts to SkyKey and List.
private static void consolidateData(InMemoryNodeEntry entry) {
List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
if (dataToConsolidate == null) {
return;
}
entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
if (isSingleReverseDep(entry)) {
Preconditions.checkState(
dataToConsolidate.size() == 1,
"dataToConsolidate not size 1 even though only one rdep: %s %s %s",
dataToConsolidate,
reverseDeps,
entry);
Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate);
SkyKey key = KeyToConsolidate.key(keyToConsolidate);
Preconditions.checkState(getOpToStoreBare(entry) == Op.CHECK, entry);
switch (KeyToConsolidate.op(keyToConsolidate, Op.CHECK)) {
case REMOVE:
entry.setReverseDepsForReverseDepsUtil(ImmutableList.of());
// Fall through to check.
case CHECK:
Preconditions.checkState(
key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, entry);
break;
case ADD:
throw new IllegalStateException(
"Shouldn't delay add if only one element: "
+ keyToConsolidate
+ ", "
+ reverseDeps
+ ", "
+ entry);
case REMOVE_OLD:
throw new IllegalStateException(
"Shouldn't be removing old deps if node already done: "
+ keyToConsolidate
+ ", "
+ reverseDeps
+ ", "
+ entry);
default:
throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + entry);
}
return;
}
List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
Set<SkyKey> reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);
Preconditions.checkState(getOpToStoreBare(entry) == Op.CHECK, entry);
for (Object keyToConsolidate : dataToConsolidate) {
SkyKey key = KeyToConsolidate.key(keyToConsolidate);
switch (KeyToConsolidate.op(keyToConsolidate, Op.CHECK)) {
case CHECK:
Preconditions.checkState(
reverseDepsAsSet.contains(key),
"%s %s %s %s",
keyToConsolidate,
reverseDepsAsSet,
dataToConsolidate,
entry);
break;
case REMOVE:
Preconditions.checkState(
reverseDepsAsSet.remove(key),
"%s %s %s %s",
keyToConsolidate,
reverseDeps,
dataToConsolidate,
entry);
break;
case ADD:
Preconditions.checkState(
reverseDepsAsSet.add(key),
"%s %s %s %s",
keyToConsolidate,
reverseDeps,
dataToConsolidate,
entry);
break;
case REMOVE_OLD:
throw new IllegalStateException(
"Shouldn't be removing old deps if node already done: "
+ keyToConsolidate
+ ", "
+ reverseDeps
+ ", "
+ dataToConsolidate
+ ", "
+ entry);
default:
throw new IllegalStateException(
keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry);
}
}
writeReverseDepsSet(entry, reverseDepsAsSet);
}
private static void writeReverseDepsSet(InMemoryNodeEntry entry, Set<SkyKey> reverseDepsAsSet) {
if (!entry.keepsEdges() || reverseDepsAsSet.isEmpty()) {
entry.setReverseDepsForReverseDepsUtil(ImmutableList.of());
} else if (reverseDepsAsSet.size() == 1) {
entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(reverseDepsAsSet));
} else {
entry.setReverseDepsForReverseDepsUtil(new ArrayList<>(reverseDepsAsSet));
}
}
private static Set<SkyKey> getReverseDepsSet(
InMemoryNodeEntry entry, List<SkyKey> reverseDepsAsList) {
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 "
+ entry);
}
return reverseDepsAsSet;
}
static String toString(InMemoryNodeEntry entry) {
return MoreObjects.toStringHelper("ReverseDeps")
.add("reverseDeps", entry.getReverseDepsRawForReverseDepsUtil())
.add("singleReverseDep", isSingleReverseDep(entry))
.add("dataToConsolidate", entry.getReverseDepsDataToConsolidateForReverseDepsUtil())
.toString();
}
private ReverseDepsUtility() {}
}