If --batch, --keep_going, --discard_analysis_cache, and the new --noexperimental_enable_critical_path_profiling flags are all specified, then Bazel will delete Actions from ActionLookupValues as they are executed in order to save memory.

Because an already-run action may output an artifact that is only requested later in the build, we need to maintain a way for the artifact to look up the action. But in most cases we don't need to keep the action itself, just its output metadata.

Some actions unfortunately are needed post-execution, and so we special-case them.

Also includes dependency change with description:
Move action out of key. This keeps action references from polluting the graph -- actions are just stored in one SkyValue, instead of being present in SkyKeys.

This does mean additional memory used: we have a separate ActionLookupData object per Action executed. That may reach ~24M for million-action builds.

PiperOrigin-RevId: 151756383

1 files changed, 122 insertions, 91 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
index 293f53083b..0020c3a3cd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -20,7 +22,8 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
-import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -29,7 +32,6 @@ import com.google.devtools.build.lib.analysis.actions.ActionTemplate;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.skyframe.ArtifactSkyKey.OwnedArtifact;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -42,7 +44,10 @@ import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
+import javax.annotation.Nullable;
 
 /** A builder of values for {@link ArtifactSkyKey} keys. */
 class ArtifactFunction implements SkyFunction {
@@ -69,69 +74,90 @@ class ArtifactFunction implements SkyFunction {
       }
     }
 
