Hi,<br><br>I just suffered the following deadlock, stress-testing my app in a JavaEE application server:<br><br>Thread 1:<br>
    at java.util.Collections$SynchronizedSet.hashCode(Collections.java:1658)<br>    - waiting to lock <0xfffffd7fdd8ce548> (a java.util.Collections$SynchronizedSet)<br>Thread 2:<br>    at java.util.Collections$SynchronizedCollection.size(Collections.java:1557)<br>
    - waiting to lock <0xfffffd7fde2bb1a0> (a java.util.Collections$SynchronizedSet)<br>    at java.util.AbstractSet.equals(AbstractSet.java:75)<br>    at java.util.Collections$SynchronizedSet.equals(Collections.java:1655)<br>
    - locked <0xfffffd7fdd8ce548> (a java.util.Collections$SynchronizedSet)<br>Thread 3:<br>    at java.util.Collections$SynchronizedCollection.size(Collections.java:1557)<br>    - waiting to lock <0xfffffd7fdd8ce548> (a java.util.Collections$SynchronizedSet)<br>
    at java.util.AbstractSet.equals(AbstractSet.java:75)<br>    at java.util.Collections$SynchronizedSet.equals(Collections.java:1655)<br>    - locked <0xfffffd7fde2bb1a0> (a java.util.Collections$SynchronizedSet)<br>
<br>This appserver has some internal Sets containing credentials information, protected by Collections.synchronizedSet(). It seems the credentials sets are often compared to each other, by just calling set1.equals(set2). This causes a deadlock because equals() will invoke methods on set2, that are also synchronized, but the appserver does this concurrently in many threads for each application transaction. (My JVM dump reveals no less than 20 app threads involved in this dealock: 18 of these waiting on 0xfffffd7fdd8ce548 to call hashCode(), 1 waiting on the same lock to call size(), and 1 waiting on 0xfffffd7fde2bb1a0 also to call size().)<br>
<br>Now this is obviously a bug in the appserver, it should be using a lock on the entire group of such Sets, at least for operations that involve more than one Set like equals(). The javadocs already make clear that the synchronized wrappers are not safe in some cases: "It is imperative that the user manually synchronize on the returned sorted set when iterating over it or any of its subSet, headSet, or tailSet views." But this documentation doesn't cover other methods that may take another synchronized collection as a parameters and may iterate it ("implementation detail" although easy to guess), like containsAll(), retainAll(), etc. The size() method is another special case, equals() could deadlock even when comparing two empty Sets, because it needs minimally to invoke size() in the other collection and this is sufficient to deadlock.<br>
<br>I wonder if we should have even more warnings in the javadocs, covering all 'dangerous' methods. This is not a stupid n00b bug, it's code from one of the leading commercial application servers and I suppose its developers are very skilled, still this bug is there (I'm going to report it today). Generally, the synchronized wrappers are a pretty bad options, remarkably since J2SE 5.0. I'd even go as far as suggesting that we just deprecate all the Collections.synchronizedXxx() methods; besides deadlocks, it's way too easy to have races by sequentially invoking multiple methods in the same collections. The synchronizedXxx() APIs send the wrong message that locking individual methods of the collection objects is adequate, which in my experience is a bad (or at least fragile) assumption in 99% of the cases - collections are just too fine-grained. There are other pitfalls, like hashCode/equals() not delegating to the backing collection only for synchronizedCollection().<br>
<br>In a separate issue, the collections returned by synchronizedXxx() are synchronized using the original collection's monitor, so that this is safe:<br><br>Set sync1 = Collections.synchronizedSet(set1);<br>Set sync2 = Collections.synchronizedSet(set2);<br>

<br>synchronized (set1) {<br>  synchronized (set2) {<br>    if (sync1.equals(sync2) {...}<br>  }<br>}<br><br>In the equals() call above, no deadlock is possible, even with other threads that invoke methods in sync1 or sync2, as long as any threads that use both will perform the same explicit locking in the same order set1->set2.<br>
<br>Encapsulating a mutex is a common practice, but in this case I wonder if it's a good idea, at least as implemented (there is no public method to provide the mutex, allowing the user to trade some scalability for code that's simple and guaranteed deadlock-free). The user may decide to write synchronized(sync1)... to prevent deadlocks like the one I reported, and this is dangerous precisely because it would work most of the time - only really convoluted code would still deadlock. The javadocs don't give any clue of how the returned collections are synchronized, which is also bad because I cannot rely that the code above will always work - I just know it works for the particular Sun JDK release which sources I inspected. Some code out there should certainly use this implementation knowledge to safely synchronize groups of synchronizedXxx()'s collections, so this implementation cannot be changed for good or bad. Once again, I suggest additional documentation, to make the synchronization strategy explicit and contractual.<br>
<br>P.S.: I also noticed some optimization opportunities along the collections hierarchy. For example, AbstractSet.equals(other) could be redefined in sorted sets, when other is also sorted, to not require lookups of each value - just iterate both in the same direction comparing each pair of values, so the cost is O(N) on size (the generic implementation is O(N log(N)) for SortedSet.equals(SortedSet)). Even more optimization is often possible for exact classes: for TreeSet.equals(TreeSet), we can visit both internal trees recursively, without the allocation and indirection costs of a Iterator, without initially finding the first entry, and without the complication of successor(). It's a matter of finding the sweet spot between extra performance and extra code size and maintenance - I suggest that at least, those cases with demonstrably Big-O advantage are considered. The current implementation still carries many size/speed tradeoff decisions made back in J2SE 1.2, and I'm all against bloat but collections are something really core, and improvements (especially of Big-O scale) can mean a lot. Notice that the special case of mixed operations with several collections of the same general kind, or even exact class - for equals(), containsAll() etc. - is a very common case, one that's very worth of optimizing for.<br>
<br>A+<br>Osvaldo<br>