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 }