Return to Answer

###The meaning of lock-free###

Although your program is free of locks in the traditional sense, "lock free programming" typically describes a style of programming with certain guarantees. One of these guarantees is that even if one or more threads are suspended indefinitely, other threads can continue to make progress. This wikipedia article on Non-blocking algorithms describes "lock-free" and "wait-free" programming in more detail.

In your code, if one thread is permanently suspended between these two lines:

 prev = atomic_xchg64(&head->tail, node);
 prev->next = node;

then some other thread will spin forever in this loop:

 while (ACCESS_ONCE(head->next) == next)
 head->next = ACCESS_ONCE(node->next);

and furthermore, no nodes past the node that the suspended thread "half-pushed" will be able to be popped.

###ABA problem###

Additionally, your code falls victim to the ABA problem. Consider an initial situation with two nodes in your FIFO:

A -> B (head->next = A, head->tail = B)

Suppose thread #1 calls __fifo_list_pop(), and gets to this line:

 if (cmpxchg_eq(&head->next, node, next) == node) {

Here, node will be A, and next will be B, and the code is about to atomically change head->next from A to B.

Now suppose thread #1 is descheduled, and in the meantime, other threads pop both A and B off the FIFO, and then push A and C back on the FIFO. Now, your FIFO looks like this:

A -> C (head->next = A, head->tail = C)

If thread #1 now wakes up, it will perform the atomic exchange, causing head->next to point at B which isn't even alive any more:

A -> B (but B was already popped and is now dead)

The meaning of lock-free

Although your program is free of locks in the traditional sense, "lock free programming" typically describes a style of programming with certain guarantees. One of these guarantees is that even if one or more threads are suspended indefinitely, other threads can continue to make progress. This wikipedia article on Non-blocking algorithms describes "lock-free" and "wait-free" programming in more detail.

In your code, if one thread is permanently suspended between these two lines:

 prev = atomic_xchg64(&head->tail, node);
 prev->next = node;

then some other thread will spin forever in this loop:

 while (ACCESS_ONCE(head->next) == next)
 head->next = ACCESS_ONCE(node->next);

and furthermore, no nodes past the node that the suspended thread "half-pushed" will be able to be popped.

ABA problem

Additionally, your code falls victim to the ABA problem. Consider an initial situation with two nodes in your FIFO:

A -> B (head->next = A, head->tail = B)

Suppose thread #1 calls __fifo_list_pop(), and gets to this line:

 if (cmpxchg_eq(&head->next, node, next) == node) {

Here, node will be A, and next will be B, and the code is about to atomically change head->next from A to B.

Now suppose thread #1 is descheduled, and in the meantime, other threads pop both A and B off the FIFO, and then push A and C back on the FIFO. Now, your FIFO looks like this:

A -> C (head->next = A, head->tail = C)

If thread #1 now wakes up, it will perform the atomic exchange, causing head->next to point at B which isn't even alive any more:

A -> B (but B was already popped and is now dead)