CopyOnWriteArrayList lost volatile write in OpenJDK 11

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

CopyOnWriteArrayList lost volatile write in OpenJDK 11

JSR166 Concurrency mailing list
Hi everyone,

In OpenJDK10 CopyOnWriteArrayList.set(index, element) always did a volatile write via the setArray method. In OpenJDK11 it was changed so that if the provided element is the same as the array[index], then no volatile write is issued (see the links and code excerpts below).

The javadoc of the CopyOnWriteArrayList class sais "actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread" without adding any conditions on whether the added object is already in the array or not. Therefore it seems to me that the semantics of the set method was changed in OpenJDK11, and with the current implementation there are allowed executions where the below CowExample never ends (such implementations are not allowed with the CopyOnWriteArrayList from OpenJDK10):

class CowExample {
  static CopyOnWriteArrayList<Boolean> cowList = new CopyOnWriteArrayList<>(new Boolean[] {Boolean.TRUE});//add Boolean.TRUE to cowList
  static int flag = 0;//a plain field

  public static void main(String... args) {
    ForkJoinPool.commonPool().submit(() -> {
      flag = 1;
      cowList.set(0, Boolean.TRUE);//is supposed to always do a volatile write; publish the write to the plain flag field
    });
    while(flag == 0) {//is allowed to loop forever
      cowList.get(0);//a volatile read
    }
  }
}


The implementations from OpenJDK10 and OpenJDK11

public E set(int index, E element) {
    synchronized (lock) {
        Object[] elements = getArray();
        E oldValue = elementAt(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    }
}

public E set(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);

        if (oldValue != element) {
            es = es.clone();
            es[index] = element;
            setArray(es);
        }
        return oldValue;
    }
}

Regards,
Valentin
LinkedIn   GitHub   YouTube

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

Re: CopyOnWriteArrayList lost volatile write in OpenJDK 11

JSR166 Concurrency mailing list
Thanks for finding this (presumably by code inspection?)

I can't remember how this changed, and you're unlikely to observe any change in behavior in practice, but we were arguably slightly overzealous, and we could fix it to:

--- src/main/java/util/concurrent/CopyOnWriteArrayList.java 11 Nov 2018 16:27:28 -0000 1.155
+++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 18 Mar 2019 18:38:52 -0000
@@ -395,8 +395,9 @@
             if (oldValue != element) {
                 es = es.clone();
                 es[index] = element;
-                setArray(es);
             }
+            // Ensure volatile write semantics even when oldvalue == element
+            setArray(es);
             return oldValue;
         }
     }


On Mon, Mar 18, 2019 at 10:35 AM Valentin Kovalenko via Concurrency-interest <[hidden email]> wrote:
Hi everyone,

In OpenJDK10 CopyOnWriteArrayList.set(index, element) always did a volatile write via the setArray method. In OpenJDK11 it was changed so that if the provided element is the same as the array[index], then no volatile write is issued (see the links and code excerpts below).

The javadoc of the CopyOnWriteArrayList class sais "actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread" without adding any conditions on whether the added object is already in the array or not. Therefore it seems to me that the semantics of the set method was changed in OpenJDK11, and with the current implementation there are allowed executions where the below CowExample never ends (such implementations are not allowed with the CopyOnWriteArrayList from OpenJDK10):

class CowExample {
  static CopyOnWriteArrayList<Boolean> cowList = new CopyOnWriteArrayList<>(new Boolean[] {Boolean.TRUE});//add Boolean.TRUE to cowList
  static int flag = 0;//a plain field

  public static void main(String... args) {
    ForkJoinPool.commonPool().submit(() -> {
      flag = 1;
      cowList.set(0, Boolean.TRUE);//is supposed to always do a volatile write; publish the write to the plain flag field
    });
    while(flag == 0) {//is allowed to loop forever
      cowList.get(0);//a volatile read
    }
  }
}


The implementations from OpenJDK10 and OpenJDK11

public E set(int index, E element) {
    synchronized (lock) {
        Object[] elements = getArray();
        E oldValue = elementAt(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    }
}

public E set(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);

        if (oldValue != element) {
            es = es.clone();
            es[index] = element;
            setArray(es);
        }
        return oldValue;
    }
}

Regards,
Valentin
LinkedIn   GitHub   YouTube
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

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

Re: CopyOnWriteArrayList lost volatile write in OpenJDK 11

JSR166 Concurrency mailing list
Yes, Martin, I found this while discussing the COWList implementation with someone (so not by observing an infinite loop). Thanks for the blazingly quick fix :)

Regards,
Valentin

On Mon, Mar 18, 2019, 12:43 Martin Buchholz <[hidden email]> wrote:
Thanks for finding this (presumably by code inspection?)

I can't remember how this changed, and you're unlikely to observe any change in behavior in practice, but we were arguably slightly overzealous, and we could fix it to:

--- src/main/java/util/concurrent/CopyOnWriteArrayList.java 11 Nov 2018 16:27:28 -0000 1.155
+++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 18 Mar 2019 18:38:52 -0000
@@ -395,8 +395,9 @@
             if (oldValue != element) {
                 es = es.clone();
                 es[index] = element;
-                setArray(es);
             }
+            // Ensure volatile write semantics even when oldvalue == element
+            setArray(es);
             return oldValue;
         }
     }

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

Re: CopyOnWriteArrayList lost volatile write in OpenJDK 11

JSR166 Concurrency mailing list
My understanding is that both implementations use synchronized which should ensure prior writes become visible once the block is left.

Valentin Kovalenko via Concurrency-interest <[hidden email]> ezt írta (időpont: 2019. márc. 18., H, 20:51):
Yes, Martin, I found this while discussing the COWList implementation with someone (so not by observing an infinite loop). Thanks for the blazingly quick fix :)

Regards,
Valentin

On Mon, Mar 18, 2019, 12:43 Martin Buchholz <[hidden email]> wrote:
Thanks for finding this (presumably by code inspection?)

I can't remember how this changed, and you're unlikely to observe any change in behavior in practice, but we were arguably slightly overzealous, and we could fix it to:

--- src/main/java/util/concurrent/CopyOnWriteArrayList.java 11 Nov 2018 16:27:28 -0000 1.155
+++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 18 Mar 2019 18:38:52 -0000
@@ -395,8 +395,9 @@
             if (oldValue != element) {
                 es = es.clone();
                 es[index] = element;
-                setArray(es);
             }
+            // Ensure volatile write semantics even when oldvalue == element
+            setArray(es);
             return oldValue;
         }
     }
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


--
Best regards,
David Karnok

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

Re: CopyOnWriteArrayList lost volatile write in OpenJDK 11

JSR166 Concurrency mailing list
No, lock release synchronizes-with only subsequent lock acquires, not arbitrary synchronisation actions.

Alex

On 19 Mar 2019, at 07:51, Dávid Karnok via Concurrency-interest <[hidden email]> wrote:

My understanding is that both implementations use synchronized which should ensure prior writes become visible once the block is left.

Valentin Kovalenko via Concurrency-interest <[hidden email]> ezt írta (időpont: 2019. márc. 18., H, 20:51):
Yes, Martin, I found this while discussing the COWList implementation with someone (so not by observing an infinite loop). Thanks for the blazingly quick fix :)

Regards,
Valentin

On Mon, Mar 18, 2019, 12:43 Martin Buchholz <[hidden email]> wrote:
Thanks for finding this (presumably by code inspection?)

I can't remember how this changed, and you're unlikely to observe any change in behavior in practice, but we were arguably slightly overzealous, and we could fix it to:

--- src/main/java/util/concurrent/CopyOnWriteArrayList.java 11 Nov 2018 16:27:28 -0000 1.155
+++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 18 Mar 2019 18:38:52 -0000
@@ -395,8 +395,9 @@
             if (oldValue != element) {
                 es = es.clone();
                 es[index] = element;
-                setArray(es);
             }
+            // Ensure volatile write semantics even when oldvalue == element
+            setArray(es);
             return oldValue;
         }
     }
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


--
Best regards,
David Karnok
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


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

Re: CopyOnWriteArrayList lost volatile write in OpenJDK 11

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Assuming to maintain the original behaviour probably placing a seq-cst fence/barrier instead of  setArray(es); in the else branch would make 
more evident the intention, without needing the comment

Il giorno mar 19 mar 2019 alle ore 08:52 Dávid Karnok via Concurrency-interest <[hidden email]> ha scritto:
My understanding is that both implementations use synchronized which should ensure prior writes become visible once the block is left.

Valentin Kovalenko via Concurrency-interest <[hidden email]> ezt írta (időpont: 2019. márc. 18., H, 20:51):
Yes, Martin, I found this while discussing the COWList implementation with someone (so not by observing an infinite loop). Thanks for the blazingly quick fix :)

Regards,
Valentin

On Mon, Mar 18, 2019, 12:43 Martin Buchholz <[hidden email]> wrote:
Thanks for finding this (presumably by code inspection?)

I can't remember how this changed, and you're unlikely to observe any change in behavior in practice, but we were arguably slightly overzealous, and we could fix it to:

--- src/main/java/util/concurrent/CopyOnWriteArrayList.java 11 Nov 2018 16:27:28 -0000 1.155
+++ src/main/java/util/concurrent/CopyOnWriteArrayList.java 18 Mar 2019 18:38:52 -0000
@@ -395,8 +395,9 @@
             if (oldValue != element) {
                 es = es.clone();
                 es[index] = element;
-                setArray(es);
             }
+            // Ensure volatile write semantics even when oldvalue == element
+            setArray(es);
             return oldValue;
         }
     }
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


--
Best regards,
David Karnok
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

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