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