non-blocking singly-linked list (incomplete)

Makefile

CFLAGS = -Wall -O2 -std=c11

all:
	$(CC) $(CFLAGS) -o tests \
		tests.c nblist.c

clean:
	rm -f tests

nblist.c

#include <assert.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdlib.h>

#include "nblist.h"

enum {
    F_MARK = 1, /* dead */
    F_FLAG = 2, /* next is about to die */
    F__MASK = 3,
};

static inline struct nblist_node *n_ptr(uintptr_t x)
{
    return (struct nblist_node *) (x & ~F__MASK);
}

/* set flag on *@pp, passing through backlinks as necessary.
 * @p_val is set to a value of (*@pp)->next. *@pp is updated to the node that
 * points to @n, which may be the list head, or NULL if @n is not on the list
 * anymore. returns true if *@pp points to @n and this flagged it, false
 * otherwise.
 */
static bool try_flag(struct nblist_node **pp,
                     uintptr_t p_val,
                     struct nblist_node *n)
{
    struct nblist_node *p = *pp;
    const uintptr_t new_val = (uintptr_t) n | F_FLAG;

    bool got;
    for (;;) {
        if (p_val == new_val) {
            *pp = p;
            return false;
        }

        uintptr_t old_val = (uintptr_t) n;
        got = atomic_compare_exchange_strong(&p->next, &old_val, new_val);
        if (got || old_val == new_val) {
            /* success, or concurrent flagging. */
            *pp = p;
            return got;
        }

        p_val = old_val;

        /* failure due to concurrent marking. follow backlinks. */
        while ((p_val & F_MARK) != 0) {
            p = atomic_load_explicit(&p->backlink, memory_order_relaxed);
            assert(p);
            p_val = atomic_load_explicit(&p->next, memory_order_relaxed);
        }

        /* @p is no longer @n's parent. walk forward until the parent is
         * found, or return NULL.
         */
        assert(n_ptr(p_val));
        while (n_ptr(p_val) != n) {
            p = n_ptr(p_val);
            p_val = atomic_load_explicit(&p->next, memory_order_relaxed);
            if (!n_ptr(p_val)) {
                *pp = NULL;
                return false;
            }
        }
    }

    *pp = p;
    return got;
}

/* complete removal of @prev -> @n, where @nextval == @n->next. */
static inline void rend_the_marked(struct nblist_node *prev,
                                   struct nblist_node *n,
                                   uintptr_t nextval)
{
    assert((nextval & F_MARK) != 0);
    assert((nextval & F_FLAG) == 0);
    uintptr_t prevval = (uintptr_t) n | F_FLAG;
    atomic_compare_exchange_strong_explicit(
        &prev->next, &prevval, nextval & ~F__MASK, memory_order_release,
        memory_order_relaxed);
}

/* complete removal of @n from flagged parent @prev. */
static void clear_flag(struct nblist_node *prev, struct nblist_node *n)
{
    struct nblist_node *old =
        atomic_exchange_explicit(&n->backlink, prev, memory_order_release);
    assert(!old || old == prev);

    /* set mark, load fresh @n->next. */
    uintptr_t nextval = atomic_load_explicit(&n->next, memory_order_relaxed);
    while ((nextval & F_MARK) == 0) {
        while ((nextval & F_FLAG) != 0) {
            clear_flag(n, n_ptr(nextval));
            nextval = atomic_load(&n->next);
        }
        if (atomic_compare_exchange_strong_explicit(
                &n->next, &nextval, nextval | F_MARK, memory_order_release,
                memory_order_relaxed)) {
            nextval |= F_MARK;
        }
    }

    rend_the_marked(prev, n, nextval);
}

bool nblist_push(struct nblist *list, struct nblist_node *top, struct nblist_node *n)
{
    assert(((uintptr_t) n & F__MASK) == 0);
    uintptr_t old = atomic_load_explicit(&list->n.next, memory_order_acquire);
    while ((old & F_FLAG) != 0) {
        clear_flag(&list->n, n_ptr(old));
        old = atomic_load(&list->n.next);
    }
    assert((old & F_MARK) == 0);
    n->next = old;
    n->backlink = NULL;
    return n_ptr(old) == top && atomic_compare_exchange_strong_explicit(
                                    &list->n.next, &old, (uintptr_t) n,
                                    memory_order_release, memory_order_relaxed);
}

