I’m reading a thesis by Maged M. Michael that introduces hazard pointer.

Here is an Enqueue function that uses hazard pointer:

//FIFO queue algorithm, stripped of memory management code
structure NodeType { Data:DataType; Next:*NodeType; }
//Shared variables
Head,Tail:*NodeType;
//Initially both Head and Tail point to a dummy node

//hp0 is private ptr to 2 of the thread's hazard ptrs

Enqueue(data: DataType) {
1. node <- NewNode();
2. node.Data <- data;
3. node.Next <- null;
   while true {
4.   t <- Tail;
4a:  *hp0 <- t;
4b:  if (Tail ≠ t) continue;
5.   next <- t.Next
6.   if (Tail ≠ t) continue;
7.   if (next ≠ null) {CAS(&Tail, t, next); continue;}
8.   if CAS(&t.next, null, node) break;
   }
9. CAS(&Tail, t, node);
}

Without lines 4a and 4b, accessing the node at line 5 could be an access hazard because another thread might have removed and reclaimed the node *t after the current thread executed line 4.

Access hazard: A thread tries to access a node that has already been freed by another thread.

The author says that Lines 4a and 4b guarantees safe memory reclamation and ABA prevention.

• line 4a: The thread assigns the address of the referenced node to a hazard pointer

• line 4b: Then, it validates that node is safe. If not, it skips over the hazards and tries again.

I understand how lines 4a and 4b guarantees safe memory reclamation, but I don’t see how they guarantees ABA prevention.

The author also mentions that another thread could potentially remove and then re-insert the node between lines 4 and 4b. However, the author says this is acceptable because it doesn’t violate a condition in Section 3.3.

In other words, the author acknowledges the ABA problem (node removal and re-insertion) might occur, but as long as a specific condition from Section 3.3 holds, it’s okay.

Section 3.3 Condition:

Therefore, the condition that an associated algorithm must satisfy is that whenever a thread is holding a hazardous reference to a node, it must be the case that at least one of the thread’s hazard pointers has been continuously holding that reference from a time when the node was definitely safe for the thread. Note that this condition implies that no thread can create a new hazardous reference to a node while it is retired.

I don’t understand how this condition relates to preventing the ABA problem at lines 4a and 4b.