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