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