1 /*
2 * Copyright 2009 Goldman Sachs International. 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 /*
26 * @test
27 * @bug 6865031
28 * @summary Application gives bad result (throws bad exception) with compressed oops
29 * @run main/othervm -XX:+UseCompressedOops -XX:HeapBaseMinAddress=32g -XX:-LoopUnswitching -XX:CompileCommand=inline,AbstractMemoryEfficientList.equals Test hello goodbye
30 */
31
32 import java.lang.ref.ReferenceQueue;
33 import java.lang.ref.WeakReference;
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.List;
37
38 interface MyList {
39 public int size();
40 public Object set(final int index, final Object element);
41 public Object get(final int index);
42 }
43
44 abstract class AbstractMemoryEfficientList implements MyList {
45 abstract public int size();
46 abstract public Object get(final int index);
47 abstract public Object set(final int index, final Object element);
48
49 public boolean equals(Object o) {
50 if (o == this) {
51 return true;
52 }
53
54 if (!(o instanceof MyList)) {
55 return false;
56 }
57
58 final MyList that = (MyList) o;
59 if (this.size() != that.size()) {
60 return false;
61 }
62
63 for (int i = 0; i < this.size(); i++) {
64 try {
65 if (!((this.get(i)).equals(that.get(i)))) {
66 return false;
67 }
68 } catch (IndexOutOfBoundsException e) {
69 System.out.println("THROWING RT EXC");
70 System.out.println("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i);
71 e.printStackTrace();
72 System.exit(97);
73 throw new RuntimeException("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i, e);
74 }
75 }
76 return true;
77 }
78
79 public int hashCode() {
80 int hashCode = 1;
81 for (int i = 0; i < this.size(); i++) {
82 Object obj = this.get(i);
83 hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
84 }
85 return hashCode;
86 }
87 }
88
89 final class SingletonList extends AbstractMemoryEfficientList {
90 private Object element1;
91
92 SingletonList(final Object obj1) {
93 super();
94 this.element1 = obj1;
95 }
96
97 public int size() {
98 return 1;
99 }
100
101 public Object get(final int index) {
102 if (index == 0) {
103 return this.element1;
104 } else {
105 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
106 }
107 }
108
109 public Object set(final int index, final Object element) {
110 if (index == 0) {
111 final Object previousElement = this.element1;
112 this.element1 = element;
113 return previousElement;
114 } else {
115 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
116 }
117 }
118 }
119
120 final class DoubletonList extends AbstractMemoryEfficientList {
121 private Object element1;
122 private Object element2;
123
124 DoubletonList(final Object obj1, final Object obj2) {
125 this.element1 = obj1;
126 this.element2 = obj2;
127 }
128
129 public int size() {
130 return 2;
131 }
132
133 public Object get(final int index) {
134 switch (index) {
135 case 0 : return this.element1;
136 case 1 : return this.element2;
137 default: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
138 }
139 }
140
141 public Object set(final int index, final Object element) {
142 switch (index) {
143 case 0 :
144 {
145 final Object previousElement = this.element1;
146 this.element1 = element;
147 return previousElement;
148 }
149 case 1 :
150 {
151 final Object previousElement = this.element2;
152 this.element2 = element;
153 return previousElement;
154 }
155 default : throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
156 }
157 }
158 }
159
160 class WeakPool<V> {
161 protected static final int DEFAULT_INITIAL_CAPACITY = 16;
162 private static final int MAXIMUM_CAPACITY = 1 << 30;
163 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
164
165 protected Entry<V>[] table;
166
167 private int size;
168 protected int threshold;
169 private final float loadFactor;
170 private final ReferenceQueue<V> queue = new ReferenceQueue<V>();
171
172 public WeakPool()
173 {
174 this.loadFactor = DEFAULT_LOAD_FACTOR;
175 threshold = DEFAULT_INITIAL_CAPACITY;
176 table = new Entry[DEFAULT_INITIAL_CAPACITY];
177 }
178
179 /**
180 * Check for equality of non-null reference x and possibly-null y. By
181 * default uses Object.equals.
182 */
183 private boolean eq(Object x, Object y)
184 {
185 return x == y || x.equals(y);
186 }
187
188 /**
189 * Return index for hash code h.
190 */
191 private int indexFor(int h, int length)
192 {
193 return h & length - 1;
194 }
195
196 /**
197 * Expunge stale entries from the table.
198 */
199 private void expungeStaleEntries()
200 {
201 Object r;
202 while ((r = queue.poll()) != null)
203 {
204 Entry e = (Entry) r;
205 int h = e.hash;
206 int i = indexFor(h, table.length);
207
208 // System.out.println("EXPUNGING " + h);
209 Entry<V> prev = table[i];
210 Entry<V> p = prev;
211 while (p != null)
212 {
213 Entry<V> next = p.next;
214 if (p == e)
215 {
216 if (prev == e)
217 {
218 table[i] = next;
219 }
220 else
221 {
222 prev.next = next;
223 }
224 e.next = null; // Help GC
225 size--;
226 break;
227 }
228 prev = p;
229 p = next;
230 }
231 }
232 }
233
234 /**
235 * Return the table after first expunging stale entries
236 */
237 private Entry<V>[] getTable()
238 {
239 expungeStaleEntries();
240 return table;
241 }
242
243 /**
244 * Returns the number of key-value mappings in this map.
245 * This result is a snapshot, and may not reflect unprocessed
246 * entries that will be removed before next attempted access
247 * because they are no longer referenced.
248 */
249 public int size()
250 {
251 if (size == 0)
252 {
253 return 0;
254 }
255 expungeStaleEntries();
256 return size;
257 }
258
259 /**
260 * Returns <tt>true</tt> if this map contains no key-value mappings.
261 * This result is a snapshot, and may not reflect unprocessed
262 * entries that will be removed before next attempted access
263 * because they are no longer referenced.
264 */
265 public boolean isEmpty()
266 {
267 return size() == 0;
268 }
269
270 /**
271 * Returns the value stored in the pool that equals the requested key
272 * or <tt>null</tt> if the map contains no mapping for
273 * this key (or the key is null)
274 *
275 * @param key the key whose equals value is to be returned.
276 * @return the object that is equal the specified key, or
277 * <tt>null</tt> if key is null or no object in the pool equals the key.
278 */
279 public V get(V key)
280 {
281 if (key == null)
282 {
283 return null;
284 }
285 int h = key.hashCode();
286 Entry<V>[] tab = getTable();
287 int index = indexFor(h, tab.length);
288 Entry<V> e = tab[index];
289 while (e != null)
290 {
291 V candidate = e.get();
292 if (e.hash == h && eq(key, candidate))
293 {
294 return candidate;
295 }
296 e = e.next;
297 }
298 return null;
299 }
300
301 /**
302 * Returns the entry associated with the specified key in the HashMap.
303 * Returns null if the HashMap contains no mapping for this key.
304 */
305 Entry getEntry(Object key)
306 {
307 int h = key.hashCode();
308 Entry[] tab = getTable();
309 int index = indexFor(h, tab.length);
310 Entry e = tab[index];
311 while (e != null && !(e.hash == h && eq(key, e.get())))
312 {
313 e = e.next;
314 }
315 return e;
316 }
317
318 /**
319 * Places the object into the pool. If the object is null, nothing happens.
320 * If an equal object already exists, it is not replaced.
321 *
322 * @param key the object to put into the pool. key may be null.
323 * @return the object in the pool that is equal to the key, or the newly placed key if no such object existed when put was called
324 */
325 public V put(V key)
326 {
327 if (key == null)
328 {
329 return null;
330 }
331 int h = key.hashCode();
332 Entry<V>[] tab = getTable();
333 int i = indexFor(h, tab.length);
334
335 for (Entry<V> e = tab[i]; e != null; e = e.next)
336 {
337 V candidate = e.get();
338 if (h == e.hash && eq(key, candidate))
339 {
340 return candidate;
341 }
342 }
343
344 tab[i] = new Entry<V>(key, queue, h, tab[i]);
345
346 if (++size >= threshold)
347 {
348 resize(tab.length * 2);
349 }
350
351 // System.out.println("Added " + key + " to pool");
352 return key;
353 }
354
355 /**
356 * Rehashes the contents of this map into a new array with a
357 * larger capacity. This method is called automatically when the
358 * number of keys in this map reaches its threshold.
359 * <p/>
360 * If current capacity is MAXIMUM_CAPACITY, this method does not
361 * resize the map, but but sets threshold to Integer.MAX_VALUE.
362 * This has the effect of preventing future calls.
363 *
364 * @param newCapacity the new capacity, MUST be a power of two;
365 * must be greater than current capacity unless current
366 * capacity is MAXIMUM_CAPACITY (in which case value
367 * is irrelevant).
368 */
369 void resize(int newCapacity)
370 {
371 Entry<V>[] oldTable = getTable();
372 int oldCapacity = oldTable.length;
373 if (oldCapacity == MAXIMUM_CAPACITY)
374 {
375 threshold = Integer.MAX_VALUE;
376 return;
377 }
378
379 Entry<V>[] newTable = new Entry[newCapacity];
380 transfer(oldTable, newTable);
381 table = newTable;
382
383 /*
384 * If ignoring null elements and processing ref queue caused massive
385 * shrinkage, then restore old table. This should be rare, but avoids
386 * unbounded expansion of garbage-filled tables.
387 */
388 if (size >= threshold / 2)
389 {
390 threshold = (int) (newCapacity * loadFactor);
391 }
392 else
393 {
394 expungeStaleEntries();
395 transfer(newTable, oldTable);
396 table = oldTable;
397 }
398 }
399
400 /**
401 * Transfer all entries from src to dest tables
402 */
403 private void transfer(Entry[] src, Entry[] dest)
404 {
405 for (int j = 0; j < src.length; ++j)
406 {
407 Entry e = src[j];
408 src[j] = null;
409 while (e != null)
410 {
411 Entry next = e.next;
412 Object key = e.get();
413 if (key == null)
414 {
415 e.next = null; // Help GC
416 size--;
417 }
418 else
419 {
420 int i = indexFor(e.hash, dest.length);
421 e.next = dest[i];
422 dest[i] = e;
423 }
424 e = next;
425 }
426 }
427 }
428
429 /**
430 * Removes the object in the pool that equals the key.
431 *
432 * @param key
433 * @return previous value associated with specified key, or <tt>null</tt>
434 * if there was no mapping for key or the key is null.
435 */
436 public V removeFromPool(V key)
437 {
438 if (key == null)
439 {
440 return null;
441 }
442 int h = key.hashCode();
443 Entry<V>[] tab = getTable();
444 int i = indexFor(h, tab.length);
445 Entry<V> prev = tab[i];
446 Entry<V> e = prev;
447
448 while (e != null)
449 {
450 Entry<V> next = e.next;
451 V candidate = e.get();
452 if (h == e.hash && eq(key, candidate))
453 {
454 size--;
455 if (prev == e)
456 {
457 tab[i] = next;
458 }
459 else
460 {
461 prev.next = next;
462 }
463 return candidate;
464 }
465 prev = e;
466 e = next;
467 }
468
469 return null;
470 }
471
472 /**
473 * Removes all mappings from this map.
474 */
475 public void clear()
476 {
477 // clear out ref queue. We don't need to expunge entries
478 // since table is getting cleared.
479 while (queue.poll() != null)
480 {
481 // nop
482 }
483
484 table = new Entry[DEFAULT_INITIAL_CAPACITY];
485 threshold = DEFAULT_INITIAL_CAPACITY;
486 size = 0;
487
488 // Allocation of array may have caused GC, which may have caused
489 // additional entries to go stale. Removing these entries from the
490 // reference queue will make them eligible for reclamation.
491 while (queue.poll() != null)
492 {
493 // nop
494 }
495 }
496
497 /**
498 * The entries in this hash table extend WeakReference, using its main ref
499 * field as the key.
500 */
501 protected static class Entry<V>
502 extends WeakReference<V>
503 {
504 private final int hash;
505 private Entry<V> next;
506
507 /**
508 * Create new entry.
509 */
510 Entry(final V key, final ReferenceQueue<V> queue, final int hash, final Entry<V> next)
511 {
512 super(key, queue);
513 this.hash = hash;
514 this.next = next;
515 }
516
517 public V getKey()
518 {
519 return super.get();
520 }
521
522 public boolean equals(Object o)
523 {
524 if (!(o instanceof WeakPool.Entry))
525 {
526 return false;
527 }
528 WeakPool.Entry<V> that = (WeakPool.Entry<V>) o;
529 V k1 = this.getKey();
530 V k2 = that.getKey();
531 return (k1==k2 || k1.equals(k2));
532 }
533
534 public int hashCode()
535 {
536 return this.hash;
537 }
538
539 public String toString()
540 {
541 return String.valueOf(this.getKey());
542 }
543 }
544 }
545
546 final class MultiSynonymKey {
547 private List<MyList> keys;
548
549 public MultiSynonymKey() {
550 keys = new ArrayList<MyList>();
551 }
552
553 public MultiSynonymKey(MyList... arg) {
554 keys = Arrays.asList(arg);
555 }
556
557 public List<MyList> getKeys() {
558 return keys;
559 }
560
561 public int hashCode() {
562 return this.getKeys().hashCode();
563 }
564
565 public boolean equals(Object obj) {
566 if (this == obj) {
567 return true;
568 }
569
570 if (!(obj instanceof MultiSynonymKey)) {
571 return false;
572 }
573
574 MultiSynonymKey that = (MultiSynonymKey) obj;
575 return this.getKeys().equals(that.getKeys());
576 }
577
578 public String toString() {
579 return this.getClass().getName() + this.getKeys().toString();
580 }
581 }
582
583 public class Test extends Thread {
584 static public Test test;
585 static private byte[] arg1;
586 static private byte[] arg2;
587 static public WeakPool<MultiSynonymKey> wp;
588 public volatile MultiSynonymKey ml1;
589 public volatile MultiSynonymKey ml2;
590 private volatile MultiSynonymKey ml3;
591
592 public void run() {
593 int count=0;
594 while (true) {
595 try {
596 Thread.sleep(10);
597 } catch (Exception e) {}
598 synchronized (wp) {
599 ml2 = new MultiSynonymKey(new DoubletonList(new String(arg1), new String(arg2)));
600 wp.put(ml2);
601 ml3 = new MultiSynonymKey(new DoubletonList(new String(arg1), new String(arg2)));
602 }
603 try {
604 Thread.sleep(10);
605 } catch (Exception e) {}
606 synchronized (wp) {
607 ml1 = new MultiSynonymKey(new SingletonList(new String(arg1)));
608 wp.put(ml1);
609 ml3 = new MultiSynonymKey(new SingletonList(new String(arg1)));
610 }
611 if (count++==100)
612 System.exit(95);
613 }
614 }
615
616 public static void main(String[] args) throws Exception {
617 wp = new WeakPool<MultiSynonymKey>();
618 test = new Test();
619
620 test.arg1 = args[0].getBytes();
621 test.arg2 = args[1].getBytes();
622
623 test.ml1 = new MultiSynonymKey(new SingletonList(new String(test.arg1)));
624 test.ml2 = new MultiSynonymKey(new DoubletonList(new String(test.arg1), new String(test.arg2)));
625 test.ml3 = new MultiSynonymKey(new DoubletonList(new String(test.arg1), new String(test.arg2)));
626
627 wp.put(test.ml1);
628 wp.put(test.ml2);
629
630 test.setDaemon(true);
631 test.start();
632
633 int counter = 0;
634 while (true) {
635 synchronized (wp) {
636 MultiSynonymKey foo = test.ml3;
637
638 if (wp.put(foo) == foo) {
639 // System.out.println("foo " + counter);
640 // System.out.println(foo);
641 }
642 }
643 counter++;
644 }
645 }
646
647 private boolean eq(Object x, Object y) {
648 return x == y || x.equals(y);
649 }
650 }