1 /*
2 * Copyright (c) 2021-2022 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #ifndef _KERN_SMR_H_
30 #define _KERN_SMR_H_
31
32 #include <sys/cdefs.h>
33 #include <stdbool.h>
34 #include <stdint.h>
35 #include <kern/assert.h>
36 #include <kern/debug.h>
37 #include <kern/smr_types.h>
38 #include <os/atomic_private.h>
39 #if XNU_KERNEL_PRIVATE
40 #include <kern/startup.h>
41 #endif
42
43 __BEGIN_DECLS
44
45 #pragma mark SMR pointers
46
47 /*
48 * SMR Accessors are meant to provide safe access to SMR protected
49 * pointers and prevent misuse and accidental access.
50 *
51 * Accessors are grouped by type:
52 * entered - Use while in a read section (between smr_enter/smr_leave())
53 * serialized - Use while holding a lock that serializes writers.
54 * Updates are synchronized with readers via included barriers.
55 * unserialized - Use after the memory is out of scope and not visible to
56 * readers.
57 *
58 * All acceses include a parameter for an assert to verify the required
59 * synchronization.
60 */
61
62
63 /*!
64 * @macro smr_unsafe_load()
65 *
66 * @brief
67 * Read from an SMR protected pointer without any synchronization.
68 *
69 * @discussion
70 * This returns an integer on purpose as dereference is generally unsafe.
71 */
72 #define smr_unsafe_load(ptr) \
73 ({ (uintptr_t)((ptr)->__smr_ptr); })
74
75 /*!
76 * @macro smr_entered_load()
77 *
78 * @brief
79 * Read from an SMR protected pointer while in a read section.
80 */
81 #define smr_entered_load(ptr) \
82 ({ (ptr)->__smr_ptr; })
83
84 /*!
85 * @macro smr_entered_load_assert()
86 *
87 * @brief
88 * Read from an SMR protected pointer while in a read section.
89 */
90 #define smr_entered_load_assert(ptr, smr) ({ \
91 assert(smr_entered(smr)); \
92 (ptr)->__smr_ptr; \
93 })
94
95 /*!
96 * @macro smr_entered_load_acquire()
97 *
98 * @brief
99 * Read from an SMR protected pointer while in a read section (with acquire
100 * fence).
101 */
102 #define smr_entered_load_acquire(ptr) \
103 os_atomic_load(&(ptr)->__smr_ptr, acquire)
104
105 /*!
106 * @macro smr_entered_load_acquire_assert()
107 *
108 * @brief
109 * Read from an SMR protected pointer while in a read section.
110 */
111 #define smr_entered_load_acquire_assert(ptr, smr) ({ \
112 assert(smr_entered(smr)); \
113 os_atomic_load(&(ptr)->__smr_ptr, acquire); \
114 })
115
116 /*!
117 * @macro smr_serialized_load_assert()
118 *
119 * @brief
120 * Read from an SMR protected pointer while serialized by an
121 * external mechanism.
122 */
123 #define smr_serialized_load_assert(ptr, held_cond) ({ \
124 assertf(held_cond, "smr_serialized_load: lock not held"); \
125 (ptr)->__smr_ptr; \
126 })
127
128 /*!
129 * @macro smr_serialized_load()
130 *
131 * @brief
132 * Read from an SMR protected pointer while serialized by an
133 * external mechanism.
134 */
135 #define smr_serialized_load(ptr) \
136 smr_serialized_load_assert(ptr, true)
137
138 /*!
139 * @macro smr_init_store()
140 *
141 * @brief
142 * Store @c value to an SMR protected pointer during initialization.
143 */
144 #define smr_init_store(ptr, value) \
145 ({ (ptr)->__smr_ptr = value; })
146
147 /*!
148 * @macro smr_clear_store()
149 *
150 * @brief
151 * Clear (sets to 0) an SMR protected pointer (this is always "allowed" to do).
152 */
153 #define smr_clear_store(ptr) \
154 smr_init_store(ptr, 0)
155
156 /*!
157 * @macro smr_serialized_store_assert()
158 *
159 * @brief
160 * Store @c value to an SMR protected pointer while serialized by an
161 * external mechanism.
162 *
163 * @discussion
164 * Writers that are serialized with mutual exclusion or on a single
165 * thread should use smr_serialized_store() rather than swap.
166 */
167 #define smr_serialized_store_assert(ptr, value, held_cond) ({ \
168 assertf(held_cond, "smr_serialized_store: lock not held"); \
169 os_atomic_thread_fence(release); \
170 (ptr)->__smr_ptr = value; \
171 })
172
173 /*!
174 * @macro smr_serialized_store()
175 *
176 * @brief
177 * Store @c value to an SMR protected pointer while serialized by an
178 * external mechanism.
179 *
180 * @discussion
181 * Writers that are serialized with mutual exclusion or on a single
182 * thread should use smr_serialized_store() rather than swap.
183 */
184 #define smr_serialized_store(ptr, value) \
185 smr_serialized_store_assert(ptr, value, true)
186
187 /*!
188 * @macro smr_serialized_store_relaxed_assert()
189 *
190 * @brief
191 * Store @c value to an SMR protected pointer while serialized by an
192 * external mechanism.
193 *
194 * @discussion
195 * This function can be used when storing a value that was already
196 * previously stored with smr_serialized_store() (for example during
197 * a linked list removal).
198 */
199 #define smr_serialized_store_relaxed_assert(ptr, value, held_cond) ({ \
200 assertf(held_cond, "smr_serialized_store_relaxed: lock not held"); \
201 (ptr)->__smr_ptr = value; \
202 })
203
204 /*!
205 * @macro smr_serialized_store_relaxed()
206 *
207 * @brief
208 * Store @c value to an SMR protected pointer while serialized by an
209 * external mechanism.
210 *
211 * @discussion
212 * This function can be used when storing a value that was already
213 * previously stored with smr_serialized_store() (for example during
214 * a linked list removal).
215 */
216 #define smr_serialized_store_relaxed(ptr, value) \
217 smr_serialized_store_relaxed_assert(ptr, value, true)
218
219 /*!
220 * @macro smr_serialized_swap_assert()
221 *
222 * @brief
223 * Swap @c value with an SMR protected pointer and return the old value
224 * while serialized by an external mechanism.
225 *
226 * @discussion
227 * Swap permits multiple writers to update a pointer concurrently.
228 */
229 #define smr_serialized_swap_assert(ptr, value, held_cond) ({ \
230 assertf(held_cond, "smr_serialized_store: lock not held"); \
231 os_atomic_xchg(&(ptr)->__smr_ptr, value, release); \
232 })
233
234 /*!
235 * @macro smr_serialized_swap()
236 *
237 * @brief
238 * Swap @c value with an SMR protected pointer and return the old value
239 * while serialized by an external mechanism.
240 *
241 * @discussion
242 * Swap permits multiple writers to update a pointer concurrently.
243 */
244 #define smr_serialized_swap(ptr, value) \
245 smr_serialized_swap_assert(ptr, value, true)
246
247 /*!
248 * @macro smr_unserialized_load()
249 *
250 * @brief.
251 * Read from an SMR protected pointer when no serialization is required
252 * such as in the destructor callback or when the caller guarantees other
253 * synchronization.
254 */
255 #define smr_unserialized_load(ptr) \
256 ({ (ptr)->__smr_ptr; })
257
258 /*!
259 * @macro smr_unserialized_store()
260 *
261 * @brief.
262 * Store to an SMR protected pointer when no serialiation is required
263 * such as in the destructor callback or when the caller guarantees other
264 * synchronization.
265 */
266 #define smr_unserialized_store(ptr, value) \
267 ({ (ptr)->__smr_ptr = value; })
268
269
270 #pragma mark SMR queues
271
272 /*
273 * SMR queues are queues that are meant to be read under SMR critical sections
274 * concurrently with possible updates to the queue.
275 *
276 * /!\ Such read operations CAN ONLY BE PERFORMED IN FORWARD DIRECTION. /!\
277 *
278 * Queues can be either:
279 * - lists where the head is a single pointer,
280 * and insertions can only be at the head;
281 * - tail queues where the head is two pointers,
282 * and insertions can be either at the head or the tail.
283 *
284 * Queue linkages can either be single forward pointer linkages or double
285 * forward/backward linkages. The latter supports O(1) deletion.
286 *
287 *
288 * The entire API surface uses type inference for the implementations,
289 * which allows to relatively easily change between the 4 types of queues
290 * with very minimal API changes (mostly the types of list heads and fields).
291 */
292
293
294 /*!
295 * @macro smrq_init
296 *
297 * @brief
298 * Initializes an SMR queue head.
299 */
300 #define smrq_init(head) ({ \
301 __auto_type __head = (head); \
302 \
303 smr_init_store(&__head->first, NULL); \
304 if (__smrq_lastp(__head)) { \
305 *__smrq_lastp(__head) = &__head->first; \
306 } \
307 })
308
309
310 /*!
311 * @macro smrq_empty
312 *
313 * @brief
314 * Returns whether an SMR queue is empty, can be called from any context.
315 */
316 #define smrq_empty(head) \
317 (smr_unsafe_load(&(head)->first) == 0)
318
319
320 /*!
321 * @macro smrq_entered_first
322 *
323 * @brief
324 * Returns the first element of an SMR queue, while in a read section.
325 */
326 #define smrq_entered_first(head, type_t, field) \
327 __container_of_safe(smr_entered_load(&(head)->first), type_t, field)
328
329
330 /*!
331 * @macro smrq_entered_next
332 *
333 * @brief
334 * Returns the next element of an SMR queue element, while in a read section.
335 */
336 #define smrq_entered_next(elem, field) \
337 __container_of_safe(smr_entered_load(&(elem)->field.next), \
338 typeof(*(elem)), field)
339
340
341 /*!
342 * @macro smrq_entered_foreach
343 *
344 * @brief
345 * Enumerates an SMR queue, while in a read section.
346 */
347 #define smrq_entered_foreach(it, head, field) \
348 for (__auto_type __it = smr_entered_load(&(head)->first); \
349 ((it) = __container_of_safe(__it, typeof(*(it)), field)); \
350 __it = smr_entered_load(&__it->next))
351
352
353 /*!
354 * @macro smrq_serialized_first
355 *
356 * @brief
357 * Returns the first element of an SMR queue, while being serialized
358 * by an external mechanism.
359 */
360 #define smrq_serialized_first(head, type_t, link) \
361 __container_of_safe(smr_serialized_load(&(head)->first), type_t, link)
362
363 /*!
364 * @macro smrq_serialized_next
365 *
366 * @brief
367 * Returns the next element of an SMR queue element, while being serialized
368 * by an external mechanism.
369 */
370 #define smrq_serialized_next(elem, field) \
371 __container_of_safe(smr_serialized_load(&(elem)->field.next), \
372 typeof(*(elem)), field)
373
374 /*!
375 * @macro smrq_serialized_foreach
376 *
377 * @brief
378 * Enumerates an SMR queue, while being serialized
379 * by an external mechanism.
380 */
381 #define smrq_serialized_foreach(it, head, field) \
382 for (__auto_type __it = smr_serialized_load(&(head)->first); \
383 ((it) = __container_of_safe(__it, typeof(*(it)), field)); \
384 __it = smr_serialized_load(&__it->next))
385
386 /*!
387 * @macro smrq_serialized_foreach_safe
388 *
389 * @brief
390 * Enumerates an SMR queue, while being serialized
391 * by an external mechanism.
392 *
393 * @discussion
394 * This variant supports removing the current element from the queue.
395 */
396 #define smrq_serialized_foreach_safe(it, head, field) \
397 for (__auto_type __it = smr_serialized_load(&(head)->first), \
398 __next_it = __it; \
399 ((it) = __container_of_safe(__it, typeof(*(it)), field)) && \
400 ((__next_it = smr_serialized_load(&__it->next)), 1); \
401 __it = __next_it)
402
403
404 /*!
405 * @macro smrq_serialized_insert_head
406 *
407 * @brief
408 * Inserts an element at the head of an SMR queue, while being serialized
409 * by an external mechanism.
410 */
411 #define smrq_serialized_insert_head(head, elem) ({ \
412 __auto_type __head = (head); \
413 \
414 __smrq_serialized_insert(&__head->first, (elem), \
415 smr_serialized_load(&__head->first), __smrq_lastp(__head)); \
416 })
417
418
419 /*!
420 * @macro smrq_serialized_insert_tail
421 *
422 * @brief
423 * Inserts an element at the tail of an SMR queue, while being serialized
424 * by an external mechanism.
425 */
426 #define smrq_serialized_insert_tail(head, elem) ({ \
427 __auto_type __head = (head); \
428 \
429 __smrq_serialized_insert(__head->last, (elem), \
430 NULL, &__head->last); \
431 })
432
433
434 /*!
435 * @macro smrq_serialized_insert_head_relaxed
436 *
437 * @brief
438 * Inserts an element at the head of an SMR queue, while being serialized
439 * by an external mechanism, without any barrier.
440 */
441 #define smrq_serialized_insert_head_relaxed(head, elem) ({ \
442 __auto_type __head = (head); \
443 \
444 __smrq_serialized_insert_relaxed(&__head->first, (elem), \
445 smr_serialized_load(&__head->first), __smrq_lastp(__head)); \
446 })
447
448
449 /*!
450 * @macro smrq_serialized_insert_tail_relaxed
451 *
452 * @brief
453 * Inserts an element at the tail of an SMR queue, while being serialized
454 * by an external mechanism, without any barrier.
455 */
456 #define smrq_serialized_insert_tail_relaxed(head, elem) ({ \
457 __auto_type __head = (head); \
458 \
459 __smrq_serialized_insert_relaxed(__head->last, (elem), \
460 NULL, &__head->last); \
461 })
462
463
464 /*!
465 * @macro smrq_serialized_remove
466 *
467 * @brief
468 * Removes an element from an SMR queue, while being serialized
469 * by an external mechanism.
470 *
471 * @discussion
472 * The @c head argument is actually unused for the @c smrq_list queue type.
473 * It is still advised to pass it, the compiler should be able to optimize
474 * the code away as computing a list head ought to have no side effects.
475 */
476 #define smrq_serialized_remove(head, elem) ({ \
477 __auto_type __head = (head); \
478 \
479 __smrq_serialized_remove(&__head->first, (elem), __smrq_lastp(__head)); \
480 })
481
482
483 /*!
484 * @macro smrq_serialized_replace
485 *
486 * @brief
487 * Replaces an element on an SMR queue with another at the same spot,
488 * while being serialized by an external mechanism.
489 */
490 #define smrq_serialized_replace(head, old_elem, new_elem) ({ \
491 __auto_type __head = (head); \
492 \
493 __smrq_serialized_replace(&__head->first, \
494 (old_elem), (new_elem), __smrq_lastp(__head)); \
495 })
496
497
498 /*!
499 * @macro smrq_serialized_iter
500 *
501 * @brief
502 * Enumerates an SMR singly linked queue, while being serialized
503 * by an external mechanism.
504 *
505 * @discussion
506 * This is for manual loops that typically perform erasures.
507 *
508 * The body of the loop must move the cursor using (once):
509 * - smrq_serialized_iter_next() to to go the next element,
510 * - smrq_serialized_iter_erase() to erase the current element.
511 *
512 * The iterator variable will _not_ be updated until the next
513 * loop iteration.
514 *
515 * This form is preferred to smrq_serialized_foreach_safe()
516 * for singly linked lists as smrq_serialized_iter_erase()
517 * is O(1) as opposed to smrq_serialized_remove().
518 */
519 #define smrq_serialized_iter(it, head, field) \
520 for (__smrq_slink_t *__prev_##it = &(head)->first, \
521 *__chk_##it = __prev_##it; \
522 ((it) = __container_of_safe(smr_serialized_load(__prev_##it), \
523 typeof(*(it)), field)); \
524 assert(__chk_##it), __chk_##it = __prev_##it)
525
526 /*!
527 * @macro smrq_serialized_iter_next
528 *
529 * @brief
530 * Goes to the next element inside an smrq_serialied_iter() loop.
531 */
532 #define smrq_serialized_iter_next(it, field) ({ \
533 assert(__chk_##it == __prev_##it); \
534 __chk_##it = NULL; \
535 __prev_##it = &(it)->field.next; \
536 })
537
538 /*!
539 * @macro smrq_serialized_iter_erase
540 *
541 * @brief
542 * Erases the element pointed at by the cursor.
543 */
544 #define smrq_serialized_iter_erase(it, field) ({ \
545 assert(__chk_##it == __prev_##it); \
546 __chk_##it = NULL; \
547 __smrq_serialized_remove_one(__prev_##it, &(it)->field, NULL); \
548 })
549
550
551 /*!
552 * @macro smrq_serialized_append
553 *
554 * @brief
555 * Appends a given list at the end of the previous one.
556 *
557 * @discussion
558 * /!\ WARNING /!\: this doesn't "move" the "source" queue like *_CONCAT
559 * for <sys/queue.h>, as it is useful to merge/split hash queues concurrently
560 * with readers while allowing readers to still read via the "source" queue.
561 *
562 * However, the "source" queue needs to be reset to a valid state
563 * if it is to be used again.
564 */
565 #define smrq_serialized_append(dst, src) ({ \
566 __auto_type __src = (src); \
567 __auto_type __dst = (dst); \
568 \
569 __smrq_serialized_append(&__dst->first, __smrq_lastp(__dst), \
570 &__src->first, __smrq_lastp(__src)); \
571 })
572
573
574 #pragma mark SMR domains
575
576 /*!
577 * @enum smr_flags_t
578 *
579 * @brief
580 * Options to pass to smr_domain_create()
581 *
582 * @const SMR_NONE
583 * Default values for the flags.
584 #if XNU_KERNEL_PRIVATE
585 *
586 * @const SMR_SLEEPABLE
587 * Create a sleepable SMR domain.
588 #endif
589 */
590 __options_closed_decl(smr_flags_t, unsigned long, {
591 SMR_NONE = 0x00000000,
592 #if XNU_KERNEL_PRIVATE
593 SMR_SLEEPABLE = 0x00000001,
594 #endif
595 });
596
597 /*!
598 * @function smr_domain_create()
599 *
600 * @brief
601 * Create an SMR domain.
602 *
603 * @discussion
604 * Be mindful when creating SMR domains, and consider carefully
605 * whether to add one or consolidate an existing one.
606 *
607 *
608 * Memory usage
609 * ~~~~~~~~~~~~
610 *
611 * SMR domains are fairly large structures that scale with the number
612 * of cores of the machine. They are meant to be use in a coarse grained
613 * manner.
614 *
615 * In addition to that, when @c smr_call() is used with the domain,
616 * the queues of callbacks are drained based on memory pressure within
617 * the domain. The more domains, the more dormant memory might exist.
618 *
619 * In general, memory considerations drive toward less domains.
620 *
621 *
622 * Scalability
623 * ~~~~~~~~~~~
624 *
625 * An SMR domain is built on top of an atomic state that is used
626 * to perform grace period detection. The more "write" activity
627 * there is on the domain (@c smr_call(), @c smr_advance(), etc...),
628 * the more this atomic might become contended. In particular,
629 * certain usage patterns might scale extremely well independently,
630 * but cause higher contention when sharing a domain.
631 *
632 * Another thing to consider is that when @c smr_call() is being used,
633 * if the callbacks act on vastly different data structures, then as
634 * the callbacks are being drained, cache misses will be higher.
635 *
636 * However, the more domains are in use, the more probable it is
637 * that using it will cause a cache miss.
638 *
639 * Generally, scalability considerations drive toward balanced
640 * coarse-grained domains.
641 *
642 *
643 * Invariants
644 * ~~~~~~~~~~
645 *
646 * The last aspect leading to the decision of creating versus reusing
647 * an SMR domain is about the invariants that these domains protect.
648 *
649 * Object graphs that are protected with SMR and are used together
650 * in many workloads will likely require to share an SMR domain
651 * in order to provide the required guarantees. Having @c smr_call()
652 * callbacks in a given domain cause downstream @c smr_call() into
653 * another different domain regularly is probably a sign that these
654 * domains should be shared.
655 *
656 * Another aspect to consider is that using @c smr_synchronize()
657 * or @c smr_barrier() can lead to two classes of problems:
658 *
659 * - these operations are extremely heavy, and if some subsystem needs to
660 * perform them on several domains, performance will be disappointing.
661 *
662 * - these operations are akin to taking a "write lock" on the domain,
663 * and as such can cause deadlocks when used improperly.
664 * Using a coarser grained unique domain is a good way to simplify
665 * reasoning about the locking dependencies between SMR domains
666 * and other regular locks.
667 *
668 *
669 * Guidance
670 * ~~~~~~~~
671 *
672 * In general, the entire kernel should have relatively few SMR domains,
673 * at the scale of the big subsystems of the kernel (think: Mach IPC, Mach VM,
674 * VFS, Networking, ...).
675 *
676 * When write operations (@c smr_call(), @c smr_synchronize, ...) are used
677 * rarely, consider using the system wide default domains.
678 */
679 extern smr_t smr_domain_create(smr_flags_t flags, const char *name);
680
681 /*!
682 * @function smr_domain_free()
683 *
684 * @brief
685 * Destroys an SMR domain previously create with @c smr_domain_create().
686 */
687 extern void smr_domain_free(smr_t smr);
688
689
690 /*!
691 * @function smr_entered()
692 *
693 * @brief
694 * Returns whether an SMR critical section is entered.
695 */
696 extern bool smr_entered(smr_t smr) __result_use_check;
697
698 /*!
699 * @function smr_enter()
700 *
701 * @brief
702 * Enter a non preemptible SMR critical section.
703 *
704 * @discussion
705 * Entering an SMR critical section is non reentrant.
706 * (entering it recursively is undefined and will panic on development kernels)
707 *
708 * @c smr_leave() must be called to end this section.
709 *
710 * This function can'be be used in interrupt context.
711 */
712 extern void smr_enter(smr_t smr);
713
714 /*!
715 * @function smr_leave()
716 *
717 * @brief
718 * Leave a non preemptible SMR critical section.
719 */
720 extern void smr_leave(smr_t smr);
721
722
723 /*!
724 * @function smr_call()
725 *
726 * @brief
727 * Defer making a call until it is safe to assume all readers
728 * will observe any update prior to this call.
729 *
730 * @discussion
731 * The target SMR domain must NOT be entered when making this call.
732 *
733 * The passed @c size doesn't have to be precise, it should be a rough
734 * estimate of the memory that will be reclaimed when when the call is made.
735 *
736 * This function gives no guarantee of forward progress,
737 * unless the magic SMR_CALL_EXPEDITE size is passed to @c smr_call().
738 *
739 * This function can'be be used in interrupt context.
740 */
741 extern void smr_call(smr_t smr, smr_node_t node, vm_size_t size, smr_cb_t cb);
742
743 #define SMR_CALL_EXPEDITE ((vm_size_t)~0)
744
745 /*!
746 * @function smr_synchronize()
747 *
748 * @brief
749 * Wait until all readers have observed any updates made prior to this call.
750 *
751 * @discussion
752 * The target SMR domain must NOT be entered when making this call.
753 *
754 * This function is quite expensive, and asynchronous deferred processing
755 * using @c smr_call() should be used instead when possible.
756 *
757 * Reserve using this call for events that are extremely rare (like system
758 * configuration events such as configuring networking interfaces, changing
759 * system wide security policies, or loading/unloading a kernel extension).
760 *
761 * This function should typically be called with preemption enabled,
762 * and no locks held.
763 */
764 extern void smr_synchronize(smr_t smr);
765
766 /*!
767 * @function smr_barrier()
768 *
769 * @brief
770 * Wait until all readers have observed any updates made prior to this call,
771 * and all @c smr_call() callbacks dispatched prior to this call on any core
772 * have completed.
773 *
774 * @discussion
775 * The target SMR domain must NOT be entered when making this call.
776 *
777 * This function is typically used when some data structure is being
778 * accessed by @c smr_call() callbacks and that data structure needs
779 * to be retired.
780 *
781 * Reserve using this call for events that are extremely rare (like system
782 * configuration events such as configuring networking interfaces, changing
783 * system wide security policies, or loading/unloading a kernel extension).
784 *
785 * This function should typically be called with preemption enabled,
786 * and no locks held.
787 */
788 extern void smr_barrier(smr_t smr);
789
790
791 #ifdef XNU_KERNEL_PRIVATE
792 #pragma GCC visibility push(hidden)
793 #pragma mark - XNU only
794 #pragma mark XNU only: SMR domains advanced
795
796 #define SMR_SEQ_INVALID ((smr_seq_t)0)
797 #define SMR_SEQ_SLEEPABLE ((smr_seq_t)1) /* only on smr_pcpu::rd_seq */
798 #define SMR_SEQ_INIT ((smr_seq_t)2)
799 #define SMR_SEQ_INC ((smr_seq_t)4)
800
801 typedef long smr_delta_t;
802
803 #define SMR_SEQ_DELTA(a, b) ((smr_delta_t)((a) - (b)))
804 #define SMR_SEQ_CMP(a, op, b) (SMR_SEQ_DELTA(a, b) op 0)
805
806 /*!
807 * @typedef smr_clock_t
808 *
809 * @brief
810 * Represents an SMR domain clock, internal type not manipulated by clients.
811 */
812 typedef struct {
813 smr_seq_t s_rd_seq;
814 smr_seq_t s_wr_seq;
815 } smr_clock_t;
816
817 #define SMR_NAME_MAX 24
818
819 /*!
820 * @typedef smr_t
821 *
822 * @brief
823 * Declares an SMR domain of synchronization.
824 */
825 struct smr {
826 smr_clock_t smr_clock;
827 struct smr_pcpu *smr_pcpu;
828 unsigned long smr_flags;
829 unsigned long smr_early;
830 char smr_name[SMR_NAME_MAX];
831 } __attribute__((aligned(64)));
832
833 /*!
834 * @macro SMR_DEFINE_FLAGS
835 *
836 * @brief
837 * Define an SMR domain with specific create flags.
838 */
839 #define SMR_DEFINE_FLAGS(var, name, flags) \
840 struct smr var = { \
841 .smr_clock.s_rd_seq = SMR_SEQ_INIT, \
842 .smr_clock.s_wr_seq = SMR_SEQ_INIT, \
843 .smr_flags = (flags), \
844 .smr_name = "" name, \
845 }; \
846 STARTUP_ARG(TUNABLES, STARTUP_RANK_LAST, __smr_domain_init, &(var)); \
847 STARTUP_ARG(ZALLOC, STARTUP_RANK_LAST, __smr_domain_init, &(var))
848
849 /*!
850 * @macro SMR_DEFINE
851 *
852 * @brief
853 * Define an SMR domain.
854 */
855 #define SMR_DEFINE(var, name) \
856 SMR_DEFINE_FLAGS(var, name, SMR_NONE)
857
858
859 /*!
860 * @macro SMR_DEFINE_SLEEPABLE
861 *
862 * @brief
863 * Define a sleepable SMR domain.
864 */
865 #define SMR_DEFINE_SLEEPABLE(var, name) \
866 SMR_DEFINE_FLAGS(var, name, SMR_SLEEPABLE)
867
868
869 /*!
870 * @function smr_advance()
871 *
872 * @brief
873 * Advance the write sequence and return the value
874 * for use as a wait goal.
875 *
876 * @discussion
877 * This guarantees that any changes made by the calling thread
878 * prior to this call will be visible to all threads after
879 * the read sequence meets or exceeds the return value.
880 */
881 extern smr_seq_t smr_advance(smr_t smr) __result_use_check;
882
883 /*!
884 * @function smr_deferred_advance()
885 *
886 * @brief
887 * Pretend-advance the write sequence and return the value
888 * for use as a wait goal.
889 *
890 * @discussion
891 * This guarantees that any changes made by the calling thread
892 * prior to this call will be visible to all threads after
893 * the read sequence meets or exceeds the return value.
894 *
895 * Unlike smr_advance(), the global clock isn't really advanced,
896 * it only sets a goal in the future. This can be used to control
897 * the pace of updating the global clock and avoid global atomics.
898 *
899 * In order for the clock to advance, clients of this API must call
900 * @c smr_deferred_advance_commit() with the goal returned by this call.
901 *
902 * Note that calls to @c smr_advance() or @c smr_wait() when passed
903 * the goal returned by this function would also allow the clock
904 * to make progress and are legal (yet less efficient) calls to make.
905 */
906 extern smr_seq_t smr_deferred_advance(smr_t smr) __result_use_check;
907
908 /*!
909 * @function smr_deferred_advance_commit()
910 *
911 * @brief
912 * Actually advance the write sequence to the goal returned by a previous
913 * call to @c smr_deferred_advance().
914 */
915 extern void smr_deferred_advance_commit(smr_t smr, smr_seq_t seq);
916
917
918 /*!
919 * @function smr_poll
920 *
921 * @brief
922 * Poll to determine whether all readers have observed the @c goal
923 * write sequence number.
924 *
925 * @discussion
926 * This function is safe to be called from preemption disabled context
927 * and its worst complexity is O(ncpu).
928 *
929 * @returns true if the goal is met and false if not.
930 */
931 extern bool smr_poll(smr_t smr, smr_seq_t goal) __result_use_check;
932
933 /*!
934 * @function smr_wait
935 *
936 * @brief
937 * Wait until all readers have observed
938 * the @c goal write sequence number.
939 *
940 * @discussion
941 * This function is safe to be called from preemption disabled context
942 * as it never explicitly blocks, however this is not recommended.
943 */
944 extern void smr_wait(smr_t smr, smr_seq_t goal);
945
946
947 #pragma mark XNU only: major sleepable SMR domains
948 /*
949 * Note: this is private for now because sleepable sections that do "bad" things
950 * (such as doing an upcall to userspace, or doing VM allocations) have
951 * the danger that they can stall the reclamation worker threads,
952 * which are a singleton resource.
953 *
954 * Until this can be mitigated or designed better, this stays private.
955 */
956
957 /*!
958 * @typedef smr_tracker_t
959 *
960 * @brief
961 * Structure used to track active sleepable SMR sections.
962 *
963 * @field smrt_domain the entered SMR domain
964 * @field smrt_seq the SMR sequence at the time of smr_enter_sleepable().
965 * @field smrt_link linkage used to track stalled sections.
966 * @field smrt_stack linkage used to track entered sections.
967 * @field smrt_ctid (if stalled) the ctid of the thread in this section.
968 * @field smrt_cpu (if stalled) the cpu the thread was on when stalled.
969 */
970 typedef struct smr_tracker {
971 smr_t smrt_domain;
972 smr_seq_t smrt_seq;
973 struct smrq_link smrt_link;
974 struct smrq_slink smrt_stack;
975 uint32_t smrt_ctid;
976 int smrt_cpu;
977 } *smr_tracker_t;
978
979 /*!
980 * @function smr_enter_sleepable()
981 *
982 * @brief
983 * Enter a sleepable SMR critical section.
984 *
985 * @discussion
986 * Entering an SMR critical section is non recursive
987 * (entering it recursively is undefined and will panic on development kernels)
988 *
989 * @c smr_leave_sleepable() must be called to end this section,
990 * passing the same tracker pointer.
991 *
992 * The SMR domain must have been created with the @c SMR_SLEEPABLE flag.
993 *
994 * It is permitted to do operations that might block under such a transaction,
995 * such as acquiring a lock, or freeing memory.
996 *
997 * It is forbidden to perform operations that wait for an unbounded amount of
998 * time such as waiting for networking packets or even a hardware driver event,
999 * as these could cause grace periods (and memory reclamation) to stall for
1000 * a very long time.
1001 */
1002 extern void smr_enter_sleepable(smr_t smr, smr_tracker_t tracker);
1003
1004 /*!
1005 * @function smr_leave_sleepable()
1006 *
1007 * @brief
1008 * Leave a sleepable SMR critical section entered with @c smr_enter_sleepable().
1009 */
1010 extern void smr_leave_sleepable(smr_t smr, smr_tracker_t tracker);
1011
1012
1013 #pragma mark XNU only: major subsystems SMR domains
1014
1015 /*!
1016 * @brief
1017 * A global system wide non preemptible domain.
1018 *
1019 * @discussion
1020 * This is provided as a fallback for when a specific SMR domain
1021 * would be overkill.
1022 *
1023 * Try not use the @c smr_system name directly, instead define
1024 * a subsystem domain that happens to be defined to it, so that
1025 * understanding the invariants being provided is easier.
1026 */
1027 extern struct smr smr_system;
1028
1029 /*!
1030 * @brief
1031 * A global system wide sleepable domain.
1032 *
1033 * @discussion
1034 * This is provided as a fallback for when a specific SMR domain
1035 * would be overkill.
1036 *
1037 * Try not use the @c smr_system_sleepable name directly,
1038 * instead define a subsystem domain that happens to be defined to it,
1039 * so that understanding the invariants being provided is easier.
1040 */
1041 extern struct smr smr_system_sleepable;
1042
1043
1044 /*!
1045 * @macro smr_ipc
1046 *
1047 * @brief
1048 * The SMR domain for the Mach IPC subsystem.
1049 */
1050 #define smr_ipc smr_system
1051 #define smr_ipc_entered() smr_entered(&smr_ipc)
1052 #define smr_ipc_enter() smr_enter(&smr_ipc)
1053 #define smr_ipc_leave() smr_leave(&smr_ipc)
1054
1055 #define smr_ipc_call(n, sz, cb) smr_call(&smr_ipc, n, sz, cb)
1056 #define smr_ipc_synchronize() smr_synchronize(&smr_ipc)
1057 #define smr_ipc_barrier() smr_barrier(&smr_ipc)
1058
1059
1060 /*!
1061 * @macro smr_proc_task
1062 *
1063 * @brief
1064 * The SMR domain for the proc/task and adjacent objects.
1065 */
1066 #define smr_proc_task smr_system
1067 #define smr_proc_task_entered() smr_entered(&smr_proc_task)
1068 #define smr_proc_task_enter() smr_enter(&smr_proc_task)
1069 #define smr_proc_task_leave() smr_leave(&smr_proc_task)
1070
1071 #define smr_proc_task_call(n, sz, cb) smr_call(&smr_proc_task, n, sz, cb)
1072 #define smr_proc_task_synchronize() smr_synchronize(&smr_proc_task)
1073 #define smr_proc_task_barrier() smr_barrier(&smr_proc_task)
1074
1075
1076 /*!
1077 * @macro smr_iokit
1078 *
1079 * @brief
1080 * The SMR domain for IOKit
1081 */
1082 #define smr_iokit smr_system
1083 #define smr_iokit_entered() smr_entered(&smr_iokit)
1084 #define smr_iokit_enter() smr_enter(&smr_iokit)
1085 #define smr_iokit_leave() smr_leave(&smr_iokit)
1086
1087 #define smr_iokit_call(n, sz, cb) smr_call(&smr_iokit, n, sz, cb)
1088 #define smr_iokit_synchronize() smr_synchronize(&smr_iokit)
1089 #define smr_iokit_barrier() smr_barrier(&smr_iokit)
1090
1091
1092 /*!
1093 * @macro smr_oslog
1094 *
1095 * @brief
1096 * The SMR domain for kernel OSLog handles.
1097 */
1098 #define smr_oslog smr_system
1099 #define smr_oslog_entered() smr_entered(&smr_oslog)
1100 #define smr_oslog_enter() smr_enter(&smr_oslog)
1101 #define smr_oslog_leave() smr_leave(&smr_oslog)
1102
1103 #define smr_oslog_call(n, sz, cb) smr_call(&smr_oslog, n, sz, cb)
1104 #define smr_oslog_synchronize() smr_synchronize(&smr_oslog)
1105 #define smr_oslog_barrier() smr_barrier(&smr_oslog)
1106
1107
1108 #pragma mark XNU only: implementation details
1109
1110 extern void __smr_domain_init(smr_t);
1111
1112 #ifdef MACH_KERNEL_PRIVATE
1113 struct processor;
1114
1115 extern bool smr_entered_cpu_noblock(smr_t smr, int cpu) __result_use_check;
1116
1117 extern void smr_ack_ipi(void);
1118
1119 extern void smr_mark_active_trackers_stalled(struct thread *self);
1120
1121 __options_closed_decl(smr_cpu_reason_t, uint8_t, {
1122 SMR_CPU_REASON_NONE = 0x00,
1123 SMR_CPU_REASON_OFFLINE = 0x01,
1124 SMR_CPU_REASON_IGNORED = 0x02,
1125 SMR_CPU_REASON_ALL = 0x03,
1126 });
1127
1128 extern void smr_cpu_init(struct processor *);
1129 extern void smr_cpu_up(struct processor *, smr_cpu_reason_t);
1130 extern void smr_cpu_down(struct processor *, smr_cpu_reason_t);
1131
1132 extern void smr_cpu_join(struct processor *, uint64_t ctime);
1133 extern void smr_cpu_tick(uint64_t ctime, bool safe_point);
1134 extern void smr_cpu_leave(struct processor *, uint64_t ctime);
1135
1136 extern void smr_maintenance(uint64_t ctime);
1137
1138 #if CONFIG_QUIESCE_COUNTER
1139 extern void cpu_quiescent_set_storage(uint64_t _Atomic *ptr);
1140 #endif
1141 #endif /* MACH_KERNEL_PRIVATE */
1142
1143 extern uint32_t smr_cpu_checkin_get_min_interval_us(void);
1144
1145 extern uint32_t smr_cpu_checkin_get_min_interval_us(void);
1146
1147 extern void smr_cpu_checkin_set_min_interval_us(uint32_t new_value);
1148
1149 #pragma GCC visibility pop
1150 #endif /* XNU_KERNEL_PRIVATE */
1151 #pragma mark - implementation details
1152 #pragma mark implementation details: SMR queues
1153
1154 extern void __smr_linkage_invalid(__smrq_link_t *link) __abortlike;
1155 extern void __smr_stail_invalid(__smrq_slink_t *link, __smrq_slink_t *last) __abortlike;
1156 extern void __smr_tail_invalid(__smrq_link_t *link, __smrq_link_t *last) __abortlike;
1157
1158 __attribute__((always_inline, overloadable))
1159 static inline __smrq_slink_t **
__smrq_lastp(struct smrq_slist_head * head __unused)1160 __smrq_lastp(struct smrq_slist_head *head __unused)
1161 {
1162 return NULL;
1163 }
1164
1165 __attribute__((always_inline, overloadable))
1166 static inline __smrq_link_t **
__smrq_lastp(struct smrq_list_head * head __unused)1167 __smrq_lastp(struct smrq_list_head *head __unused)
1168 {
1169 return NULL;
1170 }
1171
1172 __attribute__((always_inline, overloadable))
1173 static inline __smrq_slink_t **
__smrq_lastp(struct smrq_stailq_head * head)1174 __smrq_lastp(struct smrq_stailq_head *head)
1175 {
1176 __smrq_slink_t **last = &head->last;
1177
1178 __builtin_assume(last != NULL);
1179 return last;
1180 }
1181
1182 __attribute__((always_inline, overloadable))
1183 static inline __smrq_link_t **
__smrq_lastp(struct smrq_tailq_head * head)1184 __smrq_lastp(struct smrq_tailq_head *head)
1185 {
1186 __smrq_link_t **last = &head->last;
1187
1188 __builtin_assume(last != NULL);
1189 return last;
1190 }
1191
1192
1193 __attribute__((always_inline, overloadable))
1194 static inline void
__smrq_serialized_insert(__smrq_slink_t * prev,struct smrq_slink * elem,struct smrq_slink * next,__smrq_slink_t ** lastp)1195 __smrq_serialized_insert(
1196 __smrq_slink_t *prev,
1197 struct smrq_slink *elem,
1198 struct smrq_slink *next,
1199 __smrq_slink_t **lastp)
1200 {
1201 if (next == NULL && lastp) {
1202 if (*lastp != prev || smr_serialized_load(prev)) {
1203 __smr_stail_invalid(prev, *lastp);
1204 }
1205 }
1206
1207 smr_serialized_store_relaxed(&elem->next, next);
1208 smr_serialized_store(prev, elem);
1209 if (next == NULL && lastp) {
1210 *lastp = &elem->next;
1211 }
1212 }
1213
1214 __attribute__((always_inline, overloadable))
1215 static inline void
__smrq_serialized_insert(__smrq_link_t * prev,struct smrq_link * elem,struct smrq_link * next,__smrq_link_t ** lastp)1216 __smrq_serialized_insert(
1217 __smrq_link_t *prev,
1218 struct smrq_link *elem,
1219 struct smrq_link *next,
1220 __smrq_link_t **lastp)
1221 {
1222 if (next != NULL && next->prev != prev) {
1223 __smr_linkage_invalid(prev);
1224 }
1225 if (next == NULL && lastp) {
1226 if (*lastp != prev || smr_serialized_load(prev)) {
1227 __smr_tail_invalid(prev, *lastp);
1228 }
1229 }
1230
1231 smr_serialized_store_relaxed(&elem->next, next);
1232 elem->prev = prev;
1233 smr_serialized_store(prev, elem);
1234
1235 if (next != NULL) {
1236 next->prev = &elem->next;
1237 } else if (lastp) {
1238 *lastp = &elem->next;
1239 }
1240 }
1241
1242
1243 __attribute__((always_inline, overloadable))
1244 static inline void
__smrq_serialized_insert_relaxed(__smrq_slink_t * prev,struct smrq_slink * elem,struct smrq_slink * next,__smrq_slink_t ** lastp)1245 __smrq_serialized_insert_relaxed(
1246 __smrq_slink_t *prev,
1247 struct smrq_slink *elem,
1248 struct smrq_slink *next,
1249 __smrq_slink_t **lastp)
1250 {
1251 if (next == NULL && lastp) {
1252 if (*lastp != prev || smr_serialized_load(prev)) {
1253 __smr_stail_invalid(prev, *lastp);
1254 }
1255 }
1256
1257 smr_serialized_store_relaxed(&elem->next, next);
1258 smr_serialized_store_relaxed(prev, elem);
1259 if (next == NULL && lastp) {
1260 *lastp = &elem->next;
1261 }
1262 }
1263
1264 __attribute__((always_inline, overloadable))
1265 static inline void
__smrq_serialized_insert_relaxed(__smrq_link_t * prev,struct smrq_link * elem,struct smrq_link * next,__smrq_link_t ** lastp)1266 __smrq_serialized_insert_relaxed(
1267 __smrq_link_t *prev,
1268 struct smrq_link *elem,
1269 struct smrq_link *next,
1270 __smrq_link_t **lastp)
1271 {
1272 if (next != NULL && next->prev != prev) {
1273 __smr_linkage_invalid(prev);
1274 }
1275 if (next == NULL && lastp) {
1276 if (*lastp != prev || smr_serialized_load(prev)) {
1277 __smr_tail_invalid(prev, *lastp);
1278 }
1279 }
1280
1281 smr_serialized_store_relaxed(&elem->next, next);
1282 elem->prev = prev;
1283 smr_serialized_store_relaxed(prev, elem);
1284
1285 if (next != NULL) {
1286 next->prev = &elem->next;
1287 } else if (lastp) {
1288 *lastp = &elem->next;
1289 }
1290 }
1291
1292
1293 __attribute__((always_inline, overloadable))
1294 static inline void
__smrq_serialized_remove_one(__smrq_slink_t * prev,struct smrq_slink * elem,__smrq_slink_t ** lastp)1295 __smrq_serialized_remove_one(
1296 __smrq_slink_t *prev,
1297 struct smrq_slink *elem,
1298 __smrq_slink_t **lastp)
1299 {
1300 struct smrq_slink *next;
1301
1302 /*
1303 * Removal "skips" a link this way:
1304 *
1305 * e1 ---> e2 ---> e3 becomes e1 -----------> e3
1306 *
1307 * When e3 was inserted, a release barrier was issued
1308 * by smr_serialized_store(). We do not need to issue
1309 * a release barrier upon removal because `next` carries
1310 * a dependency on that smr_serialized_store()d value.
1311 */
1312 next = smr_serialized_load(&elem->next);
1313 smr_serialized_store_relaxed(prev, next);
1314 if (next == NULL && lastp) {
1315 *lastp = prev;
1316 }
1317 }
1318
1319 __attribute__((always_inline, overloadable))
1320 static inline void
__smrq_serialized_remove_one(__smrq_link_t * prev,struct smrq_link * elem,__smrq_link_t ** lastp)1321 __smrq_serialized_remove_one(
1322 __smrq_link_t *prev,
1323 struct smrq_link *elem,
1324 __smrq_link_t **lastp)
1325 {
1326 struct smrq_link *next;
1327
1328 next = smr_serialized_load(&elem->next);
1329
1330 if (smr_serialized_load(prev) != elem) {
1331 __smr_linkage_invalid(prev);
1332 }
1333 if (next && next->prev != &elem->next) {
1334 __smr_linkage_invalid(&elem->next);
1335 }
1336
1337 /*
1338 * Removal "skips" a link this way:
1339 *
1340 * e1 ---> e2 ---> e3 becomes e1 -----------> e3
1341 *
1342 * When e3 was inserted, a release barrier was issued
1343 * by smr_serialized_store(). We do not need to issue
1344 * a release barrier upon removal because `next` carries
1345 * a dependency on that smr_serialized_store()d value.
1346 */
1347 smr_serialized_store_relaxed(prev, next);
1348
1349 if (next != NULL) {
1350 next->prev = prev;
1351 } else if (lastp) {
1352 *lastp = prev;
1353 }
1354 elem->prev = NULL;
1355 }
1356
1357
1358 __attribute__((always_inline, overloadable))
1359 static inline void
__smrq_serialized_remove(__smrq_slink_t * first,struct smrq_slink * elem,__smrq_slink_t ** lastp)1360 __smrq_serialized_remove(
1361 __smrq_slink_t *first,
1362 struct smrq_slink *elem,
1363 __smrq_slink_t **lastp)
1364 {
1365 __smrq_slink_t *prev = first;
1366 struct smrq_slink *cur;
1367
1368 while ((cur = smr_serialized_load(prev)) != elem) {
1369 prev = &cur->next;
1370 }
1371
1372 __smrq_serialized_remove_one(prev, elem, lastp);
1373 }
1374
1375 __attribute__((always_inline, overloadable))
1376 static inline void
__smrq_serialized_remove(__smrq_link_t * first __unused,struct smrq_link * elem,__smrq_link_t ** lastp)1377 __smrq_serialized_remove(
1378 __smrq_link_t *first __unused,
1379 struct smrq_link *elem,
1380 __smrq_link_t **lastp)
1381 {
1382 __smrq_serialized_remove_one(elem->prev, elem, lastp);
1383 }
1384
1385
1386 __attribute__((always_inline, overloadable))
1387 static inline void
__smrq_serialized_replace(__smrq_slink_t * first,struct smrq_slink * old_elem,struct smrq_slink * new_elem,__smrq_slink_t ** lastp)1388 __smrq_serialized_replace(
1389 __smrq_slink_t *first,
1390 struct smrq_slink *old_elem,
1391 struct smrq_slink *new_elem,
1392 __smrq_slink_t **lastp)
1393 {
1394 __smrq_slink_t *prev = first;
1395 struct smrq_slink *cur;
1396 struct smrq_slink *next;
1397
1398 while ((cur = smr_serialized_load(prev)) != old_elem) {
1399 prev = &cur->next;
1400 }
1401
1402 next = smr_serialized_load(&old_elem->next);
1403 smr_serialized_store_relaxed(&new_elem->next, next);
1404 smr_serialized_store(prev, new_elem);
1405
1406 if (next == NULL && lastp) {
1407 *lastp = &new_elem->next;
1408 }
1409 }
1410
1411 __attribute__((always_inline, overloadable))
1412 static inline void
__smrq_serialized_replace(__smrq_link_t * first __unused,struct smrq_link * old_elem,struct smrq_link * new_elem,__smrq_link_t ** lastp)1413 __smrq_serialized_replace(
1414 __smrq_link_t *first __unused,
1415 struct smrq_link *old_elem,
1416 struct smrq_link *new_elem,
1417 __smrq_link_t **lastp)
1418 {
1419 __smrq_link_t *prev;
1420 struct smrq_link *next;
1421
1422 prev = old_elem->prev;
1423 next = smr_serialized_load(&old_elem->next);
1424
1425 if (smr_serialized_load(prev) != old_elem) {
1426 __smr_linkage_invalid(prev);
1427 }
1428 if (next && next->prev != &old_elem->next) {
1429 __smr_linkage_invalid(&old_elem->next);
1430 }
1431
1432 smr_serialized_store_relaxed(&new_elem->next, next);
1433 new_elem->prev = prev;
1434 smr_serialized_store(prev, new_elem);
1435
1436 if (next != NULL) {
1437 next->prev = &new_elem->next;
1438 } else if (lastp) {
1439 *lastp = &new_elem->next;
1440 }
1441 old_elem->prev = NULL;
1442 }
1443
1444 __attribute__((always_inline, overloadable))
1445 static inline void
__smrq_serialized_append(__smrq_slink_t * dst_first,__smrq_slink_t ** dst_lastp,__smrq_slink_t * src_first,__smrq_slink_t ** src_lastp)1446 __smrq_serialized_append(
1447 __smrq_slink_t *dst_first,
1448 __smrq_slink_t **dst_lastp,
1449 __smrq_slink_t *src_first,
1450 __smrq_slink_t **src_lastp)
1451 {
1452 struct smrq_slink *src = smr_serialized_load(src_first);
1453 struct smrq_slink *dst;
1454
1455 if (dst_lastp) {
1456 if (src) {
1457 smr_serialized_store_relaxed(*dst_lastp, src);
1458 *dst_lastp = *src_lastp;
1459 }
1460 } else {
1461 while ((dst = smr_serialized_load(dst_first))) {
1462 dst_first = &dst->next;
1463 }
1464 smr_serialized_store_relaxed(dst_first, src);
1465 }
1466 }
1467
1468 __attribute__((always_inline, overloadable))
1469 static inline void
__smrq_serialized_append(__smrq_link_t * dst_first,__smrq_link_t ** dst_lastp,__smrq_link_t * src_first,__smrq_link_t ** src_lastp)1470 __smrq_serialized_append(
1471 __smrq_link_t *dst_first,
1472 __smrq_link_t **dst_lastp,
1473 __smrq_link_t *src_first,
1474 __smrq_link_t **src_lastp)
1475 {
1476 struct smrq_link *src = smr_serialized_load(src_first);
1477 struct smrq_link *dst;
1478
1479 if (dst_lastp) {
1480 if (src) {
1481 smr_serialized_store_relaxed(*dst_lastp, src);
1482 src->prev = *dst_lastp;
1483 *dst_lastp = *src_lastp;
1484 }
1485 } else {
1486 while ((dst = smr_serialized_load(dst_first))) {
1487 dst_first = &dst->next;
1488 }
1489 smr_serialized_store_relaxed(dst_first, src);
1490 src->prev = &dst->next;
1491 }
1492 }
1493
1494 __END_DECLS
1495
1496 #endif /* _KERN_SMR_H_ */
1497