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