struct nblist_node *nblist_pop(struct nblist *list)
{
    struct nblist_node *p = &list->n;
    uintptr_t p_val = atomic_load(&p->next);
    assert((p_val & F_MARK) == 0);
    struct nblist_node *n = n_ptr(p_val);

    /* find the first n: p -> n where ¬p.flag ∧ ¬p.mark, and atomically set
     * p.flag .
     */
    while (n) {
        if ((p_val & F__MASK) != 0) {
            p = n;
            p_val = atomic_load(&p->next);
        } else if (atomic_compare_exchange_strong(&p->next, &p_val,
                                                  XXXX)) {
            break;
        }
        n = n_ptr(p_val);
    }
    if (!n)
        return NULL;

    clear_flag(p, n);
    return n;
}

struct nblist_node *nblist_top(struct nblist *list)
{
    return n_ptr(atomic_load_explicit(&list->n.next, memory_order_acquire));
}

bool nblist_del(struct nblist *list, struct nblist_node *target)
{
    /* find p -> n, where n == target. */
    struct nblist_node *p = &list->n, *n = NULL;
    uintptr_t p_val = atomic_load(&p->next), n_val;
    while (n_ptr(p_val)) {
        n = n_ptr(p_val);
        n_val = atomic_load(&n->next);

        if ((n_val & F_MARK) != 0 && (p_val & F_FLAG) != 0) {
            /* complete an in-progress deletion. */
            rend_the_marked(p, n, n_val);
            if (n == target)
                return false;
            p_val = atomic_load(&p->next);
        } else if (n == target) { /* got it */
            break;
        }
        p = n;
        p_val = n_val;
    }
    if (!n_ptr(p_val))
        return false;

    /* flag and delete. */
    bool got = try_flag(&p, p_val, n);
    if (p)
        clear_flag(p, n);
    return got;
}

static struct nblist_node *skip_dead_nodes(struct nblist_iter *it)
{
    while (it->cur) {
        uintptr_t next =
            atomic_load_explicit(&it->cur->next, memory_order_relaxed);
        if ((next & F_MARK) == 0)
            break;
        /* it->prev remains as before. */
        it->cur = n_ptr(next);
    }
    return it->cur;
}

struct nblist_node *nblist_first(struct nblist *list, struct nblist_iter *it)
{
    it->prev = (struct nblist_node *) &list->n;
    it->cur = n_ptr(atomic_load_explicit(&list->n.next, memory_order_acquire));
    return skip_dead_nodes(it);
}

struct nblist_node *nblist_next(struct nblist *list, struct nblist_iter *it)
{
    it->prev = it->cur;
    it->cur =
        n_ptr(atomic_load_explicit(&it->prev->next, memory_order_relaxed));
    return skip_dead_nodes(it);
}

bool nblist_del_at(struct nblist *list, struct nblist_iter *it)
{
    if (!it->cur)
        return false; /* edge case: cursor at end. */
    if (!it->prev)
        return false; /* repeat case: always NULL */

    uintptr_t cur_val =
        atomic_load_explicit(&it->cur->next, memory_order_relaxed);
    if ((cur_val & F_MARK) != 0)
        return false; /* already gone */

    struct nblist_node *p = it->prev;
    uintptr_t p_val = atomic_load_explicit(&p->next, memory_order_acquire);
    bool got = try_flag(&p, p_val, it->cur);
    it->prev = NULL;
    if (p)
        clear_flag(p, it->cur);
    return got;
}

nblist.h

/* non-blocking singly-linked lists.
 *
 * the algorithm used was presented by Fomitchev and Ruppert in "Lock-Free
 * Linked Lists and Skip Lists" (2003).
 *
 * this implementation supports insert at the list head ("push"), deletion at
 * any point, and iteration. the intrusive link structure ("nblist_node") must
 * be aligned to 4; due to storage of metadata in the low bits, structures
 * pointed to solely with this mechanism might not show up as reachable in
 * valgrind etc.
 */

