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 | |
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 |
65 | pslist_init(struct pslist_head *head) |
66 | { |
67 | |
68 | head->plh_first = NULL; |
69 | } |
70 | |
71 | static inline void |
72 | pslist_destroy(struct pslist_head *head __diagused) |
73 | { |
74 | |
75 | _PSLIST_ASSERT(head->plh_first == NULL); |
76 | } |
77 | |
78 | static inline void |
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 |
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 | 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 |
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; |
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 | |
129 | static inline void |
130 | pslist_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 | |
147 | static inline void |
148 | pslist_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 | |
166 | static inline void |
167 | pslist_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 | |
187 | static inline struct pslist_entry * |
188 | pslist_writer_first(const struct pslist_head *head) |
189 | { |
190 | |
191 | return head->plh_first; |
192 | } |
193 | |
194 | static inline struct pslist_entry * |
195 | pslist_writer_next(const struct pslist_entry *entry) |
196 | { |
197 | |
198 | _PSLIST_ASSERT(entry->ple_next != _PSLIST_POISON); |
199 | return entry->ple_next; |
200 | } |
201 | |
202 | static 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 | |
211 | static 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 | |
228 | static inline struct pslist_entry * |
229 | pslist_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 | |
239 | static inline struct pslist_entry * |
240 | pslist_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 | |
251 | static 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 | |
264 | static 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 | |