Race conditions in concurrent collections

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Race conditions in concurrent collections

Martin Buchholz


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
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Race conditions in concurrent collections

Doug Lea
Martin Buchholz wrote:
>
>
> One possible strategy for implementing Set.equals would be
> new HashSet(this).equals(new HashSet(other));
> which at one stroke eliminates concurrency issues

Although this places the burden on the HashSet(Collection c)
constructor, which is not specified to do anything special
in the face of concurrent modifications of "c" (and in fact
is likely to fail).

More generally, the java.util Collection APIs are not especially
consistent about the behavior of "binary bulk" collection
methods (Collection-constructors, putAll, equals, etc.)
The java.util.concurrent ones (ConcurrentMap, BlockingQueue)
are pretty clear about most of these. But I'm not sure whether or how
more can be said about the others. For example, while most people would
rather obtain a possibly (and defensibly) inaccurate result than
deadlock for a call to equals  with two concurrently accessible
collections, the specs cannot mandate this because many other people
have implemented these interfaces over the years, so at best, any
guarantees would hold only for those classes in the JDK.

The JSR166 expert group should/will explore alternatives
on this though.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Race conditions in concurrent collections

Martin Buchholz


Doug Lea wrote:

> Martin Buchholz wrote:
>
>>
>>One possible strategy for implementing Set.equals would be
>>new HashSet(this).equals(new HashSet(other));
>>which at one stroke eliminates concurrency issues
>
>
> Although this places the burden on the HashSet(Collection c)
> constructor, which is not specified to do anything special
> in the face of concurrent modifications of "c" (and in fact
> is likely to fail).

