Lock-free Stack

Stack is a last-in-first-out (LIFO) data structure. We will implement a linked list lock-free stack using the C11 features we learned by far.

Let's see the procedure of pushing a node into a stack.

This works well in a single-thread context, but if other threads are also modifying the stack, it’s not enough. Let's see what would happen if two threads push a node into the stack concurrently.

What can you do about this nasty race condition in a lock-free data-structure? The answer is to use an atomic compare-and-swap (CAS) operation to set the head node to point to your new node. The success of CAS operation ensures that the head hasn’t been modified since you last read it; otherwise, you should retry.

my_stack.h

#include <stdio.h>
#include <stdatomic.h>
#include <stdlib.h>

//the node type in the stack
typedef struct _Node
{
    int data;
    struct _Node *next;
} Node;

//the stack
typedef struct _lfstack_t
{
    Node *head;
} lfstack_t;

//the push function
void lfstack_push(_Atomic lfstack_t *lfstack, int value);

//pop function
int lfstack_pop(_Atomic lfstack_t *lfstack);

The procedure of pop function can be similarly analyzed. Here is the push and pop function in my_stack.c:

/* my_stack.c */
#include "my_stack.h"
// the push function
void lfstack_push(_Atomic lfstack_t *lfstack, int value) {
    lfstack_t next;
    lfstack_t orig = atomic_load(
        lfstack); // here we need a local copy of lfstack, however, lfstack is a pointer
                  // we could not get the content from a struct pointer atomically by
                  // assignment C11 provides us a function for us to atomically get the
                  // content from the location that a atomic type pointer points to.
    Node *node = malloc(sizeof(Node)); // the new node, step 1
    node->data = value;
    do {
        node->next = orig.head; // step 2
        next.head = node;       // local change of head
    } while (!atomic_compare_exchange_weak(
        lfstack, &orig, next)); // if the lfstack is not changed by others, apply the
                                // local change of head to it
}

// pop function
int lfstack_pop(_Atomic lfstack_t *lfstack) {
    lfstack_t next;
    lfstack_t orig = atomic_load(lfstack);
    do {
        if (orig.head == NULL) // return when the stack is empty
        {
            return -1;
        }
        next.head = orig.head->next; // set the head to the next node
    } while (!atomic_compare_exchange_weak(
        lfstack, &orig, next)); // if the head of stack is not changed, update the stack
    printf("poping value %d\n", orig.head->data); // just want to see the poping value.
    free(orig.head);                              // free the poping node
    return 0;
}

Next, we put the lock-free stack in a multi-threading environment to be accessed as a shared data-structure.

/* test_my_stack.c */
#include "my_stack.h"
#include <stdio.h>
#include <pthread.h>
_Atomic lfstack_t top = {NULL};

void *push(void *input)
{
    for (int i = 0; i < 100000; i++)
    {
        lfstack_push(&top, i);
        printf("push %d\n", i);
    }
    pthread_exit(NULL);
}

void *pop(void *input)
{
    for (int i = 0; i < 100000;)
    {
        int result;
        result = lfstack_pop(&top);
        if (result == -1)
            printf("the stack is empty\n");
        else
        {
            i++;
        }
    }
    pthread_exit(NULL);
}

int main()
{
    pthread_t tid[200];
    for (int i = 0; i < 100; i++)
        pthread_create(&tid[i], NULL, push, NULL);
    for (int i = 100; i < 200; i++)
        pthread_create(&tid[i], NULL, pop, NULL);
    for (int i = 0; i < 200; i++)
        pthread_join(tid[i], NULL);
    return 0;
}

Actually, the print statement is not run together after they push/pop a node, so you may not see the print results in a LIFO order. We should compile the program by using the command:

gcc -std=c11 -lpthread -o my_stack my_stack.c

The program seems perfect, but the program may still abort occasionally when you run it. There is an underlying problem that you may not have noticed. It is called ABA problem to be introduced next.