RFR (M) 8195099: Concurrent safe-memory-reclamation mechanism

[David Holmes]

On 11/04/2018 6:01 PM, Kim Barrett wrote:
>> On Apr 10, 2018, at 9:34 PM, David Holmes <david.holmes at oracle.com> wrote:
>>
>> Hi Robin,
>>
>> On 10/04/2018 10:18 PM, Robbin Ehn wrote:
>>> Hi all,
>>> We have moved the global-counter to a separate change-set. The global-counter
>>> uses a counter to determine current generation. Any reader needs to have a local
>>> counter for which generation is currently read. By increment the global-counter
>>> and scan for threads reading an old generation and wait for them to complete, we
>>> know when an old generation is not visible (no pre-existing reader). In RCU
>>> terms, this creates a grace-period. Making this mechanism suitable for a read-mostly scenario. In this initial change-set we scan JavaThreads and the VMThread.
>>
>> Sorry but I don't understand how this works. If a reader calls:
>>
>>   31 inline void GlobalCounter::critical_section_begin(Thread *thread) {
>>   32   assert(thread == Thread::current(), "must be current thread");
>>   33   assert(thread->is_VM_thread() || thread->is_Java_thread(), "must be VMThread or JavaThread");
>>   34   assert((*thread->get_rcu_counter() & COUNTER_ACTIVE) == 0x0, "nestled critical sections, not supported yet");
>>   35   volatile uintx gbl_cnt = OrderAccess::load_acquire(&_global_counter._counter);
>>   36   OrderAccess::release_store_fence(thread->get_rcu_counter(), gbl_cnt + 1);
>>   37 }
>>
>> and is preempted before the store at line 36, the writer will not see it and can go ahead and free the data used in the critical section. The reader does no validation of the counter value and so continues in to the critical section. Surely there has to be a handshake between the reader and writer, where the reader signals their intention to enter a critical section for generation X, then re-reads the generation count to check it has not changed. ??
> 
> A writer updates its protected shared state and then waits for any
> readers that might see the previous value of that shared state.  That
> is, any reader that is in the critical section (has the active bit set
> in its local counter) *and* entered before the shared state was
> updated.  The latter is conservatively approximated by actually
> checking whether the reader entered the critical section before the
> wait started, with the wait ordered after the shared state update.
> 
> The wait check implements the latter condition via a range test.  If
> the reader entered before the wait, then it's local counter is "less
> than" the writer's updated counter.  This is implementated by an
> unsigned subtract and checking for a large result.  (With this
> implementation there is a limit on just how stale the reader can be; a
> reader must complete a critical section before max_uintx/4 writers
> wait.)
> 
> When a writer updates protected shared state, increments the global
> counter, and then checks / waits for readers,
> 
> (1) If a reader obtained a global counter value before that increment,
> but has not yet set its local state to indicate it is active, then the
> writer will not wait for it.  But that's okay, because when the reader
> gets around to entering the critical region and examining the
> protected shared state, it is guaranteed not to see the old value of
> the protected shared state.
> 
> (2) If a reader obtained a global counter value before that increment
> and marked itself active, then the writer will wait until the reader
> exits the critical section.  The reader might see the old value of the
> protected shared state while in the critical region.
> 
> (3) If a reader obtained a global counter value after that increment,
> then it is guaranteed not to see the old value of the protected shared
> state.

Sorry Kim but I can't quite follow all that. What is the "shared state" 
you are referring to?

If a reader executes line 35 to read the current global counter and then 
is preempted before storing that into thread->get_rcu_counter(), then 
there is nothing for the writer to see - it has no knowledge of this 
about-to-be reader.

David

>