1/* $NetBSD: pslist.h,v 1.4 2016/11/18 06:41:52 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
38struct pslist_head;
39struct pslist_entry;
40
41struct pslist_head {
42 struct pslist_entry *plh_first;
43};
44
45struct 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
64static inline void
65pslist_init(struct pslist_head *head)
66{
67
68 head->plh_first = NULL;
69}
70
71static inline void
72pslist_destroy(struct pslist_head *head __diagused)
73{
74
75 _PSLIST_ASSERT(head->plh_first == NULL);
76}
77
78static inline void
79pslist_entry_init(struct pslist_entry *entry)
80{
81
82 entry->ple_next = NULL;
83 entry->ple_prevp = NULL;
84}
85
86static inline void
87pslist_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 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
112static inline void
113pslist_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;
123 if (head->plh_first != NULL)
124 head->plh_first->ple_prevp = &new->ple_next;
125 membar_producer();
126 head->plh_first = new;
127}
128
129static inline void
130pslist_writer_insert_before(struct pslist_entry *entry,
131 struct pslist_entry *new)
132{
133
134 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
135 _PSLIST_ASSERT(entry->ple_prevp != NULL);
136 _PSLIST_ASSERT(*entry->ple_prevp == entry);
137 _PSLIST_ASSERT(new->ple_next == NULL);
138 _PSLIST_ASSERT(new->ple_prevp == NULL);
139
140 new->ple_prevp = entry->ple_prevp;
141 new->ple_next = entry;
142 membar_producer();
143 *entry->ple_prevp = new;
144 entry->ple_prevp = &new->ple_next;
145}
146
147static inline void
148pslist_writer_insert_after(struct pslist_entry *entry,
149 struct pslist_entry *new)
150{
151
152 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
153 _PSLIST_ASSERT(entry->ple_prevp != NULL);
154 _PSLIST_ASSERT(*entry->ple_prevp == entry);
155 _PSLIST_ASSERT(new->ple_next == NULL);
156 _PSLIST_ASSERT(new->ple_prevp == NULL);
157
158 new->ple_prevp = &entry->ple_next;
159 new->ple_next = entry->ple_next;
160 if (new->ple_next != NULL)
161 new->ple_next->ple_prevp = &new->ple_next;
162 membar_producer();
163 entry->ple_next = new;
164}
165
166static inline void
167pslist_writer_remove(struct pslist_entry *entry)
168{
169
170 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
171 _PSLIST_ASSERT(entry->ple_prevp != NULL);
172 _PSLIST_ASSERT(*entry->ple_prevp == entry);
173
174 if (entry->ple_next != NULL)
175 entry->ple_next->ple_prevp = entry->ple_prevp;
176 *entry->ple_prevp = entry->ple_next;
177 entry->ple_prevp = NULL;
178
179 /*
180 * Leave entry->ple_next intact so that any extant readers can
181 * continue iterating through the list. The caller must then
182 * wait for readers to drain, e.g. with pserialize_perform,
183 * before destroying and reusing the entry.
184 */
185}
186
187static inline struct pslist_entry *
188pslist_writer_first(const struct pslist_head *head)
189{
190
191 return head->plh_first;
192}
193
194static inline struct pslist_entry *
195pslist_writer_next(const struct pslist_entry *entry)
196{
197
198 _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON);
199 return entry->ple_next;
200}
201
202static inline void *
203_pslist_writer_first_container(const struct pslist_head *head,
204 const ptrdiff_t offset)
205{
206 struct pslist_entry *first = head->plh_first;
207
208 return (first == NULL ? NULL : (char *)first - offset);
209}
210
211static inline void *
212_pslist_writer_next_container(const struct pslist_entry *entry,
213 const ptrdiff_t offset)
214{
215 struct pslist_entry *next = entry->ple_next;
216
217 _PSLIST_ASSERT(next != _PSLIST_POISON);
218 return (next == NULL ? NULL : (char *)next - offset);
219}
220
221/*
222 * Reader operations. Caller must block pserialize_perform or
223 * equivalent and be bound to a CPU. Only plh_first/ple_next may be
224 * read, and after that, a membar_datadep_consumer must precede
225 * dereferencing the resulting pointer.
226 */
227
228static inline struct pslist_entry *
229pslist_reader_first(const struct pslist_head *head)
230{
231 struct pslist_entry *first = head->plh_first;
232
233 if (first != NULL)
234 membar_datadep_consumer();
235
236 return first;
237}
238
239static inline struct pslist_entry *
240pslist_reader_next(const struct pslist_entry *entry)
241{
242 struct pslist_entry *next = entry->ple_next;
243
244 _PSLIST_ASSERT(next != _PSLIST_POISON);
245 if (next != NULL)
246 membar_datadep_consumer();
247
248 return next;
249}
250
251static inline void *
252_pslist_reader_first_container(const struct pslist_head *head,
253 const ptrdiff_t offset)
254{
255 struct pslist_entry *first = head->plh_first;
256
257 if (first == NULL)
258 return NULL;
259 membar_datadep_consumer();
260
261 return (char *)first - offset;
262}
263
264static inline void *
265_pslist_reader_next_container(const struct pslist_entry *entry,
266 const ptrdiff_t offset)
267{
268 struct pslist_entry *next = entry->ple_next;
269
270 _PSLIST_ASSERT(next != _PSLIST_POISON);
271 if (next == NULL)
272 return NULL;
273 membar_datadep_consumer();
274
275 return (char *)next - offset;
276}
277
278/*
279 * Type-safe macros for convenience.
280 */
281
282#ifdef __COVERITY__
283#define _PSLIST_VALIDATE_PTRS(P, Q) 0
284#define _PSLIST_VALIDATE_CONTAINER(P, T, F) 0
285#else
286#define _PSLIST_VALIDATE_PTRS(P, Q) \
287 (0 * sizeof((P) - (Q)) * sizeof(*(P)) * sizeof(*(Q)))
288#define _PSLIST_VALIDATE_CONTAINER(P, T, F) \
289 (0 * sizeof((P) - &((T *)(((char *)(P)) - offsetof(T, F)))->F))
290#endif
291
292#define PSLIST_INITIALIZER { .plh_first = NULL }
293#define PSLIST_ENTRY_INITIALIZER { .ple_next = NULL, .ple_prevp = NULL }
294
295#define PSLIST_INIT(H) pslist_init((H))
296#define PSLIST_DESTROY(H) pslist_destroy((H))
297#define PSLIST_ENTRY_INIT(E, F) pslist_entry_init(&(E)->F)
298#define PSLIST_ENTRY_DESTROY(E, F) pslist_entry_destroy(&(E)->F)
299
300#define PSLIST_WRITER_INSERT_HEAD(H, V, F) \
301 pslist_writer_insert_head((H), &(V)->F)
302#define PSLIST_WRITER_INSERT_BEFORE(E, N, F) \
303 pslist_writer_insert_before(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \
304 &(N)->F)
305#define PSLIST_WRITER_INSERT_AFTER(E, N, F) \
306 pslist_writer_insert_after(&(E)->F + _PSLIST_VALIDATE_PTRS(E, N), \
307 &(N)->F)
308#define PSLIST_WRITER_REMOVE(E, F) \
309 pslist_writer_remove(&(E)->F)
310#define PSLIST_WRITER_FIRST(H, T, F) \
311 ((T *)(_pslist_writer_first_container((H), offsetof(T, F))) + \
312 _PSLIST_VALIDATE_CONTAINER(pslist_writer_first(H), T, F))
313#define PSLIST_WRITER_NEXT(V, T, F) \
314 ((T *)(_pslist_writer_next_container(&(V)->F, offsetof(T, F))) + \
315 _PSLIST_VALIDATE_CONTAINER(pslist_writer_next(&(V)->F), T, F))
316#define PSLIST_WRITER_FOREACH(V, H, T, F) \
317 for ((V) = PSLIST_WRITER_FIRST((H), T, F); \
318 (V) != NULL; \
319 (V) = PSLIST_WRITER_NEXT((V), T, F))
320
321#define PSLIST_READER_FIRST(H, T, F) \
322 ((T *)(_pslist_reader_first_container((H), offsetof(T, F))) + \
323 _PSLIST_VALIDATE_CONTAINER(pslist_reader_first(H), T, F))
324#define PSLIST_READER_NEXT(V, T, F) \
325 ((T *)(_pslist_reader_next_container(&(V)->F, offsetof(T, F))) + \
326 _PSLIST_VALIDATE_CONTAINER(pslist_reader_next(&(V)->F), T, F))
327#define PSLIST_READER_FOREACH(V, H, T, F) \
328 for ((V) = PSLIST_READER_FIRST((H), T, F); \
329 (V) != NULL; \
330 (V) = PSLIST_READER_NEXT((V), T, F))
331
332#endif /* _SYS_PSLIST_H */
333