Debian Codegraph @

test/719-varhandle-concurrency/src/Main.java

raw
1 /*
2 * Copyright (C) 2022 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 import java.lang.invoke.VarHandle;
18 import java.lang.invoke.MethodHandles;
19 import java.time.Duration;
20 import java.util.concurrent.atomic.AtomicInteger;
21 import java.util.function.Consumer;
22
23 /**
24 * Runs tests to validate the concurrency guarantees of VarHandle.
25 *
26 * The tests involve having a lot of tasks and significantly fewer threads. The tasks are stored on
27 * a queue and each thread tries to grab a task from the queue using operations like
28 * VarHandle.compareAndSet(). If the operation works as specified, then each task would only be
29 * handled in a single thread, exactly once.
30 *
31 * The tasks just add atomically a specified integer to a total. If the total is different from the
32 * expected one, then either some tasks were run multiple times (on multiple threads), or some task
33 * were not run at all (skipped by all threads).
34 */
35 public class Main {
36 private static final VarHandle QA;
37 static {
38 QA = MethodHandles.arrayElementVarHandle(TestTask[].class);
39 }
40
41 private static final int TASK_COUNT = 10000;
42 private static final int THREAD_COUNT = 20;
43 /* Each test may need several retries before a concurrent failure is seen. In the past, for a
44 * known bug, between 5 and 10 retries were sufficient. Use RETRIES to configure how many
45 * iterations to retry for each test scenario. However, to avoid the test running for too long,
46 * for example with gcstress, set a cap duration in MAX_RETRIES_DURATION. With this at least one
47 * iteration would run, but there could be fewer retries if each of them takes too long. */
48 private static final int RETRIES = 50;
49 // b/235431387: timeout reduced from 1 minute
50 private static final Duration MAX_RETRIES_DURATION = Duration.ofSeconds(15);
51
52 public static void main(String[] args) throws Throwable {
53 testConcurrentProcessing(new CompareAndExchangeRunnerFactory(), "compareAndExchange");
54 testConcurrentProcessing(new CompareAndSetRunnerFactory(), "compareAndSet");
55 testConcurrentProcessing(new WeakCompareAndSetRunnerFactory(), "weakCompareAndSet");
56 }
57
58 private static void testConcurrentProcessing(RunnerFactory factory, String testName)
59 throws Throwable {
60 final Duration startTs = Duration.ofNanos(System.nanoTime());
61 final Duration endTs = startTs.plus(MAX_RETRIES_DURATION);
62 for (int i = 0; i < RETRIES; ++i) {
63 concurrentProcessingTestIteration(factory, i, testName);
64 Duration now = Duration.ofNanos(System.nanoTime());
65 if (0 < now.compareTo(endTs)) {
66 break;
67 }
68 }
69 }
70
71 private static void concurrentProcessingTestIteration(
72 RunnerFactory factory, int iteration, String testName) throws Throwable {
73 final TestTask[] tasks = new TestTask[TASK_COUNT];
74 final AtomicInteger result = new AtomicInteger();
75
76 for (int i = 0; i < TASK_COUNT; ++i) {
77 tasks[i] = new TestTask(Integer.valueOf(i + 1), result::addAndGet);
78 }
79
80 Thread[] threads = new Thread[THREAD_COUNT];
81 for (int i = 0; i < THREAD_COUNT; ++i) {
82 threads[i] = factory.createRunner(tasks);
83 }
84
85 for (int i = 0; i < THREAD_COUNT; ++i) {
86 threads[i].start();
87 }
88
89 for (int i = 0; i < THREAD_COUNT; ++i) {
90 threads[i].join();
91 }
92
93 check(result.get(),
94 TASK_COUNT * (TASK_COUNT + 1) / 2,
95 testName + " test result not as expected",
96 iteration);
97 }
98
99 /**
100 * Processes the task queue until there are no tasks left.
101 *
102 * The actual task-grabbing mechanism is implemented in subclasses through grabTask().
103 * This allows testing various mechanisms, like compareAndSet() and compareAndExchange().
104 */
105 private static abstract class TaskRunner extends Thread {
106
107 protected final TestTask[] tasks;
108
109 TaskRunner(TestTask[] tasks) {
110 this.tasks = tasks;
111 }
112
113 @Override
114 public void run() {
115 int i = 0;
116 while (i < TASK_COUNT) {
117 TestTask t = (TestTask) QA.get(tasks, i);
118 if (t == null) {
119 ++i;
120 continue;
121 }
122 if (!grabTask(t, i)) {
123 continue;
124 }
125 ++i;
126 VarHandle.releaseFence();
127 t.exec();
128 }
129 }
130
131 /**
132 * Grabs the next task from the queue in an atomic way.
133 *
134 * Once a task is retrieved successfully, the queue should no longer hold a reference to it.
135 * This would be done, for example, by swapping the task with a null value.
136 *
137 * @param t The task to get from the queue
138 * @param i The index where the task is found
139 *
140 * @return {@code true} if the task has been retrieved and is not available to any other
141 * threads. Otherwise {@code false}. If {@code false} is returned, then either the task was
142 * no longer present on the queue due to another thread grabbing it, or, in case of spurious
143 * failure, the task is still available and no other thread managed to grab it.
144 */
145 protected abstract boolean grabTask(TestTask t, int i);
146 }
147
148 private static class TaskRunnerWithCompareAndExchange extends TaskRunner {
149 TaskRunnerWithCompareAndExchange(TestTask[] tasks) {
150 super(tasks);
151 }
152
153 @Override
154 protected boolean grabTask(TestTask t, int i) {
155 return (t == QA.compareAndExchange(tasks, i, t, null));
156 }
157 }
158
159 private static class TaskRunnerWithCompareAndSet extends TaskRunner {
160 TaskRunnerWithCompareAndSet(TestTask[] tasks) {
161 super(tasks);
162 }
163
164 @Override
165 protected boolean grabTask(TestTask t, int i) {
166 return QA.compareAndSet(tasks, i, t, null);
167 }
168 }
169
170 private static class TaskRunnerWithWeakCompareAndSet extends TaskRunner {
171 TaskRunnerWithWeakCompareAndSet(TestTask[] tasks) {
172 super(tasks);
173 }
174
175 @Override
176 protected boolean grabTask(TestTask t, int i) {
177 return QA.weakCompareAndSet(tasks, i, t, null);
178 }
179 }
180
181
182 private interface RunnerFactory {
183 Thread createRunner(TestTask[] tasks);
184 }
185
186 private static class CompareAndExchangeRunnerFactory implements RunnerFactory {
187 @Override
188 public Thread createRunner(TestTask[] tasks) {
189 return new TaskRunnerWithCompareAndExchange(tasks);
190 }
191 }
192
193 private static class CompareAndSetRunnerFactory implements RunnerFactory {
194 @Override
195 public Thread createRunner(TestTask[] tasks) {
196 return new TaskRunnerWithCompareAndSet(tasks);
197 }
198 }
199
200 private static class WeakCompareAndSetRunnerFactory implements RunnerFactory {
201 @Override
202 public Thread createRunner(TestTask[] tasks) {
203 return new TaskRunnerWithWeakCompareAndSet(tasks);
204 }
205 }
206
207 private static class TestTask {
208 private final Integer ord;
209 private final Consumer<Integer> action;
210
211 TestTask(Integer ord, Consumer<Integer> action) {
212 this.ord = ord;
213 this.action = action;
214 }
215
216 public void exec() {
217 action.accept(ord);
218 }
219 }
220
221 private static void check(int actual, int expected, String msg, int iteration) {
222 if (actual != expected) {
223 System.err.println(String.format(
224 "[iteration %d] %s : %d != %d", iteration, msg, actual, expected));
225 System.exit(1);
226 }
227 }
228 }