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