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

[Kim Barrett]

On Tue, 30 Mar 2021 08:24:16 GMT, Man Cao <manc at openjdk.org> wrote:

>> src/hotspot/share/utilities/lockFreeQueue.inline.hpp line 100:
>> 
>>> 98: template<typename T, T* volatile* (*next_ptr)(T&)>
>>> 99: template<bool use_rcu>
>>> 100: T* LockFreeQueue<T, next_ptr>::pop() {
>> 
>> On further consideration I don't think this `use_rcu` conditionalized `pop` is the right path. The current behavior (with the embedded critical section) was for the specific use case in `G1DirtyCardQueueSet`. But for a general tool, I think a different approach is needed. I think better would be to not provide `pop()` at all, and instead provide `try_pop()`, which has a tri-status result: success, lost a race, or lost to an in-progress operation. So something like:
>> enum class LockFreeQueuePopStatus {
>>   success,
>>   lost_race,
>>   operation_in_progress
>> };
>> 
>> // Member of LockFreeQueue<T, ...>
>> // Executes the body of the old pop loop once, with appropriate
>> // adjustments to return value and returning rather than retrying.
>> Pair<LockFreeQueuePopStatus, T*> try_pop();
>> Then let the specific use-case determine the context in which try_pop should be called and how to handle the various possible results.
>> 
>> This eliminates `ConditionalCriticalSection` (which seems strange). This also eliminates the `G1DirtyCardQueueSet`-specific subclass of `LockFreeQueue`. Instead we have (private) `G1DirtyCardQueueSet::pop_queue()`:
>> BufferNode* G1DirtyCardQueueSet::pop_queue() {
>>   using Status = LockFreeQueuePopStatus;
>>   Thread* current_thread = Thread::current();
>>   while (true) {
>>     GlobalCounter::CriticalSection cs(current_thread);
>>     Pair<Status, BufferNode*> pop_result = _completed.try_pop();
>>     switch (pop_result.first) {
>>     case Status::success: return pop_result.second;
>>     case Status::operation_in_progress: return nullptr;
>>     case Status::lost_race: break;  // Try again.
>>     }
>>   }
>> }
>> I'm also not sure whether the G1 case actually needs the critical section inside the loop anymore. That might be a holdover from an earlier version where the operation-in-progress case did just loop to try again. It definitely does need a critical section though; the life cycle management for the BufferNodes depends on it.
>
> Thanks for the suggestion, and yes this makes sense. Done. Could you double-check if the updated comments are appropriate?
> 
> My only concern is that the difference between operation_in_progress and lost_race may be too subtle for most client code. I suppose most client code can just do "retry until succeeded" like in the test.
> I don't expect these two cases to differ much in run-time. Is there any performance data to show that the operation_in_progress case indeed takes much longer for retrying? I checked review threads for JDK-8237143 and JDK-8238867 but didn't find any.
> 
> Anyway, this CR should use the tri-status approach (and the intra-loop critical section approach), in order to avoid behavior change.

In the "lost-race" cases, there was cmpxchg contention that the current thread lost. Retry is a reasonable thing to do, though that's up to the application. Success on retry is of course not guaranteed, because there could again be contention with some other thread, but at least somebody is making progress.

In the "operation-in-progress" cases the queue is in a state where the current operation cannot make progress until a different thread changes the state. If that other thread happens to have been descheduled or something like that, it could be a (comparatively) very long time before that happens, with lots of expensive spinning by a retrying try_pop.

So I think the comment for that state needs some more work.  Maybe something like this?

"An in-progress concurrent operation interfered with taking what had been the only remaining element in the queue. A concurrent try_pop may have already claimed it, but not completely updated the queue.  Alternatively, a concurrent push/append may have not yet linked the new entry(s) to the former sole entry. Retrying the try_pop will continue to fail in this way until that other thread has updated the queue's internal structure."

That was sufficient for the G1DCQS usage, so I stopped trying to do better.  (I don't even know if it's possible to do better, though I have some old notes on an idea.) But it's pretty ugly for a general utility, which is why I left this queue class buried inside G1DCQS rather than hoisting it out and generalizing it.

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

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