RFR: 8263551: Provide shared lock-free FIFO queue implementation

[Man Cao]

On Mon, 15 Mar 2021 23:52:39 GMT, Kim Barrett <kbarrett at openjdk.org> wrote:

>> src/hotspot/share/utilities/lockFreeQueue.inline.hpp line 60:
>> 
>>> 58:     LockFreeQueueCriticalSection<rcu_pop> cs(current_thread);
>>> 59: 
>>> 60:     T* result = Atomic::load_acquire(&_head);
>> 
>> A related question about memory ordering. Are these two load_acquire() really necessary? They are not paired with any release_store().
>> I think they can be normal Atomic::load(), as append() and pop() already have Atomic::xchg() and Atomic::cmpxchg() to enforce ordering.
>
> 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.

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

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