1 /* $NetBSD: pslist.h,v 1.7 2019/12/01 15:28:19 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2016 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #ifndef _SYS_PSLIST_H
33 #define _SYS_PSLIST_H
34
35 #include <sys/param.h>
36 #include <sys/atomic.h>
37
38 struct pslist_head;
39 struct pslist_entry;
40
41 struct pslist_head {
42 struct pslist_entry *plh_first;
43 };
44
45 struct pslist_entry {
46 struct pslist_entry **ple_prevp;
47 struct pslist_entry *ple_next;
48 };
49
50 #ifdef _KERNEL
51 #define _PSLIST_ASSERT KASSERT
52 #else
53 #include <assert.h>
54 #define _PSLIST_ASSERT assert
55 #endif
56
57 #define _PSLIST_POISON ((void *)1ul)
58
59 /*
60 * Initialization. Allowed only when the caller has exclusive access,
61 * excluding writers and readers.
62 */
63
64 static __inline void
pslist_init(struct pslist_head * head)65 pslist_init(struct pslist_head *head)
66 {
67
68 head->plh_first = NULL; /* not yet published, so no atomic */
69 }
70
71 static __inline void
pslist_destroy(struct pslist_head * head __diagused)72 pslist_destroy(struct pslist_head *head __diagused)
73 {
74
75 _PSLIST_ASSERT(head->plh_first == NULL);
76 }
77
78 static __inline void
pslist_entry_init(struct pslist_entry * entry)79 pslist_entry_init(struct pslist_entry *entry)
80 {
81
82 entry->ple_next = NULL;
83 entry->ple_prevp = NULL;
84 }
85
86 static __inline void
pslist_entry_destroy(struct pslist_entry * entry)87 pslist_entry_destroy(struct pslist_entry *entry)
88 {
89
90 _PSLIST_ASSERT(entry->ple_prevp == NULL);
91
92 /*
93 * Poison the next entry. If we used NULL here, then readers
94 * would think they were simply at the end of the list.
95 * Instead, cause readers to crash.
96 */
97 atomic_store_relaxed(&entry->ple_next, _PSLIST_POISON);
98 }
99
100 /*
101 * Writer operations. Caller must exclude other writers, but not
102 * necessarily readers.
103 *
104 * Writes to initialize a new entry must precede its publication by
105 * writing to plh_first / ple_next / *ple_prevp.
106 *
107 * The ple_prevp field is serialized by the caller's exclusive lock and
108 * not read by readers, and hence its ordering relative to the internal
109 * memory barriers is inconsequential.
110 */
111
112 static __inline void
pslist_writer_insert_head(struct pslist_head * head,struct pslist_entry * new)113 pslist_writer_insert_head(struct pslist_head *head, struct pslist_entry *new)
114 {
115
116 _PSLIST_ASSERT(head->plh_first == NULL ||
117 head->plh_first->ple_prevp == &head->plh_first);
118 _PSLIST_ASSERT(new->ple_next == NULL);
119 _PSLIST_ASSERT(new->ple_prevp == NULL);
120
121 new->ple_prevp = &head->plh_first;
122 new->ple_next = head->plh_first; /* not yet published, so no atomic */
123 if (head->plh_first != NULL)
124 head->plh_first->ple_prevp = &new->ple_next;
125 atomic_store_release(&head->plh_first, new);
126 }
127
128 static __inline void
pslist_writer_insert_before(struct pslist_entry * entry,struct pslist_entry * new)129 pslist_writer_insert_before(struct pslist_entry *entry,
130 struct pslist_entry *new)
131 {
132
133 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
134 _PSLIST_ASSERT(entry->ple_prevp != NULL);
135 _PSLIST_ASSERT(*entry->ple_prevp == entry);
136 _PSLIST_ASSERT(new->ple_next == NULL);
137 _PSLIST_ASSERT(new->ple_prevp == NULL);
138
139 new->ple_prevp = entry->ple_prevp;
140 new->ple_next = entry; /* not yet published, so no atomic */
141
142 /*
143 * Pairs with atomic_load_consume in pslist_reader_first or
144 * pslist_reader_next.
145 */
146 atomic_store_release(entry->ple_prevp, new);
147
148 entry->ple_prevp = &new->ple_next;
149 }
150
151 static __inline void
pslist_writer_insert_after(struct pslist_entry * entry,struct pslist_entry * new)152 pslist_writer_insert_after(struct pslist_entry *entry,
153 struct pslist_entry *new)
154 {
155
156 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
157 _PSLIST_ASSERT(entry->ple_prevp != NULL);
158 _PSLIST_ASSERT(*entry->ple_prevp == entry);
159 _PSLIST_ASSERT(new->ple_next == NULL);
160 _PSLIST_ASSERT(new->ple_prevp == NULL);
161
162 new->ple_prevp = &entry->ple_next;
163 new->ple_next = entry->ple_next; /* not yet published, so no atomic */
164 if (new->ple_next != NULL)
165 new->ple_next->ple_prevp = &new->ple_next;
166
167 /* Pairs with atomic_load_consume in pslist_reader_next. */
168 atomic_store_release(&entry->ple_next, new);
169 }
170
171 static __inline void
pslist_writer_remove(struct pslist_entry * entry)172 pslist_writer_remove(struct pslist_entry *entry)
173 {
174
175 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
176 _PSLIST_ASSERT(entry->ple_prevp != NULL);
177 _PSLIST_ASSERT(*entry->ple_prevp == entry);
178
179 if (entry->ple_next != NULL)
180 entry->ple_next->ple_prevp = entry->ple_prevp;
181
182 /*
183 * No need for atomic_store_release because there's no
184 * initialization that this must happen after -- the store
185 * transitions from a good state with the entry to a good state
186 * without the entry, both of which are valid for readers to
187 * witness.
188 */
189 atomic_store_relaxed(entry->ple_prevp, entry->ple_next);
190 entry->ple_prevp = NULL;
191
192 /*
193 * Leave entry->ple_next intact so that any extant readers can
194 * continue iterating through the list. The caller must then
195 * wait for readers to drain, e.g. with pserialize_perform,
196 * before destroying and reusing the entry.
197 */
198 }
199
200 static __inline struct pslist_entry *
pslist_writer_first(const struct pslist_head * head)201 pslist_writer_first(const struct pslist_head *head)
202 {
203
204 return head->plh_first;
205 }
206
207 static __inline struct pslist_entry *
pslist_writer_next(const struct pslist_entry * entry)208 pslist_writer_next(const struct pslist_entry *entry)
209 {
210
211 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
212 return entry->ple_next;
213 }
214
215 static __inline void *
_pslist_writer_first_container(const struct pslist_head * head,const ptrdiff_t offset)216 _pslist_writer_first_container(const struct pslist_head *head,
217 const ptrdiff_t offset)
218 {
219 struct pslist_entry *first = head->plh_first;
220
221 return (first == NULL ? NULL : (char *)first - offset);
222 }
223
224 static __inline void *
_pslist_writer_next_container(const struct pslist_entry * entry,const ptrdiff_t offset)225 _pslist_writer_next_container(const struct pslist_entry *entry,
226 const ptrdiff_t offset)
227 {
228 struct pslist_entry *next = entry->ple_next;
229
230 _PSLIST_ASSERT(next != _PSLIST_POISON);
231 return (next == NULL ? NULL : (char *)next - offset);
232 }
233
234 /*
235 * Reader operations. Caller must block pserialize_perform or
236 * equivalent and be bound to a CPU. Only plh_first/ple_next may be
237 * read, and only with consuming memory order so that data-dependent
238 * loads happen afterward.
239 */
240
241 static __inline struct pslist_entry *
pslist_reader_first(const struct pslist_head * head)242 pslist_reader_first(const struct pslist_head *head)
243 {
244 /*
245 * Pairs with atomic_store_release in pslist_writer_insert_head
246 * or pslist_writer_insert_before.
247 */
248 return atomic_load_consume(&head->plh_first);
249 }
250
251 static __inline struct pslist_entry *
pslist_reader_next(const struct pslist_entry * entry)252 pslist_reader_next(const struct pslist_entry *entry)
253 {
254 /*
255 * Pairs with atomic_store_release in
256 * pslist_writer_insert_before or pslist_writer_insert_after.
257 */
258 struct pslist_entry *next = atomic_load_consume(&entry->ple_next);
259
260 _PSLIST_ASSERT(next != _PSLIST_POISON);
261
262 return next;
263 }
264
265 static __inline void *
_pslist_reader_first_container(const struct pslist_head * head,const ptrdiff_t offset)266 _pslist_reader_first_container(const struct pslist_head *head,
267 const ptrdiff_t offset)
268 {
269 struct pslist_entry *first = pslist_reader_first(head);
270
271 if (first == NULL)
272 return NULL;
273 return (char *)first - offset;
274 }
275
276 static __inline void *
_pslist_reader_next_container(const struct pslist_entry * entry,const ptrdiff_t offset)277 _pslist_reader_next_container(const struct pslist_entry *entry,
278 const ptrdiff_t offset)
279 {
280 struct pslist_entry *next = pslist_reader_next(entry);
281
282 if (next == NULL)
283 return NULL;
284 return (char *)next - offset;
285 }
286
287 /*
288 * Type-safe macros for convenience.
289 */
290
291 #if defined(__COVERITY__) || defined(__LGTM_BOT__)
292 #define _PSLIST_VALIDATE_PTRS(P, Q) 0
293 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) 0
294 #else
295 #define _PSLIST_VALIDATE_PTRS(P, Q) \
296 (0 * sizeof((P) - (Q)) * sizeof(*(P)) * sizeof(*(Q)))
297 #define _PSLIST_VALIDATE_CONTAINER(P, T, F) \
298 (0 * sizeof((P) - &((T *)(((char *)(P)) - offsetof(T, F)))->F))
299 #endif
300
301 #define PSLIST_INITIALIZER { .plh_first = NULL }
302 #define PSLIST_ENTRY_INITIALIZER { .ple_next = NULL, .ple_prevp = NULL }
303
304 #define PSLIST_INIT(H) pslist_init((H))
305 #define PSLIST_DESTROY(H) pslist_destroy((H))
306 #define PSLIST_ENTRY_INIT(E, F) pslist_entry_init(&(E)->F)
307 #define PSLIST_ENTRY_DESTROY(E, F) pslist_entry_destroy(&(E)->F)
308
309 #define PSLIST_WRITER_INSERT_HEAD(H, V, F) \
310 pslist_writer_insert_head((H), &(V)->F)
311 #define PSLIST_WRITER_INSERT_BEFORE(E, N, F) \
312 pslist_writer_insert_before(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \
313 &(N)->F)
314 #define PSLIST_WRITER_INSERT_AFTER(E, N, F) \
315 pslist_writer_insert_after(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \
316 &(N)->F)
317 #define PSLIST_WRITER_REMOVE(E, F) \
318 pslist_writer_remove(&(E)->F)
319 #define PSLIST_WRITER_FIRST(H, T, F) \
320 ((T *)(_pslist_writer_first_container((H), offsetof(T, F))) + \
321 _PSLIST_VALIDATE_CONTAINER(pslist_writer_first(H), T, F))
322 #define PSLIST_WRITER_NEXT(V, T, F) \
323 ((T *)(_pslist_writer_next_container(&(V)->F, offsetof(T, F))) + \
324 _PSLIST_VALIDATE_CONTAINER(pslist_writer_next(&(V)->F), T, F))
325 #define PSLIST_WRITER_FOREACH(V, H, T, F) \
326 for ((V) = PSLIST_WRITER_FIRST((H), T, F); \
327 (V) != NULL; \
328 (V) = PSLIST_WRITER_NEXT((V), T, F))
329
330 #define PSLIST_READER_FIRST(H, T, F) \
331 ((T *)(_pslist_reader_first_container((H), offsetof(T, F))) + \
332 _PSLIST_VALIDATE_CONTAINER(pslist_reader_first(H), T, F))
333 #define PSLIST_READER_NEXT(V, T, F) \
334 ((T *)(_pslist_reader_next_container(&(V)->F, offsetof(T, F))) + \
335 _PSLIST_VALIDATE_CONTAINER(pslist_reader_next(&(V)->F), T, F))
336 #define PSLIST_READER_FOREACH(V, H, T, F) \
337 for ((V) = PSLIST_READER_FIRST((H), T, F); \
338 (V) != NULL; \
339 (V) = PSLIST_READER_NEXT((V), T, F))
340
341 #endif /* _SYS_PSLIST_H */
342