# Lock-free FIFO queue implementation

struct __fifo_node_t {
void *next;
};
typedef struct __fifo_node_t fifo_node_t;

struct __fifo_list_t {
void *next;
void *tail;
};
typedef struct __fifo_list_t fifo_list_t;

static inline void __fifo_list_push(fifo_list_t *head, fifo_node_t *node)
{
fifo_node_t *prev;

prev->next = node;
}

{
fifo_node_t *node;
fifo_node_t *next = ACCESS_ONCE(node->next);
if (cmpxchg_eq(&head->next, node, next) == node) {
return node;
}
}
return NULL;
}

{
}


atomic_xchg64 - Atomic exchange 64bit with new value and return the old value

cmpxchg_eq - Atomic compare and exchange 64bit with new value and return the old value

ACCESS_ONCE - (*(volatile typeof(x) *)&(x))

Can you review it? Is this implementation thread-safe ?

Thank you.

### 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)


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)

• Yes, you're right. – ShadowStar Mar 27 '17 at 4:14
• I always working on kernel mode (no-preemption, disabled-irq) or cavium octeon simple executive mode, and ignored scheduling of process. – ShadowStar Mar 27 '17 at 4:20
• @ShadowStar If you have no preemption and interrupts disabled, then the first section about deadlocking won't happen. But you can still get the ABA problem if you encounter a rare set of timings. Basically, there is a memory delay between a write on one core and its visibility on another core, and if the timings work out just the wrong way, the ABA problem will occur. – JS1 Mar 27 '17 at 5:36
• Yes, there is ABA problem in theory. – ShadowStar Mar 27 '17 at 5:43