1/* $OpenBSD: smr.h,v 1.9 2022/07/25 08:06:44 visa Exp $ */
2
3/*
4 * Copyright (c) 2019 Visa Hankala
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19#ifndef _SYS_SMR_H_
20#define _SYS_SMR_H_
21
22#include <sys/queue.h>
23
24struct smr_entry {
25 SIMPLEQ_ENTRY(smr_entry) smr_list;
26 void (*smr_func)(void *);
27 void *smr_arg;
28};
29
30SIMPLEQ_HEAD(smr_entry_list, smr_entry);
31
32#ifdef _KERNEL
33
34#include <sys/atomic.h>
35
36void smr_startup(void);
37void smr_startup_thread(void);
38void smr_idle(void);
39void smr_read_enter(void);
40void smr_read_leave(void);
41
42void smr_call_impl(struct smr_entry *, void (*)(void *), void *, int);
43void smr_barrier_impl(int);
44
45#define smr_call(entry, func, arg) smr_call_impl(entry, func, arg, 0)
46#define smr_barrier() smr_barrier_impl(0)
47#define smr_flush() smr_barrier_impl(1)
48
49static inline void
50smr_init(struct smr_entry *smr)
51{
52 smr->smr_func = NULL;
53 smr->smr_arg = NULL;
54}
55
56#ifdef DIAGNOSTIC
57#define SMR_ASSERT_CRITICAL() do { \
58 if (panicstr == NULL && !db_active) \
59 KASSERT(curcpu()->ci_schedstate.spc_smrdepth > 0); \
60} while (0)
61#define SMR_ASSERT_NONCRITICAL() do { \
62 if (panicstr == NULL && !db_active) \
63 KASSERT(curcpu()->ci_schedstate.spc_smrdepth == 0); \
64} while (0)
65#else
66#define SMR_ASSERT_CRITICAL() do {} while (0)
67#define SMR_ASSERT_NONCRITICAL() do {} while (0)
68#endif
69
70#endif /* _KERNEL */
71
72#define SMR_PTR_GET(pptr) READ_ONCE(*pptr)
73
74#define SMR_PTR_GET_LOCKED(pptr) (*(pptr))
75
76#define SMR_PTR_SET_LOCKED(pptr, val) do { \
77 membar_producer(); \
78 WRITE_ONCE(*pptr, val); \
79} while (0)
80
81/*
82 * List implementations for use with safe memory reclamation.
83 */
84
85/*
86 * Copyright (c) 1991, 1993
87 * The Regents of the University of California. All rights reserved.
88 *
89 * Redistribution and use in source and binary forms, with or without
90 * modification, are permitted provided that the following conditions
91 * are met:
92 * 1. Redistributions of source code must retain the above copyright
93 * notice, this list of conditions and the following disclaimer.
94 * 2. Redistributions in binary form must reproduce the above copyright
95 * notice, this list of conditions and the following disclaimer in the
96 * documentation and/or other materials provided with the distribution.
97 * 3. Neither the name of the University nor the names of its contributors
98 * may be used to endorse or promote products derived from this software
99 * without specific prior written permission.
100 *
101 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
102 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
103 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
104 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
105 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
106 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
107 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
108 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
109 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
110 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
111 * SUCH DAMAGE.
112 *
113 * @(#)queue.h 8.5 (Berkeley) 8/20/94
114 */
115
116#include <sys/_null.h>
117
118/*
119 * This file defines three types of data structures: singly-linked lists,
120 * lists, and tail queues.
121 *
122 *
123 * A singly-linked list is headed by a single forward pointer. The elements
124 * are singly linked for minimum space and pointer manipulation overhead at
125 * the expense of O(n) removal for arbitrary elements. New elements can be
126 * added to the list after an existing element or at the head of the list.
127 * Elements being removed from the head of the list should use the explicit
128 * macro for this purpose for optimum efficiency. A singly-linked list may
129 * only be traversed in the forward direction. Singly-linked lists are ideal
130 * for applications with large datasets and few or no removals or for
131 * implementing a LIFO queue.
132 *
133 * A list is headed by a single forward pointer (or an array of forward
134 * pointers for a hash table header). The elements are doubly linked
135 * so that an arbitrary element can be removed without a need to
136 * traverse the list. New elements can be added to the list before
137 * or after an existing element or at the head of the list. A list
138 * may only be traversed in the forward direction.
139 *
140 * A tail queue is headed by a pair of pointers, one to the head of the
141 * list and the other to the tail of the list. The elements are doubly
142 * linked so that an arbitrary element can be removed without a need to
143 * traverse the list. New elements can be added to the list before or
144 * after an existing element, at the head of the list, or at the end of
145 * the list. A tail queue may only be traversed in the forward direction
146 * by lock-free readers.
147 */
148
149/*
150 * Singly-linked List definitions.
151 */
152#define SMR_SLIST_HEAD(name, type) \
153struct name { \
154 struct type *smr_slh_first; /* first element, SMR-protected */\
155}
156
157#define SMR_SLIST_HEAD_INITIALIZER(head) \
158 { .smr_slh_first = NULL }
159
160#define SMR_SLIST_ENTRY(type) \
161struct { \
162 struct type *smr_sle_next; /* next element, SMR-protected */\
163}
164
165/*
166 * Singly-linked List access methods.
167 */
168#define SMR_SLIST_END(head) NULL
169
170#define SMR_SLIST_FIRST(head) \
171 SMR_PTR_GET(&(head)->smr_slh_first)
172#define SMR_SLIST_NEXT(elm, field) \
173 SMR_PTR_GET(&(elm)->field.smr_sle_next)
174
175#define SMR_SLIST_FIRST_LOCKED(head) \
176 SMR_PTR_GET_LOCKED(&(head)->smr_slh_first)
177#define SMR_SLIST_EMPTY_LOCKED(head) \
178 (SMR_SLIST_FIRST_LOCKED(head) == SMR_SLIST_END(head))
179#define SMR_SLIST_NEXT_LOCKED(elm, field) \
180 SMR_PTR_GET_LOCKED(&(elm)->field.smr_sle_next)
181
182#define SMR_SLIST_FOREACH(var, head, field) \
183 for ((var) = SMR_SLIST_FIRST(head); \
184 (var) != SMR_SLIST_END(head); \
185 (var) = SMR_SLIST_NEXT(var, field))
186
187#define SMR_SLIST_FOREACH_LOCKED(var, head, field) \
188 for ((var) = SMR_SLIST_FIRST_LOCKED(head); \
189 (var) != SMR_SLIST_END(head); \
190 (var) = SMR_SLIST_NEXT_LOCKED(var, field))
191
192#define SMR_SLIST_FOREACH_SAFE_LOCKED(var, head, field, tvar) \
193 for ((var) = SMR_SLIST_FIRST_LOCKED(head); \
194 (var) && ((tvar) = SMR_SLIST_NEXT_LOCKED(var, field), 1); \
195 (var) = (tvar))
196
197/*
198 * Singly-linked List functions.
199 */
200#define SMR_SLIST_INIT(head) do { \
201 (head)->smr_slh_first = SMR_SLIST_END(head); \
202} while (0)
203
204#define SMR_SLIST_INSERT_AFTER_LOCKED(slistelm, elm, field) do { \
205 (elm)->field.smr_sle_next = (slistelm)->field.smr_sle_next; \
206 membar_producer(); \
207 (slistelm)->field.smr_sle_next = (elm); \
208} while (0)
209
210#define SMR_SLIST_INSERT_HEAD_LOCKED(head, elm, field) do { \
211 (elm)->field.smr_sle_next = (head)->smr_slh_first; \
212 membar_producer(); \
213 (head)->smr_slh_first = (elm); \
214} while (0)
215
216#define SMR_SLIST_REMOVE_AFTER_LOCKED(elm, field) do { \
217 (elm)->field.smr_sle_next = \
218 (elm)->field.smr_sle_next->field.smr_sle_next; \
219} while (0)
220
221#define SMR_SLIST_REMOVE_HEAD_LOCKED(head, field) do { \
222 (head)->smr_slh_first = (head)->smr_slh_first->field.smr_sle_next;\
223} while (0)
224
225#define SMR_SLIST_REMOVE_LOCKED(head, elm, type, field) do { \
226 if ((head)->smr_slh_first == (elm)) { \
227 SMR_SLIST_REMOVE_HEAD_LOCKED((head), field); \
228 } else { \
229 struct type *curelm = (head)->smr_slh_first; \
230 \
231 while (curelm->field.smr_sle_next != (elm)) \
232 curelm = curelm->field.smr_sle_next; \
233 curelm->field.smr_sle_next = \
234 curelm->field.smr_sle_next->field.smr_sle_next; \
235 } \
236 /* (elm)->field.smr_sle_next must be left intact to allow \
237 * any concurrent readers to proceed iteration. */ \
238} while (0)
239
240/*
241 * List definitions.
242 */
243#define SMR_LIST_HEAD(name, type) \
244struct name { \
245 struct type *smr_lh_first; /* first element, SMR-protected */\
246}
247
248#define SMR_LIST_HEAD_INITIALIZER(head) \
249 { .smr_lh_first = NULL }
250
251#define SMR_LIST_ENTRY(type) \
252struct { \
253 struct type *smr_le_next; /* next element, SMR-protected */\
254 struct type **smr_le_prev; /* address of previous next element */\
255}
256
257/*
258 * List access methods.
259 */
260#define SMR_LIST_END(head) NULL
261
262#define SMR_LIST_FIRST(head) \
263 SMR_PTR_GET(&(head)->smr_lh_first)
264#define SMR_LIST_NEXT(elm, field) \
265 SMR_PTR_GET(&(elm)->field.smr_le_next)
266
267#define SMR_LIST_FIRST_LOCKED(head) ((head)->smr_lh_first)
268#define SMR_LIST_NEXT_LOCKED(elm, field) ((elm)->field.smr_le_next)
269#define SMR_LIST_EMPTY_LOCKED(head) \
270 (SMR_LIST_FIRST_LOCKED(head) == SMR_LIST_END(head))
271
272#define SMR_LIST_FOREACH(var, head, field) \
273 for((var) = SMR_LIST_FIRST(head); \
274 (var)!= SMR_LIST_END(head); \
275 (var) = SMR_LIST_NEXT(var, field))
276
277#define SMR_LIST_FOREACH_LOCKED(var, head, field) \
278 for((var) = SMR_LIST_FIRST_LOCKED(head); \
279 (var)!= SMR_LIST_END(head); \
280 (var) = SMR_LIST_NEXT_LOCKED(var, field))
281
282#define SMR_LIST_FOREACH_SAFE_LOCKED(var, head, field, tvar) \
283 for ((var) = SMR_LIST_FIRST_LOCKED(head); \
284 (var) && ((tvar) = SMR_LIST_NEXT_LOCKED(var, field), 1); \
285 (var) = (tvar))
286
287/*
288 * List functions.
289 */
290#define SMR_LIST_INIT(head) do { \
291 (head)->smr_lh_first = SMR_LIST_END(head); \
292} while (0)
293
294#define SMR_LIST_INSERT_AFTER_LOCKED(listelm, elm, field) do { \
295 (elm)->field.smr_le_next = (listelm)->field.smr_le_next; \
296 if ((listelm)->field.smr_le_next != NULL) \
297 (listelm)->field.smr_le_next->field.smr_le_prev = \
298 &(elm)->field.smr_le_next; \
299 (elm)->field.smr_le_prev = &(listelm)->field.smr_le_next; \
300 membar_producer(); \
301 (listelm)->field.smr_le_next = (elm); \
302} while (0)
303
304#define SMR_LIST_INSERT_BEFORE_LOCKED(listelm, elm, field) do { \
305 (elm)->field.smr_le_prev = (listelm)->field.smr_le_prev; \
306 (elm)->field.smr_le_next = (listelm); \
307 membar_producer(); \
308 *(listelm)->field.smr_le_prev = (elm); \
309 (listelm)->field.smr_le_prev = &(elm)->field.smr_le_next; \
310} while (0)
311
312#define SMR_LIST_INSERT_HEAD_LOCKED(head, elm, field) do { \
313 (elm)->field.smr_le_next = (head)->smr_lh_first; \
314 (elm)->field.smr_le_prev = &(head)->smr_lh_first; \
315 if ((head)->smr_lh_first != NULL) \
316 (head)->smr_lh_first->field.smr_le_prev = \
317 &(elm)->field.smr_le_next; \
318 membar_producer(); \
319 (head)->smr_lh_first = (elm); \
320} while (0)
321
322#define SMR_LIST_REMOVE_LOCKED(elm, field) do { \
323 if ((elm)->field.smr_le_next != NULL) \
324 (elm)->field.smr_le_next->field.smr_le_prev = \
325 (elm)->field.smr_le_prev; \
326 *(elm)->field.smr_le_prev = (elm)->field.smr_le_next; \
327 /* (elm)->field.smr_le_next must be left intact to allow \
328 * any concurrent readers to proceed iteration. */ \
329} while (0)
330
331/*
332 * Tail queue definitions.
333 */
334#define SMR_TAILQ_HEAD(name, type) \
335struct name { \
336 struct type *smr_tqh_first; /* first element, SMR-protected */\
337 struct type **smr_tqh_last; /* last element */ \
338}
339
340#define SMR_TAILQ_HEAD_INITIALIZER(head) \
341 { .smr_tqh_first = NULL, .smr_tqh_last = &(head).smr_tqh_first }
342
343#define SMR_TAILQ_ENTRY(type) \
344struct { \
345 struct type *smr_tqe_next; /* next element, SMR-protected */\
346 struct type **smr_tqe_prev; /* address of previous next element */\
347}
348
349/*
350 * Tail queue access methods.
351 */
352#define SMR_TAILQ_END(head) NULL
353
354#define SMR_TAILQ_FIRST(head) \
355 SMR_PTR_GET(&(head)->smr_tqh_first)
356#define SMR_TAILQ_NEXT(elm, field) \
357 SMR_PTR_GET(&(elm)->field.smr_tqe_next)
358
359#define SMR_TAILQ_FIRST_LOCKED(head) ((head)->smr_tqh_first)
360#define SMR_TAILQ_NEXT_LOCKED(elm, field) ((elm)->field.smr_tqe_next)
361#define SMR_TAILQ_LAST_LOCKED(head, headname) \
362 (*(((struct headname *)((head)->smr_tqh_last))->smr_tqh_last))
363#define SMR_TAILQ_EMPTY_LOCKED(head) \
364 (SMR_TAILQ_FIRST_LOCKED(head) == SMR_TAILQ_END(head))
365
366#define SMR_TAILQ_FOREACH(var, head, field) \
367 for((var) = SMR_TAILQ_FIRST(head); \
368 (var)!= SMR_TAILQ_END(head); \
369 (var) = SMR_TAILQ_NEXT(var, field))
370
371#define SMR_TAILQ_FOREACH_LOCKED(var, head, field) \
372 for((var) = SMR_TAILQ_FIRST_LOCKED(head); \
373 (var)!= SMR_TAILQ_END(head); \
374 (var) = SMR_TAILQ_NEXT_LOCKED(var, field))
375
376#define SMR_TAILQ_FOREACH_SAFE_LOCKED(var, head, field, tvar) \
377 for ((var) = SMR_TAILQ_FIRST_LOCKED(head); \
378 (var) && ((tvar) = SMR_TAILQ_NEXT_LOCKED(var, field), 1); \
379 (var) = (tvar))
380
381/*
382 * Tail queue functions.
383 */
384#define SMR_TAILQ_INIT(head) do { \
385 (head)->smr_tqh_first = SMR_TAILQ_END(head); \
386 (head)->smr_tqh_last = &(head)->smr_tqh_first; \
387} while (0)
388
389#define SMR_TAILQ_INSERT_AFTER_LOCKED(head, listelm, elm, field) do { \
390 (elm)->field.smr_tqe_next = (listelm)->field.smr_tqe_next; \
391 if ((listelm)->field.smr_tqe_next != NULL) \
392 (listelm)->field.smr_tqe_next->field.smr_tqe_prev = \
393 &(elm)->field.smr_tqe_next; \
394 else \
395 (head)->smr_tqh_last = &(elm)->field.smr_tqe_next; \
396 (elm)->field.smr_tqe_prev = &(listelm)->field.smr_tqe_next; \
397 membar_producer(); \
398 (listelm)->field.smr_tqe_next = (elm); \
399} while (0)
400
401#define SMR_TAILQ_INSERT_BEFORE_LOCKED(listelm, elm, field) do { \
402 (elm)->field.smr_tqe_prev = (listelm)->field.smr_tqe_prev; \
403 (elm)->field.smr_tqe_next = (listelm); \
404 membar_producer(); \
405 *(listelm)->field.smr_tqe_prev = (elm); \
406 (listelm)->field.smr_tqe_prev = &(elm)->field.smr_tqe_next; \
407} while (0)
408
409#define SMR_TAILQ_INSERT_HEAD_LOCKED(head, elm, field) do { \
410 (elm)->field.smr_tqe_next = (head)->smr_tqh_first; \
411 (elm)->field.smr_tqe_prev = &(head)->smr_tqh_first; \
412 if ((head)->smr_tqh_first != NULL) \
413 (head)->smr_tqh_first->field.smr_tqe_prev = \
414 &(elm)->field.smr_tqe_next; \
415 else \
416 (head)->smr_tqh_last = &(elm)->field.smr_tqe_next; \
417 membar_producer(); \
418 (head)->smr_tqh_first = (elm); \
419} while (0)
420
421#define SMR_TAILQ_INSERT_TAIL_LOCKED(head, elm, field) do { \
422 (elm)->field.smr_tqe_next = NULL; \
423 (elm)->field.smr_tqe_prev = (head)->smr_tqh_last; \
424 membar_producer(); \
425 *(head)->smr_tqh_last = (elm); \
426 (head)->smr_tqh_last = &(elm)->field.smr_tqe_next; \
427} while (0)
428
429#define SMR_TAILQ_REMOVE_LOCKED(head, elm, field) do { \
430 if ((elm)->field.smr_tqe_next != NULL) \
431 (elm)->field.smr_tqe_next->field.smr_tqe_prev = \
432 (elm)->field.smr_tqe_prev; \
433 else \
434 (head)->smr_tqh_last = (elm)->field.smr_tqe_prev; \
435 *(elm)->field.smr_tqe_prev = (elm)->field.smr_tqe_next; \
436 /* (elm)->field.smr_tqe_next must be left intact to allow \
437 * any concurrent readers to proceed iteration. */ \
438} while (0)
439
440#endif /* !_SYS_SMR_ */