-
Notifications
You must be signed in to change notification settings - Fork 332
Expand file tree
/
Copy pathsmr.h
More file actions
1496 lines (1319 loc) · 42.1 KB
/
smr.h
File metadata and controls
1496 lines (1319 loc) · 42.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Copyright (c) 2021-2022 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. The rights granted to you under the License
* may not be used to create, or enable the creation or redistribution of,
* unlawful or unlicensed copies of an Apple operating system, or to
* circumvent, violate, or enable the circumvention or violation of, any
* terms of an Apple operating system software license agreement.
*
* Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
*/
#ifndef _KERN_SMR_H_
#define _KERN_SMR_H_
#include <sys/cdefs.h>
#include <stdbool.h>
#include <stdint.h>
#include <kern/assert.h>
#include <kern/debug.h>
#include <kern/smr_types.h>
#include <os/atomic_private.h>
#if XNU_KERNEL_PRIVATE
#include <kern/startup.h>
#endif
__BEGIN_DECLS
#pragma mark SMR pointers
/*
* SMR Accessors are meant to provide safe access to SMR protected
* pointers and prevent misuse and accidental access.
*
* Accessors are grouped by type:
* entered - Use while in a read section (between smr_enter/smr_leave())
* serialized - Use while holding a lock that serializes writers.
* Updates are synchronized with readers via included barriers.
* unserialized - Use after the memory is out of scope and not visible to
* readers.
*
* All acceses include a parameter for an assert to verify the required
* synchronization.
*/
/*!
* @macro smr_unsafe_load()
*
* @brief
* Read from an SMR protected pointer without any synchronization.
*
* @discussion
* This returns an integer on purpose as dereference is generally unsafe.
*/
#define smr_unsafe_load(ptr) \
({ (uintptr_t)((ptr)->__smr_ptr); })
/*!
* @macro smr_entered_load()
*
* @brief
* Read from an SMR protected pointer while in a read section.
*/
#define smr_entered_load(ptr) \
({ (ptr)->__smr_ptr; })
/*!
* @macro smr_entered_load_assert()
*
* @brief
* Read from an SMR protected pointer while in a read section.
*/
#define smr_entered_load_assert(ptr, smr) ({ \
assert(smr_entered(smr)); \
(ptr)->__smr_ptr; \
})
/*!
* @macro smr_entered_load_acquire()
*
* @brief
* Read from an SMR protected pointer while in a read section (with acquire
* fence).
*/
#define smr_entered_load_acquire(ptr) \
os_atomic_load(&(ptr)->__smr_ptr, acquire)
/*!
* @macro smr_entered_load_acquire_assert()
*
* @brief
* Read from an SMR protected pointer while in a read section.
*/
#define smr_entered_load_acquire_assert(ptr, smr) ({ \
assert(smr_entered(smr)); \
os_atomic_load(&(ptr)->__smr_ptr, acquire); \
})
/*!
* @macro smr_serialized_load_assert()
*
* @brief
* Read from an SMR protected pointer while serialized by an
* external mechanism.
*/
#define smr_serialized_load_assert(ptr, held_cond) ({ \
assertf(held_cond, "smr_serialized_load: lock not held"); \
(ptr)->__smr_ptr; \
})
/*!
* @macro smr_serialized_load()
*
* @brief
* Read from an SMR protected pointer while serialized by an
* external mechanism.
*/
#define smr_serialized_load(ptr) \
smr_serialized_load_assert(ptr, true)
/*!
* @macro smr_init_store()
*
* @brief
* Store @c value to an SMR protected pointer during initialization.
*/
#define smr_init_store(ptr, value) \
({ (ptr)->__smr_ptr = value; })
/*!
* @macro smr_clear_store()
*
* @brief
* Clear (sets to 0) an SMR protected pointer (this is always "allowed" to do).
*/
#define smr_clear_store(ptr) \
smr_init_store(ptr, 0)
/*!
* @macro smr_serialized_store_assert()
*
* @brief
* Store @c value to an SMR protected pointer while serialized by an
* external mechanism.
*
* @discussion
* Writers that are serialized with mutual exclusion or on a single
* thread should use smr_serialized_store() rather than swap.
*/
#define smr_serialized_store_assert(ptr, value, held_cond) ({ \
assertf(held_cond, "smr_serialized_store: lock not held"); \
os_atomic_thread_fence(release); \
(ptr)->__smr_ptr = value; \
})
/*!
* @macro smr_serialized_store()
*
* @brief
* Store @c value to an SMR protected pointer while serialized by an
* external mechanism.
*
* @discussion
* Writers that are serialized with mutual exclusion or on a single
* thread should use smr_serialized_store() rather than swap.
*/
#define smr_serialized_store(ptr, value) \
smr_serialized_store_assert(ptr, value, true)
/*!
* @macro smr_serialized_store_relaxed_assert()
*
* @brief
* Store @c value to an SMR protected pointer while serialized by an
* external mechanism.
*
* @discussion
* This function can be used when storing a value that was already
* previously stored with smr_serialized_store() (for example during
* a linked list removal).
*/
#define smr_serialized_store_relaxed_assert(ptr, value, held_cond) ({ \
assertf(held_cond, "smr_serialized_store_relaxed: lock not held"); \
(ptr)->__smr_ptr = value; \
})
/*!
* @macro smr_serialized_store_relaxed()
*
* @brief
* Store @c value to an SMR protected pointer while serialized by an
* external mechanism.
*
* @discussion
* This function can be used when storing a value that was already
* previously stored with smr_serialized_store() (for example during
* a linked list removal).
*/
#define smr_serialized_store_relaxed(ptr, value) \
smr_serialized_store_relaxed_assert(ptr, value, true)
/*!
* @macro smr_serialized_swap_assert()
*
* @brief
* Swap @c value with an SMR protected pointer and return the old value
* while serialized by an external mechanism.
*
* @discussion
* Swap permits multiple writers to update a pointer concurrently.
*/
#define smr_serialized_swap_assert(ptr, value, held_cond) ({ \
assertf(held_cond, "smr_serialized_store: lock not held"); \
os_atomic_xchg(&(ptr)->__smr_ptr, value, release); \
})
/*!
* @macro smr_serialized_swap()
*
* @brief
* Swap @c value with an SMR protected pointer and return the old value
* while serialized by an external mechanism.
*
* @discussion
* Swap permits multiple writers to update a pointer concurrently.
*/
#define smr_serialized_swap(ptr, value) \
smr_serialized_swap_assert(ptr, value, true)
/*!
* @macro smr_unserialized_load()
*
* @brief.
* Read from an SMR protected pointer when no serialization is required
* such as in the destructor callback or when the caller guarantees other
* synchronization.
*/
#define smr_unserialized_load(ptr) \
({ (ptr)->__smr_ptr; })
/*!
* @macro smr_unserialized_store()
*
* @brief.
* Store to an SMR protected pointer when no serialiation is required
* such as in the destructor callback or when the caller guarantees other
* synchronization.
*/
#define smr_unserialized_store(ptr, value) \
({ (ptr)->__smr_ptr = value; })
#pragma mark SMR queues
/*
* SMR queues are queues that are meant to be read under SMR critical sections
* concurrently with possible updates to the queue.
*
* /!\ Such read operations CAN ONLY BE PERFORMED IN FORWARD DIRECTION. /!\
*
* Queues can be either:
* - lists where the head is a single pointer,
* and insertions can only be at the head;
* - tail queues where the head is two pointers,
* and insertions can be either at the head or the tail.
*
* Queue linkages can either be single forward pointer linkages or double
* forward/backward linkages. The latter supports O(1) deletion.
*
*
* The entire API surface uses type inference for the implementations,
* which allows to relatively easily change between the 4 types of queues
* with very minimal API changes (mostly the types of list heads and fields).
*/
/*!
* @macro smrq_init
*
* @brief
* Initializes an SMR queue head.
*/
#define smrq_init(head) ({ \
__auto_type __head = (head); \
\
smr_init_store(&__head->first, NULL); \
if (__smrq_lastp(__head)) { \
*__smrq_lastp(__head) = &__head->first; \
} \
})
/*!
* @macro smrq_empty
*
* @brief
* Returns whether an SMR queue is empty, can be called from any context.
*/
#define smrq_empty(head) \
(smr_unsafe_load(&(head)->first) == 0)
/*!
* @macro smrq_entered_first
*
* @brief
* Returns the first element of an SMR queue, while in a read section.
*/
#define smrq_entered_first(head, type_t, field) \
__container_of_safe(smr_entered_load(&(head)->first), type_t, field)
/*!
* @macro smrq_entered_next
*
* @brief
* Returns the next element of an SMR queue element, while in a read section.
*/
#define smrq_entered_next(elem, field) \
__container_of_safe(smr_entered_load(&(elem)->field.next), \
typeof(*(elem)), field)
/*!
* @macro smrq_entered_foreach
*
* @brief
* Enumerates an SMR queue, while in a read section.
*/
#define smrq_entered_foreach(it, head, field) \
for (__auto_type __it = smr_entered_load(&(head)->first); \
((it) = __container_of_safe(__it, typeof(*(it)), field)); \
__it = smr_entered_load(&__it->next))
/*!
* @macro smrq_serialized_first
*
* @brief
* Returns the first element of an SMR queue, while being serialized
* by an external mechanism.
*/
#define smrq_serialized_first(head, type_t, link) \
__container_of_safe(smr_serialized_load(&(head)->first), type_t, link)
/*!
* @macro smrq_serialized_next
*
* @brief
* Returns the next element of an SMR queue element, while being serialized
* by an external mechanism.
*/
#define smrq_serialized_next(elem, field) \
__container_of_safe(smr_serialized_load(&(elem)->field.next), \
typeof(*(elem)), field)
/*!
* @macro smrq_serialized_foreach
*
* @brief
* Enumerates an SMR queue, while being serialized
* by an external mechanism.
*/
#define smrq_serialized_foreach(it, head, field) \
for (__auto_type __it = smr_serialized_load(&(head)->first); \
((it) = __container_of_safe(__it, typeof(*(it)), field)); \
__it = smr_serialized_load(&__it->next))
/*!
* @macro smrq_serialized_foreach_safe
*
* @brief
* Enumerates an SMR queue, while being serialized
* by an external mechanism.
*
* @discussion
* This variant supports removing the current element from the queue.
*/
#define smrq_serialized_foreach_safe(it, head, field) \
for (__auto_type __it = smr_serialized_load(&(head)->first), \
__next_it = __it; \
((it) = __container_of_safe(__it, typeof(*(it)), field)) && \
((__next_it = smr_serialized_load(&__it->next)), 1); \
__it = __next_it)
/*!
* @macro smrq_serialized_insert_head
*
* @brief
* Inserts an element at the head of an SMR queue, while being serialized
* by an external mechanism.
*/
#define smrq_serialized_insert_head(head, elem) ({ \
__auto_type __head = (head); \
\
__smrq_serialized_insert(&__head->first, (elem), \
smr_serialized_load(&__head->first), __smrq_lastp(__head)); \
})
/*!
* @macro smrq_serialized_insert_tail
*
* @brief
* Inserts an element at the tail of an SMR queue, while being serialized
* by an external mechanism.
*/
#define smrq_serialized_insert_tail(head, elem) ({ \
__auto_type __head = (head); \
\
__smrq_serialized_insert(__head->last, (elem), \
NULL, &__head->last); \
})
/*!
* @macro smrq_serialized_insert_head_relaxed
*
* @brief
* Inserts an element at the head of an SMR queue, while being serialized
* by an external mechanism, without any barrier.
*/
#define smrq_serialized_insert_head_relaxed(head, elem) ({ \
__auto_type __head = (head); \
\
__smrq_serialized_insert_relaxed(&__head->first, (elem), \
smr_serialized_load(&__head->first), __smrq_lastp(__head)); \
})
/*!
* @macro smrq_serialized_insert_tail_relaxed
*
* @brief
* Inserts an element at the tail of an SMR queue, while being serialized
* by an external mechanism, without any barrier.
*/
#define smrq_serialized_insert_tail_relaxed(head, elem) ({ \
__auto_type __head = (head); \
\
__smrq_serialized_insert_relaxed(__head->last, (elem), \
NULL, &__head->last); \
})
/*!
* @macro smrq_serialized_remove
*
* @brief
* Removes an element from an SMR queue, while being serialized
* by an external mechanism.
*
* @discussion
* The @c head argument is actually unused for the @c smrq_list queue type.
* It is still advised to pass it, the compiler should be able to optimize
* the code away as computing a list head ought to have no side effects.
*/
#define smrq_serialized_remove(head, elem) ({ \
__auto_type __head = (head); \
\
__smrq_serialized_remove(&__head->first, (elem), __smrq_lastp(__head)); \
})
/*!
* @macro smrq_serialized_replace
*
* @brief
* Replaces an element on an SMR queue with another at the same spot,
* while being serialized by an external mechanism.
*/
#define smrq_serialized_replace(head, old_elem, new_elem) ({ \
__auto_type __head = (head); \
\
__smrq_serialized_replace(&__head->first, \
(old_elem), (new_elem), __smrq_lastp(__head)); \
})
/*!
* @macro smrq_serialized_iter
*
* @brief
* Enumerates an SMR singly linked queue, while being serialized
* by an external mechanism.
*
* @discussion
* This is for manual loops that typically perform erasures.
*
* The body of the loop must move the cursor using (once):
* - smrq_serialized_iter_next() to to go the next element,
* - smrq_serialized_iter_erase() to erase the current element.
*
* The iterator variable will _not_ be updated until the next
* loop iteration.
*
* This form is preferred to smrq_serialized_foreach_safe()
* for singly linked lists as smrq_serialized_iter_erase()
* is O(1) as opposed to smrq_serialized_remove().
*/
#define smrq_serialized_iter(it, head, field) \
for (__smrq_slink_t *__prev_##it = &(head)->first, \
*__chk_##it = __prev_##it; \
((it) = __container_of_safe(smr_serialized_load(__prev_##it), \
typeof(*(it)), field)); \
assert(__chk_##it), __chk_##it = __prev_##it)
/*!
* @macro smrq_serialized_iter_next
*
* @brief
* Goes to the next element inside an smrq_serialied_iter() loop.
*/
#define smrq_serialized_iter_next(it, field) ({ \
assert(__chk_##it == __prev_##it); \
__chk_##it = NULL; \
__prev_##it = &(it)->field.next; \
})
/*!
* @macro smrq_serialized_iter_erase
*
* @brief
* Erases the element pointed at by the cursor.
*/
#define smrq_serialized_iter_erase(it, field) ({ \
assert(__chk_##it == __prev_##it); \
__chk_##it = NULL; \
__smrq_serialized_remove_one(__prev_##it, &(it)->field, NULL); \
})
/*!
* @macro smrq_serialized_append
*
* @brief
* Appends a given list at the end of the previous one.
*
* @discussion
* /!\ WARNING /!\: this doesn't "move" the "source" queue like *_CONCAT
* for <sys/queue.h>, as it is useful to merge/split hash queues concurrently
* with readers while allowing readers to still read via the "source" queue.
*
* However, the "source" queue needs to be reset to a valid state
* if it is to be used again.
*/
#define smrq_serialized_append(dst, src) ({ \
__auto_type __src = (src); \
__auto_type __dst = (dst); \
\
__smrq_serialized_append(&__dst->first, __smrq_lastp(__dst), \
&__src->first, __smrq_lastp(__src)); \
})
#pragma mark SMR domains
/*!
* @enum smr_flags_t
*
* @brief
* Options to pass to smr_domain_create()
*
* @const SMR_NONE
* Default values for the flags.
#if XNU_KERNEL_PRIVATE
*
* @const SMR_SLEEPABLE
* Create a sleepable SMR domain.
#endif
*/
__options_closed_decl(smr_flags_t, unsigned long, {
SMR_NONE = 0x00000000,
#if XNU_KERNEL_PRIVATE
SMR_SLEEPABLE = 0x00000001,
#endif
});
/*!
* @function smr_domain_create()
*
* @brief
* Create an SMR domain.
*
* @discussion
* Be mindful when creating SMR domains, and consider carefully
* whether to add one or consolidate an existing one.
*
*
* Memory usage
* ~~~~~~~~~~~~
*
* SMR domains are fairly large structures that scale with the number
* of cores of the machine. They are meant to be use in a coarse grained
* manner.
*
* In addition to that, when @c smr_call() is used with the domain,
* the queues of callbacks are drained based on memory pressure within
* the domain. The more domains, the more dormant memory might exist.
*
* In general, memory considerations drive toward less domains.
*
*
* Scalability
* ~~~~~~~~~~~
*
* An SMR domain is built on top of an atomic state that is used
* to perform grace period detection. The more "write" activity
* there is on the domain (@c smr_call(), @c smr_advance(), etc...),
* the more this atomic might become contended. In particular,
* certain usage patterns might scale extremely well independently,
* but cause higher contention when sharing a domain.
*
* Another thing to consider is that when @c smr_call() is being used,
* if the callbacks act on vastly different data structures, then as
* the callbacks are being drained, cache misses will be higher.
*
* However, the more domains are in use, the more probable it is
* that using it will cause a cache miss.
*
* Generally, scalability considerations drive toward balanced
* coarse-grained domains.
*
*
* Invariants
* ~~~~~~~~~~
*
* The last aspect leading to the decision of creating versus reusing
* an SMR domain is about the invariants that these domains protect.
*
* Object graphs that are protected with SMR and are used together
* in many workloads will likely require to share an SMR domain
* in order to provide the required guarantees. Having @c smr_call()
* callbacks in a given domain cause downstream @c smr_call() into
* another different domain regularly is probably a sign that these
* domains should be shared.
*
* Another aspect to consider is that using @c smr_synchronize()
* or @c smr_barrier() can lead to two classes of problems:
*
* - these operations are extremely heavy, and if some subsystem needs to
* perform them on several domains, performance will be disappointing.
*
* - these operations are akin to taking a "write lock" on the domain,
* and as such can cause deadlocks when used improperly.
* Using a coarser grained unique domain is a good way to simplify
* reasoning about the locking dependencies between SMR domains
* and other regular locks.
*
*
* Guidance
* ~~~~~~~~
*
* In general, the entire kernel should have relatively few SMR domains,
* at the scale of the big subsystems of the kernel (think: Mach IPC, Mach VM,
* VFS, Networking, ...).
*
* When write operations (@c smr_call(), @c smr_synchronize, ...) are used
* rarely, consider using the system wide default domains.
*/
extern smr_t smr_domain_create(smr_flags_t flags, const char *name);
/*!
* @function smr_domain_free()
*
* @brief
* Destroys an SMR domain previously create with @c smr_domain_create().
*/
extern void smr_domain_free(smr_t smr);
/*!
* @function smr_entered()
*
* @brief
* Returns whether an SMR critical section is entered.
*/
extern bool smr_entered(smr_t smr) __result_use_check;
/*!
* @function smr_enter()
*
* @brief
* Enter a non preemptible SMR critical section.
*
* @discussion
* Entering an SMR critical section is non reentrant.
* (entering it recursively is undefined and will panic on development kernels)
*
* @c smr_leave() must be called to end this section.
*
* This function can'be be used in interrupt context.
*/
extern void smr_enter(smr_t smr);
/*!
* @function smr_leave()
*
* @brief
* Leave a non preemptible SMR critical section.
*/
extern void smr_leave(smr_t smr);
/*!
* @function smr_call()
*
* @brief
* Defer making a call until it is safe to assume all readers
* will observe any update prior to this call.
*
* @discussion
* The target SMR domain must NOT be entered when making this call.
*
* The passed @c size doesn't have to be precise, it should be a rough
* estimate of the memory that will be reclaimed when when the call is made.
*
* This function gives no guarantee of forward progress,
* unless the magic SMR_CALL_EXPEDITE size is passed to @c smr_call().
*
* This function can'be be used in interrupt context.
*/
extern void smr_call(smr_t smr, smr_node_t node, vm_size_t size, smr_cb_t cb);
#define SMR_CALL_EXPEDITE ((vm_size_t)~0)
/*!
* @function smr_synchronize()
*
* @brief
* Wait until all readers have observed any updates made prior to this call.
*
* @discussion
* The target SMR domain must NOT be entered when making this call.
*
* This function is quite expensive, and asynchronous deferred processing
* using @c smr_call() should be used instead when possible.
*
* Reserve using this call for events that are extremely rare (like system
* configuration events such as configuring networking interfaces, changing
* system wide security policies, or loading/unloading a kernel extension).
*
* This function should typically be called with preemption enabled,
* and no locks held.
*/
extern void smr_synchronize(smr_t smr);
/*!
* @function smr_barrier()
*
* @brief
* Wait until all readers have observed any updates made prior to this call,
* and all @c smr_call() callbacks dispatched prior to this call on any core
* have completed.
*
* @discussion
* The target SMR domain must NOT be entered when making this call.
*
* This function is typically used when some data structure is being
* accessed by @c smr_call() callbacks and that data structure needs
* to be retired.
*
* Reserve using this call for events that are extremely rare (like system
* configuration events such as configuring networking interfaces, changing
* system wide security policies, or loading/unloading a kernel extension).
*
* This function should typically be called with preemption enabled,
* and no locks held.
*/
extern void smr_barrier(smr_t smr);
#ifdef XNU_KERNEL_PRIVATE
#pragma GCC visibility push(hidden)
#pragma mark - XNU only
#pragma mark XNU only: SMR domains advanced
#define SMR_SEQ_INVALID ((smr_seq_t)0)
#define SMR_SEQ_SLEEPABLE ((smr_seq_t)1) /* only on smr_pcpu::rd_seq */
#define SMR_SEQ_INIT ((smr_seq_t)2)
#define SMR_SEQ_INC ((smr_seq_t)4)
typedef long smr_delta_t;
#define SMR_SEQ_DELTA(a, b) ((smr_delta_t)((a) - (b)))
#define SMR_SEQ_CMP(a, op, b) (SMR_SEQ_DELTA(a, b) op 0)
/*!
* @typedef smr_clock_t
*
* @brief
* Represents an SMR domain clock, internal type not manipulated by clients.
*/
typedef struct {
smr_seq_t s_rd_seq;
smr_seq_t s_wr_seq;
} smr_clock_t;
#define SMR_NAME_MAX 24
/*!
* @typedef smr_t
*
* @brief
* Declares an SMR domain of synchronization.
*/
struct smr {
smr_clock_t smr_clock;
struct smr_pcpu *smr_pcpu;
unsigned long smr_flags;
unsigned long smr_early;
char smr_name[SMR_NAME_MAX];
} __attribute__((aligned(64)));
/*!
* @macro SMR_DEFINE_FLAGS
*
* @brief
* Define an SMR domain with specific create flags.
*/
#define SMR_DEFINE_FLAGS(var, name, flags) \
struct smr var = { \
.smr_clock.s_rd_seq = SMR_SEQ_INIT, \
.smr_clock.s_wr_seq = SMR_SEQ_INIT, \
.smr_flags = (flags), \
.smr_name = "" name, \
}; \
STARTUP_ARG(TUNABLES, STARTUP_RANK_LAST, __smr_domain_init, &(var)); \
STARTUP_ARG(ZALLOC, STARTUP_RANK_LAST, __smr_domain_init, &(var))
/*!
* @macro SMR_DEFINE
*
* @brief
* Define an SMR domain.
*/
#define SMR_DEFINE(var, name) \
SMR_DEFINE_FLAGS(var, name, SMR_NONE)
/*!
* @macro SMR_DEFINE_SLEEPABLE
*
* @brief
* Define a sleepable SMR domain.
*/
#define SMR_DEFINE_SLEEPABLE(var, name) \
SMR_DEFINE_FLAGS(var, name, SMR_SLEEPABLE)
/*!
* @function smr_advance()
*
* @brief
* Advance the write sequence and return the value
* for use as a wait goal.
*
* @discussion
* This guarantees that any changes made by the calling thread
* prior to this call will be visible to all threads after
* the read sequence meets or exceeds the return value.
*/
extern smr_seq_t smr_advance(smr_t smr) __result_use_check;
/*!
* @function smr_deferred_advance()
*
* @brief
* Pretend-advance the write sequence and return the value
* for use as a wait goal.
*
* @discussion
* This guarantees that any changes made by the calling thread
* prior to this call will be visible to all threads after
* the read sequence meets or exceeds the return value.
*
* Unlike smr_advance(), the global clock isn't really advanced,
* it only sets a goal in the future. This can be used to control
* the pace of updating the global clock and avoid global atomics.
*
* In order for the clock to advance, clients of this API must call
* @c smr_deferred_advance_commit() with the goal returned by this call.
*
* Note that calls to @c smr_advance() or @c smr_wait() when passed
* the goal returned by this function would also allow the clock
* to make progress and are legal (yet less efficient) calls to make.
*/
extern smr_seq_t smr_deferred_advance(smr_t smr) __result_use_check;
/*!
* @function smr_deferred_advance_commit()
*
* @brief
* Actually advance the write sequence to the goal returned by a previous
* call to @c smr_deferred_advance().
*/
extern void smr_deferred_advance_commit(smr_t smr, smr_seq_t seq);
/*!
* @function smr_poll
*
* @brief
* Poll to determine whether all readers have observed the @c goal
* write sequence number.
*
* @discussion
* This function is safe to be called from preemption disabled context
* and its worst complexity is O(ncpu).
*
* @returns true if the goal is met and false if not.
*/
extern bool smr_poll(smr_t smr, smr_seq_t goal) __result_use_check;
/*!
* @function smr_wait
*
* @brief
* Wait until all readers have observed
* the @c goal write sequence number.
*
* @discussion
* This function is safe to be called from preemption disabled context
* as it never explicitly blocks, however this is not recommended.
*/
extern void smr_wait(smr_t smr, smr_seq_t goal);
#pragma mark XNU only: major sleepable SMR domains
/*
* Note: this is private for now because sleepable sections that do "bad" things
* (such as doing an upcall to userspace, or doing VM allocations) have
* the danger that they can stall the reclamation worker threads,
* which are a singleton resource.
*
* Until this can be mitigated or designed better, this stays private.
*/
/*!
* @typedef smr_tracker_t
*
* @brief
* Structure used to track active sleepable SMR sections.
*
* @field smrt_domain the entered SMR domain
* @field smrt_seq the SMR sequence at the time of smr_enter_sleepable().
* @field smrt_link linkage used to track stalled sections.
* @field smrt_stack linkage used to track entered sections.
* @field smrt_ctid (if stalled) the ctid of the thread in this section.
* @field smrt_cpu (if stalled) the cpu the thread was on when stalled.
*/
typedef struct smr_tracker {
smr_t smrt_domain;
smr_seq_t smrt_seq;
struct smrq_link smrt_link;
struct smrq_slink smrt_stack;
uint32_t smrt_ctid;
int smrt_cpu;
} *smr_tracker_t;
/*!
* @function smr_enter_sleepable()
*
* @brief
* Enter a sleepable SMR critical section.
*
* @discussion
* Entering an SMR critical section is non recursive
* (entering it recursively is undefined and will panic on development kernels)
*
* @c smr_leave_sleepable() must be called to end this section,
* passing the same tracker pointer.
*
* The SMR domain must have been created with the @c SMR_SLEEPABLE flag.
*
* It is permitted to do operations that might block under such a transaction,
* such as acquiring a lock, or freeing memory.
*
* It is forbidden to perform operations that wait for an unbounded amount of
* time such as waiting for networking packets or even a hardware driver event,
* as these could cause grace periods (and memory reclamation) to stall for
* a very long time.