Lock-free FIFO queue implementation

Question

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;

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

static inline fifo_node_t *__fifo_list_pop(fifo_list_t *head)
{
        fifo_node_t *node;
        while ((node = ACCESS_ONCE(head->next)) != head) {
                fifo_node_t *next = ACCESS_ONCE(node->next);
                if (cmpxchg_eq(&head->next, node, next) == node) {
                        if (cmpxchg_eq(&head->tail, node, head) != node &&
                            next == head)
                                while (ACCESS_ONCE(head->next) == next)
                                        head->next = ACCESS_ONCE(node->next);
                        return node;
                }
        }
        return NULL;
}

static inline void __fifo_list_init(fifo_list_t *head)
{
        head->next = head->tail = head;
}

---

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.

Answer 1

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)