1/* @title: Lock-free MPSC singly-linked list */
2#pragma once
3#include <compiler.h>
4#include <container_of.h>
5#include <stdatomic.h>
6#include <stdbool.h>
7#include <stddef.h>
8
9/*
10 * Producers call mpsc_slist_push()
11 * A single consumer calls mpsc_slist_drain() or mpsc_slist_pop_one()
12 *
13 * Producers are lock-free, batch drain is wait-free for the consumer
14 *
15 * No ABA: the consumer never CAS-unlinks individual nodes,
16 * it swaps the whole chain
17 */
18
19struct mpsc_slist_node {
20 struct mpsc_slist_node *next;
21};
22
23struct mpsc_slist {
24 _Atomic(struct mpsc_slist_node *) head;
25};
26
27#define MPSC_SLIST_INIT {NULL}
28#define MPSC_SLIST(name) struct mpsc_slist name = MPSC_SLIST_INIT
29
30static inline void mpsc_slist_init(struct mpsc_slist *q) {
31 atomic_store_explicit(&q->head, NULL, memory_order_relaxed);
32}
33
34static inline int mpsc_slist_empty(const struct mpsc_slist *q) {
35 return atomic_load_explicit(&q->head, memory_order_acquire) == NULL;
36}
37
38/* Returns true if list was previously empty */
39static inline bool mpsc_slist_push(struct mpsc_slist *q,
40 struct mpsc_slist_node *n) {
41 struct mpsc_slist_node *old =
42 atomic_load_explicit(&q->head, memory_order_relaxed);
43 do {
44 n->next = old;
45 } while (!atomic_compare_exchange_weak_explicit(
46 &q->head, &old, n, memory_order_release, memory_order_relaxed));
47
48 return old == NULL;
49}
50
51/* Return the entire chain and mark as empty */
52static inline struct mpsc_slist_node *mpsc_slist_drain(struct mpsc_slist *q) {
53 return atomic_exchange_explicit(&q->head, NULL, memory_order_acquire);
54}
55
56/* Reverse a detached chain to get the FIFO list order */
57static inline struct mpsc_slist_node *
58mpsc_slist_reverse(struct mpsc_slist_node *chain) {
59 struct mpsc_slist_node *prev = NULL;
60 while (chain) {
61 struct mpsc_slist_node *next = chain->next;
62 chain->next = prev;
63 prev = chain;
64 chain = next;
65 }
66 return prev;
67}
68
69/* Single consumer pop */
70static inline struct mpsc_slist_node *mpsc_slist_pop_one(struct mpsc_slist *q) {
71 struct mpsc_slist_node *old =
72 atomic_load_explicit(&q->head, memory_order_acquire);
73 while (old) {
74 if (atomic_compare_exchange_weak_explicit(&q->head, &old, old->next,
75 memory_order_acquire,
76 memory_order_acquire))
77 return old;
78 }
79 return NULL;
80}
81
82#define mpsc_slist_entry(ptr, type, member) container_of(ptr, type, member)
83
84/* Detached chain */
85#define mpsc_slist_for_each(pos, chain) \
86 for (pos = (chain); pos; pos = pos->next)
87
88#define mpsc_slist_for_each_safe(pos, n, chain) \
89 for (pos = (chain), n = (pos) ? (pos)->next : NULL; pos; \
90 pos = n, n = (pos) ? (pos)->next : NULL)
91
92#define mpsc_slist_for_each_entry(pos, chain, member) \
93 for (pos = (chain) ? mpsc_slist_entry((chain), typeof(*pos), member) \
94 : NULL; \
95 pos; \
96 pos = (pos)->member.next ? mpsc_slist_entry((pos)->member.next, \
97 typeof(*pos), member) \
98 : NULL)
99