[concurrency-interest] Race conditions in concurrent collections

Martin Buchholz Martin.Buchholz at Sun.COM
Sat Sep 24 14:30:26 EDT 2005



Jason Mehrens wrote:
> Date: Fri, 23 Sep 2005 13:38:35 -0500
> 
> Won't this bug still carry over to the CopyOnWriteArraySet?  The 
> CopyOnWriteArraySet uses the AbstractSet implementation of the of equals 
> which calls also calls size and containsAll which could view two different 
> snapshots.

When calling equals on collections that may be concurrently mutated,
the answer is just an approximation.

In the case of CopyOnWriteArraySet, it is disturbing
that s.equals(other) might return true even if s and other were *never*
equal, for example if another thread was doing
for (;;) {
  s.clear(); s.add(new Object()); s.add(e);
}
and "other" contained only the one element {e}.
I consider this a bug.

One possible strategy for implementing Set.equals would be
new HashSet(this).equals(new HashSet(other));
which at one stroke eliminates concurrency issues and produces
an expected order N+M algorithm instead of an N*M algorithm.
The only downside is that this will always create garbage
which we would like to avoid for read operations.

> Do collections have to make any guarantees on the behavior of input 
> Collections being passed into bulk operation methods like equals, 
> containsAll, removeAll, etc.?

While reviewing this code it became clear to me that things can go
wrong when the "other" collection is being concurrently modified.
We should probably add some documentation on what the user can
expect in this sort of situation.

There is some conflict here between performance and safety.

> For example, if a program calls equals on COWArrayList and the parameter is 
> another COWArrayList, Vector, synchonizedList() the same type of race still 
> exists between size() and ListIterator() on the input Collection (check the 
> source code of COWArrayList.equals 1.56). If the input Collection size is 
> reduced before or during the traversal of the ListIterator a 
> NoSuchElementException or ConcurrentModificationException is thrown from 
> equals.

You have good reviewer eyes!  I also became aware of this problem while
reviewing the code, but it is another instance of the more
pervasive problem you pointed out above. This is something for the
expert group to think about.

> As a user of the API I would consider the ConcurrentModifcationException my 
> problem (misuse) but the NoSuchElementException I would consider something 
> the COWArrayList would have to hide or prevent.

I agree users will expect that they can use COWArrayFoos in their code
and not have to worry.

Martin

> Regards,
> 
> Jason Mehrens


More information about the Concurrency-interest mailing list