[Question] Understanding of access hazard & ABA hazard
wyhallenwu opened this issue · 1 comments
In the paper of hazard pointers page 8, the author gives an example of FIFO enqueue, the pseudo code is as follows
Enqueue(data) {
1: node <- new node
2: node.data <- data
3: node.next <- null
while true {
4a: *hp0 <- t
4b: if (tail != t ) continue
5: next <- t.next // Access hazard on t
6: if (tail != t) continue // ABA hazard
7: if (next !=null) {CAS(tail, t, next); continue;} // ABA hazard
8: if CAS(t.next, null, node) break; // Acess and ABA hazard
}
9: CAS(tail, t, node) // ABA hazard
I attach the author's statement on whether it is ABA hazard or Access hazard of each line to the code.
From my understanding, ABA hazard is reading a memory location maybe changed from A->B->A; Access hazard is reading a memory location maybe removed or reclaimed.
In this case, I'm confusing why the line 5 is only Access hazard instead of to be both ABA and Access hazard? because t is also possible to be change by another thread and then change back to its original value.
and why the line 6 becomes ABA hazard? I feel that if one line is access hazard, it's also possible to be ABA hazard.
Is there anything I misunderstand?
ABA hazard vs Access hazard
As you said, ABA hazard happens when memory locations pointed by a particular pointer changes from A -> B -> A but the first A
and second A
may have different origin (thus we should view it as a different object). Such situation happens if one thread changes the pointer from A -> B and deallocates A, but another thread reallocates A by chance and changes the pointer from B -> A. It is considered as a severe problem since we cannot distinguish the first A
and the second A
by simply reading from the pointer and comparing two addresses. So the essence of ABA problem is misjudgment by naive comparing memory accesses.
On the other hand, access hazard only considers invalid memory accesses (such as use-after-free). Thus it describes different problem with ABA hazard.
Line 5
Line 5 merely accesses .next
field of t
, but it does not make any judgement by making a comparison. As a result, line 5 is subject to only access hazard, but not ABA hazard.
Line 6
Line 6 is indeed ABA hazard since even if the latest value of tail
is equal to t
, the latest value of tail
may have different origin than t
(consider a situation where t
is deallocated by another thread and reallocated) but we are making judgement that tail
has not been changed so far by such comparison.