I'm trying to understand and implement a lock free queue in C. However there're some parts of the whitepaper I'm reading which I'm confused about.
First, if you look at line D5, locally stored head and Q->Head are being compared. When remove, it's causing issues regarding dead memory but I cannot understand how this provides any protection as Q->Head can be modified after the comparison was made.
Second, if you look at lines D4 and D19, head.ptr can(and sometimes is) be a freed pointer causing an access violation exception to be thrown.
Current implementation I have suffers from the second issue I mentioned:
int dequeue(struct Queue *queue, void **data)
{
struct Pointer QUEUE_ALIGN head;
struct Pointer QUEUE_ALIGN tail;
struct Pointer QUEUE_ALIGN next;
struct Pointer QUEUE_ALIGN new_ptr;
while (1)
{
head = queue->head;
tail = queue->tail;
next = head.ptr->next;
if (head.ptr == queue->head.ptr && head.counter == queue->head.counter)
{
if (head.ptr == tail.ptr)
{
if (next.ptr == 0)
{
return 0;
}
new_ptr.ptr = next.ptr;
new_ptr.counter = tail.counter + 1;
DWCAS((void*)&queue->tail, (void*)&tail, (void*)&new_ptr);
}
else
{
*data = next.ptr->data;
new_ptr.ptr = next.ptr;
new_ptr.counter = head.counter + 1;
if (DWCAS((void*)&queue->head, (void*)&head, (void*)&new_ptr))
{
break;
}
}
}
}
free(head.ptr);
return 1;
}