RFR: 8263551: Provide shared lock-free FIFO queue implementation [v2]

[Kim Barrett]

On Tue, 16 Mar 2021 05:47:58 GMT, Man Cao <manc at openjdk.org> wrote:

>> The ordering of xchg in append only affects the writing thread.  It does nothing for the reader side.  The second load_acquire pairs with the set_next (a release_store) in append.  However, it's always (one way or another) followed by a conservative cmpxchg, so does seem possible to weaken.  The first load_acquire is a "consume", but we don't have that and upgrade to acquire.
>
> Agreed that the second load_acquire can be weakened, and thanks for noting the first one is a "consume".
> However, I'm a bit confused about the explanation.
>> The second load_acquire pairs with the set_next (a release_store) in append.
> 
> The set_next() is Atomic::store() as in LockFreeStack, right? Then it is a relaxed store, but not a release_store. In this case the full fence provided by xchg is necessary to make set_next() a release_store.
> 
> IIUC, the following is sufficient to establish a release-acquire ordering:
> Writer thread:                         Reader thread:
> StoreStoreFence();
> relaxed_store(p);
>                                        relaxed_load(p);
>                                        LoadLoadFence();
> In this case:
> append() (Writer thread):              pop() (Reader thread):
> // Provides full fence
> Atomic::xchg(&_tail, ...);
> Atomic::store(&p._next, ...);
>                                        // Suppose we don't use load_acqurie
>                                        Atomic::load(&p._next);
>                                        // Provides full fence
>                                        Atomic::cmpxchg(&_head /* or &_tail */, ...);
> I think it is the two full fences that enables us to use relaxed store and relaxed load.

I think you are correct.  I was confused about set_next().

-------------

PR: https://git.openjdk.java.net/jdk/pull/2986