1 /* 2 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* 25 * @test 26 * @bug 6360946 6360948 27 * @summary Test various operations on concurrently mutating collections 28 * @author Martin Buchholz 29 */ 30 31 package test.java.util.Collections; 32 33 import java.util.ArrayDeque; 34 import java.util.ArrayList; 35 import java.util.Collection; 36 import java.util.Collections; 37 import java.util.Comparator; 38 import java.util.Deque; 39 import java.util.HashMap; 40 import java.util.HashSet; 41 import java.util.Hashtable; 42 import java.util.LinkedList; 43 import java.util.List; 44 import java.util.Map; 45 import java.util.Queue; 46 import java.util.Set; 47 import java.util.TreeMap; 48 import java.util.TreeSet; 49 import java.util.Vector; 50 import java.util.concurrent.ArrayBlockingQueue; 51 import java.util.concurrent.ConcurrentHashMap; 52 import java.util.concurrent.ConcurrentLinkedDeque; 53 import java.util.concurrent.ConcurrentLinkedQueue; 54 import java.util.concurrent.ConcurrentSkipListMap; 55 import java.util.concurrent.ConcurrentSkipListSet; 56 import java.util.concurrent.CopyOnWriteArrayList; 57 import java.util.concurrent.CopyOnWriteArraySet; 58 import java.util.concurrent.LinkedBlockingDeque; 59 import java.util.concurrent.LinkedBlockingQueue; 60 import java.util.concurrent.LinkedTransferQueue; 61 62 import static java.util.Collections.asLifoQueue; 63 import static java.util.Collections.checkedList; 64 import static java.util.Collections.checkedMap; 65 import static java.util.Collections.checkedSet; 66 import static java.util.Collections.newSetFromMap; 67 import static java.util.Collections.synchronizedList; 68 import static java.util.Collections.synchronizedMap; 69 import static java.util.Collections.synchronizedSet; 70 import static java.util.Collections.unmodifiableList; 71 import static java.util.Collections.unmodifiableMap; 72 import static java.util.Collections.unmodifiableSet; 73 74 import android.platform.test.annotations.LargeTest; 75 76 public class RacingCollections { 77 /** 78 * How long to run each "race" (in milliseconds). 79 * Turn this up to some higher value like 1000 for stress testing: 80 * java -Dmillis=1000 RacingCollections 81 */ 82 static final long defaultWorkTimeMillis = Long.getLong("millis", 10L); 83 84 /** 85 * Whether to print debug information. 86 */ 87 static final boolean debug = Boolean.getBoolean("debug"); 88 89 static final Integer one = 1; 90 static final Integer two = 2; 91 92 /** 93 * A thread that mutates an object forever, alternating between 94 * being empty and containing singleton "two" 95 */ 96 static class Frobber extends CheckedThread { 97 volatile boolean done = false; keepGoing(int i)98 boolean keepGoing(int i) { return (i % 128 != 0) || ! done; } 99 100 final Object elLoco; Frobber(Object elLoco)101 Frobber(Object elLoco) { 102 this.elLoco = elLoco; 103 this.start(); 104 } 105 106 @SuppressWarnings("unchecked") clear(Object o)107 void clear(Object o) { 108 if (o instanceof Collection) 109 ((Collection<?>)o).clear(); 110 else 111 ((Map<?,?>)o).clear(); 112 } 113 114 @SuppressWarnings("unchecked") realRun()115 void realRun() { 116 // Mutate elLoco wildly forever, checking occasionally for "done" 117 clear(elLoco); 118 if (elLoco instanceof List) { 119 List<Integer> l = (List<Integer>) elLoco; 120 for (int i = 0; keepGoing(i); i++) { 121 switch (i%2) { 122 case 0: l.add(two); break; 123 case 1: l.add(0, two); break; 124 } 125 switch (i%2) { 126 case 0: l.remove(two); break; 127 case 1: l.remove(0); break; 128 }}} 129 else if (elLoco instanceof Deque) { 130 Deque<Integer> q = (Deque<Integer>) elLoco; 131 for (int i = 0; keepGoing(i); i++) { 132 switch (i%6) { 133 case 0: q.add(two); break; 134 case 1: q.addFirst(two); break; 135 case 2: q.addLast(two); break; 136 case 3: q.offer(two); break; 137 case 4: q.offerFirst(two); break; 138 case 5: q.offerLast(two); break; 139 } 140 switch (i%6) { 141 case 0: q.remove(two); break; 142 case 1: q.removeFirst(); break; 143 case 2: q.removeLast(); break; 144 case 3: q.poll(); break; 145 case 4: q.pollFirst(); break; 146 case 5: q.pollLast(); break; 147 }}} 148 else if (elLoco instanceof Queue) { 149 Queue<Integer> q = (Queue<Integer>) elLoco; 150 for (int i = 0; keepGoing(i); i++) { 151 switch (i%2) { 152 case 0: q.add(two); break; 153 case 1: q.offer(two); break; 154 } 155 switch (i%2) { 156 case 0: q.remove(two); break; 157 case 1: q.poll(); break; 158 }}} 159 else if (elLoco instanceof Map) { 160 Map<Integer, Boolean> m = (Map<Integer, Boolean>) elLoco; 161 for (int i = 0; keepGoing(i); i++) { 162 m.put(two, true); 163 m.remove(two); 164 }} 165 else if (elLoco instanceof Collection) { 166 Collection<Integer> c = (Collection<Integer>) elLoco; 167 for (int i = 0; keepGoing(i); i++) { 168 c.add(two); 169 c.remove(two); 170 }} 171 else { throw new Error("Huh? " + elLoco); } 172 } 173 enoughAlready()174 void enoughAlready() { 175 done = true; 176 try { join(); } catch (Throwable t) { unexpected(t); } 177 } 178 } 179 checkEqualSanity(Object theRock, Object elLoco)180 private static void checkEqualSanity(Object theRock, Object elLoco) { 181 //equal(theRock, theRock); 182 equal(elLoco, elLoco); 183 184 // It would be nice someday to have theRock and elLoco never "equal", 185 // although the meaning of "equal" for mutating collections 186 // is a bit fuzzy. Uncomment when/if we fix: 187 // 6374942: Improve thread safety of collection .equals() methods 188 //notEqual(theRock, elLoco); 189 //notEqual(elLoco, theRock); 190 191 notEqual(theRock.toString(), elLoco.toString()); 192 } 193 194 static class Looper { 195 final long quittingTime; 196 int i = 0; Looper()197 Looper() { this(defaultWorkTimeMillis); } Looper(long workTimeMillis)198 Looper(long workTimeMillis) { 199 quittingTime = System.nanoTime() + workTimeMillis * 1024 * 1024; 200 } keepGoing()201 boolean keepGoing() { 202 return (i++ % 128 != 0) || (System.nanoTime() - quittingTime < 0); 203 } 204 } 205 frob(Object theRock, Object elLoco)206 private static void frob(Object theRock, Object elLoco) { 207 Frobber frobber = new Frobber(elLoco); 208 try { 209 if (theRock instanceof Collection) { 210 @SuppressWarnings("unchecked") 211 Collection<Integer> c = (Collection<Integer>) theRock; 212 if (! c.contains(one)) 213 c.add(one); 214 } else { 215 @SuppressWarnings("unchecked") 216 Map<Integer, Boolean> m = (Map<Integer, Boolean>) theRock; 217 if (! m.containsKey(one)) 218 m.put(one, true); 219 } 220 for (Looper looper = new Looper(); looper.keepGoing(); ) 221 checkEqualSanity(theRock, elLoco); 222 } 223 catch (Throwable t) { unexpected(t); } 224 finally { frobber.enoughAlready(); } 225 } 226 newConcurrentMaps()227 private static List<Map<Integer, Boolean>> newConcurrentMaps() { 228 List<Map<Integer, Boolean>> list = new ArrayList<>(); 229 list.add(new ConcurrentHashMap<Integer, Boolean>()); 230 list.add(new ConcurrentSkipListMap<Integer, Boolean>()); 231 return list; 232 } 233 maps()234 private static List<Map<Integer, Boolean>> maps() { 235 List<Map<Integer, Boolean>> list = newConcurrentMaps(); 236 list.add(new Hashtable<Integer, Boolean>()); 237 list.add(new HashMap<Integer, Boolean>()); 238 list.add(new TreeMap<Integer, Boolean>()); 239 Comparator<Integer> cmp = new Comparator<>() { 240 public int compare(Integer x, Integer y) { 241 return x - y; 242 }}; 243 list.add(new TreeMap<Integer, Boolean>(Collections.reverseOrder(cmp))); 244 return list; 245 } 246 newConcurrentSets()247 private static List<Set<Integer>> newConcurrentSets() { 248 List<Set<Integer>> list = new ArrayList<>(); 249 list.add(new ConcurrentSkipListSet<Integer>()); 250 list.add(new CopyOnWriteArraySet<Integer>()); 251 return list; 252 } 253 newSets()254 private static List<Set<Integer>> newSets() { 255 List<Set<Integer>> list = newConcurrentSets(); 256 list.add(new HashSet<Integer>()); 257 list.add(new TreeSet<Integer>()); 258 list.add(new TreeSet<Integer>(Collections.reverseOrder())); 259 return list; 260 } 261 newConcurrentLists()262 private static List<List<Integer>> newConcurrentLists() { 263 List<List<Integer>> list = new ArrayList<>(); 264 list.add(new CopyOnWriteArrayList<Integer>()); 265 return list; 266 } 267 newLists()268 private static List<List<Integer>> newLists() { 269 List<List<Integer>> list = newConcurrentLists(); 270 list.add(new Vector<Integer>()); 271 list.add(new ArrayList<Integer>()); 272 return list; 273 } 274 newConcurrentQueues()275 private static List<Queue<Integer>> newConcurrentQueues() { 276 List<Queue<Integer>> list = new ArrayList<>(newConcurrentDeques()); 277 list.add(new ArrayBlockingQueue<Integer>(10)); 278 list.add(new LinkedBlockingQueue<Integer>(10)); 279 list.add(new LinkedTransferQueue<Integer>()); 280 list.add(new ConcurrentLinkedQueue<Integer>()); 281 return list; 282 } 283 newQueues()284 private static List<Queue<Integer>> newQueues() { 285 List<Queue<Integer>> list = new ArrayList<>(newDeques()); 286 list.add(new LinkedBlockingQueue<Integer>(10)); 287 return list; 288 } 289 newConcurrentDeques()290 private static List<Deque<Integer>> newConcurrentDeques() { 291 List<Deque<Integer>> list = new ArrayList<>(); 292 list.add(new LinkedBlockingDeque<Integer>(10)); 293 list.add(new ConcurrentLinkedDeque<Integer>()); 294 return list; 295 } 296 newDeques()297 private static List<Deque<Integer>> newDeques() { 298 List<Deque<Integer>> list = newConcurrentDeques(); 299 list.add(new ArrayDeque<Integer>()); 300 list.add(new LinkedList<Integer>()); 301 return list; 302 } 303 describe(Class<?> k, Object x, Object y)304 private static void describe(Class<?> k, Object x, Object y) { 305 if (debug) 306 System.out.printf("%s: %s, %s%n", k.getSimpleName(), 307 x.getClass().getSimpleName(), 308 y.getClass().getSimpleName()); 309 } 310 realMain(String[] args)311 private static void realMain(String[] args) { 312 for (Map<Integer, Boolean> x : maps()) 313 for (Map<Integer, Boolean> y : newConcurrentMaps()) { 314 describe(Map.class, x, y); 315 x.put(one, true); 316 frob(x, y); 317 frob(unmodifiableMap(x), y); 318 frob(synchronizedMap(x), y); 319 frob(x, synchronizedMap(y)); 320 frob(checkedMap(x, Integer.class, Boolean.class), y); 321 frob(x, checkedMap(y, Integer.class, Boolean.class)); 322 x.clear(); 323 frob(newSetFromMap(x), newSetFromMap(y)); 324 frob(x.keySet(), newSetFromMap(y)); 325 } 326 327 for (Set<Integer> x : newSets()) 328 for (Set<Integer> y : newConcurrentSets()) { 329 describe(Set.class, x, y); 330 frob(x, y); 331 frob(unmodifiableSet(x), y); 332 frob(synchronizedSet(x), y); 333 frob(x, synchronizedSet(y)); 334 frob(checkedSet(x, Integer.class), y); 335 frob(x, checkedSet(y, Integer.class)); 336 } 337 338 for (List<Integer> x : newLists()) 339 for (List<Integer> y : newConcurrentLists()) { 340 describe(List.class, x, y); 341 frob(x, y); 342 frob(unmodifiableList(x), y); 343 frob(synchronizedList(x), y); 344 frob(x, synchronizedList(y)); 345 frob(checkedList(x, Integer.class), y); 346 frob(x, checkedList(y, Integer.class)); 347 } 348 349 for (Queue<Integer> x : newQueues()) 350 for (Queue<Integer> y : newConcurrentQueues()) { 351 describe(Queue.class, x, y); 352 frob(x, y); 353 } 354 355 for (Deque<Integer> x : newDeques()) 356 for (Deque<Integer> y : newConcurrentDeques()) { 357 describe(Deque.class, x, y); 358 frob(asLifoQueue(x), y); 359 frob(x, asLifoQueue(y)); 360 } 361 } 362 363 //--------------------- Infrastructure --------------------------- 364 static volatile int passed = 0, failed = 0; pass()365 static void pass() {passed++;} fail()366 static void fail() {failed++; Thread.dumpStack();} fail(String msg)367 static void fail(String msg) {System.out.println(msg); fail();} unexpected(Throwable t)368 static void unexpected(Throwable t) {failed++; t.printStackTrace();} check(boolean cond)369 static void check(boolean cond) {if (cond) pass(); else fail();} toString(Object x)370 static String toString(Object x) { 371 return ((x instanceof Collection) || (x instanceof Map)) ? 372 x.getClass().getName() : x.toString();} equal(Object x, Object y)373 static void equal(Object x, Object y) { 374 if (x == null ? y == null : x.equals(y)) pass(); 375 else fail(toString(x) + " not equal to " + toString(y));} notEqual(Object x, Object y)376 static void notEqual(Object x, Object y) { 377 if (x == null ? y == null : x.equals(y)) 378 fail(toString(x) + " equal to " + toString(y)); 379 else pass();} 380 @LargeTest main(String[] args)381 public static void main(String[] args) throws Throwable { 382 try {realMain(args);} catch (Throwable t) {unexpected(t);} 383 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 384 if (failed > 0) throw new AssertionError("Some tests failed");} 385 private abstract static class CheckedThread extends Thread { realRun()386 abstract void realRun() throws Throwable; run()387 public void run() { 388 try { realRun(); } catch (Throwable t) { unexpected(t); }}} 389 } 390