1 /* 2 * Copyright (c) 2007, 2017, 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 6499848 27 * @library /test/lib 28 * @build jdk.test.lib.RandomFactory 29 * @run main GCDuringIteration 30 * @summary Check that iterators work properly in the presence of 31 * concurrent finalization and removal of elements. 32 * @key randomness 33 */ 34 35 import static java.util.concurrent.TimeUnit.SECONDS; 36 37 import java.lang.ref.WeakReference; 38 import java.util.Arrays; 39 import java.util.Iterator; 40 import java.util.Map; 41 import java.util.NoSuchElementException; 42 import java.util.Random; 43 import java.util.WeakHashMap; 44 import java.util.concurrent.CountDownLatch; 45 import java.util.function.BooleanSupplier; 46 import jdk.test.lib.RandomFactory; 47 48 public class GCDuringIteration { 49 50 /** No guarantees, but effective in practice. */ 51 static void forceFullGc() { 52 CountDownLatch finalizeDone = new CountDownLatch(1); 53 WeakReference<?> ref = new WeakReference<Object>(new Object() { 54 protected void finalize() { finalizeDone.countDown(); }}); 55 try { 56 for (int i = 0; i < 10; i++) { 57 System.gc(); 58 if (finalizeDone.await(1L, SECONDS) && ref.get() == null) { 59 System.runFinalization(); // try to pick up stragglers 60 return; 61 } 62 } 63 } catch (InterruptedException unexpected) { 64 throw new AssertionError("unexpected InterruptedException"); 65 } 66 throw new AssertionError("failed to do a \"full\" gc"); 67 } 68 69 static void gcAwait(BooleanSupplier s) { 70 for (int i = 0; i < 10; i++) { 71 if (s.getAsBoolean()) 72 return; 73 forceFullGc(); 74 } 75 throw new AssertionError("failed to satisfy condition"); 76 } 77 78 // A class with the traditional pessimal hashCode implementation, 79 // to ensure that all instances end up in the same bucket. 80 static class Foo { public int hashCode() { return 42; }} 81 82 <K,V> void put(Map<K,V> map, K k, V v) { 83 check(! map.containsKey(k)); 84 equal(map.get(k), null); 85 equal(map.put(k, v), null); 86 equal(map.get(k), v); 87 check(map.containsKey(k)); 88 equal(map.put(k, v), v); 89 equal(map.get(k), v); 90 check(map.containsKey(k)); 91 check(! map.isEmpty()); 92 equal(map.keySet().iterator().next(), k); 93 equal(map.values().iterator().next(), v); 94 } 95 96 static final Random rnd = RandomFactory.getRandom(); 97 98 void checkIterator(final Iterator<Map.Entry<Foo, Integer>> it, int first) { 99 for (int i = first; i >= 0; --i) { 100 if (rnd.nextBoolean()) check(it.hasNext()); 101 equal(it.next().getValue(), i); 102 } 103 if (rnd.nextBoolean()) { 104 try { 105 it.next(); 106 throw new AssertionError("should throw"); 107 } catch (NoSuchElementException success) {} 108 } 109 110 if (rnd.nextBoolean()) 111 check(! it.hasNext()); 112 } 113 114 <K,V> V firstValue(Map<K,V> map) { 115 return map.values().iterator().next(); 116 } 117 118 void test(String[] args) throws Throwable { 119 final int n = 10; 120 // Create array of strong refs 121 final Foo[] foos = new Foo[2*n]; 122 final Map<Foo,Integer> map = new WeakHashMap<>(foos.length); 123 check(map.isEmpty()); 124 equal(map.size(), 0); 125 126 for (int i = 0; i < foos.length; i++) { 127 Foo foo = new Foo(); 128 foos[i] = foo; 129 put(map, foo, i); 130 } 131 equal(map.size(), foos.length); 132 133 { 134 int first = firstValue(map); 135 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 136 foos[first] = null; 137 gcAwait(() -> map.size() == first); 138 checkIterator(it, first-1); 139 equal(map.size(), first); 140 equal(firstValue(map), first-1); 141 } 142 143 { 144 int first = firstValue(map); 145 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 146 it.next(); // protects first entry 147 System.out.println(map.values()); 148 int oldSize = map.size(); 149 foos[first] = null; 150 forceFullGc(); 151 equal(map.size(), oldSize); 152 System.out.println(map.values()); 153 checkIterator(it, first-1); 154 // first entry no longer protected 155 gcAwait(() -> map.size() == first); 156 equal(firstValue(map), first-1); 157 } 158 159 { 160 int first = firstValue(map); 161 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 162 it.next(); // protects first entry 163 System.out.println(map.values()); 164 foos[first] = foos[first-1] = null; 165 gcAwait(() -> map.size() == first); 166 equal(firstValue(map), first); 167 System.out.println(map.values()); 168 checkIterator(it, first-2); 169 // first entry no longer protected 170 gcAwait(() -> map.size() == first-1); 171 equal(firstValue(map), first-2); 172 } 173 174 { 175 int first = firstValue(map); 176 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 177 it.next(); // protects first entry 178 it.hasNext(); // protects second entry 179 System.out.println(map.values()); 180 int oldSize = map.size(); 181 foos[first] = foos[first-1] = null; 182 forceFullGc(); 183 equal(map.size(), oldSize); 184 equal(firstValue(map), first); 185 System.out.println(map.values()); 186 checkIterator(it, first-1); 187 // first entry no longer protected 188 gcAwait(() -> map.size() == first-1); 189 equal(firstValue(map), first-2); 190 } 191 192 { 193 int first = firstValue(map); 194 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 195 it.next(); // protects first entry 196 System.out.println(map.values()); 197 equal(map.size(), first+1); 198 foos[first] = foos[first-1] = null; 199 gcAwait(() -> map.size() == first); 200 it.remove(); 201 equal(firstValue(map), first-2); 202 equal(map.size(), first-1); 203 System.out.println(map.values()); 204 checkIterator(it, first-2); 205 // first entry no longer protected 206 gcAwait(() -> map.size() == first-1); 207 equal(firstValue(map), first-2); 208 } 209 210 { 211 int first = firstValue(map); 212 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 213 it.next(); // protects first entry 214 it.remove(); 215 it.hasNext(); // protects second entry 216 System.out.println(map.values()); 217 equal(map.size(), first); 218 foos[first] = foos[first-1] = null; 219 forceFullGc(); 220 equal(firstValue(map), first-1); 221 equal(map.size(), first); 222 System.out.println(map.values()); 223 checkIterator(it, first-1); 224 gcAwait(() -> map.size() == first-1); 225 equal(firstValue(map), first-2); 226 } 227 228 { 229 int first = firstValue(map); 230 final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); 231 it.hasNext(); // protects first entry 232 Arrays.fill(foos, null); 233 gcAwait(() -> map.size() == 1); 234 System.out.println(map.values()); 235 equal(it.next().getValue(), first); 236 check(! it.hasNext()); 237 gcAwait(() -> map.size() == 0); 238 check(map.isEmpty()); 239 } 240 } 241 242 //--------------------- Infrastructure --------------------------- 243 volatile int passed = 0, failed = 0; 244 void pass() {passed++;} 245 void fail() {failed++; Thread.dumpStack();} 246 void fail(String msg) {System.err.println(msg); fail();} 247 void unexpected(Throwable t) {failed++; t.printStackTrace();} 248 void check(boolean cond) {if (cond) pass(); else fail();} 249 void equal(Object x, Object y) { 250 if (x == null ? y == null : x.equals(y)) pass(); 251 else fail(x + " not equal to " + y);} 252 public static void main(String[] args) throws Throwable { 253 new GCDuringIteration().instanceMain(args);} 254 void instanceMain(String[] args) throws Throwable { 255 try {test(args);} catch (Throwable t) {unexpected(t);} 256 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 257 if (failed > 0) throw new AssertionError("Some tests failed");} 258 }