| 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 |
} |