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