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

[Kim Barrett]

On Sat, 13 Mar 2021 10:41:44 GMT, Man Cao <manc at openjdk.org> wrote:

> Hi all,
> 
> Could anyone review this change that is mainly code motion? It creates a generalized lock-free queue implementation based on G1DirtyCardQueueSet::Queue, which will be used by JDK-8236485 in the future.
> 
> The shared LockFreeQueue is similar to the existing LockFreeStack. The notable difference is that the LockFreeQueue has an additional template parameter for whether to use GlobalCounter::CriticalSection to avoid ABA problem.
> 
> -Man

Changes requested by kbarrett (Reviewer).

src/hotspot/share/utilities/lockFreeQueue.inline.hpp line 70:

> 68:         assert(Atomic::load(&_tail) != result, "invariant");
> 69:         assert(get_next(*result) != NULL, "invariant");
> 70:         *next_ptr(*result) = NULL;

This should be set_next / Atomic::store.

src/hotspot/share/utilities/lockFreeQueue.hpp line 113:

> 111:   // Return the entry following value in the list used by the
> 112:   // specialized LockFreeQueue class.
> 113:   static T* get_next(const T& value) {

I think this function should not be public; it's needed internal to the implementation of this class, but if a client needs access to the next list entry it should be getting it via a member on T, assuming T provides such.  And if it doesn't, well, you probably aren't supposed to be doing that.  I see that LockFreeStack has public next and set_next; by that argument they should be private too.  (I think the only reason they can't currently be private is because of unit tests, which could be fixed.)

src/hotspot/share/utilities/lockFreeQueue.hpp line 46:

> 44: //
> 45: // \tparam rcu_pop true if use GlobalCounter critical section in pop().
> 46: template<typename T, T* volatile* (*next_ptr)(T&), bool rcu_pop>

I think this is the wrong place for the rcu parameterization.  Among other things, it violates the SCARY principle for template design, making the entire class dependent on this parameter that is only relevant to the one operation.  I think it would be better if the parameterization was on the pop operation.

src/hotspot/share/utilities/lockFreeQueue.inline.hpp line 58:

> 56:     // CS could lead to excessive allocation of objects, because the CS
> 57:     // may block return of released objects to a free list for reuse.
> 58:     LockFreeQueueCriticalSection<rcu_pop> cs(current_thread);

The comment about excessive allocation is closely tied to the use in G1DirtyCardQueueSet. The purpose of a critical section here needs further description and generalization. I'm wondering whether it's actually important (maybe it is, just not sure and haven't though about it for a while), but I'm also thinking LockFreeQueue/Stack ought to be consistent about this.  That would suggest a common utility for optional critical sections.

src/hotspot/share/utilities/lockFreeQueue.inline.hpp line 52:

> 50: template<typename T, T* volatile* (*next_ptr)(T&), bool rcu_pop>
> 51: T* LockFreeQueue<T, next_ptr, rcu_pop>::pop() {
> 52:   Thread* current_thread = Thread::current();

The only use of current_thread is as the argument to the critical section object, where it might not be used, depending on the value of rcu_pop.  It would be better to make this also conditional.

src/hotspot/share/utilities/lockFreeQueue.inline.hpp line 30:

> 28: #include "runtime/atomic.hpp"
> 29: #include "runtime/thread.inline.hpp"
> 30: #include "utilities/globalCounter.inline.hpp"

Presumably this include is the reason for putting the `pop` support in an inline.hpp file.  But it seems clumsy to have most of the implementation in the ordinary header and this one function here, esp. since I suspect most clients will end up needing to include this file.  So I'm suggesting move all of the implementation here.

src/hotspot/share/utilities/lockFreeQueue.hpp line 50:

> 48:   NONCOPYABLE(LockFreeQueue);
> 49: 
> 50: protected:

Protected members (to be accessible from a derived class) are inconsistent with a public non-virtual destructor (that may allow destructor slicing). I dislike classes that try to be both concrete implementation classes and base classes; they are hard to design well (and this class wasn't intended to be such).  This was done to allow G1DirtyCardQueueSet to extend it with the `take_all` function; that seems like a useful operation in the generic form, even if it can't be made thread-safe.  (The G1 function asserts_at_safepoint(), but that's not really appropriate for a generic form.)

src/hotspot/share/gc/g1/g1DirtyCardQueue.hpp line 34:

> 32: #include "gc/shared/ptrQueue.hpp"
> 33: #include "memory/allocation.hpp"
> 34: #include "memory/padded.hpp"

There are other uses of padded in this file besides those in the Queue that are being moved to lockFreeQueue.hpp.

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

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