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
41import static org.testng.Assert.*;
42import org.testng.annotations.DataProvider;
43import org.testng.annotations.Test;
44
45import java.io.ByteArrayInputStream;
46import java.io.ByteArrayOutputStream;
47import java.io.ObjectInputStream;
48import java.io.ObjectOutputStream;
49import java.lang.invoke.MethodHandles;
50import java.lang.invoke.VarHandle;
51import java.util.ArrayList;
52import java.util.Iterator;
53import java.util.List;
54import java.util.concurrent.ConcurrentLinkedQueue;
55import java.util.concurrent.ThreadLocalRandom;
56import static java.util.stream.Collectors.toList;
57import java.util.function.Consumer;
58import java.util.function.Function;
59
60@Test
61public class WhiteBox {
62    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
63    final VarHandle HEAD, TAIL, ITEM, NEXT;
64
65    WhiteBox() throws ReflectiveOperationException {
66        Class<?> qClass = ConcurrentLinkedQueue.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(ConcurrentLinkedQueue q) { return HEAD.getVolatile(q); }
77    Object tail(ConcurrentLinkedQueue 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(ConcurrentLinkedQueue 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    void assertIsSelfLinked(Object node) {
91        assertSame(next(node), node);
92        assertNull(item(node));
93    }
94
95    void assertIsNotSelfLinked(Object node) {
96        assertNotSame(node, next(node));
97    }
98
99    @Test
100    public void addRemove() {
101        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
102        assertInvariants(q);
103        assertNull(item(head(q)));
104        assertEquals(nodeCount(q), 1);
105        q.add(1);
106        assertEquals(nodeCount(q), 2);
107        assertInvariants(q);
108        q.remove(1);
109        assertEquals(nodeCount(q), 1);
110        assertInvariants(q);
111    }
112
113    /**
114     * Traversal actions that visit every node and do nothing, but
115     * have side effect of squeezing out dead nodes.
116     */
117    @DataProvider
118    public Object[][] traversalActions() {
119        return List.<Consumer<ConcurrentLinkedQueue>>of(
120            q -> q.forEach(e -> {}),
121            q -> assertFalse(q.contains(new Object())),
122            q -> assertFalse(q.remove(new Object())),
123            q -> q.spliterator().forEachRemaining(e -> {}),
124            q -> q.stream().collect(toList()),
125            q -> assertFalse(q.removeIf(e -> false)),
126            q -> assertFalse(q.removeAll(List.of())))
127            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
128    }
129
130    @Test(dataProvider = "traversalActions")
131    public void traversalOperationsCollapseNodes(
132        Consumer<ConcurrentLinkedQueue> traversalAction) {
133        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
134        Object oldHead;
135        int n = 1 + rnd.nextInt(5);
136        for (int i = 0; i < n; i++) q.add(i);
137        assertInvariants(q);
138        assertEquals(nodeCount(q), n + 1);
139        oldHead = head(q);
140        traversalAction.accept(q); // collapses head node
141        assertIsSelfLinked(oldHead);
142        assertInvariants(q);
143        assertEquals(nodeCount(q), n);
144        // Iterator.remove does not currently try to collapse dead nodes
145        for (Iterator it = q.iterator(); it.hasNext(); ) {
146            it.next();
147            it.remove();
148        }
149        assertEquals(nodeCount(q), n);
150        assertInvariants(q);
151        oldHead = head(q);
152        traversalAction.accept(q); // collapses all nodes
153        if (n > 1) assertIsSelfLinked(oldHead);
154        assertEquals(nodeCount(q), 1);
155        assertInvariants(q);
156
157        for (int i = 0; i < n + 1; i++) q.add(i);
158        assertEquals(nodeCount(q), n + 2);
159        oldHead = head(q);
160        assertEquals(0, q.poll()); // 2 leading nodes collapsed
161        assertIsSelfLinked(oldHead);
162        assertEquals(nodeCount(q), n);
163        assertTrue(q.remove(n));
164        assertEquals(nodeCount(q), n);
165        traversalAction.accept(q); // trailing node is never collapsed
166    }
167
168    @Test(dataProvider = "traversalActions")
169    public void traversalOperationsCollapseLeadingNodes(
170        Consumer<ConcurrentLinkedQueue> traversalAction) {
171        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
172        Object oldHead;
173        int n = 1 + rnd.nextInt(5);
174        for (int i = 0; i < n; i++) q.add(i);
175        assertEquals(nodeCount(q), n + 1);
176        oldHead = head(q);
177        traversalAction.accept(q);
178        assertInvariants(q);
179        assertEquals(nodeCount(q), n);
180        assertIsSelfLinked(oldHead);
181    }
182
183    @Test(dataProvider = "traversalActions")
184    public void traversalOperationsDoNotSelfLinkInteriorNodes(
185        Consumer<ConcurrentLinkedQueue> traversalAction) {
186        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
187        int c;
188        int n = 3 + rnd.nextInt(3);
189        for (int i = 0; i < n; i++) q.add(i);
190        Object oneNode;
191        for (oneNode = head(q);
192             ! (item(oneNode) != null && item(oneNode).equals(1));
193             oneNode = next(oneNode))
194            ;
195        Object next = next(oneNode);
196        c = nodeCount(q);
197        for (Iterator it = q.iterator(); it.hasNext(); )
198            if (it.next().equals(1)) it.remove();
199        assertEquals(nodeCount(q), c - 1); // iterator detached head!
200        assertNull(item(oneNode));
201        assertSame(next, next(oneNode));
202        assertInvariants(q);
203        c = nodeCount(q);
204        traversalAction.accept(q);
205        assertEquals(nodeCount(q), c - 1);
206        assertSame(next, next(oneNode)); // un-linked, but not self-linked
207    }
208
209    /**
210     * Checks that traversal operations collapse a random pattern of
211     * dead nodes as could normally only occur with a race.
212     */
213    @Test(dataProvider = "traversalActions")
214    public void traversalOperationsCollapseRandomNodes(
215        Consumer<ConcurrentLinkedQueue> traversalAction) {
216        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
217        int n = rnd.nextInt(6);
218        for (int i = 0; i < n; i++) q.add(i);
219        ArrayList nulledOut = new ArrayList();
220        for (Object p = head(q); p != null; p = next(p))
221            if (item(p) != null && rnd.nextBoolean()) {
222                nulledOut.add(item(p));
223                ITEM.setVolatile(p, null);
224            }
225        traversalAction.accept(q);
226        int c = nodeCount(q);
227        assertEquals(q.size(), c - (q.contains(n - 1) ? 0 : 1));
228        for (int i = 0; i < n; i++)
229            assertTrue(nulledOut.contains(i) ^ q.contains(i));
230    }
231
232    /**
233     * Traversal actions that remove every element, and are also
234     * expected to squeeze out dead nodes.
235     */
236    @DataProvider
237    public Object[][] bulkRemovalActions() {
238        return List.<Consumer<ConcurrentLinkedQueue>>of(
239            q -> q.clear(),
240            q -> assertTrue(q.removeIf(e -> true)),
241            q -> assertTrue(q.retainAll(List.of())))
242            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
243    }
244
245    @Test(dataProvider = "bulkRemovalActions")
246    public void bulkRemovalOperationsCollapseNodes(
247        Consumer<ConcurrentLinkedQueue> bulkRemovalAction) {
248        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
249        int n = 1 + rnd.nextInt(5);
250        for (int i = 0; i < n; i++) q.add(i);
251        bulkRemovalAction.accept(q);
252        assertEquals(nodeCount(q), 1);
253        assertInvariants(q);
254    }
255
256    /**
257     * Actions that remove the first element, and are expected to
258     * leave at most one slack dead node at head.
259     */
260    @DataProvider
261    public Object[][] pollActions() {
262        return List.<Consumer<ConcurrentLinkedQueue>>of(
263            q -> assertNotNull(q.poll()),
264            q -> assertNotNull(q.remove()))
265            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
266    }
267
268    @Test(dataProvider = "pollActions")
269    public void pollActionsOneNodeSlack(
270        Consumer<ConcurrentLinkedQueue> pollAction) {
271        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
272        int n = 1 + rnd.nextInt(5);
273        for (int i = 0; i < n; i++) q.add(i);
274        assertEquals(nodeCount(q), n + 1);
275        for (int i = 0; i < n; i++) {
276            int c = nodeCount(q);
277            boolean slack = item(head(q)) == null;
278            if (slack) assertNotNull(item(next(head(q))));
279            pollAction.accept(q);
280            assertEquals(nodeCount(q), q.isEmpty() ? 1 : c - (slack ? 2 : 0));
281        }
282        assertInvariants(q);
283    }
284
285    /**
286     * Actions that append an element, and are expected to
287     * leave at most one slack node at tail.
288     */
289    @DataProvider
290    public Object[][] addActions() {
291        return List.<Consumer<ConcurrentLinkedQueue>>of(
292            q -> q.add(1),
293            q -> q.offer(1))
294            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
295    }
296
297    @Test(dataProvider = "addActions")
298    public void addActionsOneNodeSlack(
299        Consumer<ConcurrentLinkedQueue> addAction) {
300        ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
301        int n = 1 + rnd.nextInt(5);
302        for (int i = 0; i < n; i++) {
303            boolean slack = next(tail(q)) != null;
304            addAction.accept(q);
305            if (slack)
306                assertNull(next(tail(q)));
307            else {
308                assertNotNull(next(tail(q)));
309                assertNull(next(next(tail(q))));
310            }
311            assertInvariants(q);
312        }
313    }
314
315    byte[] serialBytes(Object o) {
316        try {
317            ByteArrayOutputStream bos = new ByteArrayOutputStream();
318            ObjectOutputStream oos = new ObjectOutputStream(bos);
319            oos.writeObject(o);
320            oos.flush();
321            oos.close();
322            return bos.toByteArray();
323        } catch (Exception fail) {
324            throw new AssertionError(fail);
325        }
326    }
327
328    @SuppressWarnings("unchecked")
329    <T> T serialClone(T o) {
330        try {
331            ObjectInputStream ois = new ObjectInputStream
332                (new ByteArrayInputStream(serialBytes(o)));
333            T clone = (T) ois.readObject();
334            assertNotSame(o, clone);
335            assertSame(o.getClass(), clone.getClass());
336            return clone;
337        } catch (Exception fail) {
338            throw new AssertionError(fail);
339        }
340    }
341
342    public void testSerialization() {
343        ConcurrentLinkedQueue q = serialClone(new ConcurrentLinkedQueue());
344        assertInvariants(q);
345    }
346
347    /** Checks conditions which should always be true. */
348    void assertInvariants(ConcurrentLinkedQueue q) {
349        assertNotNull(head(q));
350        assertNotNull(tail(q));
351        // head is never self-linked (but tail may!)
352        for (Object h; next(h = head(q)) == h; )
353            assertNotSame(h, head(q)); // must be update race
354    }
355}
356