Add test for checking VarHandle CAS concurrency guarantees
Test: art/test/testrunner/testrunner.py -t 719-varhandle-concurrency
Bug: 208156527
Change-Id: I395ce6346331d43e16660d01499956270740f2e6
diff --git a/TEST_MAPPING b/TEST_MAPPING
index 5ac2d14..ad8df10 100644
--- a/TEST_MAPPING
+++ b/TEST_MAPPING
@@ -1175,6 +1175,9 @@
"name": "art-run-test-718-zipfile-finalizer[com.google.android.art.apex]"
},
{
+ "name": "art-run-test-719-varhandle-concurrency[com.google.android.art.apex]"
+ },
+ {
"name": "art-run-test-721-osr[com.google.android.art.apex]"
},
{
@@ -2464,6 +2467,9 @@
"name": "art-run-test-718-zipfile-finalizer"
},
{
+ "name": "art-run-test-719-varhandle-concurrency"
+ },
+ {
"name": "art-run-test-721-osr"
},
{
diff --git a/test/719-varhandle-concurrency/Android.bp b/test/719-varhandle-concurrency/Android.bp
new file mode 100644
index 0000000..4c9f465
--- /dev/null
+++ b/test/719-varhandle-concurrency/Android.bp
@@ -0,0 +1,40 @@
+// Generated by `regen-test-files`. Do not edit manually.
+
+// Build rules for ART run-test `719-varhandle-concurrency`.
+
+package {
+ // See: http://go/android-license-faq
+ // A large-scale-change added 'default_applicable_licenses' to import
+ // all of the 'license_kinds' from "art_license"
+ // to get the below license kinds:
+ // SPDX-license-identifier-Apache-2.0
+ default_applicable_licenses: ["art_license"],
+}
+
+// Test's Dex code.
+java_test {
+ name: "art-run-test-719-varhandle-concurrency",
+ defaults: ["art-run-test-defaults"],
+ test_config_template: ":art-run-test-target-template",
+ srcs: ["src/**/*.java"],
+ data: [
+ ":art-run-test-719-varhandle-concurrency-expected-stdout",
+ ":art-run-test-719-varhandle-concurrency-expected-stderr",
+ ],
+}
+
+// Test's expected standard output.
+genrule {
+ name: "art-run-test-719-varhandle-concurrency-expected-stdout",
+ out: ["art-run-test-719-varhandle-concurrency-expected-stdout.txt"],
+ srcs: ["expected-stdout.txt"],
+ cmd: "cp -f $(in) $(out)",
+}
+
+// Test's expected standard error.
+genrule {
+ name: "art-run-test-719-varhandle-concurrency-expected-stderr",
+ out: ["art-run-test-719-varhandle-concurrency-expected-stderr.txt"],
+ srcs: ["expected-stderr.txt"],
+ cmd: "cp -f $(in) $(out)",
+}
diff --git a/test/719-varhandle-concurrency/build b/test/719-varhandle-concurrency/build
new file mode 100755
index 0000000..98a9967
--- /dev/null
+++ b/test/719-varhandle-concurrency/build
@@ -0,0 +1,20 @@
+#!/bin/bash
+#
+# Copyright 2022 The Android Open Source Project
+#
+# 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.
+
+# Make us exit on a failure
+set -e
+
+./default-build "$@" --experimental var-handles
diff --git a/test/719-varhandle-concurrency/check b/test/719-varhandle-concurrency/check
new file mode 100755
index 0000000..4adf349
--- /dev/null
+++ b/test/719-varhandle-concurrency/check
@@ -0,0 +1,27 @@
+#!/bin/bash
+#
+# Copyright (C) 2022 The Android Open Source Project
+#
+# 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.
+
+# Inputs:
+# $1: Test's expected standard output
+# $2: Test's actual standard output
+# $3: Test's expected standard error
+# $4: Test's actual standard error
+
+# Test failures are reported through stderr. If a test is running for too long,
+# then it would stop early and report on stdout the number of iterations it ran.
+# Therefore, don't diff stdout with the expected one.
+
+diff --strip-trailing-cr -q "$3" "$4" >/dev/null
diff --git a/test/719-varhandle-concurrency/expected-stderr.txt b/test/719-varhandle-concurrency/expected-stderr.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/719-varhandle-concurrency/expected-stderr.txt
diff --git a/test/719-varhandle-concurrency/expected-stdout.txt b/test/719-varhandle-concurrency/expected-stdout.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/719-varhandle-concurrency/expected-stdout.txt
diff --git a/test/719-varhandle-concurrency/info.txt b/test/719-varhandle-concurrency/info.txt
new file mode 100644
index 0000000..3bd0853
--- /dev/null
+++ b/test/719-varhandle-concurrency/info.txt
@@ -0,0 +1 @@
+Tests concurrency guarantees of VarHandles. Written to test the core issue in b/208156527.
diff --git a/test/719-varhandle-concurrency/src/Main.java b/test/719-varhandle-concurrency/src/Main.java
new file mode 100644
index 0000000..a4e1ecd
--- /dev/null
+++ b/test/719-varhandle-concurrency/src/Main.java
@@ -0,0 +1,229 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * 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.
+ */
+
+import java.lang.invoke.VarHandle;
+import java.lang.invoke.MethodHandles;
+import java.time.Duration;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.Consumer;
+
+/**
+ * Runs tests to validate the concurrency guarantees of VarHandle.
+ *
+ * The tests involve having a lot of tasks and significantly fewer threads. The tasks are stored on
+ * a queue and each thread tries to grab a task from the queue using operations like
+ * VarHandle.compareAndSet(). If the operation works as specified, then each task would only be
+ * handled in a single thread, exactly once.
+ *
+ * The tasks just add atomically a specified integer to a total. If the total is different from the
+ * expected one, then either some tasks were run multiple times (on multiple threads), or some task
+ * were not run at all (skipped by all threads).
+ */
+public class Main {
+ private static final VarHandle QA;
+ static {
+ QA = MethodHandles.arrayElementVarHandle(TestTask[].class);
+ }
+
+ private static final int TASK_COUNT = 10000;
+ private static final int THREAD_COUNT = 100;
+ /* Each test may need several retries before a concurrent failure is seen. In the past, for a
+ * known bug, between 5 and 10 retries were sufficient. Use RETRIES to configure how many
+ * iterations to retry for each test scenario. However, to avoid the test running for too long,
+ * for example with gcstress, set a cap duration in MAX_RETRIES_DURATION. With this at least one
+ * iteration would run, but there could be fewer retries if each of them takes too long. */
+ private static final int RETRIES = 50;
+ private static final Duration MAX_RETRIES_DURATION = Duration.ofMinutes(1);
+
+ public static void main(String[] args) throws Throwable {
+ testConcurrentProcessing(new CompareAndExchangeRunnerFactory(), "compareAndExchange");
+ testConcurrentProcessing(new CompareAndSetRunnerFactory(), "compareAndSet");
+ testConcurrentProcessing(new WeakCompareAndSetRunnerFactory(), "weakCompareAndSet");
+ }
+
+ private static void testConcurrentProcessing(RunnerFactory factory,
+ String testName) throws Throwable {
+ final Duration startTs = Duration.ofNanos(System.nanoTime());
+ final Duration endTs = startTs.plus(MAX_RETRIES_DURATION);
+ for (int i = 0; i < RETRIES; ++i) {
+ concurrentProcessingTestIteration(factory, i, testName);
+ Duration now = Duration.ofNanos(System.nanoTime());
+ if (0 < now.compareTo(endTs)) {
+ System.out.println("Test timed out after " + i + " iterations");
+ break;
+ }
+ }
+ }
+
+ private static void concurrentProcessingTestIteration(RunnerFactory factory,
+ int iteration, String testName) throws Throwable {
+ final TestTask[] tasks = new TestTask[TASK_COUNT];
+ final AtomicInteger result = new AtomicInteger();
+
+ for (int i = 0; i < TASK_COUNT; ++i) {
+ tasks[i] = new TestTask(Integer.valueOf(i+1), result::addAndGet);
+ }
+
+ Thread[] threads = new Thread[THREAD_COUNT];
+ for (int i = 0; i < THREAD_COUNT; ++i) {
+ threads[i] = factory.createRunner(tasks);
+ }
+
+ for (int i = 0; i < THREAD_COUNT; ++i) {
+ threads[i].start();
+ }
+
+ for (int i = 0; i < THREAD_COUNT; ++i) {
+ threads[i].join();
+ }
+
+ check(result.get(), TASK_COUNT * (TASK_COUNT + 1) / 2,
+ testName + " test result not as expected", iteration);
+ }
+
+ /**
+ * Processes the task queue until there are no tasks left.
+ *
+ * The actual task-grabbing mechanism is implemented in subclasses through grabTask(). This allows
+ * testing various mechanisms, like compareAndSet() and compareAndExchange().
+ */
+ private static abstract class TaskRunner extends Thread {
+
+ protected final TestTask[] tasks;
+
+ TaskRunner(TestTask[] tasks) {
+ this.tasks = tasks;
+ }
+
+ @Override
+ public void run() {
+ int i = 0;
+ while (i < TASK_COUNT) {
+ TestTask t = (TestTask) QA.get(tasks, i);
+ if (t == null) {
+ ++i;
+ continue;
+ }
+ if (!grabTask(t, i)) {
+ continue;
+ }
+ ++i;
+ VarHandle.releaseFence();
+ t.exec();
+ }
+ }
+
+ /**
+ * Grabs the next task from the queue in an atomic way.
+ *
+ * Once a task is retrieved successfully, the queue should no longer hold a reference to it.
+ * This would be done, for example, by swapping the task with a null value.
+ *
+ * @param t The task to get from the queue
+ * @param i The index where the task is found
+ *
+ * @return {@code true} if the task has been retrieved and is not available to any other
+ * threads. Otherwise {@code false}. If {@code false} is returned, then either the task was no
+ * longer present on the queue due to another thread grabbing it, or, in case of spurious
+ * failure, the task is still available and no other thread managed to grab it.
+ */
+ protected abstract boolean grabTask(TestTask t, int i);
+ }
+
+ private static class TaskRunnerWithCompareAndExchange extends TaskRunner {
+
+ TaskRunnerWithCompareAndExchange(TestTask[] tasks) {
+ super(tasks);
+ }
+
+ @Override
+ protected boolean grabTask(TestTask t, int i) {
+ return (t == QA.compareAndExchange(tasks, i, t, null));
+ }
+ }
+
+ private static class TaskRunnerWithCompareAndSet extends TaskRunner {
+
+ TaskRunnerWithCompareAndSet(TestTask[] tasks) {
+ super(tasks);
+ }
+
+ @Override
+ protected boolean grabTask(TestTask t, int i) {
+ return QA.compareAndSet(tasks, i, t, null);
+ }
+ }
+
+ private static class TaskRunnerWithWeakCompareAndSet extends TaskRunner {
+
+ TaskRunnerWithWeakCompareAndSet(TestTask[] tasks) {
+ super(tasks);
+ }
+
+ @Override
+ protected boolean grabTask(TestTask t, int i) {
+ return QA.weakCompareAndSet(tasks, i, t, null);
+ }
+ }
+
+
+ private interface RunnerFactory {
+ Thread createRunner(TestTask[] tasks);
+ }
+
+ private static class CompareAndExchangeRunnerFactory implements RunnerFactory {
+ @Override
+ public Thread createRunner(TestTask[] tasks) {
+ return new TaskRunnerWithCompareAndExchange(tasks);
+ }
+ }
+
+ private static class CompareAndSetRunnerFactory implements RunnerFactory {
+ @Override
+ public Thread createRunner(TestTask[] tasks) {
+ return new TaskRunnerWithCompareAndSet(tasks);
+ }
+ }
+
+ private static class WeakCompareAndSetRunnerFactory implements RunnerFactory {
+ @Override
+ public Thread createRunner(TestTask[] tasks) {
+ return new TaskRunnerWithWeakCompareAndSet(tasks);
+ }
+ }
+
+ private static class TestTask {
+ private final Integer ord;
+ private final Consumer<Integer> action;
+
+ TestTask(Integer ord, Consumer<Integer> action) {
+ this.ord = ord;
+ this.action = action;
+ }
+
+ public void exec() {
+ action.accept(ord);
+ }
+ }
+
+ private static void check(int actual, int expected, String msg, int iteration) {
+ if (actual != expected) {
+ System.err.println(String.format("[iteration %d] %s : %d != %d",
+ iteration, msg, actual, expected));
+ System.exit(1);
+ }
+ }
+}