#pragma once

#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

/* container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */
#ifndef container_of
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#endif

struct nblist_node {
    _Atomic uintptr_t next;
    struct nblist_node *_Atomic backlink;
} __attribute__((aligned(4)));

struct nblist {
    struct nblist_node n;
};

#define NBSL_LIST_INIT(name)            \
    {                                   \
        {                               \
            .next = 0, .backlink = NULL \
        }                               \
    }

static inline void nblist_init(struct nblist *list)
{
    struct nblist proto = NBSL_LIST_INIT(proto);
    *list = proto;
}

/* push @n at the head of @list, if the previous head == @top. returns true if
 * successful, false if the caller should refetch @top and try again.
 */
bool nblist_push(struct nblist *list, struct nblist_node *top, struct nblist_node *n);

/* pop first node from @list, returning it or NULL. */
struct nblist_node *nblist_pop(struct nblist *list);

/* peek first node in @list, returning it or NULL. */
struct nblist_node *nblist_top(struct nblist *list);

/* remove @n from @list. O(n).
 *
 * returns true if the current thread removed @n from @list; false if some
 * other thread did it, or if removal was deferred due to concurrent access of
 * the previous node. in the first case @n will have gone away once nblist_del()
 * returns; in the second, @n will have been removed from @list once every
 * concurrent call to nblist_del() and nblist_push() have returned.
 */
bool nblist_del(struct nblist *list, struct nblist_node *n);

struct nblist_iter {
    struct nblist_node *prev, *cur;
};

/* iteration with option to delete. this is always read-only, i.e. never
 * causes writes to any node along the chain. it skips over dead nodes, but
 * the ones it returns may appear dead nonetheless due to concurrent delete.
 */
struct nblist_node *nblist_first(struct nblist *list, struct nblist_iter *it);
struct nblist_node *nblist_next(struct nblist *list, struct nblist_iter *it);

/* attempt to remove value returned from previous call to nblist_{first,next}(),
 * returning true on success and false on failure. @it remains robust against
 * concurrent mutation; subsequent calls to nblist_del_at() before nblist_next()
 * always return false.
 *
 * a sequence of nblist_del_at() and nblist_next() can be used to pop all nodes
 * from @list from a certain point onward.
 */
bool nblist_del_at(struct nblist *list, struct nblist_iter *it);

tests.c

/* basic interface tests on the non-blocking singly-linked lists. */

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

#include "nblist.h"

struct item {
    struct nblist_node link;
    int value;
};

static struct item *push(struct nblist *list, int value)
{
    struct item *it = malloc(sizeof(*it));
    it->value = value;
    int spins = 0;
    while (!nblist_push(list, nblist_top(list), &it->link)) {
        /* spin */
        printf("%s: repeating", __func__);
        if (++spins == 10)
            abort();
    }
    return it;
}

static struct item *pop(struct nblist *list)
{
    struct nblist_node *link = nblist_pop(list);
    return container_of(link, struct item, link);
}

static struct item *top(struct nblist *list)
{
    struct nblist_node *link = nblist_top(list);
    return container_of(link, struct item, link);
}

int main(void)
{
    struct nblist *list = malloc(sizeof(*list));
    nblist_init(list);
    struct item *n1 = push(list, 1);
    push(list, 2);
    push(list, 3);
    push(list, 4);

    /* test "pop" while items exist. */
    assert(top(list));
    assert(pop(list)->value == 4);
    assert(top(list));
    assert(top(list)->value == 3);

    /* test nblist_del() from top. */
    assert(nblist_del(list, nblist_top(list)));
    assert(top(list));
    assert(top(list)->value == 2);

    /* test nblist_del() from bottom. */
    assert(nblist_del(list, &n1->link));
    assert(top(list));
    assert(top(list)->value == 2);

    /* popping the last element */
    assert(pop(list)->value == 2);
    assert(!top(list));
    assert(!pop(list));

    return 0;
}