-    ActionAnalysisMetadata actionMetadata = extractActionFromArtifact(artifact, env);
-    if (actionMetadata == null) {
+    SkyKey actionLookupKey = getActionLookupKey(artifact);
+    ActionLookupValue actionLookupValue = getActionLookupValue(actionLookupKey, env, artifact);
+    if (actionLookupValue == null) {
       return null;
     }
+    Integer actionIndex = actionLookupValue.getGeneratingActionIndex(artifact);
+    if (artifact.hasParent() && actionIndex == null) {
+      // If a TreeFileArtifact is created by a templated action, then it should have the proper
+      // reference to its owner. However, if it was created as part of a directory, by the first
+      // TreeArtifact-generating action in a chain, then its parent's generating action also
+      // generated it. This catches that case.
+      actionIndex = actionLookupValue.getGeneratingActionIndex(artifact.getParent());
+    }
+    Preconditions.checkNotNull(
+        actionIndex, "%s %s %s", artifact, actionLookupKey, actionLookupValue);
 
     // If the action is an ActionTemplate, we need to expand the ActionTemplate into concrete
     // actions, execute those actions in parallel and then aggregate the action execution results.
-    if (artifact.isTreeArtifact() && actionMetadata instanceof ActionTemplate) {
-      // Create the directory structures for the output TreeArtifact first.
-      try {
-        FileSystemUtils.createDirectoryAndParents(artifact.getPath());
-      } catch (IOException e) {
-        env.getListener().handle(
-            Event.error(
-                String.format(
-                    "Failed to create output directory for TreeArtifact %s: %s",
-                    artifact,
-                    e.getMessage())));
-        throw new ArtifactFunctionException(e, Transience.TRANSIENT);
-      }
-
-      return createTreeArtifactValueFromActionTemplate(
-          (ActionTemplate) actionMetadata, artifact, env);
-    } else {
-      Preconditions.checkState(
-          actionMetadata instanceof Action,
-          "%s is not a proper Action object and therefore cannot be executed",
-          actionMetadata);
-      Action action = (Action) actionMetadata;
-      ActionExecutionValue actionValue =
-        (ActionExecutionValue) env.getValue(ActionExecutionValue.key(action));
-      if (actionValue == null) {
-        return null;
+    if (artifact.isTreeArtifact()) {
+      ActionAnalysisMetadata actionMetadata =
+          actionLookupValue.getIfPresentAndNotAction(actionIndex);
+      if (actionMetadata instanceof ActionTemplate) {
+        // Create the directory structures for the output TreeArtifact first.
+        try {
+          FileSystemUtils.createDirectoryAndParents(artifact.getPath());
+        } catch (IOException e) {
+          env.getListener()
+              .handle(
+                  Event.error(
+                      String.format(
+                          "Failed to create output directory for TreeArtifact %s: %s",
+                          artifact, e.getMessage())));
+          throw new ArtifactFunctionException(e, Transience.TRANSIENT);
+        }
+
+        return createTreeArtifactValueFromActionTemplate(
+            (ActionTemplate) actionMetadata, artifact, env);
       }
+    }
+    ActionExecutionValue actionValue =
+        (ActionExecutionValue) env.getValue(ActionExecutionValue.key(actionLookupKey, actionIndex));
+    if (actionValue == null) {
+      return null;
+    }
 
-      if (artifact.isTreeArtifact()) {
-        // We get a request for the whole tree artifact. We can just return the associated
-        // TreeArtifactValue.
-        return Preconditions.checkNotNull(actionValue.getTreeArtifactValue(artifact), artifact);
-      } else if (isAggregatingValue(action)) {
+    if (artifact.isTreeArtifact()) {
+      // We get a request for the whole tree artifact. We can just return the associated
+      // TreeArtifactValue.
+      return Preconditions.checkNotNull(actionValue.getTreeArtifactValue(artifact), artifact);
+    }
+    if (artifact.isMiddlemanArtifact()) {
+      Action action =
+          Preconditions.checkNotNull(
+              actionLookupValue.getAction(actionIndex),
+              "Null middleman action? %s %s %s %s",
+              artifact,
+              actionLookupKey,
+              actionLookupValue,
+              actionIndex);
+      if (isAggregatingValue(action)) {
         return createAggregatingValue(artifact, action,
             actionValue.getArtifactValue(artifact), env);
-      } else {
-        return createSimpleFileArtifactValue(artifact, actionValue);
       }
     }
+    return createSimpleFileArtifactValue(artifact, actionValue);
   }
 
   private static TreeArtifactValue createTreeArtifactValueFromActionTemplate(
-      ActionTemplate actionTemplate, Artifact treeArtifact, Environment env)
+      final ActionTemplate actionTemplate, final Artifact treeArtifact, Environment env)
       throws ArtifactFunctionException, InterruptedException {
     // Request the list of expanded actions from the ActionTemplate.
-    ActionTemplateExpansionValue expansionValue = (ActionTemplateExpansionValue) env.getValue(
-        ActionTemplateExpansionValue.key(actionTemplate));
+    SkyKey templateKey = ActionTemplateExpansionValue.key(actionTemplate);
+    ActionTemplateExpansionValue expansionValue =
+        (ActionTemplateExpansionValue) env.getValue(templateKey);
 
     // The expanded actions are not yet available.
     if (env.valuesMissing()) {
       return null;
     }
 
-    // Execute the expanded actions in parallel.
-    Iterable<SkyKey> expandedActionExecutionKeys = ActionExecutionValue.keys(
-        expansionValue.getExpandedActions());
+    List<SkyKey> expandedActionExecutionKeys = new ArrayList<>(expansionValue.getNumActions());
+    for (int i = 0; i < expansionValue.getNumActions(); i++) {
+      expandedActionExecutionKeys.add(ActionExecutionValue.key(templateKey, i));
+    }
     Map<SkyKey, SkyValue> expandedActionValueMap = env.getValues(expandedActionExecutionKeys);
 
     // The execution values of the expanded actions are not yet all available.
@@ -142,18 +168,45 @@ class ArtifactFunction implements SkyFunction {
     // Aggregate the ArtifactValues for individual TreeFileArtifacts into a TreeArtifactValue for
     // the parent TreeArtifact.
     ImmutableMap.Builder<TreeFileArtifact, FileArtifactValue> map = ImmutableMap.builder();
-    for (Map.Entry<SkyKey, SkyValue> entry : expandedActionValueMap.entrySet()) {
-      SkyKey expandedActionExecutionKey = entry.getKey();
-      ActionExecutionValue actionExecutionValue = (ActionExecutionValue) entry.getValue();
-      Action expandedAction = (Action) expandedActionExecutionKey.argument();
-
-      Iterable<TreeFileArtifact> treeFileArtifacts = findActionOutputsWithMatchingParent(
-          expandedAction, treeArtifact);
+    for (int i = 0; i < expansionValue.getNumActions(); i++) {
+      final ActionExecutionValue actionExecutionValue =
+          (ActionExecutionValue)
+              Preconditions.checkNotNull(
+                  expandedActionValueMap.get(expandedActionExecutionKeys.get(i)),
+                  "Missing tree value: %s %s %s %s %s",
+                  treeArtifact,
+                  actionTemplate,
+                  expansionValue,
+                  expandedActionValueMap,
+                  expandedActionExecutionKeys);
+      Iterable<TreeFileArtifact> treeFileArtifacts =
+          Iterables.transform(
+              Iterables.filter(
+                  actionExecutionValue.getAllFileValues().keySet(),
+                  new Predicate<Artifact>() {
+                    @Override
+                    public boolean apply(Artifact artifact) {
+                      Preconditions.checkState(
+                          artifact.hasParent(),
+                          "No parent: %s %s %s %s",
+                          artifact,
+                          treeArtifact,
+                          actionExecutionValue,
+                          actionTemplate);
+                      return artifact.getParent().equals(treeArtifact);
+                    }
+                  }),
+              new Function<Artifact, TreeFileArtifact>() {
+                @Override
+                public TreeFileArtifact apply(Artifact artifact) {
+                  return (TreeFileArtifact) artifact;
+                }
+              });
 
       Preconditions.checkState(
           !Iterables.isEmpty(treeFileArtifacts),
-          "Action %s does not output TreeFileArtifact under %s",
-          expandedAction,
+          "Action denoted by %s does not output TreeFileArtifact under %s",
+          expandedActionExecutionKeys.get(i),
           treeArtifact);
 
       for (TreeFileArtifact treeFileArtifact : treeFileArtifacts) {
@@ -281,48 +334,30 @@ class ArtifactFunction implements SkyFunction {
     return Label.print(((OwnedArtifact) skyKey.argument()).getArtifact().getOwner());
   }
 
-  private static ActionAnalysisMetadata extractActionFromArtifact(
-      Artifact artifact, SkyFunction.Environment env) throws InterruptedException {
+  @VisibleForTesting
+  static SkyKey getActionLookupKey(Artifact artifact) {
     ArtifactOwner artifactOwner = artifact.getArtifactOwner();
 
     Preconditions.checkState(artifactOwner instanceof ActionLookupKey, "", artifact, artifactOwner);
-    SkyKey actionLookupKey = ActionLookupValue.key((ActionLookupKey) artifactOwner);
+    return ActionLookupValue.key((ActionLookupKey) artifactOwner);
+  }
+
+  @Nullable
+  private static ActionLookupValue getActionLookupValue(
+      SkyKey actionLookupKey, SkyFunction.Environment env, Artifact artifact)
+      throws InterruptedException {
     ActionLookupValue value = (ActionLookupValue) env.getValue(actionLookupKey);
     if (value == null) {
-      Preconditions.checkState(artifactOwner == CoverageReportValue.ARTIFACT_OWNER,
-          "Not-yet-present artifact owner: %s", artifactOwner);
+      ArtifactOwner artifactOwner = artifact.getArtifactOwner();
+      Preconditions.checkState(
+          artifactOwner == CoverageReportValue.ARTIFACT_OWNER,
+          "Not-yet-present artifact owner: %s (%s %s)",
+          artifactOwner,
+          artifact,
+          actionLookupKey);
       return null;
     }
-    // The value should already exist (except for the coverage report action output artifacts):
-    // ConfiguredTargetValues were created during the analysis phase, and BuildInfo*Values
-    // were created during the first analysis of a configured target.
-    Preconditions.checkNotNull(value,
-        "Owner %s of %s not in graph %s", artifactOwner, artifact, actionLookupKey);
-
-    ActionAnalysisMetadata action = value.getGeneratingAction(artifact);
-    if (artifact.hasParent()) {
-      // We are trying to resolve the generating action for a TreeFileArtifact. It may not have
-      // a generating action in the action graph at analysis time. In that case, we get the
-      // generating action for its parent TreeArtifact, which contains this TreeFileArtifact.
-      if (action == null) {
-        action = value.getGeneratingAction(artifact.getParent());
-      }
-    }
-
-    return Preconditions.checkNotNull(action,
-        "Value %s does not contain generating action of %s", value, artifact);
-  }
-
-  private static Iterable<TreeFileArtifact> findActionOutputsWithMatchingParent(
-      Action action, Artifact treeArtifact) {
-    ImmutableList.Builder<TreeFileArtifact> matchingOutputs = ImmutableList.builder();
-    for (Artifact output : action.getOutputs()) {
-      Preconditions.checkState(output.hasParent(), "%s must be a TreeFileArtifact", output);
-      if (output.getParent().equals(treeArtifact)) {
-        matchingOutputs.add((TreeFileArtifact) output);
-      }
-    }
-    return matchingOutputs.build();
+    return value;
   }
 
   private static final class ArtifactFunctionException extends SkyFunctionException {
@@ -330,10 +365,6 @@ class ArtifactFunction implements SkyFunction {
       super(e, transience);
     }
 
-    ArtifactFunctionException(ActionExecutionException e, Transience transience) {
-      super(e, transience);
-    }
-
     ArtifactFunctionException(IOException e, Transience transience) {
       super(e, transience);
     }