The Author Online Book Forums are Moving

The Author Online Book Forums will soon redirect to Manning's liveBook and liveVideo. All book forum content will migrate to liveBook's discussion forum and all video forum content will migrate to liveVideo. Log in to liveBook or liveVideo with your Manning credentials to join the discussion!

Thank you for your engagement in the AoF over the years! We look forward to offering you a more enhanced forum experience.

470511 (1) [Avatar] Offline
I have a question very similar to .

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

temp = old_head;
-- pre-emption point A;
--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 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 (216) [Avatar] Offline
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.