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

[Robbin Ehn]

On 04/11/2018 02:03 PM, David Holmes wrote:
> On 11/04/2018 9:38 PM, Robbin Ehn wrote:
>> Hi,
>>
>> On 04/11/2018 12:57 PM, David Holmes wrote:
>>>
>>> Sorry no, I don't understand what this counter is doing at all. I feel I need 
>>> to see what is between the begin/end critical section for this to make any 
>>> sense to me. And to see what the writer actually does.
>>
>>  From gtest:
> 
> Thanks for that. Okay I have a better sense of how the access to the data 
> completes the handshake.
> 

Great!

> Does the naming/terminology come from some existing mechanism? I find it 
> somewhat odd and not really descriptive of the operation..

There several of different versions but they follow the same naming scheme.
E.g. such as smr_begin, smr_end, synchronize

Thanks, Robbin

> 
> Thanks,
> David
> 
>> Read side do:
>>    49       GlobalCounter::critical_section_begin(this);
>>    50       volatile TestData* test = OrderAccess::load_acquire(_test);
>>    51       long value = OrderAccess::load_acquire(&test->test_value);
>>    52       ASSERT_EQ(value, GOOD);
>>    53       GlobalCounter::critical_section_end(this);
>> Write side do:
>>   101         volatile TestData* free_tmp = test;
>>   102         tmp = new TestData();
>>   103         tmp->test_value = GOOD;
>>   104         OrderAccess::release_store(&test, tmp);
>>   105         GlobalCounter::write_synchronize();
>>   106         free_tmp->test_value = BAD;
>>   107         delete free_tmp;
>>
>> If a reader is context switch between line 50 and 51, it will have a cached 
>> value of the pointer "_test", thus no one should free it.
>>
>> Before freeing the writer calls write_synchronize which guarantees that no 
>> reader can see the old pointer and can then free it.
>>
>> If the reader is context switch inside critical_section_begin this does not 
>> matter since the fence in critical_section_begin prohibits the load of test 
>> pointer from floating up. If write_synchronize is done before this reader gets 
>> back on CPU it will see the new value but have an counter of an old generation.
>> If it gets back on CPU before write_synchronize I will see the old pointer.
>>
>> If we call the pointer values TEST_gen_1, TEST_gen_2, ...
>> test_pointer starts equal to TEST_gen_1 and generation starts at 1.
>>
>> Writer: tmp_pointer = test_pointer
>> Writer: test_pointer = TEST_gen_2
>> Reader: load global counter (fetches 1)
>> Reader: context switched out
>> Writer: write_synchronized generation = 2, and do not see the reader.
>> Reader: store local counter to 1 // critical section begin
>> Reader: load test_pointer (TEST_gen_2) // This load will always happen *after* 
>> the store to local counter
>> Writer: free tmp_pointer (TEST_gen_1) // ABA safe
>>
>> Writer: tmp_pointer = test_pointer
>> Writer: test_pointer = TEST_gen_3
>> Writer: write_synchronized generation = 3, and _sees_ on old reader => wait.
>> Reader: store local counter OFF // critical section end
>> Writer: write_synchronized now finishes.
>> Writer: free tmp_pointer (TEST_gen_2) // ABA safe
>>
>> /Robbin
>>
>>>
>>> David
>>> -----