Possible typo/bug in the Michael and Scott queue white paper psuedo-code

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.