Okay, so, I’m about to make quite a claim – and I do not make it lightly, and I make it in full knowledge that I am extremely likely to be completely wrong. M&S are experts in the field, and I am not.
This is the dequeue psuedo-code from their white paper.
dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean D1: loop // Keep trying until Dequeue is done D2: head = Q->Head // Read Head D3: tail = Q->Tail // Read Tail D4: next = head.ptr->next // Read Head.ptr->next D5: if head == Q->Head // Are head, tail, and next consistent? D6: if head.ptr == tail.ptr // Is queue empty or Tail falling behind? D7: if next.ptr == NULL // Is queue empty? D8: return FALSE // Queue is empty, couldn't dequeue D9: endif D10: CAS(&Q->Tail, tail,
) // Tail is falling behind. Try to advance it D11: else // No need to deal with Tail D12: *pvalue = next.ptr->value // Read value before CAS Otherwise, another dequeue might free the next node D13: if CAS(&Q->Head, head, ) // Try to swing Head to the next node D14: break // Dequeue is done. Exit loop D15: endif D16: endif D17: endif D18: endloop D19: free(head.ptr) // It is safe now to free the old node D20: return TRUE // Queue was not empty, dequeue succeeded
Now, note the free on D19. The authors are making the point, as they do in the white paper, that once you’ve dequeued, you’re in the clear – you can free the node.
The typo or bug which I think I see is on line D4.
D4: next = head.ptr->next // Read Head.ptr->next
The code says “next = head.ptr->next”, which is using “head”, lower-case “h”. The comment says “Head.ptr->next”, which is using “Head”, upper-case “H”, where as we see on D2, “Head” (upper-case) means Q->Head.
I may be utterly wrong, but I think if the code is used, the free on D19 is broken, because it could lead the code (not the comment – the code) on D4 to access a freed node.
The problem is that “head” (lower-case) is a copy of Q->Head. The white paper states the Q->Head will always point to a valid node (as there is a dummy node in the queue) and that’s fine – but we have taken at line D2 a copy of Q->Head, and we can imagine it points a node, where that node could be by another thread dequeued and freed at D19, before our thread gets to D4 and tries to access that node’s next pointer.
The comment however looks right to me – if we read Q->Head.ptr->next, we’d still be fine, as the if() on D5 still works – but it would mean we could now safely call free on D19.
There is a matching issue in the enqueue, on E5, E6 an E7 – but here the comment and code match up.