1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 */
22
23 /*
24 * This file is available under and governed by the GNU General Public
25 * License version 2 only, as published by the Free Software Foundation.
26 * However, the following notice accompanied the original version of this
27 * file:
28 *
29 * Written by Martin Buchholz with assistance from members of JCP
30 * JSR-166 Expert Group and released to the public domain, as
31 * explained at http://creativecommons.org/publicdomain/zero/1.0/
32 */
33
34 /*
35 * @test
36 * @modules java.base/java.util.concurrent:open
37 * @run testng WhiteBox
38 * @summary White box tests of implementation details
39 */
40
41 import static org.testng.Assert.*;
42 import org.testng.annotations.DataProvider;
43 import org.testng.annotations.Test;
44
45 import java.io.ByteArrayInputStream;
46 import java.io.ByteArrayOutputStream;
47 import java.io.ObjectInputStream;
48 import java.io.ObjectOutputStream;
49 import java.lang.invoke.MethodHandles;
50 import java.lang.invoke.VarHandle;
51 import java.util.ArrayList;
52 import java.util.Iterator;
53 import java.util.List;
54 import java.util.concurrent.LinkedTransferQueue;
55 import java.util.concurrent.ThreadLocalRandom;
56 import java.util.concurrent.TimeUnit;
57 import static java.util.stream.Collectors.toList;
58 import java.util.function.Consumer;
59
60 @Test
61 public class WhiteBox {
62 final ThreadLocalRandom rnd = ThreadLocalRandom.current();
63 final VarHandle HEAD, TAIL, ITEM, NEXT;
64
65 public WhiteBox() throws ReflectiveOperationException {
66 Class<?> qClass = LinkedTransferQueue.class;
67 Class<?> nodeClass = Class.forName(qClass.getName() + "$Node");
68 MethodHandles.Lookup lookup
69 = MethodHandles.privateLookupIn(qClass, MethodHandles.lookup());
70 HEAD = lookup.findVarHandle(qClass, "head", nodeClass);
71 TAIL = lookup.findVarHandle(qClass, "tail", nodeClass);
72 NEXT = lookup.findVarHandle(nodeClass, "next", nodeClass);
73 ITEM = lookup.findVarHandle(nodeClass, "item", Object.class);
74 }
75
76 Object head(LinkedTransferQueue q) { return HEAD.getVolatile(q); }
77 Object tail(LinkedTransferQueue q) { return TAIL.getVolatile(q); }
78 Object item(Object node) { return ITEM.getVolatile(node); }
79 Object next(Object node) { return NEXT.getVolatile(node); }
80
81 int nodeCount(LinkedTransferQueue q) {
82 int i = 0;
83 for (Object p = head(q); p != null; ) {
84 i++;
85 if (p == (p = next(p))) p = head(q);
86 }
87 return i;
88 }
89
90 int tailCount(LinkedTransferQueue q) {
91 int i = 0;
92 for (Object p = tail(q); p != null; ) {
93 i++;
94 if (p == (p = next(p))) p = head(q);
95 }
96 return i;
97 }
98
99 Object findNode(LinkedTransferQueue q, Object e) {
100 for (Object p = head(q); p != null; ) {
101 if (item(p) != null && e.equals(item(p)))
102 return p;
103 if (p == (p = next(p))) p = head(q);
104 }
105 throw new AssertionError("not found");
106 }
107
108 Iterator iteratorAt(LinkedTransferQueue q, Object e) {
109 for (Iterator it = q.iterator(); it.hasNext(); )
110 if (it.next().equals(e))
111 return it;
112 throw new AssertionError("not found");
113 }
114
115 void assertIsSelfLinked(Object node) {
116 assertSame(next(node), node);
117 assertNull(item(node));
118 }
119 void assertIsNotSelfLinked(Object node) {
120 assertNotSame(node, next(node));
121 }
122
123 @Test
124 public void addRemove() {
125 LinkedTransferQueue q = new LinkedTransferQueue();
126 assertInvariants(q);
127 assertNull(next(head(q)));
128 assertNull(item(head(q)));
129 q.add(1);
130 assertEquals(nodeCount(q), 2);
131 assertInvariants(q);
132 q.remove(1);
133 assertEquals(nodeCount(q), 1);
134 assertInvariants(q);
135 }
136
137 /**
138 * Traversal actions that visit every node and do nothing, but
139 * have side effect of squeezing out dead nodes.
140 */
141 @DataProvider
142 public Object[][] traversalActions() {
143 return List.<Consumer<LinkedTransferQueue>>of(
144 q -> q.forEach(e -> {}),
145 q -> assertFalse(q.contains(new Object())),
146 q -> assertFalse(q.remove(new Object())),
147 q -> q.spliterator().forEachRemaining(e -> {}),
148 q -> q.stream().collect(toList()),
149 q -> assertFalse(q.removeIf(e -> false)),
150 q -> assertFalse(q.removeAll(List.of())))
151 .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
152 }
153
154 @Test(dataProvider = "traversalActions")
155 public void traversalOperationsCollapseLeadingNodes(
156 Consumer<LinkedTransferQueue> traversalAction) {
157 LinkedTransferQueue q = new LinkedTransferQueue();
158 Object oldHead;
159 int n = 1 + rnd.nextInt(5);
160 for (int i = 0; i < n; i++) q.add(i);
161 assertEquals(nodeCount(q), n + 1);
162 oldHead = head(q);
163 traversalAction.accept(q);
164 assertInvariants(q);
165 assertEquals(nodeCount(q), n);
166 assertIsSelfLinked(oldHead);
167 }
168
169 @Test(dataProvider = "traversalActions")
170 public void traversalOperationsCollapseInteriorNodes(
171 Consumer<LinkedTransferQueue> traversalAction) {
172 LinkedTransferQueue q = new LinkedTransferQueue();
173 int n = 6;
174 for (int i = 0; i < n; i++) q.add(i);
175
176 // We must be quite devious to reliably create an interior dead node
177 Object p0 = findNode(q, 0);
178 Object p1 = findNode(q, 1);
179 Object p2 = findNode(q, 2);
180 Object p3 = findNode(q, 3);
181 Object p4 = findNode(q, 4);
182 Object p5 = findNode(q, 5);
183
184 Iterator it1 = iteratorAt(q, 1);
185 Iterator it2 = iteratorAt(q, 2);
186
187 it2.remove(); // causes it2's ancestor to advance to 1
188 assertSame(next(p1), p3);
189 assertSame(next(p2), p3);
190 assertNull(item(p2));
191 it1.remove(); // removes it2's ancestor
192 assertSame(next(p0), p3);
193 assertSame(next(p1), p3);
194 assertSame(next(p2), p3);
195 assertNull(item(p1));
196 assertEquals(it2.next(), 3);
197 it2.remove(); // it2's ancestor can't unlink
198
199 assertSame(next(p0), p3); // p3 is now interior dead node
200 assertSame(next(p1), p4); // it2 uselessly CASed p1.next
201 assertSame(next(p2), p3);
202 assertSame(next(p3), p4);
203 assertInvariants(q);
204
205 int c = nodeCount(q);
206 traversalAction.accept(q);
207 assertEquals(nodeCount(q), c - 1);
208
209 assertSame(next(p0), p4);
210 assertSame(next(p1), p4);
211 assertSame(next(p2), p3);
212 assertSame(next(p3), p4);
213 assertInvariants(q);
214
215 // trailing nodes are not unlinked
216 Iterator it5 = iteratorAt(q, 5); it5.remove();
217 traversalAction.accept(q);
218 assertSame(next(p4), p5);
219 assertNull(next(p5));
220 assertEquals(nodeCount(q), c - 1);
221 }
222
223 /**
224 * Checks that traversal operations collapse a random pattern of
225 * dead nodes as could normally only occur with a race.
226 */
227 @Test(dataProvider = "traversalActions")
228 public void traversalOperationsCollapseRandomNodes(
229 Consumer<LinkedTransferQueue> traversalAction) {
230 LinkedTransferQueue q = new LinkedTransferQueue();
231 int n = rnd.nextInt(6);
232 for (int i = 0; i < n; i++) q.add(i);
233 ArrayList nulledOut = new ArrayList();
234 for (Object p = head(q); p != null; p = next(p))
235 if (rnd.nextBoolean()) {
236 nulledOut.add(item(p));
237 ITEM.setVolatile(p, null);
238 }
239 traversalAction.accept(q);
240 int c = nodeCount(q);
241 assertEquals(q.size(), c - (q.contains(n - 1) ? 0 : 1));
242 for (int i = 0; i < n; i++)
243 assertTrue(nulledOut.contains(i) ^ q.contains(i));
244 }
245
246 /**
247 * Traversal actions that remove every element, and are also
248 * expected to squeeze out dead nodes.
249 */
250 @DataProvider
251 public Object[][] bulkRemovalActions() {
252 return List.<Consumer<LinkedTransferQueue>>of(
253 q -> q.clear(),
254 q -> assertTrue(q.removeIf(e -> true)),
255 q -> assertTrue(q.retainAll(List.of())))
256 .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
257 }
258
259 @Test(dataProvider = "bulkRemovalActions")
260 public void bulkRemovalOperationsCollapseNodes(
261 Consumer<LinkedTransferQueue> bulkRemovalAction) {
262 LinkedTransferQueue q = new LinkedTransferQueue();
263 int n = 1 + rnd.nextInt(5);
264 for (int i = 0; i < n; i++) q.add(i);
265 bulkRemovalAction.accept(q);
266 assertEquals(nodeCount(q), 1);
267 assertInvariants(q);
268 }
269
270 /**
271 * Actions that remove the first element, and are expected to
272 * leave at most one slack dead node at head.
273 */
274 @DataProvider
275 public Object[][] pollActions() {
276 return List.<Consumer<LinkedTransferQueue>>of(
277 q -> assertNotNull(q.poll()),
278 q -> { try { assertNotNull(q.poll(1L, TimeUnit.DAYS)); }
279 catch (Throwable x) { throw new AssertionError(x); }},
280 q -> { try { assertNotNull(q.take()); }
281 catch (Throwable x) { throw new AssertionError(x); }},
282 q -> assertNotNull(q.remove()))
283 .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
284 }
285
286 @Test(dataProvider = "pollActions")
287 public void pollActionsOneNodeSlack(
288 Consumer<LinkedTransferQueue> pollAction) {
289 LinkedTransferQueue q = new LinkedTransferQueue();
290 int n = 1 + rnd.nextInt(5);
291 for (int i = 0; i < n; i++) q.add(i);
292 assertEquals(nodeCount(q), n + 1);
293 for (int i = 0; i < n; i++) {
294 int c = nodeCount(q);
295 boolean slack = item(head(q)) == null;
296 if (slack) assertNotNull(item(next(head(q))));
297 pollAction.accept(q);
298 assertEquals(nodeCount(q), q.isEmpty() ? 1 : c - (slack ? 2 : 0));
299 }
300 assertInvariants(q);
301 }
302
303 /**
304 * Actions that append an element, and are expected to
305 * leave at most one slack node at tail.
306 */
307 @DataProvider
308 public Object[][] addActions() {
309 return List.<Consumer<LinkedTransferQueue>>of(
310 q -> q.add(1),
311 q -> q.offer(1))
312 .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
313 }
314
315 @Test(dataProvider = "addActions")
316 public void addActionsOneNodeSlack(
317 Consumer<LinkedTransferQueue> addAction) {
318 LinkedTransferQueue q = new LinkedTransferQueue();
319 int n = 1 + rnd.nextInt(9);
320 for (int i = 0; i < n; i++) {
321 boolean slack = next(tail(q)) != null;
322 addAction.accept(q);
323 if (slack)
324 assertNull(next(tail(q)));
325 else {
326 assertNotNull(next(tail(q)));
327 assertNull(next(next(tail(q))));
328 }
329 assertInvariants(q);
330 }
331 }
332
333 byte[] serialBytes(Object o) {
334 try {
335 ByteArrayOutputStream bos = new ByteArrayOutputStream();
336 ObjectOutputStream oos = new ObjectOutputStream(bos);
337 oos.writeObject(o);
338 oos.flush();
339 oos.close();
340 return bos.toByteArray();
341 } catch (Exception fail) {
342 throw new AssertionError(fail);
343 }
344 }
345
346 @SuppressWarnings("unchecked")
347 <T> T serialClone(T o) {
348 try {
349 ObjectInputStream ois = new ObjectInputStream
350 (new ByteArrayInputStream(serialBytes(o)));
351 T clone = (T) ois.readObject();
352 assertNotSame(o, clone);
353 assertSame(o.getClass(), clone.getClass());
354 return clone;
355 } catch (Exception fail) {
356 throw new AssertionError(fail);
357 }
358 }
359
360 @Test
361 public void testSerialization() {
362 LinkedTransferQueue q = serialClone(new LinkedTransferQueue());
363 assertInvariants(q);
364 }
365
366 /** Checks conditions which should always be true. */
367 void assertInvariants(LinkedTransferQueue q) {
368 assertNotNull(head(q));
369 assertNotNull(tail(q));
370 // head is never self-linked (but tail may!)
371 for (Object h; next(h = head(q)) == h; )
372 assertNotSame(h, head(q)); // must be update race
373 }
374 }