JDK-6355645 : CopyOnWriteArrayList bulk operations have race conditions
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Affected Version: 6
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2005-11-28
  • Updated: 2010-04-02
  • Resolved: 2005-12-03
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6
6 b63Fixed
Related Reports
Relates :  
JDK-6347106 - (coll) Make ArrayList(Collection) more threadsafe
Description
A number of methods of CopyOnWriteArrayList take other collections as arguments.
They assume that those collections are not being concurrently mutated.
In particular, they trust that the size() of the other collection is invariant.
This means, in particular, that "binary" operations on pairs of CopyOnWriteArrayLists
are unsafe.

This is one part of the fix for 
6347106: (coll) methods taking concurrently modified collection arguments fail sporadically
If all you have is a Collection, then both size() and iteration are unsafe!
Comments
EVALUATION Fix being supplied by Doug Lea.
28-11-2005
SUGGESTED FIX --- /u/martin/ws/mustang/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java 2005-11-07 01:23:01.115938000 -0800 +++ /u/martin/ws/jsr166/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java 2005-11-27 21:42:56.522099000 -0800 @@ -88,10 +88,10 @@ * @throws NullPointerException if the specified collection is null */ public CopyOnWriteArrayList(Collection<? extends E> c) { - Object[] elements = new Object[c.size()]; - int size = 0; - for (E e : c) - elements[size++] = e; + Object[] elements = c.toArray(); + // c.toArray might (incorrectly) not return Object[] (see 6260652) + if (elements.getClass() != Object[].class) + elements = Arrays.copyOf(elements, elements.length, Object[].class); setArray(elements); } @@ -683,25 +683,25 @@ * @see #addIfAbsent(Object) */ public int addAllAbsent(Collection<? extends E> c) { - int numNew = c.size(); - if (numNew == 0) + Object[] cs = c.toArray(); + if (cs.length == 0) return 0; + Object[] uniq = new Object[cs.length]; final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; - - Object[] temp = new Object[numNew]; int added = 0; - for (E e : c) { + for (int i = 0; i < cs.length; ++i) { // scan for duplicates + Object e = cs[i]; if (indexOf(e, elements, 0, len) < 0 && - indexOf(e, temp, 0, added) < 0) - temp[added++] = e; + indexOf(e, uniq, 0, added) < 0) + uniq[added++] = e; } - if (added != 0) { + if (added > 0) { Object[] newElements = Arrays.copyOf(elements, len + added); - System.arraycopy(temp, 0, newElements, len, added); + System.arraycopy(uniq, 0, newElements, len, added); setArray(newElements); } return added; @@ -735,17 +735,16 @@ * @see #add(Object) */ public boolean addAll(Collection<? extends E> c) { - int numNew = c.size(); - if (numNew == 0) + Object[] cs = c.toArray(); + if (cs.length == 0) return false; final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; - Object[] newElements = Arrays.copyOf(elements, len + numNew); - for (E e : c) - newElements[len++] = e; + Object[] newElements = Arrays.copyOf(elements, len + cs.length); + System.arraycopy(cs, 0, newElements, len, cs.length); setArray(newElements); return true; } finally { @@ -770,7 +769,7 @@ * @see #add(int,Object) */ public boolean addAll(int index, Collection<? extends E> c) { - int numNew = c.size(); + Object[] cs = c.toArray(); final ReentrantLock lock = this.lock; lock.lock(); try { @@ -779,21 +778,20 @@ if (index > len || index < 0) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+len); - if (numNew == 0) + if (cs.length == 0) return false; int numMoved = len - index; Object[] newElements; if (numMoved == 0) - newElements = Arrays.copyOf(elements, len + numNew); + newElements = Arrays.copyOf(elements, len + cs.length); else { - newElements = new Object[len + numNew]; + newElements = new Object[len + cs.length]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, - newElements, index + numNew, + newElements, index + cs.length, numMoved); } - for (E e : c) - newElements[index++] = e; + System.arraycopy(cs, 0, newElements, index, cs.length); setArray(newElements); return true; } finally { --- /u/martin/ws/mustang/test/java/util/concurrent/CopyOnWriteArraySet/RacingCows.java 2005-11-07 01:23:01.404415000 -0800 +++ /u/martin/ws/jsr166/test/java/util/concurrent/CopyOnWriteArraySet/RacingCows.java 2005-11-27 21:58:25.592977000 -0800 @@ -1,7 +1,7 @@ /* - * @test 1.1 05/09/30 - * @bug 6330307 - * @summary cow.equals(cow) should not return spurious true + * @test %I% %E% + * @bug 6330307 6355645 + * @summary Check for race conditions in COWArray classes * @author Martin Buchholz */ @@ -12,6 +12,7 @@ private static void realMain(String[] args) throws Throwable { final int iterations = 100000; final Integer two = Integer.valueOf(2); + final Integer three = Integer.valueOf(3); //------------ CopyOnWriteArraySet ------------------------------- final Set<Integer> s1 = new CopyOnWriteArraySet<Integer>(); @@ -34,6 +35,7 @@ //------------ CopyOnWriteArrayList ------------------------------ final List<Integer> l1 = new CopyOnWriteArrayList<Integer>(); final List<Integer> l2 = new CopyOnWriteArrayList<Integer>(); + final List<Integer> l3 = new CopyOnWriteArrayList<Integer>(); l1.add(1); final Thread t2 = new CheckedThread() { public void realRun() { @@ -49,11 +51,41 @@ }}}}; t2.start(); + final Thread t3 = new CheckedThread() { public void realRun() { + l3.add(three); + for (int i = 0; i < iterations; i++) { + switch (i%2) { + case 0: l3.add(two); break; + case 1: l3.add(0, two); break; + } + switch (i%2) { + case 0: l3.remove(two); break; + case 1: l3.remove(0); break; + }}}}; + t3.start(); + for (int i = 0; i < iterations; i++) { check(! l1.equals(l2)); check(! l2.equals(l1)); + + // CopyOnWriteArrayList(mutatingCollection) + try { new CopyOnWriteArrayList<Integer>(l2); } + catch (Throwable t) { unexpected(t); } + + // addAllAbsent(mutatingCollection) + try { new CopyOnWriteArrayList<Integer>().addAllAbsent(l3); } + catch (Throwable t) { unexpected(t); } + + // addAll(mutatingCollection) + try { new CopyOnWriteArrayList<Integer>().addAll(l3); } + catch (Throwable t) { unexpected(t); } + + // addAll(int, mutatingCollection) + try { new CopyOnWriteArrayList<Integer>().addAll(0,l3); } + catch (Throwable t) { unexpected(t); } } t2.join(); + t3.join(); } //--------------------- Infrastructure ---------------------------
28-11-2005