470511 (1) [Avatar] Offline
#1
Hello,
I have a question very similar to http://stackoverflow.com/questions/41292524/lock-free-stack-visibility-issue-when-checking-hazard-pointers-during-pop .

In your hazard pointer implementation of the lock free stack, in between the lines :


temp = old_head;
-- pre-emption point A
hp.store(old_head);
--pre-emption point B
old_head = head.load();

What would prevent a thread t2 from coming, popping the element, seeing no hazard from T1, deleting old_head, then maybe popping it back in, and then when T1 resumes it thinks all is fine and suffers from ABA.
i see no relationship forcing T2 to see the T1 hp store in the "outstanding_hazard_pointers_for" function (in the case of preemption at B), there s a release store from T1, and an acquire load from T2, but nothing forces T2 to see the "latest" value of the T1 hp pointer, only read-modify-writes operations are guaranteed to see the latest value in the modification order. The read-modify-write is only on old_head and does not "touch" hp so why should T2 see the hp set by T1? You could even consider a suspension of T1 just before the hp.store line with the same scenario of delete+reallocate.

I would appreciate any help to understand which guarantees apply that precludes the scenario I have outlines here. I have searched intensively for related articles on hazard pointers and found no rigorous explanations of why the memory ordering is sufficient this way, everyone merely copy pastes the original paper implementation with this loop.
Thank you


anthony.williams (192) [Avatar] Offline
#2
All these operations are done with the default memory_order_seq_cst memory ordering. This requires a single global total order on all such operations. Therefore any operations on other threads must either be as-if they are before the store to hp, or after it. The loads are not "acquire" loads, they are sequentially consistent loads, so force global ordering.

This loop is the start of the operation, and it ensures that it is flagged (in the hazard pointer) that we are interested in the given pointer value (head) before we use it. The ABA issue you allude to is not actually a problem --- before we store the hazard pointer it doesn't matter what happens, or how the pointer changes, as we haven't started our algorithm yet. After we store the hazard pointer, the other threads will see that store, and won't delete the object, and thus can't recycle it, so there is no ABA problem.