bazel: add --max_computation_steps flag
This change adds a --max_computation_steps=<n> flag that imposes a limit on the
number of abstract computation steps to execute a single BUILD file.
Its default value is zero, meaning no limit.
The count is deterministic, and is retained in the package metadata.
Abstract computation steps are currently eval, exec, and assign operations in
the tree-walking interpreter, but in future they will mean byte code instructions;
the two measures are incommensurable.
There is no corresponding flag for .bzl files, but they typically
do little more than execute def statements.
In the Usual Benchmark, the minimum limit for success is 4.2e6 steps,
but individual whoppers are readily found in Google's code base that
exceed 5e8 steps.
RELNOTES: The --max_computation_steps flag bounds the computation done by a BUILD file.
PiperOrigin-RevId: 301658760
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index fd2d66f..a12633d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -206,6 +206,13 @@
private ImmutableList<String> registeredExecutionPlatforms;
private ImmutableList<String> registeredToolchains;
+ private long computationSteps;
+
+ /** Returns the number of Starlark computation steps executed by this BUILD file. */
+ public long getComputationSteps() {
+ return computationSteps;
+ }
+
/**
* Package initialization, part 1 of 3: instantiates a new package with the
* given name.
@@ -788,7 +795,8 @@
* precisely, this is the wall time of the call to {@link
* PackageFactory#createPackageFromAst}. Notably, this does not include the time to read
* and parse the package's BUILD file, nor the time to read, parse, or evaluate any of the
- * transitively loaded .bzl files.
+ * transitively loaded .bzl files, and it includes time the OS thread is runnable but not
+ * running.
*/
void onLoadingCompleteAndSuccessful(
Package pkg, StarlarkSemantics starlarkSemantics, long loadTimeNanos);
@@ -808,7 +816,7 @@
@Override
public void onLoadingCompleteAndSuccessful(
- Package pkg, StarlarkSemantics starlarkSemantics, long loadTimeMs) {}
+ Package pkg, StarlarkSemantics starlarkSemantics, long loadTimeNanos) {}
}
/**
@@ -1103,6 +1111,11 @@
packageFunctionUsed = true;
}
+ /** Sets the number of Starlark computation steps executed by this BUILD file. */
+ void setComputationSteps(long n) {
+ pkg.computationSteps = n;
+ }
+
/**
* Sets the default header checking mode.
*/
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index b59ab85..dc05bdd 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -665,6 +665,18 @@
ExtendedEventHandler eventHandler)
throws InvalidPackageException {
packageValidator.validate(pkg, eventHandler);
+
+ // Enforce limit on number of compute steps in BUILD file (b/151622307).
+ long maxSteps = starlarkSemantics.maxComputationSteps();
+ long steps = pkg.getComputationSteps();
+ if (maxSteps > 0 && steps > maxSteps) {
+ throw new InvalidPackageException(
+ pkg.getPackageIdentifier(),
+ String.format(
+ "BUILD file computation took %d steps, but --max_computation_steps=%d",
+ steps, maxSteps));
+ }
+
packageBuilderHelper.onLoadingCompleteAndSuccessful(pkg, starlarkSemantics, loadTimeNanos);
}
@@ -829,6 +841,8 @@
pkgContext.eventHandler.handle(Event.error(ex.getLocation(), ex.getMessage()));
return false;
}
+
+ pkgBuilder.setComputationSteps(thread.getExecutedSteps());
}
return true; // success
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
index aec88df..f907eac 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
@@ -655,6 +655,16 @@
public boolean incompatibleLinkoptsToLinkLibs;
@Option(
+ name = "max_computation_steps",
+ defaultValue = "0",
+ documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
+ effectTags = {OptionEffectTag.BUILD_FILE_SEMANTICS},
+ help =
+ "The maximum number of Starlark computation steps that may be executed by a BUILD file"
+ + " (zero means no limit).")
+ public long maxComputationSteps;
+
+ @Option(
name = "record_rule_instantiation_callstack",
defaultValue = "false",
documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
@@ -724,6 +734,7 @@
.incompatibleRequireLinkerInputCcApi(incompatibleRequireLinkerInputCcApi)
.incompatibleRestrictStringEscapes(incompatibleRestrictStringEscapes)
.incompatibleLinkoptsToLinkLibs(incompatibleLinkoptsToLinkLibs)
+ .maxComputationSteps(maxComputationSteps)
.recordRuleInstantiationCallstack(recordRuleInstantiationCallstack)
.build();
return INTERNER.intern(semantics);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
index e558b08..c9e09b5 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
@@ -233,6 +233,8 @@
fr.dbg.before(fr.thread, loc); // location is now redundant since it's in the thread
}
+ fr.thread.steps++;
+
try {
return execDispatch(fr, st);
} catch (EvalException ex) {
@@ -273,6 +275,8 @@
*/
private static void assign(StarlarkThread.Frame fr, Expression lhs, Object value)
throws EvalException, InterruptedException {
+ fr.thread.steps++;
+
if (lhs instanceof Identifier) {
// x = ...
assignIdentifier(fr, (Identifier) lhs, value);
@@ -394,6 +398,7 @@
}
} else if (lhs instanceof ListExpression) {
+ // TODO(adonovan): make this a static error.
Location loc = stmt.getStartLocation(); // TODO(adonovan): use operator location
throw new EvalException(loc, "cannot perform augmented assignment on a list literal");
@@ -420,6 +425,8 @@
private static Object eval(StarlarkThread.Frame fr, Expression expr)
throws EvalException, InterruptedException {
+ fr.thread.steps++;
+
try {
return doEval(fr, expr);
} catch (EvalException ex) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
index 9d7786e..a541832 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
@@ -272,6 +272,8 @@
public abstract boolean incompatibleLinkoptsToLinkLibs();
+ public abstract long maxComputationSteps();
+
public abstract boolean recordRuleInstantiationCallstack();
@Memoized
@@ -351,6 +353,7 @@
.incompatibleRestrictStringEscapes(false)
.incompatibleUseCcConfigureFromRulesCc(false)
.incompatibleLinkoptsToLinkLibs(false)
+ .maxComputationSteps(0)
.recordRuleInstantiationCallstack(false)
.build();
@@ -447,6 +450,8 @@
public abstract Builder incompatibleLinkoptsToLinkLibs(boolean value);
+ public abstract Builder maxComputationSteps(long value);
+
public abstract Builder recordRuleInstantiationCallstack(boolean value);
public abstract StarlarkSemantics build();
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
index d70f47d..5c41dbd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkThread.java
@@ -84,6 +84,18 @@
private boolean interruptible = true;
+ long steps; // count of logical computation steps executed so far
+
+ /**
+ * Returns the number of Starlark computation steps executed by this thread according to a
+ * small-step semantics. (Today, that means exec, eval, and assign operations executed by the
+ * tree-walking evaluator, but in future will mean byte code instructions; the two are not
+ * commensurable.)
+ */
+ public long getExecutedSteps() {
+ return steps;
+ }
+
/**
* Disables polling of the {@link java.lang.Thread#interrupted} flag during Starlark evaluation.
*/
diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
index c1a5470..099e33f 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
@@ -166,6 +166,7 @@
"--incompatible_restrict_string_escapes=" + rand.nextBoolean(),
"--incompatible_use_cc_configure_from_rules_cc=" + rand.nextBoolean(),
"--internal_skylark_flag_test_canary=" + rand.nextBoolean(),
+ "--max_computation_steps=" + rand.nextLong(),
"--record_rule_instantiation_callstack=" + rand.nextBoolean());
}
@@ -221,6 +222,7 @@
.incompatibleRestrictStringEscapes(rand.nextBoolean())
.incompatibleUseCcConfigureFromRulesCc(rand.nextBoolean())
.internalSkylarkFlagTestCanary(rand.nextBoolean())
+ .maxComputationSteps(rand.nextLong())
.recordRuleInstantiationCallstack(rand.nextBoolean())
.build();
}
