1/* @title: Lockless MPMC LIFO list */
2#pragma once
3#include <atomic.h>
4#include <compiler/core.h>
5#include <container_of.h>
6#include <stdbool.h>
7#include <stddef.h>
8#include <stdint.h>
9#include <types/types.h>
10
11struct mpmc_lifo_list_node {
12 struct mpmc_lifo_list_node *next;
13};
14
15union mpmc_lifo_list_head {
16 struct {
17 struct mpmc_lifo_list_node *node;
18 uint64_t seq;
19 };
20 uint128_t raw;
21};
22
23struct mpmc_lifo_list {
24 atomic_uint128_t head;
25};
26
27#define MPMC_LIFO_LIST_INIT {.head = 0}
28#define MPMC_LIFO_LIST(name) struct mpmc_lifo_list name = MPMC_LIFO_LIST_INIT
29
30/* NOTE: my syntax highlighter breaks when I actually insert
31 * the keyword struct/union into the full versions, not sure why */
32ct_assert_union_size_eq(mpmc_lifo_list_head, 16);
33ct_assert_struct_size_eq(mpmc_lifo_list, 16);
34ct_assert_struct_align_eq(mpmc_lifo_list, 16);
35
36static inline bool mpmc_lifo_list_cas(struct mpmc_lifo_list *q,
37 union mpmc_lifo_list_head *expected,
38 union mpmc_lifo_list_head desired) {
39 return atomic_cas_strong(&q->head, &expected->raw, desired.raw, mo_acq_rel,
40 mo_acquire);
41}
42
43static inline union mpmc_lifo_list_head
44mpmc_lifo_list_load(const struct mpmc_lifo_list *q) {
45 return (union mpmc_lifo_list_head) {.raw = atomic_load_acq(&q->head)};
46}
47
48static inline void mpmc_lifo_list_init(struct mpmc_lifo_list *q) {
49 atomic_store_rlx(&q->head, 0);
50}
51
52static inline bool mpmc_lifo_list_empty(const struct mpmc_lifo_list *q) {
53 union mpmc_lifo_list_head h = mpmc_lifo_list_load(q);
54 return h.node == NULL;
55}
56
57static inline uint64_t mpmc_lifo_list_seq(const struct mpmc_lifo_list *q) {
58 union mpmc_lifo_list_head h = mpmc_lifo_list_load(q);
59 return h.seq;
60}
61
62static inline struct mpmc_lifo_list_node *
63mpmc_lifo_list_peek(const struct mpmc_lifo_list *q) {
64 union mpmc_lifo_list_head h = mpmc_lifo_list_load(q);
65 return h.node;
66}
67
68/* true if list was previously empty */
69static inline bool mpmc_lifo_list_push(struct mpmc_lifo_list *q,
70 struct mpmc_lifo_list_node *n) {
71 union mpmc_lifo_list_head old = mpmc_lifo_list_load(q);
72 union mpmc_lifo_list_head new_head;
73
74 do {
75 n->next = old.node;
76 new_head.node = n;
77 new_head.seq = old.seq + 1;
78 } while (!mpmc_lifo_list_cas(q, expected: &old, desired: new_head));
79
80 return old.node == NULL;
81}
82
83/* Push a chain [first ... last] */
84static inline bool mpmc_lifo_list_push_chain(struct mpmc_lifo_list *q,
85 struct mpmc_lifo_list_node *first,
86 struct mpmc_lifo_list_node *last) {
87 union mpmc_lifo_list_head old = mpmc_lifo_list_load(q);
88 union mpmc_lifo_list_head new_head;
89
90 do {
91 last->next = old.node;
92 new_head.node = first;
93 new_head.seq = old.seq + 1;
94 } while (!mpmc_lifo_list_cas(q, expected: &old, desired: new_head));
95
96 return old.node == NULL;
97}
98
99/* MC pop one node in LIFO order */
100static inline struct mpmc_lifo_list_node *
101mpmc_lifo_list_pop(struct mpmc_lifo_list *q) {
102 union mpmc_lifo_list_head old = mpmc_lifo_list_load(q);
103 union mpmc_lifo_list_head new_head;
104
105 while (old.node != NULL) {
106 new_head.node = ca_read_once(old.node->next);
107 new_head.seq = old.seq + 1;
108
109 if (mpmc_lifo_list_cas(q, expected: &old, desired: new_head))
110 return old.node;
111 }
112
113 return NULL;
114}
115
116/* Return entire chain and mark empty */
117static inline struct mpmc_lifo_list_node *
118mpmc_lifo_list_drain(struct mpmc_lifo_list *q) {
119 union mpmc_lifo_list_head old = mpmc_lifo_list_load(q);
120 union mpmc_lifo_list_head new_head;
121
122 while (old.node != NULL) {
123 new_head.node = NULL;
124 new_head.seq = old.seq + 1;
125
126 if (mpmc_lifo_list_cas(q, expected: &old, desired: new_head))
127 return old.node;
128 }
129
130 return NULL;
131}
132
133/* Get the FIFO order */
134static inline struct mpmc_lifo_list_node *
135mpmc_lifo_list_reverse(struct mpmc_lifo_list_node *chain) {
136 struct mpmc_lifo_list_node *prev = NULL;
137 while (chain) {
138 struct mpmc_lifo_list_node *next = chain->next;
139 chain->next = prev;
140 prev = chain;
141 chain = next;
142 }
143 return prev;
144}
145
146#define mpmc_lifo_list_entry(ptr, type, member) container_of(ptr, type, member)
147
148#define mpmc_lifo_list_for_each(pos, chain) \
149 for (pos = (chain); pos; pos = pos->next)
150
151#define mpmc_lifo_list_for_each_safe(pos, n, chain) \
152 for (pos = (chain), n = (pos) ? (pos)->next : NULL; pos; \
153 pos = n, n = (pos) ? (pos)->next : NULL)
154
155#define mpmc_lifo_list_for_each_entry(pos, chain, member) \
156 for (pos = (chain) ? mpmc_lifo_list_entry((chain), typeof(*pos), member) \
157 : NULL; \
158 pos; \
159 pos = (pos)->member.next ? mpmc_lifo_list_entry((pos)->member.next, \
160 typeof(*pos), member) \
161 : NULL)
162
163#define mpmc_lifo_list_for_each_entry_safe(pos, n, chain, member) \
164 for (pos = (chain) ? mpmc_lifo_list_entry((chain), typeof(*pos), member) \
165 : NULL, \
166 n = (pos && (pos)->member.next) \
167 ? mpmc_lifo_list_entry((pos)->member.next, typeof(*pos), \
168 member) \
169 : NULL; \
170 pos; pos = n, n = (pos && (pos)->member.next) \
171 ? mpmc_lifo_list_entry((pos)->member.next, \
172 typeof(*pos), member) \
173 : NULL)
174