J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 2007 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 21 | * have any questions. |
| 22 | */ |
| 23 | |
| 24 | /* |
| 25 | * @test |
| 26 | * @bug 6499848 |
| 27 | * @summary Check that iterators work properly in the presence of |
| 28 | * concurrent finalization and removal of elements. |
| 29 | */ |
| 30 | |
| 31 | import java.util.*; |
| 32 | import java.util.concurrent.CountDownLatch; |
| 33 | |
| 34 | public class GCDuringIteration { |
| 35 | static void finalizeTillYouDrop() { |
| 36 | System.gc(); // Enqueue all finalizables |
| 37 | |
| 38 | System.runFinalization(); // Drain finalizer queue |
| 39 | |
| 40 | // There may be a straggler finalizable object still being |
| 41 | // finalized by the dedicated finalizer thread. Enqueue one |
| 42 | // more finalizable object, and wait for it to be finalized. |
| 43 | final CountDownLatch latch = new CountDownLatch(1); |
| 44 | new Object() { protected void finalize() { latch.countDown(); }}; |
| 45 | System.gc(); |
| 46 | try { latch.await(); } |
| 47 | catch (InterruptedException ie) { throw new Error(ie); } |
| 48 | } |
| 49 | |
| 50 | // A class with the traditional pessimal hashCode implementation, |
| 51 | // to ensure that all instances end up in the same bucket. |
| 52 | static class Foo { public int hashCode() { return 42; }} |
| 53 | |
| 54 | <K,V> void put(Map<K,V> map, K k, V v) { |
| 55 | check(! map.containsKey(k)); |
| 56 | equal(map.get(k), null); |
| 57 | equal(map.put(k, v), null); |
| 58 | equal(map.get(k), v); |
| 59 | check(map.containsKey(k)); |
| 60 | equal(map.put(k, v), v); |
| 61 | equal(map.get(k), v); |
| 62 | check(map.containsKey(k)); |
| 63 | check(! map.isEmpty()); |
| 64 | equal(map.keySet().iterator().next(), k); |
| 65 | equal(map.values().iterator().next(), v); |
| 66 | } |
| 67 | |
| 68 | void checkIterator(final Iterator<Map.Entry<Foo, Integer>> it, int first) { |
| 69 | final Random rnd = new Random(); |
| 70 | for (int i = first; i >= 0; --i) { |
| 71 | if (rnd.nextBoolean()) check(it.hasNext()); |
| 72 | equal(it.next().getValue(), i); |
| 73 | } |
| 74 | if (rnd.nextBoolean()) |
| 75 | THROWS(NoSuchElementException.class, |
| 76 | new F(){void f(){it.next();}}); |
| 77 | if (rnd.nextBoolean()) |
| 78 | check(! it.hasNext()); |
| 79 | } |
| 80 | |
| 81 | <K,V> V firstValue(Map<K,V> map) { |
| 82 | return map.values().iterator().next(); |
| 83 | } |
| 84 | |
| 85 | void test(String[] args) throws Throwable { |
| 86 | final int n = 10; |
| 87 | // Create array of strong refs |
| 88 | final Foo[] foos = new Foo[2*n]; |
| 89 | final Map<Foo,Integer> map = new WeakHashMap<Foo,Integer>(foos.length); |
| 90 | check(map.isEmpty()); |
| 91 | equal(map.size(), 0); |
| 92 | |
| 93 | for (int i = 0; i < foos.length; i++) { |
| 94 | Foo foo = new Foo(); |
| 95 | foos[i] = foo; |
| 96 | put(map, foo, i); |
| 97 | } |
| 98 | equal(map.size(), foos.length); |
| 99 | |
| 100 | { |
| 101 | int first = firstValue(map); |
| 102 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 103 | foos[first] = null; finalizeTillYouDrop(); |
| 104 | equal(map.size(), first); |
| 105 | checkIterator(it, first-1); |
| 106 | equal(map.size(), first); |
| 107 | equal(firstValue(map), first-1); |
| 108 | } |
| 109 | |
| 110 | { |
| 111 | int first = firstValue(map); |
| 112 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 113 | it.next(); // protects first entry |
| 114 | System.out.println(map.values()); |
| 115 | foos[first] = null; finalizeTillYouDrop(); |
| 116 | equal(map.size(), first+1); |
| 117 | System.out.println(map.values()); |
| 118 | checkIterator(it, first-1); |
| 119 | finalizeTillYouDrop(); // first entry no longer protected |
| 120 | equal(map.size(), first); |
| 121 | equal(firstValue(map), first-1); |
| 122 | } |
| 123 | |
| 124 | { |
| 125 | int first = firstValue(map); |
| 126 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 127 | it.next(); // protects first entry |
| 128 | System.out.println(map.values()); |
| 129 | foos[first] = foos[first-1] = null; finalizeTillYouDrop(); |
| 130 | equal(map.size(), first); |
| 131 | equal(firstValue(map), first); |
| 132 | System.out.println(map.values()); |
| 133 | checkIterator(it, first-2); |
| 134 | finalizeTillYouDrop(); // first entry no longer protected |
| 135 | equal(map.size(), first-1); |
| 136 | equal(firstValue(map), first-2); |
| 137 | } |
| 138 | |
| 139 | { |
| 140 | int first = firstValue(map); |
| 141 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 142 | it.next(); // protects first entry |
| 143 | it.hasNext(); // protects second entry |
| 144 | System.out.println(map.values()); |
| 145 | foos[first] = foos[first-1] = null; finalizeTillYouDrop(); |
| 146 | equal(firstValue(map), first); |
| 147 | equal(map.size(), first+1); |
| 148 | System.out.println(map.values()); |
| 149 | checkIterator(it, first-1); |
| 150 | finalizeTillYouDrop(); // first entry no longer protected |
| 151 | equal(map.size(), first-1); |
| 152 | equal(firstValue(map), first-2); |
| 153 | } |
| 154 | |
| 155 | { |
| 156 | int first = firstValue(map); |
| 157 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 158 | it.next(); // protects first entry |
| 159 | System.out.println(map.values()); |
| 160 | foos[first] = foos[first-1] = null; finalizeTillYouDrop(); |
| 161 | it.remove(); |
| 162 | equal(firstValue(map), first-2); |
| 163 | equal(map.size(), first-1); |
| 164 | System.out.println(map.values()); |
| 165 | checkIterator(it, first-2); |
| 166 | finalizeTillYouDrop(); |
| 167 | equal(map.size(), first-1); |
| 168 | equal(firstValue(map), first-2); |
| 169 | } |
| 170 | |
| 171 | { |
| 172 | int first = firstValue(map); |
| 173 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 174 | it.next(); // protects first entry |
| 175 | it.remove(); |
| 176 | it.hasNext(); // protects second entry |
| 177 | System.out.println(map.values()); |
| 178 | foos[first] = foos[first-1] = null; finalizeTillYouDrop(); |
| 179 | equal(firstValue(map), first-1); |
| 180 | equal(map.size(), first); |
| 181 | System.out.println(map.values()); |
| 182 | checkIterator(it, first-1); |
| 183 | finalizeTillYouDrop(); |
| 184 | equal(map.size(), first-1); |
| 185 | equal(firstValue(map), first-2); |
| 186 | } |
| 187 | |
| 188 | { |
| 189 | int first = firstValue(map); |
| 190 | final Iterator<Map.Entry<Foo,Integer>> it = map.entrySet().iterator(); |
| 191 | it.hasNext(); // protects first entry |
| 192 | Arrays.fill(foos, null); |
| 193 | finalizeTillYouDrop(); |
| 194 | equal(map.size(), 1); |
| 195 | System.out.println(map.values()); |
| 196 | equal(it.next().getValue(), first); |
| 197 | check(! it.hasNext()); |
| 198 | finalizeTillYouDrop(); |
| 199 | equal(map.size(), 0); |
| 200 | check(map.isEmpty()); |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | //--------------------- Infrastructure --------------------------- |
| 205 | volatile int passed = 0, failed = 0; |
| 206 | void pass() {passed++;} |
| 207 | void fail() {failed++; Thread.dumpStack();} |
| 208 | void fail(String msg) {System.err.println(msg); fail();} |
| 209 | void unexpected(Throwable t) {failed++; t.printStackTrace();} |
| 210 | void check(boolean cond) {if (cond) pass(); else fail();} |
| 211 | void equal(Object x, Object y) { |
| 212 | if (x == null ? y == null : x.equals(y)) pass(); |
| 213 | else fail(x + " not equal to " + y);} |
| 214 | public static void main(String[] args) throws Throwable { |
| 215 | new GCDuringIteration().instanceMain(args);} |
| 216 | void instanceMain(String[] args) throws Throwable { |
| 217 | try {test(args);} catch (Throwable t) {unexpected(t);} |
| 218 | System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); |
| 219 | if (failed > 0) throw new AssertionError("Some tests failed");} |
| 220 | abstract class F {abstract void f() throws Throwable;} |
| 221 | void THROWS(Class<? extends Throwable> k, F... fs) { |
| 222 | for (F f : fs) |
| 223 | try {f.f(); fail("Expected " + k.getName() + " not thrown");} |
| 224 | catch (Throwable t) { |
| 225 | if (k.isAssignableFrom(t.getClass())) pass(); |
| 226 | else unexpected(t);}} |
| 227 | } |