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