RacingCollections.java revision 12745:f068a4ffddd2
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 31import static java.util.Collections.*; 32import java.util.*; 33import java.util.concurrent.*; 34 35public class RacingCollections { 36 /** 37 * How long to run each "race" (in milliseconds). 38 * Turn this up to some higher value like 1000 for stress testing: 39 * java -Dmillis=1000 RacingCollections 40 */ 41 static final long defaultWorkTimeMillis = Long.getLong("millis", 10L); 42 43 /** 44 * Whether to print debug information. 45 */ 46 static final boolean debug = Boolean.getBoolean("debug"); 47 48 static final Integer one = 1; 49 static final Integer two = 2; 50 51 /** 52 * A thread that mutates an object forever, alternating between 53 * being empty and containing singleton "two" 54 */ 55 static class Frobber extends CheckedThread { 56 volatile boolean done = false; 57 boolean keepGoing(int i) { return (i % 128 != 0) || ! done; } 58 59 final Object elLoco; 60 Frobber(Object elLoco) { 61 this.elLoco = elLoco; 62 this.start(); 63 } 64 65 @SuppressWarnings("unchecked") void clear(Object o) { 66 if (o instanceof Collection) 67 ((Collection<?>)o).clear(); 68 else 69 ((Map<?,?>)o).clear(); 70 } 71 72 @SuppressWarnings("unchecked") void realRun() { 73 // Mutate elLoco wildly forever, checking occasionally for "done" 74 clear(elLoco); 75 if (elLoco instanceof List) { 76 List<Integer> l = (List<Integer>) elLoco; 77 for (int i = 0; keepGoing(i); i++) { 78 switch (i%2) { 79 case 0: l.add(two); break; 80 case 1: l.add(0, two); break; 81 } 82 switch (i%2) { 83 case 0: l.remove(two); break; 84 case 1: l.remove(0); break; 85 }}} 86 else if (elLoco instanceof Deque) { 87 Deque<Integer> q = (Deque<Integer>) elLoco; 88 for (int i = 0; keepGoing(i); i++) { 89 switch (i%6) { 90 case 0: q.add(two); break; 91 case 1: q.addFirst(two); break; 92 case 2: q.addLast(two); break; 93 case 3: q.offer(two); break; 94 case 4: q.offerFirst(two); break; 95 case 5: q.offerLast(two); break; 96 } 97 switch (i%6) { 98 case 0: q.remove(two); break; 99 case 1: q.removeFirst(); break; 100 case 2: q.removeLast(); break; 101 case 3: q.poll(); break; 102 case 4: q.pollFirst(); break; 103 case 5: q.pollLast(); break; 104 }}} 105 else if (elLoco instanceof Queue) { 106 Queue<Integer> q = (Queue<Integer>) elLoco; 107 for (int i = 0; keepGoing(i); i++) { 108 switch (i%2) { 109 case 0: q.add(two); break; 110 case 1: q.offer(two); break; 111 } 112 switch (i%2) { 113 case 0: q.remove(two); break; 114 case 1: q.poll(); break; 115 }}} 116 else if (elLoco instanceof Map) { 117 Map<Integer, Boolean> m = (Map<Integer, Boolean>) elLoco; 118 for (int i = 0; keepGoing(i); i++) { 119 m.put(two, true); 120 m.remove(two); 121 }} 122 else if (elLoco instanceof Collection) { 123 Collection<Integer> c = (Collection<Integer>) elLoco; 124 for (int i = 0; keepGoing(i); i++) { 125 c.add(two); 126 c.remove(two); 127 }} 128 else { throw new Error("Huh? " + elLoco); } 129 } 130 131 void enoughAlready() { 132 done = true; 133 try { join(); } catch (Throwable t) { unexpected(t); } 134 } 135 } 136 137 private static void checkEqualSanity(Object theRock, Object elLoco) { 138 //equal(theRock, theRock); 139 equal(elLoco, elLoco); 140 141 // It would be nice someday to have theRock and elLoco never "equal", 142 // although the meaning of "equal" for mutating collections 143 // is a bit fuzzy. Uncomment when/if we fix: 144 // 6374942: Improve thread safety of collection .equals() methods 145 //notEqual(theRock, elLoco); 146 //notEqual(elLoco, theRock); 147 148 notEqual(theRock.toString(), elLoco.toString()); 149 } 150 151 static class Looper { 152 final long quittingTime; 153 int i = 0; 154 Looper() { this(defaultWorkTimeMillis); } 155 Looper(long workTimeMillis) { 156 quittingTime = System.nanoTime() + workTimeMillis * 1024 * 1024; 157 } 158 boolean keepGoing() { 159 return (i++ % 128 != 0) || (System.nanoTime() < quittingTime); 160 } 161 } 162 163 private static void frob(Object theRock, Object elLoco) { 164 Frobber frobber = new Frobber(elLoco); 165 try { 166 if (theRock instanceof Collection) { 167 @SuppressWarnings("unchecked") 168 Collection<Integer> c = (Collection<Integer>) theRock; 169 if (! c.contains(one)) 170 c.add(one); 171 } else { 172 @SuppressWarnings("unchecked") 173 Map<Integer, Boolean> m = (Map<Integer, Boolean>) theRock; 174 if (! m.containsKey(one)) 175 m.put(one, true); 176 } 177 for (Looper looper = new Looper(); looper.keepGoing(); ) 178 checkEqualSanity(theRock, elLoco); 179 } 180 catch (Throwable t) { unexpected(t); } 181 finally { frobber.enoughAlready(); } 182 } 183 184 private static List<Map<Integer, Boolean>> newConcurrentMaps() { 185 List<Map<Integer, Boolean>> list = 186 new ArrayList<Map<Integer, Boolean>>(); 187 list.add(new ConcurrentHashMap<Integer, Boolean>()); 188 list.add(new ConcurrentSkipListMap<Integer, Boolean>()); 189 return list; 190 } 191 192 private static List<Map<Integer, Boolean>> maps() { 193 List<Map<Integer, Boolean>> list = newConcurrentMaps(); 194 list.add(new Hashtable<Integer, Boolean>()); 195 list.add(new HashMap<Integer, Boolean>()); 196 list.add(new TreeMap<Integer, Boolean>()); 197 Comparator<Integer> cmp = new Comparator<Integer>() { 198 public int compare(Integer x, Integer y) { 199 return x - y; 200 }}; 201 list.add(new TreeMap<Integer, Boolean>(Collections.reverseOrder(cmp))); 202 return list; 203 } 204 205 private static List<Set<Integer>> newConcurrentSets() { 206 List<Set<Integer>> list = new ArrayList<Set<Integer>>(); 207 list.add(new ConcurrentSkipListSet<Integer>()); 208 list.add(new CopyOnWriteArraySet<Integer>()); 209 return list; 210 } 211 212 private static List<Set<Integer>> newSets() { 213 List<Set<Integer>> list = newConcurrentSets(); 214 list.add(new HashSet<Integer>()); 215 list.add(new TreeSet<Integer>()); 216 list.add(new TreeSet<Integer>(Collections.reverseOrder())); 217 return list; 218 } 219 220 private static List<List<Integer>> newConcurrentLists() { 221 List<List<Integer>> list = new ArrayList<List<Integer>>(); 222 list.add(new CopyOnWriteArrayList<Integer>()); 223 return list; 224 } 225 226 private static List<List<Integer>> newLists() { 227 List<List<Integer>> list = newConcurrentLists(); 228 list.add(new Vector<Integer>()); 229 list.add(new ArrayList<Integer>()); 230 return list; 231 } 232 233 private static List<Queue<Integer>> newConcurrentQueues() { 234 List<Queue<Integer>> list = 235 new ArrayList<Queue<Integer>>(newConcurrentDeques()); 236 list.add(new LinkedBlockingQueue<Integer>(10)); 237 list.add(new LinkedTransferQueue<Integer>()); 238 list.add(new ConcurrentLinkedQueue<Integer>()); 239 return list; 240 } 241 242 private static List<Queue<Integer>> newQueues() { 243 List<Queue<Integer>> list = 244 new ArrayList<Queue<Integer>>(newDeques()); 245 list.add(new LinkedBlockingQueue<Integer>(10)); 246 return list; 247 } 248 249 private static List<Deque<Integer>> newConcurrentDeques() { 250 List<Deque<Integer>> list = new ArrayList<Deque<Integer>>(); 251 list.add(new LinkedBlockingDeque<Integer>(10)); 252 list.add(new ConcurrentLinkedDeque<Integer>()); 253 return list; 254 } 255 256 private static List<Deque<Integer>> newDeques() { 257 List<Deque<Integer>> list = newConcurrentDeques(); 258 list.add(new ArrayDeque<Integer>()); 259 list.add(new LinkedList<Integer>()); 260 return list; 261 } 262 263 private static void describe(Class<?> k, Object x, Object y) { 264 if (debug) 265 System.out.printf("%s: %s, %s%n", k.getSimpleName(), 266 x.getClass().getSimpleName(), 267 y.getClass().getSimpleName()); 268 } 269 270 private static void realMain(String[] args) { 271 for (Map<Integer, Boolean> x : maps()) 272 for (Map<Integer, Boolean> y : newConcurrentMaps()) { 273 describe(Map.class, x, y); 274 x.put(one, true); 275 frob(x, y); 276 frob(unmodifiableMap(x), y); 277 frob(synchronizedMap(x), y); 278 frob(x, synchronizedMap(y)); 279 frob(checkedMap(x, Integer.class, Boolean.class), y); 280 frob(x, checkedMap(y, Integer.class, Boolean.class)); 281 x.clear(); 282 frob(newSetFromMap(x), newSetFromMap(y)); 283 frob(x.keySet(), newSetFromMap(y)); 284 } 285 286 for (Set<Integer> x : newSets()) 287 for (Set<Integer> y : newConcurrentSets()) { 288 describe(Set.class, x, y); 289 frob(x, y); 290 frob(unmodifiableSet(x), y); 291 frob(synchronizedSet(x), y); 292 frob(x, synchronizedSet(y)); 293 frob(checkedSet(x, Integer.class), y); 294 frob(x, checkedSet(y, Integer.class)); 295 } 296 297 for (List<Integer> x : newLists()) 298 for (List<Integer> y : newConcurrentLists()) { 299 describe(List.class, x, y); 300 frob(x, y); 301 frob(unmodifiableList(x), y); 302 frob(synchronizedList(x), y); 303 frob(x, synchronizedList(y)); 304 frob(checkedList(x, Integer.class), y); 305 frob(x, checkedList(y, Integer.class)); 306 } 307 308 for (Queue<Integer> x : newQueues()) 309 for (Queue<Integer> y : newConcurrentQueues()) { 310 describe(Queue.class, x, y); 311 frob(x, y); 312 } 313 314 for (Deque<Integer> x : newDeques()) 315 for (Deque<Integer> y : newConcurrentDeques()) { 316 describe(Deque.class, x, y); 317 frob(asLifoQueue(x), y); 318 frob(x, asLifoQueue(y)); 319 } 320 } 321 322 //--------------------- Infrastructure --------------------------- 323 static volatile int passed = 0, failed = 0; 324 static void pass() {passed++;} 325 static void fail() {failed++; Thread.dumpStack();} 326 static void fail(String msg) {System.out.println(msg); fail();} 327 static void unexpected(Throwable t) {failed++; t.printStackTrace();} 328 static void check(boolean cond) {if (cond) pass(); else fail();} 329 static String toString(Object x) { 330 return ((x instanceof Collection) || (x instanceof Map)) ? 331 x.getClass().getName() : x.toString();} 332 static void equal(Object x, Object y) { 333 if (x == null ? y == null : x.equals(y)) pass(); 334 else fail(toString(x) + " not equal to " + toString(y));} 335 static void notEqual(Object x, Object y) { 336 if (x == null ? y == null : x.equals(y)) 337 fail(toString(x) + " equal to " + toString(y)); 338 else pass();} 339 public static void main(String[] args) throws Throwable { 340 try {realMain(args);} catch (Throwable t) {unexpected(t);} 341 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 342 if (failed > 0) throw new AssertionError("Some tests failed");} 343 private abstract static class CheckedThread extends Thread { 344 abstract void realRun() throws Throwable; 345 public void run() { 346 try { realRun(); } catch (Throwable t) { unexpected(t); }}} 347} 348