From 659974ed5e1fbd2122efc98ed7e1a0e3d5e59472 Mon Sep 17 00:00:00 2001 From: nharmata Date: Thu, 18 Jan 2018 10:49:44 -0800 Subject: Fix bug where an was-inflight-and-is-about-to-be-done NodeEntry has incomplete deps that need to be removed, and these deps are currently duplicated in the NodeEntry's newly requested deps GroupedList. Also add a fast-path to GroupedListHelper#remove(List elements, Set toRemove) for the incredibly common case where toRemove is empty. This saves a wasteful O(elements.size()) scan over elements. This method is unconditionally called each time a SkyFunction restart causes us to add new direct deps (with elements= and toRemove=); in the case where there are a ton of new direct deps, this scan entails wasted cpu and gc churn. The bug only occurs in uncommon case that there are deps to remove. The bug has existed since GroupedList was first introduced into the codebase. In Skyframe-land, this is only observable in nokeep_going mode because in keep_going mode "we do not let SkyFunctions throw errors with missing deps" (quote from comment in AbstractParallelEvaluator). A Bazel-on-Skyframe-land example how this bug could occur in practice is PackageFunction's Skyframe hybrid globbing. If an io error is encountered during legacy globbing, the PackageFunction eagerly throws a SkyFunctionException but it has already requested the Skyframe GlobValue deps. RELNOTES: None PiperOrigin-RevId: 182403943 --- .../java/com/google/devtools/build/lib/util/GroupedList.java | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) (limited to 'src/main/java') diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java index 475e38518b..11bef3fcc2 100644 --- a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java +++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java @@ -343,6 +343,9 @@ public class GroupedList implements Iterable> { * GroupedListHelper. */ private static List remove(List elements, Set toRemove) { + if (toRemove.isEmpty()) { + return elements; + } int removedCount = 0; // elements.size is an upper bound of the needed size. Since normally removal happens just // before the list is finished and compressed, optimizing this size isn't a concern. @@ -369,8 +372,15 @@ public class GroupedList implements Iterable> { } } } + // removedCount can be larger if elements had duplicates and the duplicate was also in toRemove. Preconditions.checkState( - removedCount == toRemove.size(), "%s %s %s", elements, toRemove, newElements); + removedCount >= toRemove.size(), + "removedCount=%s, toRemove.size()=%s, elements=%s toRemove=%s newElements=%s", + removedCount, + toRemove.size(), + elements, + toRemove, + newElements); return newElements; } -- cgit v1.2.3