Hmmmm.  In the current implementation, this eventually reduces
to a standard iterator loop over "c"

        Iterator<? extends E> e = c.iterator();
        while (e.hasNext()) {
            add(e.next());

If "c" is not a concurrent collection, then concurrent modification
is simply not supposed to work, and users should expect
ConcurrentModificationException (or worse).

If "c" *is* a concurrent collection, then our implementations in
j.u.c. try to not have next() fail when hasNext() has just
succeeded, but I don't think we promise that.  Supposing we *did*
promise that, then
new HashSet(c)
would always give a "reasonable" result when c is a concurrent
collection, and cannot be expected to give a reasonable result
when c is not.

We could of course add a
try {...} catch (NoSuchElementException) {...}
to handle concurrently modified collections where next() might fail.

Unfortunately, if we implemented equals(Object) using this strategy,
we could still have equals return true when the two collections
never contained the same elements.  Indeed, there is no way to
get all the elements in a concurrent collection in such a way that
the returned elements represent a snapshot of a particular point in
time, and so there is in general no way to implement an intuitive
equals() method.  At least, if both collections are quiescent, then
c.equals(other) should give the expected result.  That is hard
to specify in the javadoc, because it depends on cooperation between two
unknown collection class implementations.

Martin
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Race conditions in concurrent collections

Mike Skells-3
Hi,
Surely the logic is wrong here

If you catch a ConcurrentModificationException  then equals() return false,
because at some time during the evaluation the collection was not equal

Similarly a NoSuchElementException should be caught and the collections
should not be equal unless they are == (in which case we should not the
iterating)

Both ConcurrentModificationException and NoSuchElementException are not
reasonable expected from a .equals() call. This may be an bug in the
java.util packages, but it does not need to be reploduced in j.u.c.

Just my 2c

Mike

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf
> Of Martin Buchholz
> Sent: 24 September 2005 22:03
> To: Doug Lea
> Cc: [hidden email]
> Subject: Re: [concurrency-interest] Race conditions in
> concurrent collections
>
>
>
> Doug Lea wrote:
> > Martin Buchholz wrote:
> >
> >>
> >>One possible strategy for implementing Set.equals would be new
> >>HashSet(this).equals(new HashSet(other)); which at one stroke
> >>eliminates concurrency issues
> >
> >
> > Although this places the burden on the HashSet(Collection c)
> > constructor, which is not specified to do anything special
> in the face
> > of concurrent modifications of "c" (and in fact is likely to fail).
>
> Hmmmm.  In the current implementation, this eventually
> reduces to a standard iterator loop over "c"
>
> Iterator<? extends E> e = c.iterator();
> while (e.hasNext()) {
>    add(e.next());
>
> If "c" is not a concurrent collection, then concurrent
> modification is simply not supposed to work, and users should
> expect ConcurrentModificationException (or worse).
>
> If "c" *is* a concurrent collection, then our implementations
> in j.u.c. try to not have next() fail when hasNext() has just
> succeeded, but I don't think we promise that.  Supposing we
> *did* promise that, then new HashSet(c) would always give a
> "reasonable" result when c is a concurrent collection, and
> cannot be expected to give a reasonable result when c is not.
>
> We could of course add a
> try {...} catch (NoSuchElementException) {...} to handle
> concurrently modified collections where next() might fail.
>
> Unfortunately, if we implemented equals(Object) using this
> strategy, we could still have equals return true when the two
> collections never contained the same elements.  Indeed, there
> is no way to get all the elements in a concurrent collection
> in such a way that the returned elements represent a snapshot
> of a particular point in time, and so there is in general no
> way to implement an intuitive
> equals() method.  At least, if both collections are quiescent, then
> c.equals(other) should give the expected result.  That is
> hard to specify in the javadoc, because it depends on
> cooperation between two unknown collection class implementations.
>
> Martin
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Race conditions in concurrent collections

Doug Lea
Mike Skells wrote:

>
> If you catch a ConcurrentModificationException  then equals() return false,
> because at some time during the evaluation the collection was not equal
>
> Similarly a NoSuchElementException should be caught and the collections
> should not be equal unless they are == (in which case we should not the
> iterating)
>
> Both ConcurrentModificationException and NoSuchElementException are not
> reasonable expected from a .equals() call.

Issues like this are why concurrent collection iterators do not
throw these exceptions unexpectedly, so these problems should never
arise when dealing solely with concurrent collections. But I agree
that it would be nice if something better can be said and done
with calls using other kinds of collections, like:
   aConcurrentHashMap.equals(aHashtable)
   aConcurrentHashMap.equals(aHashMap)

I still don't know what that something is though. While it would
make sense to simply return false here if a Hashtable iterator
throws ConcurrentModificationException, it would not be
a good idea for a HashMap iterator, because in that case
the ConcurrentModificationException almost surely reflects
some kind of corruption -- it acts as a error that would be
swallowed if it simply triggers equals to return false.

(Note that concurrent/blocking queues evade these issues
entirely by relying on identity-based equality. Ideally,
most or all other concurrent collections would as well, but
doing so would have made it more difficult for people to switch from
java.util classes to instead use them.)

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Race conditions in concurrent collections

Mike Skells-3
 

> -----Original Message-----
> From: Doug Lea [mailto:[hidden email]]
> Sent: 25 September 2005 01:15
> To: Mike Skells
> Cc: [hidden email]
> Subject: Re: [concurrency-interest] Race conditions in
> concurrent collections
>
> Mike Skells wrote:
> >
> > If you catch a ConcurrentModificationException  then
> equals() return
> > false, because at some time during the evaluation the
> collection was
> > not equal
> >
> > Similarly a NoSuchElementException should be caught and the
> > collections should not be equal unless they are == (in
> which case we
> > should not the
> > iterating)
> >
> > Both ConcurrentModificationException and NoSuchElementException are
> > not reasonable expected from a .equals() call.
>
> Issues like this are why concurrent collection iterators do
> not throw these exceptions unexpectedly, so these problems
> should never arise when dealing solely with concurrent
> collections. But I agree that it would be nice if something
> better can be said and done with calls using other kinds of
> collections, like:
>    aConcurrentHashMap.equals(aHashtable)
>    aConcurrentHashMap.equals(aHashMap)
>
> I still don't know what that something is though. While it
> would make sense to simply return false here if a Hashtable
> iterator throws ConcurrentModificationException, it would not
> be a good idea for a HashMap iterator, because in that case
> the ConcurrentModificationException almost surely reflects
> some kind of corruption -- it acts as a error that would be
> swallowed if it simply triggers equals to return false.
>
> (Note that concurrent/blocking queues evade these issues
> entirely by relying on identity-based equality. Ideally, most
> or all other concurrent collections would as well, but doing
> so would have made it more difficult for people to switch
> from java.util classes to instead use them.)
>
> -Doug

I was thinking not so much of the case when someone is dealing with a
collection per se, as when the ser is programming to say the object
interface

Object x = ...
Object y = ...

If (x.equals(y)) {
  ...
}


I dont think that it is reasonable to write

try {
   if (x.equals(y)) {
      ...
   }
} catch RuntimeException re) {
}

-----

Worse still not I come o think if it is the cases where you are indirectly
iterating
For example isnt there a similar problem with hashCode(),or even toString(),
or some other API that is being used that indirectly iterates, or calls
equals ...


Mike


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Race conditions in concurrent collections

Doug Lea
In reply to this post by Martin Buchholz
Mike Skells wrote:
>
> For example isnt there a similar problem with hashCode(),or even toString(),
> or some other API that is being used that indirectly iterates, or calls
> equals ...
>

Right. The slogan is to use java.util.concurrent implementations for
all concurrently accessible collections. They are designed to handle
these operations in reasonable ways even under concurrent modification.
(Too bad that in Tiger we were still missing a few common ones
like ConcurrentSkipList{Map,Set} to substitute for Tree{Map, Set}.)
On the other hand, even though "reasonably" implemented,
some of these operations make little sense and should usually
be avoided when the collections are concurrently accessible.

For example, computing a hashCode for a collection that is undergoing
concurrent modification is almost never a good idea from an application
level point of view, so the fact that it doesn't throw an exception is
not all that helpful. It would almost be better for it to throw an
exception anyway to warn you that you are probably doing something
nonsensical, although that would be overly paternalistic :-)

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest