RFR(M): Memory ordering in taskqueue.hpp

[Vitaly Davidovich]

Hi Goetz,

If I understand correctly the problem is that bottom is loaded before age
via compiler or arch reordering.  But why is a full fence needed? Is it not
sufficient to have just a load fence to load age and relaxed load (just
compiler barrier) for bottom?

Thanks

Sent from my phone
On Mar 8, 2013 9:06 AM, "Lindenmaier, Goetz" <goetz.lindenmaier at sap.com>
wrote:

> Hi,
>
> we have been, and still are, doing research on this issue.
> We want to keep you up to date on this, and propose on the
> further proceeding.
>
> You asked explicit memory ordering operations and a rationale
> why we added them.
>
> Axel found a paper describing the task queue algorithm and the
> needed ordering on arm and power:
> Correct and Efficient Work-Stealing for Weak Memory Models;
> Lê, Pop, Cohen, Nardelli; PPoPP'13;
> http://www.di.ens.fr/~zappa/readings/ppopp13.pdf
>
> According to this paper we need to add one fence and one load_acquire
> to your implementation of the task queue.  You find this fence in this
> small
> webrev:  http://cr.openjdk.java.net/~goetz/webrevs/8006971-2/
>
> With this fence, the algorithm works on Linux for our openjdk ppc
> port, and also for our SAP JVM .
>
> Actually, the fence fixes a problem we discovered with the concurrency
> torture test suite.  The problem occurs with four or more GC threads.
> If three threads are stealing from the queue of the fourth, two of
> them can pop the same element. Without a fence between the access
> to age and bottom in pop_global(), bottom can be older than age.
>
>
> Unfortunately, the OpenJDK implementation with the added fence
> does not work on AIX.  Axel already detected one place where the xlC
> compiler optimization removed load instruction that is required for
> the correctness of the algorithm.  If we use our access routines with
> load_acquire
> (see original webrev below) everything works, unclear why.
>
> Now, we think C++ might allow that this load is removed and xlC does
> the correct, but unexpected thing.  On the other hand it might also be
> a compiler bug.
> We are currently discussing this with the IBM xlC developers.
>
> Best regards,
>   Axel and Goetz.
>
>
> PS: The webrev we proposed originally:
> http://cr.openjdk.java.net/~goetz/webrevs/webrev-taskqueue/
>
>
>
>
>
>
>
>
>